Research On Shape Optimization For Discrete Curves And Surfaces

Discrete data modeling and processing is an important research topic in computer aided design, computer graphics and computer animation. On the one hand, because existing technologies on data acquisition, data transmission and data storage have many limitations, the shape of curves and surfaces must be of many defects inevitably. On the other hand, the required shape quality of curves and surfaces often varies according to the different applications. Hence, shape optimization has been an inportant topic in discrete data modeling and processing. In this paper, we investigate the problem of 2D and 3D shape optimization and some associated algorithms in discrete data modeling.This paper presents three main contributions. Firstly, as for the planar shape represented by discrete curves. Two curve smoothing algorithms are presented based on previous works. The first one is based on the scaling invariant intrinsic variables of planar discrete curves and angle filtering. The orientation angles of scaling invariant intrinsic variables can reflect its degree of smoothing locally and its shape feature globally. The sequence of the original curve's orientation angles is smoothed by a bilateral filtering, then the smoothed curve is reconstructed by the filtered scaling invariant variables. The second algorithm interpretates the curve smoothing as the compromise between the ramoval of noise and preservation of feature and introduce a quadratic energy related to the vertices of the smoothed curve based on the weighted least squares. The final smoothed curve is get by minimizing the quadratic energy. Experiments have shown that these two algorithms can not only remove noise but also preserve detail features.Secondly, we found that it is necessary to take both the boundary of shape and the interior of shape such as skeleton and triangulation into consideration in the context of shape editting and interpolation. Because small disturbance on the bounday of polygon often leads to some unnecessary branches in the extracted skeleton, a feature preserving approach for extracting approximated skeleton of planar polygon is proposed in order to solve this problem. Prong features guided as branch tips of skeleton are detected firstly by watershed algorithm, then an approximated joggling-free skeleton of the polygon is obtained. In order to overcome the inefficience and poor quality of existing algorithms on compatible triangulations, an approach for fast building high quality compatible triangulations between two planar polygons is presented. Specifically, an uniform triangulation for the first polygon is easily constructed by introducing some Steiner points on both the boundary and the interior, then its connectivity is transferred onto the second polygon, whose vertices'positions are determined by the relative geomtric measure in the first triangulation. Finally a joint optimization is emplyed to obatin high compatibility between these two triangulations. This approach is not only suitable for two polygons but also suitable for multiple polygons. An algorithm for planar shape blending is also introduced based on this compatible triangulations, this approach can preserve the similarity of the interiors of the polygons and can avoid local expansion and shrinkage.Finally, as for the 3D discrete surfaces represented by triangular mesh, a feature-preserving mesh smoothing algorithm based on the weighted least squares is proposed. A discrete quadratic energy related to the smoothed mesh vertices or normal is introduced, which considers not only the overall smoothness of the mesh but also the preservation of the fine features of the original model. Then a quadratic objective function based on this energy is minimized by solving a sparse linear system to get the smoothed mesh. The mesh segmentation is explicitly interpreted as the problem of transductive learning:Given a set of user-supplied labeled vertices as the training set, the algorithm needs to learn the label for the rest unlabeled vertices which are taken as the test set, and the weighted graph Laplacian method is employed to approximate the accurate solution in a transductive learning process, making the segmentation alogrithm much faster.