Sections

j3d.org

Collision Detection System

Author: Justin Couch
Last Update: $Date: 2006/04/18 18:20:02 $

Collision detection within Java 3D has been one of the most discussed areas on the interest list. Most of the discussions have been along the lines of "why doesn't it work like it is supposed to?". The answer to this, is that there really hasn't been any definitive "this is what it is supposed to do" documentation. People read parts of the API and make certain assumptions and most of the time these are incorrect.

The following discussion comes from a thread that started in early March 2001. There were a number of contributors to this including Kelvin Chung and Doug Twilleager from the J3D team at Sun. I've glued this all together and also added a heap of extra information over the top to try to bring some bigger picture information to the table as well.

 

Why Doesn't It Work?

When newcomers first look at Java 3D, they notice a whole bunch of classes and something called a behaviour system. When looking at behaviours they then notice a couple of classes - namely WakeUpOnCollisionEntry and WakeUpOnCollisionExit and automatically assume that the "system" gives them collision detection.

Unfortunately, for both the beginner and the expert, they assume that this is a one-size-fits-all thing. The reality is that it is not. Indeed, it is quite different from first expectations. Most often people see the game style collision system. As you hit a wall the user reacts by stopping or sliding along it or similar action. When they come to code this up in Java 3D using what they assume to be the right APIs, what they see on screen is quite different. Either is acts really slowly, or there are strange artifacts like entering the wall or mysterious code loops of behaviours.

Behaviours Background

In Java 3D's architecture behaviours act as a semi-synchronous mechanism for feeding back to a user information about the state of the scene. For instance you can use these to wake up a piece of code each rendered frame, have it makes some changes to the scenegraph and then go back to sleep again. What happens in the behaviour is reflected in the next rendered frame. Here is where users tend to loose the connection between expectations and code.

     Note
    The only behaviour guaranteed to be synchronous with the renderer is WakeUpOnElapsedFrame with a time of zero frames. All others are asynchronous and have no exact definition of when they will be called. As collisions are just another form of behaviour it should become clear why they behave like in this asynchronous manner.
How the above paragraph should be read is: Something happens in a frame, a behaviour is then notified, it makes some changes, exits and then the next frame happens. According to the specification, there is no guarantee that if the behaviour is called it will effect the current frame. It is possible that with dual threads, the current frame start will trigger the behaviour thread, which will then act independently of the renderer. How the changes make it from one thread to the other is not guaranteed. The safest bet approach for this is that the changes will be visible in the next frame rather than the current one that we are rendering.

How Collision Behaviours are Triggered

The most important clue from the above behaviour information is that a frame is rendered while the behaviours are being called. What that indicates is that a collision will be detected during the current frame and your behaviour code will be notified. Effectively the behaviour here is acting as an Observer pattern rather than a Command pattern. Something has already happened and all your code can do is respond to it, rather than having any ability to control what rendering code is going to do. The collision has already happened and now you have to deal with it.

For fast paced rendering such as FPS games, it is quite possible that your viewpoint could walk straight through the middle of a wall in a single frame. The collision with the wall object has already occurred, the rendering system has rendered this fact and now you are left to deal with the pieces. In a real game you want to guarantee that the collision is detected before the rendering step rather than after or during it - when it is too late already. The key behaviour keyword here is "entry". The behaviour notifies you when your viewpoint has entered the collision area. Assuming an infinitely thin wall between being inside and outside the collision area, there is no way you could ever be "just" colliding in the way that games will show. A single frame could move you from 0.1 unit outside the collision area to 0.1 unit inside it and you have no way of adjusting for that. What you really need is the ability to pre-empt the movement, calculate how far you would be allowed to move in the next frame and only allow that amount of movement.

 

Detection Algorithm

If you want to know how efficient the collision mechanism, this section details the actual algorithm used within Sun's implementation of Java 3D. For most users, it probably won't be useful, but for the high-end people that want to know how much impact the collision detection has on the overall performance, read on. The information here has been gained from several robotics people asking for further information and the answers supplied by the Sun engineers. For most general users it is probably safe to skip this bit and head to the next section on how to implement a useful Java 3D collision system.

Wheat and Chaff

Collisions are considered a form of behaviour, so the first thing that the runtime does is organise the data in spatial groups. The viewpoint has an activation region surrounding it, and each of the objects marked as collidable have a region surrounding them. If these two areas intersect then these are added to the list of active areas to watch for. There is no point trying to detect collisions with an object 1000 units away if you are only 1 unit wide.


