org.j3d.geom
Class IntersectionUtils

java.lang.Object
  org.j3d.geom.IntersectionUtils

public class IntersectionUtils
extends java.lang.Object

A collection of utility methods to do geometry intersection tests.

The design of the implementation is focused towards realtime intersection requirements for collision detection and terrain following. We avoid the standard pattern of making the methods static because we believe that you may need multiple copies of this class floating around. Internally it will also seek to reduce the amount of garbage generated by allocating arrays of data and then maintaining those arrays between calls. Arrays are only resized if they need to get bigger. Smaller data than the currently allocated structures will use the existing data. For the same reason, we do not synchronise any of the methods. If you expect to have multiple threads needing to do intersection testing, we suggest you have separate copies of this class as no results are guaranteed if you are accessing this instance with multiple threads.

Calculation of the values works by configuring the class for the sort of data that you want returned. For the higher level methods that allow you

If you need the intersection tools for collision detection only, then you can tell the routines that you only need to know if they intersect. That is as soon as you detect one polygon that intersects, exit immediately. This is useful for doing collision detection because you really don't care where on the object you collide, just that you have.

The ray/polygon intersection test is a combination test. Firstly it will check for the segment intersection if requested. Then, for an infinite ray or an intersecting segment, we use the algorithm defined from the Siggraph paper in their education course:

• Ray-Polygon
• Ray-Sphere
• Ray-Plane
• Ray-Cylinder

Version:

$Revision: 1.20 $

Author:

Justin Couch

Field Summary

protected javax.vecmath.Vector3d	pickDir
protected javax.vecmath.Point3d	pickStart Transformed pick items
protected float[]	wkPolygon Working places for a single quad
protected float[]	working2dCoords The current 2D coordinate list that we work from
protected float[]	workingCoords The current coordinate list that we work from
protected int[]	workingIndicies
protected int[]	workingStrips
static int	X_AXIS Cylinder intersection axis X
static int	Y_AXIS Cylinder intersection axis Y
static int	Z_AXIS Cylinder intersection axis Z

Constructor Summary

IntersectionUtils()
Create a default instance of this class with no internal data structures allocated.

Method Summary

void	clear() Clear the current internal structures to reduce the amount of memory used.
boolean	rayCylinder(float[] origin, float[] direction, int axis, float[] cylAxis, float cylRadius, float[] point) Compute the intersection point of the ray and an infinite cylinder.
boolean	rayCylinder(javax.vecmath.Point3d origin, javax.vecmath.Vector3d direction, int axis, float[] cylAxis, float cylRadius, javax.vecmath.Point3d point) Compute the intersection point of the ray and an infinite cylinder.
boolean	rayIndexedQuadArray(javax.vecmath.Point3d origin, javax.vecmath.Vector3d direction, float length, float[] coords, int[] indexes, int numIndex, javax.vecmath.Point3d point, boolean intersectOnly) Test an array of indexed quads for intersection.
boolean	rayIndexedTriangleArray(javax.vecmath.Point3d origin, javax.vecmath.Vector3d direction, float length, float[] coords, int[] indexes, int numIndex, javax.vecmath.Point3d point, boolean intersectOnly) Test an array of indexed triangles for intersection.
boolean	rayPlane(float[] origin, float[] direction, float[] plane, float[] point) Compute the intersection point of the ray and a plane.
boolean	rayPlane(javax.vecmath.Point3d origin, javax.vecmath.Vector3d direction, float[] plane, javax.vecmath.Point3d point) Compute the intersection point of the ray and a plane.
boolean	rayPolygon(javax.vecmath.Point3d origin, javax.vecmath.Vector3d direction, float length, float[] coords, int numCoords, javax.vecmath.Point3d point) Test to see if the polygon intersects with the given ray.
boolean	rayQuadArray(javax.vecmath.Point3d origin, javax.vecmath.Vector3d direction, float length, float[] coords, int numQuads, javax.vecmath.Point3d point, boolean intersectOnly) Test an array of quads for intersection.
boolean	raySphere(float[] origin, float[] direction, float[] sphereCenter, float sphereRadius, float[] point) Compute the intersection point of the ray and a sphere.
boolean	raySphere(javax.vecmath.Point3d origin, javax.vecmath.Vector3d direction, float[] sphereCenter, float sphereRadius, javax.vecmath.Point3d point) Compute the intersection point of the ray and a sphere.
boolean	rayTriangleArray(javax.vecmath.Point3d origin, javax.vecmath.Vector3d direction, float length, float[] coords, int numTris, javax.vecmath.Point3d point, boolean intersectOnly) Test an array of triangles for intersection.
boolean	rayTriangleFanArray(javax.vecmath.Point3d origin, javax.vecmath.Vector3d direction, float length, float[] coords, int[] stripCounts, int numStrips, javax.vecmath.Point3d point, boolean intersectOnly) Test an array of triangle fans for intersection.
boolean	rayTriangleStripArray(javax.vecmath.Point3d origin, javax.vecmath.Vector3d direction, float length, float[] coords, int[] stripCounts, int numStrips, javax.vecmath.Point3d point, boolean intersectOnly) Test an array of triangles strips for intersection.
boolean	rayUnknownGeometry(javax.vecmath.Point3d origin, javax.vecmath.Vector3d direction, float length, GeometryData data, javax.vecmath.Matrix4d vworldTransform, javax.vecmath.Point3d point, boolean intersectOnly) Convenience method to process a GeometryData and ask the intersection code to find out what the real geometry type is and process it appropriately.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

