maspack.geometry
Class BVTree

java.lang.Object
  extended by maspack.geometry.BVTree
All Implemented Interfaces:
GLRenderable
Direct Known Subclasses:
AABBTree, OBBTree

public abstract class BVTree
extends java.lang.Object
implements GLRenderable

Base class for a bounding volume tree composed of a hierarchy of bounding volumes.

Author:
lloyd

Field Summary
 
Fields inherited from interface maspack.render.GLRenderable
TRANSLUCENT, TWO_DIMENSIONAL
 
Constructor Summary
BVTree()
           
 
Method Summary
abstract  void build(Boundable[] elems, int num)
          Builds a bounding volume tree for a set of elements.
 void build(java.util.Collection<? extends Boundable> elist)
          Builds a bounding volume tree for a set of elements.
 void build(MeshBase mesh)
          Builds a bounding volume tree for a mesh.
 RigidTransform3d getBvhToWorld()
          Returns the transform that converts points from the local coordinates of this tree to world coordinates.
 void getBvhToWorld(RigidTransform3d X)
          Returns the transform that converts points from the local coordinates of this tree to world coordinates.
 void getCenter(Vector3d center)
          Returns a center point for this bounding volume hierarchy.
 java.util.ArrayList<BVNode> getLeafNodes()
          Returns all the leaf nodes in this tree.
 double getMargin()
          Returns the extra distance margin by which bounding volumes in this tree should surround their elements.
 int getMaxLeafElements()
          Returns the maximum number of elements that may be contained in a leaf node.
 double getRadius()
          Returns an approximate "radius" for this bounding volume hierarchy.
 int getRenderHints()
          Returns a bit code giving rendering hints about this renderable.
abstract  BVNode getRoot()
          Returns the root bounding volume for this tree
 void intersectLine(java.util.ArrayList<BVNode> nodes, Point3d origin, Vector3d dir, double min, double max)
          Returns a list of all leaf nodes in this tree which intersect a line.
 void intersectLineSegment(java.util.ArrayList<BVNode> nodes, Point3d p1, Point3d p2)
          Returns a list of all leaf nodes in this tree which intersect a line segment.
 void intersectPlane(java.util.ArrayList<BVNode> nodes, Plane plane)
          Returns a list of all leaf nodes in this tree which intersect a plane.
 void intersectPoint(java.util.ArrayList<BVNode> nodes, Point3d pnt)
          Returns a list of all leaf nodes in this tree which contain a specified point.
 void intersectSphere(java.util.ArrayList<BVNode> nodes, Point3d center, double r)
          Returns a list of all leaf nodes in this tree which intersect a sphere.
 void intersectTree(java.util.ArrayList<BVNode> nodes1, java.util.ArrayList<BVNode> nodes2, BVTree bvt)
          Returns all intersecting pairs of leaf nodes between this tree and another tree.
 void intersectTree(java.util.ArrayList<BVNode> nodes1, java.util.ArrayList<BVNode> nodes2, BVTree bvt, RigidTransform3d X21)
          Returns all intersecting pairs of leaf nodes between this tree and another tree.
 int numberNodes()
          Numbers all nodes in this tree in depth-first order and returns the total number of nodes.
 int numNodes()
          Returns the number of nodes in this tree.
 void prerender(RenderList list)
          Prepare for rendering, and potentially add itself to a list to be drawn by a GLRenderer.
 void print()
           
 void print(java.io.PrintWriter pw)
           
 void printElement(java.io.PrintWriter pw, Boundable src)
           
 void printNumLeafFaces(java.lang.String msg)
           
 void render(GLRenderer renderer, int flags)
          Render this object using Open GL via the JOGL.
 void setBvhToWorld(RigidTransform3d X)
          Sets the transform that converts points from the local coordinates of this tree to world coordinates.
 void setMargin(double margin)
          Sets the extra distance margin by which bounding volumes in this tree should surround their elements.
 void setMaxLeafElements(int max)
          Sets the maximum number of elements that may be contained in a leaf node.
abstract  void update()
          Updates the bounding volumes in this tree to ensure that they properly contain their enclosed elements.
 void updateBounds(Point3d min, Point3d max)
          Update the minimum and maximum points for this object.
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

BVTree

public BVTree()
Method Detail

getRadius

