maspack.geometry
Class BVFeatureQuery

java.lang.Object
  extended by maspack.geometry.BVFeatureQuery

public class BVFeatureQuery
extends java.lang.Object

Worker class for nearest feature queries using bounding volume hierarchies.


Nested Class Summary
static class BVFeatureQuery.InsideQuery
           
 
Field Summary
 boolean debug
           
 java.lang.String lastCase
           
 
Constructor Summary
BVFeatureQuery()
           
 
Method Summary
 Face getFaceForInsideOrientedTest(Point3d nearLoc, Vector2d uv)
          If called immediately after either isInsideOrientedMesh(PolygonalMesh,Point3d,double) or isInsideOrientedMesh(BVTree,Point3d,double), returns the nearest face that was used to resolve whether or not the query point is actually inside the mesh.
 int getMaxRayCasts()
          Returns the maximum number of ray casts that will be attempted by isInsideMesh(maspack.geometry.PolygonalMesh, maspack.matrix.Point3d).
static Face getNearestFaceToPoint(Point3d nearPnt, Vector2d uv, PolygonalMesh mesh, Point3d pnt)
          Returns the nearest triangular mesh face to a point.
 BVFeatureQuery.InsideQuery isInsideMesh(PolygonalMesh mesh, BVTree bvh, Point3d pnt, double tol)
          Determines if a point is on or inside a closed triangular mesh, the faces of which are contained within a specified bounding volume hierarchy.
static BVFeatureQuery.InsideQuery isInsideMesh(PolygonalMesh mesh, Point3d pnt)
          Determines if a point is on or inside a closed triangular mesh.
 BVFeatureQuery.InsideQuery isInsideMesh(PolygonalMesh mesh, Point3d pnt, double tol)
          Determines if a point is on or inside a closed triangular mesh.
 boolean isInsideOrientedMesh(BVTree bvh, Point3d pnt, double tol)
          Returns true if a point is on or inside an oriented triangular mesh, the faces of which are contained within a specified bounding volume hierarchy.
static boolean isInsideOrientedMesh(PolygonalMesh mesh, Point3d pnt)
          Returns true if a point is on or inside an oriented triangular mesh.
 boolean isInsideOrientedMesh(PolygonalMesh mesh, Point3d pnt, double tol)
          Returns true if a point is on or inside an oriented triangular mesh.
 BVFeatureQuery.InsideQuery isInsideOrOnMesh(PolygonalMesh mesh, BVTree bvh, Point3d pnt, double tol)
           
 Boundable nearestEdgeToPoint(Point3d nearPnt, DoubleHolder sval, BVTree bvh, Point3d pnt)
          Returns the nearest edge to a point, using a specified bounding volume hierarchy.
 Boundable nearestEdgeToPoint(Point3d nearPnt, DoubleHolder sval, PolygonalMesh mesh, Point3d pnt)
          Returns the nearest mesh edge to a point.
 Face nearestFaceAlongLine(Point3d nearPnt, Vector3d duv, BVTree bvh, Point3d origin, Vector3d dir, double min, double max)
          Returns the nearest triangular face to a point along a line, using a specified bounding volume hierarchy.
 Face nearestFaceAlongLine(Point3d nearPnt, Vector3d duv, PolygonalMesh mesh, Point3d origin, Vector3d dir, double min, double max)
          Returns the nearest triangular mesh face to a point along a line.
 Face nearestFaceAlongRay(Point3d nearPnt, Vector3d duv, BVTree bvh, Point3d origin, Vector3d dir)
          Returns the nearest triangular face along a directed ray, using a specified bounding volume hierarchy.
 Face nearestFaceAlongRay(Point3d nearPnt, Vector3d duv, PolygonalMesh mesh, Point3d origin, Vector3d dir)
          Returns the nearest triangular mesh face along a directed ray.
 Face nearestFaceToPoint(Point3d nearPnt, Vector2d uv, BVTree bvh, Point3d pnt)
          Returns the nearest triangular face to a point, using a specified bounding volume hierarchy.
 Face nearestFaceToPoint(Point3d nearPnt, Vector2d uv, PolygonalMesh mesh, Point3d pnt)
          Returns the nearest triangular mesh face to a point.
 Vertex3d nearestVertexToPoint(BVTree bvh, Point3d pnt)
          Returns the nearest mesh vertex to a point, using a specified bounding volume hierarchy.
 Vertex3d nearestVertexToPoint(PolygonalMesh mesh, Point3d pnt)
          Returns the nearest mesh vertex to a point.
 void setMaxRayCasts(int maxrc)
          Sets the maximum number of ray casts that will be attempted by isInsideMesh(maspack.geometry.PolygonalMesh, maspack.matrix.Point3d).
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

