

PREV PACKAGE NEXT PACKAGE  FRAMES NO FRAMES 
See:
Description
Class Summary  
ClosestFeaturesHT  Implements a hash table for use by
vclip to store the
most recent closest features between pairs of PolyTrees. 
ClosestPointPair  Describes a pair of closest points and features between two polyhedra or polytrees. 
ConvexPolygon  A 2d convex polygon used by Vclip is handling faceface contact. 
ConvexPolyhedron  A convex polyhedron. 
DistanceReport  Used by vclip to return distance information. 
Edge  An edge of a polyhedron. 
Face  A face of a polyhedron. 
Feature  Base class for the features of a polyhedron. 
FeaturePair  Represents a pair of features. 
Plane  A plane in space. 
PolyTree  A hierarchically organized collection of
convex polyhedra and the primary class for
invoking vclip . 
VclipTest  Test class for the vclip package. 
Vertex  A vertex of a polyhedron. 
Vclip is a package for computing distances and checking for collisions between polyhedra. It also computes the closest points and features between polyhedra, which is particularly useful for calculations involving contact dynamics.
The original version of Vclip was written in C++ by Brian Mirtich at MERL, and is based on his algorithm described in ``VClip: Fast and Robust Polyhedral Collision Detection'', ACM Transactions on Graphics, July, 1997. The Java port was done by John E. Lloyd and Eddy Boxerman at the UBC Computer Science Department. The copyright is held by MERL.
This implementation of Vclip uses the javax.vecmath package. A jar file of this package, along with documentation, is included in the distribution, and you can also view the vecmath documentation online. Vclip also uses the package convexhull3d, written by John Lloyd, for computing 3D convex hulls.
The basic Vclip computation involves calculating the distance between
PolyTrees
, which are hierarchical collections of
convex polyhedra. A PolyTree is either atomic or compound.
An atomic PolyTree consists of a single convex polyhedron, while
a compound PolyTree consists of several subPolyTrees.
VclipExample.java
)
which computes the distance between two PolyTrees
as they are moved closer together until they collide:
HashMap library = new HashMap(); PolyTree.scanLibrary ("PolyTreeExamples.txt", library, true); PolyTree ptree1 = (PolyTree)library.get("unitcube"); PolyTree ptree2 = (PolyTree)library.get("cone"); DistanceReport rep = new DistanceReport(); ClosestFeatureHT ht = new ClosestFeatureHT(); Matrix4d X21 = new Matrix4d(); for (double x=10; x>=0; x=1) { X21.set (new Vector3d (x, 0, 0)); // set translation double dist = ptree1.vclip (rep, ptree2, X21, 0, ht); if (dist > 0) { System.out.println (dist); } else { System.out.println ("colliding"); break; } }The PolyTrees themselves are defined and named in a text file called
PolyTreeExamples.txt
. The
method
PolyTree.scanLibrary
reads this file
and places all the defined PolyTrees into a library (which is
just a Map
of names onto PolyTrees).
Individual PolyTrees can be obtained from the library
using the Map's get
method.
The example computes the distance between the PolyTrees as they
are moved closer together along the x axis. The distance
itself is returned by the PolyTree method
vclip
,
which takes the following arguments:
DistanceReport
,
used to return the closest point and feature information;
Matrix4d
defining the spatial displacement between the
two PolyTrees (specifically, the transformation from the
reference frame of the second PolyTree into the reference frame of the
first);
vclip
exceeds this limit,
then the actual distance between the PolyTrees may in fact
be larger. This allows vclip
to save computational effort for PolyTrees that are farther apart.
A negative limit value disables this feature.
ClosestFeaturesHT
, which stores
the most recently computed closest features between pairs of
PolyTrees, thus improving the efficiency of the
subsequent vclip
computations. An application can create
a single ClosestFeaturesHT and use this in all
calls to vclip
.
DistanceReport
.
Actual point and feature information is
contained in a ClosestPointPair
,
obtained using the
getClosestPair
method:
DistanceReport rep = new DistanceReport(); ... ptree1.vclip (rep, ptree2, X21, 0, ht); ClosestPointPair cpair = rep.getClosestPair(); System.out.println ("closest points:"); System.out.println (cpair.pnt1 + ", " + cpair.pnt2); System.out.println ("closest features:"); System.out.println (cpair.feat1.getName() + ", " + cpair.feat2.getName());Points are described as Point3d objects (from the
javax.vecmath
package).
Features are described using Feature
objects, each of which will be one of the subclasses
Vertex
, Edge
, or
Face
.
If one or both PolyTrees are nonconvex, there may be more than
one ClosestPointPair; specifically, there can be one
ClosestPointPair for each pair of convex polyhedra
associated with the two PolyTrees. It is possible to
have all ClosestPointPairs whose distance is less
than a prescribed maximum value included in the
DistanceReport. This is arranged using
the methods
setMaxClosePairs
and
setMaxPairDistance
before
the call to vclip
, and the results
are obtained using
getClosePairs
:
DistanceReport rep = new DistanceReport(); // include up to 16 closest point pairs, with distance <= 0.1 rep.setMaxClosePairs (16); rep.setMaxPairDistance (0.1); ptree1.vclip (rep, ptree2, X21, 0, ht); ClosestPointPair[] closepairs = rep.getClosePairs(); System.out.println ("close pairs:"); for (int i = 0; i < rep.numClosePairs(); i++) { System.out.println (closepairs[i].pnt1 + ", " + closepairs[i].pnt2); }
scan
method:
PolyTree ptree1 = new PolyTree(); PolyTree ptree2 = new PolyTree(); StreamTokenizer stok = new StreamTokenizer (new FileReader ("PolyTreeExamples.txt")); HashMap library = new HashMap(); ptree1.scan (scanner, library, true, false); ptree2.scan (scanner, library, true, false);The arguments for this version of
scan
are:
ConvexPolyhedron.scanNamedFormat
.
scan
uses a regular
Reader instead of a StreamTokenizer, but has the disadvantage
that line number information will not be preserved between
calls.
The format used to define a PolyTree within a file is described
in the documentation for
scan
.
Alternatively, PolyTrees can be created directly from
ConvexPolyhedrons (which can in turn be read from a file
or defined directly using lists of vertices and faces).
Here is an example
(available in the file
CreateExample.java
)
in which some PolyTrees are created
from a simple ConvexPolyhedra describing a pyramid:
double[] vertexCoords = { 1.0, 0.0, 0.0, 0.0, 1.0, 0.0, 1.0, 0.0, 0.0, 0.0,1.0, 0.0, 0.0, 0.0, 1.0 }; int[][] faceIndices = { { 0, 3, 2, 1 }, { 4, 0, 1 }, { 4, 1, 2 }, { 4, 2, 3 }, { 4, 3, 0 } }; ConvexPolyhedron poly = new ConvexPolyhedron (vertexCoords, faceIndices); PolyTree pyramid = new PolyTree ("pyramid", poly); PolyTree hourglass = new PolyTree ("hourglass"); Matrix4d X = new Matrix4d(); X.setIdentity(); X.setTranslation (new Vector3d (0, 0, 1)); hourglass.addComponent ("bottom", pyramid, X); X.setTranslation (new Vector3d (0, 0, 1)); X.setRotation (new AxisAngle4d (1, 0, 0, Math.PI)); hourglass.addComponent ("top", pyramid, X); hourglass.buildBoundingHull (PolyTree.OBB_HULL);A ConvexPolyhedron is created from vertex and face information, and then used to create an atomic PolyTree called
"pyramid"
. This atomic PolyTree is
then used to define the components of a compound PolyTree called
"hourglass"
. Components are added using
the addComponent
method, which takes a
name for the component, a PolyTree from which the
component is copied, and a spatial transform giving
the location of the component relative to the
PolyTree's local frame (coordinate frames for
PolyTrees are described in the
PolyTree
documentation).
After all the components have been added, the method
buildBoundingHull
is called to build a polyhedral
hull around all the components. Bounding hulls are described
in the next section.
getPolyhedron
method. (For an atomic PolyTree, the bounding hull
is the PolyTree's actual polyhedron.)
The bounding hull is used by vclip
to
prune the distance calculations: if the distance between
the bounding hulls of two PolyTrees exceeds the distLimit
argument, then that distance is returned and the components
of the PolyTree are not examined (which is why the real
distance between the PolyTrees in this case is likely
to be larger).
When PolyTrees are read in from a file, the bounding
hull is created automatically. Otherwise, if a PolyTree
is created using calls to
addComponent
, then
the bounding hull must be created explictly by calling
buildBoundingHull
.
(If a bounding hull
is not created, then vclip
will always
examine the components and will not do any distance
pruning.)
Two types of bounding hulls can be created: the
convex hull of the components (PolyTree.CONVEX_HULL
),
and an oriented bounding box surrounding the components
(PolyTree.OBB_HULL
). The latter is probably
more efficient for calculations. When a bounding hull
is created automatically, the type specified by
getDefaultBoundingHullType
and
setDefaultBoundingHullType
is used.
In order to create a bounding hull, all PolyTree components
which are themselves compound PolyTrees must have a bounding
hull. buildBoundingHull
will ensure
that such a hull is built by calling itself recursively
on component PolyTrees when necessary. Alternatively,
the method
buildAllBoundingHulls
can
be used to explicitly build a bounding hull on
every PolyTree component in the hierarchy.
getPolyhedron
).
These include the volume of the polyhedron,
the first and second moments of volume,
and the product of volume, obtainable
using the methods
volumne
,
firstMomentOfVolume
,
secondMomentOfVolume
,
productOfVolume
, respectively.
All of these are computed with respect to the
PolyTree's local frame. In addtion, the ``radius''
of the polyhedron is computed and can be obtained
using the method
radius
.
These quantities are computed quickly using
algorithms presented by Brian Mirtich in
``Fast and Accurate Computation of Polyhedral
Mass Properties'',
Journal of Graphics Tools, Volume 1,
Number 2, 1996.
If the polyhedron represents a solid of uniform density,
then the first moment of volume can be used to
compute the center of mass, and second moment of volume
and the product of volume can be used to create
the inertia tensor. Assuming a mass of unity, these
quantities can be obtained directly using the methods
centerOfMass
and
inertiaTensor
.


PREV PACKAGE NEXT PACKAGE  FRAMES NO FRAMES 