public double getRadius()
Returns an approximate "radius" for this bounding volume hierarchy. This is just the radius of the root bounding volume.

Returns:
approximate radius of this bounding volume hierarchy.

getCenter

public void getCenter(Vector3d center)
Returns a center point for this bounding volume hierarchy. This is just the center of the root bounding volume, transformed into world coordinates.

Parameters:
center - returns the center of this bounding volume hierarchy.

getBvhToWorld

public RigidTransform3d getBvhToWorld()
Returns the transform that converts points from the local coordinates of this tree to world coordinates.

Returns:
transform from tree to world coordinates. Should not be modified.
See Also:
setBvhToWorld(maspack.matrix.RigidTransform3d)

setBvhToWorld

public void setBvhToWorld(RigidTransform3d X)
Sets the transform that converts points from the local coordinates of this tree to world coordinates. If the tree is associated with a mesh, then this transform should generally be set to the same value as that returned by MeshBase.getMeshToWorld(maspack.matrix.RigidTransform3d).

Parameters:
X - new transform value
See Also:
getBvhToWorld()

getBvhToWorld

public void getBvhToWorld(RigidTransform3d X)
Returns the transform that converts points from the local coordinates of this tree to world coordinates.

Parameters:
X - returns the transform for this tree
See Also:
setBvhToWorld(maspack.matrix.RigidTransform3d)

getRoot

public abstract BVNode getRoot()
Returns the root bounding volume for this tree

Returns:
root bounding volume

getMaxLeafElements

public int getMaxLeafElements()
Returns the maximum number of elements that may be contained in a leaf node.

Returns:
maximum number of leaf elements
See Also:
setMaxLeafElements(int)

setMaxLeafElements

public void setMaxLeafElements(int max)
Sets the maximum number of elements that may be contained in a leaf node. Setting this value will only be effective for subsequent build calls.

Parameters:
max - maximum number of leaf elements
See Also:
getMaxLeafElements()

setMargin

public void setMargin(double margin)
Sets the extra distance margin by which bounding volumes in this tree should surround their elements. This means that all elements within the tree should be at least a distance margin away from the boundaries of their containing volumes. Setting this value will only be effective for subsequent build calls or update() calls.

The purpose of a margin is mainly to overcome numercial errors in determining containment.

Parameters:
margin -
See Also:
getMargin(), update()

getMargin

public double getMargin()
Returns the extra distance margin by which bounding volumes in this tree should surround their elements.

Returns:
extra distance margin
See Also:
setMargin(double)

build

public void build(java.util.Collection<? extends Boundable> elist)
Builds a bounding volume tree for a set of elements.

Parameters:
elist - elements around which this tree is to be built.

build

public abstract void build(Boundable[] elems,
                           int num)
Builds a bounding volume tree for a set of elements.

Parameters:
elems - elements around which this tree is to be built.
num - number of elements

build

public void build(MeshBase mesh)
Builds a bounding volume tree for a mesh. The element types used to build the mesh are the same as those returned by getElementsForMesh(maspack.geometry.MeshBase).

Parameters:
mesh - mesh for which the tree should be built

intersectPoint

public void intersectPoint(java.util.ArrayList<BVNode> nodes,
                           Point3d pnt)
Returns a list of all leaf nodes in this tree which contain a specified point.

Parameters:
nodes - returns all leaf nodes containing the point
pnt - point to test for (world coordinates)

intersectSphere

public void intersectSphere(java.util.ArrayList<BVNode> nodes,
                            Point3d center,
                            double r)
Returns a list of all leaf nodes in this tree which intersect a sphere.

Parameters:
nodes - returns all leaf nodes intersecting the sphere
center - center of the sphere (world coordinates)
r - sphere radius

intersectPlane

public void intersectPlane(java.util.ArrayList<BVNode> nodes,
                           Plane plane)
Returns a list of all leaf nodes in this tree which intersect a plane.

Parameters:
nodes - returns all leaf nodes intersecting the plane
plane - plane to intersect with (world coordinates)

intersectLine

public void intersectLine(java.util.ArrayList<BVNode> nodes,
                          Point3d origin,
                          Vector3d dir,
                          double min,
                          double max)
Returns a list of all leaf nodes in this tree which intersect a line. The line is described by a point and a direction, such that points x along the line can be described by a parameter s according to
 x = origin + s dir
 
