0025222: Visualization - provide distance field builder in the Math/BVH package
authordbp <dbp@opencascade.com>
Thu, 15 Jan 2015 11:33:23 +0000 (14:33 +0300)
committerbugmaster <bugmaster@opencascade.com>
Thu, 15 Jan 2015 11:34:57 +0000 (14:34 +0300)
A distance field is a representation where, at each point within the field, the distance from that point to the closest point on the object is specified.
In addition to distance, other properties may be derived from the distance field, such as the direction to the surface, and when the distance field is signed, we may also determine if the point is internal or external to objects within the domain.
The distance field has been found to be a useful construction within the areas of computer vision, physics, and computer graphics. In particular, distance fields can be used for generating realistic visual effects and collision detection.

Fix compilation warning when using GCC.

src/BVH/BVH.cxx
src/BVH/BVH_DistanceField.hxx [new file with mode: 0644]
src/BVH/BVH_DistanceField.lxx [new file with mode: 0644]
src/BVH/FILES

index cf81cfc..48fd7c0 100644 (file)
@@ -15,6 +15,7 @@
 
 #include <BVH_Geometry.hxx>
 #include <BVH_Triangulation.hxx>
+#include <BVH_DistanceField.hxx>
 #include <BVH_LinearBuilder.hxx>
 #include <BVH_BinnedBuilder.hxx>
 #include <BVH_SweepPlaneBuilder.hxx>
@@ -124,5 +125,11 @@ template class BVH_Triangulation<Standard_ShortReal, 2>;
 template class BVH_Triangulation<Standard_ShortReal, 3>;
 template class BVH_Triangulation<Standard_ShortReal, 4>;
 
+template class BVH_DistanceField<Standard_Real, 3>;
+template class BVH_DistanceField<Standard_Real, 4>;
+
+template class BVH_DistanceField<Standard_ShortReal, 3>;
+template class BVH_DistanceField<Standard_ShortReal, 4>;
+
 template class BVH_Transform<Standard_Real, 4>;
 template class BVH_Transform<Standard_ShortReal, 4>;