X_AXIS

public static final int X_AXIS

Cylinder intersection axis X

See Also:

Constant Field Values

Y_AXIS

public static final int Y_AXIS

Cylinder intersection axis Y

See Also:

Constant Field Values

Z_AXIS

public static final int Z_AXIS

Cylinder intersection axis Z

See Also:

Constant Field Values

pickStart

protected javax.vecmath.Point3d pickStart

Transformed pick items

pickDir

protected javax.vecmath.Vector3d pickDir

workingCoords

protected float[] workingCoords

The current coordinate list that we work from

workingStrips

protected int[] workingStrips

workingIndicies

protected int[] workingIndicies

working2dCoords

protected float[] working2dCoords

The current 2D coordinate list that we work from

wkPolygon

protected float[] wkPolygon

Working places for a single quad

Constructor Detail

IntersectionUtils

public IntersectionUtils()

Create a default instance of this class with no internal data structures allocated.

Method Detail

clear

public void clear()

Clear the current internal structures to reduce the amount of memory used. It is recommended you use this method with caution as then next time a user calls this class, all the internal structures will be reallocated. If this is running in a realtime environment, that could be very costly - both allocation and the garbage collection that results from calling this method

rayUnknownGeometry

public boolean rayUnknownGeometry(javax.vecmath.Point3d origin,
                                  javax.vecmath.Vector3d direction,
                                  float length,
                                  GeometryData data,
                                  javax.vecmath.Matrix4d vworldTransform,
                                  javax.vecmath.Point3d point,
                                  boolean intersectOnly)

Convenience method to process a GeometryData and ask the intersection code to find out what the real geometry type is and process it appropriately. If there is an intersection, the point will contain the exact intersection point on the geometry.

This code will be much more efficient than the other version because we do not need to reallocate internal arrays all the time or have the need to set capability bits, hurting performance optimisations. If the geometry array does not understand the provided geometry type, it will silently ignore the request and always return false.

Parameters:

origin - The origin of the ray

direction - The direction of the ray

length - An optional length for to make the ray a segment. If the value is zero, it is ignored

data - The geometry to test against

point - The intersection point for returning

vworldTransform - Transformation matrix to go from the root of the world to this point

intersectOnly - true if we only want to know if we have a intersection and don't really care which it is

Returns:

true if there was an intersection, false if not

rayTriangleArray

public boolean rayTriangleArray(javax.vecmath.Point3d origin,
                                javax.vecmath.Vector3d direction,
                                float length,
                                float[] coords,
                                int numTris,
                                javax.vecmath.Point3d point,
                                boolean intersectOnly)

Test an array of triangles for intersection. Returns the closest intersection point to the origin of the picking ray. Assumes that the coordinates are ordered as [Xn, Yn, Zn] and are translated into the same coordinate system that the the origin and direction are from.

Parameters:

origin - The origin of the ray

direction - The direction of the ray

length - An optional length for to make the ray a segment. If the value is zero, it is ignored

coords - The coordinates of the triangles

numTris - The number of triangles to use from the array

point - The intersection point for returning

intersectOnly - true if we only want to know if we have a intersection and don't really care which it is

Returns:

true if there was an intersection, false if not

rayQuadArray

public boolean rayQuadArray(javax.vecmath.Point3d origin,
                            javax.vecmath.Vector3d direction,
                            float length,
                            float[] coords,
                            int numQuads,
                            javax.vecmath.Point3d point,
                            boolean intersectOnly)

Test an array of quads for intersection. Returns the closest intersection point to the origin of the picking ray. Assumes that the coordinates are ordered as [Xn, Yn, Zn] and are translated into the same coordinate system that the the origin and direction are from.

