Version 5 (modified by martin, 7 years ago)

--

OsgUtil delaunayTriangulator

back

The OsgUtil delaunayTriangulator library function converts randomly spaced (or regularly spaced) points into an optimised sheet of triangles.

Delaunay triangles are those which are most nearly equilateral (given a choice of triangles, the more nearly equilateral triangulation is chosen).

It is not obvious, but the Delaunay triangulation is equivalent to finding the set of triangles linking up the points where the unique circle passing through the 3 vertices of each triangle does not contain any other points 1. A very nice Java applet for exploring Delaunay triangulations is at 2 - this also explains the link between Voronoi spaces and Delaunay triangulations if you really need to know.

A constrained triangulation follows the same rules, but some of the edges joining points are forced (for example the edges of a road are forced to be edges of triangles in the triangulation). See 3.

The osgUtil tesselator assumes that the sheet to be fitted through the data is largely in the X-Y plane (that is the Z direction is UP). The sheet formed is always single valued.

Internally the triangulator places 3 points around the points to be tesselated forming a super-triangle which completely contains the points to be triangulated. The extra points are removed after the triangulation. This super-triangle is the first triangle; obviously it contains many other points and will not be part of the final triangles. The algorithm then searches for a point contained in the super-triangle, and divides the supertriangle into at least 2 triangles (usually 3); the supertriangle is deleted. Then each of the smaller triangles is searched for a containing point; if found divide and delete as before. This continues until no more points are found in the triangles.

The constraint method (Released Nov 2005) adds the DelaunayConstraint class. The terrain is then formed of points on the terrain plus constraint points (the edges of the constraints, for example edges of roads). The Delaunay Triangulator takes the unconstrained triangulation of the data points plus the constraining points and then considers each edge of the constraint line. All triangles with a (Delaunay triangulated) edge crossed by a constraint edge is deleted. This leaves a hole in the triangulated sheet. The hole is divided into 2 polygons by the constraining edge, and each part is filled by the OsgUtilTesselator routine.