0030131: Foundation Classes - support of Linear builder for 2D BVH trees
authorosa <osa@opencascade.com>
Tue, 11 Sep 2018 18:56:14 +0000 (21:56 +0300)
committerbugmaster <bugmaster@opencascade.com>
Thu, 13 Sep 2018 17:42:21 +0000 (20:42 +0300)
BVH_LinearBuilder and BVH_RadixSorter now accept N==2.
NCollection_Vec2/3/4 - added missing division by vec operators.

src/BVH/BVH.cxx
src/BVH/BVH_LinearBuilder.hxx
src/BVH/BVH_RadixSorter.hxx
src/NCollection/NCollection_Vec2.hxx
src/NCollection/NCollection_Vec3.hxx
src/NCollection/NCollection_Vec4.hxx

index 451fd0c..671844e 100644 (file)
@@ -105,15 +105,19 @@ template class BVH_QuickSorter<Standard_Real, 4>;
 template class BVH_QuickSorter<Standard_ShortReal, 3>;
 template class BVH_QuickSorter<Standard_ShortReal, 4>;
 
+template class BVH_RadixSorter<Standard_Real, 2>;
 template class BVH_RadixSorter<Standard_Real, 3>;
 template class BVH_RadixSorter<Standard_Real, 4>;
 
+template class BVH_RadixSorter<Standard_ShortReal, 2>;
 template class BVH_RadixSorter<Standard_ShortReal, 3>;
 template class BVH_RadixSorter<Standard_ShortReal, 4>;
 
+template class BVH_LinearBuilder<Standard_Real, 2>;
 template class BVH_LinearBuilder<Standard_Real, 3>;
 template class BVH_LinearBuilder<Standard_Real, 4>;
 
+template class BVH_LinearBuilder<Standard_ShortReal, 2>;
 template class BVH_LinearBuilder<Standard_ShortReal, 3>;
 template class BVH_LinearBuilder<Standard_ShortReal, 4>;
 
