• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 #ifndef GIM_QUANTIZED_SET_H_INCLUDED
2 #define GIM_QUANTIZED_SET_H_INCLUDED
3 
4 /*! \file btGImpactQuantizedBvh.h
5 \author Francisco Leon Najera
6 */
7 /*
8 This source file is part of GIMPACT Library.
9 
10 For the latest info, see http://gimpact.sourceforge.net/
11 
12 Copyright (c) 2007 Francisco Leon Najera. C.C. 80087371.
13 email: projectileman@yahoo.com
14 
15 
16 This software is provided 'as-is', without any express or implied warranty.
17 In no event will the authors be held liable for any damages arising from the use of this software.
18 Permission is granted to anyone to use this software for any purpose,
19 including commercial applications, and to alter it and redistribute it freely,
20 subject to the following restrictions:
21 
22 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.
23 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
24 3. This notice may not be removed or altered from any source distribution.
25 */
26 
27 #include "btGImpactBvh.h"
28 #include "btQuantization.h"
29 
30 
31 
32 
33 
34 ///btQuantizedBvhNode is a compressed aabb node, 16 bytes.
35 ///Node can be used for leafnode or internal node. Leafnodes can point to 32-bit triangle index (non-negative range).
ATTRIBUTE_ALIGNED16(struct)36 ATTRIBUTE_ALIGNED16	(struct) BT_QUANTIZED_BVH_NODE
37 {
38 	//12 bytes
39 	unsigned short int	m_quantizedAabbMin[3];
40 	unsigned short int	m_quantizedAabbMax[3];
41 	//4 bytes
42 	int	m_escapeIndexOrDataIndex;
43 
44 	BT_QUANTIZED_BVH_NODE()
45 	{
46 		m_escapeIndexOrDataIndex = 0;
47 	}
48 
49 	SIMD_FORCE_INLINE bool isLeafNode() const
50 	{
51 		//skipindex is negative (internal node), triangleindex >=0 (leafnode)
52 		return (m_escapeIndexOrDataIndex>=0);
53 	}
54 
55 	SIMD_FORCE_INLINE int getEscapeIndex() const
56 	{
57 		//btAssert(m_escapeIndexOrDataIndex < 0);
58 		return -m_escapeIndexOrDataIndex;
59 	}
60 
61 	SIMD_FORCE_INLINE void setEscapeIndex(int index)
62 	{
63 		m_escapeIndexOrDataIndex = -index;
64 	}
65 
66 	SIMD_FORCE_INLINE int getDataIndex() const
67 	{
68 		//btAssert(m_escapeIndexOrDataIndex >= 0);
69 
70 		return m_escapeIndexOrDataIndex;
71 	}
72 
73 	SIMD_FORCE_INLINE void setDataIndex(int index)
74 	{
75 		m_escapeIndexOrDataIndex = index;
76 	}
77 
78 	SIMD_FORCE_INLINE bool testQuantizedBoxOverlapp(
79 		unsigned short * quantizedMin,unsigned short * quantizedMax) const
80 	{
81 		if(m_quantizedAabbMin[0] > quantizedMax[0] ||
82 		   m_quantizedAabbMax[0] < quantizedMin[0] ||
83 		   m_quantizedAabbMin[1] > quantizedMax[1] ||
84 		   m_quantizedAabbMax[1] < quantizedMin[1] ||
85 		   m_quantizedAabbMin[2] > quantizedMax[2] ||
86 		   m_quantizedAabbMax[2] < quantizedMin[2])
87 		{
88 			return false;
89 		}
90 		return true;
91 	}
92 
93 };
94 
95 
96 
97 class GIM_QUANTIZED_BVH_NODE_ARRAY:public btAlignedObjectArray<BT_QUANTIZED_BVH_NODE>
98 {
99 };
100 
101 
102 
103 
104 //! Basic Box tree structure
105 class btQuantizedBvhTree
106 {
107 protected:
108 	int m_num_nodes;
109 	GIM_QUANTIZED_BVH_NODE_ARRAY m_node_array;
110 	btAABB m_global_bound;
111 	btVector3 m_bvhQuantization;
112 protected:
113 	void calc_quantization(GIM_BVH_DATA_ARRAY & primitive_boxes, btScalar boundMargin = btScalar(1.0) );
114 
115 	int _sort_and_calc_splitting_index(
116 		GIM_BVH_DATA_ARRAY & primitive_boxes,
117 		 int startIndex,  int endIndex, int splitAxis);
118 
119 	int _calc_splitting_axis(GIM_BVH_DATA_ARRAY & primitive_boxes, int startIndex,  int endIndex);
120 
121 	void _build_sub_tree(GIM_BVH_DATA_ARRAY & primitive_boxes, int startIndex,  int endIndex);
122 public:
btQuantizedBvhTree()123 	btQuantizedBvhTree()
124 	{
125 		m_num_nodes = 0;
126 	}
127 
128 	//! prototype functions for box tree management
129 	//!@{
130 	void build_tree(GIM_BVH_DATA_ARRAY & primitive_boxes);
131 
quantizePoint(unsigned short * quantizedpoint,const btVector3 & point)132 	SIMD_FORCE_INLINE void quantizePoint(
133 		unsigned short * quantizedpoint, const btVector3 & point) const
134 	{
135 		bt_quantize_clamp(quantizedpoint,point,m_global_bound.m_min,m_global_bound.m_max,m_bvhQuantization);
136 	}
137 
138 
testQuantizedBoxOverlapp(int node_index,unsigned short * quantizedMin,unsigned short * quantizedMax)139 	SIMD_FORCE_INLINE bool testQuantizedBoxOverlapp(
140 		int node_index,
141 		unsigned short * quantizedMin,unsigned short * quantizedMax) const
142 	{
143 		return m_node_array[node_index].testQuantizedBoxOverlapp(quantizedMin,quantizedMax);
144 	}
145 
clearNodes()146 	SIMD_FORCE_INLINE void clearNodes()
147 	{
148 		m_node_array.clear();
149 		m_num_nodes = 0;
150 	}
151 
152 	//! node count
getNodeCount()153 	SIMD_FORCE_INLINE int getNodeCount() const
154 	{
155 		return m_num_nodes;
156 	}
157 
158 	//! tells if the node is a leaf
isLeafNode(int nodeindex)159 	SIMD_FORCE_INLINE bool isLeafNode(int nodeindex) const
160 	{
161 		return m_node_array[nodeindex].isLeafNode();
162 	}
163 
getNodeData(int nodeindex)164 	SIMD_FORCE_INLINE int getNodeData(int nodeindex) const
165 	{
166 		return m_node_array[nodeindex].getDataIndex();
167 	}
168 
getNodeBound(int nodeindex,btAABB & bound)169 	SIMD_FORCE_INLINE void getNodeBound(int nodeindex, btAABB & bound) const
170 	{
171 		bound.m_min = bt_unquantize(
172 			m_node_array[nodeindex].m_quantizedAabbMin,
173 			m_global_bound.m_min,m_bvhQuantization);
174 
175 		bound.m_max = bt_unquantize(
176 			m_node_array[nodeindex].m_quantizedAabbMax,
177 			m_global_bound.m_min,m_bvhQuantization);
178 	}
179 
setNodeBound(int nodeindex,const btAABB & bound)180 	SIMD_FORCE_INLINE void setNodeBound(int nodeindex, const btAABB & bound)
181 	{
182 		bt_quantize_clamp(	m_node_array[nodeindex].m_quantizedAabbMin,
183 							bound.m_min,
184 							m_global_bound.m_min,
185 							m_global_bound.m_max,
186 							m_bvhQuantization);
187 
188 		bt_quantize_clamp(	m_node_array[nodeindex].m_quantizedAabbMax,
189 							bound.m_max,
190 							m_global_bound.m_min,
191 							m_global_bound.m_max,
192 							m_bvhQuantization);
193 	}
194 
getLeftNode(int nodeindex)195 	SIMD_FORCE_INLINE int getLeftNode(int nodeindex) const
196 	{
197 		return nodeindex+1;
198 	}
199 
getRightNode(int nodeindex)200 	SIMD_FORCE_INLINE int getRightNode(int nodeindex) const
201 	{
202 		if(m_node_array[nodeindex+1].isLeafNode()) return nodeindex+2;
203 		return nodeindex+1 + m_node_array[nodeindex+1].getEscapeIndex();
204 	}
205 
getEscapeNodeIndex(int nodeindex)206 	SIMD_FORCE_INLINE int getEscapeNodeIndex(int nodeindex) const
207 	{
208 		return m_node_array[nodeindex].getEscapeIndex();
209 	}
210 
211 	SIMD_FORCE_INLINE const BT_QUANTIZED_BVH_NODE * get_node_pointer(int index = 0) const
212 	{
213 		return &m_node_array[index];
214 	}
215 
216 	//!@}
217 };
218 
219 
220 
221 //! Structure for containing Boxes
222 /*!
223 This class offers an structure for managing a box tree of primitives.
224 Requires a Primitive prototype (like btPrimitiveManagerBase )
225 */
226 class btGImpactQuantizedBvh
227 {
228 protected:
229 	btQuantizedBvhTree m_box_tree;
230 	btPrimitiveManagerBase * m_primitive_manager;
231 
232 protected:
233 	//stackless refit
234 	void refit();
235 public:
236 
237 	//! this constructor doesn't build the tree. you must call	buildSet
btGImpactQuantizedBvh()238 	btGImpactQuantizedBvh()
239 	{
240 		m_primitive_manager = NULL;
241 	}
242 
243 	//! this constructor doesn't build the tree. you must call	buildSet
btGImpactQuantizedBvh(btPrimitiveManagerBase * primitive_manager)244 	btGImpactQuantizedBvh(btPrimitiveManagerBase * primitive_manager)
245 	{
246 		m_primitive_manager = primitive_manager;
247 	}
248 
getGlobalBox()249 	SIMD_FORCE_INLINE btAABB getGlobalBox()  const
250 	{
251 		btAABB totalbox;
252 		getNodeBound(0, totalbox);
253 		return totalbox;
254 	}
255 
setPrimitiveManager(btPrimitiveManagerBase * primitive_manager)256 	SIMD_FORCE_INLINE void setPrimitiveManager(btPrimitiveManagerBase * primitive_manager)
257 	{
258 		m_primitive_manager = primitive_manager;
259 	}
260 
getPrimitiveManager()261 	SIMD_FORCE_INLINE btPrimitiveManagerBase * getPrimitiveManager() const
262 	{
263 		return m_primitive_manager;
264 	}
265 
266 
267 //! node manager prototype functions
268 ///@{
269 
270 	//! this attemps to refit the box set.
update()271 	SIMD_FORCE_INLINE void update()
272 	{
273 		refit();
274 	}
275 
276 	//! this rebuild the entire set
277 	void buildSet();
278 
279 	//! returns the indices of the primitives in the m_primitive_manager
280 	bool boxQuery(const btAABB & box, btAlignedObjectArray<int> & collided_results) const;
281 
282 	//! returns the indices of the primitives in the m_primitive_manager
boxQueryTrans(const btAABB & box,const btTransform & transform,btAlignedObjectArray<int> & collided_results)283 	SIMD_FORCE_INLINE bool boxQueryTrans(const btAABB & box,
284 		 const btTransform & transform, btAlignedObjectArray<int> & collided_results) const
285 	{
286 		btAABB transbox=box;
287 		transbox.appy_transform(transform);
288 		return boxQuery(transbox,collided_results);
289 	}
290 
291 	//! returns the indices of the primitives in the m_primitive_manager
292 	bool rayQuery(
293 		const btVector3 & ray_dir,const btVector3 & ray_origin ,
294 		btAlignedObjectArray<int> & collided_results) const;
295 
296 	//! tells if this set has hierarcht
hasHierarchy()297 	SIMD_FORCE_INLINE bool hasHierarchy() const
298 	{
299 		return true;
300 	}
301 
302 	//! tells if this set is a trimesh
isTrimesh()303 	SIMD_FORCE_INLINE bool isTrimesh()  const
304 	{
305 		return m_primitive_manager->is_trimesh();
306 	}
307 
308 	//! node count
getNodeCount()309 	SIMD_FORCE_INLINE int getNodeCount() const
310 	{
311 		return m_box_tree.getNodeCount();
312 	}
313 
314 	//! tells if the node is a leaf
isLeafNode(int nodeindex)315 	SIMD_FORCE_INLINE bool isLeafNode(int nodeindex) const
316 	{
317 		return m_box_tree.isLeafNode(nodeindex);
318 	}
319 
getNodeData(int nodeindex)320 	SIMD_FORCE_INLINE int getNodeData(int nodeindex) const
321 	{
322 		return m_box_tree.getNodeData(nodeindex);
323 	}
324 
getNodeBound(int nodeindex,btAABB & bound)325 	SIMD_FORCE_INLINE void getNodeBound(int nodeindex, btAABB & bound)  const
326 	{
327 		m_box_tree.getNodeBound(nodeindex, bound);
328 	}
329 
setNodeBound(int nodeindex,const btAABB & bound)330 	SIMD_FORCE_INLINE void setNodeBound(int nodeindex, const btAABB & bound)
331 	{
332 		m_box_tree.setNodeBound(nodeindex, bound);
333 	}
334 
335 
getLeftNode(int nodeindex)336 	SIMD_FORCE_INLINE int getLeftNode(int nodeindex) const
337 	{
338 		return m_box_tree.getLeftNode(nodeindex);
339 	}
340 
getRightNode(int nodeindex)341 	SIMD_FORCE_INLINE int getRightNode(int nodeindex) const
342 	{
343 		return m_box_tree.getRightNode(nodeindex);
344 	}
345 
getEscapeNodeIndex(int nodeindex)346 	SIMD_FORCE_INLINE int getEscapeNodeIndex(int nodeindex) const
347 	{
348 		return m_box_tree.getEscapeNodeIndex(nodeindex);
349 	}
350 
getNodeTriangle(int nodeindex,btPrimitiveTriangle & triangle)351 	SIMD_FORCE_INLINE void getNodeTriangle(int nodeindex,btPrimitiveTriangle & triangle) const
352 	{
353 		m_primitive_manager->get_primitive_triangle(getNodeData(nodeindex),triangle);
354 	}
355 
356 
357 	SIMD_FORCE_INLINE const BT_QUANTIZED_BVH_NODE * get_node_pointer(int index = 0) const
358 	{
359 		return m_box_tree.get_node_pointer(index);
360 	}
361 
362 #ifdef TRI_COLLISION_PROFILING
363 	static float getAverageTreeCollisionTime();
364 #endif //TRI_COLLISION_PROFILING
365 
366 	static void find_collision(const btGImpactQuantizedBvh * boxset1, const btTransform & trans1,
367 		const btGImpactQuantizedBvh * boxset2, const btTransform & trans2,
368 		btPairSet & collision_pairs);
369 };
370 
371 
372 #endif // GIM_BOXPRUNING_H_INCLUDED
373