Parameters:

origin - The origin of the ray

direction - The direction of the ray

length - An optional length for to make the ray a segment. If the value is zero, it is ignored

coords - The coordinates of the quads

numQuads - The number of quads to use from the array

point - The intersection point for returning

intersectOnly - true if we only want to know if we have a intersection and don't really care which it is

Returns:

true if there was an intersection, false if not

rayTriangleStripArray

public boolean rayTriangleStripArray(javax.vecmath.Point3d origin,
                                     javax.vecmath.Vector3d direction,
                                     float length,
                                     float[] coords,
                                     int[] stripCounts,
                                     int numStrips,
                                     javax.vecmath.Point3d point,
                                     boolean intersectOnly)

Test an array of triangles strips for intersection. Returns the closest intersection point to the origin of the picking ray. Assumes that the coordinates are ordered as [Xn, Yn, Zn] and are translated into the same coordinate system that the the origin and direction are from.

Parameters:

origin - The origin of the ray

direction - The direction of the ray

length - An optional length for to make the ray a segment. If the value is zero, it is ignored

coords - The coordinates of the triangles

stripCounts - The number of polygons in each strip

numStrips - The number of strips to use from the array

point - The intersection point for returning

intersectOnly - true if we only want to know if we have a intersection and don't really care which it is

Returns:

true if there was an intersection, false if not

rayTriangleFanArray

public boolean rayTriangleFanArray(javax.vecmath.Point3d origin,
                                   javax.vecmath.Vector3d direction,
                                   float length,
                                   float[] coords,
                                   int[] stripCounts,
                                   int numStrips,
                                   javax.vecmath.Point3d point,
                                   boolean intersectOnly)

Test an array of triangle fans for intersection. Returns the closest intersection point to the origin of the picking ray. Assumes that the coordinates are ordered as [Xn, Yn, Zn] and are translated into the same coordinate system that the the origin and direction are from.

Parameters:

origin - The origin of the ray

direction - The direction of the ray

length - An optional length for to make the ray a segment. If the value is zero, it is ignored

coords - The coordinates of the triangles

stripCounts - The number of polygons in each fan

numStrips - The number of strips to use from the array

point - The intersection point for returning

intersectOnly - true if we only want to know if we have a intersection and don't really care which it is

Returns:

true if there was an intersection, false if not

rayIndexedTriangleArray

public boolean rayIndexedTriangleArray(javax.vecmath.Point3d origin,
                                       javax.vecmath.Vector3d direction,
                                       float length,
                                       float[] coords,
                                       int[] indexes,
                                       int numIndex,
                                       javax.vecmath.Point3d point,
                                       boolean intersectOnly)

Test an array of indexed triangles for intersection. Returns the closest intersection point to the origin of the picking ray. Assumes that the coordinates are ordered as [Xn, Yn, Zn] and are translated into the same coordinate system that the the origin and direction are from.

Parameters:

origin - The origin of the ray

direction - The direction of the ray

length - An optional length for to make the ray a segment. If the value is zero, it is ignored

coords - The coordinates of the triangles

indexes - The list of indexes to use to construct triangles

numIndex - The number of indexes to use from the array

point - The intersection point for returning

intersectOnly - true if we only want to know if we have a intersection and don't really care which it is

Returns:

true if there was an intersection, false if not

rayIndexedQuadArray

public boolean rayIndexedQuadArray(javax.vecmath.Point3d origin,
                                   javax.vecmath.Vector3d direction,
                                   float length,
                                   float[] coords,
                                   int[] indexes,
                                   int numIndex,
                                   javax.vecmath.Point3d point,
                                   boolean intersectOnly)

Test an array of indexed quads for intersection. Returns the closest intersection point to the origin of the picking ray. Assumes that the coordinates are ordered as [Xn, Yn, Zn] and are translated into the same coordinate system that the the origin and direction are from.

Parameters:

origin - The origin of the ray

direction - The direction of the ray

length - An optional length for to make the ray a segment. If the value is zero, it is ignored

coords - The coordinates of the triangles

indexes - The list of indexes to use to construct triangles

numIndex - The number of indexes to use from the array

point - The intersection point for returning

intersectOnly - true if we only want to know if we have a intersection and don't really care which it is

Returns:

true if there was an intersection, false if not

rayCylinder

public boolean rayCylinder(float[] origin,
                           float[] direction,
                           int axis,
                           float[] cylAxis,
                           float cylRadius,
                           float[] point)
                    throws java.lang.IllegalArgumentException

Compute the intersection point of the ray and an infinite cylinder. This is limited to an intersection along one of the axes.

