Collision Detection and Avoidance

Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

Collision Detection and Avoidance

One of the most basic behaviors in 3D graphics is collision detection, defined here as the ability to detect the presence of one object relative to another. Collision detection is most often used to prevent the user from crashing through walls or tables and in this case is more precisely termed collision avoidance. We will generally refer to both detection and avoidance as collision processing unless the distinction is important to the discussion at hand.

In the design of virtual environments for free ranging navigation, collision avoidance is almost a requirement. Crashing through walls causes a great deal of spatial disorientation and tends to make users want to quit.

In Java 3D, collision processing (similar to pretty much all user behavior processing) is implemented through the Behavior mechanism described previously. The programmer must therefore go back to the idea of what to do and when to do it. For simple collision detection, there already exist some very basic but useful classes. The wakeupOnCollisionEntry and wakeupOnCollisionExit classes do an adequate job of detecting the collision of two objects. Likewise, the wakeupOnViewPlatformEntry and the wakeupOnViewPlatformExit classes can be used to detect when the ViewPlatform is in contact with a single object. We demonstrate the use of these classes with a simple example (see Listing 12.11).

Collision Detection Example

To reiterate, simple collision detection is pretty straightforward. To demonstrate, we give the following example. The TransformGroup of the ViewPlatform is allowed to go forward and backward depending on whether the user pushes the up arrow key (VK_UP) or the down arrow key (VK_DOWN). Each movement is proposed, a pick cone is created, and a test is made to see whether the movement will collide.

Listing 12.11 is the simplest possible example and is elaborated on in the Collision Avoidance example (Listing 12.13 and 12.14) in the next section, “Collision Avoidance Example.”

Listing 12.11 `CollisionDetection.java`

. . .

public class CollisionDetection extends Applet {

  VirtualUniverse universe;
  Locale locale;
  TransformGroup vpTrans;
  TransformGroup[] boxTGs;
  View view;
  Bounds bounds;
  Random r;


   public BranchGroup createSceneGraph() {
        // Create the root of the branch graph; this will be returned

        BranchGroup objRoot = new BranchGroup();
. . .

            //generate random boxes here//
       for (int ii=0; ii<20; ii++) {
          System.out.println("making and adding a box");
          geoTG.addChild(makeBox(ii));
       }

       TransformGroup geoTG = new TransformGroup();
       geoTG.setCapability(TransformGroup.ALLOW_TRANSFORM_WRITE);
       objRoot.compile();
       return objRoot;
   }

    public TransformGroup makeBox(int boxnum) {

        Transform3D t3d = new Transform3D();

        Material mat = new Material();
        mat.setDiffuseColor(new Color3f(r.nextFloat(),r.nextFloat(),  r.nextFloat()));
        Appearance app = new Appearance();
        app.setMaterial(mat);

        t3d.set(new Vector3f(0.f,0.f, boxnum*6));
        TransformGroup boxTG = new TransformGroup();
        boxTG.setCapability(TransformGroup.ALLOW_TRANSFORM_WRITE);
        boxTG.setCapability(TransformGroup.ALLOW_TRANSFORM_READ);
        boxTG.setTransform(t3d);
        Box box = new Box(2*r.nextFloat(),2*r.nextFloat(),2*r.nextFloat(),
                          Box.ENABLE_GEOMETRY_PICKING | Box.GENERATE_NORMALS,
                          app);
        box.setAlternateCollisionTarget(true);
        boxTG.addChild(box);
        return boxTG;

    }

    public CollisionDetection() {
. . .
}

Listing 12.12 `CollisionBehavior.java`

import java.awt.AWTEvent;
import java.awt.event.*;
import java.util.Enumeration;
import javax.media.j3d.*;
import javax.vecmath.*;

import com.sun.j3d.utils.universe.*;
import javax.swing.JRadioButton;

import com.sun.j3d.utils.picking.PickTool;
import com.sun.j3d.utils.picking.PickResult;
// import com.sun.j3d.demos.utils.scenegraph.traverser.TreeScan;
//import com.sun.j3d.demos.utils.scenegraph.traverser.NodeChangeProcessor;

public class CollisionBehavior extends Behavior {