debug

public boolean debug

lastCase

public java.lang.String lastCase
Constructor Detail

BVFeatureQuery

public BVFeatureQuery()
Method Detail

nearestFaceToPoint

public Face nearestFaceToPoint(Point3d nearPnt,
                               Vector2d uv,
                               PolygonalMesh mesh,
                               Point3d pnt)
Returns the nearest triangular mesh face to a point. This method uses the default bounding volume hierarchy produced by the mesh.

Parameters:
nearPnt - if not null, returns the nearest point on the face in world coordinates.
uv - if not null, returns the UV coordinates of the nearest face point. These are the barycentric coordinates with respect to the second and third vertices.
mesh - mesh containing the faces.
pnt - point for which the nearest face should be found.
Returns:
the nearest face to the point, or null if the mesh contains no faces.

nearestFaceToPoint

public Face nearestFaceToPoint(Point3d nearPnt,
                               Vector2d uv,
                               BVTree bvh,
                               Point3d pnt)
Returns the nearest triangular face to a point, using a specified bounding volume hierarchy. The faces contained within the hierarchy are all assumed to be triangular.

Parameters:
nearPnt - if not null, returns the nearest point on the face in world coordinates.
uv - if not null, returns the UV coordinates of the nearest face point. These are the barycentric coordinates with respect to the second and third vertices.
bvh - bounding volume hierarchy containing the faces.
pnt - point for which the nearest face should be found.
Returns:
the nearest face to the point, or null if bvh contains no faces.

getNearestFaceToPoint

public static Face getNearestFaceToPoint(Point3d nearPnt,
                                         Vector2d uv,
                                         PolygonalMesh mesh,
                                         Point3d pnt)
Returns the nearest triangular mesh face to a point. This method uses the default bounding volume hierarchy produced by the mesh.

Parameters:
nearPnt - if not null, returns the nearest point on the face in world coordinates.
uv - if not null, returns the UV coordinates of the nearest face point. These are the barycentric coordinates with respect to the second and third vertices.
mesh - mesh containing the faces.
pnt - point for which the nearest face should be found.
Returns:
the nearest face to the point, or null if the mesh contains no faces.

nearestFaceAlongRay

public Face nearestFaceAlongRay(Point3d nearPnt,
                                Vector3d duv,
                                PolygonalMesh mesh,
                                Point3d origin,
                                Vector3d dir)
Returns the nearest triangular mesh face along a directed ray. This method uses the default bounding volume hierarchy produced by the mesh. Faces in the negative ray direction are ignored. If no face is found, the results returned int nearPnt and duv are undefined.

Parameters:
nearPnt - if not null, returns the nearest point on the face in world coordinates.
duv - if not null, returns the distance of the point to the face (in x) and the UV coordinates of the nearest face point (in y and z). The UV coordinates are the barycentric coordinates with respect to the second and third vertices.
mesh - mesh containing the faces.
origin - originating point of the ray.
dir - direction of the ray. If not normalized, the distance returned in duv will be scaled by the inverse of the length of dir.
Returns:
the nearest face along the ray, or null is no face is found.

nearestFaceAlongRay

public Face nearestFaceAlongRay(Point3d nearPnt,
                                Vector3d duv,
                                BVTree bvh,
                                Point3d origin,
                                Vector3d dir)
Returns the nearest triangular face along a directed ray, using a specified bounding volume hierarchy. The faces contained within the hierarchy are all assumed to be triangular. Faces in the negative ray direction are ignored. If no face is found, the results returned int nearPnt and duv are undefined.

