Repository

Topics

j3d.org

Using Geometry Intersection Tools

The geometry intersection tools may be used for many things but most often for detailed picking information. They also happen to be the core of the Navigation utilities. Their use can be very expensive or very cheap depending on your requirements of the application. For example you can just check to see if something intersects, or ask for all the details such as texture coordinates and normal at that place.

Philosophy

The intersection tools give you a variety of options for use. The most common is expected to be for exact intersection information with a known piece of geometry. We expect however that you may find different uses for it than those in the rest of this toolkit. Therefore all the methods that we use internally are available to you to use as well. Thus, we can provide anything from a single polygon right up to pieces of geometry straight from the scene graph.

As we don't know how you are going to deal with the data, we also define how we deal with the different coordinate spaces. Geometry and the viewpoints rarely exist within the same local coordinate system so we must be able to move back and forth between them. Therefore all of the higher level methods require some form of transformation information. At the low-level, we assume that you have already done this task and do not request transforms.

Internally, the goal of the library is to be as fast as possible. We make use of all the possible optimisation tricks. One problem that we currently have is dealing with the Java3D GeometryArray getter methods. These are generating large amounts of garbage, so we'll discuss some options for dealing with that.

 

Running

Running the geometry intersection tools requires creating and instance of the intersection class and then making requests of the methods on an as-required basis. There is no internal mechanism that continuously runs asynchronously.

Setup

Getting ready to use the interesection tools is no more than creating an instance of the IntersectionUtils class. 
    IntersectionUtils intersector = new IntersectionUtils();
All the intersections require you to supply both the geometry and the information about the ray that we are using for testing. Currently the class only handles line intersections, not arbitrary shapes. The line always has an origin and a direction. If you want to test a line segement rather than an unbounded ray, you can supply the length of the segment from origin.

For the purposes of this exercise, we have the variables as follows: 

    Point3d origin
    Vector3d direction

Small intersections

Small intersections are those where you have a single polygon that you want to check against. For these cases we assume that your picking ray and the polygon are in the same coordinate space. If they are not, you need to make sure they are before calling the class.

The polygon is defined in a flat array of floats that has the X, Y and Z values organised along the floating point arrays. The coordinates are assumed to be arranged counter-clockwise.

To find out if we have an intersection, and just what that intersection is, we need to pass in an instance of a Point3d object as well. This is used to copy the values in of the exact intersection point, if there is one. If there is an intersection with the polygon, the methods will return a boolean value. A true value means that an intersection was found and the point contains a valid value, while false indicates that no point was found. 

    boolean found = intersector.rayPolygon(origin,
                                           direction,
                                           0,
                                           my_coordinates,
                                           num_coordinates,
                                           intersectionPoint);
The extra parameter describing the number of coordinates allows you to pass in an array bigger than what is needed. We only check the coordinates defined by that value. Also, we automatically close the polygon defined by those coordinates, so there is no need to provide the first coordinate again.

Geometry intersections

We expect that most of the time you will want to do higher level checking of intersections against whole pieces of geometry. Two levels of methods are provided - on where you pass in the coordinates and another where you pass in the Java 3D GeometryArray instance to be checked.

If you want to check the raw coordinate arrays, we assume that the coordinates and pick ray exist in the same coordinate system. You will need to do any transformations beforehand.

When providing a piece of geometry, the transformation is asked for so that we may internally deal with the issue. Because you are passing in the Java 3D geometry and we need to access the information in it, that requires the right capabilities to be set. Depending on the geometry passed, you will need to allow for coordinate, index and strip information.

For both forms of geometry we provide you with the option to decide whether to just determine if there is an intersection or to get the full details about the closest intersection point. In the former case we just terminate as soon as we find any intersection point while in the later we always check every polygon and sort the results to find the closest. The first option is useful for simple collision detection where you don't really care what you've hit, just that you've hit something. The latter form is better for detailed picking information to find precise details.

In the first example we check for a quad array to see if there is any intersection between a set of coordinates and the given ray. 

    boolean found = intersector.rayQuadArray(origin,
                                             direction,
                                             0,
                                             my_quads,
                                             num_coordinates,
                                             intersectionPoint
                                             true);
The second example checks for an intersection between a TriangleStripArray and a line segment 3 units long. 
    TriangleStripArray my_array = (TriangleStripArray).myShape3D.getGeometry();
    Transform3D vworld_tx = new Transform3D();
    myShape3D.getLocalToVworld(vworld_tx);

    boolean found = intersector.rayTriangleStripArray(origin,
                                                      direction,
                                                      0,
                                                      my_array,
                                                      vworld_tx,
                                                      intersectionPoint,
                                                      false);
One problem that we encountered during the development was due to the Java3D handling of coordinate information. Internally, we had to make sure that the arrays were correctly sized. An array too large would cause an exception. The result was that almost every check requires us to throw the existing arrays away and allocate a new one - a very, very expensive operation when we are dealing with 40+ frames a second in a terrain following situation. To alleviate this problem, we provide a performance solution - if you pass us data in the form of the GeometryData that we used to do the geometry generation with, we'll use that in preference. This saves needing to set capability bits or generate heaps of garbage.

Providing us with GeometryData may be done through the variant of the rayUnknownGeometry() method or as the userData object for the GeometryArray derivative.

Summary

As you can see, the current intersection utility code is relatively simple to use. It does not yet provide all of the capabilities needed for full picking - such as texture coordinates and normals. That will come in a future iteration.

 
[ Home ] [ License ] [ javadoc ] [ Online Examples ] [ Download ]
[ j3d.org ] [ Aviatrix3D ] [ Code Repository ] [ Java3D ] [ OpenGL ] [ Books ] [ Contact Us ]
Last Updated: $Date: 2010-01-27 21:36:00 -0800 (Wed, 27 Jan 2010) $