Solving geometric constraint systems in 3-D is much more complicated than that in 2-D because the number of variables is larger and some of the results valid in 2-D cannot be extended for 3-D. In this paper, we propose a new DOF-based graph constructive method to geometric constraint systems solving that can efficiently handle well-, over- and under-constrained systems based on the dependence analysis. The basic idea is that the solutions of some geometric elements depend on some others because of the constraints between them. If some geometric elements depend on each other, they must be solved together. In our approach, we first identify all structurally redundant constraints, then we add some constraints to well constrain the system. And we prove that the order of a constraint system after processing under-constrained cases is not more than that of the original system multiplied by 5. After that, we apply a recursive searching process to identify all the clusters, which is shown to be capable of getting the minimum order-reduction result of a well-constrained system. We also briefly describe the constraint evaluation phase and show the implementation results of our method.

This paper presents an algorithm for extending B-spline curves and surfaces. Based on the unclamping algorithm for B-spline curves, we propose a new algorithm for extending B-spline curves that extrapolates using the recurrence property of the de Boor algorithm. This algorithm provides a nice extension, with maximum continuity, to the original curve segment. Moreover, it can be applied to the extension of B-spline surfaces. Extension to both single and multiple target points/curves are considered in this paper.

This paper addresses the problem of approximate merging of two adjacent B-spline curves into one B-spline curve. The basic idea of the approach is to find the conditions for precise merging of two B-spline curves, and perturb the control points of the curves by constrained optimization subject to satisfying these conditions. To obtain a merged curve without superfluous knots, we present a new knot adjustment algorithm for adjusting the end k knots of a kth order B-spline curve without changing its shape. The more general problem of merging curves to pass through some target points is also discussed.

Mesh parameterization is a key problem in digital geometry rocessing. By cutting a surface along a set of edges (a seam), one can map an arbitrary topology surface mesh to a single chart. Unfortunately, high distortion occurs when protrusions of the surface (such as fingers of a hand and horses’ legs) are flattened into a plane. This paper presents a novel skeleton-based algorithm for computing a seam on a triangulated surface. The seam produced is a full component Steiner tree in a graph constructed from the original mesh. By generating the seam so that all extremal vertices are leaves of the seam, we can obtain good parametrization with low distortion.

When two topologically identical shapes are blended, various possible transformation paths exist from the source shape to the target shape. Which one is the most plausible? Here we propose that the transformation process should obey a quasi-physical law. This paper combines morphing with deformation theory from continuum mechanics. By using strain energy, which reflects the magnitude of deformation, as an objective function, we convert the problem of path interpolation into an unconstrained optimization problem. To reduce the number of variables in the optimization we adopt shape functions, as used in the finite element method (FEM). A point-to-point correspondence between the source and target shapes is naturally established using these polynomial functions plus a distance map.