•  AllPairsTriangles:  Allpairs intersection testing between triangles of two meshes (CPU, GPU). 
•  ConstrainedDelaunay2D:  Constrained Delaunay triangulation that uses exact rational arithmetic (CPU). 
•  ConvexHull2D:  Convex hull for a set of 2D points that uses exact rational arithmetic (CPU). 
•  ConvexHull3D:  Convex hull for a set of 3D points that uses exact rational arithmetic (CPU). 
•  Delaunay2D:  Delaunay triangulation for a set of 2D points that uses exact rational arithmetic (CPU). 
•  Delaunay3D:  Delaunay tetrahedralization for a set of 3D points that uses exact rational arithmetic (CPU). 
•  DistanceAlignedBoxes:  Robust computation of distance between aligned boxes in any dimension. 
•  DistanceAlignedBoxOrientedBox:  Robust computation of distance between an aligned box and an oriented box in dimension 3. 
•  DistanceOrientedBoxes:  Robust computation of distance between oriented boxes in dimension 3. 
•  DistancePointConvexPolyhedron:  Robust computation of distance between a point and a convex polyhedron in dimension 3. 
•  DistanceRectangleBox:  Robust computation of distance between a rectangle and an aligned or oriented box in dimension 3. 
•  DistanceSegments3:  Robust computation of distance between line segments in any dimension (CPU and GPU). 
•  DistanceTriangleBox:  Robust computation of distance between a triangle and an aligned or oriented box in dimension 3. 
•  IntersectBoxCone:  Testintersection queries for an aligned/oriented box and a (finite) cone. 
•  IntersectBoxCylinder:  Testintersection queries for an aligned/oriented box and a (finite) cylinder. 
•  IntersectBoxSphere:  Testintersection queries for an aligned/oriented box and a sphere. 
•  IntersectSphereCone:  Testintersection queries for a sphere and a cone (infinite cone, infinite truncated cone, finite cone, cone frustum). 
•  IntersectTriangleBox:  Determine whether a triangle and an oriented box intersect. 
•  MinimalCycleBasis:  Extract all the cycles from a planar graph as a forest of cyclebasis trees. 
•  MinimumAreaBox2D:  Minimumarea bounding box for a set of 2D points that uses exact rational arithmetic (CPU). 
•  MinimumVolumeBox3D:  Minimumvolume bounding box for a set of 3D points that uses some exact rational arithmetic (CPU). 
•  MinimumAreaCircle2D:  Minimumarea circle for a set of 2D points that uses exact rational arithmetic (CPU). 
•  MinimumVolumeSphere3D:  Minimumvolume sphere for a set of 3D points that uses exact rational arithmetic (CPU). 
•  ShortestPath:  Shortest path in a weighted graph (rectangular lattice triangle mesh) (CPU, GPU). 
•  TriangulationEC:  Triangulation via ear clipping of polygons, nested polygons, and trees of nested polygons. 
•  TriangulationCDT:  Triangulation via constrained Delaunay triangulation of polygons, nested polygons, and trees of nested polygons. 
•  VertexCollapseMesh:  Vertex collapses to decimate a mesh while preserving the mesh topology. 
Allpairs comparison of triangles between two meshes to detect intersecting triangles.
The code uses GPGPU for the triangletriangle intersection testing. The same algorithm
is implemented on the CPU to give you an idea of how much faster the GPGPU version is.
The cylinder has 4416 triangles and the torus has 4608 triangles. The allpairs
testintersection queries on the GPU run at 170 frames per second on an AMD 7970.
The cylinder triangles that do not intersect torus triangles are dark blue; those
that do are cyan. The torus triangles that do not intersect cylinder triangles
are red; those that do are gold. The CPU version is better measured in terms of
seconds per frame. The application fps display shows 0.0. Whether CPU or GPU,
a boundingvolume hierarchy can be used to localize the intersection testing.
On the GPU, appendconsume buffers may be used to store results. Also, the
GPU version can be modified to compute actual line segments or points of
intersection.

Constrained Delaunay triangulation. This is a CPU implementation that
uses exact rational arithmetic for a robust (and correct) algorithm.
The unsigned integer type for the exact arithmetic uses a fixedsize
structure for speed. Of course, you need to determine how many bits of
precision are required for your algorithm in order to use a fixedsize
structure.
The row0column0 image shows the Delaunay triangulation of a random set
of points. The green edges are required to be part of the triangulation.
The row0column1 image shows the triangulation after inserting one green
edge. The row1column0 image shows the triangulation after insertion another
green edge. Thw row1column1 image shows the triangulation after insertion
of the final green edge.

