The original version of Vclip was written in C++ by Brian Mirtich at MERL, and is based on his algorithm described in ``V-Clip: 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 V-clip 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. V-clip also uses the package convexhull3d, written by John Lloyd, for computing 3D convex hulls.
The basic Vclip computation involves calculating the distance between {@link vclip.PolyTree 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 sub-PolyTrees.
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("unit-cube"); 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
{@link vclip.PolyTree#scanLibrary 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 {@link vclip.PolyTree#vclip vclip}, which takes the following arguments:
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.
vclip
computations. An application can create
a single ClosestFeaturesHT and use this in all
calls to vclip
.
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 {@link vclip.Feature Feature}
objects, each of which will be one of the subclasses
{@link vclip.Vertex Vertex}, {@link vclip.Edge Edge}, or
{@link vclip.Face Face}.
If one or both PolyTrees are non-convex, 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
{@link vclip.DistanceReport#setMaxClosePairs setMaxClosePairs}
and
{@link vclip.DistanceReport#setMaxPairDistance setMaxPairDistance}
before
the call to vclip
, and the results
are obtained using
{@link vclip.DistanceReport#getClosePairs 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); }
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 {@link vclip.PolyTree#scan(StreamTokenizer,Map,boolean,boolean) scan} are:
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
{@link vclip.PolyTree PolyTree} documentation).
After all the components have been added, the method {@link vclip.PolyTree#buildBoundingHull(int) buildBoundingHull} is called to build a polyhedral hull around all the components. Bounding hulls are described in the next section.
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
{@link vclip.PolyTree#addComponent addComponent}, then
the bounding hull must be created explictly by calling
{@link vclip.PolyTree#buildBoundingHull(int) 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
{@link vclip.PolyTree#getDefaultBoundingHullType
getDefaultBoundingHullType} and
{@link vclip.PolyTree#setDefaultBoundingHullType
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
{@link vclip.PolyTree#buildAllBoundingHulls buildAllBoundingHulls} can
be used to explicitly build a bounding hull on
every PolyTree component in the hierarchy.
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 {@link vclip.PolyTree#centerOfMass centerOfMass} and {@link vclip.PolyTree#inertiaTensor inertiaTensor}.