Recursive Algorithms for 3D Triangulation Decomposition and 2D Parameterization

In practical applications, we usually use surfaces of lower degree and less number of patches to interpolate irregular data points so that operations applied on these surfaces can run efficiently and robustly. In this paper, we propose a recursive and adaptive method to construct a G(exp1) (first order geometric continuity) cubic triangular Bernstein-Bezier surface over an arbitrary triangulation derived from a given set of irregular data points. For a surface triangulation delta of n sample points in 3D spaces, a monotonic sequence of triangulations delta contains delta(exp1) contains delta(exp2) contains ... contains delta(exp n-3) is constructed by removing a boundary vertex P and all triangles sharing with P at each step, where delta (exp n-3) is composed of a single triangle. The shape parameters in the G(exp 1) conditions are determined by a corresponding 2D triangulation delta that is actually a parameterization of the constructed surface. Delta (-) has the same topology with delta and is derived inductively according to the triangulation sequence in 3D. According to the parameterization, the desired smooth cubic surface can then be constructed recursively over the reversed sequence of triangulations delta(exp n-3) contains ... contains delta (exp 2) contains delta (exp 1) contains delta in 3D.