1 /*
2 Bullet Continuous Collision Detection and Physics Library
3 Copyright (c) 2003-2013 Erwin Coumans http://bulletphysics.org
4
5 This software is provided 'as-is', without any express or implied warranty.
6 In no event will the authors be held liable for any damages 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 freely,
9 subject to the following restrictions:
10
11 1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
12 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
13 3. This notice may not be removed or altered from any source distribution.
14 */
15
16 ///b3DynamicBvhBroadphase implementation by Nathanael Presson
17 #ifndef B3_DBVT_BROADPHASE_H
18 #define B3_DBVT_BROADPHASE_H
19
20 #include "Bullet3Collision/BroadPhaseCollision/b3DynamicBvh.h"
21 #include "Bullet3Collision/BroadPhaseCollision/b3OverlappingPairCache.h"
22 #include "Bullet3Common/b3AlignedObjectArray.h"
23
24 #include "b3BroadphaseCallback.h"
25
26 //
27 // Compile time config
28 //
29
30 #define B3_DBVT_BP_PROFILE 0
31 //#define B3_DBVT_BP_SORTPAIRS 1
32 #define B3_DBVT_BP_PREVENTFALSEUPDATE 0
33 #define B3_DBVT_BP_ACCURATESLEEPING 0
34 #define B3_DBVT_BP_ENABLE_BENCHMARK 0
35 #define B3_DBVT_BP_MARGIN (b3Scalar)0.05
36
37 #if B3_DBVT_BP_PROFILE
38 #define B3_DBVT_BP_PROFILING_RATE 256
39
40 #endif
41
B3_ATTRIBUTE_ALIGNED16(struct)42 B3_ATTRIBUTE_ALIGNED16(struct)
43 b3BroadphaseProxy
44 {
45 B3_DECLARE_ALIGNED_ALLOCATOR();
46
47 ///optional filtering to cull potential collisions
48 enum CollisionFilterGroups
49 {
50 DefaultFilter = 1,
51 StaticFilter = 2,
52 KinematicFilter = 4,
53 DebrisFilter = 8,
54 SensorTrigger = 16,
55 CharacterFilter = 32,
56 AllFilter = -1 //all bits sets: DefaultFilter | StaticFilter | KinematicFilter | DebrisFilter | SensorTrigger
57 };
58
59 //Usually the client b3CollisionObject or Rigidbody class
60 void* m_clientObject;
61 int m_collisionFilterGroup;
62 int m_collisionFilterMask;
63 int m_uniqueId; //m_uniqueId is introduced for paircache. could get rid of this, by calculating the address offset etc.
64
65 b3Vector3 m_aabbMin;
66 b3Vector3 m_aabbMax;
67
68 B3_FORCE_INLINE int getUid() const
69 {
70 return m_uniqueId;
71 }
72
73 //used for memory pools
74 b3BroadphaseProxy() : m_clientObject(0)
75 {
76 }
77
78 b3BroadphaseProxy(const b3Vector3& aabbMin, const b3Vector3& aabbMax, void* userPtr, int collisionFilterGroup, int collisionFilterMask)
79 : m_clientObject(userPtr),
80 m_collisionFilterGroup(collisionFilterGroup),
81 m_collisionFilterMask(collisionFilterMask),
82 m_aabbMin(aabbMin),
83 m_aabbMax(aabbMax)
84 {
85 }
86 };
87
88 //
89 // b3DbvtProxy
90 //
91 struct b3DbvtProxy : b3BroadphaseProxy
92 {
93 /* Fields */
94 //b3DbvtAabbMm aabb;
95 b3DbvtNode* leaf;
96 b3DbvtProxy* links[2];
97 int stage;
98 /* ctor */
99
b3DbvtProxyb3DbvtProxy100 explicit b3DbvtProxy() {}
b3DbvtProxyb3DbvtProxy101 b3DbvtProxy(const b3Vector3& aabbMin, const b3Vector3& aabbMax, void* userPtr, int collisionFilterGroup, int collisionFilterMask) : b3BroadphaseProxy(aabbMin, aabbMax, userPtr, collisionFilterGroup, collisionFilterMask)
102 {
103 links[0] = links[1] = 0;
104 }
105 };
106
107 typedef b3AlignedObjectArray<b3DbvtProxy*> b3DbvtProxyArray;
108
109 ///The b3DynamicBvhBroadphase implements a broadphase using two dynamic AABB bounding volume hierarchies/trees (see b3DynamicBvh).
110 ///One tree is used for static/non-moving objects, and another tree is used for dynamic objects. Objects can move from one tree to the other.
111 ///This is a very fast broadphase, especially for very dynamic worlds where many objects are moving. Its insert/add and remove of objects is generally faster than the sweep and prune broadphases b3AxisSweep3 and b332BitAxisSweep3.
112 struct b3DynamicBvhBroadphase
113 {
114 /* Config */
115 enum
116 {
117 DYNAMIC_SET = 0, /* Dynamic set index */
118 FIXED_SET = 1, /* Fixed set index */
119 STAGECOUNT = 2 /* Number of stages */
120 };
121 /* Fields */
122 b3DynamicBvh m_sets[2]; // Dbvt sets
123 b3DbvtProxy* m_stageRoots[STAGECOUNT + 1]; // Stages list
124
125 b3AlignedObjectArray<b3DbvtProxy> m_proxies;
126 b3OverlappingPairCache* m_paircache; // Pair cache
127 b3Scalar m_prediction; // Velocity prediction
128 int m_stageCurrent; // Current stage
129 int m_fupdates; // % of fixed updates per frame
130 int m_dupdates; // % of dynamic updates per frame
131 int m_cupdates; // % of cleanup updates per frame
132 int m_newpairs; // Number of pairs created
133 int m_fixedleft; // Fixed optimization left
134 unsigned m_updates_call; // Number of updates call
135 unsigned m_updates_done; // Number of updates done
136 b3Scalar m_updates_ratio; // m_updates_done/m_updates_call
137 int m_pid; // Parse id
138 int m_cid; // Cleanup index
139 bool m_releasepaircache; // Release pair cache on delete
140 bool m_deferedcollide; // Defere dynamic/static collision to collide call
141 bool m_needcleanup; // Need to run cleanup?
142 #if B3_DBVT_BP_PROFILE
143 b3Clock m_clock;
144 struct
145 {
146 unsigned long m_total;
147 unsigned long m_ddcollide;
148 unsigned long m_fdcollide;
149 unsigned long m_cleanup;
150 unsigned long m_jobcount;
151 } m_profiling;
152 #endif
153 /* Methods */
154 b3DynamicBvhBroadphase(int proxyCapacity, b3OverlappingPairCache* paircache = 0);
155 virtual ~b3DynamicBvhBroadphase();
156 void collide(b3Dispatcher* dispatcher);
157 void optimize();
158
159 /* b3BroadphaseInterface Implementation */
160 b3BroadphaseProxy* createProxy(const b3Vector3& aabbMin, const b3Vector3& aabbMax, int objectIndex, void* userPtr, int collisionFilterGroup, int collisionFilterMask);
161 virtual void destroyProxy(b3BroadphaseProxy* proxy, b3Dispatcher* dispatcher);
162 virtual void setAabb(int objectId, const b3Vector3& aabbMin, const b3Vector3& aabbMax, b3Dispatcher* dispatcher);
163 virtual void rayTest(const b3Vector3& rayFrom, const b3Vector3& rayTo, b3BroadphaseRayCallback& rayCallback, const b3Vector3& aabbMin = b3MakeVector3(0, 0, 0), const b3Vector3& aabbMax = b3MakeVector3(0, 0, 0));
164 virtual void aabbTest(const b3Vector3& aabbMin, const b3Vector3& aabbMax, b3BroadphaseAabbCallback& callback);
165
166 //virtual void getAabb(b3BroadphaseProxy* proxy,b3Vector3& aabbMin, b3Vector3& aabbMax ) const;
167 virtual void getAabb(int objectId, b3Vector3& aabbMin, b3Vector3& aabbMax) const;
168 virtual void calculateOverlappingPairs(b3Dispatcher* dispatcher = 0);
169 virtual b3OverlappingPairCache* getOverlappingPairCache();
170 virtual const b3OverlappingPairCache* getOverlappingPairCache() const;
171 virtual void getBroadphaseAabb(b3Vector3& aabbMin, b3Vector3& aabbMax) const;
172 virtual void printStats();
173
174 ///reset broadphase internal structures, to ensure determinism/reproducability
175 virtual void resetPool(b3Dispatcher* dispatcher);
176
177 void performDeferredRemoval(b3Dispatcher* dispatcher);
178
setVelocityPredictionb3DynamicBvhBroadphase179 void setVelocityPrediction(b3Scalar prediction)
180 {
181 m_prediction = prediction;
182 }
getVelocityPredictionb3DynamicBvhBroadphase183 b3Scalar getVelocityPrediction() const
184 {
185 return m_prediction;
186 }
187
188 ///this setAabbForceUpdate is similar to setAabb but always forces the aabb update.
189 ///it is not part of the b3BroadphaseInterface but specific to b3DynamicBvhBroadphase.
190 ///it bypasses certain optimizations that prevent aabb updates (when the aabb shrinks), see
191 ///http://code.google.com/p/bullet/issues/detail?id=223
192 void setAabbForceUpdate(b3BroadphaseProxy* absproxy, const b3Vector3& aabbMin, const b3Vector3& aabbMax, b3Dispatcher* /*dispatcher*/);
193
194 //static void benchmark(b3BroadphaseInterface*);
195 };
196
197 #endif
198