← Back to branch summary

~ubuntu-branches/ubuntu/vivid/emscripten/vivid

« back to all changes in this revision

Viewing changes to tests/bullet/src/BulletCollision/Gimpact/gim_box_set.cpp

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2013-05-02 13:11:51 UTC
  • Revision ID: package-import@ubuntu.com-20130502131151-q8dvteqr1ef2x7xz
Tags: upstream-1.4.1~20130504~adb56cb
Import upstream version 1.4.1~20130504~adb56cb

Show diffs side-by-side

added added

removed removed

Lines of Context:
tests/bullet/src/BulletCollision/Gimpact/gim_box_set.cpp
 
1
 
 
2
/*
 
3
-----------------------------------------------------------------------------
 
4
This source file is part of GIMPACT Library.
 
5
 
 
6
For the latest info, see http://gimpact.sourceforge.net/
 
7
 
 
8
Copyright (c) 2006 Francisco Leon Najera. C.C. 80087371.
 
9
email: 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
 
 
35
GUINT 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
 
 
66
GUINT 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
 
 
119
void 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
 
171
void 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