[216] | 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 | |
---|
| 55 | using 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 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 66 | bool 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 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 91 | float 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 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 107 | bool 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 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 138 | float 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 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 170 | float 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 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 200 | bool 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 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 225 | float 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 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 241 | float 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 | } |
---|