Figure 1: The basic collision areas and the user views. The grey areas are removed from the collision detection because they do not intersect with the user's view area

To do this first part relatively quickly, J3D uses a spatially organised tree (which is apparently used for all geometric operations - behaviour culling, rendering culling etc) which I suspect is some form of quad tree (no details have been given). The efficiency is dependent on how well balanced this tree is ie how well objects are distributed around the virtual world relative to the user's position and how many child items are there.

     Note
    Doug adds the following notes:

    Collisions are "triggered" as a part of the Behavior system. Each ViewPlatform has an activation radius. Each behavior has a scheduling region (bounds). When a behaviors scheduling region intersects with any ViewPlatform's activation radius, it may be scheduled. Note that all of this is generic to the behaviors system, and has nothing to do with collisions.

    Once a behavior is schedulable, its wakeup conditions become active. Once the behaviors wakeup conditions have been met, while it is schedulable, it is actually scheduled for execution by the behavior scheduler. So, for collision, the armed collision (via WakeupOnCollisionXXX()) is only looked for when its behavior is schedulable. Once the collision is armed and active, it is tested for collision against all of the geometry in the scene graph. It is at this stage where we need our spatial hierarchy of all the geometry in the scene graph. This spatial hierarchy is currently an axis aligned bounding box tree.

A better description is given in figure 2. Consider a standard scenegraph with transforms. At the top you have the whole world. Next step down are all the major items that have been added as children of the world. A bounding box, that covers the maximum extent of each is used. Each object has a number of smaller objects that have smaller bounding boxes - each guaranteed to be contained within the parent area. For each child of these we again have smaller bounding boxes and so on until there is no smaller piece of geometry. To determine whether we should bother to look further, we start at the top bounding box and eliminate any children that do not intersect with our viewpoint bounding box. We keep working our way down this tree until we have reached an end point of geometry that has no further children. Any that remain with overlapping bounds we can consider to be within a collision situation.


Figure 2: Dividing bounding boxes up in a heirarchical tree. The yellow box defines the "top" of the tree. The individual body parts marked in red and blue are the next branch down. Finally the hands, marked in green are further smaller branches from the arms.

More Detail

The situation just described is the default method for collision detection - ie when we use WakeUpOnCollisionEntry.USE_BOUNDS for the speed hint. The problem with this is that bounding boxes are effectively alligned to the axes and therefore cover the largest possible volume for the contained object. In many cases, what we really want is something much more accurate. If the object is lying along one of the diagonal axis, we want to be able to fly across it with having a collision report.

To do this, we have to get much more detailed in the intersection tests. Effectively this is a brute force approach. We have to test each polygon in the scene for whether it is colliding with our viewpoint bounds. Although not directly stated, I believe that the collision system first does a pass to eliminate all non-suspect objects with bounds and then hones in doing a polygonal search for the remaining objects to find out where contact was made, if at all. Once we get to this level it is an O(n^2) operation and so can be very slow. This is called the V-Collide algorithm and works with all object shapes including convex hulls.

Kelvin Chung recommends that if you are doing geometry based collision that it is better to split your objects up into a lot of smaller Shape3D's rather than one big large, complex one. This allows fast tossing away of as much data as possible before doing the costly searches.

Doug Twilleager also offers the following insight into the implementation: When a collision is armed via Behavior.wakeupOn() with one of the WakeupOnCollisionXXX() criterion, we send a message to the bounding box tree. From that point on, until the criterion is met (a collision), the bounding box tree is responsible for doing a collision query when nessesary. This means that we will only do the collision query when the collision is armed, or something is moving in the scene. This prevents any extra processing when collisions are armed. It also means that there is no extra collision thread like there was in the 1.1 version of Java 3D.

What about two objects colliding?

If you've been taking careful note of the above statements, we have been talking about the viewpoint being used as one source for the collision. What this implies is that we are not talking about one object colliding with another in the scene.

The same techniques can be applied to two objects colliding together as for the viewpoint and an object. The definition of the criteria described in Java 3D are applicable to both situations. Where the current implementation falls down is dealing with N-body collision situations - detecting if 3 or more objects are colliding at the same time together (think of the impact of the cue ball when breaking in a game of billiards).

 

Implementing Something Useful

