PDM research project

M3T: Multiresolution representation of threedimensional objects with tangent planes (1-11-2003 to 31-10-2004) (Posdoc, FWO)

Subdivision, tangent scheme

Subdivision is a powerful mechanism for the construction of smooth curves and surfaces. The main idea is to start with a set of initial coefficients which live on the coarsest domain grid and then iterate upsampling, that is inserting new vertices in the grid, and local averaging on the corresponding coefficients to build complex geometrical shapes. Recently we developed a new subdivision scheme, the tangent scheme [1]. Is it is a generalization of uniform Powell- Sabin spline subdivision [2] to arbitrary topologies. Instead of a control point there is for each vertex a control triangle that is tangent to the surface. The scheme converges and in the regular parts the surface is a Powell-Sabin spline surface. We can choose the derivatives in the the tangent points and control the surface more exactly. The additional degrees of freedom with the tangents create more modelling possibilities. It is a spline based scheme, but unlike other spline subdivision schemes, it is not approximating but interpolating in the tangent point.

1. Modelling of special features

   We observed that the limit surface is not only influenced by the direction of the tangents, but also by the size of the control triangles. Big control triangles yield smooth rounded edges, and smaller control triangles yield sharper corners. We will investigate what happens if a control triangle reduces to a line or a point. Will the scheme still converge? How do the newly introduced control triangles behave in the neighborhood of degenerate control triangles? Can we model special effects? From the theory of Powell-Sabin splines we know that when the control triangle grows, the corresponding basis functions become linearly dependent [3]. We will analyze if this has effect on the limit surface and the convergence. For most subdivision schemes special rules have been developed to model cusps. We want to do this with the tangent scheme by placing the control triangles perpendicular to the surface. The corners of the control triangles must be ordened anti-clockwise so that the normal points to the exterior of the surface. This is essential for the practical implementation. We will try to overcome this practical problem.

2. Initial control net

   The polyhedron that serves as the coarse base mesh for subdivision is typically given as a connected set of three dimensional points. In the case of the tangent scheme we need a control triangle, or in other words we also need the tangents in each point. This kind of input is not always available. We will design an algorithm to automatically calculate control triangles for an initial base poyhedron. These can be used as a starting point and adjusted to achieve the previously mentioned special effects.

3. Remeshing

   The goal of remeshing techniques is to approximate a mesh with irregular topolgy with a semi-regular mesh. This is useful because many multiresolution techniques require the input to have subdivision connectivity. We are interested in the technique of normal meshes [4]. First a mesh simplification procedure is applied to the irregular input mesh to yield a coarse base mesh. Then a subdivision algorithm is applied to the coarse mesh and an approximation of the normal in the new points is calculated. Finally a piercing procedure is applied to find the intersection of the irregular mesh and the normal. The intersection point will be used instead of the point found by subdivision. Steps 2-4 are repeated until the approximation criteria are satisfied. We will use the tangent scheme to build normal meshes. The mesh simplification step needs to be adapted to yield a base mesh with information on the tangents or alternatively we can use a standard mesh simplification algorithm and then apply an algorithm to find initial control triangles as in item 2. The main advantage of the tangent scheme lies in the fact that no approximations of normals need to be calculated based on the coarse mesh. The normal is given for free because the control triangles are tangent to the subdivision surface. The approximation order of a normal remesher depends on the approximation order of the underlying subdivision scheme. In the original algorithm only a linear subdivision scheme is used.

4. Wavelet decomposition

   A subdivision scheme defines a sequence of nested spaces. A surface on a finer level can describe more detail than a surface on a coarser level. The basis functions that span these spaces are called scaling functions. Wavelets capture the difference between succesive levels of subdivision. Wavelet functions span the complement space between two spaces in the nested sequence. The mathematical properties of wavelets are well understood in the functional setting, i.e. for the approximation of functions of one of more variables. However, for the case of curves in the plane or surfaces in the three dimensional space much less is known. In that case typically parametric representation are used where the geometry is given by a vector valued function. The wavelet analysis is then done in each of the components, and the wavelet coefficients are also vector valued. The normal mesh technique is designed to produce detail or wavelet coefficients with no tangential compoments. The wavelet vectors perfectly align with the locally defined normal direction. Then only one scalar coefficient needs to be stored instead of the standard vector. We will build a normal multiresolution based on the tangent scheme. If the only goal is remeshing we can interpret the detail coefficients as the distance the control triangle has to be translated via the normal. In a more general context we actually need three wavelet vectors because we also have three scaling vectors. Apart from reducing the vectors to a scalar it would also be useful to design a method to store other details than translation of the control triangles.

References

[1] E. Vanraes and A. Bultheel, The tangent scheme, ACM Trans. Graph., 2004. Aangeboden ter publicatie.
[2] J. Windmolders and P. Dierckx, Subdivision of uniform Powell-Sabin splines, Comput. Aided Geom. Design 16 , pp. 301-315, May, 1999.
[3] E. Vanraes, P. Dierckx and A. Bultheel, On the choice of the PS-triangles, Department of Computer Science, K.U.Leuven, Report TW 353, Leuven, Belgium, February, 2003.
[4] I. Guskov, K. Vidimce, W. Sweldens and P. Schröder, Normal meshes, Computer Graphics Proceedings (SIGGRAPH 2000), pp 95-102, 2000.