Getting Ready

Fundamentals

"I want to have terrain following in my application"

Picking the Right Answer

Well, the answer lies in how you join the dots in the above pieces of the puzzle. Have a look at the above collection of classes that we've mentioned. Not once do we ever talk about the user interface - all of the information that we have, and need is contained in the scene. If you consider what collision detection and terrain following is, it really just boils down to knowing when one part of the scenegraph comes within a given spatial proximity with another part. To do this, we make use of another tool that you are already familiar with - picking.

Picking is basically the act of projecting a line or volume from one point in 3D space to another and seeing what we find in that area. It is ideal for our task as that is exactly what we need to do - is our viewpoint about to hit something in front of us? Well the easiest way to find out is project a line where we are about to move to and let's see if something is there. If it is, we know we are about to hit something - ie a collision.

Note

An introduction to the very basics of picking within Java 3D can be found in the Raw J3D tutorial, in Chapter 6, Picking.

Avatar Representation

A simple model of your avatar is a single point in space. This point is the location of the ViewPlatform that you are current navigating with. As far as the end-user is concerned, that is the middle of the canvas you are showing the world on.

Moving up to a more complex representation involves modelling some form of volume that the avatar occupies. We can apply different types of model - spherical, cylinders and boxes are the most common. These simple shape types are also quite efficient too as there are many standard algorithms available for dealing with them.

On the final level of complexity we can fully model the avatar's geometry in the scene. When dealing with multi-user worlds this is most beneficial as what the user sees and what the other participant see exactly match. It seems really odd when an avatar is half-buried inside some object because the collision detect routines were not accurate enough, or that a user could not pass through an archway Even though their avatar clearly fits.

Collision Avoidance

As we have seen in Java 3D's internal collision detection implementation, it already takes care of the simplest code for us. These cases are when we want to know that we have moved into some bounded area, but don't really have to worry too much about dealing with the consequences.

On the other end of the spectrum, we want to know when any two arbitrary objects in the scene have collided. To go one step further, it could be when any number of objects collide with any other number of objects. This is termed n-body collision handling and is a very expensive operation to implement - particularly for highly interactive applications where you could be walking around inside the scene at the same time.

In the middle of the road, is what we're going to implement - managing collisions between the viewer and items in the scene. This provides the most realistic portrayal of the world and is fairly cheap to implement from the performance perspective. In this model we look at where the user is now, where they are about to be and determine if anything is going to be in the road. If there is we adjust approrpriately.

Implementing viewer collision avoidance is about looking very short times into the future to determine what if about to happen. Typically this is done by looking where you are going to be next frame and adjusting the movement this frame for that. To some degree this involves a small amount of prediction. However, with fast frame rates, the amount that you can travel is very small relative to the time and so the prediction is very unlikely to be wrong.

What we already know is the details about the avatar shape. We then adjust the shape's location and orientation for where the next frame says we are going to be. Then, with that new location we do a pick between the object bounds and the scenegraph. If we have something then react in some way. The typical reaction is to adjust the movement vector in some way. For example if "forwards" is defined as along the local -Z axis, then set the z value of the translation for the next frame to zero. Alternatively, if you know the distance information, you may want to modify the distance travelled proportionally. How you deal with this is really an application dependent setting. We'll show you one way that we implement, but remember that there are other alternatives.

Terrain Following

A concept that is used for terrain following is the avatar size and also a step height. The avatar's size is used to guage how high we should place the viewpoint above the underlying terrain. Each time we move forward, we have to find out what is below us. Once we know that, we have to know whether the avatar is capable of adjusting to it. If you think of a flat terrain, there is really little that needs to be done - everything is correct so just don't interfere with the system. When the terrain drops away, that is no problem either; find the height of the terrain, add the avatar height to it and adjust the position to the new value.

A new story emerges when the terrain rises for the next step. You have to be careful here because that terrain rise might actually be a collision instead. This is where the step height comes in. If the difference between the current location and the next location is less than the step height, you can adjust the avatar's position accordingly. If the step height is greater than that, it can be considered a collision - regardless of the type of avatar body that you are using.

Combining Collision and Terrain

The choice of the operation is up to you. In this discussion we are going to assume that collisions are more important than terrain following. This means we attempt collision detection routines before doing terrain following. If we collide with something, then there is no chance of being able to step over it. Of course, this makes the assumption that the avatar height is always greater than the step height.

Scenegraph setup

• Enabling reporting of pick information
• Enable reading of information back from the scenegraph
• Enable access to transformation information

Scenegraph Structure

Picking requires the use of a large collection of information about geometry and transformations. This means that the underlying rendering engine must keep a lot of extra structures around if we want to do picking. Therefore a goal of our application is to present only the minimal set of structures for picking.

