application, geometric concepts, Hodge Decomposition, discretization, differential form, fluid simulation, tangent bundles, exterior calculus, parameterizations, texture mapping, intricate details, geometric principles, hexahedral meshes, mathematical framework, base mesh, discrete exterior calculus
Statement of Purpose
Applied Differential Geometry
Yiying Tong [email protected]
My main research goal is to develop robust, predictive, and multi-purpose computation tools by leveraging differential geometric concepts and foundations. In particular, I wish to contribute a number of practical application
s in computer graphics and related areas, such as medical imaging, biometrics, medical simulation, and visualization, by focusing on the geometrical foundations common to computational science and graphics. Introduction The water sequence inside the mouth of a whale in Pixar's Finding Nemo and the traditional flow-past-disk test in Computational Fluid Dynamics may look unrelated. Their goals are, indeed, quite different. Nevertheless, their underlying dynamics obey the same set of equations, namely, the Navier-Stokes equations. In fact, much could be gained in both fields through exploration of the complementarity of both computational methods: their apparent antagonistic standpoints hide rich opportunities for cross-pollination. Probably the most important goal in computer graphics applications such as simulation methods and/or photorealistic rendering techniques is to seek real-time computations. To that purpose, many ad-hoc methods have been developed. Careful examination of the mathematical foundations of these methods is, alas, often considered irrelevant or intractable. In practice though, more and more researchers acknowledge that, on the contrary, deeper understanding of the theory usually leads to simpler, more robust algorithms. Thus, developing solid foundations can in turn not only unify and generalize, but also improve existing methods. A case in point comes from computational mechanics: variational integrators are now known to provide exact momentum preservation and conservative energy behavior-- a critical criterion in providing a qualitatively-correct visual experience in simulation. Such strong properties are actually obtained at no additional computational cost
compared to traditionally-used numerical time integration schemes. As one can use these integrators both explicitly or implicitly [KWT+06], there are only benefits to adopting such robust computational framework instead of ad-hoc integrators. Importance of Geometry In many applications of engineering, and in particular in Computer Aided Geometric Design (CAGD), geometry evidently plays a central role. Various data structure
s like half-edge and constructive solid geometry tree, and algorithms built on top of them, are intrinsically geometric in nature. But the usefulness of geometry is certainly not restricted to CAGD: it is omnipresent in computer graphics. In fact, CAGD can be seen as an application of computer graphics to the modeling process of mechanical engineering; this is just one example of the interdisciplinary nature of computer graphics. More generally, any development in computer graphics directly benefits other areas like scientific visualization, medical applications, biometrics, entertainment, communication and education. Indeed, the common link between computer graphics and these areas is the reliance on geometry (including but not restricted to low dimensional Euclidean geometry) and its applications. This means that developments in the mathematical foundations of graphics can and should utilize results from differential geometry, computational topology, continuum mechanics, electro-magnetism and other areas that use (and are defined by) geometry. In turn, these geometric foundations can be used to improve visualization, interactivity, and computation efficiency in all those areas. Past Projects My research interests emerged from a series of initial projects that stressed the importance of good geometric discretizations in a variety of contexts. Computational Science Tools The notion of atlas of a manifold is used in the very definition of manifoldness in differential geometry. However, this notion is not as simple in computer graphics since each application has a different set of requirements on the parameterizations of the atlas charts. One project I worked on demonstrated, for instance, that proper discretization of geodesics can lead to an intrinsic parameterization of surfaces independent of its embed-
ding in 3D Euclidean space
[LTD05]. This seemingly simple example is actually quite representative of a deeper underlying principle: the rationale behind a proper discretization of geometric concepts is not only relevant for Euclidean curves and surfaces, but also crucial to the treatment of more advanced, general concepts such as tangent bundles and cotangent bundles. An early attempt to discretize vector fields and the well-known notion of HelmholtzHodge decomposition was introduced in one of our papers [TLHD03] where we showed how a clean geometric discretization leads to exact discrete differential identities such as the vanishing of the curl of any gradient vector field.
Since then, a more general approach called discrete exterior calculus (DEC) has
been proposed, based on a systematic discretization of Elie Cartan's exterior calculus,
the natural calculus on arbitrary manifolds. This novel idea was initially developed
in computational electromagnetism, and used with great success. While the basic el-
ement in exterior calculus is the differential form, discrete differential forms in DEC
are defined as mappings from all k-simplices in a mesh to real numbers, which can
be represented using simple data structures
such as arrays with fixed lengths. Conse- Hodge Decomposition
quently, operators such as exterior derivative can be directly implemented using the transpose of adjacency matrices.
DEC not only provides a proper discretization for its continuous counterpart, but also heightens our intuition since
it greatly clarifies abstract concepts. To make these ideas accessible to other researchers and practitioners in graph-
ics, my collaborators and I wrote an introductory chapter for a recently-published book on Discrete Differential
Geometry (DDG) [DKT07].
As elasticity (a model of both shape and its governing dynamics) relies heav-
ily on calculus on curved objects, it is natural to apply the DEC framework in
this context. To that purpose, we developed a reformulation of continuum elas-
ticity to clearly separate metric-dependent and metric-independent geometric no-
tions involved in mechanics. In this formulation, the stress tensor is expressed
as a covector-valued 2-form that implies the Cauchy Lemma by definition. This
also indicates that a proper discretization of the stress tensor should give val- Discrete Exterior Calculus ues associated with discrete facets [KAT+07], an idea we are now pursuing.
We have also applied this same framework to fluid simulation, as fluid flow mod-
els involve another central concept in exterior calculus: the notion of Lie derivatives.
Our geometric discretization leads to a simple, stable circulation-preserving algo-
rithm designed to keep the circulation of every discrete loop preserved at each time
step as it moves with the flow. Akin to the important preservation of angular momen-
tum in a rigid body motion, preservation of vorticity is crucial to fluid simulation--in
particular visually, since this vorticity will affect the motion of smoke rings and vor-
tices to which we are quite accustomed. As the incompressibility of fluids guarantees
that the divergence is null everywhere, vorticity is the only quantity of interest when the domain is fixed. Since our
algorithm enforces the preservation of local integrals of vorticity (equivalent to circulation along the boundary of
discrete facets according to Stokes' theorem), the resulting numerical scheme does not suffer from the usual vorticity dissipation that plagues other techniques [ETK+07].
Applications in Graphics One of the major applications of the above-mentioned
parameterization is texture mapping, i.e., mapping pictures onto faces of the models,
a commonly used tool to decorate objects with rich visual (color) details in graphics.
Building an atlas of charts seamlessly stitching texture images is a difficult task that
cannot be directly achieved from examining the model alone. We proposed a novel
algorithm based on the minimization of certain compatibility functions that measure
the discontinuity in the color fields and the color gradient fields on the 2D manifolds
across various parameterizations [ZWT+05]. The mathematical framework we used in this application facilitates
texture mapping of complex objects by drastically reducing the tedious parameter adjustments that artists typically have to do to produce a visually pleasing result. Texture mapping has also been used to replace geometric details of objects (such as grooves or bumps), since early graphics hardware had very limited polygon throughput. With the recent advent of powerful graphics cards, we can now manipulate detailed meshes with millions of triangles in realtime, enhancing the visual experience through parallax, shadows and, other effects. Meshes are also very amenable to direct editing and animation, something that artists are particularly looking for. However, complex details such as weaves, ivies, and chain-mails still require a huge amount of labor to incorporate in 3D models. We recently offered a novel algorithmic way to synthesize such intricate details on arbitrary surfaces with the help of the classic "min-cut" algorithm and a low-distortion shell mapping [ZHW+06]: from a base mesh and a given 3D texture swatch, a geometric texture locally similar to the swatch everywhere is synthesized over the base mesh, resulting in models with intricate geometric and topological details requiring very little user time. This again shows that good mathematical foundations can help tremendously in the design of practical algorithms.
Stimulated by our recent results, we are now developing more computational methods
by exploring structure-preserving discretizations of deeper geometric principles.
Meshing One obvious application of the DDG framework in graphics and computa-
tional science is the adaptive meshing of static objects, through the clean treatment of
topology. Recently, we have started studying harmonic one-forms and cohomology
for the purpose of quadrangulation [TACSD06]. Harmonicity of one-forms is crucial as it guarantees local smoothness (for the quads to be well-shaped) and global
periodicity (to avoid T-junctions). Through appropriate manipulation of the topology and geometry of the meshes,
we have shown how to assemble a sparse linear system to provide an efficient solution. We are exploring ways to
generalize the method to create hexahedral meshes, which are commonly used in Finite Element Analysis. Through
principal component analysis of the Laplacian operator, a central notion in DDG, we seek methods that can help
the theoretical analysis of shapes, as well as practical algorithms such as surface reconstructing from 3D scanner
Deformation Models A natural extension to the static case is the modeling of shapes
changing over time. There are traditionally two types of discretization for deformable
objects, namely, the Eulerian and the Lagrangian approaches. In the Lagrangian ap-
proach, sample points move with the object, resulting in effecient representation and
update rules necessary for most real-time applications. We are exploring ways to fur-
ther improve the efficiency, for example, through combination of inverse kinematics
and preservation of local differential geometric quantities like mean curvature nor-
mal [SZT+07]. In the Eulerian approach, sample points are fixed in space. Although relatively less efficient, it
handles topological changes smoothly. We are investigating remedies for known problems in this approach like
the lack of Volume Control
. Our initial results can already benefit applications such as simultaneous smoothing of
surfaces in medical datasets, handling of high-genus surfaces, and incompressible fluid simulation [MMTD07].
Applications in Biochemistry, Medical Imaging/Simulation, and Biometrics
The above modeling tools can find an abundance of applications. We wish to inves-
tigate the application of a mixture of Eulerian and Lagrangian methods to deal with
molecular surfaces, as both the capability of dealing with a large number of models
and robust handling of topological alterations are necessary in problems like protein
folding and docking.
Another direction we wish to explore is the application of aforementioned eigen-
analysis based on discrete Laplacian operator. For example, we plan to extract fiber
tracks in the white matter of brains through Laplacian-based spectral analysis applied to the tensor fields obtained
through Diffusion Tensor Imaging, a magnetic resonance imaging technique. Similarly, we also plan to do spec-
tral analysis of the finite-time Lyapunov exponent field for robust extraction of Lagrangian Coherent Structure, a
particularly pertinent concept in the analysis of time-varying dynamical systems.
As 3D techniques
are increasingly accessible and utilized in biometrics, we also
plan to employ 3D deformable objects for robust identification and verification of
faces or other biometrics of humans under the influences of natural variations like
aging and weight gain/loss. Other areas of interest include template matching and
surface fairing for brain imaging [ETKD07]. Simulation For simulation of elastic objects, another interesting avenue to explore Cortical Surface Fairing
is time integration through discretization of variational principles such as the stationary action principle. The re-
sulting integrators are the variational integrators we mentioned earlier, that have now been proven to be vastly more
robust, stable, and globally conservative than the integrators resulting from arbitrary discretization of the equations
of motion. We have recently introduced a more general variational integrator based on the Pontryagin-Hamilton
principle. With the additional degrees of freedom introduced by the Pontryagin principle, we can substitute the
non-linear solve of the discrete Euler-Poincareґ equations by a minimization procedure to make the numerical implementation truly variational [KWT+06]. In addition, this procedure gives us enough leeway to design motion
interpolation techniques based on subdivision of the animation in space time and adaptive sampling of spatial and
temporal discretization during simulation--ideas that we are currently developing.
A variational integration of Fluid mechanics
is another interesting, yet mostly
unexplored approach to preserving the defining invariants such as circulation and
energy. According to the continuous theory, a correct treatment of these fluid dynam-
ics equations should respect the particle-relabeling symmetry: indeed, according to
Noether's Theorem, this symmetry would automatically guarantee the preservation
of vorticity, responsible for the intricate visual details evident in fluid motion. This
symmetry also allows the use of reduction theory, greatly reducing the dimensionality of the problem. In order to achieve such a symmetry-preserving discretization, we
are working on a discretization of the Lie groups (more precisely, of the volume-preserving diffeomorphisms) and
the corresponding Lie algebras involved in the continuous case. Once we identify the proper discrete counterpart
of the continuous groups and algebras of the continuous theory, we can "translate" the corresponding continuous
principle into a discrete, yet physically accurate language. We plan to continue this research direction, as it seems
promising and rich in consequences.
In addition to variation with respect to time, the discretization of variation of action as integral of the Lagrangian
density in field theory with respect to spatial coordinates gives multisymplectic integrators, which preserve the
momentum map and are potentially crucial in the aforementioned spatial adaptive sampling. Initial tests have been
done in electromagnetism, numerically exhibiting valid global energy behavior [STDM08].
Extension of DDG We are also working towards a more general DDG framework through, in particular, the in-
troduction of smoother basis functions (for more accurate numerics) and the construction of basis functions over
(non-simplicial) cell complex (e.g, for computations on dual meshes). We have produced an initial result on 1-forms on curved 2D surfaces through subdivision [WWT+06]. We are also seeking discretization methods for true vector
fields, metric tensors and connection forms, which are consistent with the existing DEC framework, as they are
necessary to carry out full-blown tensor analysis.
Finally, we also plan on studying new applications of DDG in modeling, real-time animation, and other ar-
eas related to graphics through the continued development of more powerful geometric techniques offering novel
[ACSTD07] Pierre Alliez, David Cohen-Steiner, Yiying Tong, and Mathieu Desbrun. Voronoi-based Variational Reconstruction of Unoriented Point Sets. In Symposium on Geometry Processing, July 2007.
Mathieu Desbrun, Eva Kanso, and Yiying Tong. Discrete Differential Forms for Computational Modeling. In A. Bobenko and P. SchroЁder, editors, Discrete Differential Geometry. Springer, 2007. Sharif Elcott, Yiying Tong, Eva Kanso, Peter SchroЁder, and Mathieu Desbrun. Stable, Circulation-Preserving, Simplicial Fluids. ACM Trans. on Graphics, 26(1):4, January 2007.
[ETKD07] I. Eckstein, Y. Tong, C.-C. J. Kuo, and M. Desbrun. Volume-controlled surface fairing. In SIGGRAPH '07: ACM SIGGRAPH 2007 sketches, page 8, New York, NY, USA, 2007. ACM. [KAT+07] Eva Kanso, Marino Arroyo, Yiying Tong, Arash Yavari, Jerrold E. Marsden, and Mathieu Desbrun. On the Geometric Character of Stress in Continuum Mechanics. Z. angew. Math. Phys., 58:114, 2007. [KWT+06] Liliya Kharevych, Weiwei, Yiying Tong, Eva Kanso, Jerrold E. Marsden, Peter SchroЁder, and Mathieu Desbrun. Geometric, Variational Integrators for Computer Animation. In ACM/EG Symposium on Computer Animation, pages 4351, July 2006.
[LTD05] Haeyoung Lee, Yiying Tong, and Mathieu Desbrun. Geodesics-based One-to-One Parameterization of 3D Triangle Meshes. IEEE Multimedia, 12(1):2733, January 2005.
[MMTD07] Patrick Mullen, Alexander McKenzie, Yiying Tong, and Mathieu Desbrun. A Variational Approach to Eulerian Geometry Processing. ACM Trans. on Graphics (SIGGRAPH), July 2007.
[STDM08] A. Stern, Y. Tong, M. Desbrun, and J. E. Marsden. Variational integrators for maxwell's equations with sources. In Progress in Electromagnetics Research Symposium (PIERS), 2008. to appear. [SZT+07] Xiaohan Shi, Kun Zhou, Yiying Tong, Mathieu Desbrun, Hujun Bao, and Baining Guo. Mesh Puppetry: Cascading Optimization of Mesh Deformation with Inverse Kinematics. ACM Trans. on Graphics (SIGGRAPH), July 2007.
[TACSD06] Yiying Tong, Pierre Alliez, David Cohen-Steiner, and Mathieu Desbrun. Designing Quadrangulations with Discrete Harmonic Forms. In ACM/EG Symposium on Geometry Processing, pages 201210, July 2006.
[TLHD03] Yiying Tong, Santiago Lombeyda, Anil Hirani, and Mathieu Desbrun. Discrete Multiscale Vector Field Decomposition. In ACM Trans. on Graphics (SIGGRAPH), volume 22, pages 445452, June 2003. [WWT+06] Ke Wang, Weiwei, Yiying Tong, Mathieu Desbrun, and Peter SchroЁder. Edge Subdivision Schemes and the Construction of Smooth Vector Fields. ACM Trans. on Graphics (SIGGRAPH), 25(3):10411048, July 2006. [ZHW+06] K. Zhou, X. Huang, X. Wang, Y. Tong, M. Desbrun, B. Guo, and H.-Y. Sheum. Mesh Quilting For Geometric Texture Synthesis. ACM Trans. on Graphics (SIGGRAPH), 25(3):690697, July 2006. [ZWT+05] Kun Zhou, Xi Wang, Yiying Tong, Mathieu Desbrun, Baining Guo, and H.-Y. Shum. TextureMontage: Seamless Texturing of Surfaces From Multiple Images. ACM Trans. on Graphics (SIGGRAPH), 24(3):11481155, July 2005.