Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: code/branches/ode/ode-0.9/OPCODE/OPC_TreeBuilders.cpp @ 216

Last change on this file since 216 was 216, checked in by mathiask, 16 years ago

[Physik] add ode-0.9
File size: 11.6 KB
Line 
1///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
2/*
3 *      OPCODE - Optimized Collision Detection
4 *      Copyright (C) 2001 Pierre Terdiman
5 *      Homepage: http://www.codercorner.com/Opcode.htm
6 */
7///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
8
9///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
10/**
11 *      Contains code for tree builders.
12 *      \file           OPC_TreeBuilders.cpp
13 *      \author         Pierre Terdiman
14 *      \date           March, 20, 2001
15 */
16///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
17
18///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
19/**
20 *      A builder for AABB-trees of vertices.
21 *
22 *      \class          AABBTreeOfVerticesBuilder
23 *      \author         Pierre Terdiman
24 *      \version        1.3
25 *      \date           March, 20, 2001
26*/
27///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
28
29///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
30/**
31 *      A builder for AABB-trees of AABBs.
32 *
33 *      \class          AABBTreeOfAABBsBuilder
34 *      \author         Pierre Terdiman
35 *      \version        1.3
36 *      \date           March, 20, 2001
37*/
38///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
39
40///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
41/**
42 *      A builder for AABB-trees of triangles.
43 *
44 *      \class          AABBTreeOfTrianglesBuilder
45 *      \author         Pierre Terdiman
46 *      \version        1.3
47 *      \date           March, 20, 2001
48*/
49///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
50
51///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
52// Precompiled Header
53#include "Stdafx.h"
54
55using namespace Opcode;
56
57///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
58/**
59 *      Computes the AABB of a set of primitives.
60 *      \param          primitives              [in] list of indices of primitives
61 *      \param          nb_prims                [in] number of indices
62 *      \param          global_box              [out] global AABB enclosing the set of input primitives
63 *      \return         true if success
64 */
65///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
66bool AABBTreeOfAABBsBuilder::ComputeGlobalBox(const udword* primitives, udword nb_prims, AABB& global_box) const
67{
68        // Checkings
69        if(!primitives || !nb_prims)    return false;
70
71        // Initialize global box
72        global_box = mAABBArray[primitives[0]];
73
74        // Loop through boxes
75        for(udword i=1;i<nb_prims;i++)
76        {
77                // Update global box
78                global_box.Add(mAABBArray[primitives[i]]);
79        }
80        return true;
81}
82
83///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
84/**
85 *      Computes the splitting value along a given axis for a given primitive.
86 *      \param          index           [in] index of the primitive to split
87 *      \param          axis            [in] axis index (0,1,2)
88 *      \return         splitting value
89 */
90///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
91float AABBTreeOfAABBsBuilder::GetSplittingValue(udword index, udword axis) const
92{
93        // For an AABB, the splitting value is the middle of the given axis,
94        // i.e. the corresponding component of the center point
95        return mAABBArray[index].GetCenter(axis);
96}
97
98///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
99/**
100 *      Computes the AABB of a set of primitives.
101 *      \param          primitives              [in] list of indices of primitives
102 *      \param          nb_prims                [in] number of indices
103 *      \param          global_box              [out] global AABB enclosing the set of input primitives
104 *      \return         true if success
105 */
106///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
107bool AABBTreeOfTrianglesBuilder::ComputeGlobalBox(const udword* primitives, udword nb_prims, AABB& global_box) const
108{
109        // Checkings
110        if(!primitives || !nb_prims)    return false;
111
112        // Initialize global box
113        Point Min(MAX_FLOAT, MAX_FLOAT, MAX_FLOAT);
114        Point Max(MIN_FLOAT, MIN_FLOAT, MIN_FLOAT);
115
116        // Loop through triangles
117        VertexPointers VP;
118        while(nb_prims--)
119        {
120                // Get current triangle-vertices
121                mIMesh->GetTriangle(VP, *primitives++);
122                // Update global box
123                Min.Min(*VP.Vertex[0]).Min(*VP.Vertex[1]).Min(*VP.Vertex[2]);
124                Max.Max(*VP.Vertex[0]).Max(*VP.Vertex[1]).Max(*VP.Vertex[2]);
125        }
126        global_box.SetMinMax(Min, Max);
127        return true;
128}
129
130///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
131/**
132 *      Computes the splitting value along a given axis for a given primitive.
133 *      \param          index           [in] index of the primitive to split
134 *      \param          axis            [in] axis index (0,1,2)
135 *      \return         splitting value
136 */
137///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
138float AABBTreeOfTrianglesBuilder::GetSplittingValue(udword index, udword axis) const
139{
140/*      // Compute center of triangle
141        Point Center;
142        mTriList[index].Center(mVerts, Center);
143        // Return value
144        return Center[axis];*/
145
146        // Compute correct component from center of triangle
147//      return  (mVerts[mTriList[index].mVRef[0]][axis]
148//                      +mVerts[mTriList[index].mVRef[1]][axis]
149//                      +mVerts[mTriList[index].mVRef[2]][axis])*INV3;
150
151        VertexPointers VP;
152        mIMesh->GetTriangle(VP, index);
153
154        // Compute correct component from center of triangle
155        return  ((*VP.Vertex[0])[axis]
156                        +(*VP.Vertex[1])[axis]
157                        +(*VP.Vertex[2])[axis])*INV3;
158}
159
160///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
161/**
162 *      Computes the splitting value along a given axis for a given node.
163 *      \param          primitives              [in] list of indices of primitives
164 *      \param          nb_prims                [in] number of indices
165 *      \param          global_box              [in] global AABB enclosing the set of input primitives
166 *      \param          axis                    [in] axis index (0,1,2)
167 *      \return         splitting value
168 */
169///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
170float AABBTreeOfTrianglesBuilder::GetSplittingValue(const udword* primitives, udword nb_prims, const AABB& global_box, udword axis)     const
171{
172        if(mSettings.mRules&SPLIT_GEOM_CENTER)
173        {
174                // Loop through triangles
175                float SplitValue = 0.0f;
176                VertexPointers VP;
177                for(udword i=0;i<nb_prims;i++)
178                {
179                        // Get current triangle-vertices
180                        mIMesh->GetTriangle(VP, primitives[i]);
181                        // Update split value
182                        SplitValue += (*VP.Vertex[0])[axis];
183                        SplitValue += (*VP.Vertex[1])[axis];
184                        SplitValue += (*VP.Vertex[2])[axis];
185                }
186                return SplitValue / float(nb_prims*3);
187        }
188        else return AABBTreeBuilder::GetSplittingValue(primitives, nb_prims, global_box, axis);
189}
190
191///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
192/**
193 *      Computes the AABB of a set of primitives.
194 *      \param          primitives              [in] list of indices of primitives
195 *      \param          nb_prims                [in] number of indices
196 *      \param          global_box              [out] global AABB enclosing the set of input primitives
197 *      \return         true if success
198 */
199///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
200bool AABBTreeOfVerticesBuilder::ComputeGlobalBox(const udword* primitives, udword nb_prims, AABB& global_box) const
201{
202        // Checkings
203        if(!primitives || !nb_prims)    return false;
204
205        // Initialize global box
206        global_box.SetEmpty();
207
208        // Loop through vertices
209        for(udword i=0;i<nb_prims;i++)
210        {
211                // Update global box
212                global_box.Extend(mVertexArray[primitives[i]]);
213        }
214        return true;
215}
216
217///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
218/**
219 *      Computes the splitting value along a given axis for a given primitive.
220 *      \param          index           [in] index of the primitive to split
221 *      \param          axis            [in] axis index (0,1,2)
222 *      \return         splitting value
223 */
224///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
225float AABBTreeOfVerticesBuilder::GetSplittingValue(udword index, udword axis) const
226{
227        // For a vertex, the splitting value is simply the vertex coordinate.
228        return mVertexArray[index][axis];
229}
230
231///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
232/**
233 *      Computes the splitting value along a given axis for a given node.
234 *      \param          primitives              [in] list of indices of primitives
235 *      \param          nb_prims                [in] number of indices
236 *      \param          global_box              [in] global AABB enclosing the set of input primitives
237 *      \param          axis                    [in] axis index (0,1,2)
238 *      \return         splitting value
239 */
240///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
241float AABBTreeOfVerticesBuilder::GetSplittingValue(const udword* primitives, udword nb_prims, const AABB& global_box, udword axis)      const
242{
243        if(mSettings.mRules&SPLIT_GEOM_CENTER)
244        {
245                // Loop through vertices
246                float SplitValue = 0.0f;
247                for(udword i=0;i<nb_prims;i++)
248                {
249                        // Update split value
250                        SplitValue += mVertexArray[primitives[i]][axis];
251                }
252                return SplitValue / float(nb_prims);
253        }
254        else return AABBTreeBuilder::GetSplittingValue(primitives, nb_prims, global_box, axis);
255}
Note: See TracBrowser for help on using the repository browser.