00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
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 ¢re, 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
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
00218
00219
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
00238
00239 if (isLeaf())
00240 {
00241
00242 children[0] = new BVHNode<BoundingVolumeClass>(
00243 this, volume, body
00244 );
00245
00246
00247 children[1] = new BVHNode<BoundingVolumeClass>(
00248 this, newVolume, newBody
00249 );
00250
00251
00252 this->body = NULL;
00253
00254
00255 recalculateBoundingVolume();
00256 }
00257
00258
00259
00260
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
00281
00282 if (parent)
00283 {
00284
00285 BVHNode<BoundingVolumeClass> *sibling;
00286 if (parent->children[0] == this) sibling = parent->children[1];
00287 else sibling = parent->children[0];
00288
00289
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
00296
00297 sibling->parent = NULL;
00298 sibling->body = NULL;
00299 sibling->children[0] = NULL;
00300 sibling->children[1] = NULL;
00301 delete sibling;
00302
00303
00304 parent->recalculateBoundingVolume();
00305 }
00306
00307
00308
00309
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
00329 volume = BoundingVolumeClass(
00330 children[0]->volume,
00331 children[1]->volume
00332 );
00333
00334
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
00345
00346 if (isLeaf() || limit == 0) return 0;
00347
00348
00349
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
00363
00364 if (!overlaps(other) || limit == 0) return 0;
00365
00366
00367 if (isLeaf() && other->isLeaf())
00368 {
00369 contacts->body[0] = body;
00370 contacts->body[1] = other->body;
00371 return 1;
00372 }
00373
00374
00375
00376
00377 if (other->isLeaf() ||
00378 (!isLeaf() && volume->getSize() >= other->volume->getSize()))
00379 {
00380
00381 unsigned count = children[0]->getPotentialContactsWith(
00382 other, contacts, limit
00383 );
00384
00385
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
00397 unsigned count = getPotentialContactsWith(
00398 other->children[0], contacts, limit
00399 );
00400
00401
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 }
00414
00415 #endif // CYCLONE_COLLISION_FINE_H