Cyclone Cyclone: C:/data/physeng_code/include/cyclone/collide_coarse.h Source File

C:/data/physeng_code/include/cyclone/collide_coarse.h

Go to the documentation of this file.
00001 /*
00002  * Interface file for the coarse collision detection system.
00003  * 
00004  * Part of the Cyclone physics system.
00005  * 
00006  * Copyright (c) Icosagon 2003. All Rights Reserved.
00007  *
00008  * This software is distributed under licence. Use of this software
00009  * implies agreement with all terms and conditions of the accompanying
00010  * software licence.
00011  */
00012 
00020 #ifndef CYCLONE_COLLISION_COARSE_H
00021 #define CYCLONE_COLLISION_COARSE_H
00022 
00023 #include <vector>
00024 #include "contacts.h"
00025 
00026 namespace cyclone {
00027 
00029 
00032     struct BoundingSphere
00033     {
00034         Vector3 centre;
00035         real radius;
00036 
00037     public:
00041         BoundingSphere(const Vector3 &centre, real radius);
00042 
00047         BoundingSphere(const BoundingSphere &one, const BoundingSphere &two);
00048 
00053         bool overlaps(const BoundingSphere *other) const;
00055 
00064         real getGrowth(const BoundingSphere &other) const;
00065 
00071         real getSize() const
00072         {
00073             return ((real)1.333333) * R_PI * radius * radius * radius;
00074         }
00076     };
00078 
00080 
00083     struct PotentialContact
00084     {
00088         RigidBody* body[2];
00089     };
00090 
00092 
00098     template<class BoundingVolumeClass>
00099     class BVHNode
00100     {
00101     public:
00103 
00106         BVHNode * children[2];
00107 
00112         BoundingVolumeClass volume;
00113 
00122         RigidBody * body;
00124 
00126         // ... other BVHNode code as before ...
00128 
00130 
00133         BVHNode * parent;
00135 
00139         BVHNode(BVHNode *parent, const BoundingVolumeClass &volume,
00140             RigidBody* body=NULL)
00141             : parent(parent), volume(volume), body(body)
00142         {
00143             children[0] = children[1] = NULL;
00144         }
00145 
00147 
00150         bool isLeaf() const 
00151         { 
00152             return (body != NULL);
00153         }
00154 
00161         unsigned getPotentialContacts(PotentialContact* contacts,
00162                                       unsigned limit) const;
00164 
00166 
00171         void insert(RigidBody* body, const BoundingVolumeClass &volume);
00173 
00175 
00185         ~BVHNode();
00187 
00188     protected:
00189         
00195         bool overlaps(const BVHNode<BoundingVolumeClass> *other) const;
00196 
00203         unsigned getPotentialContactsWith(
00204             const BVHNode<BoundingVolumeClass> *other,
00205             PotentialContact* contacts,
00206             unsigned limit) const;
00207 
00212         void recalculateBoundingVolume(bool recurse = true);
00214     };
00216 
00217     // Note that, because we're dealing with a template here, we
00218     // need to have the implementations accessible to anything that
00219     // imports this header.
00221 
00222     template<class BoundingVolumeClass> 
00223     bool BVHNode<BoundingVolumeClass>::overlaps(
00224         const BVHNode<BoundingVolumeClass> * other
00225         ) const
00226     {
00227         return volume->overlaps(other->volume);
00228     }
00230 
00232     template<class BoundingVolumeClass>
00233     void BVHNode<BoundingVolumeClass>::insert(
00234         RigidBody* newBody, const BoundingVolumeClass &newVolume
00235         )
00236     {
00237         // If we are a leaf, then the only option is to spawn two
00238         // new children and place the new body in one.
00239         if (isLeaf())
00240         {
00241             // Child one is a copy of us.
00242             children[0] = new BVHNode<BoundingVolumeClass>(
00243                 this, volume, body
00244                 );
00245 
00246             // Child two holds the new body
00247             children[1] = new BVHNode<BoundingVolumeClass>(
00248                 this, newVolume, newBody
00249                 );
00250 
00251             // And we now loose the body (we're no longer a leaf)
00252             this->body = NULL;
00253 
00254             // We need to recalculate our bounding volume
00255             recalculateBoundingVolume();
00256         }
00257 
00258         // Otherwise we need to work out which child gets to keep 
00259         // the inserted body. We give it to whoever would grow the
00260         // least to incorporate it.
00261         else
00262         {
00263             if (children[0]->volume.getGrowth(newVolume) <
00264                 children[1]->volume.getGrowth(newVolume))
00265             {
00266                 children[0]->insert(newBody, newVolume);
00267             }
00268             else
00269             {
00270                 children[1]->insert(newBody, newVolume);
00271             }
00272         }
00273     }
00275 
00277     template<class BoundingVolumeClass>
00278     BVHNode<BoundingVolumeClass>::~BVHNode<BoundingVolumeClass>()
00279     {
00280         // If we don't have a parent, then we ignore the sibling
00281         // processing
00282         if (parent)
00283         {
00284             // Find our sibling
00285             BVHNode<BoundingVolumeClass> *sibling;
00286             if (parent->children[0] == this) sibling = parent->children[1];
00287             else sibling = parent->children[0];
00288 
00289             // Write its data to our parent
00290             parent->volume = sibling->volume;
00291             parent->body = sibling->body;
00292             parent->children[0] = sibling->children[0];
00293             parent->children[1] = sibling->children[1];
00294             
00295             // Delete the sibling (we blank its parent and 
00296             // children to avoid processing/deleting them)
00297             sibling->parent = NULL;
00298             sibling->body = NULL;
00299             sibling->children[0] = NULL;
00300             sibling->children[1] = NULL;
00301             delete sibling;
00302 
00303             // Recalculate the parent's bounding volume
00304             parent->recalculateBoundingVolume();
00305         }
00306 
00307         // Delete our children (again we remove their
00308         // parent data so we don't try to process their siblings
00309         // as they are deleted).
00310         if (children[0]) {
00311             children[0]->parent = NULL;
00312             delete children[0];
00313         }
00314         if (children[1]) {
00315             children[1]->parent = NULL;
00316             delete children[0];
00317         }
00318     }
00320 
00321     template<class BoundingVolumeClass> 
00322         void BVHNode<BoundingVolumeClass>::recalculateBoundingVolume(
00323         bool recurse
00324         )
00325     {
00326         if (isLeaf()) return;
00327 
00328         // Use the bounding volume combining constructor.
00329         volume = BoundingVolumeClass(
00330             children[0]->volume,
00331             children[1]->volume
00332             );
00333 
00334         // Recurse up the tree
00335         if (parent) parent->recalculateBoundingVolume(true);
00336     }
00337 
00339     template<class BoundingVolumeClass> 
00340     unsigned BVHNode<BoundingVolumeClass>::getPotentialContacts(
00341         PotentialContact* contacts, unsigned limit
00342         ) const
00343     {
00344         // Early out if we don't have the room for contacts, or
00345         // if we're a leaf node.
00346         if (isLeaf() || limit == 0) return 0;
00347 
00348         // Get the potential contacts of one of our children with
00349         // the other
00350         return children[0]->getPotentialContactsWith(
00351             children[1], contacts, limit
00352             );
00353     }
00354 
00355     template<class BoundingVolumeClass>
00356     unsigned BVHNode<BoundingVolumeClass>::getPotentialContactsWith(
00357         const BVHNode<BoundingVolumeClass> *other,
00358         PotentialContact* contacts,
00359         unsigned limit
00360         ) const
00361     {
00362         // Early out if we don't overlap or if we have no room
00363         // to report contacts
00364         if (!overlaps(other) || limit == 0) return 0;
00365 
00366         // If we're both at leaf nodes, then we have a potential contact
00367         if (isLeaf() && other->isLeaf()) 
00368         {
00369             contacts->body[0] = body;
00370             contacts->body[1] = other->body;
00371             return 1;
00372         }
00373 
00374         // Determine which node to descend into. If either is
00375         // a leaf, then we descend the other. If both are branches, 
00376         // then we use the one with the largest size.
00377         if (other->isLeaf() || 
00378             (!isLeaf() && volume->getSize() >= other->volume->getSize()))
00379         {
00380             // Recurse into ourself
00381             unsigned count = children[0]->getPotentialContactsWith(
00382                 other, contacts, limit
00383                 );
00384 
00385             // Check we have enough slots to do the other side too
00386             if (limit > count) {
00387                 return count + children[1]->getPotentialContactsWith(
00388                     other, contacts+count, limit-count
00389                     );
00390             } else { 
00391                 return count;
00392             }
00393         }
00394         else
00395         {
00396             // Recurse into the other node
00397             unsigned count = getPotentialContactsWith(
00398                 other->children[0], contacts, limit
00399                 );
00400 
00401             // Check we have enough slots to do the other side too
00402             if (limit > count) {
00403                 return count + getPotentialContactsWith(
00404                     other->children[1], contacts+count, limit-count
00405                     );
00406             } else { 
00407                 return count;
00408             }
00409         }
00410     }
00412 
00413 } // namespace cyclone
00414 
00415 #endif // CYCLONE_COLLISION_FINE_H