j3d.org Code

## org.j3d.geom Class TriangulationUtils

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

`public class TriangulationUtilsextends 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/