  private TransformGroup tg;
  private Transform3D transform3D;
  private WakeupCondition keyCriterion;

  private final static double TWO_PI = (2.0 * Math.PI);

  private double moveRate = 0.3;
  int keycode;

  Locale locale;
  PickTool pickTool;
  double rotateXAmount = Math.PI / 16.0;
  double rotateYAmount = Math.PI / 16.0;
  double rotateZAmount = Math.PI / 16.0;

  double speed;

  public CollisionBehavior(TransformGroup tg, Locale locale ) {

    this.tg = tg;
    this.locale = locale;
    transform3D = new Transform3D();

    pickTool = new PickTool( locale );
    pickTool.setMode( PickTool.GEOMETRY_INTERSECT_INFO );

  }
  public void setSpeed(double speed) {
      this.speed = speed;
  }

  public void initialize()
  {
    WakeupCriterion[] keyEvents = new WakeupCriterion[2];

    keyEvents[0] = new WakeupOnAWTEvent( KeyEvent.KEY_PRESSED);
    keyEvents[1] = new WakeupOnAWTEvent( KeyEvent.KEY_RELEASED );
    keyCriterion = new WakeupOr( keyEvents );
    wakeupOn( keyCriterion );
  }

    public void processStimulus( Enumeration criteria )
  {
    WakeupCriterion wakeup;
    AWTEvent[] event;

    while( criteria.hasMoreElements() )
    {
      wakeup = (WakeupCriterion) criteria.nextElement();
      if( !(wakeup instanceof WakeupOnAWTEvent) )
        continue;

      event = ((WakeupOnAWTEvent)wakeup).getAWTEvent();
      for( int i = 0; i < event.length; i++ )
      {
        if( event[i].getID() == KeyEvent.KEY_PRESSED )
        {
          processKeyEvent((KeyEvent)event[i]);
        }
      }
    }
    wakeupOn( keyCriterion );
  }

  protected void processKeyEvent(KeyEvent event)
  {
    keycode = event.getKeyCode();
    if(keycode == KeyEvent.VK_UP)
      prepareMove(new Vector3d(0.f, 0.f, -1.f));
    else if(keycode == KeyEvent.VK_DOWN)
      prepareMove(new Vector3d(0.f, 0.f, 1.f));
    else if(keycode == KeyEvent.VK_LEFT)
      System.out.println("rot left");
    else if(keycode == KeyEvent.VK_RIGHT)
      System.out.println("rot right");

    executeMove();
  }