As we have outlined above, the standard behaviours provided by Java 3D are a collision detection system. That is, they notify you that a collision has taken place, but don't allow you to do much about it. An example of an application where this might be useful is a furniture placement app where when two objects overlap you want to change their colour or make some sort of highlight to indicate a problem. It is not useful for doing a FPS system where you want to stop people passing through walls. This sort of requirement is more correctly termed a collision avoidance scheme. Java 3D does not provide this and you will need to implement it yourself.

There are two major forms of collision avoidance schemes that most people want to use in their application: terrain following and solid geometry. The procedures that you use to implement this in the first are then more generalised for the second.

Please note that this is a discussion more along architecture lines of Java 3D rather than a detailed implementation guide. Here we are only talking about general principles rather than large slabs of code.

Terrain Following

Terrain following involves an object maintaining a certain given distance above the "ground". In a virtual environment, this ground concept does not necessarily need to be something that has grass or carpet on it. It could well be some arbitrary data level or similar construct.The core principle is that we have a direction that is considered to be "down" and that we want to maintain a certain distance away from that.

To maintain the distance, we need to determine what the current distance is and adjust it accordingly. To work out what that distance is, we basically look directly along the "down" vector and see where it intersects the object below us. In Java 3D, the concept of looking along a line for an intersection point is called picking. For all the concepts you see here, you basically use the picking API's to cast a ray from one object to see what else it intersects and then make some course of action based on the result. Figure 3 shows how this would work along a smoothly undulating terrain.


Figure 3: Simplistic terrain following. The object always stays a fixed position above the ground directly below.

This simplistic view of the world does have some short-comings. What if the terrain has holes in it with nothing below or we encounter a large step object in our path. Both of these situations are illustrated in Figure 4. In the first case, there is nothing ever below us, so picking will not return a picked object. Therefore, how do we know what value to set the transform of our object?

In the latter case, things get more interesting. Here we see the effects of Java 3D's behaviour system. We have moved, or are about to move. We cast a ray below us and determine that we have to jump a certain height. However, because the behaviour could nominally be running in parallel with the renderer the renderer might draw us in this frame inside the box and then the next frame, after we have made the jump above the box. This leads to nasty visual artifacts and really is an unwanted thing.


Figure 4: The effects of the simplistic algorithm when dealing with different conditions: On the left step type objects - a sudden shift in the viewpoint position. On the right, nothing below us, what do we do?

Jumping from one height to another is bad for two reasons: Firstly we could end up with the visual effects that you saw above. Secondly, in real life transitions between the two levels are not a jump cut, but a transistion. With this behaviour we have lost all realism and potentially a good dose of motion sickness on the part of the viewer.

To combat the jumping box syndrome, we need to go to something more intelligent about deciding when and how much to move the object. In effect, this means doing some sort of search ahead to determine what we should do a frame or two ahead of where we are now. Perhaps we need to wrap a sphere around the object to have it detect the closest point on that. Small edges like the box would then give nice transitions. Also holes in the terrain, if smaller than the diameter of the sphere would save us odd calculation problems too.

Collision Avoidance

A generalised collision avoidance system is a generalised version of terrain following. Now we are concerned more about what is all around us rather just purely what is below. This is where the spherical technique is useful. Not only does it tell us about things below, but also above and to the sides. You can hit your head in virtual worlds too!

The biggest difference between collision avoidance and terrain following is what you do with the distance information to picked objects once you've got it. Say we are moving along at two units per frame. Directly in front of us there is a solid wall one unit away. If we kept going, next frame we would be right through the wall, which we really want to avoid. So, what we do is only allow the user to move one unit next frame. This puts them right on top of the wall. The frame after that they can't move at all because their distance away is now zero. You see the difference in techniques here: For terrain following we adjust the transform matrix to always keep a fixed distance where in avoidance we clamp the values being put into the matrix depending on the situation.

Of course, the human body is not spherical, so if you want to go to that next level of accuracy your collision avoidance routine will have to change the shape that represents your user or object in the world. When doing this, note that it now becomes another object to object collision problem - but instead of the rendering system doing for you, you will need to do everything yourself. As you will remember from before, this is a very expensive operation in CPU cycles so you would probably be much better of dropping one notch in the realism stakes for a much more interactive world.

 

Cleaning Up

That's the end of the collision discussions. If you don't know how to implement picking or collisions, then look in one of the tutorials or Java 3D books.

Further Information

 
[ j3d.org ] [ Aviatrix3D ] [ Code Repository ] [ Java3D ] [ OpenGL ] [ Books ] [ Contact Us ]
Hosted by
Last Updated: $Date: 2006/04/18 18:20:02 $