Sample Applications: Geometrics

AllPairsTriangles: All-pairs 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: Test-intersection queries for an aligned/oriented box and a (finite) cone.
IntersectBoxCylinder: Test-intersection queries for an aligned/oriented box and a (finite) cylinder.
IntersectBoxSphere: Test-intersection queries for an aligned/oriented box and a sphere.
IntersectTriangleBox: Determine whether a triangle and an oriented box intersect.
MinimalCycleBasis: Extract all the cycles from a planar graph as a forest of cycle-basis trees.
MinimumAreaBox2D: Minimum-area bounding box for a set of 2D points that uses exact rational arithmetic (CPU).
MinimumVolumeBox3D: Minimum-volume bounding box for a set of 3D points that uses some exact rational arithmetic (CPU).
MinimumAreaCircle2D: Minimum-area circle for a set of 2D points that uses exact rational arithmetic (CPU).
MinimumVolumeSphere3D: Minimum-volume 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.

All-pairs comparison of triangles between two meshes to detect intersecting triangles. The code uses GPGPU for the triangle-triangle 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 all-pairs test-intersection 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 bounding-volume hierarchy can be used to localize the intersection testing. On the GPU, append-consume buffers may be used to store results. Also, the GPU version can be modified to compute actual line segments or points of intersection.

AllPairsTriangles0

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 fixed-size structure for speed. Of course, you need to determine how many bits of precision are required for your algorithm in order to use a fixed-size structure. The row0-column0 image shows the Delaunay triangulation of a random set of points. The green edges are required to be part of the triangulation. The row0-column1 image shows the triangulation after inserting one green edge. The row1-column0 image shows the triangulation after insertion another green edge. Thw row1-column1 image shows the triangulation after insertion of the final green edge.

ConstrainedDelaunay2D_0 ConstrainedDelaunay2D_1
ConstrainedDelaunay2D_2 ConstrainedDelaunay2D_3

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 variable-size 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 fixed-size 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 floating-point arithmetic, because the set has collinear points and the classification of collinearity using signs of determinants might be incorrect due to round-off errors.

ConvexHull2D_0 ConvexHull2D_1

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 fixed-size structure for speed. Of course, you need to determine how many bits of precision are required for your algorithm in order to use a fixed-size structure. The images show the convex hull of various data sets. These data sets (courtesy of John Ratcliff) were ones that failed the floating-point-only 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.

ConvexHull3D_0 ConvexHull3D_1 ConvexHull3D_2

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 variable-size 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 fixed-size 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 linear-walk search algorithm for locating a triangle that contains a point. The green triangle is where the user clicked the left-mouse button. An initial triangle is selected and the binary-space 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 floating-point implementations because of the presence of cocircular points.

Delaunay2D_0 Delaunay2D_1 Delaunay2D_2

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 fixed-size structure for speed. Of course, you need to determine how many bits of precision are required for your algorithm in order to use a fixed-size 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 purple-colored 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 floating-point implementations because of the presence of cospherical points.

Delaunay3D_0 Delaunay3D_1 Delaunay3D_2

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).

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).

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).

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).

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).

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 all-pairs 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).

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 box-cone 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 box-cone 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. Top-left: The initial configuration where the cone vertex is inside the box (intersection). Top-middle: 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). Top-right: The box is outside the cone with one edge close to the cone (no intersection). Bottom-left: The box in the top-right is moved closer to the cone. A box edge intersects the cone but the edge endpoints are outside the cone (intersection). Bottom-middle: The box is above the truncating plane of the cone (no intersection). Bottom-right: 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 plane-at-a-time box-frustum 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 planes--not outside either plane--yet the box does not intersect the frustum.

IntersectBoxCone0 IntersectBoxCone1 IntersectBoxCone2
IntersectBoxCone3 IntersectBoxCone4 IntersectBoxCone5

Test-intersection 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 box-cone application.

Test-intersection queries for an aligned/oriented box and a sphere. The manipulation of objects is similar to that of the box-cone application.

Determine whether a triangle and an oriented box intersect. The test-intersection query uses the method of separating axes. The find-intersection query clips the triangle against the planes of the box faces.

Extract all the cycles from a planar graph as a forest of cycle-basis 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 cycle-basis trees.

MinimalCycleBasis0 MinimalCycleBasis1

Minimum-area 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 variable-size 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 fixed-size structure instead in order to improve the performance. The minimum-area 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.

MinimumAreaBox2D_0

Minimum-area 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 variable-size 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 fixed-size structure instead in order to improve the performance. The minimum-area 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.

MinimumAreaBox2D_0

Minimum-volume 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 minimum-volume 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 floating-point arithmetic, so there is the potential for round-off errors that leads to a box that is close to, but not, the theoretical minimum-volume box. The minimum-area 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.

MinimumVolumeBox3D_0

Minimum-area 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 variable-size 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 fixed-size structure instead in order to improve the performance. The sample displays the minimum-area 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 minimum-area circle is supported by two points.

MinimumAreaCircle2D_0 MinimumAreaCircle2D_1 MinimumAreaCircle2D_2
MinimumAreaCircle2D_3 MinimumAreaCircle2D_4

Minimum-volume 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 variable-size 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 fixed-size structure instead in order to improve the performance. The sample displays the minimum-volume 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 minimum-volume sphere is supported by four points.

MinimumVolumeSphere3D_0 MinimumVolumeSphere3D_1 MinimumVolumeSphere3D_2
MinimumVolumeSphere3D_3 MinimumVolumeSphere3D_4

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 straightforward--it uses dynamic programming to compute partial sums of numbers in parallel. The left image shows a Bezier bicubic gray-scale 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 lower-right corner.

ShortestPath0 ShortestPath1

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.

TriangulationEC_0 TriangulationEC_1 TriangulationEC_2
TriangulationEC_3 TriangulationEC_4

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 point-in-triangle 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.

TriangulationCDT_0 TriangulationCDT_1
TriangulationCDT_2 TriangulationCDT_3

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.

VertexCollapseMesh0 VertexCollapseMesh1
VertexCollapseMesh2 VertexCollapseMesh3