  protected void checkDistance(Vector3d preMove, Vector3d postMove) {
      System.out.println("checking distances to collidable objects");
      int lookahead = -5;

      pickTool.setShapeSegment(new Point3d(preMove.x,
                                           preMove.y,
                                           preMove.z),
                               new Point3d(preMove.x,
                                           preMove.y,
                                           preMove.z + lookahead));

      System.out.println("preMove.x: " + preMove.x +
                         "preMove.y: " + preMove.y +
                         "preMove.z: " + preMove.z +
                         "postMove.x: " + postMove.x +
                         "postMove.y: " + postMove.y +
                         "postMove.z: " + preMove.z);

      PickResult pickRes = pickTool.pickClosest();
      if (pickRes!=null) {

        System.out.println(pickRes.toString());
      }
  }

Figure 12.6 shows the screen output from CollisionDetection.java. A small pick shape, in this case a Pick Segment, is used to test each successive move for a collision. Regardless of the collision, the platform advances. The program is the simplest form of detection algorithm and is used only to reinforce the concepts.

Figure 12.6. Screen output from `CollisionDetection.java`.

Collision Avoidance Example

Collision avoidance is tougher to implement because it requires a type of look ahead function that makes intelligent guesses about where the ViewPlatform will be sometime in the future. The need for the look ahead function is that by the time a collision is detected, it is probably too late to do anything about it. Looking ahead is a common problem in tracking.

Returning to the issue of navigation, we note that if the user is moving faster or slower, the computations of the future location (in a frame or two) are greatly affected. Therefore, it is necessary to have an idea of the user's speed and acceleration in order to do a reasonable job of predicting.

Deciding whether the user will collide with an object in the next frame or two can be solved a number of ways, however: The most straightforward mechanism is an extension of the ray casting picking algorithm described in the previous section. Recall that in mouse-based picking, we shoot a ray from our best guess of the user's eye position through the point of the screen where the user clicked and into the virtual world. Any pickable objects that intersected this ray are put in a cue for future processing.

In the standard Java 3D collision avoidance scheme, a ray (often multiple rays in different directions) is cast from the object of interest (most often the camera position of the ViewPlatform) through the scene. Just as in picking, an array of objects (this time, collidable objects) is returned for future processing. This is the step in which you can estimate the objects that the user is likely to contact in the next frame.

We now present our virtualMSU navigation (see Listing 12.13) that closely approaches a full fledged navigation behavior.

Listing 12.13 `virtualMSU.java`

import java.awt.event.*;
import java.awt.AWTEvent;
import java.util.Enumeration;
import javax.media.j3d.*;
import javax.vecmath.*;
import com.sun.j3d.utils.picking.PickIntersection;
import com.sun.j3d.utils.picking.PickResult;
import com.sun.j3d.utils.picking.PickTool;
import com.sun.j3d.utils.universe.*;
import Joystick;

public class VMSUBehavior extends Behavior {

    // the CollisionBehavior Class's member variables
    private Canvas3D canvas;
    private TransformGroup Target;
    private TransformGroup BackTrans;
    private Transform3D Translation = new Transform3D();
    private Transform3D XRotation = new Transform3D();
    private Transform3D YRotation = new Transform3D();
    private PickTool pickTool;
    private Vector3d UserThrust = new Vector3d(0.0,0.0,0.0);
    private Vector3d Direction = new Vector3d(0.0,0.0,-1.0);
    private Vector3d Velocity = new Vector3d(0.0,0.0,0.0);
    private Point3d CurrentLocation = new Point3d(0.0,5.0,0.0);
    private WakeupCondition WakeCriterion;

    private boolean ForwardKey = false, BackKey = false, RightKey = false,
                    LeftKey = false, UpKey = false, DownKey = false, JumpKey=false;

    private double XAngle = 0.0;
    private double YAngle = 0.0;
    private int old_mouse_x=-1, old_mouse_y=-1, mouse_x=-1, mouse_y=-1;

    private Vector3d Gravity = new Vector3d(0.0,-0.06,0.0);
    private double CollisionRadius = 0.8;
    private double Friction = 0.0;
    private double speed = 0.08;
    private int InputDevice = 0;                    // 0 - mouse + keyboard
                                                    // 1 - Joystick
    private Joystick joy = new Joystick(0);
    private double InputSensitivity = 0.01;

    //
    // Constructor with the simple universe to use
    //
    public VMSUBehavior(SimpleUniverse u) {
        this.Target=u.getViewingPlatform().getViewPlatformTransform();
        this.canvas = u.getCanvas();
        pickTool = new PickTool(u.getLocale());
    }

    //
    // this method gets called automatically.  I use it to set the
    // conditions for what triggers the behavior
    //
    public void initialize() {
        pickTool.setMode(PickTool.GEOMETRY_INTERSECT_INFO);
        WakeupCriterion[] MouseWakeEvents = new WakeupCriterion[5];

        MouseWakeEvents[0] = new WakeupOnAWTEvent( MouseEvent.MOUSE_MOVED);
        MouseWakeEvents[1] = new WakeupOnAWTEvent( MouseEvent.MOUSE_DRAGGED );
        MouseWakeEvents[2] = new WakeupOnAWTEvent( KeyEvent.KEY_PRESSED );
        MouseWakeEvents[3] = new WakeupOnAWTEvent( KeyEvent.KEY_RELEASED );
        MouseWakeEvents[4] = new WakeupOnElapsedFrames(0);

        WakeCriterion = new WakeupOr( MouseWakeEvents );
        wakeupOn( WakeCriterion );
    }

