(Meditations at the Edge: Paper & Spirit,
Peter and Donna Thomas.)
Jonathan's papers
Most recent:
Greatest personal satisfaction: My 2002 paper on 2D Delaunay Refinement was awarded the 2012 Test-of-Time Award by the journal Computational Geometry: Theory and Applications. |
It gives me great pleasure to announce my first book, co-authored with Siu-Wing Cheng of the Hong Kong University of Science and Technology and Tamal Dey of The Ohio State University.
“I hate meshes. I cannot believe how hard this is. Geometry is hard.”THE GREAT CHALLENGE OF TETRAHEDRAL MESH GENERATION is to create tetrahedra whose dihedral angles are never too small nor too large. Although Delaunay refinement usually does this well in practice, there's lots of room for improvement—in obtaining mathematically guaranteed bounds on angles, in further improving the angles beyond what Delaunay algorithms or guaranteed-quality algorithms can provide, and in maintaining the quality as a domain changes shape during a simulation. Our isosurface stuffing algorithm comes with theoretical guarantees on dihedral angles. Through mesh improvement procedures, we can make the tetrahedra even better in practice. We use the same mesh improvement methods as a basis for dynamic meshing algorithms for simulating objects undergoing radical changes in shape. We also use a simpler, faster form of dynamic meshing to simulate a surgical procedure in which a steerable needle is inserted into flesh.
— David Baraff, Senior Research Scientist, Pixar Animation Studios
Prior to my work below, the CDT had not been generalized to higher dimensions, and it can never be fully generalized because not every polyhedron has a constrained tetrahedralization (allowing no additional vertices). Here, however, I prove that there is an easily tested condition that guarantees that a polyhedron (or piecewise linear domain) in three or more dimensions does have a constrained Delaunay triangulation. (A domain that satisfies the condition is said to be edge-protected in three dimenions, or ridge-protected in general dimensions.)
Suppose you want to tetrahedralize a three-dimensional domain. The result implies that if you insert enough extra vertices on the boundary of a polygon to recover its edges in a Delaunay tetrahedralization (in other words, if you make it be edge-protected) then you can recover the polygon's interior for free—that is, you can force the triangular faces of the tetrahedralization to conform to the polygon without inserting yet more vertices. This method of polygon recovery is immediately useful for mesh generation or the interpolation of discontinuous functions. (The result also fills a theoretical hole in my dissertation by showing that it is safe to delete a vertex from a constrained Delaunay tetrahedralization in the circumstances where my “diametral lens” algorithm does so.)
I provide two algorithms for constructing general-dimensional constrained Delaunay triangulations that are fast enough to be useful in practice. One is based on bistellar flips (which swap a few tetrahedra for a few others), and one is a sweep algorithm. The flip algorithm is easier to implement, and is probably usually faster in practice. However, the sweep algorithm works on almost every input that has a CDT, whereas the flip algorithm works only on ridge-protected inputs. The question of which algorithm is asymptotically faster is tricky—the answer depends on the size of the output, and is different for a worst-case input than for a random input; see the flip algorithm paper for details. See the “Strange Complexity” paper to find out why the sweep algorithm doesn't work on every input that has a CDT.
By starting with a Delaunay (or regular) triangulation and
incrementally inserting polygons one by one,
you can construct the constrained Delaunay
(or constrained regular) triangulation of a ridge-protected input in
O(nv
+ 1 log nv) time,
where nv is the number of input vertices
and d is the dimensionality.
In odd dimensions (including three dimensions, which is what I care about most)
this is within a factor of log nv of worst-case optimal.
The algorithm is likely to take only
O(nv log nv)
time in many practical cases.
Aimed at both programmers and computational geometers.
Discusses the general-dimensional case, but most useful in three dimensions.
To make robust geometric tests fast, I propose two new techniques (which can also be applied to other problems of numerical accuracy). First, I develop and prove the correctness of software-level algorithms for arbitrary precision floating-point arithmetic. These algorithms are refinements (especially with regard to speed) of algorithms suggested by Douglas Priest, and are roughly five times faster than the best available competing method when values of small or intermediate precision (hundreds or thousands of bits) are used. Second, I show how simple expressions (whose only operations are addition, subtraction, and multiplication) can be computed adaptively, trading off accuracy and speed as necessary to satisfy an error bound as quickly as possible. (This technique is probably applicable to any exact arithmetic scheme.) I apply these ideas to build fast, correct orientation and incircle tests in two and three dimensions, and to make robust the implementations of two- and three-dimensional Delaunay triangulation in Triangle and Pyramid. Detailed measurements show that in most circumstances, these programs run nearly as quickly when using my adaptive predicates as they do using nonrobust predicates.
See my
Robust Predicates page for more information
about this research, or to obtain C source code for
exact floating-point addition and multiplication
and the robust geometric predicates.