In order to achieve this goal, we want to minimise the number of structures that we enable picking on (picking is not enabled by default). This requires us to think about how we are going to organise the scene graph with regards to pickable and non-pickable parts. Of course, the items that we want to collide against are not necessarily the same items as the ones we want to follow for terrain either. If they are not the same thing, then this makes for smaller selections of nodes that we have to pick from. Less nodes to pick from in each frame means faster processing and therefore greater framerates. So our second goal is to separate the scenegraph structure into two parts - one for terrain and one for collisions.

The end result is a scene graph that has (at least) three logical structures under the one root area - terrain, collidables and everything else. This basic structure is illustrated in Figure 1. Each of these areas are represented by a BranchGroup that holds the information. This is important, because we can only ask a BranchGroup or Locale for picking requests.

Figure 1: Logical scenegraph structure for collision detection and terrain following

Once you structure your scene graph in this manner, you had better make sure that everything is correctly organised from the permissions point of view. If you pass in geometry that is not pickable to say the terrain, then what is the point of even having it there!

Picking Setup

To start our setup, we need to enable picking on the geometry and all of the parent groups to that. The Java 3D spec says that if we do not enable picking on a group, then it is assumed that none of the children are pickable. Thus, before picking can work you need to enable it on every group between the end geometry and the root branchgroup that contains all of our terrain or collidables.

Picking is enabled by calling the setPickable() method on the nodes. Note that you can't just call it on the root node and expect that every child is automatically pickable. Remember that every group with it turned off will disable it for all children. All groups have it turned off by default so that means that although the root node has it enabled, none of its children will and you'll be stuffed. This means you need to turn it on for every node right down to the destination Shape3D instances that contain the real geometry.

One capability that you do not need to enable is the capability ENABLE_PICK_REPORTING. For collision detection purposes, we really only care about the geometry at the end. This capability allows you to look at the nodes between the root Locale and the final Shape3D, which we don't need for this situation. For a similar reason, there is no need to enable the ALLOW_INTERSECT capability on the geometry. For our code, it really isn't going to gain us anything as the intersect operation only works on the parent Shape3D instance, not the individual items of geometry.

Information Reading

There are several ways of performing these calculations, but in the end it still means that we need access to the raw data about vertex coordinates. Then, as we need the vertex coordinates, we need to source those from somewhere. Again, several options are available - perhaps your application keeps a map of geometry to an external set of coordinates. However, for the general purpose case we are going to consider here, we can't assume that and therefore must source the geometry information from the picked node itself.

As the first step, we must enable the appropriate capabilities on the geometry itself. As we are going to build a generalised system, you will need to enable all of the reading information. For example, for a TriangleArray you will need to set ALLOW_COORDINATES_READ. For a more complex item such as an IndexedTriangleStripArray you will need to set much more - coordinates, indices and strip counts.

Geometry could be provided in a number of ways too. Sometimes the information is provided by reference, other times internal copies. Data may be interleaved in the arrays and more. To make sure that we deal nicely with this, we are also going to have to ask for the vertex format information so we know exactly how to read the data from the object. This requires the need to enable yet another capability - ALLOW_FORMAT_READ.

Finally, we need one more thing enabled on the geometry. Asking for the array data means that we need to pre-allocate an array of the correct size for it to be copied into. To do this means we need to enable the ability to read the vertex count from the geometry too. This time the capability is ALLOW_COUNT_READ.

But wait, there's more!

So you thought the geometry was all you needed to handle. How do we get access to the geometry in the first place? Picking returns us a list of Node instances, geometry is extending from NodeComponent. To get access to the geometry, you need to first get the Shape3D instance from the SceneGraphPath that the picking routines return to you. From there you must read the geometry information. So, finally, the last capability you need to enable is ALLOW_GEOMETRY_READ.

Transformation Information

You should know which parts of your scenegraph handle the viewing information. So, what you need to do is allow that part to ask for the transformation from local coordinates to world coordinates. This is known as the VWorld transform in Java 3D parlance. The trick here is to know how you are going to set up the view information. If you are dealing with very simple application models, your scenegraph is only likely to have a simple view platform instance below the transform group that your user interface is controlling (eg mouse). However, come to a more complex scene that has a HUD device and it could be that your viewplatform is acutally a couple of levels down from the main transform group that the user interface is actually acting on. In a game type environment, this means that you really want the collisions to act on the parent transform as that defines your "real" position in the virtual world rather than where the viewplatform is.

If we have the simple case of just ViewPlatform to deal with, all we need to do is set the ALLOW_LOCAL_TO_VWORLD_READ capability directly on the view class itself. For the more complex case, we need to enable it on the controlling transform group - the one that your mouse or keyboard directly controls. Now, you will also need to enable another capability as well. Due to a quirk in the Java 3D specification, when you ask for the vworld transform of a TransformGroup it does not include the local transformation information. That is, you get the vworld transforms to the parent node, not the local node. Thus, to know where you really are, you need to deal with both the parent transforms and the local transform. To do this, you need to add the ALLOW_TRANFORM_READ as well.

Next steps

• Back to the Contents
• On to Collision Detection
• Skip to Terrain Following