    //
    // called whenever the wakeup conditions are met,
    // does Physics() every frame and MouseControl whenever the mouse
    // is moved
    //
    public void processStimulus(java.util.Enumeration enumeration) {
        // stop the renderer so it doesn't show stuff while we are in the middle of 
calculating
        canvas.stopRenderer();

        WakeupCriterion wakeup;
        // determine what event awoke it
        while (enumeration.hasMoreElements() ){
            wakeup = (WakeupCriterion) enumeration.nextElement();
            if ( wakeup instanceof WakeupOnElapsedFrames)
                Physics();
            if ( InputDevice == 0 ){
                if ( wakeup instanceof WakeupOnAWTEvent ) {
                    // determine if it is a mouse event
                    AWTEvent[] events = ((WakeupOnAWTEvent)wakeup)
                    for (int i = 0; i<events.length; i++) {
                        if (events[i] instanceof MouseEvent){
                            MouseControl( (MouseEvent)events[i] );
                        } else if (events[i] instanceof KeyEvent){
                            KeyControl( (KeyEvent)events[i] );
                        }
                    }
                }
            } else {
                JoystickControl();
            }
        }
        wakeupOn( WakeCriterion );

        // ok we're done
        canvas.startRenderer();
    }

    //
    // allows you to change the internal variables
    //
    public void setCurrentLocation(double x, double y, double z) {
        CurrentLocation.set(x,y,z);
    }
    public void setGravity(double x, double y, double z) {
        Gravity.set(x,y,z);
    }
    public void setFriction(double friction) {
        Friction = friction;
    }
    public void setCollisionRadius(double radius) {
        CollisionRadius = radius;
    }
    public void setSpeed(double NewSpeed) {
        speed = NewSpeed;
    }

    //
    // lets the you attach a background object to the Behavior
    //
    public void addBack( TransformGroup trans){
        BackTrans = trans;
    }

   //
   // KeyEvent code below
   //
   public void keyPressed(java.awt.event.KeyEvent keyEvent) {
        if (InputDevice==0) {
            switch (keyEvent.getKeyCode()){
                // Forward
                case KeyEvent.VK_W:
                    ForwardKey = true;
                    break;
                // Backward
                case KeyEvent.VK_S:
                    BackKey = true;
                    break;
                // Right
                case KeyEvent.VK_D:
                    RightKey = true;
                    break;
                // Left
                case KeyEvent.VK_A:
                    LeftKey = true;
                    break;
                // go up
                case KeyEvent.VK_SPACE:
                    JumpKey = true;
                    break;
                // garbage collect
                case KeyEvent.VK_ESCAPE:
                    System.gc();
            }
        }
    }
    public void keyReleased(java.awt.event.KeyEvent keyEvent) {
        if (InputDevice==0) {
            switch (keyEvent.getKeyCode()){
                // Forward
                case KeyEvent.VK_W:
                    ForwardKey = false;
                    break;
                // Backward
                case KeyEvent.VK_S:
                    BackKey = false;
                    break;
                // Right
                case KeyEvent.VK_D:
                    RightKey = false;
                    break;
                // Left
                case KeyEvent.VK_A:
                    LeftKey = false;
                    break;
                // go up
                case KeyEvent.VK_SPACE:
                    JumpKey = false;
                    break;
            }
        }
    }

    //
    // Turns the transform when the mouse is moved
    //
    private void MouseControl( MouseEvent mevt){
        int dx, dy;
        mouse_x = mevt.getX();
        mouse_y = mevt.getY();
        dx = (mouse_x - old_mouse_x);
        dy = (mouse_y - old_mouse_y);
        old_mouse_x = mouse_x;
        old_mouse_y = mouse_y;
        if (old_mouse_x!=-1){
            YAngle += dx * -1 * InputSensitivity;
            XAngle += dy * -1 * InputSensitivity;
            if (XAngle > Math.PI/2.0)
                XAngle = Math.PI/2.0;
            if (XAngle < 0.0-Math.PI/2.0)
                XAngle = 0.0 - Math.PI/2.0;
        }
    }

