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 {@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.

Simple Example

Here is a simple example (available in the file 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:

Distance Reports

As mentioned above, the closest points and features between two PolyTrees is returned in a {@link vclip.DistanceReport DistanceReport}. Actual point and feature information is contained in a {@link vclip.ClosestPointPair ClosestPointPair}, obtained using the {@link vclip.DistanceReport#getClosestPair 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 {@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);
     }

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 {@link vclip.PolyTree#scan(StreamTokenizer,Map,boolean,boolean) 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 {@link vclip.PolyTree#scan(StreamTokenizer,Map,boolean,boolean) scan} are: Another version of {@link vclip.PolyTree#scan(Reader,Map,boolean,boolean) 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 {@link vclip.PolyTree#scan(Reader,Map,boolean,boolean) 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 {@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.

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 {@link vclip.PolyTree#getPolyhedron 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 {@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.

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 {@link vclip.PolyTree#getPolyhedron getPolyhedron}). These include the volume of the polyhedron, the first and second moments of volume, and the product of volume, obtainable using the methods {@link vclip.PolyTree#volume volumne}, {@link vclip.PolyTree#firstMomentOfVolume firstMomentOfVolume}, {@link vclip.PolyTree#secondMomentOfVolume secondMomentOfVolume}, {@link vclip.PolyTree#productOfVolume 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 {@link vclip.PolyTree#radius 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 {@link vclip.PolyTree#centerOfMass centerOfMass} and {@link vclip.PolyTree#inertiaTensor inertiaTensor}.