summaryrefslogtreecommitdiffhomepage
path: root/Opcode/OpcodeLib/OPC_TreeBuilders.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'Opcode/OpcodeLib/OPC_TreeBuilders.cpp')
-rw-r--r--Opcode/OpcodeLib/OPC_TreeBuilders.cpp255
1 files changed, 255 insertions, 0 deletions
diff --git a/Opcode/OpcodeLib/OPC_TreeBuilders.cpp b/Opcode/OpcodeLib/OPC_TreeBuilders.cpp
new file mode 100644
index 0000000..fa415db
--- /dev/null
+++ b/Opcode/OpcodeLib/OPC_TreeBuilders.cpp
@@ -0,0 +1,255 @@
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/*
+ * OPCODE - Optimized Collision Detection
+ * Copyright (C) 2001 Pierre Terdiman
+ * Homepage: http://www.codercorner.com/Opcode.htm
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ * Contains code for tree builders.
+ * \file OPC_TreeBuilders.cpp
+ * \author Pierre Terdiman
+ * \date March, 20, 2001
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ * A builder for AABB-trees of vertices.
+ *
+ * \class AABBTreeOfVerticesBuilder
+ * \author Pierre Terdiman
+ * \version 1.3
+ * \date March, 20, 2001
+*/
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ * A builder for AABB-trees of AABBs.
+ *
+ * \class AABBTreeOfAABBsBuilder
+ * \author Pierre Terdiman
+ * \version 1.3
+ * \date March, 20, 2001
+*/
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ * A builder for AABB-trees of triangles.
+ *
+ * \class AABBTreeOfTrianglesBuilder
+ * \author Pierre Terdiman
+ * \version 1.3
+ * \date March, 20, 2001
+*/
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+// Precompiled Header
+#include "Stdafx.h"
+
+using namespace Opcode;
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ * Computes the AABB of a set of primitives.
+ * \param primitives [in] list of indices of primitives
+ * \param nb_prims [in] number of indices
+ * \param global_box [out] global AABB enclosing the set of input primitives
+ * \return true if success
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+bool AABBTreeOfAABBsBuilder::ComputeGlobalBox(const udword* primitives, udword nb_prims, AABB& global_box) const
+{
+ // Checkings
+ if(!primitives || !nb_prims) return false;
+
+ // Initialize global box
+ global_box = mAABBArray[primitives[0]];
+
+ // Loop through boxes
+ for(udword i=1;i<nb_prims;i++)
+ {
+ // Update global box
+ global_box.Add(mAABBArray[primitives[i]]);
+ }
+ return true;
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ * Computes the splitting value along a given axis for a given primitive.
+ * \param index [in] index of the primitive to split
+ * \param axis [in] axis index (0,1,2)
+ * \return splitting value
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+float AABBTreeOfAABBsBuilder::GetSplittingValue(udword index, udword axis) const
+{
+ // For an AABB, the splitting value is the middle of the given axis,
+ // i.e. the corresponding component of the center point
+ return mAABBArray[index].GetCenter(axis);
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ * Computes the AABB of a set of primitives.
+ * \param primitives [in] list of indices of primitives
+ * \param nb_prims [in] number of indices
+ * \param global_box [out] global AABB enclosing the set of input primitives
+ * \return true if success
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+bool AABBTreeOfTrianglesBuilder::ComputeGlobalBox(const udword* primitives, udword nb_prims, AABB& global_box) const
+{
+ // Checkings
+ if(!primitives || !nb_prims) return false;
+
+ // Initialize global box
+ IcePoint Min(MAX_FLOAT, MAX_FLOAT, MAX_FLOAT);
+ IcePoint Max(MIN_FLOAT, MIN_FLOAT, MIN_FLOAT);
+
+ // Loop through triangles
+ VertexPointers VP;
+ while(nb_prims--)
+ {
+ // Get current triangle-vertices
+ mIMesh->GetTriangle(VP, *primitives++);
+ // Update global box
+ Min.Min(*VP.Vertex[0]).Min(*VP.Vertex[1]).Min(*VP.Vertex[2]);
+ Max.Max(*VP.Vertex[0]).Max(*VP.Vertex[1]).Max(*VP.Vertex[2]);
+ }
+ global_box.SetMinMax(Min, Max);
+ return true;
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ * Computes the splitting value along a given axis for a given primitive.
+ * \param index [in] index of the primitive to split
+ * \param axis [in] axis index (0,1,2)
+ * \return splitting value
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+float AABBTreeOfTrianglesBuilder::GetSplittingValue(udword index, udword axis) const
+{
+/* // Compute center of triangle
+ IcePoint Center;
+ mTriList[index].Center(mVerts, Center);
+ // Return value
+ return Center[axis];*/
+
+ // Compute correct component from center of triangle
+// return (mVerts[mTriList[index].mVRef[0]][axis]
+// +mVerts[mTriList[index].mVRef[1]][axis]
+// +mVerts[mTriList[index].mVRef[2]][axis])*INV3;
+
+ VertexPointers VP;
+ mIMesh->GetTriangle(VP, index);
+
+ // Compute correct component from center of triangle
+ return ((*VP.Vertex[0])[axis]
+ +(*VP.Vertex[1])[axis]
+ +(*VP.Vertex[2])[axis])*INV3;
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ * Computes the splitting value along a given axis for a given node.
+ * \param primitives [in] list of indices of primitives
+ * \param nb_prims [in] number of indices
+ * \param global_box [in] global AABB enclosing the set of input primitives
+ * \param axis [in] axis index (0,1,2)
+ * \return splitting value
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+float AABBTreeOfTrianglesBuilder::GetSplittingValue(const udword* primitives, udword nb_prims, const AABB& global_box, udword axis) const
+{
+ if(mSettings.mRules&SPLIT_GEOM_CENTER)
+ {
+ // Loop through triangles
+ float SplitValue = 0.0f;
+ VertexPointers VP;
+ for(udword i=0;i<nb_prims;i++)
+ {
+ // Get current triangle-vertices
+ mIMesh->GetTriangle(VP, primitives[i]);
+ // Update split value
+ SplitValue += (*VP.Vertex[0])[axis];
+ SplitValue += (*VP.Vertex[1])[axis];
+ SplitValue += (*VP.Vertex[2])[axis];
+ }
+ return SplitValue / float(nb_prims*3);
+ }
+ else return AABBTreeBuilder::GetSplittingValue(primitives, nb_prims, global_box, axis);
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ * Computes the AABB of a set of primitives.
+ * \param primitives [in] list of indices of primitives
+ * \param nb_prims [in] number of indices
+ * \param global_box [out] global AABB enclosing the set of input primitives
+ * \return true if success
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+bool AABBTreeOfVerticesBuilder::ComputeGlobalBox(const udword* primitives, udword nb_prims, AABB& global_box) const
+{
+ // Checkings
+ if(!primitives || !nb_prims) return false;
+
+ // Initialize global box
+ global_box.SetEmpty();
+
+ // Loop through vertices
+ for(udword i=0;i<nb_prims;i++)
+ {
+ // Update global box
+ global_box.Extend(mVertexArray[primitives[i]]);
+ }
+ return true;
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ * Computes the splitting value along a given axis for a given primitive.
+ * \param index [in] index of the primitive to split
+ * \param axis [in] axis index (0,1,2)
+ * \return splitting value
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+float AABBTreeOfVerticesBuilder::GetSplittingValue(udword index, udword axis) const
+{
+ // For a vertex, the splitting value is simply the vertex coordinate.
+ return mVertexArray[index][axis];
+}
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+/**
+ * Computes the splitting value along a given axis for a given node.
+ * \param primitives [in] list of indices of primitives
+ * \param nb_prims [in] number of indices
+ * \param global_box [in] global AABB enclosing the set of input primitives
+ * \param axis [in] axis index (0,1,2)
+ * \return splitting value
+ */
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+float AABBTreeOfVerticesBuilder::GetSplittingValue(const udword* primitives, udword nb_prims, const AABB& global_box, udword axis) const
+{
+ if(mSettings.mRules&SPLIT_GEOM_CENTER)
+ {
+ // Loop through vertices
+ float SplitValue = 0.0f;
+ for(udword i=0;i<nb_prims;i++)
+ {
+ // Update split value
+ SplitValue += mVertexArray[primitives[i]][axis];
+ }
+ return SplitValue / float(nb_prims);
+ }
+ else return AABBTreeBuilder::GetSplittingValue(primitives, nb_prims, global_box, axis);
+}