A Class Project for ME758 under Professor Vadim Shapiro

Fitting B-Spline Surfaces to Polygonal Soup

Introduction:

 

• Improvements in Patches creation:

• Manual  Path  Approach:  Instead of relying solely on mouse interaction for curves creatios process, we use exact and approximate shortest path on the polygonal model (also called geodesics) . For large models, users need to click very few number of landmarks nodes on the model and the algorithm automatically joins these landmark nodes with the shortest path reducing the time significanly.

• Automatic Path Approach:  
  
• One of the proven approach for transforming triangular mesh into high quality quadrilateral mesh with bounded quality is based on Graph Matching algorithm. Although this approach was also adopted by Eck and Hoppe, but significant time reduction can be achieved by using approximate tree matching ( proposed by Suneeta' Ramaswamy ) than an expact Edmond's  Blossum Algorithm.   We believe that Edmond's perfect graph matching is an overkill for this application.

• Once we have quadrilateral mesh which may have many irregular nodes ( valency != 4 ), therefore, the next step is to perform Quadmesh Cleanup operations to maximize the regularity of the mesh.

• The third and final step is the generation of  quad patches that have structured mesh topology. We implemented Motorcycle Graph to partition quad mesh partitioning into structured patches.

• Surface Fitting and Stitching Approach:
  

• We implemented both constrained (Milroy)  and non-constrained least square methods with Tikhonov regularization to get smooth patches.
  

• For extremely  large models, the least square solution could be extremely time consuming ( and possibly unwanted also) , we used RANSAC ( RANdom SAmple Consensus) algorithm for sampling small number of surface points for control points evalution.

• Since surface fitting is an iterative two step process i.e.

• Fitting Step:  For a given parameterization of surface points, obtain the control points using least square solvers.

• Reparmeterization Step:  For given control points, adjust the paremeter values ( u,v) of the surface points.

                The initial parameterization have influence on the performance of the iterative solver. The initial parameterization of a given quad patch which is homeomorphic to a open disk is done by                         either (1) Floater parameterization (2) Harmomic Map Parameterization.

Mathamatical Formulation:

The general equation of B-Spline is given as

Where C(i,j) are control points and B(u) and B(v) are the basis functions in the "u" and "v" direction respectively. This equation can be written in the matrix form as

In the surface fitting problem, the unknown quantities are the control points, which can be obtained using least square solution as

This raw formulation doesn't guarantee smoothness of control points values, therefore, some regularization is performed so that the norm of control points is also minimized. This leads
to standard "Tikhnov Regularization".

Here Gamma is any suitable matrix, but in our implementation it is set to identity matrix. Therefore, the modified controls points are given by

Even after regualization, there is no guarantee that control points of the adjacent patches will match, if they don't match, then the resulting model will not be watertight and seams will be visible in the model. In order to provide G1 continuity, we will use "constrained least square problem".  With this approach. the boundary controls points are fixed and only the internal control points are determined  using the least square solution. The initial values of the control points is determined from the unconstrained least square solution  described above. This ensures that the boundry control points are fixed. However, this simplicity assumes that the number of controls points are the same on two adjacent surfaces therefore, this requirement probihibtes using adaptive controls points.   

Once we have control points for each patch, the determination of full resolution mesh is simple.

Results:

Cylinder : 8 Patches	Torus : 8 patches	Bunny 50 patches.	Foot 64 patches.

Note that in these figure, tangent discontinuity is not resolved properly, but visually it is absent. Mathematically, there might be someshort comings in our approach to ensure C2 continuity.

Conclusions:

Both manual and automatic approches have advantages in creating high quality B-Spline patches creations and in this project, we have made an attempt an engineering attempt  to improve both the methods. Although our present results have shown good quality, but it still has one serious problem that the quadrilateral mesh may not be curvature aligned. There are some premature ideas of generating vector field over the model to give some feedback to facilitate an user to create nice patches, but this is the work for the future.

Software Information:

Bibliography:

• Fitting Smooth Surfaces to Dense Polygonal

• Mesh Venkat Krishnamurthy and Marc Levoy ( 1996)

• Automatic Reconstruction of B-Spline Surfaces of Arbitrary Topology type
  

•  ( M. Eck and H. Hoppe 1996)

• Fast Exact and Approximate Geodesics on Meshes
  
• ( V. Surazhsky, T. Surazhsky, D. Kirsanov, S. Gortler and H.Hoppe 2005)

• Multiresolution Analysis of Arbitray Meshes

• ( M.Eck, T. DeRose, T. Duchamp, H.Hoppe, M. Lounsbery and W. Stuetzle 1995)

• G1 Continuity of B-Spline Surface Patches in Reverse Engineering
  
• ( M.J. Milroy, C Bradley, G W Vickers and DJ Weir )