godot/thirdparty/recastnavigation/Recast/Source/RecastMeshDetail.cpp

//
// Copyright (c) 2009-2010 Mikko Mononen [email protected]
//
// 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 <float.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include "Recast.h"
#include "RecastAlloc.h"
#include "RecastAssert.h"


static const unsigned RC_UNSET_HEIGHT = …;

struct rcHeightPatch
{ … };


inline float vdot2(const float* a, const float* b)
{ … }

inline float vdistSq2(const float* p, const float* q)
{ … }

inline float vdist2(const float* p, const float* q)
{ … }

inline float vcross2(const float* p1, const float* p2, const float* p3)
{ … }

static bool circumCircle(const float* p1, const float* p2, const float* p3,
						 float* c, float& r)
{ … }

static float distPtTri(const float* p, const float* a, const float* b, const float* c)
{ … }

static float distancePtSeg(const float* pt, const float* p, const float* q)
{ … }

static float distancePtSeg2d(const float* pt, const float* p, const float* q)
{ … }

static float distToTriMesh(const float* p, const float* verts, const int /*nverts*/, const int* tris, const int ntris)
{ … }

static float distToPoly(int nvert, const float* verts, const float* p)
{ … }


static unsigned short getHeight(const float fx, const float fy, const float fz,
								const float /*cs*/, const float ics, const float ch,
								const int radius, const rcHeightPatch& hp)
{ … }


enum EdgeValues
{ … };

static int findEdge(const int* edges, int nedges, int s, int t)
{ … }

static int addEdge(rcContext* ctx, int* edges, int& nedges, const int maxEdges, int s, int t, int l, int r)
{ … }

static void updateLeftFace(int* e, int s, int t, int f)
{ … }

static int overlapSegSeg2d(const float* a, const float* b, const float* c, const float* d)
{ … }

static bool overlapEdges(const float* pts, const int* edges, int nedges, int s1, int t1)
{ … }

static void completeFacet(rcContext* ctx, const float* pts, int npts, int* edges, int& nedges, const int maxEdges, int& nfaces, int e)
{ … }

static void delaunayHull(rcContext* ctx, const int npts, const float* pts,
						 const int nhull, const int* hull,
						 rcIntArray& tris, rcIntArray& edges)
{ … }

// Calculate minimum extend of the polygon.
static float polyMinExtent(const float* verts, const int nverts)
{ … }

// Last time I checked the if version got compiled using cmov, which was a lot faster than module (with idiv).
inline int prev(int i, int n) { … }
inline int next(int i, int n) { … }

static void triangulateHull(const int /*nverts*/, const float* verts, const int nhull, const int* hull, const int nin, rcIntArray& tris)
{ … }


inline float getJitterX(const int i)
{ … }

inline float getJitterY(const int i)
{ … }

static bool buildPolyDetail(rcContext* ctx, const float* in, const int nin,
							const float sampleDist, const float sampleMaxError,
							const int heightSearchRadius, const rcCompactHeightfield& chf,
							const rcHeightPatch& hp, float* verts, int& nverts,
							rcIntArray& tris, rcIntArray& edges, rcIntArray& samples)
{ … }

static void seedArrayWithPolyCenter(rcContext* ctx, const rcCompactHeightfield& chf,
									const unsigned short* poly, const int npoly,
									const unsigned short* verts, const int bs,
									rcHeightPatch& hp, rcIntArray& array)
{ … }


static void push3(rcIntArray& queue, int v1, int v2, int v3)
{ … }

static void getHeightData(rcContext* ctx, const rcCompactHeightfield& chf,
						  const unsigned short* poly, const int npoly,
						  const unsigned short* verts, const int bs,
						  rcHeightPatch& hp, rcIntArray& queue,
						  int region)
{ … }

static unsigned char getEdgeFlags(const float* va, const float* vb,
								  const float* vpoly, const int npoly)
{ … }

static unsigned char getTriFlags(const float* va, const float* vb, const float* vc,
								 const float* vpoly, const int npoly)
{ … }

/// @par
///
/// See the #rcConfig documentation for more information on the configuration parameters.
///
/// @see rcAllocPolyMeshDetail, rcPolyMesh, rcCompactHeightfield, rcPolyMeshDetail, rcConfig
bool rcBuildPolyMeshDetail(rcContext* ctx, const rcPolyMesh& mesh, const rcCompactHeightfield& chf,
						   const float sampleDist, const float sampleMaxError,
						   rcPolyMeshDetail& dmesh)
{ … }

/// @see rcAllocPolyMeshDetail, rcPolyMeshDetail
bool rcMergePolyMeshDetails(rcContext* ctx, rcPolyMeshDetail** meshes, const int nmeshes, rcPolyMeshDetail& mesh)
{ … }