Dual Scene Collider

The class SoDualSceneCollider performs very fast collision detection for the case of two scene graphs, one static and one moving. This class has been designed to detect collisions between very large scenes (i.e., containing millions of triangles) while still allowing interactive display of the two scenes. You can retrieve information about colliding triangles, coordinates of common points, and so forth. This is useful, for example, for walk-through of a complex factory environment.

SoDualSceneCollider has not been designed to check collisions
of an animated scene in which several shapes are moving.

Using SoDualSceneCollider

The first scene, called the “moving scene”, is specified by the method setMovingScene(). The second scene, called the “static scene”, is specified by the method setStaticScene(). These two methods each have two arguments, an SoPath and an integer. The tail node of this path specifies the root of the moving or static scene graph. SoDualSceneCollider references each of the scenes by storing its triangle list and by building a database as a tree. The tree is organized spatially and hierarchically to optimize the process of searching for intersecting pairs of triangles. The leaves of this tree contain the triangles while the internal nodes do not. The performance of intersection checking between the two scenes depends on the number of triangles in each leaf. For this reason, the methods setMovingScene()/**setStaticScene()** have also an integer argument (max_triangles_per_leaf) for specifying the maximum number of triangles per leaf.

The spatial tree does not depend on the organization of the two supplied Open Inventor scene graphs. This means that the application does not need to spatially organize the scene graphs to get better performance when using SoDualSceneCollider.

The following figure shows the tree of the same Open Inventor scene graph with three different values of max_triangles_per_leaf.

Typical scene graph organization

null transform, this transform is monitored by SoDualSceneCollider. Each time the transform node changes, the method checkCollision() is automatically called and checks if the moving scene collides with the static scene.

SoDualSceneCollider does not monitor the scene graph:checkCollision() is not called when a modification to the Open
Inventor nodes in the static scene or the moving scene occurs. To maintain consistency between
the scene graph and the spatial tree (see above), setMovingScene() / setStaticScene() must be
called whenever the moving/static scene graph is changed.

When the two scenes collide, the “response” method searchNextIntersection() is called for each common point of the two scenes. Each time checkCollision() finds a new pair of intersecting triangles, searchNextIntersection() is called. By default, this method returns FALSE, telling checkCollision() that no other pairs of intersecting triangles need to be searched. This default implementation means that checkCollision() is just answering the question: are the two scenes colliding or not?

However, the main interest of collision detection is to provide different responses like, for instance:

1. Get the number of pairs of intersecting triangles
2. Get the coordinates of each pair of common points
3. Highlight the shapes that are intersecting
4. Get back to the last state of the moving scene when it did not collide with the static scene
5. Glue the moving scene to the static scene by doing an approximation between the last state and the current state of the moving scene Your application must override the method searchNextIntersection() (and also checkCollision() if necessary) to implement these kinds of collision responses. Of course, overriding means subclassing the class SoDualSceneCollider.

The simplest response type is item 1, and can be implemented as shown below. See source code at:

$OIVHOME/src/Inventor/examples/Features/Collision/SimpleSceneCollider/CountingIntersection.cxx

C++ :

class CountingIntersection : public SoDualSceneCollider
{
private:
  mutable int num_ti; // num intersecting pair of triangle.
public:
  SbBool
  checkCollision() const
  {
    num_ti = 0;
    SbBool result = SoDualSceneCollider::checkCollision();
    std::cout << "Number of triangle intersection " << num_ti << std::endl;
    return result;
  }
 
  SbBool
  searchNextIntersection() const
  {
    num_ti++;
    return TRUE; // yes, search again for other intersections!
  }
};

C# :

class CountingIntersection : SoDualSceneCollider
{
  private int num_ti; // num intersecting pair of triangle.
 
  public override bool CheckCollision()
  {
    num_ti = 0;
    bool result = base.CheckCollision();
    Console.WriteLine( "Number of triangle intersection: {0}", num_ti );
    return result;
  }
 
  public override bool SearchNextIntersection()
  {
    num_ti++;
    return true; // yes, search again other intersections !
  }
}

Java :

This previous example is not the most efficient way to know if two scenes
collide or not. The default implementation of SoDualSceneCollider is much more efficient because it stops the search for
intersecting triangles after the first pair is found.

In order to implement other types of responses, for example items 2 through 5 in the list above, the API of SoDualSceneCollider provides additional methods (protected) that can be called by an overridden version of searchNextIntersection():

Returns the path in the scene of the current colliding shape:

• getCollidingStaticPath()
• getCollidingMovingPath() Returns the coordinates of the current colliding triangle in the static scene:
• getCollidingStaticTriangle()
• getCollidingMovingTriangle() Returns the coordinates of the two common points of the current pair of intersecting triangles (one per scene)
• getCommonPoints() See the reference manual page of SoDualSceneCollider for more details

The following example shows a way of getting the coordinates of each pair of common points. See source code at:

$OIVHOME/Inventor/examples/Features/Collision/SimpleSceneCollider/GettingIntersectionPoints.cxx

C++ :

class GettingIntersectionPoints : public SoDualSceneCollider
{
private:
  std::vector<SbVec3f> common_p0;
  std::vector<SbVec3f> common_p1;
 
public:
  SbBool
  checkCollision() const
  {
    common_p0.clear();
    common_p1.clear();
    SbBool result = SoDualSceneCollider::checkCollision();
    // print here the list of common points
    return result;
  }
  SbBool
  searchNextIntersection() const
  {
    SbVec3f p0, p1;
    getCommonPoints( p0, p1 );
    common_p0.push_back( p0 );
    common_p1.push_back( p1 );
    return TRUE; // yes, search again for other intersections!
  }
}

C# :

class GettingIntersectionPoints : SoDualSceneCollider
{
  private List<SbVec3f> common_p0 = new List<SbVec3f>();
  private List<SbVec3f> common_p1 = new List<SbVec3f>();
 
  public override bool CheckCollision()
  {
    common_p0.Clear();
    common_p1.Clear();
    bool result = base.CheckCollision();
    PrintCommonPoints();
    return result;
  }
 
  public override bool SearchNextIntersection()
  {
    SbVec3f p0 = new SbVec3f();
    SbVec3f p1 = new SbVec3f();
 
    GetCommonPoints( out p0, out p1 );
    common_p0.Add( p0 );
    common_p1.Add( p1 );
    return true; // yes, search again other intersections !
  }
}

The SoDualSceneCollider also provides methods that allow an application to know when the hierarchical structure of the scenes is rebuilding.

• movingTriangleListBuilt() ,movingLeafBuilt()
• staticTriangleListBuilt() ,staticLeafBuilt() As the build can be relatively time consuming on a slow CPU (especially when handling several millions of triangles), these methods can be used to provide information for a progress bar.

The demonstration example DemoCollider shows a more sophisticated implementation of searchNextIntersection() and checkCollision() that

• highlights the first pair of intersecting shapes
• highlights the common points
• unhighlights previous shapes and common points when no collision is detected
• counts the total number of collisions Furthermore, the protected methods staticTriangleListBuilt(), staticLeafBuilt(), movingTriangleListBuilt(), and movingLeafBuilt() are overridden by DemoCollider to display a progress bar while the hierarchical structure of the scenes is being built (i.e., when a new scene is read from an .iv file)

See source code at:

$OIVHOME/Inventor/examples/Features/Collision/SceneCollider/DemoCollider.cxx