diff --git a/src/BVH/BVH_DistanceField.hxx b/src/BVH/BVH_DistanceField.hxx
new file mode 100644 (file)
index 0000000..e17f011
--- /dev/null
@@ -0,0 +1,148 @@
+// Created on: 2014-09-06
+// Created by: Denis BOGOLEPOV
+// Copyright (c) 2013-2014 OPEN CASCADE SAS
+//
+// This file is part of Open CASCADE Technology software library.
+//
+// This library is free software; you can redistribute it and/or modify it under
+// the terms of the GNU Lesser General Public License version 2.1 as published
+// by the Free Software Foundation, with special exception defined in the file
+// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
+// distribution for complete text of the license and disclaimer of any warranty.
+//
+// Alternatively, this file may be used under the terms of Open CASCADE
+// commercial license or contractual agreement.
+
+#ifndef _BVH_DistanceField_Header
+#define _BVH_DistanceField_Header
+
+#include <BVH_Geometry.hxx>
+
+template<class T, int N> class BVH_ParallelDistanceFieldBuilder;
+
+//! Tool object for building 3D distance field from the set of BVH triangulations.
+//! Distance field is a scalar field that measures the distance from a given point
+//! to some object, including optional information about the inside and outside of
+//! the structure. Distance fields are used as alternative surface representations
+//! (like polygons or NURBS).
+template<class T, int N>
+class BVH_DistanceField
+{
+  friend class BVH_ParallelDistanceFieldBuilder<T, N>;
+
+public:
+
+  typedef typename BVH::VectorType<T, N>::Type BVH_VecNt;
+
+public:
+
+  //! Creates empty 3D distance field.
+  BVH_DistanceField (const Standard_Integer theMaximumSize,
+                     const Standard_Boolean theComputeSign);
+
+  //! Releases resources of 3D distance field.
+  virtual ~BVH_DistanceField();
+
+  //! Builds 3D distance field from BVH geometry.
+  Standard_Boolean Build (BVH_Geometry<T, N>& theGeometry);
+
+public:
+
+  //! Returns packed voxel data.
+  const T* PackedData() const
+  {
+    return myVoxelData;
+  }
+
+  //! Returns distance value for the given voxel.
+  T& Voxel (const Standard_Integer theX,
+            const Standard_Integer theY,
+            const Standard_Integer theZ)
+  {
+    return myVoxelData[theX + (theY + theZ * myDimensionY) * myDimensionX];
+  }
+
+  //! Returns distance value for the given voxel.
+  T Voxel (const Standard_Integer theX,
+           const Standard_Integer theY,
+           const Standard_Integer theZ) const
+  {
+    return myVoxelData[theX + (theY + theZ * myDimensionY) * myDimensionX];
+  }
+
+  //! Returns size of voxel grid in X dimension.
+  Standard_Integer DimensionX() const
+  {
+    return myDimensionX;
+  }
+
+  //! Returns size of voxel grid in Y dimension.
+  Standard_Integer DimensionY() const
+  {
+    return myDimensionY;
+  }
+
+  //! Returns size of voxel grid in Z dimension.
+  Standard_Integer DimensionZ() const
+  {
+    return myDimensionZ;
+  }
+
+  //! Returns size of single voxel.
+  const BVH_VecNt& VoxelSize() const
+  {
+    return myVoxelSize;
+  }
+
+  //! Returns minimum corner of voxel grid.
+  const BVH_VecNt& CornerMin() const
+  {
+    return myCornerMin;
+  }
+
+  //! Returns maximum corner of voxel grid.
+  const BVH_VecNt& CornerMax() const
+  {
+    return myCornerMax;
+  }
+
+protected:
+
+  //! Performs building of distance field for the given Z slices.
+  void BuildSlices (BVH_Geometry<T, N>& theGeometry,
+    const Standard_Integer theStartZ, const Standard_Integer theFinalZ);
+
+protected:
+
+  //! Array of voxels.
+  T* myVoxelData;
+
+  //! Size of single voxel.
+  BVH_VecNt myVoxelSize;
+
+  //! Minimum corner of voxel grid.
+  BVH_VecNt myCornerMin;
+
+  //! Maximum corner of voxel grid.
+  BVH_VecNt myCornerMax;
+
+  //! Size of voxel grid in X dimension.
+  Standard_Integer myDimensionX;
+
+  //! Size of voxel grid in Y dimension.
+  Standard_Integer myDimensionY;
+
+  //! Size of voxel grid in Z dimension.
+  Standard_Integer myDimensionZ;
+
+  //! Size of voxel grid in maximum dimension.
+  Standard_Integer myMaximumSize;
+
+  //! Enables/disables signing of distance field.
+  Standard_Boolean myComputeSign;
+
+};
+
+#include <BVH_DistanceField.lxx>
+
+#endif // _BVH_DistanceField_Header
diff --git a/src/BVH/BVH_DistanceField.lxx b/src/BVH/BVH_DistanceField.lxx
new file mode 100644 (file)
index 0000000..570cc7a
--- /dev/null
@@ -0,0 +1,528 @@
+// Created on: 2014-09-06
+// Created by: Denis BOGOLEPOV
+// Copyright (c) 2013-2014 OPEN CASCADE SAS
+//
+// This file is part of Open CASCADE Technology software library.
+//
+// This library is free software; you can redistribute it and/or modify it under
+// the terms of the GNU Lesser General Public License version 2.1 as published
+// by the Free Software Foundation, with special exception defined in the file
+// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
+// distribution for complete text of the license and disclaimer of any warranty.
+//
+// Alternatively, this file may be used under the terms of Open CASCADE
+// commercial license or contractual agreement.
+
+#include <Standard_Assert.hxx>
+
+#include <BVH_Triangulation.hxx>
+
+#ifdef HAVE_TBB
+  // On Windows, function TryEnterCriticalSection has appeared in Windows NT
+  // and is surrounded by #ifdef in MS VC++ 7.1 headers.
+  // Thus to use it we need to define appropriate macro saying that we will
+  // run on Windows NT 4.0 at least
+  #if defined(_WIN32) && !defined(_WIN32_WINNT)
+    #define _WIN32_WINNT 0x0501
+  #endif
+
+  #include <tbb/tbb.h>
+#endif
+
+// =======================================================================
+// function : BVH_DistanceField
+// purpose  :
+// =======================================================================
+template<class T, int N>
+BVH_DistanceField<T, N>::BVH_DistanceField (const Standard_Integer theMaximumSize,
+                                            const Standard_Boolean theComputeSign)
+: myMaximumSize (theMaximumSize),
+  myComputeSign (theComputeSign)
+{
+  Standard_STATIC_ASSERT (N == 3 || N == 4);
+
+  myVoxelData = new T[myMaximumSize * myMaximumSize * myMaximumSize];
+}
+
+// =======================================================================
+// function : ~BVH_DistanceField
+// purpose  :
+// =======================================================================
+template<class T, int N>
+BVH_DistanceField<T, N>::~BVH_DistanceField()
+{
+  delete [] myVoxelData;
+}
+
+#if defined (_WIN32) && defined (max)
+  #undef max
+#endif
+
+#include <limits>
+
+#define BVH_DOT3(A, B) (A.x() * B.x() + A.y() * B.y() + A.z() * B.z())
+
+namespace BVH
+{
+  //=======================================================================
+  //function : DistanceToBox
+  //purpose  : Computes squared distance from point to box
+  //=======================================================================
+  template<class T, int N>
+  T DistanceToBox (const typename VectorType<T, N>::Type& thePnt,
+                   const typename VectorType<T, N>::Type& theMin,
+                   const typename VectorType<T, N>::Type& theMax)
+  {
+    Standard_STATIC_ASSERT (N == 3 || N == 4);
+
+    T aNearestX = Min (Max (thePnt.x(), theMin.x()), theMax.x());
+    T aNearestY = Min (Max (thePnt.y(), theMin.y()), theMax.y());
+    T aNearestZ = Min (Max (thePnt.z(), theMin.z()), theMax.z());
+
+    if (aNearestX == thePnt.x()
+     && aNearestY == thePnt.y()
+     && aNearestZ == thePnt.z())
+    {
+      return static_cast<T> (0);
+    }
+
+    aNearestX -= thePnt.x();
+    aNearestY -= thePnt.y();
+    aNearestZ -= thePnt.z();
+
+    return aNearestX * aNearestX +
+           aNearestY * aNearestY +
+           aNearestZ * aNearestZ;
+  }
+
+  //=======================================================================
+  //function : DirectionToNearestPoint
+  //purpose  : Computes squared distance from point to triangle
+  // ======================================================================
+  template<class T, int N>
+  typename VectorType<T, N>::Type DirectionToNearestPoint (
+    const typename VectorType<T, N>::Type& thePoint,
+    const typename VectorType<T, N>::Type& theVertA,
+    const typename VectorType<T, N>::Type& theVertB,
+    const typename VectorType<T, N>::Type& theVertC)
+  {
+    Standard_STATIC_ASSERT (N == 3 || N == 4);
+
+    const typename VectorType<T, N>::Type aAB = theVertB - theVertA;
+    const typename VectorType<T, N>::Type aAC = theVertC - theVertA;
+    const typename VectorType<T, N>::Type aAP = thePoint - theVertA;
+
+    const T aABdotAP = BVH_DOT3 (aAB, aAP);
+    const T aACdotAP = BVH_DOT3 (aAC, aAP);
+
+    if (aABdotAP <= static_cast<T> (0) && aACdotAP <= static_cast<T> (0))
+    {
+      return aAP;
+    }
+
+    const typename VectorType<T, N>::Type aBC = theVertC - theVertB;
+    const typename VectorType<T, N>::Type aBP = thePoint - theVertB;
+
+    const T aBAdotBP = -BVH_DOT3 (aAB, aBP);
+    const T aBCdotBP =  BVH_DOT3 (aBC, aBP);
+
+    if (aBAdotBP <= static_cast<T> (0) && aBCdotBP <= static_cast<T> (0))
+    {
+      return aBP;
+    }
+
+    const typename VectorType<T, N>::Type aCP = thePoint - theVertC;
+
+    const T aCBdotCP = -BVH_DOT3 (aBC, aCP);
+    const T aCAdotCP = -BVH_DOT3 (aAC, aCP);
+
+    if (aCAdotCP <= static_cast<T> (0) && aCBdotCP <= static_cast<T> (0))
+    {
+      return aCP;
+    }
+
+    const T aACdotBP = BVH_DOT3 (aAC, aBP);
+
+    const T aVC = aABdotAP * aACdotBP + aBAdotBP * aACdotAP;
+
+    if (aVC <= static_cast<T> (0) && aABdotAP >= static_cast<T> (0) && aBAdotBP >= static_cast<T> (0))
+    {
+      return aAP - aAB * (aABdotAP / (aABdotAP + aBAdotBP));
+    }
+
+    const T aABdotCP = BVH_DOT3 (aAB, aCP);
+
+    const T aVA = aBAdotBP * aCAdotCP - aABdotCP * aACdotBP;
+
+    if (aVA <= static_cast<T> (0) && aBCdotBP >= static_cast<T> (0) && aCBdotCP >= static_cast<T> (0))
+    {
+      return aBP - aBC * (aBCdotBP / (aBCdotBP + aCBdotCP));
+    }
+
+    const T aVB = aABdotCP * aACdotAP + aABdotAP * aCAdotCP;
+
+    if (aVB <= static_cast<T> (0) && aACdotAP >= static_cast<T> (0) && aCAdotCP >= static_cast<T> (0))
+    {
+      return aAP - aAC * (aACdotAP / (aACdotAP + aCAdotCP));
+    }
+
+    const T aNorm = static_cast<T> (1.0) / (aVA + aVB + aVC);
+
+    const T aU = aVA * aNorm;
+    const T aV = aVB * aNorm;
+
+    return thePoint - (theVertA * aU + theVertB * aV + theVertC * (static_cast<T> (1.0) - aU - aV));
+  }
+
+  //=======================================================================
+  //function : SquareDistanceToObject
+  //purpose  : Computes squared distance from point to BVH triangulation
+  //=======================================================================
+  template<class T, int N>
+  T SquareDistanceToObject (BVH_Object<T, N>* theObject,
+    const typename VectorType<T, N>::Type& thePnt, Standard_Boolean& theIsOutside)
+  {
+    Standard_STATIC_ASSERT (N == 3 || N == 4);
+
+    T aMinDistance = std::numeric_limits<T>::max();
+
+    BVH_Triangulation<T, N>* aTriangulation =
+      dynamic_cast<BVH_Triangulation<T, N>*> (theObject);
+
+    Standard_ASSERT_RETURN (aTriangulation != NULL,
+      "Error: Unsupported BVH object (non triangulation)", aMinDistance);
+
+    const NCollection_Handle<BVH_Tree<T, N> >& aBVH = aTriangulation->BVH();
+
+    if (aBVH.IsNull())
+    {
+      return Standard_False;
+    }
+
+    std::pair<Standard_Integer, T> aStack[32];
+
+    Standard_Integer aHead = -1;
+    Standard_Integer aNode =  0; // root node
+
+    for (;;)
+    {
+      BVH_Vec4i aData = aBVH->NodeInfoBuffer()[aNode];
+
+      if (aData.x() == 0) // if inner node
+      {
+        const T aDistToLft = DistanceToBox<T, N> (thePnt,
+                                                  aBVH->MinPoint (aData.y()),
+                                                  aBVH->MaxPoint (aData.y()));
+
+        const T aDistToRgh = DistanceToBox<T, N> (thePnt,
+                                                  aBVH->MinPoint (aData.z()),
+                                                  aBVH->MaxPoint (aData.z()));
+
+        const Standard_Boolean aHitLft = aDistToLft <= aMinDistance;
+        const Standard_Boolean aHitRgh = aDistToRgh <= aMinDistance;
+
+        if (aHitLft & aHitRgh)
+        {
+          aNode = (aDistToLft < aDistToRgh) ? aData.y() : aData.z();
+
+          aStack[++aHead] = std::pair<Standard_Integer, T> (
+            aDistToLft < aDistToRgh ? aData.z() : aData.y(), Max (aDistToLft, aDistToRgh));
+        }
+        else
+        {
+          if (aHitLft | aHitRgh)
+          {
+            aNode = aHitLft ? aData.y() : aData.z();
+          }
+          else
+          {
+            if (aHead < 0)
+              return aMinDistance;
+
+            std::pair<Standard_Integer, T>& anInfo = aStack[aHead--];
+
+            while (anInfo.second > aMinDistance)
+            {
+              if (aHead < 0)
+                return aMinDistance;
+
+              anInfo = aStack[aHead--];
+            }
+
+            aNode = anInfo.first;
+          }
+        }
+      }
+      else  // if leaf node
+      {
+        for (Standard_Integer aTrgIdx = aData.y(); aTrgIdx <= aData.z(); ++aTrgIdx)
+        {
+          const BVH_Vec4i aTriangle = aTriangulation->Elements[aTrgIdx];
+
+          const typename VectorType<T, N>::Type aVertex0 = aTriangulation->Vertices[aTriangle.x()];
+          const typename VectorType<T, N>::Type aVertex1 = aTriangulation->Vertices[aTriangle.y()];
+          const typename VectorType<T, N>::Type aVertex2 = aTriangulation->Vertices[aTriangle.z()];
+
+          const typename VectorType<T, N>::Type aDirection =
+            DirectionToNearestPoint<T, N> (thePnt, aVertex0, aVertex1, aVertex2);
+
+          const T aDistance = BVH_DOT3 (aDirection, aDirection);
+
+          if (aDistance < aMinDistance)
+          {
+            aMinDistance = aDistance;
+
+            typename VectorType<T, N>::Type aTrgEdges[] = { aVertex1 - aVertex0,
+                                                            aVertex2 - aVertex0 };
+
+            typename VectorType<T, N>::Type aTrgNormal;
+            
+            aTrgNormal.x() = aTrgEdges[0].y() * aTrgEdges[1].z() - aTrgEdges[0].z() * aTrgEdges[1].y();
+            aTrgNormal.y() = aTrgEdges[0].z() * aTrgEdges[1].x() - aTrgEdges[0].x() * aTrgEdges[1].z();
+            aTrgNormal.z() = aTrgEdges[0].x() * aTrgEdges[1].y() - aTrgEdges[0].y() * aTrgEdges[1].x();
+
+            theIsOutside = BVH_DOT3 (aTrgNormal, aDirection) > 0;
+          }
+        }
+
+        if (aHead < 0)
+          return aMinDistance;
+
+        std::pair<Standard_Integer, T>& anInfo = aStack[aHead--];
+
+        while (anInfo.second > aMinDistance)
+        {
+          if (aHead < 0)
+            return aMinDistance;
+
+          anInfo = aStack[aHead--];
+        }
+
+        aNode = anInfo.first;
+      }
+    }
+  }
+
+  //=======================================================================
+  //function : SquareDistanceToGeomerty
+  //purpose  : Computes squared distance from point to BVH geometry
+  //=======================================================================
+  template<class T, int N>
+  T SquareDistanceToGeomerty (BVH_Geometry<T, N>& theGeometry,
+    const typename VectorType<T, N>::Type& thePnt, Standard_Boolean& theIsOutside)
+  {
+    Standard_STATIC_ASSERT (N == 3 || N == 4);
+
+    const NCollection_Handle<BVH_Tree<T, N> >& aBVH = theGeometry.BVH();
+
+    if (aBVH.IsNull())
+    {
+      return Standard_False;
+    }
+
+    std::pair<Standard_Integer, T> aStack[32];
+
+    Standard_Integer aHead = -1;
+    Standard_Integer aNode =  0; // root node
+
+    T aMinDistance = std::numeric_limits<T>::max();
+
+    for (;;)
+    {
+      BVH_Vec4i aData = aBVH->NodeInfoBuffer()[aNode];
+
+      if (aData.x() == 0) // if inner node
+      {
+        const T aDistToLft = DistanceToBox<T, N> (thePnt,
+                                                  aBVH->MinPoint (aData.y()),
+                                                  aBVH->MaxPoint (aData.y()));
+
+        const T aDistToRgh = DistanceToBox<T, N> (thePnt,
+                                                  aBVH->MinPoint (aData.z()),
+                                                  aBVH->MaxPoint (aData.z()));
+
+        const Standard_Boolean aHitLft = aDistToLft <= aMinDistance;
+        const Standard_Boolean aHitRgh = aDistToRgh <= aMinDistance;
+
+        if (aHitLft & aHitRgh)
+        {
+          aNode = (aDistToLft < aDistToRgh) ? aData.y() : aData.z();
+
+          aStack[++aHead] = std::pair<Standard_Integer, T> (
+            aDistToLft < aDistToRgh ? aData.z() : aData.y(), Max (aDistToLft, aDistToRgh));
+        }
+        else
+        {
+          if (aHitLft | aHitRgh)
+          {
+            aNode = aHitLft ? aData.y() : aData.z();
+          }
+          else
+          {
+            if (aHead < 0)
+              return aMinDistance;
+
+            std::pair<Standard_Integer, T>& anInfo = aStack[aHead--];
+
+            while (anInfo.second > aMinDistance)
+            {
+              if (aHead < 0)
+                return aMinDistance;
+
+              anInfo = aStack[aHead--];
+            }
+
+            aNode = anInfo.first;
+          }
+        }
+      }
+      else  // if leaf node
+      {
+        Standard_Boolean isOutside = Standard_True;
+
+        const T aDistance = SquareDistanceToObject (
+          theGeometry.Objects()(aNode).operator->(), thePnt, isOutside);
+
+        if (aDistance < aMinDistance)
+        {
+          aMinDistance = aDistance;
+          theIsOutside = isOutside;
+        }
+
+        if (aHead < 0)
+          return aMinDistance;
+
+        std::pair<Standard_Integer, T>& anInfo = aStack[aHead--];
+
+        while (anInfo.second > aMinDistance)
+        {
+          if (aHead < 0)
+            return aMinDistance;
+
+          anInfo = aStack[aHead--];
+        }
+
+        aNode = anInfo.first;
+      }
+    }
+  }
+}
+
+#undef BVH_DOT3
+
+#ifdef HAVE_TBB
+
+//! Tool object for parallel construction of distance field (uses Intel TBB).
+template<class T, int N>
+class BVH_ParallelDistanceFieldBuilder
+{
+private:
+
+  //! Input BVH geometry.
+  BVH_Geometry<T, N>* myGeometry;
+
+  //! Output distance field.
+  BVH_DistanceField<T, N>* myOutField;
+
+public:
+
+  BVH_ParallelDistanceFieldBuilder (BVH_DistanceField<T, N>* theOutField, BVH_Geometry<T, N>* theGeometry)
+  : myGeometry (theGeometry),
+    myOutField (theOutField)
+  {
+    //
+  }
+
+  void operator() (const tbb::blocked_range<Standard_Integer>& theRange) const
+  {
+    myOutField->BuildSlices (*myGeometry, theRange.begin(), theRange.end());
+  }
+};
+
+#endif
+
+// =======================================================================
+// function : BuildSlices
+// purpose  : Performs building of distance field for the given Z slices
+// =======================================================================
+template<class T, int N>
+void BVH_DistanceField<T, N>::BuildSlices (BVH_Geometry<T, N>& theGeometry,
+  const Standard_Integer theStartSlice, const Standard_Integer theFinalSlice)
+{
+  for (Standard_Integer aZ = theStartSlice; aZ < theFinalSlice; ++aZ)
+  {
+    for (Standard_Integer aY = 0; aY < myDimensionY; ++aY)
+    {
+      for (Standard_Integer aX = 0; aX < myDimensionX; ++aX)
+      {
+        BVH_VecNt aCenter;
+        
+        aCenter.x() = myCornerMin.x() + myVoxelSize.x() * (aX + static_cast<T> (0.5));
+        aCenter.y() = myCornerMin.y() + myVoxelSize.y() * (aY + static_cast<T> (0.5));
+        aCenter.z() = myCornerMin.z() + myVoxelSize.z() * (aZ + static_cast<T> (0.5));
+
+        Standard_Boolean isOutside = Standard_True;
+
+        const T aDistance = sqrt (
+          BVH::SquareDistanceToGeomerty<T, N> (theGeometry, aCenter, isOutside));
+
+        Voxel (aX, aY, aZ) = (!myComputeSign || isOutside) ? aDistance : -aDistance;
+      }
+    }
+  }
+}
+
+// =======================================================================
+// function : Build
+// purpose  : Builds 3D distance field from BVH geometry
+// =======================================================================
+template<class T, int N>
+Standard_Boolean BVH_DistanceField<T, N>::Build (BVH_Geometry<T, N>& theGeometry)
+{
+  if (theGeometry.Size() == 0)
+  {
+    return Standard_False;
+  }
+
+  const BVH_VecNt aGlobalBoxSize = theGeometry.Box().Size();
+
+  const T aMaxBoxSide = Max (Max (aGlobalBoxSize.x(), aGlobalBoxSize.y()), aGlobalBoxSize.z());
+
+  myDimensionX = static_cast<Standard_Integer> (myMaximumSize * aGlobalBoxSize.x() / aMaxBoxSide);
+  myDimensionY = static_cast<Standard_Integer> (myMaximumSize * aGlobalBoxSize.y() / aMaxBoxSide);
+  myDimensionZ = static_cast<Standard_Integer> (myMaximumSize * aGlobalBoxSize.z() / aMaxBoxSide);
+
+  myDimensionX = Min (myMaximumSize, Max (myDimensionX, 16));
+  myDimensionY = Min (myMaximumSize, Max (myDimensionY, 16));
+  myDimensionZ = Min (myMaximumSize, Max (myDimensionZ, 16));
+
+  const BVH_VecNt aGlobalBoxMin = theGeometry.Box().CornerMin();
+  const BVH_VecNt aGlobalBoxMax = theGeometry.Box().CornerMax();
+
+  const Standard_Integer aVoxelOffset = 2;
+
+  myCornerMin.x() = aGlobalBoxMin.x() - aVoxelOffset * aGlobalBoxSize.x() / (myDimensionX - 2 * aVoxelOffset);
+  myCornerMin.y() = aGlobalBoxMin.y() - aVoxelOffset * aGlobalBoxSize.y() / (myDimensionY - 2 * aVoxelOffset);
+  myCornerMin.z() = aGlobalBoxMin.z() - aVoxelOffset * aGlobalBoxSize.z() / (myDimensionZ - 2 * aVoxelOffset);
+
+  myCornerMax.x() = aGlobalBoxMax.x() + aVoxelOffset * aGlobalBoxSize.x() / (myDimensionX - 2 * aVoxelOffset);
+  myCornerMax.y() = aGlobalBoxMax.y() + aVoxelOffset * aGlobalBoxSize.y() / (myDimensionY - 2 * aVoxelOffset);
+  myCornerMax.z() = aGlobalBoxMax.z() + aVoxelOffset * aGlobalBoxSize.z() / (myDimensionZ - 2 * aVoxelOffset);
+  
+  myVoxelSize.x() = (myCornerMax.x() - myCornerMin.x()) / myDimensionX;
+  myVoxelSize.y() = (myCornerMax.y() - myCornerMin.y()) / myDimensionY;
+  myVoxelSize.z() = (myCornerMax.z() - myCornerMin.z()) / myDimensionZ;
+
+#ifdef HAVE_TBB
+  
+  tbb::parallel_for (tbb::blocked_range<Standard_Integer> (0, myDimensionZ),
+    BVH_ParallelDistanceFieldBuilder<T, N> (this, &theGeometry));
+
+#else
+
+  BuildSlices (theGeometry, 0, myDimensionZ);
+
+#endif
+
+  return Standard_True;
+}
index 5c73d63..4442236 100644 (file)
@@ -33,3 +33,5 @@ BVH_Triangulation.lxx
 BVH_Types.hxx
 BVH_QueueBuilder.hxx
 BVH_QueueBuilder.lxx
+BVH_DistanceField.hxx
+BVH_DistanceField.lxx