Local Deformation Of Subdivision Curves And Surfaces

Surface modeling method is one of the research emphases all the time, and what it focuses on is the denotation, design, display, and analysis of surface under the environment of computer graphics system. Subdivision is one method to denote surface, a branch of the research emphases of surface modeling. Prom the metaphase and anaphase of 70's in the 20th century, with the development of subdivision theories and the expansion of application fields, Subdivision modeling methods have been put into wider application in computer graphics, computer aided geometric design (CAGD), computer animation, and virtual reality (VR) etc. In fact, subdivision is a method that recursively computes the new vertices, which are averaged with weight by old vertices in previous level, from the initial polyhedron named control mesh. The biggest advantage of subdivision method is that it can generate smooth surface from arbitrary initial mesh. However, in the practical application, we perhaps do not satisfy with the local shape of subdivision curves or surfaces. In order to solve this problem, in this thesis, we begin with the curve case, and develop a practical local deformation algorithm to change the part which is not satisfied with design requirement, using least square method to control the error between design requirement and the curve after deforming. Furthermore, we also present a similar algorithm in the case of subdivision surfaces. The main work is as follows:Firstly, for subdivision curve case, we present a local deformation algorithm as follows:STEP1: We assume that there is the initial control polygon and the corresponding subdivision curve. Let P_i(i = 0,1, …, n) be the points of the initial control polygon, and give the curve segment which we want to obtain after deformation in local part. Meanwhile, we select some points Qi(i — 0,1, … , m) in this curve segment, named sampling point.STEP2: For every point Qi, we find the closest point to each Q_i in the subdivisioncurve, and use LPi(i = 0,1, ? ? ? , m) to denote these points.STEP3: Determine the points that are needed to change in the initial control polygon, the detail is given as follows. Let Qo, Qi be the endpoint of the curve segment, utilizing these two points to construct a line I. Here, we assume all other sampling points are located at one side of I, then we can use I to divide the initial control points into two sets:A = {Pi\l(Pi) >0};B = {PMPj) < 0}Next, we select one point Qk among Qi (except endpoint) and determine the value of l(Qk), whether it is smaller than zero or not. If l(Qk) > 0 , then we will find the points in set .A(if there is no point in set A, we assume that this case is beyond the local deformation range, and do not deal with it);otherwise, we will choose set B. Here, we may choose set A, and project all points of A onto the line I, after that, we find the projective points in the interval QoQi, then change the initial control points which are relevant to these projective points. If there is no projective point in the interval Q0Q1, for Qo and Q%, we find the closest point in the initial control points and change them.STEP4: The closest points corresponding to the sampling points in the subdivision curve are LPi(i = 0,1, ??? ,m), let L'Pi(i = 0,1,??? ,m) be the points corresponding to LPi(i = 0,1, ? ■ ? , m) after deformation. Therefore, our goal is to obtain the proper changed initial control points to minimize the objective function:n> _i=0Let TPiii = 0,1, ? ? ? ,k) be the initial control points which are needed to change, their coordinates are denoted with (xi,yi)(i — 0,1, ? ? ? ,k). While substituting the objective function S with these (xi,yi), we could notice that 5 is polynomial in Xi,yi of degree 2. Due to the independence of x, y, we also could divide the objective function, and rewrite it in the following form:k kq — ' f \~* ? 4- \^ h 4- X~* , j \t=0 fc>i,j>0,t^i i=0k kSy = minCjT, OyiVi + Y, ^jViVj + 5Z?=0 k>i,j>O,ift ?=0Therefore, what we really want to do is just to obtain the minimum of Sx,Sy.Next, In the case of subdivision surfaces, Because other steps are similar, so we will focus on the step 3 and 4.STEP3: Among the sampling points, we select 3 points properly to construct a plane n, and it reflects the design requirement. We also assume that other sampling points are located at one side of this plane. In the following, we consider projecting all sampling points onto this plane, and use the extreme value of projective points to construct one bounding box such that this bounding box contains all sampling points, then similar to the subdivision curve case, we choose one set, and project points of set onto the plane it, then find the projective points that are included in the bounding box, finally, change the initial control points corresponding to these projective points. If there is no point in the bounding box, for every corner point of bounding box, we find the closest point among the initial control points respectively, then we change these initial control points.STEP4: We should notice that owing to the subdivision surface case, when writing objective function , there will be one more expression with respect to z coordinate. Hence,the expression is:k kSx = min(Y^ axixf + ^ bxijXiXj + ^ CxiXi + dx)i=0 fe>?,j>O,?/j i=0k kSy = min(J2 aviVit=0 A;kSz = min(*T aziZ? + JZ b^ZiZj + ^ cziZi + dz)i=0 k>i,j>O,ijtj i=0and then , what we should do is to obtain the minimum of Sx,Sy,Sz.In addition, If we want to attain the minimum of Sx,Sy,Sz, we only should know the Oxii bxij, cxi,dx, a-yi, byij,Cyi,dy,azi, bzij,cz{, dz. Because the expressionSx,Sy,Sz are derived after serval times subdivision , it is not easy to obtain them directly, so here,we apply the interpolating method to solve this problem, and deal with the curve case in a similar way.