godot/thirdparty/vhacd/src/VHACD.cpp

/* Copyright (c) 2011 Khaled Mamou (kmamou at gmail dot com)
 All rights reserved.
 
 
 Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
 
 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
 
 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.
 
 3. The names of the contributors may not be used to endorse or promote products derived from this software without specific prior written permission.
 
 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.
 */

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <algorithm>
#include <fstream>
#include <iomanip>
#include <limits>
#include <sstream>
#if _OPENMP
#include <omp.h>
#endif // _OPENMP

#include "../public/VHACD.h"
#include "btConvexHullComputer.h"
#include "vhacdICHull.h"
#include "vhacdMesh.h"
#include "vhacdSArray.h"
#include "vhacdTimer.h"
#include "vhacdVHACD.h"
#include "vhacdVector.h"
#include "vhacdVolume.h"
#include "FloatMath.h"

#define MAX(a, b) …
#define MIN(a, b) …
#define ABS(a) …
#define ZSGN(a) …
#define MAX_DOUBLE …

#ifdef _MSC_VER
#pragma warning(disable:4267 4100 4244 4456)
#endif

#ifdef USE_SSE
#include <immintrin.h>

const int32_t SIMD_WIDTH = 4;
inline int32_t FindMinimumElement(const float* const d, float* const _, const int32_t n)
{
    // Min within vectors
    __m128 min_i = _mm_set1_ps(-1.0f);
    __m128 min_v = _mm_set1_ps(std::numeric_limits<float>::max());
    for (int32_t i = 0; i <= n - SIMD_WIDTH; i += SIMD_WIDTH) {
        const __m128 data = _mm_load_ps(&d[i]);
        const __m128 pred = _mm_cmplt_ps(data, min_v);

        min_i = _mm_blendv_ps(min_i, _mm_set1_ps(i), pred);
        min_v = _mm_min_ps(data, min_v);
    }

    /* Min within vector */
    const __m128 min1 = _mm_shuffle_ps(min_v, min_v, _MM_SHUFFLE(1, 0, 3, 2));
    const __m128 min2 = _mm_min_ps(min_v, min1);
    const __m128 min3 = _mm_shuffle_ps(min2, min2, _MM_SHUFFLE(0, 1, 0, 1));
    const __m128 min4 = _mm_min_ps(min2, min3);
    float min_d = _mm_cvtss_f32(min4);

    // Min index
    const int32_t min_idx = __builtin_ctz(_mm_movemask_ps(_mm_cmpeq_ps(min_v, min4)));
    int32_t ret = min_i[min_idx] + min_idx;

    // Trailing elements
    for (int32_t i = (n & ~(SIMD_WIDTH - 1)); i < n; ++i) {
        if (d[i] < min_d) {
            min_d = d[i];
            ret = i;
        }
    }

    *m = min_d;
    return ret;
}

inline int32_t FindMinimumElement(const float* const d, float* const m, const int32_t begin, const int32_t end)
{
    // Leading elements
    int32_t min_i = -1;
    float min_d = std::numeric_limits<float>::max();
    const int32_t aligned = (begin & ~(SIMD_WIDTH - 1)) + ((begin & (SIMD_WIDTH - 1)) ? SIMD_WIDTH : 0);
    for (int32_t i = begin; i < std::min(end, aligned); ++i) {
        if (d[i] < min_d) {
            min_d = d[i];
            min_i = i;
        }
    }

    // Middle and trailing elements
    float r_m = std::numeric_limits<float>::max();
    const int32_t n = end - aligned;
    const int32_t r_i = (n > 0) ? FindMinimumElement(&d[aligned], &r_m, n) : 0;

    // Pick the lowest
    if (r_m < min_d) {
        *m = r_m;
        return r_i + aligned;
    }
    else {
        *m = min_d;
        return min_i;
    }
}
#else
inline int32_t FindMinimumElement(const float* const d, float* const m, const int32_t begin, const int32_t end)
{ … }
#endif

//#define OCL_SOURCE_FROM_FILE
#ifndef OCL_SOURCE_FROM_FILE
const char* oclProgramSource = …;
#endif //OCL_SOURCE_FROM_FILE

namespace VHACD {
IVHACD* CreateVHACD(void)
{ … }
bool VHACD::OCLInit(void* const oclDevice, IUserLogger* const logger)
{ … }
bool VHACD::OCLRelease(IUserLogger* const logger)
{ … }
void VHACD::ComputePrimitiveSet(const Parameters& params)
{ … }
bool VHACD::Compute(const double* const points, const uint32_t nPoints,
    const uint32_t* const triangles,const uint32_t nTriangles, const Parameters& params)
{ … }
bool VHACD::Compute(const float* const points,const uint32_t nPoints,
    const uint32_t* const triangles,const uint32_t nTriangles, const Parameters& params)
{ … }
double ComputePreferredCuttingDirection(const PrimitiveSet* const tset, Vec3<double>& dir)
{ … }
void ComputeAxesAlignedClippingPlanes(const VoxelSet& vset, const short downsampling, SArray<Plane>& planes)
{ … }
void ComputeAxesAlignedClippingPlanes(const TetrahedronSet& tset, const short downsampling, SArray<Plane>& planes)
{ … }
void RefineAxesAlignedClippingPlanes(const VoxelSet& vset, const Plane& bestPlane, const short downsampling,
    SArray<Plane>& planes)
{ … }
void RefineAxesAlignedClippingPlanes(const TetrahedronSet& tset, const Plane& bestPlane, const short downsampling,
    SArray<Plane>& planes)
{ … }
inline double ComputeLocalConcavity(const double volume, const double volumeCH)
{ … }
inline double ComputeConcavity(const double volume, const double volumeCH, const double volume0)
{ … }

//#define DEBUG_TEMP
void VHACD::ComputeBestClippingPlane(const PrimitiveSet* inputPSet, const double volume, const SArray<Plane>& planes,
    const Vec3<double>& preferredCuttingDirection, const double w, const double alpha, const double beta,
    const int32_t convexhullDownsampling, const double progress0, const double progress1, Plane& bestPlane,
    double& minConcavity, const Parameters& params)
{ … }
void VHACD::ComputeACD(const Parameters& params)
{ … }
void AddPoints(const Mesh* const mesh, SArray<Vec3<double> >& pts)
{ … }
void ComputeConvexHull(const Mesh* const ch1, const Mesh* const ch2, SArray<Vec3<double> >& pts, Mesh* const combinedCH)
{ … }
void VHACD::MergeConvexHulls(const Parameters& params)
{ … }
void VHACD::SimplifyConvexHull(Mesh* const ch, const size_t nvertices, const double minVolume)
{ … }
void VHACD::SimplifyConvexHulls(const Parameters& params)
{ … }

bool VHACD::ComputeCenterOfMass(double centerOfMass[3]) const
{ … }

} // end of VHACD namespace