j3d.org Code

org.j3d.geom Class TriangulationUtils

java.lang.Object org.j3d.geom.TriangulationUtils

public class TriangulationUtils
extends java.lang.Object

Utility routines for triangulating arbitrary polygons.

The concave triangulation routine is designed for small numbers of vertices as it uses a much simpler, but slower algorithm that is O(kn) where k is the number of concave vertices, rather than the more efficient, but much more complex to implement Seidel's Algorithm. A summary of the implementation can be found here.

If at any time an error is detected in the input geometry, the return value of the triangulation methods will be a negative value. The number will still indicate the number of triangles successfully created for the return, but the negative is used to indicate an error occurred that could not allow for any more triangulation to take place.

Seidel's algorithm is described here: http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html

Version:
\$Revision: 1.8 \$
Author:
Justin Couch, Eric Fickenscher

Constructor Summary
TriangulationUtils()
Construct a new instance of the triangulation utilities.
TriangulationUtils(int size)
Construct a new instance of the triangulation utilities with a given maximum polygon size hint.

Method Summary
void clearCachedObjects()
Clean up the internal cache and reduce it to zero.
static boolean isConvexVertex(float[] coords, int p0, int p, int p1, float[] normal)
Check to see if this vertex is a concave vertex or convex.
int triangulateConcavePolygon(float[] coords, int[] coordOutput, float[] normal)
Triangulate a concave polygon in the given array.
int triangulateConcavePolygon(float[] coords, int[] coordIndex, int[] coordOutput, float[] normal)
Triangulate a concave polygon using an indexed coordinates array.
int triangulateConcavePolygon(float[] coords, int startIndex, int numVertex, int[] coordOutput, float[] normal)
Triangulate a concave polygon in the given array.
int triangulateConcavePolygon(float[] coords, int startIndex, int numVertex, int[] coordIndex, int[] coordOutput, float[] normal)
Triangulate a concave polygon using an indexed coordinates array.
int triangulateConcavePolygon(float[] coords, int startIndex, int numVertex, int[] coordIndex, int firstNormalIndex, int[] normalIndex, int firstColorIndex, int[] colorIndex, int firstTexCoordIndex, int[] texCoordIndex, int[] coordOutput, int[] normalOutput, int[] colorOutput, int[] texCoordOutput, float[] normal)
Triangulate a concave polygon using an indexed coordinates array.
int triangulateConcavePolygon(float[] coords, int startIndex, int numVertex, int firstNormalIndex, int firstColorIndex, int firstTexCoordIndex, int[] coordOutput, int[] normalOutput, int[] colorOutput, int[] texCoordOutput, float[] normal)
Triangulate a concave polygon in the given array.
void triangulatePolygon2D(int numContours, int[] contourCounts, float[] vertices, int[] triangles)
Triangulate a simple polygon that may have zero or more holes in it.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

TriangulationUtils

public TriangulationUtils()
Construct a new instance of the triangulation utilities. Assumes a default max polygon size of 6 vertices.

TriangulationUtils

public TriangulationUtils(int size)
Construct a new instance of the triangulation utilities with a given maximum polygon size hint. A number of internal structures are created and this hint is used to ensure that the structures are large enough and don't need to be dynamically re-created during the triangulation process.

Parameters:
size - Hint to the maximum size of polygon to deal with
Method Detail

triangulatePolygon2D

public void triangulatePolygon2D(int numContours,
int[] contourCounts,
float[] vertices,
int[] triangles)
Triangulate a simple polygon that may have zero or more holes in it. There is no requirement for the polygon to be concave, but it will be limited to two-dimensional coordinate systems. If you have a polygon in 3 dimensions, you will need to project it to 2 dimensions before calling this method.

Each part of the polygon is defined by a set of contour points. The outer-most set of points must be defined in counter-clockwise order. All inner points must be defined in clock-wise order.

triangulateConcavePolygon

public int triangulateConcavePolygon(float[] coords,
int startIndex,
int numVertex,
int[] coordIndex,
int[] coordOutput,
float[] normal)
Triangulate a concave polygon using an indexed coordinates array. The start index is the index into the indexArray for the first vertex of the polygon. The coordinates are not required to be a closed polygon as the algorithm will automatically close it. The output array is the new indexes to use.

If an error occurs, the result will be negative number of triangles.

Parameters:
coords - The coordinates of the face
startIndex - The index of the first coordinate in the face
numVertex - The number of vertices to read from the list
coordOutput - The array to copy the coord index values to
normal - The normal to this face these vertices are a part of
Returns:
The number of triangles in the output array

triangulateConcavePolygon

public int triangulateConcavePolygon(float[] coords,
int[] coordIndex,
int[] coordOutput,
float[] normal)
Triangulate a concave polygon using an indexed coordinates array. Assumes that the index of the first coordinate in the coordIndex is 0. Will read every vertex from the coordIndex list (ie: numVertex = coordIndex.length) The coordinates are not required to be a closed polygon as the algorithm will automatically close it. The output array is the new indexes to use.

If an error occurs, the result will be negative number of triangles.

Parameters:
coords - The coordinates of the face
coordOutput - The array to copy the coord index values to
normal - The normal to this face these vertices are a part of
Returns:
The number of triangles in the output array

