Fixed a stupid bug when exporting meshes with empty material slots.
[blender.git] / extern / bullet / Bullet / CollisionShapes / OptimizedBvh.cpp
1 /*
2  * Copyright (c) 2006 Erwin Coumans http://continuousphysics.com/Bullet/
3  *
4  * Permission to use, copy, modify, distribute and sell this software
5  * and its documentation for any purpose is hereby granted without fee,
6  * provided that the above copyright notice appear in all copies.
7  * Erwin Coumans makes no representations about the suitability 
8  * of this software for any purpose.  
9  * It is provided "as is" without express or implied warranty.
10 */
11
12 #include "OptimizedBvh.h"
13 #include "StridingMeshInterface.h"
14 #include "AabbUtil2.h"
15
16
17
18 void OptimizedBvh::Build(StridingMeshInterface* triangles)
19 {
20         int countTriangles = 0;
21
22         
23
24         // NodeArray    triangleNodes;
25
26         struct  NodeTriangleCallback : public InternalTriangleIndexCallback
27         {
28                 NodeArray&      m_triangleNodes;
29
30                 NodeTriangleCallback(NodeArray& triangleNodes)
31                         :m_triangleNodes(triangleNodes)
32                 {
33
34                 }
35
36                 virtual void InternalProcessTriangleIndex(SimdVector3* triangle,int partId,int  triangleIndex)
37                 {
38
39                         OptimizedBvhNode node;
40                         node.m_aabbMin = SimdVector3(1e30f,1e30f,1e30f); 
41                         node.m_aabbMax = SimdVector3(-1e30f,-1e30f,-1e30f); 
42                         node.m_aabbMin.setMin(triangle[0]);
43                         node.m_aabbMax.setMax(triangle[0]);
44                         node.m_aabbMin.setMin(triangle[1]);
45                         node.m_aabbMax.setMax(triangle[1]);
46                         node.m_aabbMin.setMin(triangle[2]);
47                         node.m_aabbMax.setMax(triangle[2]);
48
49                         node.m_escapeIndex = -1;
50                         node.m_leftChild = 0;
51                         node.m_rightChild = 0;
52
53
54                         //for child nodes
55                         node.m_subPart = partId;
56                         node.m_triangleIndex = triangleIndex;
57
58                         
59                         m_triangleNodes.push_back(node);
60                 }
61         };
62
63         
64
65         NodeTriangleCallback    callback(m_leafNodes);
66
67         SimdVector3 aabbMin(-1e30f,-1e30f,-1e30f);
68         SimdVector3 aabbMax(1e30f,1e30f,1e30f);
69
70         triangles->InternalProcessAllTriangles(&callback,aabbMin,aabbMax);
71
72         //now we have an array of leafnodes in m_leafNodes
73
74         m_contiguousNodes = new OptimizedBvhNode[2*m_leafNodes.size()];
75         m_curNodeIndex = 0;
76
77         m_rootNode1 = BuildTree(m_leafNodes,0,m_leafNodes.size());
78
79
80         ///create the leafnodes first
81 //      OptimizedBvhNode* leafNodes = new OptimizedBvhNode;
82 }
83
84
85 OptimizedBvhNode*       OptimizedBvh::BuildTree (NodeArray&     leafNodes,int startIndex,int endIndex)
86 {
87         OptimizedBvhNode* internalNode;
88
89         int splitAxis, splitIndex, i;
90         int numIndices =endIndex-startIndex;
91         int curIndex = m_curNodeIndex;
92
93         assert(numIndices>0);
94
95         if (numIndices==1)
96         {
97                 return new (&m_contiguousNodes[m_curNodeIndex++]) OptimizedBvhNode(leafNodes[startIndex]);
98         }
99         //calculate Best Splitting Axis and where to split it. Sort the incoming 'leafNodes' array within range 'startIndex/endIndex'.
100         
101         splitAxis = CalcSplittingAxis(leafNodes,startIndex,endIndex);
102
103         splitIndex = SortAndCalcSplittingIndex(leafNodes,startIndex,endIndex,splitAxis);
104
105         internalNode = &m_contiguousNodes[m_curNodeIndex++];
106         
107         internalNode->m_aabbMax.setValue(-1e30f,-1e30f,-1e30f);
108         internalNode->m_aabbMin.setValue(1e30f,1e30f,1e30f);
109         
110         for (i=startIndex;i<endIndex;i++)
111         {
112                 internalNode->m_aabbMax.setMax(leafNodes[i].m_aabbMax);
113                 internalNode->m_aabbMin.setMin(leafNodes[i].m_aabbMin);
114         }
115
116         
117
118         //internalNode->m_escapeIndex;
119         internalNode->m_leftChild = BuildTree(leafNodes,startIndex,splitIndex);
120         internalNode->m_rightChild = BuildTree(leafNodes,splitIndex,endIndex);
121
122         internalNode->m_escapeIndex  = m_curNodeIndex - curIndex;
123         return internalNode;
124 }
125
126 int     OptimizedBvh::SortAndCalcSplittingIndex(NodeArray&      leafNodes,int startIndex,int endIndex,int splitAxis)
127 {
128         int i;
129         int splitIndex =startIndex;
130         int numIndices = endIndex - startIndex;
131         float splitValue;
132
133         SimdVector3 means(0.f,0.f,0.f);
134         for (i=startIndex;i<endIndex;i++)
135         {
136                 SimdVector3 center = 0.5f*(leafNodes[i].m_aabbMax+leafNodes[i].m_aabbMin);
137                 means+=center;
138         }
139         means *= (1.f/(float)numIndices);
140         
141         splitValue = means[splitAxis];
142         
143         //sort leafNodes so all values larger then splitValue comes first, and smaller values start from 'splitIndex'.
144         for (i=startIndex;i<endIndex;i++)
145         {
146                 SimdVector3 center = 0.5f*(leafNodes[i].m_aabbMax+leafNodes[i].m_aabbMin);
147                 if (center[splitAxis] > splitValue)
148                 {
149                         //swap
150                         OptimizedBvhNode tmp = leafNodes[i];
151                         leafNodes[i] = leafNodes[splitIndex];
152                         leafNodes[splitIndex] = tmp;
153                         splitIndex++;
154                 }
155         }
156         if ((splitIndex==startIndex) || (splitIndex == (endIndex-1)))
157         {
158                 splitIndex = startIndex+ (numIndices>>1);
159         }
160         return splitIndex;
161 }
162
163
164 int     OptimizedBvh::CalcSplittingAxis(NodeArray&      leafNodes,int startIndex,int endIndex)
165 {
166         int i;
167
168         SimdVector3 means(0.f,0.f,0.f);
169         SimdVector3 variance(0.f,0.f,0.f);
170         int numIndices = endIndex-startIndex;
171
172         for (i=startIndex;i<endIndex;i++)
173         {
174                 SimdVector3 center = 0.5f*(leafNodes[i].m_aabbMax+leafNodes[i].m_aabbMin);
175                 means+=center;
176         }
177         means *= (1.f/(float)numIndices);
178                 
179         for (i=startIndex;i<endIndex;i++)
180         {
181                 SimdVector3 center = 0.5f*(leafNodes[i].m_aabbMax+leafNodes[i].m_aabbMin);
182                 SimdVector3 diff2 = center-means;
183                 diff2 = diff2 * diff2;
184                 variance += diff2;
185         }
186         variance *= (1.f/       ((float)numIndices-1)   );
187         
188         return variance.maxAxis();
189 }
190
191
192         
193 void    OptimizedBvh::ReportAabbOverlappingNodex(NodeOverlapCallback* nodeCallback,const SimdVector3& aabbMin,const SimdVector3& aabbMax) const
194 {
195         int i;
196
197         if (aabbMin.length() > 1000.f)
198         {
199                 for (i=0;i<m_leafNodes.size();i++)
200                 {
201                         const OptimizedBvhNode& node = m_leafNodes[i];
202                         nodeCallback->ProcessNode(&node);
203                 }
204         } else
205         {
206                 //WalkTree(m_rootNode1,nodeCallback,aabbMin,aabbMax);
207                 WalkStacklessTree(m_rootNode1,nodeCallback,aabbMin,aabbMax);
208         }
209 }
210
211 void    OptimizedBvh::WalkTree(OptimizedBvhNode* rootNode,NodeOverlapCallback* nodeCallback,const SimdVector3& aabbMin,const SimdVector3& aabbMax) const
212 {
213         bool isLeafNode, aabbOverlap = TestAabbAgainstAabb2(aabbMin,aabbMax,rootNode->m_aabbMin,rootNode->m_aabbMax);
214         if (aabbOverlap)
215         {
216                 isLeafNode = (!rootNode->m_leftChild && !rootNode->m_rightChild);
217                 if (isLeafNode)
218                 {
219                         nodeCallback->ProcessNode(rootNode);
220                 } else
221                 {
222                         WalkTree(rootNode->m_leftChild,nodeCallback,aabbMin,aabbMax);
223                         WalkTree(rootNode->m_rightChild,nodeCallback,aabbMin,aabbMax);
224                 }
225         }
226
227 }
228
229 int maxIterations = 0;
230
231 void    OptimizedBvh::WalkStacklessTree(OptimizedBvhNode* rootNode,NodeOverlapCallback* nodeCallback,const SimdVector3& aabbMin,const SimdVector3& aabbMax) const
232 {
233         int escapeIndex, curIndex = 0;
234         int walkIterations = 0;
235         bool aabbOverlap, isLeafNode;
236
237         while (curIndex < m_curNodeIndex)
238         {
239                 //catch bugs in tree data
240                 assert (walkIterations < m_curNodeIndex);
241
242                 walkIterations++;
243                 aabbOverlap = TestAabbAgainstAabb2(aabbMin,aabbMax,rootNode->m_aabbMin,rootNode->m_aabbMax);
244                 isLeafNode = (!rootNode->m_leftChild && !rootNode->m_rightChild);
245                 
246                 if (isLeafNode && aabbOverlap)
247                 {
248                         nodeCallback->ProcessNode(rootNode);
249                 } 
250                 
251                 if (aabbOverlap || isLeafNode)
252                 {
253                         rootNode++;
254                         curIndex++;
255                 } else
256                 {
257                         escapeIndex = rootNode->m_escapeIndex;
258                         rootNode += escapeIndex;
259                         curIndex += escapeIndex;
260                 }
261                 
262         }
263
264         if (maxIterations < walkIterations)
265                 maxIterations = walkIterations;
266
267 }
268
269
270 void    OptimizedBvh::ReportSphereOverlappingNodex(NodeOverlapCallback* nodeCallback,const SimdVector3& aabbMin,const SimdVector3& aabbMax) const
271 {
272
273 }
274