    //
    // Joystick Control
    //
    private void JoystickControl(){
        XAngle += joy.getYPos()*InputSensitivity;
        YAngle -= joy.getXPos()*InputSensitivity;
        if (XAngle > Math.PI/2.0)
            XAngle = Math.PI/2.0;
        if (XAngle < 0.0-Math.PI/2.0)
            XAngle = 0.0 - Math.PI/2.0;
    }

    //
    // Sets the acceleration in response to key presses
    //
    private void KeyControl( KeyEvent kevt){
        switch (kevt.getID()){
            case KeyEvent.KEY_PRESSED:
                keyPressed(kevt);
                break;
            case KeyEvent.KEY_RELEASED:
                keyReleased(kevt);
                break;
        }

    }

    //
    // handles collisions -  I'm sure this could be written
    // more efficiently but I finally got it working and I'm
    // afraid of changing it
    //
    private void Collisions() {
        // might not have to do anything
         if (Velocity.lengthSquared() < 0.0001)
            return;

        // Prepare to pick
        pickTool.setShapeRay( CurrentLocation, Velocity);
        // a few variables to be used in this function
        Vector3d Normal = new Vector3d();
        Point3d pickHit = new Point3d();
        Vector3d a = new Vector3d();
        double d1=0.0;

        // do the pick
        PickResult pr = pickTool.pickClosest();
        if (pr!=null){
            PickIntersection pi = pr.getClosestIntersection( CurrentLocation );
            if ((pi!=null)&&(pi.getPointNormal()!=null)){
                Normal.set(pi.getPointNormal());
                Normal.normalize();
                pickHit = pi.getPointCoordinatesVW();
                // a is the vector from the collision point to  the future location
                a.set(CurrentLocation);
                a.add(Velocity);
                a.sub(pickHit);
                // use a dot product to see how far he is from the collision plane
                d1 = a.dot(Normal);
                if (d1 < CollisionRadius){
                    //CurrentLocation.scaleAdd((CollisionRadius-d1), Normal, 
CurrentLocation);
                    Velocity.scaleAdd( (CollisionRadius-d1), Normal, Velocity);
                    Velocity.scaleAdd( -1.0*(Velocity.dot(Normal)), Normal, Velocity);
                }
            }
        }
        // re-pick, this time checking the downward direction
        pickTool.setShapeRay( CurrentLocation, Gravity);
        pr = pickTool.pickClosest();
        if (pr!=null){
            PickIntersection pi = pr.getClosestIntersection( CurrentLocation );
            if ((pi!=null)&&(pi.getPointNormal()!=null)){
                Normal.set(pi.getPointNormal());
                Normal.normalize();
                pickHit = pi.getPointCoordinatesVW();
                // a is the vector from the collision point to the future location
                a.set(CurrentLocation);
                a.add(Velocity);
                a.sub(pickHit);
                // use a dot product to see how far he is from the collision plane
                d1 = a.dot(Normal);
                if (d1 < CollisionRadius){
                    //CurrentLocation.scaleAdd((CollisionRadius-d1), Normal, 
CurrentLocation);
                    Velocity.scaleAdd( (CollisionRadius-d1), Normal, Velocity);
                    //Velocity.scaleAdd( -1.0*(Velocity.dot(Normal)), Normal, Velocity);
                }
            }
        }
    }

    //
    // Calls the functions associated with the physics simulation
    //
    private void Physics() {
        //
        UserAcceleration();
        Collisions();
        Movement();

        UpdateTransform();
    }

    //
    // Updates the position of the transform
    //
    private void Movement() {
        // I don't really like this, but it is necessary to
        // prevent there from being too much sliding
        if (Velocity.lengthSquared() < 0.0001)
            Velocity.set(0.0,0.0,0.0);
        else
            CurrentLocation.add(Velocity);
    }

    //
    // Lets the user accelerate
    //
    private void UserAcceleration() {
        CalcUserThrust();
        Velocity.set(UserThrust);
        Velocity.add(Gravity);
    }

