User:Southdii
From K-3D
Quadrilateral Remeshing
Proposal
Abstract
The goal of this project is to improve the Quadrilateral Remeshing K-3D plug-in by using a different algorithm that requires less user input. The current implementation requires the user to specify extrema points on the mesh. The proposed alternative algorithm for the plug-in will create a quad-dominant mesh that is aligned with the principal curvature directions.
Detailed Description
Quadrilateral remeshing is the process of taking a triangular mesh and producing a mesh primarily made of quads and has the same shape as the original mesh. This can lower the number of elements to save memory and computation time while still preserving the shape, and be better suited for some subdivision schemes.
K-3D's current implementation of quad remeshing is based off of the paper "Harmonic functions for quadrilateral remeshing of arbitrary manifolds". To quadrangulate a mesh with this method, the user must specify min and max extrema vertices on the mesh. Using these vertices, a harmonic scalar field is generated on the surface of the mesh such that the extrema of the field are at the specified vertices. The method then constructs two vector fields along the surface, one is the gradient of the scalar field, and the other is perpendicular to the gradient. These vector fields are traced to produce two families of lines on the surface, where the lines and their intersections are used to construct a quad mesh.
A good description of this process along with pictures can be found on the K-3D website: http://wiki.k-3d.org/QuadrilateralRemeshing
Using this method introduces a few problems because of the need for the user to give extra information by specifying the extrema vertices. What are good points on a mesh to specify as extrema? Good extrema are at the end points of shape features, such as the finger tips in a hand model. If improper extrema points are chosen, a poor quality mesh will be constructed, for example in this image: http://wiki.k-3d.org/Image:QR_other.png
In addition, by requiring user input, the algorithm cannot be automated, such as quadrangulating a shape that is changing with time. If the mesh is deformed in such a way that the specified extrema points are no longer good choices, then the user would need to intervene. A better implementation choice for this plug-in would be to use a quadrangulating method that produces good quality meshes without user input.
One such method is based off of the parameterization algorithm described in the recent paper "Periodic Global Parameterization" by Nicolas Ray, et al. This method takes as input two perpendicular vector fields on the mesh, and produces a parameterization of the mesh such that the gradient of the parameterization variables are aligned with the vector fields. The level curves can then be used to construct a quad mesh that is aligned with the input vector fields. The best choices for vector fields are the principal curvature directions, which specify the directions of maximum and minimum curvature.
For this project I will create a Quadrilateral Remeshing K-3D plug-in using some of algorithm described in the "Periodic Global Parameterization" paper. The full algorithm is not needed to generate a quad-dominant mesh. Once each triangle has its own linear parameterization, we can find the iso-lines for each triangle. These will correspond to the iso-lines of the global parameterization, and can be combined to create the quad mesh.
Plan
This project can be split into three separate parts: principal curvature directions, remeshing, and if time allows, vector field smoothing and curl correction.
Before remeshing can be done, we will need to find the principal curvature directions of the mesh. They could be found by implementing the method described in the paper "Anisotropic Polygonal Remeshing" by Pierre Alliez, et al. An alternative would be to use the GNU Triangulated Surface Library (GTS) to find the principal curvature directions.
Vector field smoothing and curl correction are optional features that preprocess the principal curvature vector fields before using them for remeshing. These will reduce the number of singular areas in the parameterization, and as a result will reduce the amount of triangles needed in the quad-dominant mesh. The "Periodic Global Parameterization" paper describes methods for both. Alternatively, the vector field smoothing can be done by smoothing them as a single tensor field, as described in the paper "Interactive Vector and Tensor Field Design on Surfaces" by Eugene Zhang, et al.
Personal Background
I am currently a senior at Oregon State University, where I am pursuing my bachelor's degree in computer science with a minor in mathematics. In September I will be attending graduate school at either UC-Davis or University of British Columbia. For the last year I have worked with Dr. Eugene Zhang on a research project related to the quadrilateral remeshing. My programming language of choice is C++.
References
Harmonic functions for quadrilateral remeshing of arbitrary manifolds. S. Dong, S. Kircher, M. Garland, Computer Aided Geometry Design, 2005. http://graphics.cs.uiuc.edu/~garland/papers/harmonic-preprint.pdf
Periodic Global Parameterization N. Ray, W. C. Li, B. Levy, A. Sheffer, P. Alliez, ACM Transactions on Graphics, October, 2006. http://alice.loria.fr/publications/papers/2006/TOG_pgp/pgp.pdf
Anisotropic Polygonal Remeshing P. Alliez, D. Cohen-Steiner, O. Devillers, B. Lévy, and M. Desbrun, ACM Siggraph, 2003. http://www.geometry.caltech.edu/pubs/ACDLD03.pdf
Interactive Vector and Tensor Field Design on Surfaces E. Zhang, K. Mischaikow, K. Hays, G. Turk, IEEE Transactions on Visualization and Computer Graphics, 2007. http://web.engr.oregonstate.edu/~zhange/images/tenflddesn.pdf
Images
Initial Meshes
(Not completely working yet):
Timing
| Model | #Faces | #Vertices | Pre-processing (s) | Curvature (s) | Smoothing (s) | Total (s) |
| Torus | 9216 | 4608 | 0.272 | 0.297 | 1.871 | 2.447 |
| Bunny | 40000 | 20002 | 1.661 | 1.420 | 12.308 | 15.421 |
| Dragon | 40000 | 19998 | 1.725 | 1.367 | 10.672 | 13.795 |
Note: The the slowest aspect of the algorithm is the smoothing, which is crucial for removing the noise in the curvature. Increasing the timestep will increase the amount of smoothing with only a small increase in time, but adding an additional step will double the amount of time. These parameters could be tweaked later for the best tradeoff between speed and quality needed for remeshing.
References
Periodic Global Parameterization - http://alice.loria.fr/publications/papers/2006/TOG_pgp/pgp.pdf
Periodic Global Parameterization (Images) - http://alice.loria.fr/php/article.php?pub=../publications/papers/2005/PGP
Discrete Differential-Geometry Operators for Triangulated 2-Manifolds - http://www.multires.caltech.edu/pubs/diffGeoOps.pdf
Rotational Symmetry Field Design on Surfaces - http://web.engr.oregonstate.edu/~zhange/rotational_symmetry.html
