Main Page Class List Class Members

- Main Page
- User's Guide
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

# sdk/extensions/authoring/source/VHACD/inc/vhacdVolume.h

Go to the documentation of this file.

    00001 /* Copyright (c) 2011 Khaled Mamou (kmamou at gmail dot com)
    00002  All rights reserved.
    00003
    00004
    00005  Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
    00006
    00007  1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
    00008
    00009  2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
    00010
    00011  3. The names of the contributors may not be used to endorse or promote products derived from this software without specific prior written permission.
    00012
    00013  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    00014  */
    00015 #pragma once
    00016 #ifndef VHACD_VOLUME_H
    00017 #define VHACD_VOLUME_H
    00018 #include "vhacdMesh.h"
    00019 #include "vhacdVector.h"
    00020 #include <assert.h>
    00021
    00022 #ifdef _MSC_VER
    00023 #pragma warning(push)
    00024 #pragma warning(disable:4456 4701)
    00025 #endif
    00026
    00027 namespace VHACD {
    00028
    00029 enum VOXEL_VALUE {
    00030     PRIMITIVE_UNDEFINED = 0,
    00031     PRIMITIVE_OUTSIDE_SURFACE = 1,
    00032     PRIMITIVE_INSIDE_SURFACE = 2,
    00033     PRIMITIVE_ON_SURFACE = 3
    00034 };
    00035
    00036 struct Voxel {
    00037 public:
    00038     short m_coord[3];
    00039     short m_data;
    00040 };
    00041
    00042 class PrimitiveSet {
    00043 public:
    00044     virtual ~PrimitiveSet(){};
    00045     virtual PrimitiveSet* Create() const = 0;
    00046     virtual const size_t GetNPrimitives() const = 0;
    00047     virtual const size_t GetNPrimitivesOnSurf() const = 0;
    00048     virtual const size_t GetNPrimitivesInsideSurf() const = 0;
    00049     virtual const double GetEigenValue(AXIS axis) const = 0;
    00050     virtual const double ComputeMaxVolumeError() const = 0;
    00051     virtual const double ComputeVolume() const = 0;
    00052     virtual void Clip(const Plane& plane, PrimitiveSet* const positivePart,
    00053         PrimitiveSet* const negativePart) const = 0;
    00054     virtual void Intersect(const Plane& plane, SArray<Vec3<double> >* const positivePts,
    00055         SArray<Vec3<double> >* const negativePts, const size_t sampling) const = 0;
    00056     virtual void ComputeExteriorPoints(const Plane& plane, const Mesh& mesh,
    00057         SArray<Vec3<double> >* const exteriorPts) const = 0;
    00058     virtual void ComputeClippedVolumes(const Plane& plane, double& positiveVolume,
    00059         double& negativeVolume) const = 0;
    00060     virtual void SelectOnSurface(PrimitiveSet* const onSurfP) const = 0;
    00061     virtual void ComputeConvexHull(Mesh& meshCH, const size_t sampling = 1) const = 0;
    00062     virtual void ComputeBB() = 0;
    00063     virtual void ComputePrincipalAxes() = 0;
    00064     virtual void AlignToPrincipalAxes() = 0;
    00065     virtual void RevertAlignToPrincipalAxes() = 0;
    00066     virtual void Convert(Mesh& mesh, const VOXEL_VALUE value) const = 0;
    00067     const Mesh& GetConvexHull() const { return m_convexHull; };
    00068     Mesh& GetConvexHull() { return m_convexHull; };
    00069 private:
    00070     Mesh m_convexHull;
    00071 };
    00072
    00074 class VoxelSet : public PrimitiveSet {
    00075     friend class Volume;
    00076
    00077 public:
    00079     ~VoxelSet(void);
    00081     VoxelSet();
    00082
    00083     const size_t GetNPrimitives() const { return m_voxels.Size(); }
    00084     const size_t GetNPrimitivesOnSurf() const { return m_numVoxelsOnSurface; }
    00085     const size_t GetNPrimitivesInsideSurf() const { return m_numVoxelsInsideSurface; }
    00086     const double GetEigenValue(AXIS axis) const { return m_D[axis][axis]; }
    00087     const double ComputeVolume() const { return m_unitVolume * m_voxels.Size(); }
    00088     const double ComputeMaxVolumeError() const { return m_unitVolume * m_numVoxelsOnSurface; }
    00089     const Vec3<short>& GetMinBBVoxels() const { return m_minBBVoxels; }
    00090     const Vec3<short>& GetMaxBBVoxels() const { return m_maxBBVoxels; }
    00091     const Vec3<double>& GetMinBB() const { return m_minBB; }
    00092     const double& GetScale() const { return m_scale; }
    00093     const double& GetUnitVolume() const { return m_unitVolume; }
    00094     Vec3<double> GetPoint(Vec3<short> voxel) const
    00095     {
    00096         return Vec3<double>(voxel[0] * m_scale + m_minBB[0],
    00097             voxel[1] * m_scale + m_minBB[1],
    00098             voxel[2] * m_scale + m_minBB[2]);
    00099     }
    00100     Vec3<double> GetPoint(const Voxel& voxel) const
    00101     {
    00102         return Vec3<double>(voxel.m_coord[0] * m_scale + m_minBB[0],
    00103             voxel.m_coord[1] * m_scale + m_minBB[1],
    00104             voxel.m_coord[2] * m_scale + m_minBB[2]);
    00105     }
    00106     Vec3<double> GetPoint(Vec3<double> voxel) const
    00107     {
    00108         return Vec3<double>(voxel[0] * m_scale + m_minBB[0],
    00109             voxel[1] * m_scale + m_minBB[1],
    00110             voxel[2] * m_scale + m_minBB[2]);
    00111     }
    00112     void GetPoints(const Voxel& voxel, Vec3<double>* const pts) const;
    00113     void ComputeConvexHull(Mesh& meshCH, const size_t sampling = 1) const;
    00114     void Clip(const Plane& plane, PrimitiveSet* const positivePart, PrimitiveSet* const negativePart) const;
    00115     void Intersect(const Plane& plane, SArray<Vec3<double> >* const positivePts,
    00116         SArray<Vec3<double> >* const negativePts, const size_t sampling) const;
    00117     void ComputeExteriorPoints(const Plane& plane, const Mesh& mesh,
    00118         SArray<Vec3<double> >* const exteriorPts) const;
    00119     void ComputeClippedVolumes(const Plane& plane, double& positiveVolume, double& negativeVolume) const;
    00120     void SelectOnSurface(PrimitiveSet* const onSurfP) const;
    00121     void ComputeBB();
    00122     void Convert(Mesh& mesh, const VOXEL_VALUE value) const;
    00123     void ComputePrincipalAxes();
    00124     PrimitiveSet* Create() const
    00125     {
    00126         return new VoxelSet();
    00127     }
    00128     void AlignToPrincipalAxes(){};
    00129     void RevertAlignToPrincipalAxes(){};
    00130     Voxel* const GetVoxels() { return m_voxels.Data(); }
    00131     const Voxel* const GetVoxels() const { return m_voxels.Data(); }
    00132
    00133 private:
    00134     size_t m_numVoxelsOnSurface;
    00135     size_t m_numVoxelsInsideSurface;
    00136     Vec3<double> m_minBB;
    00137     double m_scale;
    00138     SArray<Voxel, 8> m_voxels;
    00139     double m_unitVolume;
    00140     Vec3<double> m_minBBPts;
    00141     Vec3<double> m_maxBBPts;
    00142     Vec3<short> m_minBBVoxels;
    00143     Vec3<short> m_maxBBVoxels;
    00144     Vec3<short> m_barycenter;
    00145     double m_Q[3][3];
    00146     double m_D[3][3];
    00147     Vec3<double> m_barycenterPCA;
    00148 };
    00149
    00150 struct Tetrahedron {
    00151 public:
    00152     Vec3<double> m_pts[4];
    00153     unsigned char m_data;
    00154 };
    00155
    00157 class TetrahedronSet : public PrimitiveSet {
    00158     friend class Volume;
    00159
    00160 public:
    00162     ~TetrahedronSet(void);
    00164     TetrahedronSet();
    00165
    00166     const size_t GetNPrimitives() const { return m_tetrahedra.Size(); }
    00167     const size_t GetNPrimitivesOnSurf() const { return m_numTetrahedraOnSurface; }
    00168     const size_t GetNPrimitivesInsideSurf() const { return m_numTetrahedraInsideSurface; }
    00169     const Vec3<double>& GetMinBB() const { return m_minBB; }
    00170     const Vec3<double>& GetMaxBB() const { return m_maxBB; }
    00171     const Vec3<double>& GetBarycenter() const { return m_barycenter; }
    00172     const double GetEigenValue(AXIS axis) const { return m_D[axis][axis]; }
    00173     const double GetSacle() const { return m_scale; }
    00174     const double ComputeVolume() const;
    00175     const double ComputeMaxVolumeError() const;
    00176     void ComputeConvexHull(Mesh& meshCH, const size_t sampling = 1) const;
    00177     void ComputePrincipalAxes();
    00178     void AlignToPrincipalAxes();
    00179     void RevertAlignToPrincipalAxes();
    00180     void Clip(const Plane& plane, PrimitiveSet* const positivePart, PrimitiveSet* const negativePart) const;
    00181     void Intersect(const Plane& plane, SArray<Vec3<double> >* const positivePts,
    00182         SArray<Vec3<double> >* const negativePts, const size_t sampling) const;
    00183     void ComputeExteriorPoints(const Plane& plane, const Mesh& mesh,
    00184         SArray<Vec3<double> >* const exteriorPts) const;
    00185     void ComputeClippedVolumes(const Plane& plane, double& positiveVolume, double& negativeVolume) const;
    00186     void SelectOnSurface(PrimitiveSet* const onSurfP) const;
    00187     void ComputeBB();
    00188     void Convert(Mesh& mesh, const VOXEL_VALUE value) const;
    00189     inline bool Add(Tetrahedron& tetrahedron);
    00190     PrimitiveSet* Create() const
    00191     {
    00192         return new TetrahedronSet();
    00193     }
    00194     static const double EPS;
    00195
    00196 private:
    00197     void AddClippedTetrahedra(const Vec3<double> (&pts)[10], const int32_t nPts);
    00198
    00199     size_t m_numTetrahedraOnSurface;
    00200     size_t m_numTetrahedraInsideSurface;
    00201     double m_scale;
    00202     Vec3<double> m_minBB;
    00203     Vec3<double> m_maxBB;
    00204     Vec3<double> m_barycenter;
    00205     SArray<Tetrahedron, 8> m_tetrahedra;
    00206     double m_Q[3][3];
    00207     double m_D[3][3];
    00208 };
    00209
    00211 class Volume {
    00212 public:
    00214     ~Volume(void);
    00215
    00217     Volume();
    00218
    00220     template <class T>
    00221     void Voxelize(const T* const points, const uint32_t stridePoints, const uint32_t nPoints,
    00222         const int32_t* const triangles, const uint32_t strideTriangles, const uint32_t nTriangles,
    00223         const size_t dim, const Vec3<double>& barycenter, const double (&rot)[3][3]);
    00224     unsigned char& GetVoxel(const size_t i, const size_t j, const size_t k)
    00225     {
    00226         assert(i < m_dim[0] || i >= 0);
    00227         assert(j < m_dim[0] || j >= 0);
    00228         assert(k < m_dim[0] || k >= 0);
    00229         return m_data[i + j * m_dim[0] + k * m_dim[0] * m_dim[1]];
    00230     }
    00231     const unsigned char& GetVoxel(const size_t i, const size_t j, const size_t k) const
    00232     {
    00233         assert(i < m_dim[0] || i >= 0);
    00234         assert(j < m_dim[0] || j >= 0);
    00235         assert(k < m_dim[0] || k >= 0);
    00236         return m_data[i + j * m_dim[0] + k * m_dim[0] * m_dim[1]];
    00237     }
    00238     const size_t GetNPrimitivesOnSurf() const { return m_numVoxelsOnSurface; }
    00239     const size_t GetNPrimitivesInsideSurf() const { return m_numVoxelsInsideSurface; }
    00240     void Convert(Mesh& mesh, const VOXEL_VALUE value) const;
    00241     void Convert(VoxelSet& vset) const;
    00242     void Convert(TetrahedronSet& tset) const;
    00243     void AlignToPrincipalAxes(double (&rot)[3][3]) const;
    00244
    00245 private:
    00246     void FillOutsideSurface(const size_t i0, const size_t j0, const size_t k0, const size_t i1,
    00247         const size_t j1, const size_t k1);
    00248     void FillInsideSurface();
    00249     template <class T>
    00250     void ComputeBB(const T* const points, const uint32_t stridePoints, const uint32_t nPoints,
    00251         const Vec3<double>& barycenter, const double (&rot)[3][3]);
    00252     void Allocate();
    00253     void Free();
    00254
    00255     Vec3<double> m_minBB;
    00256     Vec3<double> m_maxBB;
    00257     double m_scale;
    00258     size_t m_dim[3]; //>! dim
    00259     size_t m_numVoxelsOnSurface;
    00260     size_t m_numVoxelsInsideSurface;
    00261     size_t m_numVoxelsOutsideSurface;
    00262     unsigned char* m_data;
    00263 };
    00264 int32_t TriBoxOverlap(const Vec3<double>& boxcenter, const Vec3<double>& boxhalfsize, const Vec3<double>& triver0,
    00265     const Vec3<double>& triver1, const Vec3<double>& triver2);
    00266 template <class T>
    00267 inline void ComputeAlignedPoint(const T* const points, const uint32_t idx, const Vec3<double>& barycenter,
    00268     const double (&rot)[3][3], Vec3<double>& pt){};
    00269 template <>
    00270 inline void ComputeAlignedPoint<float>(const float* const points, const uint32_t idx, const Vec3<double>& barycenter, const double (&rot)[3][3], Vec3<double>& pt)
    00271 {
    00272     double x = points[idx + 0] - barycenter[0];
    00273     double y = points[idx + 1] - barycenter[1];
    00274     double z = points[idx + 2] - barycenter[2];
    00275     pt[0] = rot[0][0] * x + rot[1][0] * y + rot[2][0] * z;
    00276     pt[1] = rot[0][1] * x + rot[1][1] * y + rot[2][1] * z;
    00277     pt[2] = rot[0][2] * x + rot[1][2] * y + rot[2][2] * z;
    00278 }
    00279 template <>
    00280 inline void ComputeAlignedPoint<double>(const double* const points, const uint32_t idx, const Vec3<double>& barycenter, const double (&rot)[3][3], Vec3<double>& pt)
    00281 {
    00282     double x = points[idx + 0] - barycenter[0];
    00283     double y = points[idx + 1] - barycenter[1];
    00284     double z = points[idx + 2] - barycenter[2];
    00285     pt[0] = rot[0][0] * x + rot[1][0] * y + rot[2][0] * z;
    00286     pt[1] = rot[0][1] * x + rot[1][1] * y + rot[2][1] * z;
    00287     pt[2] = rot[0][2] * x + rot[1][2] * y + rot[2][2] * z;
    00288 }
    00289 template <class T>
    00290 void Volume::ComputeBB(const T* const points, const uint32_t stridePoints, const uint32_t nPoints,
    00291     const Vec3<double>& barycenter, const double (&rot)[3][3])
    00292 {
    00293     Vec3<double> pt;
    00294     ComputeAlignedPoint(points, 0, barycenter, rot, pt);
    00295     m_maxBB = pt;
    00296     m_minBB = pt;
    00297     for (uint32_t v = 1; v < nPoints; ++v) {
    00298         ComputeAlignedPoint(points, v * stridePoints, barycenter, rot, pt);
    00299         for (int32_t i = 0; i < 3; ++i) {
    00300             if (pt[i] < m_minBB[i])
    00301                 m_minBB[i] = pt[i];
    00302             else if (pt[i] > m_maxBB[i])
    00303                 m_maxBB[i] = pt[i];
    00304         }
    00305     }
    00306 }
    00307 template <class T>
    00308 void Volume::Voxelize(const T* const points, const uint32_t stridePoints, const uint32_t nPoints,
    00309     const int32_t* const triangles, const uint32_t strideTriangles, const uint32_t nTriangles,
    00310     const size_t dim, const Vec3<double>& barycenter, const double (&rot)[3][3])
    00311 {
    00312     if (nPoints == 0) {
    00313         return;
    00314     }
    00315     ComputeBB(points, stridePoints, nPoints, barycenter, rot);
    00316
    00317     double d[3] = { m_maxBB[0] - m_minBB[0], m_maxBB[1] - m_minBB[1], m_maxBB[2] - m_minBB[2] };
    00318     double r;
    00319     if (d[0] > d[1] && d[0] > d[2]) {
    00320         r = d[0];
    00321         m_dim[0] = dim;
    00322         m_dim[1] = 2 + static_cast<size_t>(dim * d[1] / d[0]);
    00323         m_dim[2] = 2 + static_cast<size_t>(dim * d[2] / d[0]);
    00324     }
    00325     else if (d[1] > d[0] && d[1] > d[2]) {
    00326         r = d[1];
    00327         m_dim[1] = dim;
    00328         m_dim[0] = 2 + static_cast<size_t>(dim * d[0] / d[1]);
    00329         m_dim[2] = 2 + static_cast<size_t>(dim * d[2] / d[1]);
    00330     }
    00331     else {
    00332         r = d[2];
    00333         m_dim[2] = dim;
    00334         m_dim[0] = 2 + static_cast<size_t>(dim * d[0] / d[2]);
    00335         m_dim[1] = 2 + static_cast<size_t>(dim * d[1] / d[2]);
    00336     }
    00337
    00338     m_scale = r / (dim - 1);
    00339     double invScale = (dim - 1) / r;
    00340
    00341     Allocate();
    00342     m_numVoxelsOnSurface = 0;
    00343     m_numVoxelsInsideSurface = 0;
    00344     m_numVoxelsOutsideSurface = 0;
    00345
    00346     Vec3<double> p[3];
    00347     size_t i, j, k;
    00348     size_t i0, j0, k0;
    00349     size_t i1, j1, k1;
    00350     Vec3<double> boxcenter;
    00351     Vec3<double> pt;
    00352     const Vec3<double> boxhalfsize(0.5, 0.5, 0.5);
    00353     for (size_t t = 0, ti = 0; t < nTriangles; ++t, ti += strideTriangles) {
    00354         Vec3<int32_t> tri(triangles[ti + 0],
    00355             triangles[ti + 1],
    00356             triangles[ti + 2]);
    00357         for (int32_t c = 0; c < 3; ++c) {
    00358             ComputeAlignedPoint(points, tri[c] * stridePoints, barycenter, rot, pt);
    00359             p[c][0] = (pt[0] - m_minBB[0]) * invScale;
    00360             p[c][1] = (pt[1] - m_minBB[1]) * invScale;
    00361             p[c][2] = (pt[2] - m_minBB[2]) * invScale;
    00362             i = static_cast<size_t>(p[c][0] + 0.5);
    00363             j = static_cast<size_t>(p[c][1] + 0.5);
    00364             k = static_cast<size_t>(p[c][2] + 0.5);
    00365             assert(i < m_dim[0] && i >= 0 && j < m_dim[1] && j >= 0 && k < m_dim[2] && k >= 0);
    00366
    00367             if (c == 0) {
    00368                 i0 = i1 = i;
    00369                 j0 = j1 = j;
    00370                 k0 = k1 = k;
    00371             }
    00372             else {
    00373                 if (i < i0)
    00374                     i0 = i;
    00375                 if (j < j0)
    00376                     j0 = j;
    00377                 if (k < k0)
    00378                     k0 = k;
    00379                 if (i > i1)
    00380                     i1 = i;
    00381                 if (j > j1)
    00382                     j1 = j;
    00383                 if (k > k1)
    00384                     k1 = k;
    00385             }
    00386         }
    00387         if (i0 > 0)
    00388             --i0;
    00389         if (j0 > 0)
    00390             --j0;
    00391         if (k0 > 0)
    00392             --k0;
    00393         if (i1 < m_dim[0])
    00394             ++i1;
    00395         if (j1 < m_dim[1])
    00396             ++j1;
    00397         if (k1 < m_dim[2])
    00398             ++k1;
    00399         for (size_t i = i0; i < i1; ++i) {
    00400             boxcenter[0] = (double)i;
    00401             for (size_t j = j0; j < j1; ++j) {
    00402                 boxcenter[1] = (double)j;
    00403                 for (size_t k = k0; k < k1; ++k) {
    00404                     boxcenter[2] = (double)k;
    00405                     int32_t res = TriBoxOverlap(boxcenter, boxhalfsize, p[0], p[1], p[2]);
    00406                     unsigned char& value = GetVoxel(i, j, k);
    00407                     if (res == 1 && value == PRIMITIVE_UNDEFINED) {
    00408                         value = PRIMITIVE_ON_SURFACE;
    00409                         ++m_numVoxelsOnSurface;
    00410                     }
    00411                 }
    00412             }
    00413         }
    00414     }
    00415     FillOutsideSurface(0, 0, 0, m_dim[0], m_dim[1], 1);
    00416     FillOutsideSurface(0, 0, m_dim[2] - 1, m_dim[0], m_dim[1], m_dim[2]);
    00417     FillOutsideSurface(0, 0, 0, m_dim[0], 1, m_dim[2]);
    00418     FillOutsideSurface(0, m_dim[1] - 1, 0, m_dim[0], m_dim[1], m_dim[2]);
    00419     FillOutsideSurface(0, 0, 0, 1, m_dim[1], m_dim[2]);
    00420     FillOutsideSurface(m_dim[0] - 1, 0, 0, m_dim[0], m_dim[1], m_dim[2]);
    00421     FillInsideSurface();
    00422 }
    00423 }
    00424
    00425 #ifdef _MSC_VER
    00426 #pragma warning(pop)
    00427 #endif
    00428
    00429
    00430 #endif // VHACD_VOLUME_H

Copyright © 2015-2017 NVIDIA Corporation, 2701 San Tomas Expressway, Santa Clara, CA 95050 U.S.A. All rights reserved. www.nvidia.com