Parameters:
nearPnt - if not null, returns the nearest point on the face in world coordinates.
duv - if not null, returns the distance of the point to the face (in x) and the UV coordinates of the nearest face point (in y and z). The UV coordinates are the barycentric coordinates with respect to the second and third vertices.
bvh - bounding volume hierarchy containing the faces.
origin - origininating point of the ray.
dir - direction of the ray. If not normalized, the distance returned in duv will be scaled by the inverse of the length of dir.
Returns:
the nearest face along the ray, or null is no face is found.

nearestFaceAlongLine

public Face nearestFaceAlongLine(Point3d nearPnt,
                                 Vector3d duv,
                                 PolygonalMesh mesh,
                                 Point3d origin,
                                 Vector3d dir,
                                 double min,
                                 double max)
Returns the nearest triangular mesh face to a point along a line. This method uses the default bounding volume hierarchy produced by the mesh. If no face is found, the results returned int nearPnt and duv are undefined. The search can be restricted to a line segment by restricting min and max to finite values. Setting them to negative and positive infinity causes the entire line to be searched.

Parameters:
nearPnt - if not null, returns the nearest point on the face in world coordinates.
duv - if not null, returns the distance of the point to the face (in x) and the UV coordinates of the nearest face point (in y and z). The UV coordinates are the barycentric coordinates with respect to the second and third vertices.
mesh - mesh containing the faces
origin - originating point of the line
dir - direction of the line. If not normalized, the distance returned in duv will be scaled by the inverse of the length of dir.
min - minimum allowed distance along the line from origin.
max - maximum allowed distance along the line from origin.
Returns:
the nearest face along the ray, or null is no face is found.

nearestFaceAlongLine

public Face nearestFaceAlongLine(Point3d nearPnt,
                                 Vector3d duv,
                                 BVTree bvh,
                                 Point3d origin,
                                 Vector3d dir,
                                 double min,
                                 double max)
Returns the nearest triangular face to a point along a line, using a specified bounding volume hierarchy. The faces contained within the hierarchy are all assumed to be triangular. If no face is found, the results returned int nearPnt and duv are undefined. The search can be restricted to a line segment by restricting min and max to finite values. Setting them to negative and positive infinity causes the entire line to be searched.

Parameters:
nearPnt - if not null, returns the nearest point on the face in world coordinates.
duv - if not null, returns the distance of the point to the face (in x) and the UV coordinates of the nearest face point (in y and z). The UV coordinates are the barycentric coordinates with respect to the second and third vertices.
bvh - bounding volume hierarchy containing the faces.
origin - originating point of the line
dir - direction of the line. If not normalized, the distance returned in duv will be scaled by the inverse of the length of dir.
min - minimum allowed distance along the line from origin.
max - maximum allowed distance along the line from origin.
Returns:
the nearest face along the ray, or null is no face is found.

isInsideOrientedMesh

public static boolean isInsideOrientedMesh(PolygonalMesh mesh,
                                           Point3d pnt)
Returns true if a point is on or inside an oriented triangular mesh. "Oriented" means that all face normals are assumed to point outwards. Whether or not the point is on the mesh is determined using a numerical tolerance computed from the meshes overall dimensions.

The method works by inspecting the nearest face, edge or vertex to the point. Hance the mesh does not need to be closed, and the method is faster, though possibly less numerically robust, than isInsideMesh(PolygonalMesh,Point3d), which uses ray casting.

Parameters:
mesh - mesh which point may be inside.
pnt - point to check.
Returns:
true if pnt is on or inside the mesh.

isInsideOrientedMesh

public boolean isInsideOrientedMesh(PolygonalMesh mesh,
                                    Point3d pnt,
                                    double tol)
Returns true if a point is on or inside an oriented triangular mesh. "Oriented" means that all face normals are assumed to point outwards. The method works by inspecting the nearest face, edge or vertex to the point.

