![]() |
(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. |
Unstructured Mesh Generation, chapter 10 of
Combinatorial
Scientific Computing (Uwe Naumann and Olaf Schenk, editors),
pages 257–297, CRC Press, January 2012.
PostScript (1,756k, 41 pages).
A survey of the four main method of mesh generation:
advancing front methods, Delaunay triangulations, grid and octree methods, and
mesh improvement (also known as “clean-up”).
My goals for this chapter were to trace the historical origins of
many well-known ideas in mesh generation, and
to provide a greater level of algorithmic detail than
you would expect in a survey this short.
Note that this version differs slightly from the version in the book in
one respect: I use slightly more verbose references here.
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.
Delaunay Refinement Mesh Generation,
Ph.D. thesis, Technical Report CMU-CS-97-137,
School of Computer Science, Carnegie Mellon
University, Pittsburgh, Pennsylvania, 18 May 1997.
Abstract (with BibTeX citation),
compressed PostScript (1,768k, 207 pages)
(expands to 10,435k when uncompressed),
PDF (2,635k, 207 pages).
Includes extensive treatment of Delaunay triangulations,
two- and three-dimensional Delaunay refinement algorithms,
and implementation details.
However, Chapter 3 on two-dimensional Delaunay refinement is superseded
by the much-improved article above.
Tetrahedral Mesh Generation by Delaunay Refinement,
Proceedings of the Fourteenth Annual Symposium on
Computational Geometry (Minneapolis, Minnesota), pages 86–95,
Association for Computing Machinery, June 1998.
PostScript (1,504k, 10 pages),
PDF (299k, 10 pages).
A description of the core three-dimensional mesh generation algorithm
used in Pyramid, for those who want a quick overview with less detail.
A more thorough treatment appears in Chapter 4 of
my dissertation.
Triangle: Engineering a 2D Quality Mesh
Generator and Delaunay Triangulator,
in Applied Computational Geometry: Towards Geometric Engineering
(Ming C. Lin and Dinesh Manocha, editors),
volume 1148 of Lecture Notes in Computer Science,
pages 203–222, Springer-Verlag (Berlin), May 1996.
From the First Workshop on Applied Computational Geometry
(Philadelphia, Pennsylvania).
Abstract (with BibTeX citation),
PostScript (513k, 10 pages),
PDF (153k, 10 pages),
HTML.
A short paper on Triangle, for those who want a quick overview
with less detail.
All this material is scattered through my dissertation
as well.
François Labelle and Jonathan Richard Shewchuk,
Anisotropic Voronoi Diagrams and
Guaranteed-Quality Anisotropic Mesh Generation,
Proceedings of the Nineteenth Annual Symposium on
Computational Geometry (San Diego, California), pages 191–200,
Association for Computing Machinery, June 2003.
PostScript (910k, 10 pages),
PDF (284k, 10 pages).
The best triangulations for interpolation and numerical modeling
are often anisotropic: long and skinny, oriented in directions
dictated by the function being approximated.
(See my “What Is a Good Linear Element?” papers below for details.)
The ideal orientations and aspect ratios of the elements may vary
greatly from one position to another.
This paper discusses a Voronoi refinement algorithm for
provably good anisotropic mesh generation.
The skewed elements are generated with the help of
anisotropic Voronoi diagrams,
wherein each site has its own distorted distance metric.
Anisotropic Voronoi diagrams are somewhat badly behaved,
and do not always dualize to triangulations.
We call it “Voronoi refinement” because the diagrams
can be tamed by inserting new sites.
After they are carefully refined, they dualize to guaranteed-quality
anisotropic triangular meshes.
Mesh Generation for Domains with Small Angles,
Proceedings of the Sixteenth Annual Symposium on
Computational Geometry (Hong Kong), pages 1–10,
Association for Computing Machinery, June 2000.
PostScript (663k, 10 pages),
PDF (237k, 10 pages).
How to adapt Delaunay refinement algorithms to domains that are difficult
to mesh because they have small angles.
The two-dimensional portion of this paper is superseded by the
improved writing in “Delaunay Refinement Algorithms for Triangular Mesh
Generation,” above.
The three-dimensional portion is still found only here.
Star Splaying: An Algorithm for Repairing
Delaunay Triangulations and Convex Hulls,
Proceedings of the Twenty-First Annual Symposium on
Computational Geometry (Pisa, Italy), pages 237–246,
Association for Computing Machinery, June 2005.
PostScript (392k, 10 pages),
PDF (209k, 10 pages).
Star splaying is a general-dimensional algorithm for
fixing broken Delaunay triangulations and convex hulls.
Its input is a triangulation, an approximate convex hull,
or even just a set of vertices and guesses about who their neighbors are.
If the input is “nearly Delaunay” or “nearly convex,”
star splaying is quite fast,
so I call it a “Delaunay repair” algorithm.
Star splaying is designed for dynamic mesh generation,
to repair the quality of a finite element mesh
that has lost the Delaunay property after its vertices have moved
in response to simulated physical forces.
Star splaying is akin to Lawson's edge flip algorithm for converting
a two-dimensional triangulation to a Delaunay triangulation,
but it works in any dimensionality.
“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
Nuttapong Chentanez, Bryan Feldman, François Labelle,
James O'Brien, and Jonathan Richard Shewchuk,
Liquid Simulation on Lattice-Based Tetrahedral Meshes,
2007 Symposium on Computer Animation (San Diego, California),
pages 219–228, August 2007.
PDF (color, 4,782k, 10 pages).
Here, we use isosurface stuffing (above) as part of an algorithm for
simulating liquids with free surfaces.
The graded meshes allow us to maintain fine detail on the liquid surface
without excessive computational cost in the interior.
The rendered surface is represented as a separate surface triangulation,
at an even finer detail than the surface of the tetrahedral mesh.
We exploit the regularity of the meshes for fast point location,
needed for semi-Lagrangian advection of the velocities and the surface itself.
We also introduce a thickening strategy to prevent the liquid from
breaking up into sheets or droplets so thin that they disappear,
falling below the finest resolution of the mesh.
Bryan Matthew Klingner and Jonathan Richard Shewchuk,
Aggressive Tetrahedral Mesh Improvement,
Proceedings of the 16th International Meshing Roundtable (Seattle, Washington),
pages 3–23, October 2007.
PDF (color, 26,567k, 18 pages).
Mesh clean-up software takes an existing mesh and improves the
quality of its elements by way of operations such as smoothing
(moving vertices to better locations) and topological transformations
(replacing a small set of tetrahedra with better ones).
Here, we demonstrate algorithms and software that so aggressively improve
tetrahedral meshes that we obtain quality substantially better than that
produced by any previous method for tetrahedral mesh generation or
mesh improvement.
Our main innovation is to augment the best traditional clean-up methods
(including some from the Discrete Optimization Algorithms paper below)
with topological transformations
and combinatorial optimization algorithms that insert new vertices.
Our publicly available
software Stellar often improves a mesh so that
all its dihedral angles are between 30o and 130o.
Martin Wicke, Daniel Ritchie, Bryan M. Klingner, Sebastian Burke,
Jonathan R. Shewchuk, and James F. O'Brien,
Dynamic Local Remeshing for Elastoplastic Simulation,
ACM Transactions on Graphics 29(4):49.1–49.11, July 2010.
Special issue on Proceedings of SIGGRAPH 2010.
PDF (color, 3,650k, 11 pages).
We develop a dynamic finite element method for modeling elastoplastic materials
undergoing extreme deformations and fracture,
such as slime dripping from a ceiling or clay forced through an aperture.
Radical changes in the shape of an object necessitate remeshing, but
we must resample the strain field from the old mesh to the new one and
thereby incur errors that manifest as artificial plasticity.
We introduce two techniques to mitigate these errors.
First, we have a new notion of “material space” that represents
the configuration of the object with minimum internal strain, and
we remesh in that space, rather than remesh in world space as
some previous researchers have done.
Second, we have algorithms for dynamic mesh generation that locally
improve small regions of the mesh while leaving the majority undisturbed.
Our dynamic remeshing techniques are a variant of our mesh improvement methods
from the paper above.
Pascal Clausen, Martin Wicke, Jonathan R. Shewchuk, and James F. O'Brien,
Simulating Liquids and Solid-Liquid Interactions with Lagrangian Meshes,
ACM Transactions on Graphics 32(2), April 2013.
PDF (color, 15,031k, 15 pages).
We develop a Lagrangian finite element method that
simulates the behavior of liquids and solids in a unified framework.
We continue the development of dynamic mesh generation algorithms from
the two papers above;
our dynamic mesh improvement library Stellar maintains
a high-quality tetrahedral mesh even as it is advected by fluid flow.
Topological changes in the domain are explicitly treated with
local mesh splitting and merging.
We conserve volume and momentum, locally and globally, by assigning
each element an independent rest volume and adjusting it
to correct for deviations during remeshing and collisions.
Our method models surface
tension with an implicit formulation based on surface energies
computed on the boundary of the volume mesh.
With this method we can model elastic, plastic, and liquid materials
in a single mesh, with no need for explicit coupling. We also model
heat diffusion and thermoelastic effects, which allow us to simulate
phase changes like melting.
Two Discrete Optimization Algorithms for the
Topological Improvement of Tetrahedral Meshes,
unpublished manuscript, 2002.
PostScript (295k, 11 pages),
PDF (168k, 11 pages).
This tutorial studies two local topological transformations for
improving tetrahedral meshes: edge removal and
multi-face removal.
Given a selected edge, edge removal deletes all the tetrahedra
that contain the edge, and replaces them with other tetrahedra.
I work out in detail (and attempt to popularize)
an algorithm of Klincsek for finding the optimal set of new tetrahedra.
The multi-face removal operation is the inverse of the edge removal operation.
I give a new algorithm for finding the optimal multi-face removal operation
that involves a selected face of the tetrahedralization.
These algorithms are part of our tetrahedral mesh improvement software
described in the papers above.
Florian Hecht, Yeon Jin Lee, Jonathan R. Shewchuk, and James F. O'Brien,
Updated Sparse Cholesky Factors for Corotational Elastodynamics,
ACM Transactions on Graphics 31(5):123.1–123.13, October 2012.
PDF (color, 24,436k, 13 pages).
We introduce warp-canceling corotation,
a nonlinear finite element formulation for elastodynamic simulation that
achieves fast performance by making only partial or
delayed changes to the simulation's linearized system matrices.
This formulation combines the widely used corotational finite element method
with stiffness warping so that changes in the per-element rotations are
initially approximated by inexpensive per-node rotations.
When the errors of this approximation grow too large,
the per-element rotations are selectively corrected by updating parts of
the matrix chosen according to locally measured errors.
These changes to the system matrix are propagated to
its sparse Cholesky factor by incremental updates that are
much faster than refactoring the matrix from scratch.
A nested dissection ordering of the system matrix gives rise to
a hierarchical factorization in which changes to the system matrix cause
limited, well-structured changes to the Cholesky factor.
Because our method requires computing only partial updates of
the Cholesky factor, it is substantially faster than
full refactorization and outperforms widely used iterative methods such as
preconditioned conjugate gradients, but
it realizes the stability and scalability of a sparse direct method.
Unlike iterative methods, our method's performance does not slow for
stiffer materials; rather, it improves.
Nuttapong Chentanez, Ron Alterovitz, Daniel Ritchie, Lita Cho, Kris K. Hauser,
Ken Goldberg, Jonathan R. Shewchuk, and James F. O'Brien,
Interactive Simulation of Surgical Needle Insertion and Steering,
ACM Transactions on Graphics 28(3):88.1–88.10, August 2009.
Special issue on Proceedings of SIGGRAPH 2009.
PDF (color, 6,580k, 10 pages).
Clinical procedures such as biopsies, injections, and neurosurgery involve
inserting a needle into tissue; here we focus on
brachytherapy cancer treatment with a steerable needle,
in which radioactive seeds are injected
into a prostate gland to locally irradiate tumors.
Needle insertion deforms body tissues, making it difficult to
accurately place the needle tip while avoiding vulnerable vessels and nerves.
We describe an interactive, real-time simulator of needle insertion that
might lead to software for training surgeons and planning surgeries based on
medical images from patients.
The simulator models the coupling between a steerable needle and
deformable tissue as a linear complementarity problem.
A key part of our simulator is
a novel algorithm for dynamic local remeshing that quickly enforces
the conformity of a tetrahedral tissue mesh to a curvilinear needle path,
enabling accurate computation of contact forces.
Because a one-dimensional needle intersects the tissue mesh in simple ways,
we can use a simple and fast dynamic meshing algorithm that
keeps the quality of the modified tetrahedra high in practice.
Martin Isenburg, Yuanxin Liu, Jonathan Shewchuk, Jack Snoeyink, and
Tim Thirion,
Generating Raster DEM from Mass Points via TIN Streaming,
Proceedings of the Fourth International Conference on
Geographic Information Science
(GIScience 2006, Münster, Germany), September 2006.
PostScript (color, 16,554k, 13 pages).
PDF (color, 490k, 13 pages).
Martin Isenburg, Peter Lindstrom, Stefan Gumhold, and Jonathan Shewchuk,
Streaming Compression of Tetrahedral Volume Meshes,
Proceedings: Graphics Interface 2006 (Quebec City, Quebec, Canada),
pages 115–121, June 2006.
PDF (color, 3,821k, 7 pages).
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
General-Dimensional Constrained Delaunay and
Constrained Regular Triangulations, I: Combinatorial Properties.
Discrete & Computational Geometry 39(1–3):580–637,
March 2008.
PostScript (865k, 54 pages),
PDF (447k, 54 pages).
This manuscript lays down the combinatorial foundations of CDTs and
weighted CDTs.
It begins by proving that many properties of Delaunay triangulations
(of any dimension)
generalize to constrained Delaunay triangulations—in particular,
the Delaunay Lemma, which states that a triangulation is a weighted CDT
if and only if every (d–1)-dimensional face is either
“locally regular” (locally convex on the lifting map) or
a constraining face.
Next, the manuscript shows that (weighted) CDTs have several optimality
properties when used for piecewise linear interpolation.
It culminates with the proof that if an input is weakly ridge-protected
(a less restrictive condition than ridge-protected), it has a CDT.
This proof also applies to weighted CDTs.
This paper is the ideal starting point for researchers
who want to work with CDTs of dimension higher than two,
and it is the foundation of the correctness proofs of my CDT construction
algorithms.
For those who don't want to read the proofs,
the introduction summarizes the results and how to use them.
Aimed at computational geometers.
Discusses the general-dimensional case.
A Condition Guaranteeing the Existence of
Higher-Dimensional Constrained Delaunay Triangulations,
Proceedings of the Fourteenth Annual Symposium on
Computational Geometry (Minneapolis, Minnesota), pages 76–85,
Association for Computing Machinery, June 1998.
PostScript (328k, 10 pages),
PDF (181k, 10 pages).
An early version of the CDT existence proof,
which is the most difficult proof I've ever done.
This version of the proof is shorter than the more general and rigorous
proof in the paper above, but it also has some unnecessary complications that
I excised from the later version.
The proof is tough reading, but you don't need to understand it to use the
result.
Also includes a discussion of a slow-but-simple gift-wrapping algorithm
for constructing a constrained Delaunay triangulation.
This paper does not discuss weighted CDTs (constrained regular triangulations);
see the paper above for that.
Aimed at computational geometers.
Discusses the general-dimensional case.
Updating and Constructing Constrained Delaunay and
Constrained Regular Triangulations by Flips,
Proceedings of the Nineteenth Annual Symposium on
Computational Geometry (San Diego, California), pages 181–190,
Association for Computing Machinery, June 2003.
PostScript (545k, 14 pages including a four-page appendix
not in the published version),
PDF (244k, 14 pages).
If you want to incrementally update a constrained Delaunay triangulation,
you need four operations:
inserting and deleting a polygon, and inserting and deleting a vertex.
(To “insert a polygon” is to force the faces of the CDT
to respect the polygon;
to “delete a polygon” is to relax the polygon constraint so
the CDT can act a little more Delaunay and a little less constrained.)
This paper gives algorithms for the first two, based on simple bistellar flips.
A sweep algorithm for deleting a vertex appears in the paper below
(and it is trivially converted to a flip algorithm).
Finally, Barry Joe's flip algorithm for inserting a vertex
into a Delaunay triangulation is easily modified to work in a CDT.
These operations work in any dimensionality, and they can all be applied
to the more general class of
constrained regular triangulations (which include CDTs).
+ 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.
Hang Si and Jonathan Richard Shewchuk,
Incrementally Constructing and Updating
Constrained Delaunay Tetrahedralizations with Finite Precision Coordinates,
Proceedings of the 21st International Meshing Roundtable
(San Jose, California), pages 173–190, October 2012.
PDF (881k, 18 pages).
An experimental comparison of two recent algorithms for inserting
a polygon into a CDT:
my bistellar flip algorithm (see the paper above) and
a cavity retriangulation algorithm of Si and Gärtner
(Proceeding of the Fourteenth International Meshing Roundtable,
September 2005).
With respect to speed, there is no clear winner.
We modify these algorithms to succeed in practice for polygons whose vertices
deviate from exact coplanarity, which cause problems both theoretical and
numerical.
It proves to be easier to make Si and Gärtner's algorithm reliable than
mine.
Sweep Algorithms for Constructing
Higher-Dimensional Constrained Delaunay Triangulations,
Proceedings of the Sixteenth Annual Symposium on
Computational Geometry (Hong Kong), pages 350–359,
Association for Computing Machinery, June 2000.
PostScript (352k, 10 pages),
PDF (195k, 10 pages).
Gives an O(nvns)-time sweep algorithm
for constructing a constrained Delaunay triangulation,
where nv is the number of input vertices,
and ns is the number of simplices in the triangulation.
(The algorithm is likely to be faster in most practical cases.)
The running time improves to
O(ns log nv)
for star-shaped polytopes, yielding an efficient way to delete a vertex
from a CDT.
Nicolas Grislain and Jonathan Richard Shewchuk,
The Strange Complexity of Constrained Delaunay Triangulation,
Proceedings of the Fifteenth Canadian Conference on Computational Geometry
(Halifax, Nova Scotia), pages 89–93, August 2003.
PostScript (195k, 4 pages),
PDF (73k, 4 pages).
The problem of constructing
a constrained Delaunay tetrahedralization has the unusual status
(for a small-dimensional problem) of being NP-hard only for
degenerate inputs, namely those with subsets of five or more
cospherical vertices.
This paper proves one half of that statement:
it is NP-hard to decide whether a polyhedron
has a constrained Delaunay tetrahedralization.
The paper on sweep algorithms (above) contains the proof of the other half:
for a polyhedron (or more generally, a piecewise linear complex)
with no five vertices lying on a common sphere, a polynomial-time algorithm
constructs the CDT (if it exists) and thereby solves the decision problem.
Freaky, eh?
Stabbing Delaunay Tetrahedralizations,
Discrete & Computational Geometry 32(3):339–343, October 2004.
PostScript (143k, 4 pages),
PDF (70k, 4 pages),
HTML.
This note answers (pessimistically) the formerly open question of
how many tetrahedra in an n-point Delaunay tetrahedralization
can be stabbed by a straight line.
The answer: for a worst-case tetrahedralization,
a line can intersect the interiors of
tetrahedra.
In d dimensions,
a line can stab the interiors of
Delaunay d-simplices.
The result explains why my sweep algorithm for constructing CDTs
has a worst-case running time of O(nvns) and not
O(nv2 +
ns log nv).
The difficulty of finding the worst-case example explains why
the sweep algorithm is unlikely to take longer than
O(nv2 +
ns log nv)
time on any real-world input.
Chen Shen, James F. O'Brien, and Jonathan R. Shewchuk,
Interpolating and Approximating Implicit Surfaces from Polygon Soup,
ACM Transactions on Graphics 23(3):896–904, August 2004.
Special issue on Proceedings of SIGGRAPH 2004.
PDF (color, 17,269k, 9 pages).
The Moving Least Squares (MLS) method is a popular way to define
an implicit surface that interpolates or approximates a set of points
in three-dimensional space.
But graphics programmers have made millions of polygonalized surface
models; what if we want to interpolate whole polygons?
Approximating a polygon as a bunch of points gives poor results.
Instead, we show how to force an MLS function to have a specified value over
each input polygon, by integrating constraints over triangles.
Better yet, we show how to force the MLS function to have a specified gradient
over each polygon as well,
so that we can robustly specify which parts of space should be
inside or outside the implicit surface—without creating
undue oscillations in the MLS function.
The trick is to define a different function on each input polygon, and
use MLS to interpolate between functions—not
just to interpolate between values
(as the usual formulations of MLS for implicit surfaces do).
This trick gives us profound control of an MLS function.
Although our examples are all surfaces embedded in three-dimensional space,
the techniques generalize to any dimensionality.
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.