git.maemo.org Git - blok/blob - Box2D/Source/Collision/b2BroadPhase.h

   1 /*
   2 * Copyright (c) 2006-2007 Erin Catto http://www.gphysics.com
   3 *
   4 * This software is provided 'as-is', without any express or implied
   5 * warranty.  In no event will the authors be held liable for any damages
   6 * arising from the use of this software.
   7 * Permission is granted to anyone to use this software for any purpose,
   8 * including commercial applications, and to alter it and redistribute it
   9 * freely, subject to the following restrictions:
  10 * 1. The origin of this software must not be misrepresented; you must not
  11 * claim that you wrote the original software. If you use this software
  12 * in a product, an acknowledgment in the product documentation would be
  13 * appreciated but is not required.
  14 * 2. Altered source versions must be plainly marked as such, and must not be
  15 * misrepresented as being the original software.
  16 * 3. This notice may not be removed or altered from any source distribution.
  17 */
  18
  19 #ifndef B2_BROAD_PHASE_H
  20 #define B2_BROAD_PHASE_H
  21
  22 /*
  23 This broad phase uses the Sweep and Prune algorithm as described in:
  24 Collision Detection in Interactive 3D Environments by Gino van den Bergen
  25 Also, some ideas, such as using integral values for fast compares comes from
  26 Bullet (http:/www.bulletphysics.com).
  27 */
  28
  29 #include "../Common/b2Settings.h"
  30 #include "b2Collision.h"
  31 #include "b2PairManager.h"
  32 #include <climits>
  33
  34 #ifdef TARGET_FLOAT32_IS_FIXED
  35 #define B2BROADPHASE_MAX        (USHRT_MAX/2)
  36 #else
  37 #define B2BROADPHASE_MAX        USHRT_MAX
  38
  39 #endif
  40
  41 const uint16 b2_invalid = B2BROADPHASE_MAX;
  42 const uint16 b2_nullEdge = B2BROADPHASE_MAX;
  43 struct b2BoundValues;
  44
  45 struct b2Bound
  46 {
  47         bool IsLower() const { return (value & 1) == 0; }
  48         bool IsUpper() const { return (value & 1) == 1; }
  49
  50         uint16 value;
  51         uint16 proxyId;
  52         uint16 stabbingCount;
  53 };
  54
  55 struct b2Proxy
  56 {
  57         uint16 GetNext() const { return lowerBounds[0]; }
  58         void SetNext(uint16 next) { lowerBounds[0] = next; }
  59         bool IsValid() const { return overlapCount != b2_invalid; }
  60
  61         uint16 lowerBounds[2], upperBounds[2];
  62         uint16 overlapCount;
  63         uint16 timeStamp;
  64         void* userData;
  65 };
  66
  67 class b2BroadPhase
  68 {
  69 public:
  70         b2BroadPhase(const b2AABB& worldAABB, b2PairCallback* callback);
  71         ~b2BroadPhase();
  72
  73         // Use this to see if your proxy is in range. If it is not in range,
  74         // it should be destroyed. Otherwise you may get O(m^2) pairs, where m
  75         // is the number of proxies that are out of range.
  76         bool InRange(const b2AABB& aabb) const;
  77
  78         // Create and destroy proxies. These call Flush first.
  79         uint16 CreateProxy(const b2AABB& aabb, void* userData);
  80         void DestroyProxy(int32 proxyId);
  81
  82         // Call MoveProxy as many times as you like, then when you are done
  83         // call Commit to finalized the proxy pairs (for your time step).
  84         void MoveProxy(int32 proxyId, const b2AABB& aabb);
  85         void Commit();
  86
  87         // Get a single proxy. Returns NULL if the id is invalid.
  88         b2Proxy* GetProxy(int32 proxyId);
  89
  90         // Query an AABB for overlapping proxies, returns the user data and
  91         // the count, up to the supplied maximum count.
  92         int32 Query(const b2AABB& aabb, void** userData, int32 maxCount);
  93
  94         void Validate();
  95         void ValidatePairs();
  96
  97 private:
  98         void ComputeBounds(uint16* lowerValues, uint16* upperValues, const b2AABB& aabb);
  99
 100         bool TestOverlap(b2Proxy* p1, b2Proxy* p2);
 101         bool TestOverlap(const b2BoundValues& b, b2Proxy* p);
 102
 103         void Query(int32* lowerIndex, int32* upperIndex, uint16 lowerValue, uint16 upperValue,
 104                                 b2Bound* bounds, int32 boundCount, int32 axis);
 105         void IncrementOverlapCount(int32 proxyId);
 106         void IncrementTimeStamp();
 107
 108 public:
 109         friend class b2PairManager;
 110
 111         b2PairManager m_pairManager;
 112
 113         b2Proxy m_proxyPool[b2_maxProxies];
 114         uint16 m_freeProxy;
 115
 116         b2Bound m_bounds[2][2*b2_maxProxies];
 117
 118         uint16 m_queryResults[b2_maxProxies];
 119         int32 m_queryResultCount;
 120
 121         b2AABB m_worldAABB;
 122         b2Vec2 m_quantizationFactor;
 123         int32 m_proxyCount;
 124         uint16 m_timeStamp;
 125
 126         static bool s_validate;
 127 };
 128
 129
 130 inline bool b2BroadPhase::InRange(const b2AABB& aabb) const
 131 {
 132         b2Vec2 d = b2Max(aabb.lowerBound - m_worldAABB.upperBound, m_worldAABB.lowerBound - aabb.upperBound);
 133         return b2Max(d.x, d.y) < 0.0f;
 134 }
 135
 136 inline b2Proxy* b2BroadPhase::GetProxy(int32 proxyId)
 137 {
 138         if (proxyId == b2_nullProxy || m_proxyPool[proxyId].IsValid() == false)
 139         {
 140                 return NULL;
 141         }
 142
 143         return m_proxyPool + proxyId;
 144 }
 145
 146 #endif