Contents 1 Collision Models --Cesar 13:49, 26 November 2006 (EST) 1.1 Basic Structure: the pipeline 1.2 The collision model 1.3 The CollisionElementIterator

Collision Models --Cesar 13:49, 26 November 2006 (EST)

Zut ! No comments ! This is the first thing you might think when you see the uncommented code of SOFA. But it is worst if you are starting with SOFA and you don't know the architecture of SOFA and there is nobody who can explains you. Now, imagine that you need to implement a collision detection model and you don't even know where to start... So, if you are in this situation, then, you might find useful to read these lines. See also the information and discussion in the wiki corresponding to "Collision".

Basic Structure: the pipeline

If you don't know anything about collision detection, then you are really lost! However, I will try to give a short explanation of this. Collision detection aims to find the intersection of objects during a simulation. Once this intersection is found, then you need to apply some collision response models to separate the objects from eachother. The collision detection process is one of the factors that slow down the simulation. So, to accelerate this proccess, SOFA developers follow the next steps:

• Broad phase: The objects in the scene may have either a bounding box or a bounding sphere. So, this phase identifies the bounding volumes in interaction.
• Narrow phase: This phase tests the possible collision between the hierarchy tree bounding volumes. Each bounding volume contains a set of sub-volumes (children) and each subvolume can also contain a set of subvolumes. This defines a hierarchy tree. If the bounding volumes of two objects are colliding, then their subvolumes are tested for collision. Then, the children of the colliding sub-volumes are tested for collision and so on, until the subvolumes do not have children (these subvolumes are know as leaves of the tree).
• Exact phase: "Leaves" are normally associated to the polygons of the object. The colliding leaves will let us know which polygons (or primitives)should be tested. In this phase, we might find triangle-triangle intersection.

These phases are found in:

   void PipelineSofa::doCollisionDetection(§)
   {  :
     broadPhaseDetection->addCollisionModels(vectBoundingVolume);  
      :
     narrowPhaseDetection->addCollisionPairs(vectCMPair);
      :
     DetectionOutput *detection = intersectionMethod->intersect(cm1, cm2);
      :
    }

Unless you are already an expert, you will probably do not want to modify this class. Instead, you should better derive this class as, for example "TestDetection" class.

   class TestDetection : public Collision::BroadPhaseDetection, public Collision::NarrowPhaseDetection, public Abstract::VisualModel
   {
     :
     void addCollisionModel (Abstract::CollisionModel *cm);
     void addCollisionPair (const std::pair<Abstract::CollisionModel*, Abstract::CollisionModel*>& cmPair);
     :
   }

Note that it derives from BroadPhaseDetection and NarrowDetection, so you can use the virtual methods "addCollisionModels" and "addCollisionPairs". To make SOFA use this class, you have to indicate it in the XML file as: <Object type="TestDetection" name="TestDetection" />. So far, other options are possible (e.g. BruteForceDetection.cpp).

NB: Do not forget to put in your class SOFA_DECL_CLASS(yourClass) and in init.cpp: SOFA_LINK_CLASS(TestDetection).

Hence in the broadphase, you identify a set of pairs corresponding to the colliding bounding volumes. You should store these pairs in:

     cmPairs.push_back(std::make_pair(cm, cm2));

"cmPairs" is a STL vector defined in the parent classes. Later, you transfer these pairs to the narrow phase, so you use the method "addCollisionPair". This method should store the leaves of the bounding tree in a STL vector named: elemPairs. So far, the exact phase is carried out in PipelineSofa.cpp, but that should change in the future. The final result is store in the "detection" instance, which is a class (DetectionOutput) containing data such a interpenetretion, colliding point, etc.

The collision model

As you have probably noticed, we have been using a collision model instance (e.g. cm) to define our bounding volume hierarchy of the objects. Let us see this taking as an example SphereTreeModel.cpp. In this example, the sphere tree hierarchy is constructed in an off line proccess. Each sphere in the hierarchy (also known as node) is assigned an "index". So, each time a sphere is read from a file, an index is assigned and incremented. The number of indexes represents the number of degrees of freedom (DOF) of the collision model. In this case, the center of the spheres represents the degree of freedom. Hence, to modify or access them, we use:

    Vector3 ctrOfSph = (*getX())[index]   

