# Palomino - Collision-Detection Module

©2004,2009 Jim E. Brooks http://www.palomino3d.org

- Index
- Flaws
- Overview

- Collision vs. Crash

- Implementation
- OSG Ray Intersection
- Safe Contact

## Flaws

[2010/12]

A known flaw is that every collidable is tested against every other one, resulting in redundant testing.

For Objects { A, B, C }, testing should iterate as a mathematical combination
where a tested Object is removed from further testing:
combination: AB, AC, BC
inefficient: AB, AC, BA, BC, CA, CB
AB and BA are redundant.

## Overview

[2010/05]

The Collision class abstracts the exact collision-detection algorithm. It is passed a Dyna and determines if it has collided into another Object. Dyna objects have a Dyna::Tick() method which executes collision-detection.

Collision-detection is done when Tick() is called because that is the place where a Dyna will be animated. SetMatrix() isn't the reliable place to do collision-detection, because it could be bypassed, for example, SetPosition() could be implemented to directly change the matrix.

### Collision vs. Crash

[2008/03]

The collision module is dedicated to collision-detection as opposed to crash-determination.

Don't confuse collision-detection with crash-determination. A collision is just an intersection of graphical objects. Determining a crash is a more complex function that begins with collision as the first criteria, but involves additional criteria such as physics (velocity, momentum).

## Implementation

[2008/08]

Collision-detection is based on OSG ray intersection (osg::IntersectionVisitor). But the algorithm is abstracted by the Collision class, which would allow reimplementing Collision (using BSP trees in case OSG ray intersection proves sub-optimal).

Collidable and non-collidable objects are segregated by the Collision singleton. This is for both correctness and efficency. Objects such as clouds and sky domes aren't collidable but might be intersected. Collision maintains a container of collidable Objects. Objects, via Object::SetCollidable(), informs changes in collidability to Collision.

## OSG Ray Intersection

[2008/02]

Dyna objects are translated in 3D space every tick. The starting and ending 3D points of the movement ("step") forms the ray used for testing intersection. Note the alternative of using a positive and negative radius to form a ray across the Object's bounding sphere would be inaccurate because the length of a step could be several times greater.

From the Naval Postgraduate School's OSG tutorial:

LineSegments (osg::LineSegment) Intersection detection is based on rays. Line segments provide a means to define these rays. Line segments consist of two osg::Vec3 instances - one to define a start point and one to define the end point. When invoked, intersection detection is performed along this ray. [..]
IntersectionVisitor: Intersection detection tests between a ray and geometry instances in a scene are initiated by creating and applying an intersection visitor. The intersectionVisitor class is derived from the NodeVisitor class. A list of line segments to use for intersection detection is maintained. For each of these segments, a list of hits (osgUtil::IntersectVisitor::HitList instance) is created.

## Safe Contact

[2008/02]

The collision module, being graphical in nature, is separate from physics. Collision::IfCollision() simply reports an intersection of a line and geometry.

Determining a safe contact shall be done externally by combining methods of the collision and physics modules.

    Craft::Tick()
    {
        mCollision = Collision::GetInstance().IfCollision( this )
        if ( mCollision )
        {

            // If descending, velocity's altitude coordinate will be negative.
            const Velocity velocity = GetCraftPhysics().ComputeVelocity();
            if ( velocity[ALT] < SAFE_LANDING_THRESHOLD )
            {
                Crash();
            }
        }
    }

    CraftPhysics::Tick()
    {
        if ( mCraft->IfCollision() )
        {
            [add contact force]
        }
    }

Last modified: Tue Dec 14 11:39:44 CST 2010