Convex hull of 2D points. This is a CPU implementation that uses exact
rational arithmetic for a robust (and correct) algorithm. The unsigned
integer type for the exact arithmetic uses a variablesize structure, so
a large portion of the execution time is spent allocating and
deallocating memory. Feel free to determine how many bits of precision
are required and switch to a fixedsize structure instead in order to
improve the performance.
The left image shows the convex hull of a random set of 2D points. The
right image shows the convex hull of a 3x3 grid of points. The 3x3 grid
is a typical data set that causes problems when using floatingpoint
arithmetic, because the set has collinear points and the classification
of collinearity using signs of determinants might be incorrect due to
roundoff errors.

Convex hull of 3D points. This is a CPU implementation that uses exact
rational arithmetic for a robust (and correct) algorithm. The unsigned
integer type for the exact arithmetic uses a fixedsize structure for
speed. Of course, you need to determine how many bits of precision are
required for your algorithm in order to use a fixedsize structure.
The images show the convex hull of various data sets. These data sets
(courtesy of John Ratcliff) were ones that failed the floatingpointonly
algorithm in an earlier version of Wild Magic (leading to some scrambling
to make that algorithm more robust). All hulls are computed correctly with
the exact arithmetic of GTEngine.

Delaunay triangulation. This is a CPU implementation that uses
exact rational arithmetic for a robust (and correct) algorithm. The
unsigned integer type for the exact arithmetic uses a variablesize
structure, so a large portion of the execution time is spent allocating
and deallocating memory. Feel free to determine how many bits of
precision are required and switch to a fixedsize structure instead in
order to improve the performance.
The left image shows the Delaunay triangulation of a random set of 2D points.
The middle image shows the linearwalk search algorithm for locating a triangle that contains a point. The green triangle is where the user clicked the leftmouse button. An initial triangle is selected and the binaryspace partitioning tree implied by the triangulation is used to guide the search path to that triangle. The initial triangle is on the boundary of the triangulation, and the path leads vertically upward. You can save the last containing triangle and specify that as the starting triangle for the next search query. For spatially coherent point selections, such as in resampling of meshes for interpolation, this provides effectively an O(1) algorithm for searching. The right image shows the Delaunay triangulation for a 3x3 grid of points. This is a typical data set that cause problems for floatingpoint implementations because of the presence of cocircular points. 
Delaunay tetrahedralization. This is a CPU implementation that
uses exact rational arithmetic for a robust (and correct) algorithm.
The unsigned integer type for the exact arithmetic uses a fixedsize
structure for speed. Of course, you need to determine how many bits
of precision are required for your algorithm in order to use a
fixedsize structure.
The left image shows the Delaunay tetrahedralization of a set of random 3D points.
The middle image shows a linear walk, similar to that in 2D, to find a tetrahedron containing a query point. In this example, the query point is shown as a small black sphere. The search path starts with a purplecolored tetrahedron. The final tetrahedron is colored red. The tetrahedra from start to finish have increasing red channel and decreasing blue channel. In practice, the linear walk is an efficient algorithm, but it is known that there exist (pathological) data sets for which the search algorithm is quadratic in time. The right image shows the Delaunay tetrahedralization of a 3x3x3 grid of points. This is a typical data set that cause problems for floatingpoint implementations because of the presence of cospherical points. 
Robust computation of distance between aligned boxes in any dimension.
The algorithm is based on convex quadratic programming (CQP) and a
formulation as a linear complementarity problem (LCP).
Various configurations are shown next.

Robust computation of distance between an aligned box and an oriented box
in dimension 3. The algorithm is based on convex quadratic programming (CQP)
and a formulation as a linear complementarity problem (LCP).
Various configurations are shown next.

Robust computation of distance between oriented boxes in dimension 3.
The algorithm is based on convex quadratic programming (CQP) and a
formulation as a linear complementarity problem (LCP).
Various configurations are shown next. The rightmost configuration shows the
two boxes overlapping. The distance is zero, but the convex polyhedron of
intersection is not computed.

Robust computation of distance between a point and a convex polyhedron in dimension 3.
The algorithm is based on convex quadratic programming (CQP) and a
formulation as a linear complementarity problem (LCP).
Various configurations are shown next. The point is drawn as the center of the
green sphere. The left configuration has a face point as closest point. The
middle configuration has an edge point as closest point. The right configuration
has a vertex as closest point.