The method works by inspecting the nearest face, edge or vertex to the point. Hance the mesh does not need to be closed, and the method is faster, though possibly less numerically robust, than isInsideMesh(PolygonalMesh,Point3d,double), which uses ray casting.

Parameters:
mesh - mesh which point may be inside.
pnt - point to check.
tol - tolerance within which the point is considered to be on the mesh surfaces. A value of -1 will cause the tolerance to be computed automatically.
Returns:
true if pnt is on or inside the mesh.

isInsideOrientedMesh

public boolean isInsideOrientedMesh(BVTree bvh,
                                    Point3d pnt,
                                    double tol)
Returns true if a point is on or inside an oriented triangular mesh, the faces of which are contained within a specified bounding volume hierarchy. "Oriented" means that all face normals are assumed to point outwards. The method works by inspecting the nearest face, edge or vertex to the point.

The method works by inspecting the nearest face, edge or vertex to the point. Hance the mesh does not need to be closed, and the method is faster, though possibly less numerically robust, than isInsideMesh(PolygonalMesh,BVTree,Point3d,double), which uses ray casting.

Parameters:
bvh - bounding volume hierarchy containing the faces.
pnt - point to check.
tol - tolerance within which the point is considered to be on the mesh surface. A value of -1 will cause the tolerance to be computed automatically.
Returns:
true if pnt is on or inside the mesh.

getFaceForInsideOrientedTest

public Face getFaceForInsideOrientedTest(Point3d nearLoc,
                                         Vector2d uv)
If called immediately after either isInsideOrientedMesh(PolygonalMesh,Point3d,double) or isInsideOrientedMesh(BVTree,Point3d,double), returns the nearest face that was used to resolve whether or not the query point is actually inside the mesh. If the point is outside the mesh's bounding tree, then no nearest face will have been computed and this method will return null.

Parameters:
nearLoc - if not null, and if the returned face is not null, returns the nearest point (to the query point) on the face in mesh local coordinates.
uv - if not null, and if the returned face is not null, returns the UV coordinates of the nearest point on the face. These are the barycentric coordinates with respect to the second and third vertices.
Returns:
the nearest face, if any, used to resolve whether the query point is actually inside the mesh.

getMaxRayCasts

public int getMaxRayCasts()
Returns the maximum number of ray casts that will be attempted by isInsideMesh(maspack.geometry.PolygonalMesh, maspack.matrix.Point3d).

Returns:
maximum number of ray casts

setMaxRayCasts

public void setMaxRayCasts(int maxrc)
Sets the maximum number of ray casts that will be attempted by isInsideMesh(maspack.geometry.PolygonalMesh, maspack.matrix.Point3d).

Parameters:
maxrc - maximum number of ray casts

isInsideMesh

public static BVFeatureQuery.InsideQuery isInsideMesh(PolygonalMesh mesh,
                                                      Point3d pnt)
Determines if a point is on or inside a closed triangular mesh. The mesh normals are assumed to be pointing outwards. The method works by counting the number of times a random ray cast from the point intersects the mesh. Degeneracies are detected and result in another ray being cast. Whether or not the point is on the mesh is determined using a numerical tolerance computed from the mesh's overall dimensions.

The maximum number of ray casts can be controlled by the methods getMaxRayCasts() and setMaxRayCasts(int). If the number of ray casts exceeds this total the method returns InsideQuery.UNSURE.

Parameters:
mesh - mesh which point may be inside.
pnt - point to check.
Returns:
InsideQuery.INSIDE if pnt is inside, InsideQuery.ON if on, InsideQuery.OUTSIDE if it is outside, and InsideQuery.UNSURE if the method did not converge.

isInsideMesh

public BVFeatureQuery.InsideQuery isInsideMesh(PolygonalMesh mesh,
                                               Point3d pnt,
                                               double tol)
Determines if a point is on or inside a closed triangular mesh. The mesh normals are assumed to be pointing outwards. The method works by counting the number of times a random ray cast from the point intersects the mesh. Degeneracies are detected and result in another ray being cast.

The maximum number of ray casts can be controlled by the methods getMaxRayCasts() and setMaxRayCasts(int). If the number of ray casts exceeds this total the method returns InsideQuery.UNSURE.