    //
    // Forces the player to head down
    //
    private void GravityAcceleration() {
        Velocity.set(Gravity);
    }

    //
    // applies the changes to the transform
    //
    private void UpdateTransform() {
        YRotation.rotY(YAngle);
        XRotation.rotX(XAngle);
        YRotation.mul(XRotation);
        YRotation.setTranslation( new Vector3d(CurrentLocation) );
        Target.setTransform(YRotation);

        if (BackTrans!=null){
            Translation.setTranslation( new Vector3d(CurrentLocation) );
            BackTrans.setTransform(Translation);
        }
    }

    //
    // find new thrust vector based on user input
    //
    private void CalcUserThrust() {
        UserThrust.set(0.0,0.0,0.0);
        // handle the acceleration vector control
        if (InputDevice==0) {
            if (ForwardKey){
                Direction.set(-1.0*(float)Math.cos(Math.PI/2.0-YAngle), 0.0, -1.0*(
float)Math.sin(Math.PI/2.0-YAngle));
                UserThrust.add(Direction);
            } if (BackKey) {
                Direction.set((float)Math.cos(Math.PI/2.0-YAngle), 0.0, (float)Math.sin(
Math.PI/2.0-YAngle));
                UserThrust.add(Direction);
            } if (RightKey) {
                Direction.set(-1.0*(float)Math.cos(Math.PI-YAngle), 0.0, -1.0*(float)Math.
sin(Math.PI-YAngle) );
                UserThrust.add(Direction);
            } if (LeftKey) {
                Direction.set((float)Math.cos(Math.PI-YAngle), 0.0, (float)Math.sin(Math.
PI-YAngle) );
                UserThrust.add(Direction);
            } if (UpKey) {
                Direction.set(0.0, 1.0, 0.0);
                UserThrust.add(Direction);
            } if (DownKey) {
                Direction.set(0.0, -1.0, 0.0);
                UserThrust.add(Direction);
            } if (JumpKey) {
                Direction.set(0.0, 1.0, 0.0);
                UserThrust.add(Direction);
            }
            // set it to the correct magnitude
            if (UserThrust.length()>0.0) {
                UserThrust.normalize();
                UserThrust.scale(speed);
            }
        } else if (InputDevice==1) {
            if (joy.getButtons()==1){
                Direction.set(-1.0*(float)Math.cos(Math.PI/2.0-YAngle),
                               0.0, -1.0*(float)Math.sin(Math.PI/2.0-YAngle));
                UserThrust.add(Direction);
            }
            // set it to the correct magnitude
            if (UserThrust.length()>0.0) {
                UserThrust.normalize();
                UserThrust.scale(speed);
            }
        }
    }

    //
    // changes the control system
    //
    public void useJoystick(double sensitivity){
        InputDevice = 1;
        InputSensitivity = sensitivity;
    }

    //
    // changes the control system
    //
    private void useMouseAndKeyboard(){
        InputDevice = 0;
    }
}

Figure 12.7 shows screen output from the VirtualMSU.java. The user is able to navigate and look around a virtual reality model of various parts of the VirtualMSU Campus using the virtualMSUBehavior navigator.

Figure 12.7. Screen output from the `VirtualMSU.java`.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for Collision Detection and Avoidance

Create new playlist

Sign In

Sign Up

Collision Detection and Avoidance

Collision Detection Example

Listing 12.11 CollisionDetection.java

Listing 12.12 CollisionBehavior.java

Figure 12.6. Screen output from CollisionDetection.java.

Collision Avoidance Example

Listing 12.13 virtualMSU.java

Figure 12.7. Screen output from the VirtualMSU.java.

Table of Contents for
Collision Detection and Avoidance

Listing 12.11 `CollisionDetection.java`

Listing 12.12 `CollisionBehavior.java`

Figure 12.6. Screen output from `CollisionDetection.java`.

Listing 12.13 `virtualMSU.java`

Figure 12.7. Screen output from the `VirtualMSU.java`.