Robust computation of distance between a rectangle and an aligned box or an oriented box in dimension 3.
The algorithm is based on convex quadratic programming (CQP) and a
formulation as a linear complementarity problem (LCP).
Two configurations are shown next.

Robust computation of distance between line segments in any dimension (CPU and GPU). The sample has accuracy and performance tests, both for the CPU and GPU. The performance test involves allpairs distance computations for 16384 segments in 3D. 
Robust computation of distance between a triangle and an aligned box or an oriented box in dimension 3.
The algorithm is based on convex quadratic programming (CQP) and a
formulation as a linear complementarity problem (LCP).
Two configurations are shown next.

Determine whether an oriented box and a cone intersect in the context of
culling. The prototypical case is when the cone represents a spot light
and lighting of objects is expensive. The oriented box is a bounding box
for an object. If the bounding box does not intersect the cone, the object
need not be lit; thus, the object is culled from the lighting pass. If the
light is not attenuated, the cone is chosen to be infinite and the boxcone
intersection test is always correct. However, if the light is not attenuated
and the extent of the light's influence is modeled by using a finite cone
(infinite cone truncated by a plane perpendicular to the cone axis), then
the boxcone intersection test is conservative and can have false
positives. It is possible that the query reports an intersection when there
is none. In particular, this happens when a portion of the box is inside
the infinite cone but above the truncating plane but another portion of
the box is below the truncating plane (see the images below). The application
is dynamic, allowing you to translate and rotate the box using the keyboard.
The box is drawn in red when it intersects the cone or drawn in blue when it
does not intersect the cone.
Topleft: The initial configuration where the cone vertex is inside the box (intersection).
Topmiddle: The cone vertex is not in the box and all box vertices and edges
are outside the cone, but the cone passes through box faces (intersection).
Topright: The box is outside the cone with one edge close to the cone (no intersection).
Bottomleft: The box in the topright is moved closer to the cone. A box
edge intersects the cone but the edge endpoints are outside the cone (intersection).
Bottommiddle: The box is above the truncating plane of the cone (no intersection).
Bottomright: A false positive. The box straddles the truncating plane and
straddles the cone boundary. The query reports an intersection when there is not one.
This is akin to planeatatime boxfrustum culling for visibility testing. If a box
is outside any frustum plane, it is not visible; otherwise, draw the box. It is possible
the box straddles two frustum planesnot outside either planeyet the box does not
intersect the frustum.

Testintersection queries for an aligned/oriented box and a (finite) cylinder. The implementation uses convex quadratic programming with a formulation in terms of a Linear Complementarity Problem (LCP). The manipulation of objects is similar to that of the boxcone application. 
Testintersection queries for an aligned/oriented box and a sphere. The manipulation of objects is similar to that of the boxcone application. 
Testintersection queries for a sphere and a cone (infinite cone, infinite truncated cone,
finite cone, cone frustum). The manipulation of objects is similar to that of the
boxcone application.
Various configurations are shown next. The sphere is drawn in red. The cone wall is
drawn in blue and the cone disk caps are drawn in green when the cone and sphere are
not intersecting. The cone wall is drawn in cyan and the cone disk caps are drawn in
yellow when the cone and sphere are intersecting.

Determine whether a triangle and an oriented box intersect. The testintersection query uses the method of separating axes. The findintersection query clips the triangle against the planes of the box faces. 
Extract all the cycles from a planar graph as a forest of cyclebasis trees.
The algorithm is described in the PDF document.
The SimpleGraph1.txt file contains the information for a graph of 26 vertices
and 30 edges. The left image shows the graph with labeled vertices. The
right image shows the extracted forest of cyclebasis trees.

Minimumarea box containing a set of 2D points. This is a CPU
implementation that uses exact rational arithmetic for a robust (and
correct) algorithm. The unsigned integer type for the exact arithmetic
uses a variablesize structure, so a large portion of the execution time
is spent allocating and deallocating memory. Feel free to determine how
many bits of precision are required and switch to a fixedsize structure
instead in order to improve the performance.
The minimumarea box containing a set of 2D points randomly generated within
an oriented ellipse is shown in the image. The convex hull of the points
is drawn in red. The box is drawn in blue.

Minimumarea box containing a set of 2D points. This is a CPU
implementation that uses exact rational arithmetic for a robust (and
correct) algorithm. The unsigned integer type for the exact arithmetic
uses a variablesize structure, so a large portion of the execution time
is spent allocating and deallocating memory. Feel free to determine how
many bits of precision are required and switch to a fixedsize structure
instead in order to improve the performance.
The minimumarea box containing a set of 2D points randomly generated within
an oriented ellipse is shown in the image. The convex hull of the points
is drawn in red. The box is drawn in blue.

