godot/thirdparty/vhacd/src/btConvexHullComputer.cpp

/*
Copyright (c) 2011 Ole Kniemeyer, MAXON, www.maxon.net

This software is provided 'as-is', without any express or implied warranty.
In no event will the authors be held liable for any damages arising from the use of this software.
Permission is granted to anyone to use this software for any purpose, 
including commercial applications, and to alter it and redistribute it freely, 
subject to the following restrictions:

1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
3. This notice may not be removed or altered from any source distribution.
*/

#include <string.h>

#include "btAlignedObjectArray.h"
#include "btConvexHullComputer.h"
#include "btMinMax.h"
#include "btVector3.h"

#ifdef __GNUC__
#include <stdint.h>
#elif defined(_MSC_VER)
typedef __int32 int32_t;
typedef __int64 int64_t;
typedef unsigned __int32 uint32_t;
typedef unsigned __int64 uint64_t;
#else
typedef int32_t int32_t;
typedef long long int32_t int64_t;
typedef uint32_t uint32_t;
typedef unsigned long long int32_t uint64_t;
#endif

#ifdef _MSC_VER
#pragma warning(disable:4458)
#endif

//The definition of USE_X86_64_ASM is moved into the build system. You can enable it manually by commenting out the following lines
//#if (defined(__GNUC__) && defined(__x86_64__) && !defined(__ICL))  // || (defined(__ICL) && defined(_M_X64))   bug in Intel compiler, disable inline assembly
//	#define USE_X86_64_ASM
//#endif

//#define DEBUG_CONVEX_HULL
//#define SHOW_ITERATIONS

#if defined(DEBUG_CONVEX_HULL) || defined(SHOW_ITERATIONS)
#include <stdio.h>
#endif

// -- GODOT start --
namespace VHACD {
// -- GODOT end --

// Convex hull implementation based on Preparata and Hong
// Ole Kniemeyer, MAXON Computer GmbH
class btConvexHullInternal { … };

btConvexHullInternal::Int128 btConvexHullInternal::Int128::operator*(int64_t b) const
{ … }

btConvexHullInternal::Int128 btConvexHullInternal::Int128::mul(int64_t a, int64_t b)
{ … }

btConvexHullInternal::Int128 btConvexHullInternal::Int128::mul(uint64_t a, uint64_t b)
{ … }

int32_t btConvexHullInternal::Rational64::compare(const Rational64& b) const
{ … }

int32_t btConvexHullInternal::Rational128::compare(const Rational128& b) const
{ … }

int32_t btConvexHullInternal::Rational128::compare(int64_t b) const
{ … }

btConvexHullInternal::Edge* btConvexHullInternal::newEdgePair(Vertex* from, Vertex* to)
{ … }

bool btConvexHullInternal::mergeProjection(IntermediateHull& h0, IntermediateHull& h1, Vertex*& c0, Vertex*& c1)
{ … }

void btConvexHullInternal::computeInternal(int32_t start, int32_t end, IntermediateHull& result)
{ … }

#ifdef DEBUG_CONVEX_HULL
void btConvexHullInternal::IntermediateHull::print()
{
    printf("    Hull\n");
    for (Vertex* v = minXy; v;) {
        printf("      ");
        v->print();
        if (v == maxXy) {
            printf(" maxXy");
        }
        if (v == minYx) {
            printf(" minYx");
        }
        if (v == maxYx) {
            printf(" maxYx");
        }
        if (v->next->prev != v) {
            printf(" Inconsistency");
        }
        printf("\n");
        v = v->next;
        if (v == minXy) {
            break;
        }
    }
    if (minXy) {
        minXy->copy = (minXy->copy == -1) ? -2 : -1;
        minXy->printGraph();
    }
}

void btConvexHullInternal::Vertex::printGraph()
{
    print();
    printf("\nEdges\n");
    Edge* e = edges;
    if (e) {
        do {
            e->print();
            printf("\n");
            e = e->next;
        } while (e != edges);
        do {
            Vertex* v = e->target;
            if (v->copy != copy) {
                v->copy = copy;
                v->printGraph();
            }
            e = e->next;
        } while (e != edges);
    }
}
#endif

btConvexHullInternal::Orientation btConvexHullInternal::getOrientation(const Edge* prev, const Edge* next, const Point32& s, const Point32& t)
{ … }

btConvexHullInternal::Edge* btConvexHullInternal::findMaxAngle(bool ccw, const Vertex* start, const Point32& s, const Point64& rxs, const Point64& sxrxs, Rational64& minCot)
{ … }

void btConvexHullInternal::findEdgeForCoplanarFaces(Vertex* c0, Vertex* c1, Edge*& e0, Edge*& e1, Vertex* stop0, Vertex* stop1)
{ … }

void btConvexHullInternal::merge(IntermediateHull& h0, IntermediateHull& h1)
{ … }

static bool pointCmp(const btConvexHullInternal::Point32& p, const btConvexHullInternal::Point32& q)
{ … }

void btConvexHullInternal::compute(const void* coords, bool doubleCoords, int32_t stride, int32_t count)
{ … }

btVector3 btConvexHullInternal::toBtVector(const Point32& v)
{ … }

btVector3 btConvexHullInternal::getBtNormal(Face* face)
{ … }

btVector3 btConvexHullInternal::getCoordinates(const Vertex* v)
{ … }

btScalar btConvexHullInternal::shrink(btScalar amount, btScalar clampAmount)
{ … }

bool btConvexHullInternal::shiftFace(Face* face, btScalar amount, btAlignedObjectArray<Vertex*> stack)
{ … }

static int32_t getVertexCopy(btConvexHullInternal::Vertex* vertex, btAlignedObjectArray<btConvexHullInternal::Vertex*>& vertices)
{ … }

btScalar btConvexHullComputer::compute(const void* coords, bool doubleCoords, int32_t stride, int32_t count, btScalar shrink, btScalar shrinkClamp)
{ … }

// -- GODOT start --
}; // namespace VHACD
// -- GODOT end --