Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: code/trunk/src/external/bullet/BulletCollision/Gimpact/gim_box_set.cpp @ 8066

Last change on this file since 8066 was 5781, checked in by rgrieder, 15 years ago

Reverted trunk again. We might want to find a way to delete these revisions again (x3n's changes are still available as diff in the commit mails).

  • Property svn:eol-style set to native
File size: 5.6 KB
Line 
1
2/*
3-----------------------------------------------------------------------------
4This source file is part of GIMPACT Library.
5
6For the latest info, see http://gimpact.sourceforge.net/
7
8Copyright (c) 2006 Francisco Leon Najera. C.C. 80087371.
9email: projectileman@yahoo.com
10
11 This library is free software; you can redistribute it and/or
12 modify it under the terms of EITHER:
13   (1) The GNU Lesser General Public License as published by the Free
14       Software Foundation; either version 2.1 of the License, or (at
15       your option) any later version. The text of the GNU Lesser
16       General Public License is included with this library in the
17       file GIMPACT-LICENSE-LGPL.TXT.
18   (2) The BSD-style license that is included with this library in
19       the file GIMPACT-LICENSE-BSD.TXT.
20   (3) The zlib/libpng license that is included with this library in
21       the file GIMPACT-LICENSE-ZLIB.TXT.
22
23 This library is distributed in the hope that it will be useful,
24 but WITHOUT ANY WARRANTY; without even the implied warranty of
25 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the files
26 GIMPACT-LICENSE-LGPL.TXT, GIMPACT-LICENSE-ZLIB.TXT and GIMPACT-LICENSE-BSD.TXT for more details.
27
28-----------------------------------------------------------------------------
29*/
30
31
32#include "gim_box_set.h"
33
34
35GUINT GIM_BOX_TREE::_calc_splitting_axis(
36        gim_array<GIM_AABB_DATA> & primitive_boxes, GUINT startIndex,  GUINT endIndex)
37{
38        GUINT i;
39
40        btVector3 means(btScalar(0.),btScalar(0.),btScalar(0.));
41        btVector3 variance(btScalar(0.),btScalar(0.),btScalar(0.));
42        GUINT numIndices = endIndex-startIndex;
43
44        for (i=startIndex;i<endIndex;i++)
45        {
46                btVector3 center = btScalar(0.5)*(primitive_boxes[i].m_bound.m_max +
47                                         primitive_boxes[i].m_bound.m_min);
48                means+=center;
49        }
50        means *= (btScalar(1.)/(btScalar)numIndices);
51
52        for (i=startIndex;i<endIndex;i++)
53        {
54                btVector3 center = btScalar(0.5)*(primitive_boxes[i].m_bound.m_max +
55                                         primitive_boxes[i].m_bound.m_min);
56                btVector3 diff2 = center-means;
57                diff2 = diff2 * diff2;
58                variance += diff2;
59        }
60        variance *= (btScalar(1.)/      ((btScalar)numIndices-1)        );
61
62        return variance.maxAxis();
63}
64
65
66GUINT GIM_BOX_TREE::_sort_and_calc_splitting_index(
67        gim_array<GIM_AABB_DATA> & primitive_boxes, GUINT startIndex,
68        GUINT endIndex, GUINT splitAxis)
69{
70        GUINT i;
71        GUINT splitIndex =startIndex;
72        GUINT numIndices = endIndex - startIndex;
73
74        // average of centers
75        btScalar splitValue = 0.0f;
76        for (i=startIndex;i<endIndex;i++)
77        {
78                splitValue+= 0.5f*(primitive_boxes[i].m_bound.m_max[splitAxis] +
79                                         primitive_boxes[i].m_bound.m_min[splitAxis]);
80        }
81        splitValue /= (btScalar)numIndices;
82
83        //sort leafNodes so all values larger then splitValue comes first, and smaller values start from 'splitIndex'.
84        for (i=startIndex;i<endIndex;i++)
85        {
86                btScalar center = 0.5f*(primitive_boxes[i].m_bound.m_max[splitAxis] +
87                                         primitive_boxes[i].m_bound.m_min[splitAxis]);
88                if (center > splitValue)
89                {
90                        //swap
91                        primitive_boxes.swap(i,splitIndex);
92                        splitIndex++;
93                }
94        }
95
96        //if the splitIndex causes unbalanced trees, fix this by using the center in between startIndex and endIndex
97        //otherwise the tree-building might fail due to stack-overflows in certain cases.
98        //unbalanced1 is unsafe: it can cause stack overflows
99        //bool unbalanced1 = ((splitIndex==startIndex) || (splitIndex == (endIndex-1)));
100
101        //unbalanced2 should work too: always use center (perfect balanced trees)
102        //bool unbalanced2 = true;
103
104        //this should be safe too:
105        GUINT rangeBalancedIndices = numIndices/3;
106        bool unbalanced = ((splitIndex<=(startIndex+rangeBalancedIndices)) || (splitIndex >=(endIndex-1-rangeBalancedIndices)));
107
108        if (unbalanced)
109        {
110                splitIndex = startIndex+ (numIndices>>1);
111        }
112
113        btAssert(!((splitIndex==startIndex) || (splitIndex == (endIndex))));
114
115        return splitIndex;
116}
117
118
119void GIM_BOX_TREE::_build_sub_tree(gim_array<GIM_AABB_DATA> & primitive_boxes, GUINT startIndex,  GUINT endIndex)
120{
121        GUINT current_index = m_num_nodes++;
122
123        btAssert((endIndex-startIndex)>0);
124
125        if((endIndex-startIndex) == 1) //we got a leaf
126        {               
127                m_node_array[current_index].m_left = 0;
128                m_node_array[current_index].m_right = 0;
129                m_node_array[current_index].m_escapeIndex = 0;
130
131                m_node_array[current_index].m_bound = primitive_boxes[startIndex].m_bound;
132                m_node_array[current_index].m_data = primitive_boxes[startIndex].m_data;
133                return;
134        }
135
136        //configure inner node
137
138        GUINT splitIndex;
139
140        //calc this node bounding box
141        m_node_array[current_index].m_bound.invalidate();       
142        for (splitIndex=startIndex;splitIndex<endIndex;splitIndex++)
143        {
144                m_node_array[current_index].m_bound.merge(primitive_boxes[splitIndex].m_bound);
145        }
146
147        //calculate Best Splitting Axis and where to split it. Sort the incoming 'leafNodes' array within range 'startIndex/endIndex'.
148
149        //split axis
150        splitIndex = _calc_splitting_axis(primitive_boxes,startIndex,endIndex);
151
152        splitIndex = _sort_and_calc_splitting_index(
153                        primitive_boxes,startIndex,endIndex,splitIndex);
154
155        //configure this inner node : the left node index
156        m_node_array[current_index].m_left = m_num_nodes;
157        //build left child tree
158        _build_sub_tree(primitive_boxes, startIndex, splitIndex );
159
160        //configure this inner node : the right node index
161        m_node_array[current_index].m_right = m_num_nodes;
162
163        //build right child tree
164        _build_sub_tree(primitive_boxes, splitIndex ,endIndex);
165
166        //configure this inner node : the escape index
167        m_node_array[current_index].m_escapeIndex  = m_num_nodes - current_index;
168}
169
170//! stackless build tree
171void GIM_BOX_TREE::build_tree(
172        gim_array<GIM_AABB_DATA> & primitive_boxes)
173{
174        // initialize node count to 0
175        m_num_nodes = 0;
176        // allocate nodes
177        m_node_array.resize(primitive_boxes.size()*2);
178       
179        _build_sub_tree(primitive_boxes, 0, primitive_boxes.size());
180}
181
182
Note: See TracBrowser for help on using the repository browser.