maspack.geometry

Class BVFeatureQuery

java.lang.Object

maspack.geometry.BVFeatureQuery

public class BVFeatureQuery
extends java.lang.Object

Worker class for nearest feature queries using bounding volume hierarchies.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	BVFeatureQuery.InsideQuery
static class	BVFeatureQuery.NearestKCollector<T> Collects the nearest K boundables, as in a k-nearest-neighbor search
static interface	BVFeatureQuery.ObjectDistanceCalculator
static interface	BVFeatureQuery.ObjectDistanceCollector Utility class for collecting objects when performing a nearest-distance search until a condition is met (e.g.
static class	BVFeatureQuery.ObjectDistanceEntry<T> Pair of { Object, Distance}, used by nearest object queries

Field Summary

Fields

Modifier and Type	Field and Description
boolean	debug
java.lang.String	lastCase
maspack.geometry.BVFeatureQuery.PointFaceDistanceCalculator	myPointFaceCalc

Constructor Summary

Constructors

Constructor and Description
BVFeatureQuery()

Method Summary

Modifier and Type	Method and Description
static double	distanceToMesh(Point3d nearPnt, PolygonalMesh mesh, Point3d pnt) Returns the nearest distance from a point to a mesh.
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, MeshBase 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.
Feature	nearestFeatureToPoint(Point3d nearPnt, BVTree featureTree, Point3d pnt) Find the nearest feature to a point
java.util.TreeSet<BVFeatureQuery.ObjectDistanceEntry<Feature>>	nearestKFeaturesToPoint(BVTree bvh, int k, Point3d pnt) Finds the K nearest features in the bounding-volume hierarchy to a point in world coordinates The resulting tree is ordered by distance (nearest to furthest).
BVNode	nearestLeafToPoint(BVTree bvh, Point3d pnt)
Boundable	nearestObject(BVTree bvh, BVFeatureQuery.ObjectDistanceCalculator dcalc)
void	nearestObjects(BVTree bvh, BVFeatureQuery.ObjectDistanceCalculator dcalc, BVFeatureQuery.ObjectDistanceCollector coll) Find and collect objects starting at the nearest and working outwards until a given criteria is met
Boundable	nearestObjectToPoint(Point3d nearPnt, BVTree bvh, BVFeatureQuery.ObjectDistanceCalculator calc) Returns the nearest Object to a point, using a specified bounding volume hierarchy.
static Point3d	nearestPointAlongRay(PolygonalMesh mesh, Point3d origin, Vector3d dir) Returns the nearest point on a polygonal mesh that intersects a given ray, or null if the ray does not intersect the mesh.
Vertex3d	nearestVertexToPoint(BVTree bvh, Point3d pnt) Returns the nearest mesh vertex to a point, using a specified bounding volume hierarchy.
Vertex3d	nearestVertexToPoint(MeshBase 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

myPointFaceCalc

public maspack.geometry.BVFeatureQuery.PointFaceDistanceCalculator myPointFaceCalc

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.

nearestFeatureToPoint

public Feature nearestFeatureToPoint(Point3d nearPnt,
                                     BVTree featureTree,
                                     Point3d pnt)

Find the nearest feature to a point

Parameters:

nearPnt - populates with location of nearest point on set of features

featureTree - bounding-volume tree containing desired features

pnt - point from which to find the nearest feature

Returns:

the nearest feature, or null

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.

distanceToMesh

public static double distanceToMesh(Point3d nearPnt,
                                    PolygonalMesh mesh,
                                    Point3d pnt)

Returns the nearest distance from a point to a mesh.

Parameters:

nearPnt - if not null, returns the nearest point on the mesh in world coordinates.

mesh - mesh to which distance should be computed.

pnt - point for which distance should be computed (world coords)

Returns:

distance to the mesh, or -1 if the point is too far away

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.

nearestPointAlongRay

public static Point3d nearestPointAlongRay(PolygonalMesh mesh,
                                           Point3d origin,
                                           Vector3d dir)

Returns the nearest point on a polygonal mesh that intersects a given ray, or null if the ray does not intersect the mesh.

Parameters:

mesh - to intersect with the ray

origin - origininating point of the ray.

dir - direction of the ray.

Returns:

nearest intersecting point, or null if no intersection

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 in 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. Hence 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. Hence 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 (in world coordinates)

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. Hence 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 (in world coordinates)

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(MeshBase 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,
                                    MeshBase 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.

nearestObjectToPoint

public Boundable nearestObjectToPoint(Point3d nearPnt,
                                      BVTree bvh,
                                      BVFeatureQuery.ObjectDistanceCalculator calc)

Returns the nearest Object to a point, using a specified bounding volume hierarchy.

Parameters:

nearPnt - if not null, returns the nearest point in the boundable

bvh - bounding volume hierarchy containing the faces.

calc - distance calculator for which nearest object should be found.

Returns:

the nearest object to the point, or null if bvh contains no objects.

nearestObject

public Boundable nearestObject(BVTree bvh,
                               BVFeatureQuery.ObjectDistanceCalculator dcalc)

nearestObjects

public void nearestObjects(BVTree bvh,
                           BVFeatureQuery.ObjectDistanceCalculator dcalc,
                           BVFeatureQuery.ObjectDistanceCollector coll)

Find and collect objects starting at the nearest and working outwards until a given criteria is met

Parameters:

bvh - bounding object hierarchy

dcalc - distance calculator

coll - distance condition

nearestKFeaturesToPoint

public java.util.TreeSet<BVFeatureQuery.ObjectDistanceEntry<Feature>> nearestKFeaturesToPoint(BVTree bvh,
                                                                                              int k,
                                                                                              Point3d pnt)

Finds the K nearest features in the bounding-volume hierarchy to a point in world coordinates The resulting tree is ordered by distance (nearest to furthest). There may be fewer than K entries if the bounding tree contains fewer than K elements, and there may be more than K entries if the last size()-k+1 elements all have exactly the same distance

Parameters:

bvh - bounding volume hierarchy

k - number of elements to return

pnt - point (world-coordinates)

Returns:

set of nearest features

nearestLeafToPoint

public BVNode nearestLeafToPoint(BVTree bvh,
                                 Point3d pnt)