index c2aee79..35e20d4 100644 (file)
@@ -308,7 +308,7 @@ void BVH_LinearBuilder<T, N>::Build (BVH_Set<T, N>*       theSet,
                                      BVH_Tree<T, N>*      theBVH,
                                      const BVH_Box<T, N>& theBox) const
 {
-  Standard_STATIC_ASSERT (N == 3 || N == 4);
+  Standard_STATIC_ASSERT (N == 2 || N == 3 || N == 4);
   const Standard_Integer aSetSize = theSet->Size();
   if (theBVH == NULL || aSetSize == 0)
   {
index 83acb45..4425a74 100644 (file)
@@ -173,18 +173,18 @@ namespace BVH
 template<class T, int N>
 void BVH_RadixSorter<T, N>::Perform (BVH_Set<T, N>* theSet, const Standard_Integer theStart, const Standard_Integer theFinal)
 {
-  Standard_STATIC_ASSERT (N == 3 || N == 4);
+  Standard_STATIC_ASSERT (N == 2 || N == 3 || N == 4);
 
-  const Standard_Integer aDimensionX = 1024;
-  const Standard_Integer aDimensionY = 1024;
-  const Standard_Integer aDimensionZ = 1024;
+  const Standard_Integer aDimension = 1024;
+  const Standard_Integer aNbEffComp = N == 2 ? 2 : 3; // 4th component is ignored
 
   const BVH_VecNt aSceneMin = myBox.CornerMin();
   const BVH_VecNt aSceneMax = myBox.CornerMax();
 
-  const T aReverseSizeX = static_cast<T> (aDimensionX) / Max (static_cast<T> (BVH::THE_NODE_MIN_SIZE), aSceneMax.x() - aSceneMin.x());
-  const T aReverseSizeY = static_cast<T> (aDimensionY) / Max (static_cast<T> (BVH::THE_NODE_MIN_SIZE), aSceneMax.y() - aSceneMin.y());
-  const T aReverseSizeZ = static_cast<T> (aDimensionZ) / Max (static_cast<T> (BVH::THE_NODE_MIN_SIZE), aSceneMax.z() - aSceneMin.z());
+  BVH_VecNt aNodeMinSizeVecT (static_cast<T>(BVH::THE_NODE_MIN_SIZE));
+  BVH::BoxMinMax<T, N>::CwiseMax (aNodeMinSizeVecT, aSceneMax - aSceneMin);
+
+  const BVH_VecNt aReverseSize = BVH_VecNt (static_cast<T>(aDimension)) / aNodeMinSizeVecT;
 
   myEncodedLinks = new NCollection_Shared<NCollection_Array1<BVH_EncodedLink> >(theStart, theFinal);
 
@@ -192,32 +192,24 @@ void BVH_RadixSorter<T, N>::Perform (BVH_Set<T, N>* theSet, const Standard_Integ
   for (Standard_Integer aPrimIdx = theStart; aPrimIdx <= theFinal; ++aPrimIdx)
   {
     const BVH_VecNt aCenter = theSet->Box (aPrimIdx).Center();
+    const BVH_VecNt aVoxelF = (aCenter - aSceneMin) * aReverseSize;
 
-    Standard_Integer aVoxelX = BVH::IntFloor ((aCenter.x() - aSceneMin.x()) * aReverseSizeX);
-    Standard_Integer aVoxelY = BVH::IntFloor ((aCenter.y() - aSceneMin.y()) * aReverseSizeY);
-    Standard_Integer aVoxelZ = BVH::IntFloor ((aCenter.z() - aSceneMin.z()) * aReverseSizeZ);
-
-    aVoxelX = Max (0, Min (aVoxelX, aDimensionX - 1));
-    aVoxelY = Max (0, Min (aVoxelY, aDimensionY - 1));
-    aVoxelZ = Max (0, Min (aVoxelZ, aDimensionZ - 1));
+    Standard_Integer aMortonCode = 0;
+    for (Standard_Integer aCompIter = 0; aCompIter < aNbEffComp; ++aCompIter)
+    {
+      Standard_Integer aVoxel = BVH::IntFloor (BVH::VecComp<T, N>::Get (aVoxelF, aCompIter));
 
-    aVoxelX = (aVoxelX | (aVoxelX << 16)) & 0x030000FF;
-    aVoxelX = (aVoxelX | (aVoxelX <<  8)) & 0x0300F00F;
-    aVoxelX = (aVoxelX | (aVoxelX <<  4)) & 0x030C30C3;
-    aVoxelX = (aVoxelX | (aVoxelX <<  2)) & 0x09249249;
+      aVoxel = Max (0, Min (aVoxel, aDimension - 1));
 
-    aVoxelY = (aVoxelY | (aVoxelY << 16)) & 0x030000FF;
-    aVoxelY = (aVoxelY | (aVoxelY <<  8)) & 0x0300F00F;
-    aVoxelY = (aVoxelY | (aVoxelY <<  4)) & 0x030C30C3;
-    aVoxelY = (aVoxelY | (aVoxelY <<  2)) & 0x09249249;
+      aVoxel = (aVoxel | (aVoxel << 16)) & 0x030000FF;
+      aVoxel = (aVoxel | (aVoxel <<  8)) & 0x0300F00F;
+      aVoxel = (aVoxel | (aVoxel <<  4)) & 0x030C30C3;
+      aVoxel = (aVoxel | (aVoxel <<  2)) & 0x09249249;
 
-    aVoxelZ = (aVoxelZ | (aVoxelZ << 16)) & 0x030000FF;
-    aVoxelZ = (aVoxelZ | (aVoxelZ <<  8)) & 0x0300F00F;
-    aVoxelZ = (aVoxelZ | (aVoxelZ <<  4)) & 0x030C30C3;
-    aVoxelZ = (aVoxelZ | (aVoxelZ <<  2)) & 0x09249249;
+      aMortonCode |= (aVoxel << aCompIter);
+    }
 
-    myEncodedLinks->ChangeValue (aPrimIdx) = BVH_EncodedLink (
-      aVoxelX | (aVoxelY << 1) | (aVoxelZ << 2), aPrimIdx);
+    myEncodedLinks->ChangeValue (aPrimIdx) = BVH_EncodedLink (aMortonCode, aPrimIdx);
   }
 
   // Step 2 -- Sort primitives by their Morton codes using radix sort
index bb74d07..c1ebb05 100644 (file)
@@ -217,6 +217,14 @@ public:
     return *this;
   }
 
+  //! Compute per-component division.
+  NCollection_Vec2& operator/= (const NCollection_Vec2& theRight)
+  {
+    v[0] /= theRight.v[0];
+    v[1] /= theRight.v[1];
+    return *this;
+  }
+
   //! Compute per-component multiplication by scale factor.
   NCollection_Vec2 operator* (const Element_t theFactor) const
   {
@@ -230,6 +238,14 @@ public:
             v[1] / theInvFactor);
   }
 
+  //! Compute per-component division.
+  friend NCollection_Vec2 operator/ (const NCollection_Vec2& theLeft,
+                                     const NCollection_Vec2& theRight)
+  {
+    return NCollection_Vec2 (theLeft.v[0] / theRight.v[0],
+                             theLeft.v[1] / theRight.v[1]);
+  }
+
   //! Computes the dot product.
   Element_t Dot (const NCollection_Vec2& theOther) const
   {
index 165b6d5..7a4e45b 100644 (file)
@@ -290,6 +290,15 @@ public:
     return *this;
   }
 
+  //! Compute per-component division.
+  NCollection_Vec3& operator/= (const NCollection_Vec3& theRight)
+  {
+    v[0] /= theRight.v[0];
+    v[1] /= theRight.v[1];
+    v[2] /= theRight.v[2];
+    return *this;
+  }
+
   //! Compute per-component division by scale factor.
   NCollection_Vec3 operator/ (const Element_t theInvFactor) const
   {
@@ -297,6 +306,14 @@ public:
     return aResult /= theInvFactor;
   }
 
+  //! Compute per-component division.
+  friend NCollection_Vec3 operator/ (const NCollection_Vec3& theLeft,
+                                     const NCollection_Vec3& theRight)
+  {
+    NCollection_Vec3 aResult = NCollection_Vec3 (theLeft);
+    return aResult /= theRight;
+  }
+
   //! Computes the dot product.
   Element_t Dot (const NCollection_Vec3& theOther) const
   {
index c3cb93a..f049585 100644 (file)
@@ -336,6 +336,16 @@ public:
     return *this;
   }
 
+  //! Compute per-component division.
+  NCollection_Vec4& operator/= (const NCollection_Vec4& theRight)
+  {
+    v[0] /= theRight.v[0];
+    v[1] /= theRight.v[1];
+    v[2] /= theRight.v[2];
+    v[3] /= theRight.v[3];
+    return *this;
+  }
+
   //! Compute per-component division by scale factor.
   NCollection_Vec4 operator/ (const Element_t theInvFactor)
   {
@@ -343,6 +353,14 @@ public:
     return aResult /= theInvFactor;
   }
 
+  //! Compute per-component division.
+  friend NCollection_Vec4 operator/ (const NCollection_Vec4& theLeft,
+                                     const NCollection_Vec4& theRight)
+  {
+    NCollection_Vec4 aResult = NCollection_Vec4 (theLeft);
+    return aResult /= theRight;
+  }
+
 private:
 
   Element_t v[4]; //!< define the vector as array to avoid structure alignment issues