Implementing Terrain Following in Java 3D

Depending on your view of the world, terrain following is sort of like collision detection. However, this time, instead of looking where we are going, we'll be looking down at our feet to see if we trip up on something.

Just like the collision detection system, what we present here will be a generalised algorithm that is applicable for most applications. There are also a lot of ways to optimise this process and we'll point those out as we go and also don't forget all of the tips from the previous section.

Note

If you want to use the basic algorithms appearing here, there is a complete implementation available in the j3d.org Code Repository. This code is the generalised solution that you see here and so can be plugged into any application immediately.

Basic Process

Navel Gazing

Just like collision detection, actions for terrain following are based on dealing with knowing where we are about to go, rather than where we are now. The whole point of terrain following is to make sure that we are the correct height above the ground now, rather than correcting for mistakes of the past. To do this, we must look during this frame where we are going to be next frame and adjust the positions accordingly.

Where collision avoidance and terrain following is the direction they look and how far they look. Collision detection was really only interested in knowing about the next frame so it purposefully limited its search to a very small distance. In terrain following, we really don't know where we are located above the underlying terrain (if at all!). To know this, we have to cast an endless ray into the scenegraph rather than just a line segment.

The second difference is where we are looking. Collision detection looked out along the -Z axis to see what was in front of us. Terrain following requires looking at our feet so this time the direction is along the -Y axis.

Jumping to Conclusions

The concept that we introduced was that of a step height - the maximum positive change in the terrain delta between our current position and the next position before we decide to disallow it and call it a collision. For example, climbing a set of stairs requires the use of sharp discontinuities in height, but if the stair becomes too big, it becomes a wall. Each time we deal with terrain changes, we have to decide whether the delta is too big. Also, one assumption here is that we don't care about descending terrain - the user can fall as far as they like.

Figure 3: Data and terms used when dealing with terrains

Another interesting consideration in this work is - what if the viewpoint that the user first gives us is not at the exact height above the terrain? Well, this might be deliberate. Think of a viewpoint where the world author is attempting to make a series of snapshot views but offer no navigation at that point. They wouldn't take to kindly to us "correcting" their obviously mistaken judgement, so we limit the algorithm to apply only when the user starts to move around. Only after they have made that first step can you be assured that it is OK to move the viewpoint around to be at the right height above the terrain.

Gravity does the work

All terrain following has a form of gravity, it is just a case of deciding how quickly we want it to take effect. Also, getting gravity right is a very tricky problem to solve. In many cases real world accelaration style gravity just feels wrong. A constant value for gravity feels more gentle on the user. Step over a cliff and you get this nice steady descent and soft landing rather than as a bug splat on the ground.

Implementation

Design Assumptions

1. do we always have triangle sets or do we have to deal with arbitrary sized data.
2. Can we guarantee that there is only one GeometryArray per Shape3D?
3. Has the user structured the scene graph properly so that we never have intersecting geometry bounding boxes for the type of operation that we want to do (collisions or terrain following)
4. Do either the viewpoint or the data exist under a large set of transforms or are they all at the world root?
5. Is gravity at work or not?
6. How do we react when there is no ground?

In this first implementation, we are not going to worry about gravity handling. If we encounter a large drop, we will jump that distance immediately.

Dealing with no ground below us can be an interesting problem. For safety, if we discover that there is no ground then we just don't play with anything. This allows us to deal with problems where we might get a very slight mismatch in the boundaries between two sets of polygons that define terrain trials. Another mistake it catches is having a world that has no ground but the user accidently selected terrain following anyway.

Stock standard bits

Looking down upon something

    viewTg.getLocalToVworld(worldEyeTransform);
    worldEyeTransform.mul(viewTx);

    worldEyeTransform.get(locationVector);
    locationPoint.add(locationVector, oneFrameTranslation);

Note

If you are using both collision avoidance and terrain following together, you don't need to recalculate the new location. This will save you a few more CPU cycles per frame.

The next piece you need to deal with is projecting the down vector. Because this time we are concerned about everything that might be below us, there is actually less work to do. All we have to do is swing the local "down" vector into the world coordinate space.

    worldEyeTransform.transform(Y_DOWN, downVector);

    terrainPicker.set(locationPoint, downVector);

Finding the terrain

    SceneGraphPath[] ground = terrain.pickAllSorted(terrainPicker);

    if(ground == null)
    return;

Internally, we have a similar loop to the collision avoidance:

    double shortest_length = -1;

    for(int i = 0; i < ground.length; i++)
    {
        Transform3D local_tx = ground[i].getTransform();
        local_tx.get(locationVector);

        Shape3D i_shape = (Shape3D)ground[i].getObject();

        Enumeration geom_list = i_shape.getAllGeometries();

        while(geom_list.hasMoreElements())
        {
            GeometryArray geom = (GeometryArray)geom_list.nextElement();

            if(geom == null)
                continue;

            if(insection detection)
            {
                diffVec.sub(locationPoint, this_intersection_point);

                if((shortest_length == -1) ||
                   (diffVec.lengthSquared() < shortest_length))
                {
                    shortest_length = diffVec.lengthSquared();
                    intersectionPoint.set(wkPoint);
                }
            }
        }
    }

Now, at the end of this loop we have the closest intersection point of our terrain stored in intersectionPoint and we also have an indicator as to whether we found anything. Remember - if the loop never found a real intersection, the value of shortest_length will still be negative. If we didn't find anything exit now.

What's up shorty?

    double terrain_step = intersectionPoint.y - lastTerrainHeight;
    double height_above_terrain = locationPoint.y - intersectionPoint.y;

When the heights are not the same. we check to see which set of conditions hold and act accordingly:

• If the change in height is zero then we need to adjust the height of the avatar to be the correct height above the ground.
• If the change in height of the terrain is less than the step height, we adjust the height to be the new height plus the avatar's height. (This includes dealing with negative changes - falling terrain).
• Otherwise the change in height greater than the step height and therefore we treat it as a collision and prevent any movement this turn.

    if(height_above_terrain != avatarHeight)
    {
        if(terrain_step == 0)
        {
            oneFrameTranslation.y = avatarHeight - height_above_terrain;
        }
        else if(terrain_step < avatarStep)
        {
            oneFrameTranslation.y += terrain_step;
            ret_val = true;
        }
        else
        {
            ret_val = false;
        }
    }

    lastTerrainHeight = (float)intersectionPoint.y;

Getting Started

Nope. In the above pieces of code we've assumed that the value of lastTerrainHeight is set from the last time around so that we can make some valid judgements. Problem is, what happens the first frame where we don't have any pre-established data?

To get around this problem, what we do is make sure that when the viewpoint information is first set, to do a terrain intersection run then. This will establish what the fundamental height is of the terrain. Note that at this point we don't even adjust the viewpoint, we just make note of the current terrain height for future reference.

Summary

As we've hinted throughout this tutorial, what we have covered is a generalised system that should work for any environment. However, if you know that you can apply certain restrictions to your scenegraph structure and you don't have to deal with arbitrary data, then quite a number of performance optimisations can be made to the code.

We hope that this has been a useful tutorial. Please feel free to send the usual feedback on areas that you think could do with more work or explanation. Lastly, if you don't feel like implementing all of this code yourself, please drop by the J3d.org Code Repository for the implementation there.

• Back to the Contents
• Back to Setup
• Back to Collision Detection