Package vclip

Vclip is a package for computing distances and checking for collisions between polyhedra.


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 face-face 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.

Package vclip Description

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 ``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 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.

Simple Example

Here is a simple example (available in the file 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);
	{ System.out.println ("colliding");
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:

Distance Reports

As mentioned above, the closest points and features between two PolyTrees is returned in a 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 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 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);

Defining PolyTrees

PolyTrees can be created in various ways. One of the most straightforward is to read them from a stream, either as a library, or individually, using the 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: Another version of 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 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.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.

Bounding Hulls

A bounding hull is a convex polyhedron which encapsulates all the components within a compound PolyTree, and is the polyhedron returned by the 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.

Mass and Volume Parameters of Convex Polyhedra

Mass and volume parameters are automatically created for the convex polyhedron associated with a PolyTree (i.e., the one returned by 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.