Parameters:
mesh - mesh which point may be inside.
pnt - point to check.
tol - tolerance within which the point is considered to be on the mesh surface. A value of -1 will cause the tolerance to be computed automatically.
Returns:
InsideQuery.INSIDE if pnt is inside, InsideQuery.ON if on, InsideQuery.OUTSIDE if it is outside, and InsideQuery.UNSURE if the method did not converge.

isInsideMesh

public BVFeatureQuery.InsideQuery isInsideMesh(PolygonalMesh mesh,
                                               BVTree bvh,
                                               Point3d pnt,
                                               double tol)
Determines if a point is on or inside a closed triangular mesh, the faces of which are contained within a specified bounding volume hierarchy. The method works by counting the number of times a random ray cast from the point intersects the mesh. Degeneracies are detected and result in another ray being cast.

The maximum number of ray casts can be controlled by the methods getMaxRayCasts() and setMaxRayCasts(int). If the number of ray casts exceeds this total the method returns InsideQuery.UNSURE.

Parameters:
mesh - mesh which point may be inside.
bvh - bounding volume hierarchy containing the mesh.
pnt - point to check.
tol - tolerance within which the point is considered to be on the mesh surface. A value of -1 will cause the tolerance to be computed automatically.
Returns:
InsideQuery.INSIDE if pnt is inside or on, InsideQuery.OUTSIDE if it is outside, and InsideQuery.UNSURE if the method did not converge.

isInsideOrOnMesh

public BVFeatureQuery.InsideQuery isInsideOrOnMesh(PolygonalMesh mesh,
                                                   BVTree bvh,
                                                   Point3d pnt,
                                                   double tol)

nearestVertexToPoint

public Vertex3d nearestVertexToPoint(PolygonalMesh mesh,
                                     Point3d pnt)
Returns the nearest mesh vertex to a point. This method uses the default bounding volume hierarchy produced by the mesh.

Parameters:
mesh - mesh containing the vertices.
pnt - point for which the nearest vertex should be found.
Returns:
the nearest vertex to the point, or null if the mesh contains no vertices.

nearestVertexToPoint

public Vertex3d nearestVertexToPoint(BVTree bvh,
                                     Point3d pnt)
Returns the nearest mesh vertex to a point, using a specified bounding volume hierarchy.

Parameters:
bvh - bounding volume hierarchy containing the vertices.
pnt - point for which the nearest vertex should be found.
Returns:
the nearest vertex to the point, or null if bvh contains no vertices.

nearestEdgeToPoint

public Boundable nearestEdgeToPoint(Point3d nearPnt,
                                    DoubleHolder sval,
                                    PolygonalMesh mesh,
                                    Point3d pnt)
Returns the nearest mesh edge to a point. This method uses the default bounding volume hierarchy produced by the mesh. An edge may be either a HalfEdge or a LineSegment. The former are found in PolygonalMeshes, while the latter are found the bounding volume hierarchies produced for PolylineMeshes.

Parameters:
nearPnt - if not null, returns the nearest point on the edge.
sval - if not null, returns a coordinate in the range [0,1] giving the location of the nearest point along the edge.
mesh - mesh containing the edges.
pnt - point for which the nearest edge should be found.
Returns:
the nearest edge to the point, or null if the mesh contains no edges.

nearestEdgeToPoint

public Boundable nearestEdgeToPoint(Point3d nearPnt,
                                    DoubleHolder sval,
                                    BVTree bvh,
                                    Point3d pnt)
Returns the nearest edge to a point, using a specified bounding volume hierarchy. An edge may be either a HalfEdge or a LineSegment. The former are found in PolygonalMeshes, while the latter are found the bounding volume hierarchies produced for PolylineMeshes.

Parameters:
nearPnt - if not null, returns the nearest point on the edge.
sval - if not null, returns a coordinate in the range [0,1] giving the location of the nearest point along the edge.
bvh - bounding volume hierarchy containing the faces.
pnt - point for which the nearest edge should be found.
Returns:
the nearest edge to the point, or null if bvh contains no edges.