Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: code/branches/physics/src/bullet/BulletCollision/GIMPACT/gim_box_set.h @ 2379

Last change on this file since 2379 was 2192, checked in by rgrieder, 16 years ago

Reverted all changes of attempt to update physics branch.

  • Property svn:eol-style set to native
File size: 16.3 KB
Line 
1#ifndef GIM_BOX_SET_H_INCLUDED
2#define GIM_BOX_SET_H_INCLUDED
3
4/*! \file gim_box_set.h
5\author Francisco Len Nßjera
6*/
7/*
8-----------------------------------------------------------------------------
9This source file is part of GIMPACT Library.
10
11For the latest info, see http://gimpact.sourceforge.net/
12
13Copyright (c) 2006 Francisco Leon Najera. C.C. 80087371.
14email: projectileman@yahoo.com
15
16 This library is free software; you can redistribute it and/or
17 modify it under the terms of EITHER:
18   (1) The GNU Lesser General Public License as published by the Free
19       Software Foundation; either version 2.1 of the License, or (at
20       your option) any later version. The text of the GNU Lesser
21       General Public License is included with this library in the
22       file GIMPACT-LICENSE-LGPL.TXT.
23   (2) The BSD-style license that is included with this library in
24       the file GIMPACT-LICENSE-BSD.TXT.
25   (3) The zlib/libpng license that is included with this library in
26       the file GIMPACT-LICENSE-ZLIB.TXT.
27
28 This library is distributed in the hope that it will be useful,
29 but WITHOUT ANY WARRANTY; without even the implied warranty of
30 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the files
31 GIMPACT-LICENSE-LGPL.TXT, GIMPACT-LICENSE-ZLIB.TXT and GIMPACT-LICENSE-BSD.TXT for more details.
32
33-----------------------------------------------------------------------------
34*/
35
36
37#include "gim_array.h"
38#include "gim_radixsort.h"
39#include "gim_box_collision.h"
40#include "gim_tri_collision.h"
41
42
43/*! \defgroup BOX_PRUNNING
44
45
46
47*/
48//! @{
49
50//! Overlapping pair
51struct GIM_PAIR
52{
53    GUINT m_index1;
54    GUINT m_index2;
55    GIM_PAIR()
56    {}
57
58    GIM_PAIR(const GIM_PAIR & p)
59    {
60        m_index1 = p.m_index1;
61        m_index2 = p.m_index2;
62        }
63
64        GIM_PAIR(GUINT index1, GUINT index2)
65    {
66        m_index1 = index1;
67        m_index2 = index2;
68        }
69};
70
71//! A pairset array
72class gim_pair_set: public gim_array<GIM_PAIR>
73{
74public:
75        gim_pair_set():gim_array<GIM_PAIR>(32)
76        {
77        }
78        inline void push_pair(GUINT index1,GUINT index2)
79        {
80                push_back(GIM_PAIR(index1,index2));
81        }
82
83        inline void push_pair_inv(GUINT index1,GUINT index2)
84        {
85                push_back(GIM_PAIR(index2,index1));
86        }
87};
88
89
90//! Prototype Base class for primitive classification
91/*!
92This class is a wrapper for primitive collections.
93This tells relevant info for the Bounding Box set classes, which take care of space classification.
94This class can manage Compound shapes and trimeshes, and if it is managing trimesh then the  Hierarchy Bounding Box classes will take advantage of primitive Vs Box overlapping tests for getting optimal results and less Per Box compairisons.
95*/
96class GIM_PRIMITIVE_MANAGER_PROTOTYPE
97{
98public:
99
100        //! determines if this manager consist on only triangles, which special case will be optimized
101        virtual bool is_trimesh() = 0;
102        virtual GUINT get_primitive_count() = 0;
103        virtual void get_primitive_box(GUINT prim_index ,GIM_AABB & primbox) = 0;
104        virtual void get_primitive_triangle(GUINT prim_index,GIM_TRIANGLE & triangle) = 0;
105};
106
107
108struct GIM_AABB_DATA
109{
110        GIM_AABB m_bound;
111        GUINT m_data;
112};
113
114//! Node Structure for trees
115struct GIM_BOX_TREE_NODE
116{
117        GIM_AABB m_bound;
118        GUINT m_left;//!< Left subtree
119        GUINT m_right;//!< Right subtree
120        GUINT m_escapeIndex;//!< Scape index for traversing
121        GUINT m_data;//!< primitive index if apply
122
123        GIM_BOX_TREE_NODE()
124        {
125            m_left = 0;
126            m_right = 0;
127            m_escapeIndex = 0;
128            m_data = 0;
129        }
130
131        SIMD_FORCE_INLINE bool is_leaf_node() const
132        {
133            return  (!m_left && !m_right);
134        }
135};
136
137//! Basic Box tree structure
138class GIM_BOX_TREE
139{
140protected:
141        GUINT m_num_nodes;
142        gim_array<GIM_BOX_TREE_NODE> m_node_array;
143protected:
144        GUINT _sort_and_calc_splitting_index(
145                gim_array<GIM_AABB_DATA> & primitive_boxes,
146                 GUINT startIndex,  GUINT endIndex, GUINT splitAxis);
147
148        GUINT _calc_splitting_axis(gim_array<GIM_AABB_DATA> & primitive_boxes, GUINT startIndex,  GUINT endIndex);
149
150        void _build_sub_tree(gim_array<GIM_AABB_DATA> & primitive_boxes, GUINT startIndex,  GUINT endIndex);
151public:
152        GIM_BOX_TREE()
153        {
154                m_num_nodes = 0;
155        }
156
157        //! prototype functions for box tree management
158        //!@{
159        void build_tree(gim_array<GIM_AABB_DATA> & primitive_boxes);
160
161        SIMD_FORCE_INLINE void clearNodes()
162        {
163                m_node_array.clear();
164                m_num_nodes = 0;
165        }
166
167        //! node count
168        SIMD_FORCE_INLINE GUINT getNodeCount() const
169        {
170                return m_num_nodes;
171        }
172
173        //! tells if the node is a leaf
174        SIMD_FORCE_INLINE bool isLeafNode(GUINT nodeindex) const
175        {
176                return m_node_array[nodeindex].is_leaf_node();
177        }
178
179        SIMD_FORCE_INLINE GUINT getNodeData(GUINT nodeindex) const
180        {
181                return m_node_array[nodeindex].m_data;
182        }
183
184        SIMD_FORCE_INLINE void getNodeBound(GUINT nodeindex, GIM_AABB & bound) const
185        {
186                bound = m_node_array[nodeindex].m_bound;
187        }
188
189        SIMD_FORCE_INLINE void setNodeBound(GUINT nodeindex, const GIM_AABB & bound)
190        {
191                m_node_array[nodeindex].m_bound = bound;
192        }
193
194        SIMD_FORCE_INLINE GUINT getLeftNodeIndex(GUINT nodeindex)  const
195        {
196                return m_node_array[nodeindex].m_left;
197        }
198
199        SIMD_FORCE_INLINE GUINT getRightNodeIndex(GUINT nodeindex)  const
200        {
201                return m_node_array[nodeindex].m_right;
202        }
203
204        SIMD_FORCE_INLINE GUINT getScapeNodeIndex(GUINT nodeindex) const
205        {
206                return m_node_array[nodeindex].m_escapeIndex;
207        }
208
209        //!@}
210};
211
212
213//! Generic Box Tree Template
214/*!
215This class offers an structure for managing a box tree of primitives.
216Requires a Primitive prototype (like GIM_PRIMITIVE_MANAGER_PROTOTYPE ) and
217a Box tree structure ( like GIM_BOX_TREE).
218*/
219template<typename _GIM_PRIMITIVE_MANAGER_PROTOTYPE, typename _GIM_BOX_TREE_PROTOTYPE>
220class GIM_BOX_TREE_TEMPLATE_SET
221{
222protected:
223        _GIM_PRIMITIVE_MANAGER_PROTOTYPE m_primitive_manager;
224        _GIM_BOX_TREE_PROTOTYPE m_box_tree;
225protected:
226        //stackless refit
227        SIMD_FORCE_INLINE void refit()
228        {
229                GUINT nodecount = getNodeCount();
230                while(nodecount--)
231                {
232                        if(isLeafNode(nodecount))
233                        {
234                                GIM_AABB leafbox;
235                                m_primitive_manager.get_primitive_box(getNodeData(nodecount),leafbox);
236                                setNodeBound(nodecount,leafbox);
237                        }
238                        else
239                        {
240                                //get left bound
241                                GUINT childindex = getLeftNodeIndex(nodecount);
242                                GIM_AABB bound;
243                                getNodeBound(childindex,bound);
244                                //get right bound
245                                childindex = getRightNodeIndex(nodecount);
246                                GIM_AABB bound2;
247                                getNodeBound(childindex,bound2);
248                                bound.merge(bound2);
249
250                                setNodeBound(nodecount,bound);
251                        }
252                }
253        }
254public:
255
256        GIM_BOX_TREE_TEMPLATE_SET()
257        {
258        }
259
260        SIMD_FORCE_INLINE GIM_AABB getGlobalBox()  const
261        {
262                GIM_AABB totalbox;
263                getNodeBound(0, totalbox);
264                return totalbox;
265        }
266
267        SIMD_FORCE_INLINE void setPrimitiveManager(const _GIM_PRIMITIVE_MANAGER_PROTOTYPE & primitive_manager)
268        {
269                m_primitive_manager = primitive_manager;
270        }
271
272        const _GIM_PRIMITIVE_MANAGER_PROTOTYPE & getPrimitiveManager() const
273        {
274                return m_primitive_manager;
275        }
276
277        _GIM_PRIMITIVE_MANAGER_PROTOTYPE & getPrimitiveManager()
278        {
279                return m_primitive_manager;
280        }
281
282//! node manager prototype functions
283///@{
284
285        //! this attemps to refit the box set.
286        SIMD_FORCE_INLINE void update()
287        {
288                refit();
289        }
290
291        //! this rebuild the entire set
292        SIMD_FORCE_INLINE void buildSet()
293        {
294                //obtain primitive boxes
295                gim_array<GIM_AABB_DATA> primitive_boxes;
296                primitive_boxes.resize(m_primitive_manager.get_primitive_count(),false);
297
298                for (GUINT i = 0;i<primitive_boxes.size() ;i++ )
299                {
300                         m_primitive_manager.get_primitive_box(i,primitive_boxes[i].m_bound);
301                         primitive_boxes[i].m_data = i;
302                }
303
304                m_box_tree.build_tree(primitive_boxes);
305        }
306
307        //! returns the indices of the primitives in the m_primitive_manager
308        SIMD_FORCE_INLINE bool boxQuery(const GIM_AABB & box, gim_array<GUINT> & collided_results) const
309        {
310                GUINT curIndex = 0;
311                GUINT numNodes = getNodeCount();
312
313                while (curIndex < numNodes)
314                {
315                        GIM_AABB bound;
316                        getNodeBound(curIndex,bound);
317
318                        //catch bugs in tree data
319
320                        bool aabbOverlap = bound.has_collision(box);
321                        bool isleafnode = isLeafNode(curIndex);
322
323                        if (isleafnode && aabbOverlap)
324                        {
325                                collided_results.push_back(getNodeData(curIndex));
326                        }
327
328                        if (aabbOverlap || isleafnode)
329                        {
330                                //next subnode
331                                curIndex++;
332                        }
333                        else
334                        {
335                                //skip node
336                                curIndex+= getScapeNodeIndex(curIndex);
337                        }
338                }
339                if(collided_results.size()>0) return true;
340                return false;
341        }
342
343        //! returns the indices of the primitives in the m_primitive_manager
344        SIMD_FORCE_INLINE bool boxQueryTrans(const GIM_AABB & box,
345                 const btTransform & transform, gim_array<GUINT> & collided_results) const
346        {
347                GIM_AABB transbox=box;
348                transbox.appy_transform(transform);
349                return boxQuery(transbox,collided_results);
350        }
351
352        //! returns the indices of the primitives in the m_primitive_manager
353        SIMD_FORCE_INLINE bool rayQuery(
354                const btVector3 & ray_dir,const btVector3 & ray_origin ,
355                gim_array<GUINT> & collided_results) const
356        {
357                GUINT curIndex = 0;
358                GUINT numNodes = getNodeCount();
359
360                while (curIndex < numNodes)
361                {
362                        GIM_AABB bound;
363                        getNodeBound(curIndex,bound);
364
365                        //catch bugs in tree data
366
367                        bool aabbOverlap = bound.collide_ray(ray_origin,ray_dir);
368                        bool isleafnode = isLeafNode(curIndex);
369
370                        if (isleafnode && aabbOverlap)
371                        {
372                                collided_results.push_back(getNodeData( curIndex));
373                        }
374
375                        if (aabbOverlap || isleafnode)
376                        {
377                                //next subnode
378                                curIndex++;
379                        }
380                        else
381                        {
382                                //skip node
383                                curIndex+= getScapeNodeIndex(curIndex);
384                        }
385                }
386                if(collided_results.size()>0) return true;
387                return false;
388        }
389
390        //! tells if this set has hierarcht
391        SIMD_FORCE_INLINE bool hasHierarchy() const
392        {
393                return true;
394        }
395
396        //! tells if this set is a trimesh
397        SIMD_FORCE_INLINE bool isTrimesh()  const
398        {
399                return m_primitive_manager.is_trimesh();
400        }
401
402        //! node count
403        SIMD_FORCE_INLINE GUINT getNodeCount() const
404        {
405                return m_box_tree.getNodeCount();
406        }
407
408        //! tells if the node is a leaf
409        SIMD_FORCE_INLINE bool isLeafNode(GUINT nodeindex) const
410        {
411                return m_box_tree.isLeafNode(nodeindex);
412        }
413
414        SIMD_FORCE_INLINE GUINT getNodeData(GUINT nodeindex) const
415        {
416                return m_box_tree.getNodeData(nodeindex);
417        }
418
419        SIMD_FORCE_INLINE void getNodeBound(GUINT nodeindex, GIM_AABB & bound)  const
420        {
421                m_box_tree.getNodeBound(nodeindex, bound);
422        }
423
424        SIMD_FORCE_INLINE void setNodeBound(GUINT nodeindex, const GIM_AABB & bound)
425        {
426                m_box_tree.setNodeBound(nodeindex, bound);
427        }
428
429        SIMD_FORCE_INLINE GUINT getLeftNodeIndex(GUINT nodeindex) const
430        {
431                return m_box_tree.getLeftNodeIndex(nodeindex);
432        }
433
434        SIMD_FORCE_INLINE GUINT getRightNodeIndex(GUINT nodeindex) const
435        {
436                return m_box_tree.getRightNodeIndex(nodeindex);
437        }
438
439        SIMD_FORCE_INLINE GUINT getScapeNodeIndex(GUINT nodeindex) const
440        {
441                return m_box_tree.getScapeNodeIndex(nodeindex);
442        }
443
444        SIMD_FORCE_INLINE void getNodeTriangle(GUINT nodeindex,GIM_TRIANGLE & triangle) const
445        {
446                m_primitive_manager.get_primitive_triangle(getNodeData(nodeindex),triangle);
447        }
448
449//! @}
450};
451
452//! Class for Box Tree Sets
453/*!
454this has the GIM_BOX_TREE implementation for bounding boxes.
455*/
456template<typename _GIM_PRIMITIVE_MANAGER_PROTOTYPE>
457class GIM_BOX_TREE_SET: public GIM_BOX_TREE_TEMPLATE_SET< _GIM_PRIMITIVE_MANAGER_PROTOTYPE, GIM_BOX_TREE>
458{
459public:
460
461};
462
463
464
465
466
467/// GIM_BOX_SET collision methods
468template<typename BOX_SET_CLASS0,typename BOX_SET_CLASS1>
469class GIM_TREE_TREE_COLLIDER
470{
471public:
472        gim_pair_set * m_collision_pairs;
473        BOX_SET_CLASS0 * m_boxset0;
474        BOX_SET_CLASS1 * m_boxset1;
475        GUINT current_node0;
476        GUINT current_node1;
477        bool node0_is_leaf;
478        bool node1_is_leaf;
479        bool t0_is_trimesh;
480        bool t1_is_trimesh;
481        bool node0_has_triangle;
482        bool node1_has_triangle;
483        GIM_AABB m_box0;
484        GIM_AABB m_box1;
485        GIM_BOX_BOX_TRANSFORM_CACHE trans_cache_1to0;
486        btTransform trans_cache_0to1;
487        GIM_TRIANGLE m_tri0;
488        btVector4 m_tri0_plane;
489        GIM_TRIANGLE m_tri1;
490        btVector4 m_tri1_plane;
491
492
493public:
494        GIM_TREE_TREE_COLLIDER()
495        {
496                current_node0 = G_UINT_INFINITY;
497                current_node1 = G_UINT_INFINITY;
498        }
499protected:
500        SIMD_FORCE_INLINE void retrieve_node0_triangle(GUINT node0)
501        {
502                if(node0_has_triangle) return;
503                m_boxset0->getNodeTriangle(node0,m_tri0);
504                //transform triangle
505                m_tri0.m_vertices[0] = trans_cache_0to1(m_tri0.m_vertices[0]);
506                m_tri0.m_vertices[1] = trans_cache_0to1(m_tri0.m_vertices[1]);
507                m_tri0.m_vertices[2] = trans_cache_0to1(m_tri0.m_vertices[2]);
508                m_tri0.get_plane(m_tri0_plane);
509
510                node0_has_triangle = true;
511        }
512
513        SIMD_FORCE_INLINE void retrieve_node1_triangle(GUINT node1)
514        {
515                if(node1_has_triangle) return;
516                m_boxset1->getNodeTriangle(node1,m_tri1);
517                //transform triangle
518                m_tri1.m_vertices[0] = trans_cache_1to0.transform(m_tri1.m_vertices[0]);
519                m_tri1.m_vertices[1] = trans_cache_1to0.transform(m_tri1.m_vertices[1]);
520                m_tri1.m_vertices[2] = trans_cache_1to0.transform(m_tri1.m_vertices[2]);
521                m_tri1.get_plane(m_tri1_plane);
522
523                node1_has_triangle = true;
524        }
525
526        SIMD_FORCE_INLINE void retrieve_node0_info(GUINT node0)
527        {
528                if(node0 == current_node0) return;
529                m_boxset0->getNodeBound(node0,m_box0);
530                node0_is_leaf = m_boxset0->isLeafNode(node0);
531                node0_has_triangle = false;
532                current_node0 = node0;
533        }
534
535        SIMD_FORCE_INLINE void retrieve_node1_info(GUINT node1)
536        {
537                if(node1 == current_node1) return;
538                m_boxset1->getNodeBound(node1,m_box1);
539                node1_is_leaf = m_boxset1->isLeafNode(node1);
540                node1_has_triangle = false;
541                current_node1 = node1;
542        }
543
544        SIMD_FORCE_INLINE bool node_collision(GUINT node0 ,GUINT node1)
545        {
546                retrieve_node0_info(node0);
547                retrieve_node1_info(node1);
548                bool result = m_box0.overlapping_trans_cache(m_box1,trans_cache_1to0,true);
549                if(!result) return false;
550
551                if(t0_is_trimesh && node0_is_leaf)
552                {
553                        //perform primitive vs box collision
554                        retrieve_node0_triangle(node0);
555                        //do triangle vs box collision
556                        m_box1.increment_margin(m_tri0.m_margin);
557
558                        result = m_box1.collide_triangle_exact(
559                                m_tri0.m_vertices[0],m_tri0.m_vertices[1],m_tri0.m_vertices[2],m_tri0_plane);
560
561                        m_box1.increment_margin(-m_tri0.m_margin);
562
563                        if(!result) return false;
564                        return true;
565                }
566                else if(t1_is_trimesh && node1_is_leaf)
567                {
568                        //perform primitive vs box collision
569                        retrieve_node1_triangle(node1);
570                        //do triangle vs box collision
571                        m_box0.increment_margin(m_tri1.m_margin);
572
573                        result = m_box0.collide_triangle_exact(
574                                m_tri1.m_vertices[0],m_tri1.m_vertices[1],m_tri1.m_vertices[2],m_tri1_plane);
575
576                        m_box0.increment_margin(-m_tri1.m_margin);
577
578                        if(!result) return false;
579                        return true;
580                }
581                return true;
582        }
583
584        //stackless collision routine
585        void find_collision_pairs()
586        {
587                gim_pair_set stack_collisions;
588                stack_collisions.reserve(32);
589
590                //add the first pair
591                stack_collisions.push_pair(0,0);
592
593
594                while(stack_collisions.size())
595                {
596                        //retrieve the last pair and pop
597                        GUINT node0 = stack_collisions.back().m_index1;
598                        GUINT node1 = stack_collisions.back().m_index2;
599                        stack_collisions.pop_back();
600                        if(node_collision(node0,node1)) // a collision is found
601                        {
602                                if(node0_is_leaf)
603                                {
604                                        if(node1_is_leaf)
605                                        {
606                                                m_collision_pairs->push_pair(m_boxset0->getNodeData(node0),m_boxset1->getNodeData(node1));
607                                        }
608                                        else
609                                        {
610                                                //collide left
611                                                stack_collisions.push_pair(node0,m_boxset1->getLeftNodeIndex(node1));
612
613                                                //collide right
614                                                stack_collisions.push_pair(node0,m_boxset1->getRightNodeIndex(node1));
615                                        }
616                                }
617                                else
618                                {
619                                        if(node1_is_leaf)
620                                        {
621                                                //collide left
622                                                stack_collisions.push_pair(m_boxset0->getLeftNodeIndex(node0),node1);
623                                                //collide right
624                                                stack_collisions.push_pair(m_boxset0->getRightNodeIndex(node0),node1);
625                                        }
626                                        else
627                                        {
628                                                GUINT left0 = m_boxset0->getLeftNodeIndex(node0);
629                                                GUINT right0 = m_boxset0->getRightNodeIndex(node0);
630                                                GUINT left1 = m_boxset1->getLeftNodeIndex(node1);
631                                                GUINT right1 = m_boxset1->getRightNodeIndex(node1);
632                                                //collide left
633                                                stack_collisions.push_pair(left0,left1);
634                                                //collide right
635                                                stack_collisions.push_pair(left0,right1);
636                                                //collide left
637                                                stack_collisions.push_pair(right0,left1);
638                                                //collide right
639                                                stack_collisions.push_pair(right0,right1);
640
641                                        }// else if node1 is not a leaf
642                                }// else if node0 is not a leaf
643
644                        }// if(node_collision(node0,node1))
645                }//while(stack_collisions.size())
646        }
647public:
648        void find_collision(BOX_SET_CLASS0 * boxset1, const btTransform & trans1,
649                BOX_SET_CLASS1 * boxset2, const btTransform & trans2,
650                gim_pair_set & collision_pairs, bool complete_primitive_tests = true)
651        {
652                m_collision_pairs = &collision_pairs;
653                m_boxset0 = boxset1;
654                m_boxset1 = boxset2;
655
656                trans_cache_1to0.calc_from_homogenic(trans1,trans2);
657
658                trans_cache_0to1 =  trans2.inverse();
659                trans_cache_0to1 *= trans1;
660
661
662                if(complete_primitive_tests)
663                {
664                        t0_is_trimesh = boxset1->getPrimitiveManager().is_trimesh();
665                        t1_is_trimesh = boxset2->getPrimitiveManager().is_trimesh();
666                }
667                else
668                {
669                        t0_is_trimesh = false;
670                        t1_is_trimesh = false;
671                }
672
673                find_collision_pairs();
674        }
675};
676
677
678#endif // GIM_BOXPRUNING_H_INCLUDED
Note: See TracBrowser for help on using the repository browser.