triangulateConcavePolygon

public int triangulateConcavePolygon(float[] coords,
int startIndex,
int numVertex,
int[] coordIndex,
int firstNormalIndex,
int[] normalIndex,
int firstColorIndex,
int[] colorIndex,
int firstTexCoordIndex,
int[] texCoordIndex,
int[] coordOutput,
int[] normalOutput,
int[] colorOutput,
int[] texCoordOutput,
float[] normal)
Triangulate a concave polygon using an indexed coordinates array. The start index is the index into the indexArray for the first vertex of the polygon. The coordinates are not required to be a closed polygon as the algorithm will automatically close it. The output array is the new indexes to use

If an error occurs, the result will be negative number of triangles.

Parameters:
coords - The coordinates of the face
startIndex - The index of the first coordinate in the face
numVertex - The number of vertices to read from the list
firstNormalIndex - The first position of the normalIndex array
normalIndex - The index of normals for each coordinate
firstColorIndex - The first position of the colorIndex array
colorIndex - The index of color for each coordinate
firstTexCoordIndex - The first position of the texCoordIndex array
texCoordIndex - The index of textureCoordinates for each coordinate
coordOutput - The array to copy the coord index values to
normalOutput - The array to copy the normal index values to
colorOutput - The array to copy the color index values to
texCoordOutput - The array to copy the texCoord index values to
normal - The normal to this face these vertices are a part of
Returns:
The number of triangles in the output array

triangulateConcavePolygon

public int triangulateConcavePolygon(float[] coords,
int startIndex,
int numVertex,
int[] coordOutput,
float[] normal)
Triangulate a concave polygon in the given array. The array is a flat array of coordinates of [...Xn, Yn, Zn....] values. The start index is the index into the array of the X component of the first item, while the endIndex is the index into the array of the X component of the last item. The coordinates are not required to be a closed polygon as the algorithm will automatically close it. The output array is indexes into the original array (including compensating for the 3 index values per coordinate)

If an error occurs, the result will be negative number of triangles.

Parameters:
coords - The coordinates of the face
startIndex - The index of the first coordinate in the face
numVertex - The number of vertices to read from the list
coordOutput - The array to copy the coord index values to
normal - The normal to this face these vertices are a part of
Returns:
The number of triangles in the output array

triangulateConcavePolygon

public int triangulateConcavePolygon(float[] coords,
int[] coordOutput,
float[] normal)
Triangulate a concave polygon in the given array. The array is a flat array of coordinates of [...Xn, Yn, Zn....] values. Assumes that the index of the first coordinate in the face is 0. Will read every vertex from the list (ie: numVertex = coords.length/3) The coordinates are not required to be a closed polygon as the algorithm will automatically close it. The output array is indexes into the original array (including compensating for the 3 index values per coordinate)

If an error occurs, the result will be negative number of triangles.

Parameters:
coords - The coordinates of the face
coordOutput - The array to copy the coord index values to
normal - The normal to this face these vertices are a part of
Returns:
The number of triangles in the output array

triangulateConcavePolygon

public int triangulateConcavePolygon(float[] coords,
int startIndex,
int numVertex,
int firstNormalIndex,
int firstColorIndex,
int firstTexCoordIndex,
int[] coordOutput,
int[] normalOutput,
int[] colorOutput,
int[] texCoordOutput,
float[] normal)
Triangulate a concave polygon in the given array. The array is a flat array of coordinates of [...Xn, Yn, Zn....] values. The start index is the index into the array of the X component of the first item, while the endIndex is the index into the array of the X component of the last item. The coordinates are not required to be a closed polygon as the algorithm will automatically close it. The output array is indexes into the original array (including compensating for the 3 index values per coordinate)

If an error occurs, the result will be negative number of triangles.

Parameters:
coords - The coordinates of the face
startIndex - The index of the first coordinate in the face
numVertex - The number of vertices to read from the list
firstNormalIndex - The first position of the normalIndex array
firstColorIndex - The index of color for each coordinate
firstTexCoordIndex - The first position of the texCoordIndex array
coordOutput - The array to copy the coord index values to
normalOutput - The array to copy the normal index values to
colorOutput - The array to copy the color index values to
texCoordOutput - The array to copy the texCoord index values to
normal - The normal to this face these vertices are a part of
Returns:
The number of triangles in the output array

clearCachedObjects

public void clearCachedObjects()
Clean up the internal cache and reduce it to zero.

isConvexVertex

public static boolean isConvexVertex(float[] coords,
int p0,
int p,
int p1,
float[] normal)
Check to see if this vertex is a concave vertex or convex. It assumes a right-handed coordinate system and counter-clockwise ordering of the vertices. The coordinate array is assumed to be flat with vertex values stored [ ... Xn, Yn, Zn, ...] with the index values provided assuming that flattened structure (ie Pi = n, Pi+1 = n + 3). The turn direction is given by n . (a x b) <= 0 (always want right turns).

Parameters:
coords - The array to read coodinate values from
p0 - The index of the previous vertex to the one in question
p - The index of the vertex being tested
p1 - The index after the vertex after the one in question
normal - The normal to this face these vertices are a part of
Returns:
true if this is a convex vertex, false for concave

j3d.org Code

Latest Info from http://code.j3d.org/