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