"getX()" recovers the pointer to the corresponding degree of freedom (center) given by the "index". Each sphere might have some additional information like its children. See below:

    class SphereTreeModel : public Core::MechanicalObject<Vec3Types>, public Abstract::CollisionModel, public Abstract::VisualModel
    {
      public:
        :
      	struct SphereData
        {   
           :
           std::vector< Abstract::CollisionElementIterator* > children;
        };
         
       /** @brief Nodes of the tree. elem[i] is the "i" DOF of the collision model*/
       std::vector< SphereData > elems;
         :
         
       protected:
          :
        /** @brief  vector of radii of spheres in the model */
        std::vector<double> radius;	
         :
     }

All the information is kept in the SphereTreeModel. So the radius and the spheres are stored in STL vectors and identified by "index". Note that we use a "struct" instead of creating a class for each node. Creating an independent class to instantiate a node (e.g. Sphere sph, Cube cb,) might be computationally expensive.

The CollisionElementIterator

There is however a need to access this information from external classes (e.g. objects defined using virtual classes). To do this, we use a "glorious" pointer. See below:

     class SingleSphere : public Abstract::TCollisionElementIterator<SphereTreeModel>
     {
        public:
        /** @brief Constructor. */
        SingleSphere(SphereTreeModel* model, int index);
         
       /** @brief Constructor */ 
       explicit SingleSphere(Abstract::CollisionElementIterator& i);
       
       /** @brief Returns center of the sphere. It points (according to the index "i")
       to the DOF's of the collision model i.e. the centers of the spheres*/
       const Vector3& center() const;
       
       /** @brief  Set center of sphere. It modifies the center of the sphere with index "i"
       i.e. it modifies one element of the DOF's of the collision model*/
       void setCenter( double x, double y, double z );
        
       /** @brief Returns the radius of the sphere "i" */
       double r() const;
       
        };

Note first that its parent class is an Abstract::TCollisionElementIterator<SphereTreeModel>. This means, that each node of the collision model (in this case, a spheretree) should be related to a TCollisionElementIterator. In order to do this, we construct the element iterator (the glorious pointer SingleSphere) by using the index and model. e.g.

    bool SphereTreeModel::loadSphereTree( const char *fileName )
    {
      :
      for (int i = 0; i < numnodes; i++) 
      {
         :
         --Read center and radius of sphere "i" from file.
         // Collision element iterator
         SingleSphere *s = new SingleSphere(this, i);
         :
         radius[i] = r; 
         :
         SphereData sph;
         --create informatin for sph -
         elems.push_back(sph);	
         :
      }
     :
     }

Hence, each time a sphere is read from a file, we associate it a TCollisionElementIterator giving it the corresponding index "i" and spheretree model "this". Notice that it corresponds to the index where we store the radius and the information of the sphere "elems[i]. So, imagine that you want to access the root node (the largest sphere corresponding, in this case, to index=0) from an external class. So, you define a method as:

      Abstract::CollisionElementIterator* SphereTreeModel::getRootNode( void )
      {
       Abstract::CollisionElementIterator *it = new Abstract::CollisionElementIterator(this, 0 );
       return it;
      }

So, in an external class, like for example in TestDetection.cpp, you can access the root of a model as:

      void TestDetection::addCollisionPair(const std::pair<CollisionModel*, CollisionModel*>& cmPair)
      {
       :
       CollisionModel *cm1 = cmPair.first; 
       Abstract::CollisionElementIterator *rootElem1 = cm1->getRootNode();
       :
      }

Additionally, the TCollisionElementIterator is used to identify which intersection method should be used for that CollisionElementIterator. In other words,

      Collision::ElementIntersector* intersector = intersectionMethod->findIntersector(cm1, cm2);

findIntersector is a templated method that given the collision models cm1, cm2 returns the type of method to use for intersection. For this, you MUST define the type of collision models, and type of intersections in the class DiscreteIntersection.

       DiscreteIntersection::DiscreteIntersection()
       {
        intersectors.add<CubeModel,     CubeModel,     intersectionCubeCube,        distCorrectionCubeCube, false>();
        intersectors.add<SphereModel,   SphereModel,   intersectionSphereSphere,     distCorrectionSphereSphere,     false>();
        intersectors.add<SphereModel,   RayModel,      intersectionSphereRay,        distCorrectionSphereRay,        true>();
        intersectors.add<SphereModel,   RayPickInteractor,      intersectionSphereRay,        distCorrectionSphereRay, true>();
        intersectors.add<SphereTreeModel, SphereTreeModel, intersectionSingleSphereSingleSphere, distCorrectionSingleSphereSingleSphere,false>();

}

Additionally, you need to write the corresponding intersection methods (e.g. intersectionSingleSphereSingleSphere, distCorrectionSingleSphereSingleSphere). ... to continue