The cylAxis value refers to the coefficients for the axis of the cylinder that does not pass through the origin. If we assume the general equation for a cylinder that lies along the X axis is (y - b)^2 + (z - c)^2 = r^2 then the values of this parameter represent the coefficients (a, b, c). For the given axis, only the two coefficients for the other axes are used.

Parameters:

origin - The origin of the ray

direction - The direction of the ray

axis - Identifier of which axis this is aligned to

cylAxis - The vector coefficients describing the axis of the cylinder

cylRadius - The raduis of the cylinder

point - The intersection point for returning

Returns:

true if there was an intersection, false if not

Throws:

java.lang.IllegalArgumentException - The axis ID given is not valid

rayCylinder

public boolean rayCylinder(javax.vecmath.Point3d origin,
                           javax.vecmath.Vector3d direction,
                           int axis,
                           float[] cylAxis,
                           float cylRadius,
                           javax.vecmath.Point3d point)
                    throws java.lang.IllegalArgumentException

Compute the intersection point of the ray and an infinite cylinder. This is limited to an intersection along one of the axes.

The cylAxis value refers to the coefficients for the axis of the cylinder that does not pass through the origin. If we assume the general equation for a cylinder that lies along the X axis is (y - b)^2 + (z - c)^2 = r^2 then the values of this parameter represent the coefficients (a, b, c). For the given axis, only the two coefficients for the other axes are used.

Parameters:

origin - The origin of the ray

direction - The direction of the ray

axis - Identifier of which axis this is aligned to

cylAxis - The vector coefficients describing the axis of the cylinder

cylRadius - The raduis of the cylinder

point - The intersection point for returning

Returns:

true if there was an intersection, false if not

Throws:

java.lang.IllegalArgumentException - The axis ID given is not valid

raySphere

public boolean raySphere(float[] origin,
                         float[] direction,
                         float[] sphereCenter,
                         float sphereRadius,
                         float[] point)

Compute the intersection point of the ray and a sphere.

Parameters:

origin - The origin of the ray

direction - The direction of the ray

sphereCenter - The coordinates of the center of the sphere

sphereRadius - The raduis of the sphere

point - The intersection point for returning

Returns:

true if there was an intersection, false if not

raySphere

public boolean raySphere(javax.vecmath.Point3d origin,
                         javax.vecmath.Vector3d direction,
                         float[] sphereCenter,
                         float sphereRadius,
                         javax.vecmath.Point3d point)

Compute the intersection point of the ray and a sphere.

Parameters:

origin - The origin of the ray

direction - The direction of the ray

sphereCenter - The coordinates of the center of the sphere

sphereRadius - The raduis of the sphere

point - The intersection point for returning

Returns:

true if there was an intersection, false if not

rayPlane

public boolean rayPlane(float[] origin,
                        float[] direction,
                        float[] plane,
                        float[] point)

Compute the intersection point of the ray and a plane. Assumes that the plane equation defines a unit normal in the coefficients a,b,c. If not, weird things happen.

Parameters:

origin - The origin of the ray

direction - The direction of the ray

plane - The coefficients for the plane equation (ax + by + cz + d = 0)

point - The intersection point for returning

Returns:

true if there was an intersection, false if not

rayPlane

public boolean rayPlane(javax.vecmath.Point3d origin,
                        javax.vecmath.Vector3d direction,
                        float[] plane,
                        javax.vecmath.Point3d point)

Compute the intersection point of the ray and a plane. Assumes that the plane equation defines a unit normal in the coefficients a,b,c. If not, weird things happen.

Parameters:

origin - The origin of the ray

direction - The direction of the ray

plane - The coefficients for the plane equation (ax + by + cz + d = 0)

point - The intersection point for returning

Returns:

true if there was an intersection, false if not

rayPolygon

public boolean rayPolygon(javax.vecmath.Point3d origin,
                          javax.vecmath.Vector3d direction,
                          float length,
                          float[] coords,
                          int numCoords,
                          javax.vecmath.Point3d point)

Test to see if the polygon intersects with the given ray. The coordinates are ordered as [Xn, Yn, Zn]. The algorithm assumes that the points are co-planar. If they are not, the results may not be accurate. The normal is calculated based on the first 3 points of the polygon. We don't do any testing for less than 3 points.

Parameters:

origin - The origin of the ray

direction - The direction of the ray

length - An optional length for to make the ray a segment. If the value is zero, it is ignored

coords - The coordinates of the polygon

numCoords - The number of coordinates to use from the array

point - The intersection point for returning

Returns:

true if there was an intersection, false if not