godot/thirdparty/recastnavigation/Recast/Source/RecastContour.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 <math.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include "Recast.h"
#include "RecastAlloc.h"
#include "RecastAssert.h"


static int getCornerHeight(int x, int y, int i, int dir,
						   const rcCompactHeightfield& chf,
						   bool& isBorderVertex)
{ … }

static void walkContour(int x, int y, int i,
						const rcCompactHeightfield& chf,
						unsigned char* flags, rcIntArray& points)
{ … }

static float distancePtSeg(const int x, const int z,
						   const int px, const int pz,
						   const int qx, const int qz)
{ … }

static void simplifyContour(rcIntArray& points, rcIntArray& simplified,
							const float maxError, const int maxEdgeLen, const int buildFlags)
{ … }

static int calcAreaOfPolygon2D(const int* verts, const int nverts)
{ … }

// TODO: these are the same as in RecastMesh.cpp, consider using the same.
// 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) { … }

inline int area2(const int* a, const int* b, const int* c)
{ … }

//	Exclusive or: true iff exactly one argument is true.
//	The arguments are negated to ensure that they are 0/1
//	values.  Then the bitwise Xor operator may apply.
//	(This idea is due to Michael Baldwin.)
inline bool xorb(bool x, bool y)
{ … }

// Returns true iff c is strictly to the left of the directed
// line through a to b.
inline bool left(const int* a, const int* b, const int* c)
{ … }

inline bool leftOn(const int* a, const int* b, const int* c)
{ … }

inline bool collinear(const int* a, const int* b, const int* c)
{ … }

//	Returns true iff ab properly intersects cd: they share
//	a point interior to both segments.  The properness of the
//	intersection is ensured by using strict leftness.
static bool intersectProp(const int* a, const int* b, const int* c, const int* d)
{ … }

// Returns T iff (a,b,c) are collinear and point c lies
// on the closed segement ab.
static bool between(const int* a, const int* b, const int* c)
{ … }

// Returns true iff segments ab and cd intersect, properly or improperly.
static bool intersect(const int* a, const int* b, const int* c, const int* d)
{ … }

static bool vequal(const int* a, const int* b)
{ … }

static bool intersectSegContour(const int* d0, const int* d1, int i, int n, const int* verts)
{ … }

static bool	inCone(int i, int n, const int* verts, const int* pj)
{ … }


static void removeDegenerateSegments(rcIntArray& simplified)
{ … }


static bool mergeContours(rcContour& ca, rcContour& cb, int ia, int ib)
{ … }

struct rcContourHole
{ … };

struct rcContourRegion
{ … };

struct rcPotentialDiagonal
{ … };

// Finds the lowest leftmost vertex of a contour.
static void findLeftMostVertex(rcContour* contour, int* minx, int* minz, int* leftmost)
{ … }

static int compareHoles(const void* va, const void* vb)
{ … }


static int compareDiagDist(const void* va, const void* vb)
{ … }


static void mergeRegionHoles(rcContext* ctx, rcContourRegion& region)
{ … }


/// @par
///
/// The raw contours will match the region outlines exactly. The @p maxError and @p maxEdgeLen
/// parameters control how closely the simplified contours will match the raw contours.
///
/// Simplified contours are generated such that the vertices for portals between areas match up.
/// (They are considered mandatory vertices.)
///
/// Setting @p maxEdgeLength to zero will disabled the edge length feature.
///
/// See the #rcConfig documentation for more information on the configuration parameters.
///
/// @see rcAllocContourSet, rcCompactHeightfield, rcContourSet, rcConfig
bool rcBuildContours(rcContext* ctx, const rcCompactHeightfield& chf,
					 const float maxError, const int maxEdgeLen,
					 rcContourSet& cset, const int buildFlags)
{ … }