Minimumvolume box containing a set of 3D points. This is a CPU
implementation that uses exact rational arithmetic to compute the convex
hull of the points. The minimumvolume box is selected from those boxes
that are coincident with a face of the hull or with three perpendicular
edges of the hull. The algorithm requires projection onto planes and
lines, and it is not tractible to compute with exact rational arithmetic.
This portion of the algorithm switches to floatingpoint arithmetic, so
there is the potential for roundoff errors that leads to a box that is
close to, but not, the theoretical minimumvolume box.
The minimumarea box containing a set of 3D points randomly generated within
an oriented ellipsoid is shown in the image. The wireframe of the convex hull
of the points is visible as well as the wireframe of the bounding box.

Minimumarea circle containing a set of 2D points. This is a CPU
implementation that uses exact rational arithmetic for a robust (and
correct) algorithm. The unsigned integer type for the exact arithmetic
uses a variablesize structure, so a large portion of the execution time
is spent allocating and deallocating memory. Feel free to determine how
many bits of precision are required and switch to a fixedsize structure
instead in order to improve the performance.
The sample displays the minimumarea circle as you insert each point one
at a time. The first row of images (left to right) show insertion of two,
three, and four points. The next row, first column. shows insertion of many but not
all of the points. The last image shows insertion of all the point; in this
example, the minimumarea circle is supported by two points.

Minimumvolume sphere containing a set of 3D points. This is a CPU
implementation that uses exact rational arithmetic for a robust (and
correct) algorithm. The unsigned integer type for the exact arithmetic
uses a variablesize structure, so a large portion of the execution time
is spent allocating and deallocating memory. Feel free to determine how
many bits of precision are required and switch to a fixedsize structure
instead in order to improve the performance.
The sample displays the minimumvolume sphere as you insert each point one
at a time. The first row of images (left to right) show insertion of two,
three, and four points. The next row, first column. shows insertion of many but not
all of the points. The last image shows insertion of all the point; in this
example, the minimumvolume sphere is supported by four points.

Compute the shortest path in a weigted graph, which in this sample is
a rectangular array of nodes and each node has three predecessors. The
implementation is GPGPU. A CPU implementation is provided for
comparison, both for performance and to show that the GPU version is not
straightforwardit uses dynamic programming to compute partial sums of
numbers in parallel.
The left image shows a Bezier bicubic grayscale image with additive random
noise. This image acts as the weights of the graph. The shortest path is
drawn in red. The right image shows the shortest path when no random noise
is added. This path is as you would expect. The path follows dark parts of
the image, initially along the top border. It then steers towards the nearest
saddle point to head towards the dark basin. It then exits the basin and
heads towards the saddle point near the lowerright corner.

Triangulation via ear clipping of polygons, nested polygons, and trees of nested polygons.
In the first row, the triangulation of a simple polygon is shown in the
left image. The middle image shows a polygon with a single hole. The right
image shows a polygon with two holes. In the bottom row, the left image is
the triangulation of a tree of nested polygons. The right image is the
triangulation of a polygon with three holes. The sample code generates the
triangulations for each of the six possible orderings of the holes, leading
to valid triangulations in all cases.

Triangulation via constrained Delaunay triangulation of polygons, nested polygons, and trees of nested polygons.
The TriangulateCDT class produces a convex hull of the polygon vertices and requires
that the polygon edges are in the triangulation. The triangles are either inside or outside
the polygon. Those inside form the triangulation of the polygon. However, having the convex hull is
useful for applications that want to test for triangle containment. You can use a PlanarMesh
object of the output triangles, which allows you to determine which triangle contains the query
point. That triangle's index can be passed to a TriangulateCDT function that tells you
whether the triangle is inside or outside the triangulation. A typical application might be
interpolation of function data that is defined on a nonconvex domain.
The sample application uses the same polygons as for TriangulationEC. However,
a PlanarMesh object is built from the triangulation. Each pixel in the
image is sent to a pointintriangle query. If in a triangle, a query is made
to determine whether it is inside or outside the polygon triangulation. If inside,
the pixel is colored blue; if outside, the pixel is colored orange.

Vertex collapses to decimate a mesh while preserving the mesh topology.
The top row of images is the original mesh, an approximation to a cylinder, and is
shown as a solid surface and as a wireframe surface. The bottom row of images is
the mesh with 12 vertex collapses applied.
