maspack.geometry

Class RobustPreds

java.lang.Object

maspack.geometry.RobustPreds

public class RobustPreds
extends java.lang.Object

A set of utility methods for robust intersection queries involving line segments and faces.

In general, the methods will first perform the query using regular double-precision arithmetic. If this is insufficient to yield a correct answer, the query is reevaluated using "robust" predicates involving adaptive precision arithmetic (Jonathan Shewchuck, "Adaptive precision floating-point arithmetic and fast robust geometric predicates", Discrete & Computational Geometry, 1997).

If the computation is exactly degenerate (i.e., an edge exactly intersects a triangle vertex or edge, then a whether or not an intersection occurs is determined using tie-breaking rules as described in Edelsbrunner and Peter, "Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms", ACM Transactions on Graphics, 1990, and as implemented by Aftosmis et al., "Robust and efficient Cartesian mesh generation for component-based geometry", AIAA journal, 1998. These tie-breaking rules require assigning unique indices to all primitive vertices, and making sure that these remain the same across all the calculations. In cases where all queries involve triangles and faces from two triangular meshes, we can determine such unique indices using the mesh-specific vertex indices. For the vertices on the first mesh, we use mesh indices verbatim, while for the second mesh we use the mesh indices plus the number of vertices on the first mesh.

The robust predicates used by this class are supported using a native code library.

Field Summary

Fields

Modifier and Type	Field and Description
static int	DEGENERACY_MASK
static int	E01_ON_SEGMENT triangle edge 01 is on the segment, according to exact arithmetic
static int	E12_ON_SEGMENT triangle edge 12 is on the segment, according to exact arithmetic
static int	E20_ON_SEGMENT triangle edge 20 is on the segment, according to exact arithmetic
static int	HEAD_ON_TRIANGLE head segment point is on the triangle plane, according to exact arithmetic
static int	INTERSECTS segment and triangle intersect
static int	TAIL_ON_TRIANGLE tail segment point is on the triangle plane, according to exact arithmetic
static int	TAIL_OUTSIDE tail segment point is outside the (counterclockwise) triangle, according to tie-breaking rules
static int	V0_ON_SEGMENT triangle vertex 0 is on the segment, according to exact arithmetic
static int	V1_ON_SEGMENT triangle vertex 1 is on the segment, according to exact arithmetic
static int	V2_ON_SEGMENT triangle vertex 2 is on the segment, according to exact arithmetic

Constructor Summary

Constructors

Constructor and Description
RobustPreds()

Method Summary

Modifier and Type	Method and Description
static int	closestIntersection(Face faceC, HalfEdge edge, Face faceD) Assuming that faceC and faceD both intersect edge, determines which intersection point comes irst.
static int	intersectEdgeTriangle(Point3d ipnt, HalfEdge edge, Face face, double maxlen, boolean edgeOnMesh0, boolean worldCoords) Tests for the intersection of an edge and a triangle described by a face.
static int	intersectSegmentTriangle(Point3d ipnt, int it, Vector3d pt, int ih, Vector3d ph, int i0, Vector3d p0, int i1, Vector3d p1, int i2, Vector3d p2) Tests for the intersection of a line segment and a triangle.
static int	intersectSegmentTriangle(Point3d ipnt, Point3d pt, Point3d ph, Face face, double maxlen, boolean worldCoords) Tests for the intersection of a line segment and a triangle described by a face.
static int	intersectSegmentTriangleFast(Point3d ipnt, Point3d pt, Point3d ph, Point3d p0, Point3d p1, Point3d p2, double maxlen) Tests for the intersection of a line segment and a triangle described by a face using double precision arithmetic.
static boolean	orient3d(Vertex3d v0, Vertex3d v1, Vertex3d v2, Vertex3d v3, boolean v3OnMesh0, boolean worldCoords) Returns true if v3 is "below", or "inside" the plane formed by the counterclockwise triangle v0, v1, v2.
static double	orient3dFast(Vector3d p0, Vector3d p1, Vector3d p2, Vector3d p3, double maxlen) Fast test to see if p3 is "below", or "inside" the plane formed by the counterclockwise triangle p0, p1, p2.
static void	printIntersectEdgeFace(HalfEdge edge, Face face, boolean edgeOnMesh0) For debugging - prints out arguments sent to jniIntersectSegmentTriangle().

Methods inherited from class java.lang.Object

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

Field Detail

INTERSECTS

public static final int INTERSECTS

segment and triangle intersect

See Also:

Constant Field Values

TAIL_OUTSIDE

public static final int TAIL_OUTSIDE

tail segment point is outside the (counterclockwise) triangle, according to tie-breaking rules

See Also:

Constant Field Values

TAIL_ON_TRIANGLE

public static final int TAIL_ON_TRIANGLE

tail segment point is on the triangle plane, according to exact arithmetic

See Also:

Constant Field Values

HEAD_ON_TRIANGLE

public static final int HEAD_ON_TRIANGLE

head segment point is on the triangle plane, according to exact arithmetic

See Also:

Constant Field Values

E01_ON_SEGMENT

public static final int E01_ON_SEGMENT

triangle edge 01 is on the segment, according to exact arithmetic

See Also:

Constant Field Values

E12_ON_SEGMENT

public static final int E12_ON_SEGMENT

triangle edge 12 is on the segment, according to exact arithmetic

See Also:

Constant Field Values

E20_ON_SEGMENT

public static final int E20_ON_SEGMENT

triangle edge 20 is on the segment, according to exact arithmetic

See Also:

Constant Field Values

V0_ON_SEGMENT

public static final int V0_ON_SEGMENT

triangle vertex 0 is on the segment, according to exact arithmetic

See Also:

Constant Field Values

V1_ON_SEGMENT

public static final int V1_ON_SEGMENT

triangle vertex 1 is on the segment, according to exact arithmetic

See Also:

Constant Field Values

V2_ON_SEGMENT

public static final int V2_ON_SEGMENT

triangle vertex 2 is on the segment, according to exact arithmetic

See Also:

Constant Field Values

DEGENERACY_MASK

public static final int DEGENERACY_MASK

See Also:

Constant Field Values

Constructor Detail

RobustPreds

public RobustPreds()

Method Detail

orient3d

public static boolean orient3d(Vertex3d v0,
                               Vertex3d v1,
                               Vertex3d v2,
                               Vertex3d v3,
                               boolean v3OnMesh0,
                               boolean worldCoords)

Returns true if v3 is "below", or "inside" the plane formed by the counterclockwise triangle v0, v1, v2.

The computation first performs a quick numeric calculation to see if the intersection can be determined within regular double precision tolerances. If it cannot, then a more detailed calculation is performed using robust predicates.

If tie-breaking is needed, then this is done using "Simulation of Simplicity", as described in the class header, by assigning unique indices to each vertex based on their underlying mesh indices. If the meshes are different, then if v3OnMesh0 is true, we increment the triangle vertex indices by the number of vertices on the v3 mesh, while if it is false we increment the v3 vertex index by the number of vertices on the triangle mesh.

Parameters:

v0 - first triangle vertex

v1 - second triangle vertex

v2 - third vertex

v3 - vertex to test

v3OnMesh0 - used to determine vertex indices for tie-breaking, as described above

worldCoords - if true, computes the intersection in world coordinates. Otherwise, mesh local coordinates are used.

Returns:

true if v3 is inside the triangle

printIntersectEdgeFace

public static void printIntersectEdgeFace(HalfEdge edge,
                                          Face face,
                                          boolean edgeOnMesh0)

For debugging - prints out arguments sent to jniIntersectSegmentTriangle().

closestIntersection

public static int closestIntersection(Face faceC,
                                      HalfEdge edge,
                                      Face faceD)

Assuming that faceC and faceD both intersect edge, determines which intersection point comes irst. Specifically, let c and d be the intersection of faceC and faceD with edge. Then this method returns: 1 if d is closer to the edge's tail, -1 if c is closer to the edge's tail, and 0 if they are equidistant. This method uses adaptive arithmetic to determine an exact solution.

Parameters:

faceC - first face to test

edge - edge to tect

faceD - second face to test

Returns:

1, 0, or -1 if faceD is closer, equidistant, or farther from the edge's tail

intersectEdgeTriangle

public static int intersectEdgeTriangle(Point3d ipnt,
                                        HalfEdge edge,
                                        Face face,
                                        double maxlen,
                                        boolean edgeOnMesh0,
                                        boolean worldCoords)

Tests for the intersection of an edge and a triangle described by a face. Returns an intersection and a non-zero set of flags if there is. Flags may include INTERSECTS (always set if there is an intersection), TAIL_OUTSIDE, TAIL_ON_TRIANGLE, HEAD_ON_TRIANGLE, E01_ON_SEGMENT, E12_ON_SEGMENT, and E20_ON_SEGMENT. If there is an intersection, and ipnt is non-null, then the intersection point is computed and returned in ipnt.

If maxlen > 0, the method first performs a quick numeric calculation to see if the intersection can be determined within to tolerance based on maxlen. If it cannot, then a more detailed calculation is performed using robust predicates. In order to work properly, maxlen must be >= the length of the edge and any of the face edges. If maxlen = 0, then the robust predicates are called directly.

If tie-breaking is needed, then this is done using "Simulation of Simplicity", as described in the class header, by assigning unique indices to each vertex based on their underlying mesh indices. If the meshes are different, then if edgeOnMesh0 is true, we increment the face vertex indices by the number of vertices on the edge mesh, while if it is false we increment the edge vertex indices by the number of vertices on the face mesh.

Parameters:

ipnt - if non-null and if the edge and face intersect, returns the intersection point

edge - edge to test for intersection

face - face to test for intersection

maxlen - if > 0, specifies an upper bound for the length of the edge and face edges which is used to see if the intersection can be determined using regular double precision

edgeOnMesh0 - used to determine vertex indices for tie-breaking, as described above

worldCoords - if true, computes the intersection in world coordinates. Otherwise, mesh local coordinates are used.

Returns:

code 0 if there is no intersection; flags describing the intersection if there is

intersectSegmentTriangle

public static int intersectSegmentTriangle(Point3d ipnt,
                                           Point3d pt,
                                           Point3d ph,
                                           Face face,
                                           double maxlen,
                                           boolean worldCoords)

Tests for the intersection of a line segment and a triangle described by a face. Returns 0 is there is no intersection and a non-zero set of flags if there is. Flags may include INTERSECTS (always set if there is an intersection), TAIL_OUTSIDE, TAIL_ON_TRIANGLE, HEAD_ON_TRIANGLE, E01_ON_SEGMENT, E12_ON_SEGMENT, and E20_ON_SEGMENT. If there is an intersection, and ipnt is non-null, then the intersection point is computed and returned in ipnt.

If maxlen > 0, the method first performs a quick numeric calculation to see if the intersection can be determined within to tolerance based on maxlen. If it cannot, then a more detailed calculation is performed using robust predicates. In order to work properly, maxlen must be >= the length of the segment and any of the face edges. If maxlen = 0, then the robust predicates are called directly.

If tie-breaking is needed, then this is done using "Simulation of Simplicity", as described in the class header, by assigning unique indices to each vertex based on their underlying mesh indices. Vertices for the line segment end points (pt and ph) are assigned 0 and 1, while for the face vertices indices are assigned using their underlying mesh vertices plus 2.

For tie-breaking purposes, it is assumed that the line segment is a stand-alone primitive and independent of the face mesh. If multiple queries are performed with the same line segment and different faces from the same mesh, then pt and ph should always refer to the same segment end points.

Parameters:

ipnt - if non-null and if the segment and face intersect, returns the intersection point

pt - tail point of the line segment

ph - head point of the line segment

face - face to test for intersection

maxlen - if > 0, specifies an upper bound for the length of the edge and face edges which is used to see if the intersection can be determined using regular double precision

worldCoords - if true, computes the intersection in world coordinates. Otherwise, mesh local coordinates are used.

Returns:

code 0 if there is no intersection; flags describing the intersection if there is

orient3dFast

public static double orient3dFast(Vector3d p0,
                                  Vector3d p1,
                                  Vector3d p2,
                                  Vector3d p3,
                                  double maxlen)

Fast test to see if p3 is "below", or "inside" the plane formed by the counterclockwise triangle p0, p1, p2. This is done by computing the and returning the volume of the corresponding tetrahedron. p3 is "below" if this volume is negative, and "above" if it is positive. If the volume can not be determined accurately within machine precision, the 0 is returned. To help determine this precision, the argument maxlen may be used; this should be >= the maximum length of all edges associated with the calculation. If maxlen is given as zero, then it is computed automatically from the edges of the tetrahedron.

Parameters:

p0 - first triangle point

p1 - second triangle point

p2 - third triangle point

p3 - point to test

maxlen - optional; if > 0, should be the maximum length of all edges associated with the calculation

Returns:

positive or negative if p3 is above or inside the plane, or 0 if this cannot be determined.

intersectSegmentTriangleFast

public static int intersectSegmentTriangleFast(Point3d ipnt,
                                               Point3d pt,
                                               Point3d ph,
                                               Point3d p0,
                                               Point3d p1,
                                               Point3d p2,
                                               double maxlen)

Tests for the intersection of a line segment and a triangle described by a face using double precision arithmetic. Returns -1 if this cannot be determined using double precision arithmetic. Otherise, returns 0 is there is no intersection and a non-zero set of flags if there is. Flags may include INTERSECTS (always set if there is an intersection), and TAIL_OUTSIDE if the tail of the segment is outside the triangle (in a counterclockwise sense). If there is an intersection, and ipnt is non-null, then the intersection point is computed and returned in ipnt.

Parameters:

ipnt - if non-null and if the segment and face intersect, returns the intersection point

pt - tail point of the line segment

ph - head point of the line segment

p0 - first face vertex point

p1 - second face vertex point

p2 - third face vertex point

maxlen - maximum length used to determine if the computation can be done using double precision arithmetic. Should be >= the length of the segment and any of the face edges.

Returns:

code 0 if there is no intersection; flags describing the intersection if there is

intersectSegmentTriangle

public static int intersectSegmentTriangle(Point3d ipnt,
                                           int it,
                                           Vector3d pt,
                                           int ih,
                                           Vector3d ph,
                                           int i0,
                                           Vector3d p0,
                                           int i1,
                                           Vector3d p1,
                                           int i2,
                                           Vector3d p2)

Tests for the intersection of a line segment and a triangle. Returns 0 is there is no intersection and a non-zero set of flags if there is. Flags may include INTERSECTS (always set if there is an intersection), TAIL_OUTSIDE, TAIL_ON_TRIANGLE, HEAD_ON_TRIANGLE, E01_ON_SEGMENT, E12_ON_SEGMENT, and E20_ON_SEGMENT. If there is an intersection, and ipnt is non-null, then the intersection point is computed and returned in ipnt.

The computation first performs a quick numeric calculation to see if the intersection can be determined within regular double precision tolerances. If it cannot, then a more detailed calculation is performed using robust predicates.

If tie-breaking is needed, then this is done using "Simulation of Simplicity", as described in the class header, using the indices supplied for each vertex. These should be unique to each vertex across all queries.

Parameters:

ipnt - if non-null and if the edge and triangle intersect, returns the intersection point

it - tie-breaking index for tail segment vertex

pt - position of tail segment vertex

ih - tie-breaking index for head segment vertex

ph - position of head segment vertex

i0 - tie-breaking index for first face vertex

p0 - position of first face vertex

i1 - tie-breaking index for second face vertex

p1 - position of second face vertex

i2 - tie-breaking index for third face vertex

p2 - position of third face vertex

Returns:

code 0 if there is no intersection; flags describing the intersection if there is