The line can be given finite bounds by specifying maximum and minimum bounds for s.

Parameters:
nodes - returns all leaf nodes intersecting the line
origin - originating point for the line (world coordinates)
dir - direction of the line (world coordinates)
min - minimum s value for the line, or -infinity if there is no minimum value
max - maximum s value for the line, or +infinity if there is no maximum value

intersectTree

public void intersectTree(java.util.ArrayList<BVNode> nodes1,
                          java.util.ArrayList<BVNode> nodes2,
                          BVTree bvt)
Returns all intersecting pairs of leaf nodes between this tree and another tree. The pairs are returned in two arrays of equal length. The relative coordinates frames of each tree (as specified by getBvhToWorld()) are taken into account when computing this intersection.

Parameters:
nodes1 - intersecting leaf nodes from this tree
nodes2 - intersecting leaf nodes from the other tree
bvt - other tree to intersect with

numberNodes

public int numberNodes()
Numbers all nodes in this tree in depth-first order and returns the total number of nodes.

Returns:
number of nodes in the tree

intersectTree

public void intersectTree(java.util.ArrayList<BVNode> nodes1,
                          java.util.ArrayList<BVNode> nodes2,
                          BVTree bvt,
                          RigidTransform3d X21)
Returns all intersecting pairs of leaf nodes between this tree and another tree. The pairs are returned in two arrays of equal length. The relative coordinate transformation between the two tree is specified explicity and not based on the values returned by getBvhToWorld().

Parameters:
nodes1 - intersecting leaf nodes from this tree
nodes2 - intersecting leaf nodes from the other tree
bvt - other tree to intersect with
X21 - transform from the coordinate frame of the other tree to that of this tree.

intersectLineSegment

public void intersectLineSegment(java.util.ArrayList<BVNode> nodes,
                                 Point3d p1,
                                 Point3d p2)
Returns a list of all leaf nodes in this tree which intersect a line segment.

Parameters:
p1 - first segment end point
p2 - second segment end point
nodes - returns all leaf nodes intersecting the line segment

update

public abstract void update()
Updates the bounding volumes in this tree to ensure that they properly contain their enclosed elements. This should be called when the positions of the elements changes (such when the vertices of mesh change position).

See Also:
setMargin(double)

getRenderHints

public int getRenderHints()
Returns a bit code giving rendering hints about this renderable. Current bit codes include TRANSLUCENT.

Specified by:
getRenderHints in interface GLRenderable
Returns:
bit code of rendering hints.

updateBounds

public void updateBounds(Point3d min,
                         Point3d max)
Update the minimum and maximum points for this object. In an x-y-z coordinate system with x directed to the right and y directed upwards, the minimum and maximum points can be thought of as defining the left-lower-far and right-upper-near corners of a bounding cube. This method should only reduce the elements of the minimum point and increase the elements of the maximum point, since it may be used as part of an iteration to determine the bounding cube for several different objects.

Specified by:
updateBounds in interface GLRenderable
Parameters:
min - minimum point
max - maximum point

prerender

public void prerender(RenderList list)
Prepare for rendering, and potentially add itself to a list to be drawn by a GLRenderer.

Specified by:
prerender in interface GLRenderable

render

public void render(GLRenderer renderer,
                   int flags)
Render this object using Open GL via the JOGL.

Specified by:
render in interface GLRenderable
Parameters:
renderer - renderer object which is used to perform the rendering. Provides pointers to GL and GLU, along with helper functions.
flags - supplies flags that may be used to control different aspects of the rendering. Flags are defined in GLRenderer and currently include GLRenderer.SELECTED, GLRenderer.VERTEX_COLORING, GLRenderer.HSV_COLOR_INTERPOLATION, GLRenderer.SORT_FACES, and GLRenderer.CLEAR_MESH_DISPLAY_LISTS.

print

public void print()

print

public void print(java.io.PrintWriter pw)

printElement

public void printElement(java.io.PrintWriter pw,
                         Boundable src)

getLeafNodes

public java.util.ArrayList<BVNode> getLeafNodes()
Returns all the leaf nodes in this tree.

Returns:
all leaf nodes

numNodes

public int numNodes()
Returns the number of nodes in this tree.

Returns:
number of nodes in the tree

printNumLeafFaces

public void printNumLeafFaces(java.lang.String msg)