summaryrefslogtreecommitdiff
path: root/thirdparty/misc
diff options
context:
space:
mode:
Diffstat (limited to 'thirdparty/misc')
-rw-r--r--thirdparty/misc/easing_equations.cpp39
-rw-r--r--thirdparty/misc/open-simplex-noise.c31
-rw-r--r--thirdparty/misc/open-simplex-noise.h6
-rw-r--r--thirdparty/misc/patches/polypartition-godot-types.patch819
-rw-r--r--thirdparty/misc/pcg.cpp33
-rw-r--r--thirdparty/misc/pcg.h1
-rw-r--r--thirdparty/misc/polypartition.cpp1849
-rw-r--r--thirdparty/misc/polypartition.h378
-rw-r--r--thirdparty/misc/r128.h10
-rw-r--r--thirdparty/misc/smolv.cpp2108
-rw-r--r--thirdparty/misc/smolv.h169
-rw-r--r--thirdparty/misc/stb_vorbis.c18
-rw-r--r--thirdparty/misc/triangulator.cpp1550
-rw-r--r--thirdparty/misc/triangulator.h306
14 files changed, 5419 insertions, 1898 deletions
diff --git a/thirdparty/misc/easing_equations.cpp b/thirdparty/misc/easing_equations.cpp
index bc84564b19..ce32c1a362 100644
--- a/thirdparty/misc/easing_equations.cpp
+++ b/thirdparty/misc/easing_equations.cpp
@@ -188,7 +188,8 @@ static real_t out_in(real_t t, real_t b, real_t c, real_t d) {
///////////////////////////////////////////////////////////////////////////
namespace cubic {
static real_t in(real_t t, real_t b, real_t c, real_t d) {
- return c * (t /= d) * t * t + b;
+ t /= d;
+ return c * t * t * t + b;
}
static real_t out(real_t t, real_t b, real_t c, real_t d) {
@@ -197,8 +198,10 @@ static real_t out(real_t t, real_t b, real_t c, real_t d) {
}
static real_t in_out(real_t t, real_t b, real_t c, real_t d) {
- if ((t /= d / 2) < 1) return c / 2 * t * t * t + b;
- return c / 2 * ((t -= 2) * t * t + 2) + b;
+ t /= d / 2;
+ if (t < 1) return c / 2 * t * t * t + b;
+ t -= 2;
+ return c / 2 * (t * t * t + 2) + b;
}
static real_t out_in(real_t t, real_t b, real_t c, real_t d) {
@@ -210,16 +213,22 @@ static real_t out_in(real_t t, real_t b, real_t c, real_t d) {
///////////////////////////////////////////////////////////////////////////
namespace circ {
static real_t in(real_t t, real_t b, real_t c, real_t d) {
- return -c * (sqrt(1 - (t /= d) * t) - 1) + b; // TODO: ehrich: operation with t is undefined
+ t /= d;
+ return -c * (sqrt(1 - t * t) - 1) + b;
}
static real_t out(real_t t, real_t b, real_t c, real_t d) {
- return c * sqrt(1 - (t = t / d - 1) * t) + b; // TODO: ehrich: operation with t is undefined
+ t = t / d - 1;
+ return c * sqrt(1 - t * t) + b;
}
static real_t in_out(real_t t, real_t b, real_t c, real_t d) {
- if ((t /= d / 2) < 1) return -c / 2 * (sqrt(1 - t * t) - 1) + b;
- return c / 2 * (sqrt(1 - t * (t -= 2)) + 1) + b; // TODO: ehrich: operation with t is undefined
+ t /= d / 2;
+ if (t < 1) {
+ return -c / 2 * (sqrt(1 - t * t) - 1) + b;
+ }
+ t -= 2;
+ return c / 2 * (sqrt(1 - t * t) + 1) + b;
}
static real_t out_in(real_t t, real_t b, real_t c, real_t d) {
@@ -271,14 +280,16 @@ static real_t in(real_t t, real_t b, real_t c, real_t d) {
static real_t out(real_t t, real_t b, real_t c, real_t d) {
float s = 1.70158f;
- return c * ((t = t / d - 1) * t * ((s + 1) * t + s) + 1) + b; // TODO: ehrich: operation with t is undefined
+ t = t / d - 1;
+ return c * (t * t * ((s + 1) * t + s) + 1) + b;
}
static real_t in_out(real_t t, real_t b, real_t c, real_t d) {
- float s = 1.70158f;
- if ((t /= d / 2) < 1) return c / 2 * (t * t * (((s *= (1.525f)) + 1) * t - s)) + b; // TODO: ehrich: operation with s is undefined
- float postFix = t -= 2;
- return c / 2 * ((postFix)*t * (((s *= (1.525f)) + 1) * t + s) + 2) + b; // TODO: ehrich: operation with s is undefined
+ float s = 1.70158f * 1.525f;
+ t /= d / 2;
+ if (t < 1) return c / 2 * (t * t * ((s + 1) * t - s)) + b;
+ t -= 2;
+ return c / 2 * (t * t * ((s + 1) * t + s) + 2) + b;
}
static real_t out_in(real_t t, real_t b, real_t c, real_t d) {
@@ -286,7 +297,7 @@ static real_t out_in(real_t t, real_t b, real_t c, real_t d) {
}
}; // namespace back
-Tween::interpolater Tween::interpolaters[Tween::TRANS_COUNT][Tween::EASE_COUNT] = {
+Tween::interpolater Tween::interpolaters[Tween::TRANS_MAX][Tween::EASE_MAX] = {
{ &linear::in, &linear::out, &linear::in_out, &linear::out_in },
{ &sine::in, &sine::out, &sine::in_out, &sine::out_in },
{ &quint::in, &quint::out, &quint::in_out, &quint::out_in },
@@ -300,7 +311,7 @@ Tween::interpolater Tween::interpolaters[Tween::TRANS_COUNT][Tween::EASE_COUNT]
{ &back::in, &back::out, &back::in_out, &back::out_in },
};
-real_t Tween::_run_equation(TransitionType p_trans_type, EaseType p_ease_type, real_t t, real_t b, real_t c, real_t d) {
+real_t Tween::run_equation(TransitionType p_trans_type, EaseType p_ease_type, real_t t, real_t b, real_t c, real_t d) {
interpolater cb = interpolaters[p_trans_type][p_ease_type];
ERR_FAIL_COND_V(cb == NULL, b);
diff --git a/thirdparty/misc/open-simplex-noise.c b/thirdparty/misc/open-simplex-noise.c
index 42f2fbb5be..44a072cad1 100644
--- a/thirdparty/misc/open-simplex-noise.c
+++ b/thirdparty/misc/open-simplex-noise.c
@@ -100,27 +100,27 @@ static const signed char gradients4D[] = {
-3, -1, -1, -1, -1, -3, -1, -1, -1, -1, -3, -1, -1, -1, -1, -3,
};
-static double extrapolate2(struct osn_context *ctx, int xsb, int ysb, double dx, double dy)
+static double extrapolate2(const struct osn_context *ctx, int xsb, int ysb, double dx, double dy)
{
- int16_t *perm = ctx->perm;
+ const int16_t *perm = ctx->perm;
int index = perm[(perm[xsb & 0xFF] + ysb) & 0xFF] & 0x0E;
return gradients2D[index] * dx
+ gradients2D[index + 1] * dy;
}
-static double extrapolate3(struct osn_context *ctx, int xsb, int ysb, int zsb, double dx, double dy, double dz)
+static double extrapolate3(const struct osn_context *ctx, int xsb, int ysb, int zsb, double dx, double dy, double dz)
{
- int16_t *perm = ctx->perm;
- int16_t *permGradIndex3D = ctx->permGradIndex3D;
+ const int16_t *perm = ctx->perm;
+ const int16_t *permGradIndex3D = ctx->permGradIndex3D;
int index = permGradIndex3D[(perm[(perm[xsb & 0xFF] + ysb) & 0xFF] + zsb) & 0xFF];
return gradients3D[index] * dx
+ gradients3D[index + 1] * dy
+ gradients3D[index + 2] * dz;
}
-static double extrapolate4(struct osn_context *ctx, int xsb, int ysb, int zsb, int wsb, double dx, double dy, double dz, double dw)
+static double extrapolate4(const struct osn_context *ctx, int xsb, int ysb, int zsb, int wsb, double dx, double dy, double dz, double dw)
{
- int16_t *perm = ctx->perm;
+ const int16_t *perm = ctx->perm;
int index = perm[(perm[(perm[(perm[xsb & 0xFF] + ysb) & 0xFF] + zsb) & 0xFF] + wsb) & 0xFF] & 0xFC;
return gradients4D[index] * dx
+ gradients4D[index + 1] * dy
@@ -189,14 +189,15 @@ int open_simplex_noise(int64_t seed, struct osn_context *ctx)
permGradIndex3D = ctx->permGradIndex3D;
// -- GODOT end --
+ uint64_t seedU = seed;
for (i = 0; i < 256; i++)
source[i] = (int16_t) i;
- seed = seed * 6364136223846793005LL + 1442695040888963407LL;
- seed = seed * 6364136223846793005LL + 1442695040888963407LL;
- seed = seed * 6364136223846793005LL + 1442695040888963407LL;
+ seedU = seedU * 6364136223846793005ULL + 1442695040888963407ULL;
+ seedU = seedU * 6364136223846793005ULL + 1442695040888963407ULL;
+ seedU = seedU * 6364136223846793005ULL + 1442695040888963407ULL;
for (i = 255; i >= 0; i--) {
- seed = seed * 6364136223846793005LL + 1442695040888963407LL;
- r = (int)((seed + 31) % (i + 1));
+ seedU = seedU * 6364136223846793005ULL + 1442695040888963407ULL;
+ r = (int)((seedU + 31) % (i + 1));
if (r < 0)
r += (i + 1);
perm[i] = source[r];
@@ -226,7 +227,7 @@ void open_simplex_noise_free(struct osn_context *ctx)
// -- GODOT end --
/* 2D OpenSimplex (Simplectic) Noise. */
-double open_simplex_noise2(struct osn_context *ctx, double x, double y)
+double open_simplex_noise2(const struct osn_context *ctx, double x, double y)
{
/* Place input coordinates onto grid. */
@@ -354,7 +355,7 @@ double open_simplex_noise2(struct osn_context *ctx, double x, double y)
/*
* 3D OpenSimplex (Simplectic) Noise
*/
-double open_simplex_noise3(struct osn_context *ctx, double x, double y, double z)
+double open_simplex_noise3(const struct osn_context *ctx, double x, double y, double z)
{
/* Place input coordinates on simplectic honeycomb. */
@@ -927,7 +928,7 @@ double open_simplex_noise3(struct osn_context *ctx, double x, double y, double z
/*
* 4D OpenSimplex (Simplectic) Noise.
*/
-double open_simplex_noise4(struct osn_context *ctx, double x, double y, double z, double w)
+double open_simplex_noise4(const struct osn_context *ctx, double x, double y, double z, double w)
{
double uins;
double dx1, dy1, dz1, dw1;
diff --git a/thirdparty/misc/open-simplex-noise.h b/thirdparty/misc/open-simplex-noise.h
index 89e0df8218..fd9248c3a1 100644
--- a/thirdparty/misc/open-simplex-noise.h
+++ b/thirdparty/misc/open-simplex-noise.h
@@ -47,9 +47,9 @@ int open_simplex_noise(int64_t seed, struct osn_context *ctx);
//int open_simplex_noise_init_perm(struct osn_context *ctx, int16_t p[], int nelements);
// -- GODOT end --
void open_simplex_noise_free(struct osn_context *ctx);
-double open_simplex_noise2(struct osn_context *ctx, double x, double y);
-double open_simplex_noise3(struct osn_context *ctx, double x, double y, double z);
-double open_simplex_noise4(struct osn_context *ctx, double x, double y, double z, double w);
+double open_simplex_noise2(const struct osn_context *ctx, double x, double y);
+double open_simplex_noise3(const struct osn_context *ctx, double x, double y, double z);
+double open_simplex_noise4(const struct osn_context *ctx, double x, double y, double z, double w);
#ifdef __cplusplus
}
diff --git a/thirdparty/misc/patches/polypartition-godot-types.patch b/thirdparty/misc/patches/polypartition-godot-types.patch
new file mode 100644
index 0000000000..782f02e8dc
--- /dev/null
+++ b/thirdparty/misc/patches/polypartition-godot-types.patch
@@ -0,0 +1,819 @@
+diff --git a/thirdparty/misc/polypartition.cpp b/thirdparty/misc/polypartition.cpp
+index 3a8a6efa83..5e94793b79 100644
+--- a/thirdparty/misc/polypartition.cpp
++++ b/thirdparty/misc/polypartition.cpp
+@@ -23,10 +23,7 @@
+
+ #include "polypartition.h"
+
+-#include <math.h>
+-#include <string.h>
+ #include <algorithm>
+-#include <vector>
+
+ TPPLPoly::TPPLPoly() {
+ hole = false;
+@@ -186,7 +183,7 @@ int TPPLPartition::Intersects(TPPLPoint &p11, TPPLPoint &p12, TPPLPoint &p21, TP
+ // Removes holes from inpolys by merging them with non-holes.
+ int TPPLPartition::RemoveHoles(TPPLPolyList *inpolys, TPPLPolyList *outpolys) {
+ TPPLPolyList polys;
+- TPPLPolyList::iterator holeiter, polyiter, iter, iter2;
++ TPPLPolyList::Element *holeiter, *polyiter, *iter, *iter2;
+ long i, i2, holepointindex, polypointindex;
+ TPPLPoint holepoint, polypoint, bestpolypoint;
+ TPPLPoint linep1, linep2;
+@@ -198,15 +195,15 @@ int TPPLPartition::RemoveHoles(TPPLPolyList *inpolys, TPPLPolyList *outpolys) {
+
+ // Check for the trivial case of no holes.
+ hasholes = false;
+- for (iter = inpolys->begin(); iter != inpolys->end(); iter++) {
+- if (iter->IsHole()) {
++ for (iter = inpolys->front(); iter; iter = iter->next()) {
++ if (iter->get().IsHole()) {
+ hasholes = true;
+ break;
+ }
+ }
+ if (!hasholes) {
+- for (iter = inpolys->begin(); iter != inpolys->end(); iter++) {
+- outpolys->push_back(*iter);
++ for (iter = inpolys->front(); iter; iter = iter->next()) {
++ outpolys->push_back(iter->get());
+ }
+ return 1;
+ }
+@@ -216,8 +213,8 @@ int TPPLPartition::RemoveHoles(TPPLPolyList *inpolys, TPPLPolyList *outpolys) {
+ while (1) {
+ // Find the hole point with the largest x.
+ hasholes = false;
+- for (iter = polys.begin(); iter != polys.end(); iter++) {
+- if (!iter->IsHole()) {
++ for (iter = polys.front(); iter; iter = iter->next()) {
++ if (!iter->get().IsHole()) {
+ continue;
+ }
+
+@@ -227,8 +224,8 @@ int TPPLPartition::RemoveHoles(TPPLPolyList *inpolys, TPPLPolyList *outpolys) {
+ holepointindex = 0;
+ }
+
+- for (i = 0; i < iter->GetNumPoints(); i++) {
+- if (iter->GetPoint(i).x > holeiter->GetPoint(holepointindex).x) {
++ for (i = 0; i < iter->get().GetNumPoints(); i++) {
++ if (iter->get().GetPoint(i).x > holeiter->get().GetPoint(holepointindex).x) {
+ holeiter = iter;
+ holepointindex = i;
+ }
+@@ -237,24 +234,24 @@ int TPPLPartition::RemoveHoles(TPPLPolyList *inpolys, TPPLPolyList *outpolys) {
+ if (!hasholes) {
+ break;
+ }
+- holepoint = holeiter->GetPoint(holepointindex);
++ holepoint = holeiter->get().GetPoint(holepointindex);
+
+ pointfound = false;
+- for (iter = polys.begin(); iter != polys.end(); iter++) {
+- if (iter->IsHole()) {
++ for (iter = polys.front(); iter; iter = iter->next()) {
++ if (iter->get().IsHole()) {
+ continue;
+ }
+- for (i = 0; i < iter->GetNumPoints(); i++) {
+- if (iter->GetPoint(i).x <= holepoint.x) {
++ for (i = 0; i < iter->get().GetNumPoints(); i++) {
++ if (iter->get().GetPoint(i).x <= holepoint.x) {
+ continue;
+ }
+- if (!InCone(iter->GetPoint((i + iter->GetNumPoints() - 1) % (iter->GetNumPoints())),
+- iter->GetPoint(i),
+- iter->GetPoint((i + 1) % (iter->GetNumPoints())),
++ if (!InCone(iter->get().GetPoint((i + iter->get().GetNumPoints() - 1) % (iter->get().GetNumPoints())),
++ iter->get().GetPoint(i),
++ iter->get().GetPoint((i + 1) % (iter->get().GetNumPoints())),
+ holepoint)) {
+ continue;
+ }
+- polypoint = iter->GetPoint(i);
++ polypoint = iter->get().GetPoint(i);
+ if (pointfound) {
+ v1 = Normalize(polypoint - holepoint);
+ v2 = Normalize(bestpolypoint - holepoint);
+@@ -263,13 +260,13 @@ int TPPLPartition::RemoveHoles(TPPLPolyList *inpolys, TPPLPolyList *outpolys) {
+ }
+ }
+ pointvisible = true;
+- for (iter2 = polys.begin(); iter2 != polys.end(); iter2++) {
+- if (iter2->IsHole()) {
++ for (iter2 = polys.front(); iter2; iter2->next()) {
++ if (iter2->get().IsHole()) {
+ continue;
+ }
+- for (i2 = 0; i2 < iter2->GetNumPoints(); i2++) {
+- linep1 = iter2->GetPoint(i2);
+- linep2 = iter2->GetPoint((i2 + 1) % (iter2->GetNumPoints()));
++ for (i2 = 0; i2 < iter2->get().GetNumPoints(); i2++) {
++ linep1 = iter2->get().GetPoint(i2);
++ linep2 = iter2->get().GetPoint((i2 + 1) % (iter2->get().GetNumPoints()));
+ if (Intersects(holepoint, polypoint, linep1, linep2)) {
+ pointvisible = false;
+ break;
+@@ -292,18 +289,18 @@ int TPPLPartition::RemoveHoles(TPPLPolyList *inpolys, TPPLPolyList *outpolys) {
+ return 0;
+ }
+
+- newpoly.Init(holeiter->GetNumPoints() + polyiter->GetNumPoints() + 2);
++ newpoly.Init(holeiter->get().GetNumPoints() + polyiter->get().GetNumPoints() + 2);
+ i2 = 0;
+ for (i = 0; i <= polypointindex; i++) {
+- newpoly[i2] = polyiter->GetPoint(i);
++ newpoly[i2] = polyiter->get().GetPoint(i);
+ i2++;
+ }
+- for (i = 0; i <= holeiter->GetNumPoints(); i++) {
+- newpoly[i2] = holeiter->GetPoint((i + holepointindex) % holeiter->GetNumPoints());
++ for (i = 0; i <= holeiter->get().GetNumPoints(); i++) {
++ newpoly[i2] = holeiter->get().GetPoint((i + holepointindex) % holeiter->get().GetNumPoints());
+ i2++;
+ }
+- for (i = polypointindex; i < polyiter->GetNumPoints(); i++) {
+- newpoly[i2] = polyiter->GetPoint(i);
++ for (i = polypointindex; i < polyiter->get().GetNumPoints(); i++) {
++ newpoly[i2] = polyiter->get().GetPoint(i);
+ i2++;
+ }
+
+@@ -312,8 +309,8 @@ int TPPLPartition::RemoveHoles(TPPLPolyList *inpolys, TPPLPolyList *outpolys) {
+ polys.push_back(newpoly);
+ }
+
+- for (iter = polys.begin(); iter != polys.end(); iter++) {
+- outpolys->push_back(*iter);
++ for (iter = polys.front(); iter; iter = iter->next()) {
++ outpolys->push_back(iter->get());
+ }
+
+ return 1;
+@@ -524,13 +521,13 @@ int TPPLPartition::Triangulate_EC(TPPLPoly *poly, TPPLPolyList *triangles) {
+
+ int TPPLPartition::Triangulate_EC(TPPLPolyList *inpolys, TPPLPolyList *triangles) {
+ TPPLPolyList outpolys;
+- TPPLPolyList::iterator iter;
++ TPPLPolyList::Element *iter;
+
+ if (!RemoveHoles(inpolys, &outpolys)) {
+ return 0;
+ }
+- for (iter = outpolys.begin(); iter != outpolys.end(); iter++) {
+- if (!Triangulate_EC(&(*iter), triangles)) {
++ for (iter = outpolys.front(); iter; iter = iter->next()) {
++ if (!Triangulate_EC(&(iter->get()), triangles)) {
+ return 0;
+ }
+ }
+@@ -543,7 +540,7 @@ int TPPLPartition::ConvexPartition_HM(TPPLPoly *poly, TPPLPolyList *parts) {
+ }
+
+ TPPLPolyList triangles;
+- TPPLPolyList::iterator iter1, iter2;
++ TPPLPolyList::Element *iter1, *iter2;
+ TPPLPoly *poly1 = NULL, *poly2 = NULL;
+ TPPLPoly newpoly;
+ TPPLPoint d1, d2, p1, p2, p3;
+@@ -578,19 +575,19 @@ int TPPLPartition::ConvexPartition_HM(TPPLPoly *poly, TPPLPolyList *parts) {
+ return 0;
+ }
+
+- for (iter1 = triangles.begin(); iter1 != triangles.end(); iter1++) {
+- poly1 = &(*iter1);
++ for (iter1 = triangles.front(); iter1; iter1 = iter1->next()) {
++ poly1 = &(iter1->get());
+ for (i11 = 0; i11 < poly1->GetNumPoints(); i11++) {
+ d1 = poly1->GetPoint(i11);
+ i12 = (i11 + 1) % (poly1->GetNumPoints());
+ d2 = poly1->GetPoint(i12);
+
+ isdiagonal = false;
+- for (iter2 = iter1; iter2 != triangles.end(); iter2++) {
++ for (iter2 = iter1; iter2; iter2 = iter2->next()) {
+ if (iter1 == iter2) {
+ continue;
+ }
+- poly2 = &(*iter2);
++ poly2 = &(iter2->get());
+
+ for (i21 = 0; i21 < poly2->GetNumPoints(); i21++) {
+ if ((d2.x != poly2->GetPoint(i21).x) || (d2.y != poly2->GetPoint(i21).y)) {
+@@ -660,16 +657,16 @@ int TPPLPartition::ConvexPartition_HM(TPPLPoly *poly, TPPLPolyList *parts) {
+ }
+
+ triangles.erase(iter2);
+- *iter1 = newpoly;
+- poly1 = &(*iter1);
++ iter1->get() = newpoly;
++ poly1 = &(iter1->get());
+ i11 = -1;
+
+ continue;
+ }
+ }
+
+- for (iter1 = triangles.begin(); iter1 != triangles.end(); iter1++) {
+- parts->push_back(*iter1);
++ for (iter1 = triangles.front(); iter1; iter1 = iter1->next()) {
++ parts->push_back(iter1->get());
+ }
+
+ return 1;
+@@ -677,13 +674,13 @@ int TPPLPartition::ConvexPartition_HM(TPPLPoly *poly, TPPLPolyList *parts) {
+
+ int TPPLPartition::ConvexPartition_HM(TPPLPolyList *inpolys, TPPLPolyList *parts) {
+ TPPLPolyList outpolys;
+- TPPLPolyList::iterator iter;
++ TPPLPolyList::Element *iter;
+
+ if (!RemoveHoles(inpolys, &outpolys)) {
+ return 0;
+ }
+- for (iter = outpolys.begin(); iter != outpolys.end(); iter++) {
+- if (!ConvexPartition_HM(&(*iter), parts)) {
++ for (iter = outpolys.front(); iter; iter = iter->next()) {
++ if (!ConvexPartition_HM(&(iter->get()), parts)) {
+ return 0;
+ }
+ }
+@@ -824,8 +821,8 @@ int TPPLPartition::Triangulate_OPT(TPPLPoly *poly, TPPLPolyList *triangles) {
+ newdiagonal.index1 = 0;
+ newdiagonal.index2 = n - 1;
+ diagonals.push_back(newdiagonal);
+- while (!diagonals.empty()) {
+- diagonal = *(diagonals.begin());
++ while (!diagonals.is_empty()) {
++ diagonal = diagonals.front()->get();
+ diagonals.pop_front();
+ bestvertex = dpstates[diagonal.index2][diagonal.index1].bestvertex;
+ if (bestvertex == -1) {
+@@ -873,10 +870,10 @@ void TPPLPartition::UpdateState(long a, long b, long w, long i, long j, DPState2
+ pairs->push_front(newdiagonal);
+ dpstates[a][b].weight = w;
+ } else {
+- if ((!pairs->empty()) && (i <= pairs->begin()->index1)) {
++ if ((!pairs->is_empty()) && (i <= pairs->front()->get().index1)) {
+ return;
+ }
+- while ((!pairs->empty()) && (pairs->begin()->index2 >= j)) {
++ while ((!pairs->is_empty()) && (pairs->front()->get().index2 >= j)) {
+ pairs->pop_front();
+ }
+ pairs->push_front(newdiagonal);
+@@ -885,7 +882,7 @@ void TPPLPartition::UpdateState(long a, long b, long w, long i, long j, DPState2
+
+ void TPPLPartition::TypeA(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates) {
+ DiagonalList *pairs = NULL;
+- DiagonalList::iterator iter, lastiter;
++ DiagonalList::Element *iter, *lastiter;
+ long top;
+ long w;
+
+@@ -902,23 +899,23 @@ void TPPLPartition::TypeA(long i, long j, long k, PartitionVertex *vertices, DPS
+ }
+ if (j - i > 1) {
+ pairs = &(dpstates[i][j].pairs);
+- iter = pairs->end();
+- lastiter = pairs->end();
+- while (iter != pairs->begin()) {
++ iter = pairs->back();
++ lastiter = pairs->back();
++ while (iter != pairs->front()) {
+ iter--;
+- if (!IsReflex(vertices[iter->index2].p, vertices[j].p, vertices[k].p)) {
++ if (!IsReflex(vertices[iter->get().index2].p, vertices[j].p, vertices[k].p)) {
+ lastiter = iter;
+ } else {
+ break;
+ }
+ }
+- if (lastiter == pairs->end()) {
++ if (lastiter == pairs->back()) {
+ w++;
+ } else {
+- if (IsReflex(vertices[k].p, vertices[i].p, vertices[lastiter->index1].p)) {
++ if (IsReflex(vertices[k].p, vertices[i].p, vertices[lastiter->get().index1].p)) {
+ w++;
+ } else {
+- top = lastiter->index1;
++ top = lastiter->get().index1;
+ }
+ }
+ }
+@@ -927,7 +924,7 @@ void TPPLPartition::TypeA(long i, long j, long k, PartitionVertex *vertices, DPS
+
+ void TPPLPartition::TypeB(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates) {
+ DiagonalList *pairs = NULL;
+- DiagonalList::iterator iter, lastiter;
++ DiagonalList::Element *iter, *lastiter;
+ long top;
+ long w;
+
+@@ -946,21 +943,21 @@ void TPPLPartition::TypeB(long i, long j, long k, PartitionVertex *vertices, DPS
+ if (k - j > 1) {
+ pairs = &(dpstates[j][k].pairs);
+
+- iter = pairs->begin();
+- if ((!pairs->empty()) && (!IsReflex(vertices[i].p, vertices[j].p, vertices[iter->index1].p))) {
++ iter = pairs->front();
++ if ((!pairs->is_empty()) && (!IsReflex(vertices[i].p, vertices[j].p, vertices[iter->get().index1].p))) {
+ lastiter = iter;
+- while (iter != pairs->end()) {
+- if (!IsReflex(vertices[i].p, vertices[j].p, vertices[iter->index1].p)) {
++ while (iter) {
++ if (!IsReflex(vertices[i].p, vertices[j].p, vertices[iter->get().index1].p)) {
+ lastiter = iter;
+- iter++;
++ iter = iter->next();
+ } else {
+ break;
+ }
+ }
+- if (IsReflex(vertices[lastiter->index2].p, vertices[k].p, vertices[i].p)) {
++ if (IsReflex(vertices[lastiter->get().index2].p, vertices[k].p, vertices[i].p)) {
+ w++;
+ } else {
+- top = lastiter->index2;
++ top = lastiter->get().index2;
+ }
+ } else {
+ w++;
+@@ -981,11 +978,11 @@ int TPPLPartition::ConvexPartition_OPT(TPPLPoly *poly, TPPLPolyList *parts) {
+ DiagonalList diagonals, diagonals2;
+ Diagonal diagonal, newdiagonal;
+ DiagonalList *pairs = NULL, *pairs2 = NULL;
+- DiagonalList::iterator iter, iter2;
++ DiagonalList::Element *iter, *iter2;
+ int ret;
+ TPPLPoly newpoly;
+- std::vector<long> indices;
+- std::vector<long>::iterator iiter;
++ List<long> indices;
++ List<long>::Element *iiter;
+ bool ijreal, jkreal;
+
+ n = poly->GetNumPoints();
+@@ -1110,35 +1107,35 @@ int TPPLPartition::ConvexPartition_OPT(TPPLPoly *poly, TPPLPolyList *parts) {
+ newdiagonal.index1 = 0;
+ newdiagonal.index2 = n - 1;
+ diagonals.push_front(newdiagonal);
+- while (!diagonals.empty()) {
+- diagonal = *(diagonals.begin());
++ while (!diagonals.is_empty()) {
++ diagonal = diagonals.front()->get();
+ diagonals.pop_front();
+ if ((diagonal.index2 - diagonal.index1) <= 1) {
+ continue;
+ }
+ pairs = &(dpstates[diagonal.index1][diagonal.index2].pairs);
+- if (pairs->empty()) {
++ if (pairs->is_empty()) {
+ ret = 0;
+ break;
+ }
+ if (!vertices[diagonal.index1].isConvex) {
+- iter = pairs->end();
++ iter = pairs->back();
+ iter--;
+- j = iter->index2;
++ j = iter->get().index2;
+ newdiagonal.index1 = j;
+ newdiagonal.index2 = diagonal.index2;
+ diagonals.push_front(newdiagonal);
+ if ((j - diagonal.index1) > 1) {
+- if (iter->index1 != iter->index2) {
++ if (iter->get().index1 != iter->get().index2) {
+ pairs2 = &(dpstates[diagonal.index1][j].pairs);
+ while (1) {
+- if (pairs2->empty()) {
++ if (pairs2->is_empty()) {
+ ret = 0;
+ break;
+ }
+- iter2 = pairs2->end();
++ iter2 = pairs2->back();
+ iter2--;
+- if (iter->index1 != iter2->index1) {
++ if (iter->get().index1 != iter2->get().index1) {
+ pairs2->pop_back();
+ } else {
+ break;
+@@ -1153,21 +1150,21 @@ int TPPLPartition::ConvexPartition_OPT(TPPLPoly *poly, TPPLPolyList *parts) {
+ diagonals.push_front(newdiagonal);
+ }
+ } else {
+- iter = pairs->begin();
+- j = iter->index1;
++ iter = pairs->front();
++ j = iter->get().index1;
+ newdiagonal.index1 = diagonal.index1;
+ newdiagonal.index2 = j;
+ diagonals.push_front(newdiagonal);
+ if ((diagonal.index2 - j) > 1) {
+- if (iter->index1 != iter->index2) {
++ if (iter->get().index1 != iter->get().index2) {
+ pairs2 = &(dpstates[j][diagonal.index2].pairs);
+ while (1) {
+- if (pairs2->empty()) {
++ if (pairs2->is_empty()) {
+ ret = 0;
+ break;
+ }
+- iter2 = pairs2->begin();
+- if (iter->index2 != iter2->index2) {
++ iter2 = pairs2->front();
++ if (iter->get().index2 != iter2->get().index2) {
+ pairs2->pop_front();
+ } else {
+ break;
+@@ -1197,8 +1194,8 @@ int TPPLPartition::ConvexPartition_OPT(TPPLPoly *poly, TPPLPolyList *parts) {
+ newdiagonal.index1 = 0;
+ newdiagonal.index2 = n - 1;
+ diagonals.push_front(newdiagonal);
+- while (!diagonals.empty()) {
+- diagonal = *(diagonals.begin());
++ while (!diagonals.is_empty()) {
++ diagonal = diagonals.front()->get();
+ diagonals.pop_front();
+ if ((diagonal.index2 - diagonal.index1) <= 1) {
+ continue;
+@@ -1210,8 +1207,8 @@ int TPPLPartition::ConvexPartition_OPT(TPPLPoly *poly, TPPLPolyList *parts) {
+ indices.push_back(diagonal.index2);
+ diagonals2.push_front(diagonal);
+
+- while (!diagonals2.empty()) {
+- diagonal = *(diagonals2.begin());
++ while (!diagonals2.is_empty()) {
++ diagonal = diagonals2.front()->get();
+ diagonals2.pop_front();
+ if ((diagonal.index2 - diagonal.index1) <= 1) {
+ continue;
+@@ -1220,16 +1217,16 @@ int TPPLPartition::ConvexPartition_OPT(TPPLPoly *poly, TPPLPolyList *parts) {
+ jkreal = true;
+ pairs = &(dpstates[diagonal.index1][diagonal.index2].pairs);
+ if (!vertices[diagonal.index1].isConvex) {
+- iter = pairs->end();
++ iter = pairs->back();
+ iter--;
+- j = iter->index2;
+- if (iter->index1 != iter->index2) {
++ j = iter->get().index2;
++ if (iter->get().index1 != iter->get().index2) {
+ ijreal = false;
+ }
+ } else {
+- iter = pairs->begin();
+- j = iter->index1;
+- if (iter->index1 != iter->index2) {
++ iter = pairs->front();
++ j = iter->get().index1;
++ if (iter->get().index1 != iter->get().index2) {
+ jkreal = false;
+ }
+ }
+@@ -1253,11 +1250,12 @@ int TPPLPartition::ConvexPartition_OPT(TPPLPoly *poly, TPPLPolyList *parts) {
+ indices.push_back(j);
+ }
+
+- std::sort(indices.begin(), indices.end());
++ //std::sort(indices.begin(), indices.end());
++ indices.sort();
+ newpoly.Init((long)indices.size());
+ k = 0;
+- for (iiter = indices.begin(); iiter != indices.end(); iiter++) {
+- newpoly[k] = vertices[*iiter].p;
++ for (iiter = indices.front(); iiter != indices.back(); iiter = iiter->next()) {
++ newpoly[k] = vertices[iiter->get()].p;
+ k++;
+ }
+ parts->push_back(newpoly);
+@@ -1281,7 +1279,7 @@ int TPPLPartition::ConvexPartition_OPT(TPPLPoly *poly, TPPLPolyList *parts) {
+ // "Computational Geometry: Algorithms and Applications"
+ // by Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars.
+ int TPPLPartition::MonotonePartition(TPPLPolyList *inpolys, TPPLPolyList *monotonePolys) {
+- TPPLPolyList::iterator iter;
++ TPPLPolyList::Element *iter;
+ MonotoneVertex *vertices = NULL;
+ long i, numvertices, vindex, vindex2, newnumvertices, maxnumvertices;
+ long polystartindex, polyendindex;
+@@ -1291,11 +1289,8 @@ int TPPLPartition::MonotonePartition(TPPLPolyList *inpolys, TPPLPolyList *monoto
+ bool error = false;
+
+ numvertices = 0;
+- for (iter = inpolys->begin(); iter != inpolys->end(); iter++) {
+- if (!iter->Valid()) {
+- return 0;
+- }
+- numvertices += iter->GetNumPoints();
++ for (iter = inpolys->front(); iter; iter = iter->next()) {
++ numvertices += iter->get().GetNumPoints();
+ }
+
+ maxnumvertices = numvertices * 3;
+@@ -1303,8 +1298,8 @@ int TPPLPartition::MonotonePartition(TPPLPolyList *inpolys, TPPLPolyList *monoto
+ newnumvertices = numvertices;
+
+ polystartindex = 0;
+- for (iter = inpolys->begin(); iter != inpolys->end(); iter++) {
+- poly = &(*iter);
++ for (iter = inpolys->front(); iter; iter = iter->next()) {
++ poly = &(iter->get());
+ polyendindex = polystartindex + poly->GetNumPoints() - 1;
+ for (i = 0; i < poly->GetNumPoints(); i++) {
+ vertices[i + polystartindex].p = poly->GetPoint(i);
+@@ -1360,14 +1355,14 @@ int TPPLPartition::MonotonePartition(TPPLPolyList *inpolys, TPPLPolyList *monoto
+ // Note that while set doesn't actually have to be implemented as
+ // a tree, complexity requirements for operations are the same as
+ // for the balanced binary search tree.
+- std::set<ScanLineEdge> edgeTree;
++ Set<ScanLineEdge> edgeTree;
+ // Store iterators to the edge tree elements.
+ // This makes deleting existing edges much faster.
+- std::set<ScanLineEdge>::iterator *edgeTreeIterators, edgeIter;
+- edgeTreeIterators = new std::set<ScanLineEdge>::iterator[maxnumvertices];
+- std::pair<std::set<ScanLineEdge>::iterator, bool> edgeTreeRet;
++ Set<ScanLineEdge>::Element **edgeTreeIterators, *edgeIter;
++ edgeTreeIterators = new Set<ScanLineEdge>::Element *[maxnumvertices];
++ //Pair<Set<ScanLineEdge>::iterator, bool> edgeTreeRet;
+ for (i = 0; i < numvertices; i++) {
+- edgeTreeIterators[i] = edgeTree.end();
++ edgeTreeIterators[i] = nullptr;
+ }
+
+ // For each vertex.
+@@ -1387,13 +1382,14 @@ int TPPLPartition::MonotonePartition(TPPLPolyList *inpolys, TPPLPolyList *monoto
+ newedge.p1 = v->p;
+ newedge.p2 = vertices[v->next].p;
+ newedge.index = vindex;
+- edgeTreeRet = edgeTree.insert(newedge);
+- edgeTreeIterators[vindex] = edgeTreeRet.first;
++ //edgeTreeRet = edgeTree.insert(newedge);
++ //edgeTreeIterators[vindex] = edgeTreeRet.first;
++ edgeTreeIterators[vindex] = edgeTree.insert(newedge);
+ helpers[vindex] = vindex;
+ break;
+
+ case TPPL_VERTEXTYPE_END:
+- if (edgeTreeIterators[v->previous] == edgeTree.end()) {
++ if (edgeTreeIterators[v->previous] == edgeTree.back()) {
+ error = true;
+ break;
+ }
+@@ -1412,29 +1408,30 @@ int TPPLPartition::MonotonePartition(TPPLPolyList *inpolys, TPPLPolyList *monoto
+ newedge.p1 = v->p;
+ newedge.p2 = v->p;
+ edgeIter = edgeTree.lower_bound(newedge);
+- if (edgeIter == edgeTree.begin()) {
++ if (edgeIter == nullptr || edgeIter == edgeTree.front()) {
+ error = true;
+ break;
+ }
+ edgeIter--;
+ // Insert the diagonal connecting vi to helper(e_j) in D.
+- AddDiagonal(vertices, &newnumvertices, vindex, helpers[edgeIter->index],
++ AddDiagonal(vertices, &newnumvertices, vindex, helpers[edgeIter->get().index],
+ vertextypes, edgeTreeIterators, &edgeTree, helpers);
+ vindex2 = newnumvertices - 2;
+ v2 = &(vertices[vindex2]);
+ // helper(e_j) in v_i.
+- helpers[edgeIter->index] = vindex;
++ helpers[edgeIter->get().index] = vindex;
+ // Insert e_i in T and set helper(e_i) to v_i.
+ newedge.p1 = v2->p;
+ newedge.p2 = vertices[v2->next].p;
+ newedge.index = vindex2;
+- edgeTreeRet = edgeTree.insert(newedge);
+- edgeTreeIterators[vindex2] = edgeTreeRet.first;
++ //edgeTreeRet = edgeTree.insert(newedge);
++ //edgeTreeIterators[vindex2] = edgeTreeRet.first;
++ edgeTreeIterators[vindex2] = edgeTree.insert(newedge);
+ helpers[vindex2] = vindex2;
+ break;
+
+ case TPPL_VERTEXTYPE_MERGE:
+- if (edgeTreeIterators[v->previous] == edgeTree.end()) {
++ if (edgeTreeIterators[v->previous] == edgeTree.back()) {
+ error = true;
+ break;
+ }
+@@ -1452,25 +1449,25 @@ int TPPLPartition::MonotonePartition(TPPLPolyList *inpolys, TPPLPolyList *monoto
+ newedge.p1 = v->p;
+ newedge.p2 = v->p;
+ edgeIter = edgeTree.lower_bound(newedge);
+- if (edgeIter == edgeTree.begin()) {
++ if (edgeIter == nullptr || edgeIter == edgeTree.front()) {
+ error = true;
+ break;
+ }
+ edgeIter--;
+ // If helper(e_j) is a merge vertex.
+- if (vertextypes[helpers[edgeIter->index]] == TPPL_VERTEXTYPE_MERGE) {
++ if (vertextypes[helpers[edgeIter->get().index]] == TPPL_VERTEXTYPE_MERGE) {
+ // Insert the diagonal connecting v_i to helper(e_j) in D.
+- AddDiagonal(vertices, &newnumvertices, vindex2, helpers[edgeIter->index],
++ AddDiagonal(vertices, &newnumvertices, vindex2, helpers[edgeIter->get().index],
+ vertextypes, edgeTreeIterators, &edgeTree, helpers);
+ }
+ // helper(e_j) <- v_i
+- helpers[edgeIter->index] = vindex2;
++ helpers[edgeIter->get().index] = vindex2;
+ break;
+
+ case TPPL_VERTEXTYPE_REGULAR:
+ // If the interior of P lies to the right of v_i.
+ if (Below(v->p, vertices[v->previous].p)) {
+- if (edgeTreeIterators[v->previous] == edgeTree.end()) {
++ if (edgeTreeIterators[v->previous] == edgeTree.back()) {
+ error = true;
+ break;
+ }
+@@ -1488,27 +1485,28 @@ int TPPLPartition::MonotonePartition(TPPLPolyList *inpolys, TPPLPolyList *monoto
+ newedge.p1 = v2->p;
+ newedge.p2 = vertices[v2->next].p;
+ newedge.index = vindex2;
+- edgeTreeRet = edgeTree.insert(newedge);
+- edgeTreeIterators[vindex2] = edgeTreeRet.first;
++ //edgeTreeRet = edgeTree.insert(newedge);
++ //edgeTreeIterators[vindex2] = edgeTreeRet.first;
++ edgeTreeIterators[vindex2] = edgeTree.insert(newedge);
+ helpers[vindex2] = vindex;
+ } else {
+ // Search in T to find the edge e_j directly left of v_i.
+ newedge.p1 = v->p;
+ newedge.p2 = v->p;
+ edgeIter = edgeTree.lower_bound(newedge);
+- if (edgeIter == edgeTree.begin()) {
++ if (edgeIter == nullptr || edgeIter == edgeTree.front()) {
+ error = true;
+ break;
+ }
+- edgeIter--;
++ edgeIter = edgeIter->prev();
+ // If helper(e_j) is a merge vertex.
+- if (vertextypes[helpers[edgeIter->index]] == TPPL_VERTEXTYPE_MERGE) {
++ if (vertextypes[helpers[edgeIter->get().index]] == TPPL_VERTEXTYPE_MERGE) {
+ // Insert the diagonal connecting v_i to helper(e_j) in D.
+- AddDiagonal(vertices, &newnumvertices, vindex, helpers[edgeIter->index],
++ AddDiagonal(vertices, &newnumvertices, vindex, helpers[edgeIter->get().index],
+ vertextypes, edgeTreeIterators, &edgeTree, helpers);
+ }
+ // helper(e_j) <- v_i.
+- helpers[edgeIter->index] = vindex;
++ helpers[edgeIter->get().index] = vindex;
+ }
+ break;
+ }
+@@ -1569,8 +1567,8 @@ int TPPLPartition::MonotonePartition(TPPLPolyList *inpolys, TPPLPolyList *monoto
+
+ // Adds a diagonal to the doubly-connected list of vertices.
+ void TPPLPartition::AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2,
+- TPPLVertexType *vertextypes, std::set<ScanLineEdge>::iterator *edgeTreeIterators,
+- std::set<ScanLineEdge> *edgeTree, long *helpers) {
++ TPPLVertexType *vertextypes, Set<ScanLineEdge>::Element **edgeTreeIterators,
++ Set<ScanLineEdge> *edgeTree, long *helpers) {
+ long newindex1, newindex2;
+
+ newindex1 = *numvertices;
+@@ -1597,14 +1595,14 @@ void TPPLPartition::AddDiagonal(MonotoneVertex *vertices, long *numvertices, lon
+ vertextypes[newindex1] = vertextypes[index1];
+ edgeTreeIterators[newindex1] = edgeTreeIterators[index1];
+ helpers[newindex1] = helpers[index1];
+- if (edgeTreeIterators[newindex1] != edgeTree->end()) {
+- edgeTreeIterators[newindex1]->index = newindex1;
++ if (edgeTreeIterators[newindex1] != edgeTree->back()) {
++ edgeTreeIterators[newindex1]->get().index = newindex1;
+ }
+ vertextypes[newindex2] = vertextypes[index2];
+ edgeTreeIterators[newindex2] = edgeTreeIterators[index2];
+ helpers[newindex2] = helpers[index2];
+- if (edgeTreeIterators[newindex2] != edgeTree->end()) {
+- edgeTreeIterators[newindex2]->index = newindex2;
++ if (edgeTreeIterators[newindex2] != edgeTree->back()) {
++ edgeTreeIterators[newindex2]->get().index = newindex2;
+ }
+ }
+
+@@ -1830,13 +1828,13 @@ int TPPLPartition::TriangulateMonotone(TPPLPoly *inPoly, TPPLPolyList *triangles
+
+ int TPPLPartition::Triangulate_MONO(TPPLPolyList *inpolys, TPPLPolyList *triangles) {
+ TPPLPolyList monotone;
+- TPPLPolyList::iterator iter;
++ TPPLPolyList::Element *iter;
+
+ if (!MonotonePartition(inpolys, &monotone)) {
+ return 0;
+ }
+- for (iter = monotone.begin(); iter != monotone.end(); iter++) {
+- if (!TriangulateMonotone(&(*iter), triangles)) {
++ for (iter = monotone.front(); iter; iter = iter->next()) {
++ if (!TriangulateMonotone(&(iter->get()), triangles)) {
+ return 0;
+ }
+ }
+diff --git a/thirdparty/misc/polypartition.h b/thirdparty/misc/polypartition.h
+index f163f5d217..b2d905a3ef 100644
+--- a/thirdparty/misc/polypartition.h
++++ b/thirdparty/misc/polypartition.h
+@@ -24,8 +24,9 @@
+ #ifndef POLYPARTITION_H
+ #define POLYPARTITION_H
+
+-#include <list>
+-#include <set>
++#include "core/math/vector2.h"
++#include "core/templates/list.h"
++#include "core/templates/set.h"
+
+ typedef double tppl_float;
+
+@@ -44,49 +45,7 @@ enum TPPLVertexType {
+ };
+
+ // 2D point structure.
+-struct TPPLPoint {
+- tppl_float x;
+- tppl_float y;
+- // User-specified vertex identifier. Note that this isn't used internally
+- // by the library, but will be faithfully copied around.
+- int id;
+-
+- TPPLPoint operator+(const TPPLPoint &p) const {
+- TPPLPoint r;
+- r.x = x + p.x;
+- r.y = y + p.y;
+- return r;
+- }
+-
+- TPPLPoint operator-(const TPPLPoint &p) const {
+- TPPLPoint r;
+- r.x = x - p.x;
+- r.y = y - p.y;
+- return r;
+- }
+-
+- TPPLPoint operator*(const tppl_float f) const {
+- TPPLPoint r;
+- r.x = x * f;
+- r.y = y * f;
+- return r;
+- }
+-
+- TPPLPoint operator/(const tppl_float f) const {
+- TPPLPoint r;
+- r.x = x / f;
+- r.y = y / f;
+- return r;
+- }
+-
+- bool operator==(const TPPLPoint &p) const {
+- return ((x == p.x) && (y == p.y));
+- }
+-
+- bool operator!=(const TPPLPoint &p) const {
+- return !((x == p.x) && (y == p.y));
+- }
+-};
++typedef Vector2 TPPLPoint;
+
+ // Polygon implemented as an array of points with a "hole" flag.
+ class TPPLPoly {
+@@ -168,9 +127,9 @@ class TPPLPoly {
+ };
+
+ #ifdef TPPL_ALLOCATOR
+-typedef std::list<TPPLPoly, TPPL_ALLOCATOR(TPPLPoly)> TPPLPolyList;
++typedef List<TPPLPoly, TPPL_ALLOCATOR(TPPLPoly)> TPPLPolyList;
+ #else
+-typedef std::list<TPPLPoly> TPPLPolyList;
++typedef List<TPPLPoly> TPPLPolyList;
+ #endif
+
+ class TPPLPartition {
+@@ -209,9 +168,9 @@ public:
+ };
+
+ #ifdef TPPL_ALLOCATOR
+- typedef std::list<Diagonal, TPPL_ALLOCATOR(Diagonal)> DiagonalList;
++ typedef List<Diagonal, TPPL_ALLOCATOR(Diagonal)> DiagonalList;
+ #else
+- typedef std::list<Diagonal> DiagonalList;
++ typedef List<Diagonal> DiagonalList;
+ #endif
+
+ // Dynamic programming state for minimum-weight triangulation.
+@@ -265,8 +224,8 @@ public:
+ // Helper functions for MonotonePartition.
+ bool Below(TPPLPoint &p1, TPPLPoint &p2);
+ void AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2,
+- TPPLVertexType *vertextypes, std::set<ScanLineEdge>::iterator *edgeTreeIterators,
+- std::set<ScanLineEdge> *edgeTree, long *helpers);
++ TPPLVertexType *vertextypes, Set<ScanLineEdge>::Element **edgeTreeIterators,
++ Set<ScanLineEdge> *edgeTree, long *helpers);
+
+ // Triangulates a monotone polygon, used in Triangulate_MONO.
+ int TriangulateMonotone(TPPLPoly *inPoly, TPPLPolyList *triangles);
diff --git a/thirdparty/misc/pcg.cpp b/thirdparty/misc/pcg.cpp
index c421e16f89..914a353874 100644
--- a/thirdparty/misc/pcg.cpp
+++ b/thirdparty/misc/pcg.cpp
@@ -23,3 +23,36 @@ void pcg32_srandom_r(pcg32_random_t* rng, uint64_t initstate, uint64_t initseq)
rng->state += initstate;
pcg32_random_r(rng);
}
+
+// Source from https://github.com/imneme/pcg-c-basic/blob/master/pcg_basic.c
+// pcg32_boundedrand_r(rng, bound):
+// Generate a uniformly distributed number, r, where 0 <= r < bound
+uint32_t pcg32_boundedrand_r(pcg32_random_t *rng, uint32_t bound) {
+ // To avoid bias, we need to make the range of the RNG a multiple of
+ // bound, which we do by dropping output less than a threshold.
+ // A naive scheme to calculate the threshold would be to do
+ //
+ // uint32_t threshold = 0x100000000ull % bound;
+ //
+ // but 64-bit div/mod is slower than 32-bit div/mod (especially on
+ // 32-bit platforms). In essence, we do
+ //
+ // uint32_t threshold = (0x100000000ull-bound) % bound;
+ //
+ // because this version will calculate the same modulus, but the LHS
+ // value is less than 2^32.
+ uint32_t threshold = -bound % bound;
+
+ // Uniformity guarantees that this loop will terminate. In practice, it
+ // should usually terminate quickly; on average (assuming all bounds are
+ // equally likely), 82.25% of the time, we can expect it to require just
+ // one iteration. In the worst case, someone passes a bound of 2^31 + 1
+ // (i.e., 2147483649), which invalidates almost 50% of the range. In
+ // practice, bounds are typically small and only a tiny amount of the range
+ // is eliminated.
+ for (;;) {
+ uint32_t r = pcg32_random_r(rng);
+ if (r >= threshold)
+ return r % bound;
+ }
+}
diff --git a/thirdparty/misc/pcg.h b/thirdparty/misc/pcg.h
index 6f42b3b094..0faab73e64 100644
--- a/thirdparty/misc/pcg.h
+++ b/thirdparty/misc/pcg.h
@@ -11,5 +11,6 @@
typedef struct { uint64_t state; uint64_t inc; } pcg32_random_t;
uint32_t pcg32_random_r(pcg32_random_t* rng);
void pcg32_srandom_r(pcg32_random_t* rng, uint64_t initstate, uint64_t initseq);
+uint32_t pcg32_boundedrand_r(pcg32_random_t* rng, uint32_t bound);
#endif // RANDOM_H
diff --git a/thirdparty/misc/polypartition.cpp b/thirdparty/misc/polypartition.cpp
new file mode 100644
index 0000000000..5e94793b79
--- /dev/null
+++ b/thirdparty/misc/polypartition.cpp
@@ -0,0 +1,1849 @@
+/*************************************************************************/
+/* Copyright (c) 2011-2021 Ivan Fratric and contributors. */
+/* */
+/* Permission is hereby granted, free of charge, to any person obtaining */
+/* a copy of this software and associated documentation files (the */
+/* "Software"), to deal in the Software without restriction, including */
+/* without limitation the rights to use, copy, modify, merge, publish, */
+/* distribute, sublicense, and/or sell copies of the Software, and to */
+/* permit persons to whom the Software is furnished to do so, subject to */
+/* the following conditions: */
+/* */
+/* The above copyright notice and this permission notice shall be */
+/* included in all copies or substantial portions of the Software. */
+/* */
+/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
+/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
+/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/
+/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
+/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
+/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
+/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
+/*************************************************************************/
+
+#include "polypartition.h"
+
+#include <algorithm>
+
+TPPLPoly::TPPLPoly() {
+ hole = false;
+ numpoints = 0;
+ points = NULL;
+}
+
+TPPLPoly::~TPPLPoly() {
+ if (points) {
+ delete[] points;
+ }
+}
+
+void TPPLPoly::Clear() {
+ if (points) {
+ delete[] points;
+ }
+ hole = false;
+ numpoints = 0;
+ points = NULL;
+}
+
+void TPPLPoly::Init(long numpoints) {
+ Clear();
+ this->numpoints = numpoints;
+ points = new TPPLPoint[numpoints];
+}
+
+void TPPLPoly::Triangle(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3) {
+ Init(3);
+ points[0] = p1;
+ points[1] = p2;
+ points[2] = p3;
+}
+
+TPPLPoly::TPPLPoly(const TPPLPoly &src) :
+ TPPLPoly() {
+ hole = src.hole;
+ numpoints = src.numpoints;
+
+ if (numpoints > 0) {
+ points = new TPPLPoint[numpoints];
+ memcpy(points, src.points, numpoints * sizeof(TPPLPoint));
+ }
+}
+
+TPPLPoly &TPPLPoly::operator=(const TPPLPoly &src) {
+ Clear();
+ hole = src.hole;
+ numpoints = src.numpoints;
+
+ if (numpoints > 0) {
+ points = new TPPLPoint[numpoints];
+ memcpy(points, src.points, numpoints * sizeof(TPPLPoint));
+ }
+
+ return *this;
+}
+
+TPPLOrientation TPPLPoly::GetOrientation() const {
+ long i1, i2;
+ tppl_float area = 0;
+ for (i1 = 0; i1 < numpoints; i1++) {
+ i2 = i1 + 1;
+ if (i2 == numpoints) {
+ i2 = 0;
+ }
+ area += points[i1].x * points[i2].y - points[i1].y * points[i2].x;
+ }
+ if (area > 0) {
+ return TPPL_ORIENTATION_CCW;
+ }
+ if (area < 0) {
+ return TPPL_ORIENTATION_CW;
+ }
+ return TPPL_ORIENTATION_NONE;
+}
+
+void TPPLPoly::SetOrientation(TPPLOrientation orientation) {
+ TPPLOrientation polyorientation = GetOrientation();
+ if (polyorientation != TPPL_ORIENTATION_NONE && polyorientation != orientation) {
+ Invert();
+ }
+}
+
+void TPPLPoly::Invert() {
+ std::reverse(points, points + numpoints);
+}
+
+TPPLPartition::PartitionVertex::PartitionVertex() :
+ previous(NULL), next(NULL) {
+}
+
+TPPLPoint TPPLPartition::Normalize(const TPPLPoint &p) {
+ TPPLPoint r;
+ tppl_float n = sqrt(p.x * p.x + p.y * p.y);
+ if (n != 0) {
+ r = p / n;
+ } else {
+ r.x = 0;
+ r.y = 0;
+ }
+ return r;
+}
+
+tppl_float TPPLPartition::Distance(const TPPLPoint &p1, const TPPLPoint &p2) {
+ tppl_float dx, dy;
+ dx = p2.x - p1.x;
+ dy = p2.y - p1.y;
+ return (sqrt(dx * dx + dy * dy));
+}
+
+// Checks if two lines intersect.
+int TPPLPartition::Intersects(TPPLPoint &p11, TPPLPoint &p12, TPPLPoint &p21, TPPLPoint &p22) {
+ if ((p11.x == p21.x) && (p11.y == p21.y)) {
+ return 0;
+ }
+ if ((p11.x == p22.x) && (p11.y == p22.y)) {
+ return 0;
+ }
+ if ((p12.x == p21.x) && (p12.y == p21.y)) {
+ return 0;
+ }
+ if ((p12.x == p22.x) && (p12.y == p22.y)) {
+ return 0;
+ }
+
+ TPPLPoint v1ort, v2ort, v;
+ tppl_float dot11, dot12, dot21, dot22;
+
+ v1ort.x = p12.y - p11.y;
+ v1ort.y = p11.x - p12.x;
+
+ v2ort.x = p22.y - p21.y;
+ v2ort.y = p21.x - p22.x;
+
+ v = p21 - p11;
+ dot21 = v.x * v1ort.x + v.y * v1ort.y;
+ v = p22 - p11;
+ dot22 = v.x * v1ort.x + v.y * v1ort.y;
+
+ v = p11 - p21;
+ dot11 = v.x * v2ort.x + v.y * v2ort.y;
+ v = p12 - p21;
+ dot12 = v.x * v2ort.x + v.y * v2ort.y;
+
+ if (dot11 * dot12 > 0) {
+ return 0;
+ }
+ if (dot21 * dot22 > 0) {
+ return 0;
+ }
+
+ return 1;
+}
+
+// Removes holes from inpolys by merging them with non-holes.
+int TPPLPartition::RemoveHoles(TPPLPolyList *inpolys, TPPLPolyList *outpolys) {
+ TPPLPolyList polys;
+ TPPLPolyList::Element *holeiter, *polyiter, *iter, *iter2;
+ long i, i2, holepointindex, polypointindex;
+ TPPLPoint holepoint, polypoint, bestpolypoint;
+ TPPLPoint linep1, linep2;
+ TPPLPoint v1, v2;
+ TPPLPoly newpoly;
+ bool hasholes;
+ bool pointvisible;
+ bool pointfound;
+
+ // Check for the trivial case of no holes.
+ hasholes = false;
+ for (iter = inpolys->front(); iter; iter = iter->next()) {
+ if (iter->get().IsHole()) {
+ hasholes = true;
+ break;
+ }
+ }
+ if (!hasholes) {
+ for (iter = inpolys->front(); iter; iter = iter->next()) {
+ outpolys->push_back(iter->get());
+ }
+ return 1;
+ }
+
+ polys = *inpolys;
+
+ while (1) {
+ // Find the hole point with the largest x.
+ hasholes = false;
+ for (iter = polys.front(); iter; iter = iter->next()) {
+ if (!iter->get().IsHole()) {
+ continue;
+ }
+
+ if (!hasholes) {
+ hasholes = true;
+ holeiter = iter;
+ holepointindex = 0;
+ }
+
+ for (i = 0; i < iter->get().GetNumPoints(); i++) {
+ if (iter->get().GetPoint(i).x > holeiter->get().GetPoint(holepointindex).x) {
+ holeiter = iter;
+ holepointindex = i;
+ }
+ }
+ }
+ if (!hasholes) {
+ break;
+ }
+ holepoint = holeiter->get().GetPoint(holepointindex);
+
+ pointfound = false;
+ for (iter = polys.front(); iter; iter = iter->next()) {
+ if (iter->get().IsHole()) {
+ continue;
+ }
+ for (i = 0; i < iter->get().GetNumPoints(); i++) {
+ if (iter->get().GetPoint(i).x <= holepoint.x) {
+ continue;
+ }
+ if (!InCone(iter->get().GetPoint((i + iter->get().GetNumPoints() - 1) % (iter->get().GetNumPoints())),
+ iter->get().GetPoint(i),
+ iter->get().GetPoint((i + 1) % (iter->get().GetNumPoints())),
+ holepoint)) {
+ continue;
+ }
+ polypoint = iter->get().GetPoint(i);
+ if (pointfound) {
+ v1 = Normalize(polypoint - holepoint);
+ v2 = Normalize(bestpolypoint - holepoint);
+ if (v2.x > v1.x) {
+ continue;
+ }
+ }
+ pointvisible = true;
+ for (iter2 = polys.front(); iter2; iter2->next()) {
+ if (iter2->get().IsHole()) {
+ continue;
+ }
+ for (i2 = 0; i2 < iter2->get().GetNumPoints(); i2++) {
+ linep1 = iter2->get().GetPoint(i2);
+ linep2 = iter2->get().GetPoint((i2 + 1) % (iter2->get().GetNumPoints()));
+ if (Intersects(holepoint, polypoint, linep1, linep2)) {
+ pointvisible = false;
+ break;
+ }
+ }
+ if (!pointvisible) {
+ break;
+ }
+ }
+ if (pointvisible) {
+ pointfound = true;
+ bestpolypoint = polypoint;
+ polyiter = iter;
+ polypointindex = i;
+ }
+ }
+ }
+
+ if (!pointfound) {
+ return 0;
+ }
+
+ newpoly.Init(holeiter->get().GetNumPoints() + polyiter->get().GetNumPoints() + 2);
+ i2 = 0;
+ for (i = 0; i <= polypointindex; i++) {
+ newpoly[i2] = polyiter->get().GetPoint(i);
+ i2++;
+ }
+ for (i = 0; i <= holeiter->get().GetNumPoints(); i++) {
+ newpoly[i2] = holeiter->get().GetPoint((i + holepointindex) % holeiter->get().GetNumPoints());
+ i2++;
+ }
+ for (i = polypointindex; i < polyiter->get().GetNumPoints(); i++) {
+ newpoly[i2] = polyiter->get().GetPoint(i);
+ i2++;
+ }
+
+ polys.erase(holeiter);
+ polys.erase(polyiter);
+ polys.push_back(newpoly);
+ }
+
+ for (iter = polys.front(); iter; iter = iter->next()) {
+ outpolys->push_back(iter->get());
+ }
+
+ return 1;
+}
+
+bool TPPLPartition::IsConvex(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3) {
+ tppl_float tmp;
+ tmp = (p3.y - p1.y) * (p2.x - p1.x) - (p3.x - p1.x) * (p2.y - p1.y);
+ if (tmp > 0) {
+ return 1;
+ } else {
+ return 0;
+ }
+}
+
+bool TPPLPartition::IsReflex(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3) {
+ tppl_float tmp;
+ tmp = (p3.y - p1.y) * (p2.x - p1.x) - (p3.x - p1.x) * (p2.y - p1.y);
+ if (tmp < 0) {
+ return 1;
+ } else {
+ return 0;
+ }
+}
+
+bool TPPLPartition::IsInside(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3, TPPLPoint &p) {
+ if (IsConvex(p1, p, p2)) {
+ return false;
+ }
+ if (IsConvex(p2, p, p3)) {
+ return false;
+ }
+ if (IsConvex(p3, p, p1)) {
+ return false;
+ }
+ return true;
+}
+
+bool TPPLPartition::InCone(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3, TPPLPoint &p) {
+ bool convex;
+
+ convex = IsConvex(p1, p2, p3);
+
+ if (convex) {
+ if (!IsConvex(p1, p2, p)) {
+ return false;
+ }
+ if (!IsConvex(p2, p3, p)) {
+ return false;
+ }
+ return true;
+ } else {
+ if (IsConvex(p1, p2, p)) {
+ return true;
+ }
+ if (IsConvex(p2, p3, p)) {
+ return true;
+ }
+ return false;
+ }
+}
+
+bool TPPLPartition::InCone(PartitionVertex *v, TPPLPoint &p) {
+ TPPLPoint p1, p2, p3;
+
+ p1 = v->previous->p;
+ p2 = v->p;
+ p3 = v->next->p;
+
+ return InCone(p1, p2, p3, p);
+}
+
+void TPPLPartition::UpdateVertexReflexity(PartitionVertex *v) {
+ PartitionVertex *v1 = NULL, *v3 = NULL;
+ v1 = v->previous;
+ v3 = v->next;
+ v->isConvex = !IsReflex(v1->p, v->p, v3->p);
+}
+
+void TPPLPartition::UpdateVertex(PartitionVertex *v, PartitionVertex *vertices, long numvertices) {
+ long i;
+ PartitionVertex *v1 = NULL, *v3 = NULL;
+ TPPLPoint vec1, vec3;
+
+ v1 = v->previous;
+ v3 = v->next;
+
+ v->isConvex = IsConvex(v1->p, v->p, v3->p);
+
+ vec1 = Normalize(v1->p - v->p);
+ vec3 = Normalize(v3->p - v->p);
+ v->angle = vec1.x * vec3.x + vec1.y * vec3.y;
+
+ if (v->isConvex) {
+ v->isEar = true;
+ for (i = 0; i < numvertices; i++) {
+ if ((vertices[i].p.x == v->p.x) && (vertices[i].p.y == v->p.y)) {
+ continue;
+ }
+ if ((vertices[i].p.x == v1->p.x) && (vertices[i].p.y == v1->p.y)) {
+ continue;
+ }
+ if ((vertices[i].p.x == v3->p.x) && (vertices[i].p.y == v3->p.y)) {
+ continue;
+ }
+ if (IsInside(v1->p, v->p, v3->p, vertices[i].p)) {
+ v->isEar = false;
+ break;
+ }
+ }
+ } else {
+ v->isEar = false;
+ }
+}
+
+// Triangulation by ear removal.
+int TPPLPartition::Triangulate_EC(TPPLPoly *poly, TPPLPolyList *triangles) {
+ if (!poly->Valid()) {
+ return 0;
+ }
+
+ long numvertices;
+ PartitionVertex *vertices = NULL;
+ PartitionVertex *ear = NULL;
+ TPPLPoly triangle;
+ long i, j;
+ bool earfound;
+
+ if (poly->GetNumPoints() < 3) {
+ return 0;
+ }
+ if (poly->GetNumPoints() == 3) {
+ triangles->push_back(*poly);
+ return 1;
+ }
+
+ numvertices = poly->GetNumPoints();
+
+ vertices = new PartitionVertex[numvertices];
+ for (i = 0; i < numvertices; i++) {
+ vertices[i].isActive = true;
+ vertices[i].p = poly->GetPoint(i);
+ if (i == (numvertices - 1)) {
+ vertices[i].next = &(vertices[0]);
+ } else {
+ vertices[i].next = &(vertices[i + 1]);
+ }
+ if (i == 0) {
+ vertices[i].previous = &(vertices[numvertices - 1]);
+ } else {
+ vertices[i].previous = &(vertices[i - 1]);
+ }
+ }
+ for (i = 0; i < numvertices; i++) {
+ UpdateVertex(&vertices[i], vertices, numvertices);
+ }
+
+ for (i = 0; i < numvertices - 3; i++) {
+ earfound = false;
+ // Find the most extruded ear.
+ for (j = 0; j < numvertices; j++) {
+ if (!vertices[j].isActive) {
+ continue;
+ }
+ if (!vertices[j].isEar) {
+ continue;
+ }
+ if (!earfound) {
+ earfound = true;
+ ear = &(vertices[j]);
+ } else {
+ if (vertices[j].angle > ear->angle) {
+ ear = &(vertices[j]);
+ }
+ }
+ }
+ if (!earfound) {
+ delete[] vertices;
+ return 0;
+ }
+
+ triangle.Triangle(ear->previous->p, ear->p, ear->next->p);
+ triangles->push_back(triangle);
+
+ ear->isActive = false;
+ ear->previous->next = ear->next;
+ ear->next->previous = ear->previous;
+
+ if (i == numvertices - 4) {
+ break;
+ }
+
+ UpdateVertex(ear->previous, vertices, numvertices);
+ UpdateVertex(ear->next, vertices, numvertices);
+ }
+ for (i = 0; i < numvertices; i++) {
+ if (vertices[i].isActive) {
+ triangle.Triangle(vertices[i].previous->p, vertices[i].p, vertices[i].next->p);
+ triangles->push_back(triangle);
+ break;
+ }
+ }
+
+ delete[] vertices;
+
+ return 1;
+}
+
+int TPPLPartition::Triangulate_EC(TPPLPolyList *inpolys, TPPLPolyList *triangles) {
+ TPPLPolyList outpolys;
+ TPPLPolyList::Element *iter;
+
+ if (!RemoveHoles(inpolys, &outpolys)) {
+ return 0;
+ }
+ for (iter = outpolys.front(); iter; iter = iter->next()) {
+ if (!Triangulate_EC(&(iter->get()), triangles)) {
+ return 0;
+ }
+ }
+ return 1;
+}
+
+int TPPLPartition::ConvexPartition_HM(TPPLPoly *poly, TPPLPolyList *parts) {
+ if (!poly->Valid()) {
+ return 0;
+ }
+
+ TPPLPolyList triangles;
+ TPPLPolyList::Element *iter1, *iter2;
+ TPPLPoly *poly1 = NULL, *poly2 = NULL;
+ TPPLPoly newpoly;
+ TPPLPoint d1, d2, p1, p2, p3;
+ long i11, i12, i21, i22, i13, i23, j, k;
+ bool isdiagonal;
+ long numreflex;
+
+ // Check if the poly is already convex.
+ numreflex = 0;
+ for (i11 = 0; i11 < poly->GetNumPoints(); i11++) {
+ if (i11 == 0) {
+ i12 = poly->GetNumPoints() - 1;
+ } else {
+ i12 = i11 - 1;
+ }
+ if (i11 == (poly->GetNumPoints() - 1)) {
+ i13 = 0;
+ } else {
+ i13 = i11 + 1;
+ }
+ if (IsReflex(poly->GetPoint(i12), poly->GetPoint(i11), poly->GetPoint(i13))) {
+ numreflex = 1;
+ break;
+ }
+ }
+ if (numreflex == 0) {
+ parts->push_back(*poly);
+ return 1;
+ }
+
+ if (!Triangulate_EC(poly, &triangles)) {
+ return 0;
+ }
+
+ for (iter1 = triangles.front(); iter1; iter1 = iter1->next()) {
+ poly1 = &(iter1->get());
+ for (i11 = 0; i11 < poly1->GetNumPoints(); i11++) {
+ d1 = poly1->GetPoint(i11);
+ i12 = (i11 + 1) % (poly1->GetNumPoints());
+ d2 = poly1->GetPoint(i12);
+
+ isdiagonal = false;
+ for (iter2 = iter1; iter2; iter2 = iter2->next()) {
+ if (iter1 == iter2) {
+ continue;
+ }
+ poly2 = &(iter2->get());
+
+ for (i21 = 0; i21 < poly2->GetNumPoints(); i21++) {
+ if ((d2.x != poly2->GetPoint(i21).x) || (d2.y != poly2->GetPoint(i21).y)) {
+ continue;
+ }
+ i22 = (i21 + 1) % (poly2->GetNumPoints());
+ if ((d1.x != poly2->GetPoint(i22).x) || (d1.y != poly2->GetPoint(i22).y)) {
+ continue;
+ }
+ isdiagonal = true;
+ break;
+ }
+ if (isdiagonal) {
+ break;
+ }
+ }
+
+ if (!isdiagonal) {
+ continue;
+ }
+
+ p2 = poly1->GetPoint(i11);
+ if (i11 == 0) {
+ i13 = poly1->GetNumPoints() - 1;
+ } else {
+ i13 = i11 - 1;
+ }
+ p1 = poly1->GetPoint(i13);
+ if (i22 == (poly2->GetNumPoints() - 1)) {
+ i23 = 0;
+ } else {
+ i23 = i22 + 1;
+ }
+ p3 = poly2->GetPoint(i23);
+
+ if (!IsConvex(p1, p2, p3)) {
+ continue;
+ }
+
+ p2 = poly1->GetPoint(i12);
+ if (i12 == (poly1->GetNumPoints() - 1)) {
+ i13 = 0;
+ } else {
+ i13 = i12 + 1;
+ }
+ p3 = poly1->GetPoint(i13);
+ if (i21 == 0) {
+ i23 = poly2->GetNumPoints() - 1;
+ } else {
+ i23 = i21 - 1;
+ }
+ p1 = poly2->GetPoint(i23);
+
+ if (!IsConvex(p1, p2, p3)) {
+ continue;
+ }
+
+ newpoly.Init(poly1->GetNumPoints() + poly2->GetNumPoints() - 2);
+ k = 0;
+ for (j = i12; j != i11; j = (j + 1) % (poly1->GetNumPoints())) {
+ newpoly[k] = poly1->GetPoint(j);
+ k++;
+ }
+ for (j = i22; j != i21; j = (j + 1) % (poly2->GetNumPoints())) {
+ newpoly[k] = poly2->GetPoint(j);
+ k++;
+ }
+
+ triangles.erase(iter2);
+ iter1->get() = newpoly;
+ poly1 = &(iter1->get());
+ i11 = -1;
+
+ continue;
+ }
+ }
+
+ for (iter1 = triangles.front(); iter1; iter1 = iter1->next()) {
+ parts->push_back(iter1->get());
+ }
+
+ return 1;
+}
+
+int TPPLPartition::ConvexPartition_HM(TPPLPolyList *inpolys, TPPLPolyList *parts) {
+ TPPLPolyList outpolys;
+ TPPLPolyList::Element *iter;
+
+ if (!RemoveHoles(inpolys, &outpolys)) {
+ return 0;
+ }
+ for (iter = outpolys.front(); iter; iter = iter->next()) {
+ if (!ConvexPartition_HM(&(iter->get()), parts)) {
+ return 0;
+ }
+ }
+ return 1;
+}
+
+// Minimum-weight polygon triangulation by dynamic programming.
+// Time complexity: O(n^3)
+// Space complexity: O(n^2)
+int TPPLPartition::Triangulate_OPT(TPPLPoly *poly, TPPLPolyList *triangles) {
+ if (!poly->Valid()) {
+ return 0;
+ }
+
+ long i, j, k, gap, n;
+ DPState **dpstates = NULL;
+ TPPLPoint p1, p2, p3, p4;
+ long bestvertex;
+ tppl_float weight, minweight, d1, d2;
+ Diagonal diagonal, newdiagonal;
+ DiagonalList diagonals;
+ TPPLPoly triangle;
+ int ret = 1;
+
+ n = poly->GetNumPoints();
+ dpstates = new DPState *[n];
+ for (i = 1; i < n; i++) {
+ dpstates[i] = new DPState[i];
+ }
+
+ // Initialize states and visibility.
+ for (i = 0; i < (n - 1); i++) {
+ p1 = poly->GetPoint(i);
+ for (j = i + 1; j < n; j++) {
+ dpstates[j][i].visible = true;
+ dpstates[j][i].weight = 0;
+ dpstates[j][i].bestvertex = -1;
+ if (j != (i + 1)) {
+ p2 = poly->GetPoint(j);
+
+ // Visibility check.
+ if (i == 0) {
+ p3 = poly->GetPoint(n - 1);
+ } else {
+ p3 = poly->GetPoint(i - 1);
+ }
+ if (i == (n - 1)) {
+ p4 = poly->GetPoint(0);
+ } else {
+ p4 = poly->GetPoint(i + 1);
+ }
+ if (!InCone(p3, p1, p4, p2)) {
+ dpstates[j][i].visible = false;
+ continue;
+ }
+
+ if (j == 0) {
+ p3 = poly->GetPoint(n - 1);
+ } else {
+ p3 = poly->GetPoint(j - 1);
+ }
+ if (j == (n - 1)) {
+ p4 = poly->GetPoint(0);
+ } else {
+ p4 = poly->GetPoint(j + 1);
+ }
+ if (!InCone(p3, p2, p4, p1)) {
+ dpstates[j][i].visible = false;
+ continue;
+ }
+
+ for (k = 0; k < n; k++) {
+ p3 = poly->GetPoint(k);
+ if (k == (n - 1)) {
+ p4 = poly->GetPoint(0);
+ } else {
+ p4 = poly->GetPoint(k + 1);
+ }
+ if (Intersects(p1, p2, p3, p4)) {
+ dpstates[j][i].visible = false;
+ break;
+ }
+ }
+ }
+ }
+ }
+ dpstates[n - 1][0].visible = true;
+ dpstates[n - 1][0].weight = 0;
+ dpstates[n - 1][0].bestvertex = -1;
+
+ for (gap = 2; gap < n; gap++) {
+ for (i = 0; i < (n - gap); i++) {
+ j = i + gap;
+ if (!dpstates[j][i].visible) {
+ continue;
+ }
+ bestvertex = -1;
+ for (k = (i + 1); k < j; k++) {
+ if (!dpstates[k][i].visible) {
+ continue;
+ }
+ if (!dpstates[j][k].visible) {
+ continue;
+ }
+
+ if (k <= (i + 1)) {
+ d1 = 0;
+ } else {
+ d1 = Distance(poly->GetPoint(i), poly->GetPoint(k));
+ }
+ if (j <= (k + 1)) {
+ d2 = 0;
+ } else {
+ d2 = Distance(poly->GetPoint(k), poly->GetPoint(j));
+ }
+
+ weight = dpstates[k][i].weight + dpstates[j][k].weight + d1 + d2;
+
+ if ((bestvertex == -1) || (weight < minweight)) {
+ bestvertex = k;
+ minweight = weight;
+ }
+ }
+ if (bestvertex == -1) {
+ for (i = 1; i < n; i++) {
+ delete[] dpstates[i];
+ }
+ delete[] dpstates;
+
+ return 0;
+ }
+
+ dpstates[j][i].bestvertex = bestvertex;
+ dpstates[j][i].weight = minweight;
+ }
+ }
+
+ newdiagonal.index1 = 0;
+ newdiagonal.index2 = n - 1;
+ diagonals.push_back(newdiagonal);
+ while (!diagonals.is_empty()) {
+ diagonal = diagonals.front()->get();
+ diagonals.pop_front();
+ bestvertex = dpstates[diagonal.index2][diagonal.index1].bestvertex;
+ if (bestvertex == -1) {
+ ret = 0;
+ break;
+ }
+ triangle.Triangle(poly->GetPoint(diagonal.index1), poly->GetPoint(bestvertex), poly->GetPoint(diagonal.index2));
+ triangles->push_back(triangle);
+ if (bestvertex > (diagonal.index1 + 1)) {
+ newdiagonal.index1 = diagonal.index1;
+ newdiagonal.index2 = bestvertex;
+ diagonals.push_back(newdiagonal);
+ }
+ if (diagonal.index2 > (bestvertex + 1)) {
+ newdiagonal.index1 = bestvertex;
+ newdiagonal.index2 = diagonal.index2;
+ diagonals.push_back(newdiagonal);
+ }
+ }
+
+ for (i = 1; i < n; i++) {
+ delete[] dpstates[i];
+ }
+ delete[] dpstates;
+
+ return ret;
+}
+
+void TPPLPartition::UpdateState(long a, long b, long w, long i, long j, DPState2 **dpstates) {
+ Diagonal newdiagonal;
+ DiagonalList *pairs = NULL;
+ long w2;
+
+ w2 = dpstates[a][b].weight;
+ if (w > w2) {
+ return;
+ }
+
+ pairs = &(dpstates[a][b].pairs);
+ newdiagonal.index1 = i;
+ newdiagonal.index2 = j;
+
+ if (w < w2) {
+ pairs->clear();
+ pairs->push_front(newdiagonal);
+ dpstates[a][b].weight = w;
+ } else {
+ if ((!pairs->is_empty()) && (i <= pairs->front()->get().index1)) {
+ return;
+ }
+ while ((!pairs->is_empty()) && (pairs->front()->get().index2 >= j)) {
+ pairs->pop_front();
+ }
+ pairs->push_front(newdiagonal);
+ }
+}
+
+void TPPLPartition::TypeA(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates) {
+ DiagonalList *pairs = NULL;
+ DiagonalList::Element *iter, *lastiter;
+ long top;
+ long w;
+
+ if (!dpstates[i][j].visible) {
+ return;
+ }
+ top = j;
+ w = dpstates[i][j].weight;
+ if (k - j > 1) {
+ if (!dpstates[j][k].visible) {
+ return;
+ }
+ w += dpstates[j][k].weight + 1;
+ }
+ if (j - i > 1) {
+ pairs = &(dpstates[i][j].pairs);
+ iter = pairs->back();
+ lastiter = pairs->back();
+ while (iter != pairs->front()) {
+ iter--;
+ if (!IsReflex(vertices[iter->get().index2].p, vertices[j].p, vertices[k].p)) {
+ lastiter = iter;
+ } else {
+ break;
+ }
+ }
+ if (lastiter == pairs->back()) {
+ w++;
+ } else {
+ if (IsReflex(vertices[k].p, vertices[i].p, vertices[lastiter->get().index1].p)) {
+ w++;
+ } else {
+ top = lastiter->get().index1;
+ }
+ }
+ }
+ UpdateState(i, k, w, top, j, dpstates);
+}
+
+void TPPLPartition::TypeB(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates) {
+ DiagonalList *pairs = NULL;
+ DiagonalList::Element *iter, *lastiter;
+ long top;
+ long w;
+
+ if (!dpstates[j][k].visible) {
+ return;
+ }
+ top = j;
+ w = dpstates[j][k].weight;
+
+ if (j - i > 1) {
+ if (!dpstates[i][j].visible) {
+ return;
+ }
+ w += dpstates[i][j].weight + 1;
+ }
+ if (k - j > 1) {
+ pairs = &(dpstates[j][k].pairs);
+
+ iter = pairs->front();
+ if ((!pairs->is_empty()) && (!IsReflex(vertices[i].p, vertices[j].p, vertices[iter->get().index1].p))) {
+ lastiter = iter;
+ while (iter) {
+ if (!IsReflex(vertices[i].p, vertices[j].p, vertices[iter->get().index1].p)) {
+ lastiter = iter;
+ iter = iter->next();
+ } else {
+ break;
+ }
+ }
+ if (IsReflex(vertices[lastiter->get().index2].p, vertices[k].p, vertices[i].p)) {
+ w++;
+ } else {
+ top = lastiter->get().index2;
+ }
+ } else {
+ w++;
+ }
+ }
+ UpdateState(i, k, w, j, top, dpstates);
+}
+
+int TPPLPartition::ConvexPartition_OPT(TPPLPoly *poly, TPPLPolyList *parts) {
+ if (!poly->Valid()) {
+ return 0;
+ }
+
+ TPPLPoint p1, p2, p3, p4;
+ PartitionVertex *vertices = NULL;
+ DPState2 **dpstates = NULL;
+ long i, j, k, n, gap;
+ DiagonalList diagonals, diagonals2;
+ Diagonal diagonal, newdiagonal;
+ DiagonalList *pairs = NULL, *pairs2 = NULL;
+ DiagonalList::Element *iter, *iter2;
+ int ret;
+ TPPLPoly newpoly;
+ List<long> indices;
+ List<long>::Element *iiter;
+ bool ijreal, jkreal;
+
+ n = poly->GetNumPoints();
+ vertices = new PartitionVertex[n];
+
+ dpstates = new DPState2 *[n];
+ for (i = 0; i < n; i++) {
+ dpstates[i] = new DPState2[n];
+ }
+
+ // Initialize vertex information.
+ for (i = 0; i < n; i++) {
+ vertices[i].p = poly->GetPoint(i);
+ vertices[i].isActive = true;
+ if (i == 0) {
+ vertices[i].previous = &(vertices[n - 1]);
+ } else {
+ vertices[i].previous = &(vertices[i - 1]);
+ }
+ if (i == (poly->GetNumPoints() - 1)) {
+ vertices[i].next = &(vertices[0]);
+ } else {
+ vertices[i].next = &(vertices[i + 1]);
+ }
+ }
+ for (i = 1; i < n; i++) {
+ UpdateVertexReflexity(&(vertices[i]));
+ }
+
+ // Initialize states and visibility.
+ for (i = 0; i < (n - 1); i++) {
+ p1 = poly->GetPoint(i);
+ for (j = i + 1; j < n; j++) {
+ dpstates[i][j].visible = true;
+ if (j == i + 1) {
+ dpstates[i][j].weight = 0;
+ } else {
+ dpstates[i][j].weight = 2147483647;
+ }
+ if (j != (i + 1)) {
+ p2 = poly->GetPoint(j);
+
+ // Visibility check.
+ if (!InCone(&vertices[i], p2)) {
+ dpstates[i][j].visible = false;
+ continue;
+ }
+ if (!InCone(&vertices[j], p1)) {
+ dpstates[i][j].visible = false;
+ continue;
+ }
+
+ for (k = 0; k < n; k++) {
+ p3 = poly->GetPoint(k);
+ if (k == (n - 1)) {
+ p4 = poly->GetPoint(0);
+ } else {
+ p4 = poly->GetPoint(k + 1);
+ }
+ if (Intersects(p1, p2, p3, p4)) {
+ dpstates[i][j].visible = false;
+ break;
+ }
+ }
+ }
+ }
+ }
+ for (i = 0; i < (n - 2); i++) {
+ j = i + 2;
+ if (dpstates[i][j].visible) {
+ dpstates[i][j].weight = 0;
+ newdiagonal.index1 = i + 1;
+ newdiagonal.index2 = i + 1;
+ dpstates[i][j].pairs.push_back(newdiagonal);
+ }
+ }
+
+ dpstates[0][n - 1].visible = true;
+ vertices[0].isConvex = false; // By convention.
+
+ for (gap = 3; gap < n; gap++) {
+ for (i = 0; i < n - gap; i++) {
+ if (vertices[i].isConvex) {
+ continue;
+ }
+ k = i + gap;
+ if (dpstates[i][k].visible) {
+ if (!vertices[k].isConvex) {
+ for (j = i + 1; j < k; j++) {
+ TypeA(i, j, k, vertices, dpstates);
+ }
+ } else {
+ for (j = i + 1; j < (k - 1); j++) {
+ if (vertices[j].isConvex) {
+ continue;
+ }
+ TypeA(i, j, k, vertices, dpstates);
+ }
+ TypeA(i, k - 1, k, vertices, dpstates);
+ }
+ }
+ }
+ for (k = gap; k < n; k++) {
+ if (vertices[k].isConvex) {
+ continue;
+ }
+ i = k - gap;
+ if ((vertices[i].isConvex) && (dpstates[i][k].visible)) {
+ TypeB(i, i + 1, k, vertices, dpstates);
+ for (j = i + 2; j < k; j++) {
+ if (vertices[j].isConvex) {
+ continue;
+ }
+ TypeB(i, j, k, vertices, dpstates);
+ }
+ }
+ }
+ }
+
+ // Recover solution.
+ ret = 1;
+ newdiagonal.index1 = 0;
+ newdiagonal.index2 = n - 1;
+ diagonals.push_front(newdiagonal);
+ while (!diagonals.is_empty()) {
+ diagonal = diagonals.front()->get();
+ diagonals.pop_front();
+ if ((diagonal.index2 - diagonal.index1) <= 1) {
+ continue;
+ }
+ pairs = &(dpstates[diagonal.index1][diagonal.index2].pairs);
+ if (pairs->is_empty()) {
+ ret = 0;
+ break;
+ }
+ if (!vertices[diagonal.index1].isConvex) {
+ iter = pairs->back();
+ iter--;
+ j = iter->get().index2;
+ newdiagonal.index1 = j;
+ newdiagonal.index2 = diagonal.index2;
+ diagonals.push_front(newdiagonal);
+ if ((j - diagonal.index1) > 1) {
+ if (iter->get().index1 != iter->get().index2) {
+ pairs2 = &(dpstates[diagonal.index1][j].pairs);
+ while (1) {
+ if (pairs2->is_empty()) {
+ ret = 0;
+ break;
+ }
+ iter2 = pairs2->back();
+ iter2--;
+ if (iter->get().index1 != iter2->get().index1) {
+ pairs2->pop_back();
+ } else {
+ break;
+ }
+ }
+ if (ret == 0) {
+ break;
+ }
+ }
+ newdiagonal.index1 = diagonal.index1;
+ newdiagonal.index2 = j;
+ diagonals.push_front(newdiagonal);
+ }
+ } else {
+ iter = pairs->front();
+ j = iter->get().index1;
+ newdiagonal.index1 = diagonal.index1;
+ newdiagonal.index2 = j;
+ diagonals.push_front(newdiagonal);
+ if ((diagonal.index2 - j) > 1) {
+ if (iter->get().index1 != iter->get().index2) {
+ pairs2 = &(dpstates[j][diagonal.index2].pairs);
+ while (1) {
+ if (pairs2->is_empty()) {
+ ret = 0;
+ break;
+ }
+ iter2 = pairs2->front();
+ if (iter->get().index2 != iter2->get().index2) {
+ pairs2->pop_front();
+ } else {
+ break;
+ }
+ }
+ if (ret == 0) {
+ break;
+ }
+ }
+ newdiagonal.index1 = j;
+ newdiagonal.index2 = diagonal.index2;
+ diagonals.push_front(newdiagonal);
+ }
+ }
+ }
+
+ if (ret == 0) {
+ for (i = 0; i < n; i++) {
+ delete[] dpstates[i];
+ }
+ delete[] dpstates;
+ delete[] vertices;
+
+ return ret;
+ }
+
+ newdiagonal.index1 = 0;
+ newdiagonal.index2 = n - 1;
+ diagonals.push_front(newdiagonal);
+ while (!diagonals.is_empty()) {
+ diagonal = diagonals.front()->get();
+ diagonals.pop_front();
+ if ((diagonal.index2 - diagonal.index1) <= 1) {
+ continue;
+ }
+
+ indices.clear();
+ diagonals2.clear();
+ indices.push_back(diagonal.index1);
+ indices.push_back(diagonal.index2);
+ diagonals2.push_front(diagonal);
+
+ while (!diagonals2.is_empty()) {
+ diagonal = diagonals2.front()->get();
+ diagonals2.pop_front();
+ if ((diagonal.index2 - diagonal.index1) <= 1) {
+ continue;
+ }
+ ijreal = true;
+ jkreal = true;
+ pairs = &(dpstates[diagonal.index1][diagonal.index2].pairs);
+ if (!vertices[diagonal.index1].isConvex) {
+ iter = pairs->back();
+ iter--;
+ j = iter->get().index2;
+ if (iter->get().index1 != iter->get().index2) {
+ ijreal = false;
+ }
+ } else {
+ iter = pairs->front();
+ j = iter->get().index1;
+ if (iter->get().index1 != iter->get().index2) {
+ jkreal = false;
+ }
+ }
+
+ newdiagonal.index1 = diagonal.index1;
+ newdiagonal.index2 = j;
+ if (ijreal) {
+ diagonals.push_back(newdiagonal);
+ } else {
+ diagonals2.push_back(newdiagonal);
+ }
+
+ newdiagonal.index1 = j;
+ newdiagonal.index2 = diagonal.index2;
+ if (jkreal) {
+ diagonals.push_back(newdiagonal);
+ } else {
+ diagonals2.push_back(newdiagonal);
+ }
+
+ indices.push_back(j);
+ }
+
+ //std::sort(indices.begin(), indices.end());
+ indices.sort();
+ newpoly.Init((long)indices.size());
+ k = 0;
+ for (iiter = indices.front(); iiter != indices.back(); iiter = iiter->next()) {
+ newpoly[k] = vertices[iiter->get()].p;
+ k++;
+ }
+ parts->push_back(newpoly);
+ }
+
+ for (i = 0; i < n; i++) {
+ delete[] dpstates[i];
+ }
+ delete[] dpstates;
+ delete[] vertices;
+
+ return ret;
+}
+
+// Creates a monotone partition of a list of polygons that
+// can contain holes. Triangulates a set of polygons by
+// first partitioning them into monotone polygons.
+// Time complexity: O(n*log(n)), n is the number of vertices.
+// Space complexity: O(n)
+// The algorithm used here is outlined in the book
+// "Computational Geometry: Algorithms and Applications"
+// by Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars.
+int TPPLPartition::MonotonePartition(TPPLPolyList *inpolys, TPPLPolyList *monotonePolys) {
+ TPPLPolyList::Element *iter;
+ MonotoneVertex *vertices = NULL;
+ long i, numvertices, vindex, vindex2, newnumvertices, maxnumvertices;
+ long polystartindex, polyendindex;
+ TPPLPoly *poly = NULL;
+ MonotoneVertex *v = NULL, *v2 = NULL, *vprev = NULL, *vnext = NULL;
+ ScanLineEdge newedge;
+ bool error = false;
+
+ numvertices = 0;
+ for (iter = inpolys->front(); iter; iter = iter->next()) {
+ numvertices += iter->get().GetNumPoints();
+ }
+
+ maxnumvertices = numvertices * 3;
+ vertices = new MonotoneVertex[maxnumvertices];
+ newnumvertices = numvertices;
+
+ polystartindex = 0;
+ for (iter = inpolys->front(); iter; iter = iter->next()) {
+ poly = &(iter->get());
+ polyendindex = polystartindex + poly->GetNumPoints() - 1;
+ for (i = 0; i < poly->GetNumPoints(); i++) {
+ vertices[i + polystartindex].p = poly->GetPoint(i);
+ if (i == 0) {
+ vertices[i + polystartindex].previous = polyendindex;
+ } else {
+ vertices[i + polystartindex].previous = i + polystartindex - 1;
+ }
+ if (i == (poly->GetNumPoints() - 1)) {
+ vertices[i + polystartindex].next = polystartindex;
+ } else {
+ vertices[i + polystartindex].next = i + polystartindex + 1;
+ }
+ }
+ polystartindex = polyendindex + 1;
+ }
+
+ // Construct the priority queue.
+ long *priority = new long[numvertices];
+ for (i = 0; i < numvertices; i++) {
+ priority[i] = i;
+ }
+ std::sort(priority, &(priority[numvertices]), VertexSorter(vertices));
+
+ // Determine vertex types.
+ TPPLVertexType *vertextypes = new TPPLVertexType[maxnumvertices];
+ for (i = 0; i < numvertices; i++) {
+ v = &(vertices[i]);
+ vprev = &(vertices[v->previous]);
+ vnext = &(vertices[v->next]);
+
+ if (Below(vprev->p, v->p) && Below(vnext->p, v->p)) {
+ if (IsConvex(vnext->p, vprev->p, v->p)) {
+ vertextypes[i] = TPPL_VERTEXTYPE_START;
+ } else {
+ vertextypes[i] = TPPL_VERTEXTYPE_SPLIT;
+ }
+ } else if (Below(v->p, vprev->p) && Below(v->p, vnext->p)) {
+ if (IsConvex(vnext->p, vprev->p, v->p)) {
+ vertextypes[i] = TPPL_VERTEXTYPE_END;
+ } else {
+ vertextypes[i] = TPPL_VERTEXTYPE_MERGE;
+ }
+ } else {
+ vertextypes[i] = TPPL_VERTEXTYPE_REGULAR;
+ }
+ }
+
+ // Helpers.
+ long *helpers = new long[maxnumvertices];
+
+ // Binary search tree that holds edges intersecting the scanline.
+ // Note that while set doesn't actually have to be implemented as
+ // a tree, complexity requirements for operations are the same as
+ // for the balanced binary search tree.
+ Set<ScanLineEdge> edgeTree;
+ // Store iterators to the edge tree elements.
+ // This makes deleting existing edges much faster.
+ Set<ScanLineEdge>::Element **edgeTreeIterators, *edgeIter;
+ edgeTreeIterators = new Set<ScanLineEdge>::Element *[maxnumvertices];
+ //Pair<Set<ScanLineEdge>::iterator, bool> edgeTreeRet;
+ for (i = 0; i < numvertices; i++) {
+ edgeTreeIterators[i] = nullptr;
+ }
+
+ // For each vertex.
+ for (i = 0; i < numvertices; i++) {
+ vindex = priority[i];
+ v = &(vertices[vindex]);
+ vindex2 = vindex;
+ v2 = v;
+
+ // Depending on the vertex type, do the appropriate action.
+ // Comments in the following sections are copied from
+ // "Computational Geometry: Algorithms and Applications".
+ // Notation: e_i = e subscript i, v_i = v subscript i, etc.
+ switch (vertextypes[vindex]) {
+ case TPPL_VERTEXTYPE_START:
+ // Insert e_i in T and set helper(e_i) to v_i.
+ newedge.p1 = v->p;
+ newedge.p2 = vertices[v->next].p;
+ newedge.index = vindex;
+ //edgeTreeRet = edgeTree.insert(newedge);
+ //edgeTreeIterators[vindex] = edgeTreeRet.first;
+ edgeTreeIterators[vindex] = edgeTree.insert(newedge);
+ helpers[vindex] = vindex;
+ break;
+
+ case TPPL_VERTEXTYPE_END:
+ if (edgeTreeIterators[v->previous] == edgeTree.back()) {
+ error = true;
+ break;
+ }
+ // If helper(e_i - 1) is a merge vertex
+ if (vertextypes[helpers[v->previous]] == TPPL_VERTEXTYPE_MERGE) {
+ // Insert the diagonal connecting vi to helper(e_i - 1) in D.
+ AddDiagonal(vertices, &newnumvertices, vindex, helpers[v->previous],
+ vertextypes, edgeTreeIterators, &edgeTree, helpers);
+ }
+ // Delete e_i - 1 from T
+ edgeTree.erase(edgeTreeIterators[v->previous]);
+ break;
+
+ case TPPL_VERTEXTYPE_SPLIT:
+ // Search in T to find the edge e_j directly left of v_i.
+ newedge.p1 = v->p;
+ newedge.p2 = v->p;
+ edgeIter = edgeTree.lower_bound(newedge);
+ if (edgeIter == nullptr || edgeIter == edgeTree.front()) {
+ error = true;
+ break;
+ }
+ edgeIter--;
+ // Insert the diagonal connecting vi to helper(e_j) in D.
+ AddDiagonal(vertices, &newnumvertices, vindex, helpers[edgeIter->get().index],
+ vertextypes, edgeTreeIterators, &edgeTree, helpers);
+ vindex2 = newnumvertices - 2;
+ v2 = &(vertices[vindex2]);
+ // helper(e_j) in v_i.
+ helpers[edgeIter->get().index] = vindex;
+ // Insert e_i in T and set helper(e_i) to v_i.
+ newedge.p1 = v2->p;
+ newedge.p2 = vertices[v2->next].p;
+ newedge.index = vindex2;
+ //edgeTreeRet = edgeTree.insert(newedge);
+ //edgeTreeIterators[vindex2] = edgeTreeRet.first;
+ edgeTreeIterators[vindex2] = edgeTree.insert(newedge);
+ helpers[vindex2] = vindex2;
+ break;
+
+ case TPPL_VERTEXTYPE_MERGE:
+ if (edgeTreeIterators[v->previous] == edgeTree.back()) {
+ error = true;
+ break;
+ }
+ // if helper(e_i - 1) is a merge vertex
+ if (vertextypes[helpers[v->previous]] == TPPL_VERTEXTYPE_MERGE) {
+ // Insert the diagonal connecting vi to helper(e_i - 1) in D.
+ AddDiagonal(vertices, &newnumvertices, vindex, helpers[v->previous],
+ vertextypes, edgeTreeIterators, &edgeTree, helpers);
+ vindex2 = newnumvertices - 2;
+ v2 = &(vertices[vindex2]);
+ }
+ // Delete e_i - 1 from T.
+ edgeTree.erase(edgeTreeIterators[v->previous]);
+ // Search in T to find the edge e_j directly left of v_i.
+ newedge.p1 = v->p;
+ newedge.p2 = v->p;
+ edgeIter = edgeTree.lower_bound(newedge);
+ if (edgeIter == nullptr || edgeIter == edgeTree.front()) {
+ error = true;
+ break;
+ }
+ edgeIter--;
+ // If helper(e_j) is a merge vertex.
+ if (vertextypes[helpers[edgeIter->get().index]] == TPPL_VERTEXTYPE_MERGE) {
+ // Insert the diagonal connecting v_i to helper(e_j) in D.
+ AddDiagonal(vertices, &newnumvertices, vindex2, helpers[edgeIter->get().index],
+ vertextypes, edgeTreeIterators, &edgeTree, helpers);
+ }
+ // helper(e_j) <- v_i
+ helpers[edgeIter->get().index] = vindex2;
+ break;
+
+ case TPPL_VERTEXTYPE_REGULAR:
+ // If the interior of P lies to the right of v_i.
+ if (Below(v->p, vertices[v->previous].p)) {
+ if (edgeTreeIterators[v->previous] == edgeTree.back()) {
+ error = true;
+ break;
+ }
+ // If helper(e_i - 1) is a merge vertex.
+ if (vertextypes[helpers[v->previous]] == TPPL_VERTEXTYPE_MERGE) {
+ // Insert the diagonal connecting v_i to helper(e_i - 1) in D.
+ AddDiagonal(vertices, &newnumvertices, vindex, helpers[v->previous],
+ vertextypes, edgeTreeIterators, &edgeTree, helpers);
+ vindex2 = newnumvertices - 2;
+ v2 = &(vertices[vindex2]);
+ }
+ // Delete e_i - 1 from T.
+ edgeTree.erase(edgeTreeIterators[v->previous]);
+ // Insert e_i in T and set helper(e_i) to v_i.
+ newedge.p1 = v2->p;
+ newedge.p2 = vertices[v2->next].p;
+ newedge.index = vindex2;
+ //edgeTreeRet = edgeTree.insert(newedge);
+ //edgeTreeIterators[vindex2] = edgeTreeRet.first;
+ edgeTreeIterators[vindex2] = edgeTree.insert(newedge);
+ helpers[vindex2] = vindex;
+ } else {
+ // Search in T to find the edge e_j directly left of v_i.
+ newedge.p1 = v->p;
+ newedge.p2 = v->p;
+ edgeIter = edgeTree.lower_bound(newedge);
+ if (edgeIter == nullptr || edgeIter == edgeTree.front()) {
+ error = true;
+ break;
+ }
+ edgeIter = edgeIter->prev();
+ // If helper(e_j) is a merge vertex.
+ if (vertextypes[helpers[edgeIter->get().index]] == TPPL_VERTEXTYPE_MERGE) {
+ // Insert the diagonal connecting v_i to helper(e_j) in D.
+ AddDiagonal(vertices, &newnumvertices, vindex, helpers[edgeIter->get().index],
+ vertextypes, edgeTreeIterators, &edgeTree, helpers);
+ }
+ // helper(e_j) <- v_i.
+ helpers[edgeIter->get().index] = vindex;
+ }
+ break;
+ }
+
+ if (error)
+ break;
+ }
+
+ char *used = new char[newnumvertices];
+ memset(used, 0, newnumvertices * sizeof(char));
+
+ if (!error) {
+ // Return result.
+ long size;
+ TPPLPoly mpoly;
+ for (i = 0; i < newnumvertices; i++) {
+ if (used[i]) {
+ continue;
+ }
+ v = &(vertices[i]);
+ vnext = &(vertices[v->next]);
+ size = 1;
+ while (vnext != v) {
+ vnext = &(vertices[vnext->next]);
+ size++;
+ }
+ mpoly.Init(size);
+ v = &(vertices[i]);
+ mpoly[0] = v->p;
+ vnext = &(vertices[v->next]);
+ size = 1;
+ used[i] = 1;
+ used[v->next] = 1;
+ while (vnext != v) {
+ mpoly[size] = vnext->p;
+ used[vnext->next] = 1;
+ vnext = &(vertices[vnext->next]);
+ size++;
+ }
+ monotonePolys->push_back(mpoly);
+ }
+ }
+
+ // Cleanup.
+ delete[] vertices;
+ delete[] priority;
+ delete[] vertextypes;
+ delete[] edgeTreeIterators;
+ delete[] helpers;
+ delete[] used;
+
+ if (error) {
+ return 0;
+ } else {
+ return 1;
+ }
+}
+
+// Adds a diagonal to the doubly-connected list of vertices.
+void TPPLPartition::AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2,
+ TPPLVertexType *vertextypes, Set<ScanLineEdge>::Element **edgeTreeIterators,
+ Set<ScanLineEdge> *edgeTree, long *helpers) {
+ long newindex1, newindex2;
+
+ newindex1 = *numvertices;
+ (*numvertices)++;
+ newindex2 = *numvertices;
+ (*numvertices)++;
+
+ vertices[newindex1].p = vertices[index1].p;
+ vertices[newindex2].p = vertices[index2].p;
+
+ vertices[newindex2].next = vertices[index2].next;
+ vertices[newindex1].next = vertices[index1].next;
+
+ vertices[vertices[index2].next].previous = newindex2;
+ vertices[vertices[index1].next].previous = newindex1;
+
+ vertices[index1].next = newindex2;
+ vertices[newindex2].previous = index1;
+
+ vertices[index2].next = newindex1;
+ vertices[newindex1].previous = index2;
+
+ // Update all relevant structures.
+ vertextypes[newindex1] = vertextypes[index1];
+ edgeTreeIterators[newindex1] = edgeTreeIterators[index1];
+ helpers[newindex1] = helpers[index1];
+ if (edgeTreeIterators[newindex1] != edgeTree->back()) {
+ edgeTreeIterators[newindex1]->get().index = newindex1;
+ }
+ vertextypes[newindex2] = vertextypes[index2];
+ edgeTreeIterators[newindex2] = edgeTreeIterators[index2];
+ helpers[newindex2] = helpers[index2];
+ if (edgeTreeIterators[newindex2] != edgeTree->back()) {
+ edgeTreeIterators[newindex2]->get().index = newindex2;
+ }
+}
+
+bool TPPLPartition::Below(TPPLPoint &p1, TPPLPoint &p2) {
+ if (p1.y < p2.y) {
+ return true;
+ } else if (p1.y == p2.y) {
+ if (p1.x < p2.x) {
+ return true;
+ }
+ }
+ return false;
+}
+
+// Sorts in the falling order of y values, if y is equal, x is used instead.
+bool TPPLPartition::VertexSorter::operator()(long index1, long index2) {
+ if (vertices[index1].p.y > vertices[index2].p.y) {
+ return true;
+ } else if (vertices[index1].p.y == vertices[index2].p.y) {
+ if (vertices[index1].p.x > vertices[index2].p.x) {
+ return true;
+ }
+ }
+ return false;
+}
+
+bool TPPLPartition::ScanLineEdge::IsConvex(const TPPLPoint &p1, const TPPLPoint &p2, const TPPLPoint &p3) const {
+ tppl_float tmp;
+ tmp = (p3.y - p1.y) * (p2.x - p1.x) - (p3.x - p1.x) * (p2.y - p1.y);
+ if (tmp > 0) {
+ return 1;
+ }
+
+ return 0;
+}
+
+bool TPPLPartition::ScanLineEdge::operator<(const ScanLineEdge &other) const {
+ if (other.p1.y == other.p2.y) {
+ if (p1.y == p2.y) {
+ return (p1.y < other.p1.y);
+ }
+ return IsConvex(p1, p2, other.p1);
+ } else if (p1.y == p2.y) {
+ return !IsConvex(other.p1, other.p2, p1);
+ } else if (p1.y < other.p1.y) {
+ return !IsConvex(other.p1, other.p2, p1);
+ } else {
+ return IsConvex(p1, p2, other.p1);
+ }
+}
+
+// Triangulates monotone polygon.
+// Time complexity: O(n)
+// Space complexity: O(n)
+int TPPLPartition::TriangulateMonotone(TPPLPoly *inPoly, TPPLPolyList *triangles) {
+ if (!inPoly->Valid()) {
+ return 0;
+ }
+
+ long i, i2, j, topindex, bottomindex, leftindex, rightindex, vindex;
+ TPPLPoint *points = NULL;
+ long numpoints;
+ TPPLPoly triangle;
+
+ numpoints = inPoly->GetNumPoints();
+ points = inPoly->GetPoints();
+
+ // Trivial case.
+ if (numpoints == 3) {
+ triangles->push_back(*inPoly);
+ return 1;
+ }
+
+ topindex = 0;
+ bottomindex = 0;
+ for (i = 1; i < numpoints; i++) {
+ if (Below(points[i], points[bottomindex])) {
+ bottomindex = i;
+ }
+ if (Below(points[topindex], points[i])) {
+ topindex = i;
+ }
+ }
+
+ // Check if the poly is really monotone.
+ i = topindex;
+ while (i != bottomindex) {
+ i2 = i + 1;
+ if (i2 >= numpoints) {
+ i2 = 0;
+ }
+ if (!Below(points[i2], points[i])) {
+ return 0;
+ }
+ i = i2;
+ }
+ i = bottomindex;
+ while (i != topindex) {
+ i2 = i + 1;
+ if (i2 >= numpoints) {
+ i2 = 0;
+ }
+ if (!Below(points[i], points[i2])) {
+ return 0;
+ }
+ i = i2;
+ }
+
+ char *vertextypes = new char[numpoints];
+ long *priority = new long[numpoints];
+
+ // Merge left and right vertex chains.
+ priority[0] = topindex;
+ vertextypes[topindex] = 0;
+ leftindex = topindex + 1;
+ if (leftindex >= numpoints) {
+ leftindex = 0;
+ }
+ rightindex = topindex - 1;
+ if (rightindex < 0) {
+ rightindex = numpoints - 1;
+ }
+ for (i = 1; i < (numpoints - 1); i++) {
+ if (leftindex == bottomindex) {
+ priority[i] = rightindex;
+ rightindex--;
+ if (rightindex < 0) {
+ rightindex = numpoints - 1;
+ }
+ vertextypes[priority[i]] = -1;
+ } else if (rightindex == bottomindex) {
+ priority[i] = leftindex;
+ leftindex++;
+ if (leftindex >= numpoints) {
+ leftindex = 0;
+ }
+ vertextypes[priority[i]] = 1;
+ } else {
+ if (Below(points[leftindex], points[rightindex])) {
+ priority[i] = rightindex;
+ rightindex--;
+ if (rightindex < 0) {
+ rightindex = numpoints - 1;
+ }
+ vertextypes[priority[i]] = -1;
+ } else {
+ priority[i] = leftindex;
+ leftindex++;
+ if (leftindex >= numpoints) {
+ leftindex = 0;
+ }
+ vertextypes[priority[i]] = 1;
+ }
+ }
+ }
+ priority[i] = bottomindex;
+ vertextypes[bottomindex] = 0;
+
+ long *stack = new long[numpoints];
+ long stackptr = 0;
+
+ stack[0] = priority[0];
+ stack[1] = priority[1];
+ stackptr = 2;
+
+ // For each vertex from top to bottom trim as many triangles as possible.
+ for (i = 2; i < (numpoints - 1); i++) {
+ vindex = priority[i];
+ if (vertextypes[vindex] != vertextypes[stack[stackptr - 1]]) {
+ for (j = 0; j < (stackptr - 1); j++) {
+ if (vertextypes[vindex] == 1) {
+ triangle.Triangle(points[stack[j + 1]], points[stack[j]], points[vindex]);
+ } else {
+ triangle.Triangle(points[stack[j]], points[stack[j + 1]], points[vindex]);
+ }
+ triangles->push_back(triangle);
+ }
+ stack[0] = priority[i - 1];
+ stack[1] = priority[i];
+ stackptr = 2;
+ } else {
+ stackptr--;
+ while (stackptr > 0) {
+ if (vertextypes[vindex] == 1) {
+ if (IsConvex(points[vindex], points[stack[stackptr - 1]], points[stack[stackptr]])) {
+ triangle.Triangle(points[vindex], points[stack[stackptr - 1]], points[stack[stackptr]]);
+ triangles->push_back(triangle);
+ stackptr--;
+ } else {
+ break;
+ }
+ } else {
+ if (IsConvex(points[vindex], points[stack[stackptr]], points[stack[stackptr - 1]])) {
+ triangle.Triangle(points[vindex], points[stack[stackptr]], points[stack[stackptr - 1]]);
+ triangles->push_back(triangle);
+ stackptr--;
+ } else {
+ break;
+ }
+ }
+ }
+ stackptr++;
+ stack[stackptr] = vindex;
+ stackptr++;
+ }
+ }
+ vindex = priority[i];
+ for (j = 0; j < (stackptr - 1); j++) {
+ if (vertextypes[stack[j + 1]] == 1) {
+ triangle.Triangle(points[stack[j]], points[stack[j + 1]], points[vindex]);
+ } else {
+ triangle.Triangle(points[stack[j + 1]], points[stack[j]], points[vindex]);
+ }
+ triangles->push_back(triangle);
+ }
+
+ delete[] priority;
+ delete[] vertextypes;
+ delete[] stack;
+
+ return 1;
+}
+
+int TPPLPartition::Triangulate_MONO(TPPLPolyList *inpolys, TPPLPolyList *triangles) {
+ TPPLPolyList monotone;
+ TPPLPolyList::Element *iter;
+
+ if (!MonotonePartition(inpolys, &monotone)) {
+ return 0;
+ }
+ for (iter = monotone.front(); iter; iter = iter->next()) {
+ if (!TriangulateMonotone(&(iter->get()), triangles)) {
+ return 0;
+ }
+ }
+ return 1;
+}
+
+int TPPLPartition::Triangulate_MONO(TPPLPoly *poly, TPPLPolyList *triangles) {
+ TPPLPolyList polys;
+ polys.push_back(*poly);
+
+ return Triangulate_MONO(&polys, triangles);
+}
diff --git a/thirdparty/misc/polypartition.h b/thirdparty/misc/polypartition.h
new file mode 100644
index 0000000000..b2d905a3ef
--- /dev/null
+++ b/thirdparty/misc/polypartition.h
@@ -0,0 +1,378 @@
+/*************************************************************************/
+/* Copyright (c) 2011-2021 Ivan Fratric and contributors. */
+/* */
+/* Permission is hereby granted, free of charge, to any person obtaining */
+/* a copy of this software and associated documentation files (the */
+/* "Software"), to deal in the Software without restriction, including */
+/* without limitation the rights to use, copy, modify, merge, publish, */
+/* distribute, sublicense, and/or sell copies of the Software, and to */
+/* permit persons to whom the Software is furnished to do so, subject to */
+/* the following conditions: */
+/* */
+/* The above copyright notice and this permission notice shall be */
+/* included in all copies or substantial portions of the Software. */
+/* */
+/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
+/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
+/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/
+/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
+/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
+/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
+/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
+/*************************************************************************/
+
+#ifndef POLYPARTITION_H
+#define POLYPARTITION_H
+
+#include "core/math/vector2.h"
+#include "core/templates/list.h"
+#include "core/templates/set.h"
+
+typedef double tppl_float;
+
+enum TPPLOrientation {
+ TPPL_ORIENTATION_CW = -1,
+ TPPL_ORIENTATION_NONE = 0,
+ TPPL_ORIENTATION_CCW = 1,
+};
+
+enum TPPLVertexType {
+ TPPL_VERTEXTYPE_REGULAR = 0,
+ TPPL_VERTEXTYPE_START = 1,
+ TPPL_VERTEXTYPE_END = 2,
+ TPPL_VERTEXTYPE_SPLIT = 3,
+ TPPL_VERTEXTYPE_MERGE = 4,
+};
+
+// 2D point structure.
+typedef Vector2 TPPLPoint;
+
+// Polygon implemented as an array of points with a "hole" flag.
+class TPPLPoly {
+ protected:
+ TPPLPoint *points;
+ long numpoints;
+ bool hole;
+
+ public:
+ // Constructors and destructors.
+ TPPLPoly();
+ ~TPPLPoly();
+
+ TPPLPoly(const TPPLPoly &src);
+ TPPLPoly &operator=(const TPPLPoly &src);
+
+ // Getters and setters.
+ long GetNumPoints() const {
+ return numpoints;
+ }
+
+ bool IsHole() const {
+ return hole;
+ }
+
+ void SetHole(bool hole) {
+ this->hole = hole;
+ }
+
+ TPPLPoint &GetPoint(long i) {
+ return points[i];
+ }
+
+ const TPPLPoint &GetPoint(long i) const {
+ return points[i];
+ }
+
+ TPPLPoint *GetPoints() {
+ return points;
+ }
+
+ TPPLPoint &operator[](int i) {
+ return points[i];
+ }
+
+ const TPPLPoint &operator[](int i) const {
+ return points[i];
+ }
+
+ // Clears the polygon points.
+ void Clear();
+
+ // Inits the polygon with numpoints vertices.
+ void Init(long numpoints);
+
+ // Creates a triangle with points p1, p2, and p3.
+ void Triangle(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3);
+
+ // Inverts the orfer of vertices.
+ void Invert();
+
+ // Returns the orientation of the polygon.
+ // Possible values:
+ // TPPL_ORIENTATION_CCW: Polygon vertices are in counter-clockwise order.
+ // TPPL_ORIENTATION_CW: Polygon vertices are in clockwise order.
+ // TPPL_ORIENTATION_NONE: The polygon has no (measurable) area.
+ TPPLOrientation GetOrientation() const;
+
+ // Sets the polygon orientation.
+ // Possible values:
+ // TPPL_ORIENTATION_CCW: Sets vertices in counter-clockwise order.
+ // TPPL_ORIENTATION_CW: Sets vertices in clockwise order.
+ // TPPL_ORIENTATION_NONE: Reverses the orientation of the vertices if there
+ // is one, otherwise does nothing (if orientation is already NONE).
+ void SetOrientation(TPPLOrientation orientation);
+
+ // Checks whether a polygon is valid or not.
+ inline bool Valid() const { return this->numpoints >= 3; }
+};
+
+#ifdef TPPL_ALLOCATOR
+typedef List<TPPLPoly, TPPL_ALLOCATOR(TPPLPoly)> TPPLPolyList;
+#else
+typedef List<TPPLPoly> TPPLPolyList;
+#endif
+
+class TPPLPartition {
+ protected:
+ struct PartitionVertex {
+ bool isActive;
+ bool isConvex;
+ bool isEar;
+
+ TPPLPoint p;
+ tppl_float angle;
+ PartitionVertex *previous;
+ PartitionVertex *next;
+
+ PartitionVertex();
+ };
+
+ struct MonotoneVertex {
+ TPPLPoint p;
+ long previous;
+ long next;
+ };
+
+ class VertexSorter {
+ MonotoneVertex *vertices;
+
+public:
+ VertexSorter(MonotoneVertex *v) :
+ vertices(v) {}
+ bool operator()(long index1, long index2);
+ };
+
+ struct Diagonal {
+ long index1;
+ long index2;
+ };
+
+#ifdef TPPL_ALLOCATOR
+ typedef List<Diagonal, TPPL_ALLOCATOR(Diagonal)> DiagonalList;
+#else
+ typedef List<Diagonal> DiagonalList;
+#endif
+
+ // Dynamic programming state for minimum-weight triangulation.
+ struct DPState {
+ bool visible;
+ tppl_float weight;
+ long bestvertex;
+ };
+
+ // Dynamic programming state for convex partitioning.
+ struct DPState2 {
+ bool visible;
+ long weight;
+ DiagonalList pairs;
+ };
+
+ // Edge that intersects the scanline.
+ struct ScanLineEdge {
+ mutable long index;
+ TPPLPoint p1;
+ TPPLPoint p2;
+
+ // Determines if the edge is to the left of another edge.
+ bool operator<(const ScanLineEdge &other) const;
+
+ bool IsConvex(const TPPLPoint &p1, const TPPLPoint &p2, const TPPLPoint &p3) const;
+ };
+
+ // Standard helper functions.
+ bool IsConvex(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3);
+ bool IsReflex(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3);
+ bool IsInside(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3, TPPLPoint &p);
+
+ bool InCone(TPPLPoint &p1, TPPLPoint &p2, TPPLPoint &p3, TPPLPoint &p);
+ bool InCone(PartitionVertex *v, TPPLPoint &p);
+
+ int Intersects(TPPLPoint &p11, TPPLPoint &p12, TPPLPoint &p21, TPPLPoint &p22);
+
+ TPPLPoint Normalize(const TPPLPoint &p);
+ tppl_float Distance(const TPPLPoint &p1, const TPPLPoint &p2);
+
+ // Helper functions for Triangulate_EC.
+ void UpdateVertexReflexity(PartitionVertex *v);
+ void UpdateVertex(PartitionVertex *v, PartitionVertex *vertices, long numvertices);
+
+ // Helper functions for ConvexPartition_OPT.
+ void UpdateState(long a, long b, long w, long i, long j, DPState2 **dpstates);
+ void TypeA(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates);
+ void TypeB(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates);
+
+ // Helper functions for MonotonePartition.
+ bool Below(TPPLPoint &p1, TPPLPoint &p2);
+ void AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2,
+ TPPLVertexType *vertextypes, Set<ScanLineEdge>::Element **edgeTreeIterators,
+ Set<ScanLineEdge> *edgeTree, long *helpers);
+
+ // Triangulates a monotone polygon, used in Triangulate_MONO.
+ int TriangulateMonotone(TPPLPoly *inPoly, TPPLPolyList *triangles);
+
+ public:
+ // Simple heuristic procedure for removing holes from a list of polygons.
+ // It works by creating a diagonal from the right-most hole vertex
+ // to some other visible vertex.
+ // Time complexity: O(h*(n^2)), h is the # of holes, n is the # of vertices.
+ // Space complexity: O(n)
+ // params:
+ // inpolys:
+ // A list of polygons that can contain holes.
+ // Vertices of all non-hole polys have to be in counter-clockwise order.
+ // Vertices of all hole polys have to be in clockwise order.
+ // outpolys:
+ // A list of polygons without holes.
+ // Returns 1 on success, 0 on failure.
+ int RemoveHoles(TPPLPolyList *inpolys, TPPLPolyList *outpolys);
+
+ // Triangulates a polygon by ear clipping.
+ // Time complexity: O(n^2), n is the number of vertices.
+ // Space complexity: O(n)
+ // params:
+ // poly:
+ // An input polygon to be triangulated.
+ // Vertices have to be in counter-clockwise order.
+ // triangles:
+ // A list of triangles (result).
+ // Returns 1 on success, 0 on failure.
+ int Triangulate_EC(TPPLPoly *poly, TPPLPolyList *triangles);
+
+ // Triangulates a list of polygons that may contain holes by ear clipping
+ // algorithm. It first calls RemoveHoles to get rid of the holes, and then
+ // calls Triangulate_EC for each resulting polygon.
+ // Time complexity: O(h*(n^2)), h is the # of holes, n is the # of vertices.
+ // Space complexity: O(n)
+ // params:
+ // inpolys:
+ // A list of polygons to be triangulated (can contain holes).
+ // Vertices of all non-hole polys have to be in counter-clockwise order.
+ // Vertices of all hole polys have to be in clockwise order.
+ // triangles:
+ // A list of triangles (result).
+ // Returns 1 on success, 0 on failure.
+ int Triangulate_EC(TPPLPolyList *inpolys, TPPLPolyList *triangles);
+
+ // Creates an optimal polygon triangulation in terms of minimal edge length.
+ // Time complexity: O(n^3), n is the number of vertices
+ // Space complexity: O(n^2)
+ // params:
+ // poly:
+ // An input polygon to be triangulated.
+ // Vertices have to be in counter-clockwise order.
+ // triangles:
+ // A list of triangles (result).
+ // Returns 1 on success, 0 on failure.
+ int Triangulate_OPT(TPPLPoly *poly, TPPLPolyList *triangles);
+
+ // Triangulates a polygon by first partitioning it into monotone polygons.
+ // Time complexity: O(n*log(n)), n is the number of vertices.
+ // Space complexity: O(n)
+ // params:
+ // poly:
+ // An input polygon to be triangulated.
+ // Vertices have to be in counter-clockwise order.
+ // triangles:
+ // A list of triangles (result).
+ // Returns 1 on success, 0 on failure.
+ int Triangulate_MONO(TPPLPoly *poly, TPPLPolyList *triangles);
+
+ // Triangulates a list of polygons by first
+ // partitioning them into monotone polygons.
+ // Time complexity: O(n*log(n)), n is the number of vertices.
+ // Space complexity: O(n)
+ // params:
+ // inpolys:
+ // A list of polygons to be triangulated (can contain holes).
+ // Vertices of all non-hole polys have to be in counter-clockwise order.
+ // Vertices of all hole polys have to be in clockwise order.
+ // triangles:
+ // A list of triangles (result).
+ // Returns 1 on success, 0 on failure.
+ int Triangulate_MONO(TPPLPolyList *inpolys, TPPLPolyList *triangles);
+
+ // Creates a monotone partition of a list of polygons that
+ // can contain holes. Triangulates a set of polygons by
+ // first partitioning them into monotone polygons.
+ // Time complexity: O(n*log(n)), n is the number of vertices.
+ // Space complexity: O(n)
+ // params:
+ // inpolys:
+ // A list of polygons to be triangulated (can contain holes).
+ // Vertices of all non-hole polys have to be in counter-clockwise order.
+ // Vertices of all hole polys have to be in clockwise order.
+ // monotonePolys:
+ // A list of monotone polygons (result).
+ // Returns 1 on success, 0 on failure.
+ int MonotonePartition(TPPLPolyList *inpolys, TPPLPolyList *monotonePolys);
+
+ // Partitions a polygon into convex polygons by using the
+ // Hertel-Mehlhorn algorithm. The algorithm gives at most four times
+ // the number of parts as the optimal algorithm, however, in practice
+ // it works much better than that and often gives optimal partition.
+ // It uses triangulation obtained by ear clipping as intermediate result.
+ // Time complexity O(n^2), n is the number of vertices.
+ // Space complexity: O(n)
+ // params:
+ // poly:
+ // An input polygon to be partitioned.
+ // Vertices have to be in counter-clockwise order.
+ // parts:
+ // Resulting list of convex polygons.
+ // Returns 1 on success, 0 on failure.
+ int ConvexPartition_HM(TPPLPoly *poly, TPPLPolyList *parts);
+
+ // Partitions a list of polygons into convex parts by using the
+ // Hertel-Mehlhorn algorithm. The algorithm gives at most four times
+ // the number of parts as the optimal algorithm, however, in practice
+ // it works much better than that and often gives optimal partition.
+ // It uses triangulation obtained by ear clipping as intermediate result.
+ // Time complexity O(n^2), n is the number of vertices.
+ // Space complexity: O(n)
+ // params:
+ // inpolys:
+ // An input list of polygons to be partitioned. Vertices of
+ // all non-hole polys have to be in counter-clockwise order.
+ // Vertices of all hole polys have to be in clockwise order.
+ // parts:
+ // Resulting list of convex polygons.
+ // Returns 1 on success, 0 on failure.
+ int ConvexPartition_HM(TPPLPolyList *inpolys, TPPLPolyList *parts);
+
+ // Optimal convex partitioning (in terms of number of resulting
+ // convex polygons) using the Keil-Snoeyink algorithm.
+ // For reference, see M. Keil, J. Snoeyink, "On the time bound for
+ // convex decomposition of simple polygons", 1998.
+ // Time complexity O(n^3), n is the number of vertices.
+ // Space complexity: O(n^3)
+ // params:
+ // poly:
+ // An input polygon to be partitioned.
+ // Vertices have to be in counter-clockwise order.
+ // parts:
+ // Resulting list of convex polygons.
+ // Returns 1 on success, 0 on failure.
+ int ConvexPartition_OPT(TPPLPoly *poly, TPPLPolyList *parts);
+};
+
+#endif
diff --git a/thirdparty/misc/r128.h b/thirdparty/misc/r128.h
index 1f7aab78fb..a345cc47ba 100644
--- a/thirdparty/misc/r128.h
+++ b/thirdparty/misc/r128.h
@@ -1,5 +1,5 @@
/*
-r128.h: 128-bit (64.64) signed fixed-point arithmetic. Version 1.4.3
+r128.h: 128-bit (64.64) signed fixed-point arithmetic. Version 1.4.4
COMPILATION
-----------
@@ -76,8 +76,8 @@ OTHER DEALINGS IN THE SOFTWARE.
# include <stdint.h>
# define R128_S32 int32_t
# define R128_U32 uint32_t
-# define R128_S64 int64_t
-# define R128_U64 uint64_t
+# define R128_S64 long long
+# define R128_U64 unsigned long long
# define R128_LIT_S64(x) x##ll
# define R128_LIT_U64(x) x##ull
#endif
@@ -701,7 +701,7 @@ static R128_U32 r128__udiv64(R128_U32 nlo, R128_U32 nhi, R128_U32 d, R128_U32 *r
return (R128_U32)(n64 / d);
# endif
}
-#elif !defined(_M_X64) || defined(R128_STDC_ONLY)
+#elif defined(R128_STDC_ONLY) || !R128_INTEL
#define r128__umul64(a, b) ((a) * (R128_U64)(b))
static R128_U32 r128__udiv64(R128_U32 nlo, R128_U32 nhi, R128_U32 d, R128_U32 *rem)
{
@@ -799,7 +799,7 @@ static void r128__umul128(R128 *dst, R128_U64 a, R128_U64 b)
// MSVC x64 provides neither inline assembly nor (pre-2019) a div intrinsic, so we do fake
// "inline assembly" to avoid long division or outline assembly.
#pragma code_seg(".text")
-__declspec(allocate(".text")) static const unsigned char r128__udiv128Code[] = {
+__declspec(allocate(".text") align(16)) static const unsigned char r128__udiv128Code[] = {
0x48, 0x8B, 0xC1, //mov rax, rcx
0x49, 0xF7, 0xF0, //div rax, r8
0x49, 0x89, 0x11, //mov qword ptr [r9], rdx
diff --git a/thirdparty/misc/smolv.cpp b/thirdparty/misc/smolv.cpp
new file mode 100644
index 0000000000..26ed7294f9
--- /dev/null
+++ b/thirdparty/misc/smolv.cpp
@@ -0,0 +1,2108 @@
+// smol-v - public domain - https://github.com/aras-p/smol-v
+// authored 2016-2020 by Aras Pranckevicius
+// no warranty implied; use at your own risk
+// See end of file for license information.
+
+#include "smolv.h"
+#include <stdint.h>
+#include <vector>
+#include <algorithm>
+#include <cstdio>
+#include <cstring>
+
+#if !defined(_MSC_VER) && __cplusplus < 201103L
+#define static_assert(x,y)
+#endif
+
+#define _SMOLV_ARRAY_SIZE(a) (sizeof(a)/sizeof((a)[0]))
+
+// --------------------------------------------------------------------------------------------
+// Metadata about known SPIR-V operations
+
+enum SpvOp
+{
+ SpvOpNop = 0,
+ SpvOpUndef = 1,
+ SpvOpSourceContinued = 2,
+ SpvOpSource = 3,
+ SpvOpSourceExtension = 4,
+ SpvOpName = 5,
+ SpvOpMemberName = 6,
+ SpvOpString = 7,
+ SpvOpLine = 8,
+ SpvOpExtension = 10,
+ SpvOpExtInstImport = 11,
+ SpvOpExtInst = 12,
+ SpvOpVectorShuffleCompact = 13, // not in SPIR-V, added for SMOL-V!
+ SpvOpMemoryModel = 14,
+ SpvOpEntryPoint = 15,
+ SpvOpExecutionMode = 16,
+ SpvOpCapability = 17,
+ SpvOpTypeVoid = 19,
+ SpvOpTypeBool = 20,
+ SpvOpTypeInt = 21,
+ SpvOpTypeFloat = 22,
+ SpvOpTypeVector = 23,
+ SpvOpTypeMatrix = 24,
+ SpvOpTypeImage = 25,
+ SpvOpTypeSampler = 26,
+ SpvOpTypeSampledImage = 27,
+ SpvOpTypeArray = 28,
+ SpvOpTypeRuntimeArray = 29,
+ SpvOpTypeStruct = 30,
+ SpvOpTypeOpaque = 31,
+ SpvOpTypePointer = 32,
+ SpvOpTypeFunction = 33,
+ SpvOpTypeEvent = 34,
+ SpvOpTypeDeviceEvent = 35,
+ SpvOpTypeReserveId = 36,
+ SpvOpTypeQueue = 37,
+ SpvOpTypePipe = 38,
+ SpvOpTypeForwardPointer = 39,
+ SpvOpConstantTrue = 41,
+ SpvOpConstantFalse = 42,
+ SpvOpConstant = 43,
+ SpvOpConstantComposite = 44,
+ SpvOpConstantSampler = 45,
+ SpvOpConstantNull = 46,
+ SpvOpSpecConstantTrue = 48,
+ SpvOpSpecConstantFalse = 49,
+ SpvOpSpecConstant = 50,
+ SpvOpSpecConstantComposite = 51,
+ SpvOpSpecConstantOp = 52,
+ SpvOpFunction = 54,
+ SpvOpFunctionParameter = 55,
+ SpvOpFunctionEnd = 56,
+ SpvOpFunctionCall = 57,
+ SpvOpVariable = 59,
+ SpvOpImageTexelPointer = 60,
+ SpvOpLoad = 61,
+ SpvOpStore = 62,
+ SpvOpCopyMemory = 63,
+ SpvOpCopyMemorySized = 64,
+ SpvOpAccessChain = 65,
+ SpvOpInBoundsAccessChain = 66,
+ SpvOpPtrAccessChain = 67,
+ SpvOpArrayLength = 68,
+ SpvOpGenericPtrMemSemantics = 69,
+ SpvOpInBoundsPtrAccessChain = 70,
+ SpvOpDecorate = 71,
+ SpvOpMemberDecorate = 72,
+ SpvOpDecorationGroup = 73,
+ SpvOpGroupDecorate = 74,
+ SpvOpGroupMemberDecorate = 75,
+ SpvOpVectorExtractDynamic = 77,
+ SpvOpVectorInsertDynamic = 78,
+ SpvOpVectorShuffle = 79,
+ SpvOpCompositeConstruct = 80,
+ SpvOpCompositeExtract = 81,
+ SpvOpCompositeInsert = 82,
+ SpvOpCopyObject = 83,
+ SpvOpTranspose = 84,
+ SpvOpSampledImage = 86,
+ SpvOpImageSampleImplicitLod = 87,
+ SpvOpImageSampleExplicitLod = 88,
+ SpvOpImageSampleDrefImplicitLod = 89,
+ SpvOpImageSampleDrefExplicitLod = 90,
+ SpvOpImageSampleProjImplicitLod = 91,
+ SpvOpImageSampleProjExplicitLod = 92,
+ SpvOpImageSampleProjDrefImplicitLod = 93,
+ SpvOpImageSampleProjDrefExplicitLod = 94,
+ SpvOpImageFetch = 95,
+ SpvOpImageGather = 96,
+ SpvOpImageDrefGather = 97,
+ SpvOpImageRead = 98,
+ SpvOpImageWrite = 99,
+ SpvOpImage = 100,
+ SpvOpImageQueryFormat = 101,
+ SpvOpImageQueryOrder = 102,
+ SpvOpImageQuerySizeLod = 103,
+ SpvOpImageQuerySize = 104,
+ SpvOpImageQueryLod = 105,
+ SpvOpImageQueryLevels = 106,
+ SpvOpImageQuerySamples = 107,
+ SpvOpConvertFToU = 109,
+ SpvOpConvertFToS = 110,
+ SpvOpConvertSToF = 111,
+ SpvOpConvertUToF = 112,
+ SpvOpUConvert = 113,
+ SpvOpSConvert = 114,
+ SpvOpFConvert = 115,
+ SpvOpQuantizeToF16 = 116,
+ SpvOpConvertPtrToU = 117,
+ SpvOpSatConvertSToU = 118,
+ SpvOpSatConvertUToS = 119,
+ SpvOpConvertUToPtr = 120,
+ SpvOpPtrCastToGeneric = 121,
+ SpvOpGenericCastToPtr = 122,
+ SpvOpGenericCastToPtrExplicit = 123,
+ SpvOpBitcast = 124,
+ SpvOpSNegate = 126,
+ SpvOpFNegate = 127,
+ SpvOpIAdd = 128,
+ SpvOpFAdd = 129,
+ SpvOpISub = 130,
+ SpvOpFSub = 131,
+ SpvOpIMul = 132,
+ SpvOpFMul = 133,
+ SpvOpUDiv = 134,
+ SpvOpSDiv = 135,
+ SpvOpFDiv = 136,
+ SpvOpUMod = 137,
+ SpvOpSRem = 138,
+ SpvOpSMod = 139,
+ SpvOpFRem = 140,
+ SpvOpFMod = 141,
+ SpvOpVectorTimesScalar = 142,
+ SpvOpMatrixTimesScalar = 143,
+ SpvOpVectorTimesMatrix = 144,
+ SpvOpMatrixTimesVector = 145,
+ SpvOpMatrixTimesMatrix = 146,
+ SpvOpOuterProduct = 147,
+ SpvOpDot = 148,
+ SpvOpIAddCarry = 149,
+ SpvOpISubBorrow = 150,
+ SpvOpUMulExtended = 151,
+ SpvOpSMulExtended = 152,
+ SpvOpAny = 154,
+ SpvOpAll = 155,
+ SpvOpIsNan = 156,
+ SpvOpIsInf = 157,
+ SpvOpIsFinite = 158,
+ SpvOpIsNormal = 159,
+ SpvOpSignBitSet = 160,
+ SpvOpLessOrGreater = 161,
+ SpvOpOrdered = 162,
+ SpvOpUnordered = 163,
+ SpvOpLogicalEqual = 164,
+ SpvOpLogicalNotEqual = 165,
+ SpvOpLogicalOr = 166,
+ SpvOpLogicalAnd = 167,
+ SpvOpLogicalNot = 168,
+ SpvOpSelect = 169,
+ SpvOpIEqual = 170,
+ SpvOpINotEqual = 171,
+ SpvOpUGreaterThan = 172,
+ SpvOpSGreaterThan = 173,
+ SpvOpUGreaterThanEqual = 174,
+ SpvOpSGreaterThanEqual = 175,
+ SpvOpULessThan = 176,
+ SpvOpSLessThan = 177,
+ SpvOpULessThanEqual = 178,
+ SpvOpSLessThanEqual = 179,
+ SpvOpFOrdEqual = 180,
+ SpvOpFUnordEqual = 181,
+ SpvOpFOrdNotEqual = 182,
+ SpvOpFUnordNotEqual = 183,
+ SpvOpFOrdLessThan = 184,
+ SpvOpFUnordLessThan = 185,
+ SpvOpFOrdGreaterThan = 186,
+ SpvOpFUnordGreaterThan = 187,
+ SpvOpFOrdLessThanEqual = 188,
+ SpvOpFUnordLessThanEqual = 189,
+ SpvOpFOrdGreaterThanEqual = 190,
+ SpvOpFUnordGreaterThanEqual = 191,
+ SpvOpShiftRightLogical = 194,
+ SpvOpShiftRightArithmetic = 195,
+ SpvOpShiftLeftLogical = 196,
+ SpvOpBitwiseOr = 197,
+ SpvOpBitwiseXor = 198,
+ SpvOpBitwiseAnd = 199,
+ SpvOpNot = 200,
+ SpvOpBitFieldInsert = 201,
+ SpvOpBitFieldSExtract = 202,
+ SpvOpBitFieldUExtract = 203,
+ SpvOpBitReverse = 204,
+ SpvOpBitCount = 205,
+ SpvOpDPdx = 207,
+ SpvOpDPdy = 208,
+ SpvOpFwidth = 209,
+ SpvOpDPdxFine = 210,
+ SpvOpDPdyFine = 211,
+ SpvOpFwidthFine = 212,
+ SpvOpDPdxCoarse = 213,
+ SpvOpDPdyCoarse = 214,
+ SpvOpFwidthCoarse = 215,
+ SpvOpEmitVertex = 218,
+ SpvOpEndPrimitive = 219,
+ SpvOpEmitStreamVertex = 220,
+ SpvOpEndStreamPrimitive = 221,
+ SpvOpControlBarrier = 224,
+ SpvOpMemoryBarrier = 225,
+ SpvOpAtomicLoad = 227,
+ SpvOpAtomicStore = 228,
+ SpvOpAtomicExchange = 229,
+ SpvOpAtomicCompareExchange = 230,
+ SpvOpAtomicCompareExchangeWeak = 231,
+ SpvOpAtomicIIncrement = 232,
+ SpvOpAtomicIDecrement = 233,
+ SpvOpAtomicIAdd = 234,
+ SpvOpAtomicISub = 235,
+ SpvOpAtomicSMin = 236,
+ SpvOpAtomicUMin = 237,
+ SpvOpAtomicSMax = 238,
+ SpvOpAtomicUMax = 239,
+ SpvOpAtomicAnd = 240,
+ SpvOpAtomicOr = 241,
+ SpvOpAtomicXor = 242,
+ SpvOpPhi = 245,
+ SpvOpLoopMerge = 246,
+ SpvOpSelectionMerge = 247,
+ SpvOpLabel = 248,
+ SpvOpBranch = 249,
+ SpvOpBranchConditional = 250,
+ SpvOpSwitch = 251,
+ SpvOpKill = 252,
+ SpvOpReturn = 253,
+ SpvOpReturnValue = 254,
+ SpvOpUnreachable = 255,
+ SpvOpLifetimeStart = 256,
+ SpvOpLifetimeStop = 257,
+ SpvOpGroupAsyncCopy = 259,
+ SpvOpGroupWaitEvents = 260,
+ SpvOpGroupAll = 261,
+ SpvOpGroupAny = 262,
+ SpvOpGroupBroadcast = 263,
+ SpvOpGroupIAdd = 264,
+ SpvOpGroupFAdd = 265,
+ SpvOpGroupFMin = 266,
+ SpvOpGroupUMin = 267,
+ SpvOpGroupSMin = 268,
+ SpvOpGroupFMax = 269,
+ SpvOpGroupUMax = 270,
+ SpvOpGroupSMax = 271,
+ SpvOpReadPipe = 274,
+ SpvOpWritePipe = 275,
+ SpvOpReservedReadPipe = 276,
+ SpvOpReservedWritePipe = 277,
+ SpvOpReserveReadPipePackets = 278,
+ SpvOpReserveWritePipePackets = 279,
+ SpvOpCommitReadPipe = 280,
+ SpvOpCommitWritePipe = 281,
+ SpvOpIsValidReserveId = 282,
+ SpvOpGetNumPipePackets = 283,
+ SpvOpGetMaxPipePackets = 284,
+ SpvOpGroupReserveReadPipePackets = 285,
+ SpvOpGroupReserveWritePipePackets = 286,
+ SpvOpGroupCommitReadPipe = 287,
+ SpvOpGroupCommitWritePipe = 288,
+ SpvOpEnqueueMarker = 291,
+ SpvOpEnqueueKernel = 292,
+ SpvOpGetKernelNDrangeSubGroupCount = 293,
+ SpvOpGetKernelNDrangeMaxSubGroupSize = 294,
+ SpvOpGetKernelWorkGroupSize = 295,
+ SpvOpGetKernelPreferredWorkGroupSizeMultiple = 296,
+ SpvOpRetainEvent = 297,
+ SpvOpReleaseEvent = 298,
+ SpvOpCreateUserEvent = 299,
+ SpvOpIsValidEvent = 300,
+ SpvOpSetUserEventStatus = 301,
+ SpvOpCaptureEventProfilingInfo = 302,
+ SpvOpGetDefaultQueue = 303,
+ SpvOpBuildNDRange = 304,
+ SpvOpImageSparseSampleImplicitLod = 305,
+ SpvOpImageSparseSampleExplicitLod = 306,
+ SpvOpImageSparseSampleDrefImplicitLod = 307,
+ SpvOpImageSparseSampleDrefExplicitLod = 308,
+ SpvOpImageSparseSampleProjImplicitLod = 309,
+ SpvOpImageSparseSampleProjExplicitLod = 310,
+ SpvOpImageSparseSampleProjDrefImplicitLod = 311,
+ SpvOpImageSparseSampleProjDrefExplicitLod = 312,
+ SpvOpImageSparseFetch = 313,
+ SpvOpImageSparseGather = 314,
+ SpvOpImageSparseDrefGather = 315,
+ SpvOpImageSparseTexelsResident = 316,
+ SpvOpNoLine = 317,
+ SpvOpAtomicFlagTestAndSet = 318,
+ SpvOpAtomicFlagClear = 319,
+ SpvOpImageSparseRead = 320,
+ SpvOpSizeOf = 321,
+ SpvOpTypePipeStorage = 322,
+ SpvOpConstantPipeStorage = 323,
+ SpvOpCreatePipeFromPipeStorage = 324,
+ SpvOpGetKernelLocalSizeForSubgroupCount = 325,
+ SpvOpGetKernelMaxNumSubgroups = 326,
+ SpvOpTypeNamedBarrier = 327,
+ SpvOpNamedBarrierInitialize = 328,
+ SpvOpMemoryNamedBarrier = 329,
+ SpvOpModuleProcessed = 330,
+ SpvOpExecutionModeId = 331,
+ SpvOpDecorateId = 332,
+ SpvOpGroupNonUniformElect = 333,
+ SpvOpGroupNonUniformAll = 334,
+ SpvOpGroupNonUniformAny = 335,
+ SpvOpGroupNonUniformAllEqual = 336,
+ SpvOpGroupNonUniformBroadcast = 337,
+ SpvOpGroupNonUniformBroadcastFirst = 338,
+ SpvOpGroupNonUniformBallot = 339,
+ SpvOpGroupNonUniformInverseBallot = 340,
+ SpvOpGroupNonUniformBallotBitExtract = 341,
+ SpvOpGroupNonUniformBallotBitCount = 342,
+ SpvOpGroupNonUniformBallotFindLSB = 343,
+ SpvOpGroupNonUniformBallotFindMSB = 344,
+ SpvOpGroupNonUniformShuffle = 345,
+ SpvOpGroupNonUniformShuffleXor = 346,
+ SpvOpGroupNonUniformShuffleUp = 347,
+ SpvOpGroupNonUniformShuffleDown = 348,
+ SpvOpGroupNonUniformIAdd = 349,
+ SpvOpGroupNonUniformFAdd = 350,
+ SpvOpGroupNonUniformIMul = 351,
+ SpvOpGroupNonUniformFMul = 352,
+ SpvOpGroupNonUniformSMin = 353,
+ SpvOpGroupNonUniformUMin = 354,
+ SpvOpGroupNonUniformFMin = 355,
+ SpvOpGroupNonUniformSMax = 356,
+ SpvOpGroupNonUniformUMax = 357,
+ SpvOpGroupNonUniformFMax = 358,
+ SpvOpGroupNonUniformBitwiseAnd = 359,
+ SpvOpGroupNonUniformBitwiseOr = 360,
+ SpvOpGroupNonUniformBitwiseXor = 361,
+ SpvOpGroupNonUniformLogicalAnd = 362,
+ SpvOpGroupNonUniformLogicalOr = 363,
+ SpvOpGroupNonUniformLogicalXor = 364,
+ SpvOpGroupNonUniformQuadBroadcast = 365,
+ SpvOpGroupNonUniformQuadSwap = 366,
+};
+static const int kKnownOpsCount = SpvOpGroupNonUniformQuadSwap+1;
+
+
+static const char* kSpirvOpNames[] =
+{
+ "Nop",
+ "Undef",
+ "SourceContinued",
+ "Source",
+ "SourceExtension",
+ "Name",
+ "MemberName",
+ "String",
+ "Line",
+ "#9",
+ "Extension",
+ "ExtInstImport",
+ "ExtInst",
+ "VectorShuffleCompact",
+ "MemoryModel",
+ "EntryPoint",
+ "ExecutionMode",
+ "Capability",
+ "#18",
+ "TypeVoid",
+ "TypeBool",
+ "TypeInt",
+ "TypeFloat",
+ "TypeVector",
+ "TypeMatrix",
+ "TypeImage",
+ "TypeSampler",
+ "TypeSampledImage",
+ "TypeArray",
+ "TypeRuntimeArray",
+ "TypeStruct",
+ "TypeOpaque",
+ "TypePointer",
+ "TypeFunction",
+ "TypeEvent",
+ "TypeDeviceEvent",
+ "TypeReserveId",
+ "TypeQueue",
+ "TypePipe",
+ "TypeForwardPointer",
+ "#40",
+ "ConstantTrue",
+ "ConstantFalse",
+ "Constant",
+ "ConstantComposite",
+ "ConstantSampler",
+ "ConstantNull",
+ "#47",
+ "SpecConstantTrue",
+ "SpecConstantFalse",
+ "SpecConstant",
+ "SpecConstantComposite",
+ "SpecConstantOp",
+ "#53",
+ "Function",
+ "FunctionParameter",
+ "FunctionEnd",
+ "FunctionCall",
+ "#58",
+ "Variable",
+ "ImageTexelPointer",
+ "Load",
+ "Store",
+ "CopyMemory",
+ "CopyMemorySized",
+ "AccessChain",
+ "InBoundsAccessChain",
+ "PtrAccessChain",
+ "ArrayLength",
+ "GenericPtrMemSemantics",
+ "InBoundsPtrAccessChain",
+ "Decorate",
+ "MemberDecorate",
+ "DecorationGroup",
+ "GroupDecorate",
+ "GroupMemberDecorate",
+ "#76",
+ "VectorExtractDynamic",
+ "VectorInsertDynamic",
+ "VectorShuffle",
+ "CompositeConstruct",
+ "CompositeExtract",
+ "CompositeInsert",
+ "CopyObject",
+ "Transpose",
+ "#85",
+ "SampledImage",
+ "ImageSampleImplicitLod",
+ "ImageSampleExplicitLod",
+ "ImageSampleDrefImplicitLod",
+ "ImageSampleDrefExplicitLod",
+ "ImageSampleProjImplicitLod",
+ "ImageSampleProjExplicitLod",
+ "ImageSampleProjDrefImplicitLod",
+ "ImageSampleProjDrefExplicitLod",
+ "ImageFetch",
+ "ImageGather",
+ "ImageDrefGather",
+ "ImageRead",
+ "ImageWrite",
+ "Image",
+ "ImageQueryFormat",
+ "ImageQueryOrder",
+ "ImageQuerySizeLod",
+ "ImageQuerySize",
+ "ImageQueryLod",
+ "ImageQueryLevels",
+ "ImageQuerySamples",
+ "#108",
+ "ConvertFToU",
+ "ConvertFToS",
+ "ConvertSToF",
+ "ConvertUToF",
+ "UConvert",
+ "SConvert",
+ "FConvert",
+ "QuantizeToF16",
+ "ConvertPtrToU",
+ "SatConvertSToU",
+ "SatConvertUToS",
+ "ConvertUToPtr",
+ "PtrCastToGeneric",
+ "GenericCastToPtr",
+ "GenericCastToPtrExplicit",
+ "Bitcast",
+ "#125",
+ "SNegate",
+ "FNegate",
+ "IAdd",
+ "FAdd",
+ "ISub",
+ "FSub",
+ "IMul",
+ "FMul",
+ "UDiv",
+ "SDiv",
+ "FDiv",
+ "UMod",
+ "SRem",
+ "SMod",
+ "FRem",
+ "FMod",
+ "VectorTimesScalar",
+ "MatrixTimesScalar",
+ "VectorTimesMatrix",
+ "MatrixTimesVector",
+ "MatrixTimesMatrix",
+ "OuterProduct",
+ "Dot",
+ "IAddCarry",
+ "ISubBorrow",
+ "UMulExtended",
+ "SMulExtended",
+ "#153",
+ "Any",
+ "All",
+ "IsNan",
+ "IsInf",
+ "IsFinite",
+ "IsNormal",
+ "SignBitSet",
+ "LessOrGreater",
+ "Ordered",
+ "Unordered",
+ "LogicalEqual",
+ "LogicalNotEqual",
+ "LogicalOr",
+ "LogicalAnd",
+ "LogicalNot",
+ "Select",
+ "IEqual",
+ "INotEqual",
+ "UGreaterThan",
+ "SGreaterThan",
+ "UGreaterThanEqual",
+ "SGreaterThanEqual",
+ "ULessThan",
+ "SLessThan",
+ "ULessThanEqual",
+ "SLessThanEqual",
+ "FOrdEqual",
+ "FUnordEqual",
+ "FOrdNotEqual",
+ "FUnordNotEqual",
+ "FOrdLessThan",
+ "FUnordLessThan",
+ "FOrdGreaterThan",
+ "FUnordGreaterThan",
+ "FOrdLessThanEqual",
+ "FUnordLessThanEqual",
+ "FOrdGreaterThanEqual",
+ "FUnordGreaterThanEqual",
+ "#192",
+ "#193",
+ "ShiftRightLogical",
+ "ShiftRightArithmetic",
+ "ShiftLeftLogical",
+ "BitwiseOr",
+ "BitwiseXor",
+ "BitwiseAnd",
+ "Not",
+ "BitFieldInsert",
+ "BitFieldSExtract",
+ "BitFieldUExtract",
+ "BitReverse",
+ "BitCount",
+ "#206",
+ "DPdx",
+ "DPdy",
+ "Fwidth",
+ "DPdxFine",
+ "DPdyFine",
+ "FwidthFine",
+ "DPdxCoarse",
+ "DPdyCoarse",
+ "FwidthCoarse",
+ "#216",
+ "#217",
+ "EmitVertex",
+ "EndPrimitive",
+ "EmitStreamVertex",
+ "EndStreamPrimitive",
+ "#222",
+ "#223",
+ "ControlBarrier",
+ "MemoryBarrier",
+ "#226",
+ "AtomicLoad",
+ "AtomicStore",
+ "AtomicExchange",
+ "AtomicCompareExchange",
+ "AtomicCompareExchangeWeak",
+ "AtomicIIncrement",
+ "AtomicIDecrement",
+ "AtomicIAdd",
+ "AtomicISub",
+ "AtomicSMin",
+ "AtomicUMin",
+ "AtomicSMax",
+ "AtomicUMax",
+ "AtomicAnd",
+ "AtomicOr",
+ "AtomicXor",
+ "#243",
+ "#244",
+ "Phi",
+ "LoopMerge",
+ "SelectionMerge",
+ "Label",
+ "Branch",
+ "BranchConditional",
+ "Switch",
+ "Kill",
+ "Return",
+ "ReturnValue",
+ "Unreachable",
+ "LifetimeStart",
+ "LifetimeStop",
+ "#258",
+ "GroupAsyncCopy",
+ "GroupWaitEvents",
+ "GroupAll",
+ "GroupAny",
+ "GroupBroadcast",
+ "GroupIAdd",
+ "GroupFAdd",
+ "GroupFMin",
+ "GroupUMin",
+ "GroupSMin",
+ "GroupFMax",
+ "GroupUMax",
+ "GroupSMax",
+ "#272",
+ "#273",
+ "ReadPipe",
+ "WritePipe",
+ "ReservedReadPipe",
+ "ReservedWritePipe",
+ "ReserveReadPipePackets",
+ "ReserveWritePipePackets",
+ "CommitReadPipe",
+ "CommitWritePipe",
+ "IsValidReserveId",
+ "GetNumPipePackets",
+ "GetMaxPipePackets",
+ "GroupReserveReadPipePackets",
+ "GroupReserveWritePipePackets",
+ "GroupCommitReadPipe",
+ "GroupCommitWritePipe",
+ "#289",
+ "#290",
+ "EnqueueMarker",
+ "EnqueueKernel",
+ "GetKernelNDrangeSubGroupCount",
+ "GetKernelNDrangeMaxSubGroupSize",
+ "GetKernelWorkGroupSize",
+ "GetKernelPreferredWorkGroupSizeMultiple",
+ "RetainEvent",
+ "ReleaseEvent",
+ "CreateUserEvent",
+ "IsValidEvent",
+ "SetUserEventStatus",
+ "CaptureEventProfilingInfo",
+ "GetDefaultQueue",
+ "BuildNDRange",
+ "ImageSparseSampleImplicitLod",
+ "ImageSparseSampleExplicitLod",
+ "ImageSparseSampleDrefImplicitLod",
+ "ImageSparseSampleDrefExplicitLod",
+ "ImageSparseSampleProjImplicitLod",
+ "ImageSparseSampleProjExplicitLod",
+ "ImageSparseSampleProjDrefImplicitLod",
+ "ImageSparseSampleProjDrefExplicitLod",
+ "ImageSparseFetch",
+ "ImageSparseGather",
+ "ImageSparseDrefGather",
+ "ImageSparseTexelsResident",
+ "NoLine",
+ "AtomicFlagTestAndSet",
+ "AtomicFlagClear",
+ "ImageSparseRead",
+ "SizeOf",
+ "TypePipeStorage",
+ "ConstantPipeStorage",
+ "CreatePipeFromPipeStorage",
+ "GetKernelLocalSizeForSubgroupCount",
+ "GetKernelMaxNumSubgroups",
+ "TypeNamedBarrier",
+ "NamedBarrierInitialize",
+ "MemoryNamedBarrier",
+ "ModuleProcessed",
+ "ExecutionModeId",
+ "DecorateId",
+ "GroupNonUniformElect",
+ "GroupNonUniformAll",
+ "GroupNonUniformAny",
+ "GroupNonUniformAllEqual",
+ "GroupNonUniformBroadcast",
+ "GroupNonUniformBroadcastFirst",
+ "GroupNonUniformBallot",
+ "GroupNonUniformInverseBallot",
+ "GroupNonUniformBallotBitExtract",
+ "GroupNonUniformBallotBitCount",
+ "GroupNonUniformBallotFindLSB",
+ "GroupNonUniformBallotFindMSB",
+ "GroupNonUniformShuffle",
+ "GroupNonUniformShuffleXor",
+ "GroupNonUniformShuffleUp",
+ "GroupNonUniformShuffleDown",
+ "GroupNonUniformIAdd",
+ "GroupNonUniformFAdd",
+ "GroupNonUniformIMul",
+ "GroupNonUniformFMul",
+ "GroupNonUniformSMin",
+ "GroupNonUniformUMin",
+ "GroupNonUniformFMin",
+ "GroupNonUniformSMax",
+ "GroupNonUniformUMax",
+ "GroupNonUniformFMax",
+ "GroupNonUniformBitwiseAnd",
+ "GroupNonUniformBitwiseOr",
+ "GroupNonUniformBitwiseXor",
+ "GroupNonUniformLogicalAnd",
+ "GroupNonUniformLogicalOr",
+ "GroupNonUniformLogicalXor",
+ "GroupNonUniformQuadBroadcast",
+ "GroupNonUniformQuadSwap",
+};
+static_assert(_SMOLV_ARRAY_SIZE(kSpirvOpNames) == kKnownOpsCount, "kSpirvOpNames table mismatch with known SpvOps");
+
+
+struct OpData
+{
+ uint8_t hasResult; // does it have result ID?
+ uint8_t hasType; // does it have type ID?
+ uint8_t deltaFromResult; // How many words after (optional) type+result to write out as deltas from result?
+ uint8_t varrest; // should the rest of words be written in varint encoding?
+};
+static const OpData kSpirvOpData[] =
+{
+ {0, 0, 0, 0}, // Nop
+ {1, 1, 0, 0}, // Undef
+ {0, 0, 0, 0}, // SourceContinued
+ {0, 0, 0, 1}, // Source
+ {0, 0, 0, 0}, // SourceExtension
+ {0, 0, 0, 0}, // Name
+ {0, 0, 0, 0}, // MemberName
+ {0, 0, 0, 0}, // String
+ {0, 0, 0, 1}, // Line
+ {1, 1, 0, 0}, // #9
+ {0, 0, 0, 0}, // Extension
+ {1, 0, 0, 0}, // ExtInstImport
+ {1, 1, 0, 1}, // ExtInst
+ {1, 1, 2, 1}, // VectorShuffleCompact - new in SMOLV
+ {0, 0, 0, 1}, // MemoryModel
+ {0, 0, 0, 1}, // EntryPoint
+ {0, 0, 0, 1}, // ExecutionMode
+ {0, 0, 0, 1}, // Capability
+ {1, 1, 0, 0}, // #18
+ {1, 0, 0, 1}, // TypeVoid
+ {1, 0, 0, 1}, // TypeBool
+ {1, 0, 0, 1}, // TypeInt
+ {1, 0, 0, 1}, // TypeFloat
+ {1, 0, 0, 1}, // TypeVector
+ {1, 0, 0, 1}, // TypeMatrix
+ {1, 0, 0, 1}, // TypeImage
+ {1, 0, 0, 1}, // TypeSampler
+ {1, 0, 0, 1}, // TypeSampledImage
+ {1, 0, 0, 1}, // TypeArray
+ {1, 0, 0, 1}, // TypeRuntimeArray
+ {1, 0, 0, 1}, // TypeStruct
+ {1, 0, 0, 1}, // TypeOpaque
+ {1, 0, 0, 1}, // TypePointer
+ {1, 0, 0, 1}, // TypeFunction
+ {1, 0, 0, 1}, // TypeEvent
+ {1, 0, 0, 1}, // TypeDeviceEvent
+ {1, 0, 0, 1}, // TypeReserveId
+ {1, 0, 0, 1}, // TypeQueue
+ {1, 0, 0, 1}, // TypePipe
+ {0, 0, 0, 1}, // TypeForwardPointer
+ {1, 1, 0, 0}, // #40
+ {1, 1, 0, 0}, // ConstantTrue
+ {1, 1, 0, 0}, // ConstantFalse
+ {1, 1, 0, 0}, // Constant
+ {1, 1, 9, 0}, // ConstantComposite
+ {1, 1, 0, 1}, // ConstantSampler
+ {1, 1, 0, 0}, // ConstantNull
+ {1, 1, 0, 0}, // #47
+ {1, 1, 0, 0}, // SpecConstantTrue
+ {1, 1, 0, 0}, // SpecConstantFalse
+ {1, 1, 0, 0}, // SpecConstant
+ {1, 1, 9, 0}, // SpecConstantComposite
+ {1, 1, 0, 0}, // SpecConstantOp
+ {1, 1, 0, 0}, // #53
+ {1, 1, 0, 1}, // Function
+ {1, 1, 0, 0}, // FunctionParameter
+ {0, 0, 0, 0}, // FunctionEnd
+ {1, 1, 9, 0}, // FunctionCall
+ {1, 1, 0, 0}, // #58
+ {1, 1, 0, 1}, // Variable
+ {1, 1, 0, 0}, // ImageTexelPointer
+ {1, 1, 1, 1}, // Load
+ {0, 0, 2, 1}, // Store
+ {0, 0, 0, 0}, // CopyMemory
+ {0, 0, 0, 0}, // CopyMemorySized
+ {1, 1, 0, 1}, // AccessChain
+ {1, 1, 0, 0}, // InBoundsAccessChain
+ {1, 1, 0, 0}, // PtrAccessChain
+ {1, 1, 0, 0}, // ArrayLength
+ {1, 1, 0, 0}, // GenericPtrMemSemantics
+ {1, 1, 0, 0}, // InBoundsPtrAccessChain
+ {0, 0, 0, 1}, // Decorate
+ {0, 0, 0, 1}, // MemberDecorate
+ {1, 0, 0, 0}, // DecorationGroup
+ {0, 0, 0, 0}, // GroupDecorate
+ {0, 0, 0, 0}, // GroupMemberDecorate
+ {1, 1, 0, 0}, // #76
+ {1, 1, 1, 1}, // VectorExtractDynamic
+ {1, 1, 2, 1}, // VectorInsertDynamic
+ {1, 1, 2, 1}, // VectorShuffle
+ {1, 1, 9, 0}, // CompositeConstruct
+ {1, 1, 1, 1}, // CompositeExtract
+ {1, 1, 2, 1}, // CompositeInsert
+ {1, 1, 1, 0}, // CopyObject
+ {1, 1, 0, 0}, // Transpose
+ {1, 1, 0, 0}, // #85
+ {1, 1, 0, 0}, // SampledImage
+ {1, 1, 2, 1}, // ImageSampleImplicitLod
+ {1, 1, 2, 1}, // ImageSampleExplicitLod
+ {1, 1, 3, 1}, // ImageSampleDrefImplicitLod
+ {1, 1, 3, 1}, // ImageSampleDrefExplicitLod
+ {1, 1, 2, 1}, // ImageSampleProjImplicitLod
+ {1, 1, 2, 1}, // ImageSampleProjExplicitLod
+ {1, 1, 3, 1}, // ImageSampleProjDrefImplicitLod
+ {1, 1, 3, 1}, // ImageSampleProjDrefExplicitLod
+ {1, 1, 2, 1}, // ImageFetch
+ {1, 1, 3, 1}, // ImageGather
+ {1, 1, 3, 1}, // ImageDrefGather
+ {1, 1, 2, 1}, // ImageRead
+ {0, 0, 3, 1}, // ImageWrite
+ {1, 1, 1, 0}, // Image
+ {1, 1, 1, 0}, // ImageQueryFormat
+ {1, 1, 1, 0}, // ImageQueryOrder
+ {1, 1, 2, 0}, // ImageQuerySizeLod
+ {1, 1, 1, 0}, // ImageQuerySize
+ {1, 1, 2, 0}, // ImageQueryLod
+ {1, 1, 1, 0}, // ImageQueryLevels
+ {1, 1, 1, 0}, // ImageQuerySamples
+ {1, 1, 0, 0}, // #108
+ {1, 1, 1, 0}, // ConvertFToU
+ {1, 1, 1, 0}, // ConvertFToS
+ {1, 1, 1, 0}, // ConvertSToF
+ {1, 1, 1, 0}, // ConvertUToF
+ {1, 1, 1, 0}, // UConvert
+ {1, 1, 1, 0}, // SConvert
+ {1, 1, 1, 0}, // FConvert
+ {1, 1, 1, 0}, // QuantizeToF16
+ {1, 1, 1, 0}, // ConvertPtrToU
+ {1, 1, 1, 0}, // SatConvertSToU
+ {1, 1, 1, 0}, // SatConvertUToS
+ {1, 1, 1, 0}, // ConvertUToPtr
+ {1, 1, 1, 0}, // PtrCastToGeneric
+ {1, 1, 1, 0}, // GenericCastToPtr
+ {1, 1, 1, 1}, // GenericCastToPtrExplicit
+ {1, 1, 1, 0}, // Bitcast
+ {1, 1, 0, 0}, // #125
+ {1, 1, 1, 0}, // SNegate
+ {1, 1, 1, 0}, // FNegate
+ {1, 1, 2, 0}, // IAdd
+ {1, 1, 2, 0}, // FAdd
+ {1, 1, 2, 0}, // ISub
+ {1, 1, 2, 0}, // FSub
+ {1, 1, 2, 0}, // IMul
+ {1, 1, 2, 0}, // FMul
+ {1, 1, 2, 0}, // UDiv
+ {1, 1, 2, 0}, // SDiv
+ {1, 1, 2, 0}, // FDiv
+ {1, 1, 2, 0}, // UMod
+ {1, 1, 2, 0}, // SRem
+ {1, 1, 2, 0}, // SMod
+ {1, 1, 2, 0}, // FRem
+ {1, 1, 2, 0}, // FMod
+ {1, 1, 2, 0}, // VectorTimesScalar
+ {1, 1, 2, 0}, // MatrixTimesScalar
+ {1, 1, 2, 0}, // VectorTimesMatrix
+ {1, 1, 2, 0}, // MatrixTimesVector
+ {1, 1, 2, 0}, // MatrixTimesMatrix
+ {1, 1, 2, 0}, // OuterProduct
+ {1, 1, 2, 0}, // Dot
+ {1, 1, 2, 0}, // IAddCarry
+ {1, 1, 2, 0}, // ISubBorrow
+ {1, 1, 2, 0}, // UMulExtended
+ {1, 1, 2, 0}, // SMulExtended
+ {1, 1, 0, 0}, // #153
+ {1, 1, 1, 0}, // Any
+ {1, 1, 1, 0}, // All
+ {1, 1, 1, 0}, // IsNan
+ {1, 1, 1, 0}, // IsInf
+ {1, 1, 1, 0}, // IsFinite
+ {1, 1, 1, 0}, // IsNormal
+ {1, 1, 1, 0}, // SignBitSet
+ {1, 1, 2, 0}, // LessOrGreater
+ {1, 1, 2, 0}, // Ordered
+ {1, 1, 2, 0}, // Unordered
+ {1, 1, 2, 0}, // LogicalEqual
+ {1, 1, 2, 0}, // LogicalNotEqual
+ {1, 1, 2, 0}, // LogicalOr
+ {1, 1, 2, 0}, // LogicalAnd
+ {1, 1, 1, 0}, // LogicalNot
+ {1, 1, 3, 0}, // Select
+ {1, 1, 2, 0}, // IEqual
+ {1, 1, 2, 0}, // INotEqual
+ {1, 1, 2, 0}, // UGreaterThan
+ {1, 1, 2, 0}, // SGreaterThan
+ {1, 1, 2, 0}, // UGreaterThanEqual
+ {1, 1, 2, 0}, // SGreaterThanEqual
+ {1, 1, 2, 0}, // ULessThan
+ {1, 1, 2, 0}, // SLessThan
+ {1, 1, 2, 0}, // ULessThanEqual
+ {1, 1, 2, 0}, // SLessThanEqual
+ {1, 1, 2, 0}, // FOrdEqual
+ {1, 1, 2, 0}, // FUnordEqual
+ {1, 1, 2, 0}, // FOrdNotEqual
+ {1, 1, 2, 0}, // FUnordNotEqual
+ {1, 1, 2, 0}, // FOrdLessThan
+ {1, 1, 2, 0}, // FUnordLessThan
+ {1, 1, 2, 0}, // FOrdGreaterThan
+ {1, 1, 2, 0}, // FUnordGreaterThan
+ {1, 1, 2, 0}, // FOrdLessThanEqual
+ {1, 1, 2, 0}, // FUnordLessThanEqual
+ {1, 1, 2, 0}, // FOrdGreaterThanEqual
+ {1, 1, 2, 0}, // FUnordGreaterThanEqual
+ {1, 1, 0, 0}, // #192
+ {1, 1, 0, 0}, // #193
+ {1, 1, 2, 0}, // ShiftRightLogical
+ {1, 1, 2, 0}, // ShiftRightArithmetic
+ {1, 1, 2, 0}, // ShiftLeftLogical
+ {1, 1, 2, 0}, // BitwiseOr
+ {1, 1, 2, 0}, // BitwiseXor
+ {1, 1, 2, 0}, // BitwiseAnd
+ {1, 1, 1, 0}, // Not
+ {1, 1, 4, 0}, // BitFieldInsert
+ {1, 1, 3, 0}, // BitFieldSExtract
+ {1, 1, 3, 0}, // BitFieldUExtract
+ {1, 1, 1, 0}, // BitReverse
+ {1, 1, 1, 0}, // BitCount
+ {1, 1, 0, 0}, // #206
+ {1, 1, 0, 0}, // DPdx
+ {1, 1, 0, 0}, // DPdy
+ {1, 1, 0, 0}, // Fwidth
+ {1, 1, 0, 0}, // DPdxFine
+ {1, 1, 0, 0}, // DPdyFine
+ {1, 1, 0, 0}, // FwidthFine
+ {1, 1, 0, 0}, // DPdxCoarse
+ {1, 1, 0, 0}, // DPdyCoarse
+ {1, 1, 0, 0}, // FwidthCoarse
+ {1, 1, 0, 0}, // #216
+ {1, 1, 0, 0}, // #217
+ {0, 0, 0, 0}, // EmitVertex
+ {0, 0, 0, 0}, // EndPrimitive
+ {0, 0, 0, 0}, // EmitStreamVertex
+ {0, 0, 0, 0}, // EndStreamPrimitive
+ {1, 1, 0, 0}, // #222
+ {1, 1, 0, 0}, // #223
+ {0, 0, 3, 0}, // ControlBarrier
+ {0, 0, 2, 0}, // MemoryBarrier
+ {1, 1, 0, 0}, // #226
+ {1, 1, 0, 0}, // AtomicLoad
+ {0, 0, 0, 0}, // AtomicStore
+ {1, 1, 0, 0}, // AtomicExchange
+ {1, 1, 0, 0}, // AtomicCompareExchange
+ {1, 1, 0, 0}, // AtomicCompareExchangeWeak
+ {1, 1, 0, 0}, // AtomicIIncrement
+ {1, 1, 0, 0}, // AtomicIDecrement
+ {1, 1, 0, 0}, // AtomicIAdd
+ {1, 1, 0, 0}, // AtomicISub
+ {1, 1, 0, 0}, // AtomicSMin
+ {1, 1, 0, 0}, // AtomicUMin
+ {1, 1, 0, 0}, // AtomicSMax
+ {1, 1, 0, 0}, // AtomicUMax
+ {1, 1, 0, 0}, // AtomicAnd
+ {1, 1, 0, 0}, // AtomicOr
+ {1, 1, 0, 0}, // AtomicXor
+ {1, 1, 0, 0}, // #243
+ {1, 1, 0, 0}, // #244
+ {1, 1, 0, 0}, // Phi
+ {0, 0, 2, 1}, // LoopMerge
+ {0, 0, 1, 1}, // SelectionMerge
+ {1, 0, 0, 0}, // Label
+ {0, 0, 1, 0}, // Branch
+ {0, 0, 3, 1}, // BranchConditional
+ {0, 0, 0, 0}, // Switch
+ {0, 0, 0, 0}, // Kill
+ {0, 0, 0, 0}, // Return
+ {0, 0, 0, 0}, // ReturnValue
+ {0, 0, 0, 0}, // Unreachable
+ {0, 0, 0, 0}, // LifetimeStart
+ {0, 0, 0, 0}, // LifetimeStop
+ {1, 1, 0, 0}, // #258
+ {1, 1, 0, 0}, // GroupAsyncCopy
+ {0, 0, 0, 0}, // GroupWaitEvents
+ {1, 1, 0, 0}, // GroupAll
+ {1, 1, 0, 0}, // GroupAny
+ {1, 1, 0, 0}, // GroupBroadcast
+ {1, 1, 0, 0}, // GroupIAdd
+ {1, 1, 0, 0}, // GroupFAdd
+ {1, 1, 0, 0}, // GroupFMin
+ {1, 1, 0, 0}, // GroupUMin
+ {1, 1, 0, 0}, // GroupSMin
+ {1, 1, 0, 0}, // GroupFMax
+ {1, 1, 0, 0}, // GroupUMax
+ {1, 1, 0, 0}, // GroupSMax
+ {1, 1, 0, 0}, // #272
+ {1, 1, 0, 0}, // #273
+ {1, 1, 0, 0}, // ReadPipe
+ {1, 1, 0, 0}, // WritePipe
+ {1, 1, 0, 0}, // ReservedReadPipe
+ {1, 1, 0, 0}, // ReservedWritePipe
+ {1, 1, 0, 0}, // ReserveReadPipePackets
+ {1, 1, 0, 0}, // ReserveWritePipePackets
+ {0, 0, 0, 0}, // CommitReadPipe
+ {0, 0, 0, 0}, // CommitWritePipe
+ {1, 1, 0, 0}, // IsValidReserveId
+ {1, 1, 0, 0}, // GetNumPipePackets
+ {1, 1, 0, 0}, // GetMaxPipePackets
+ {1, 1, 0, 0}, // GroupReserveReadPipePackets
+ {1, 1, 0, 0}, // GroupReserveWritePipePackets
+ {0, 0, 0, 0}, // GroupCommitReadPipe
+ {0, 0, 0, 0}, // GroupCommitWritePipe
+ {1, 1, 0, 0}, // #289
+ {1, 1, 0, 0}, // #290
+ {1, 1, 0, 0}, // EnqueueMarker
+ {1, 1, 0, 0}, // EnqueueKernel
+ {1, 1, 0, 0}, // GetKernelNDrangeSubGroupCount
+ {1, 1, 0, 0}, // GetKernelNDrangeMaxSubGroupSize
+ {1, 1, 0, 0}, // GetKernelWorkGroupSize
+ {1, 1, 0, 0}, // GetKernelPreferredWorkGroupSizeMultiple
+ {0, 0, 0, 0}, // RetainEvent
+ {0, 0, 0, 0}, // ReleaseEvent
+ {1, 1, 0, 0}, // CreateUserEvent
+ {1, 1, 0, 0}, // IsValidEvent
+ {0, 0, 0, 0}, // SetUserEventStatus
+ {0, 0, 0, 0}, // CaptureEventProfilingInfo
+ {1, 1, 0, 0}, // GetDefaultQueue
+ {1, 1, 0, 0}, // BuildNDRange
+ {1, 1, 2, 1}, // ImageSparseSampleImplicitLod
+ {1, 1, 2, 1}, // ImageSparseSampleExplicitLod
+ {1, 1, 3, 1}, // ImageSparseSampleDrefImplicitLod
+ {1, 1, 3, 1}, // ImageSparseSampleDrefExplicitLod
+ {1, 1, 2, 1}, // ImageSparseSampleProjImplicitLod
+ {1, 1, 2, 1}, // ImageSparseSampleProjExplicitLod
+ {1, 1, 3, 1}, // ImageSparseSampleProjDrefImplicitLod
+ {1, 1, 3, 1}, // ImageSparseSampleProjDrefExplicitLod
+ {1, 1, 2, 1}, // ImageSparseFetch
+ {1, 1, 3, 1}, // ImageSparseGather
+ {1, 1, 3, 1}, // ImageSparseDrefGather
+ {1, 1, 1, 0}, // ImageSparseTexelsResident
+ {0, 0, 0, 0}, // NoLine
+ {1, 1, 0, 0}, // AtomicFlagTestAndSet
+ {0, 0, 0, 0}, // AtomicFlagClear
+ {1, 1, 0, 0}, // ImageSparseRead
+ {1, 1, 0, 0}, // SizeOf
+ {1, 1, 0, 0}, // TypePipeStorage
+ {1, 1, 0, 0}, // ConstantPipeStorage
+ {1, 1, 0, 0}, // CreatePipeFromPipeStorage
+ {1, 1, 0, 0}, // GetKernelLocalSizeForSubgroupCount
+ {1, 1, 0, 0}, // GetKernelMaxNumSubgroups
+ {1, 1, 0, 0}, // TypeNamedBarrier
+ {1, 1, 0, 1}, // NamedBarrierInitialize
+ {0, 0, 2, 1}, // MemoryNamedBarrier
+ {1, 1, 0, 0}, // ModuleProcessed
+ {0, 0, 0, 1}, // ExecutionModeId
+ {0, 0, 0, 1}, // DecorateId
+ {1, 1, 1, 1}, // GroupNonUniformElect
+ {1, 1, 1, 1}, // GroupNonUniformAll
+ {1, 1, 1, 1}, // GroupNonUniformAny
+ {1, 1, 1, 1}, // GroupNonUniformAllEqual
+ {1, 1, 1, 1}, // GroupNonUniformBroadcast
+ {1, 1, 1, 1}, // GroupNonUniformBroadcastFirst
+ {1, 1, 1, 1}, // GroupNonUniformBallot
+ {1, 1, 1, 1}, // GroupNonUniformInverseBallot
+ {1, 1, 1, 1}, // GroupNonUniformBallotBitExtract
+ {1, 1, 1, 1}, // GroupNonUniformBallotBitCount
+ {1, 1, 1, 1}, // GroupNonUniformBallotFindLSB
+ {1, 1, 1, 1}, // GroupNonUniformBallotFindMSB
+ {1, 1, 1, 1}, // GroupNonUniformShuffle
+ {1, 1, 1, 1}, // GroupNonUniformShuffleXor
+ {1, 1, 1, 1}, // GroupNonUniformShuffleUp
+ {1, 1, 1, 1}, // GroupNonUniformShuffleDown
+ {1, 1, 1, 1}, // GroupNonUniformIAdd
+ {1, 1, 1, 1}, // GroupNonUniformFAdd
+ {1, 1, 1, 1}, // GroupNonUniformIMul
+ {1, 1, 1, 1}, // GroupNonUniformFMul
+ {1, 1, 1, 1}, // GroupNonUniformSMin
+ {1, 1, 1, 1}, // GroupNonUniformUMin
+ {1, 1, 1, 1}, // GroupNonUniformFMin
+ {1, 1, 1, 1}, // GroupNonUniformSMax
+ {1, 1, 1, 1}, // GroupNonUniformUMax
+ {1, 1, 1, 1}, // GroupNonUniformFMax
+ {1, 1, 1, 1}, // GroupNonUniformBitwiseAnd
+ {1, 1, 1, 1}, // GroupNonUniformBitwiseOr
+ {1, 1, 1, 1}, // GroupNonUniformBitwiseXor
+ {1, 1, 1, 1}, // GroupNonUniformLogicalAnd
+ {1, 1, 1, 1}, // GroupNonUniformLogicalOr
+ {1, 1, 1, 1}, // GroupNonUniformLogicalXor
+ {1, 1, 1, 1}, // GroupNonUniformQuadBroadcast
+ {1, 1, 1, 1}, // GroupNonUniformQuadSwap
+};
+static_assert(_SMOLV_ARRAY_SIZE(kSpirvOpData) == kKnownOpsCount, "kSpirvOpData table mismatch with known SpvOps");
+
+// Instruction encoding depends on the table that describes the various SPIR-V opcodes.
+// Whenever we change or expand the table, we need to bump up the SMOL-V version, and make
+// sure that we can still decode files encoded by an older version.
+static int smolv_GetKnownOpsCount(int version)
+{
+ if (version == 0)
+ return SpvOpModuleProcessed+1;
+ if (version == 1) // 2020 February, version 1 added ExecutionModeId..GroupNonUniformQuadSwap
+ return SpvOpGroupNonUniformQuadSwap+1;
+ return 0;
+}
+
+static bool smolv_OpHasResult(SpvOp op, int opsCount)
+{
+ if (op < 0 || op >= opsCount)
+ return false;
+ return kSpirvOpData[op].hasResult != 0;
+}
+
+static bool smolv_OpHasType(SpvOp op, int opsCount)
+{
+ if (op < 0 || op >= opsCount)
+ return false;
+ return kSpirvOpData[op].hasType != 0;
+}
+
+static int smolv_OpDeltaFromResult(SpvOp op, int opsCount)
+{
+ if (op < 0 || op >= opsCount)
+ return 0;
+ return kSpirvOpData[op].deltaFromResult;
+}
+
+static bool smolv_OpVarRest(SpvOp op, int opsCount)
+{
+ if (op < 0 || op >= opsCount)
+ return false;
+ return kSpirvOpData[op].varrest != 0;
+}
+
+static bool smolv_OpDebugInfo(SpvOp op, int opsCount)
+{
+ return
+ op == SpvOpSourceContinued ||
+ op == SpvOpSource ||
+ op == SpvOpSourceExtension ||
+ op == SpvOpName ||
+ op == SpvOpMemberName ||
+ op == SpvOpString ||
+ op == SpvOpLine ||
+ op == SpvOpNoLine ||
+ op == SpvOpModuleProcessed;
+}
+
+
+static int smolv_DecorationExtraOps(int dec)
+{
+ if (dec == 0 || (dec >= 2 && dec <= 5)) // RelaxedPrecision, Block..ColMajor
+ return 0;
+ if (dec >= 29 && dec <= 37) // Stream..XfbStride
+ return 1;
+ return -1; // unknown, encode length
+}
+
+
+// --------------------------------------------------------------------------------------------
+
+
+static bool smolv_CheckGenericHeader(const uint32_t* words, size_t wordCount, uint32_t expectedMagic, uint32_t versionMask)
+{
+ if (!words)
+ return false;
+ if (wordCount < 5)
+ return false;
+
+ uint32_t headerMagic = words[0];
+ if (headerMagic != expectedMagic)
+ return false;
+ uint32_t headerVersion = words[1] & versionMask;
+ if (headerVersion < 0x00010000 || headerVersion > 0x00010500)
+ return false; // only support 1.0 through 1.5
+
+ return true;
+}
+
+static const int kSpirVHeaderMagic = 0x07230203;
+static const int kSmolHeaderMagic = 0x534D4F4C; // "SMOL"
+
+static const int kSmolCurrEncodingVersion = 1;
+
+static bool smolv_CheckSpirVHeader(const uint32_t* words, size_t wordCount)
+{
+ //@TODO: if SPIR-V header magic was reversed, that means the file got written
+ // in a "big endian" order. Need to byteswap all words then.
+ return smolv_CheckGenericHeader(words, wordCount, kSpirVHeaderMagic, 0xFFFFFFFF);
+}
+static bool smolv_CheckSmolHeader(const uint8_t* bytes, size_t byteCount)
+{
+ if (!smolv_CheckGenericHeader((const uint32_t*)bytes, byteCount/4, kSmolHeaderMagic, 0x00FFFFFF))
+ return false;
+ if (byteCount < 24) // one more word past header to store decoded length
+ return false;
+ // SMOL-V version
+ int smolVersion = ((const uint32_t*)bytes)[1] >> 24;
+ if (smolVersion < 0 || smolVersion > kSmolCurrEncodingVersion)
+ return false;
+ return true;
+}
+
+
+static void smolv_Write4(smolv::ByteArray& arr, uint32_t v)
+{
+ arr.push_back(v & 0xFF);
+ arr.push_back((v >> 8) & 0xFF);
+ arr.push_back((v >> 16) & 0xFF);
+ arr.push_back(v >> 24);
+}
+
+static void smolv_Write4(uint8_t*& buf, uint32_t v)
+{
+ memcpy(buf, &v, 4);
+ buf += 4;
+}
+
+
+static bool smolv_Read4(const uint8_t*& data, const uint8_t* dataEnd, uint32_t& outv)
+{
+ if (data + 4 > dataEnd)
+ return false;
+ outv = (data[0]) | (data[1] << 8) | (data[2] << 16) | (data[3] << 24);
+ data += 4;
+ return true;
+}
+
+
+// --------------------------------------------------------------------------------------------
+
+// Variable-length integer encoding for unsigned integers. In each byte:
+// - highest bit set if more bytes follow, cleared if this is last byte.
+// - other 7 bits are the actual value payload.
+// Takes 1-5 bytes to encode an integer (values between 0 and 127 take one byte, etc.).
+
+static void smolv_WriteVarint(smolv::ByteArray& arr, uint32_t v)
+{
+ while (v > 127)
+ {
+ arr.push_back((v & 127) | 128);
+ v >>= 7;
+ }
+ arr.push_back(v & 127);
+}
+
+static bool smolv_ReadVarint(const uint8_t*& data, const uint8_t* dataEnd, uint32_t& outVal)
+{
+ uint32_t v = 0;
+ uint32_t shift = 0;
+ while (data < dataEnd)
+ {
+ uint8_t b = *data;
+ v |= (b & 127) << shift;
+ shift += 7;
+ data++;
+ if (!(b & 128))
+ break;
+ }
+ outVal = v;
+ return true; //@TODO: report failures
+}
+
+static uint32_t smolv_ZigEncode(int32_t i)
+{
+ return (uint32_t(i) << 1) ^ (i >> 31);
+}
+
+static int32_t smolv_ZigDecode(uint32_t u)
+{
+ return (u & 1) ? ((u >> 1) ^ ~0) : (u >> 1);
+}
+
+
+// Remap most common Op codes (Load, Store, Decorate, VectorShuffle etc.) to be in < 16 range, for
+// more compact varint encoding. This basically swaps rarely used op values that are < 16 with the
+// ones that are common.
+
+static SpvOp smolv_RemapOp(SpvOp op)
+{
+# define _SMOLV_SWAP_OP(op1,op2) if (op==op1) return op2; if (op==op2) return op1
+ _SMOLV_SWAP_OP(SpvOpDecorate,SpvOpNop); // 0: 24%
+ _SMOLV_SWAP_OP(SpvOpLoad,SpvOpUndef); // 1: 17%
+ _SMOLV_SWAP_OP(SpvOpStore,SpvOpSourceContinued); // 2: 9%
+ _SMOLV_SWAP_OP(SpvOpAccessChain,SpvOpSource); // 3: 7.2%
+ _SMOLV_SWAP_OP(SpvOpVectorShuffle,SpvOpSourceExtension); // 4: 5.0%
+ // Name - already small enum value - 5: 4.4%
+ // MemberName - already small enum value - 6: 2.9%
+ _SMOLV_SWAP_OP(SpvOpMemberDecorate,SpvOpString); // 7: 4.0%
+ _SMOLV_SWAP_OP(SpvOpLabel,SpvOpLine); // 8: 0.9%
+ _SMOLV_SWAP_OP(SpvOpVariable,(SpvOp)9); // 9: 3.9%
+ _SMOLV_SWAP_OP(SpvOpFMul,SpvOpExtension); // 10: 3.9%
+ _SMOLV_SWAP_OP(SpvOpFAdd,SpvOpExtInstImport); // 11: 2.5%
+ // ExtInst - already small enum value - 12: 1.2%
+ // VectorShuffleCompact - already small enum value - used for compact shuffle encoding
+ _SMOLV_SWAP_OP(SpvOpTypePointer,SpvOpMemoryModel); // 14: 2.2%
+ _SMOLV_SWAP_OP(SpvOpFNegate,SpvOpEntryPoint); // 15: 1.1%
+# undef _SMOLV_SWAP_OP
+ return op;
+}
+
+
+// For most compact varint encoding of common instructions, the instruction length should come out
+// into 3 bits (be <8). SPIR-V instruction lengths are always at least 1, and for some other
+// instructions they are guaranteed to be some other minimum length. Adjust the length before encoding,
+// and after decoding accordingly.
+
+static uint32_t smolv_EncodeLen(SpvOp op, uint32_t len)
+{
+ len--;
+ if (op == SpvOpVectorShuffle) len -= 4;
+ if (op == SpvOpVectorShuffleCompact) len -= 4;
+ if (op == SpvOpDecorate) len -= 2;
+ if (op == SpvOpLoad) len -= 3;
+ if (op == SpvOpAccessChain) len -= 3;
+ return len;
+}
+
+static uint32_t smolv_DecodeLen(SpvOp op, uint32_t len)
+{
+ len++;
+ if (op == SpvOpVectorShuffle) len += 4;
+ if (op == SpvOpVectorShuffleCompact) len += 4;
+ if (op == SpvOpDecorate) len += 2;
+ if (op == SpvOpLoad) len += 3;
+ if (op == SpvOpAccessChain) len += 3;
+ return len;
+}
+
+
+// Shuffling bits of length + opcode to be more compact in varint encoding in typical cases:
+// 0x LLLL OOOO is how SPIR-V encodes it (L=length, O=op), we shuffle into:
+// 0x LLLO OOLO, so that common case (op<16, len<8) is encoded into one byte.
+
+static bool smolv_WriteLengthOp(smolv::ByteArray& arr, uint32_t len, SpvOp op)
+{
+ len = smolv_EncodeLen(op, len);
+ // SPIR-V length field is 16 bits; if we get a larger value that means something
+ // was wrong, e.g. a vector shuffle instruction with less than 4 words (and our
+ // adjustment to common lengths in smolv_EncodeLen wrapped around)
+ if (len > 0xFFFF)
+ return false;
+ op = smolv_RemapOp(op);
+ uint32_t oplen = ((len >> 4) << 20) | ((op >> 4) << 8) | ((len & 0xF) << 4) | (op & 0xF);
+ smolv_WriteVarint(arr, oplen);
+ return true;
+}
+
+static bool smolv_ReadLengthOp(const uint8_t*& data, const uint8_t* dataEnd, uint32_t& outLen, SpvOp& outOp)
+{
+ uint32_t val;
+ if (!smolv_ReadVarint(data, dataEnd, val))
+ return false;
+ outLen = ((val >> 20) << 4) | ((val >> 4) & 0xF);
+ outOp = (SpvOp)(((val >> 4) & 0xFFF0) | (val & 0xF));
+
+ outOp = smolv_RemapOp(outOp);
+ outLen = smolv_DecodeLen(outOp, outLen);
+ return true;
+}
+
+
+
+#define _SMOLV_READ_OP(len, words, op) \
+ uint32_t len = words[0] >> 16; \
+ if (len < 1) return false; /* malformed instruction, length needs to be at least 1 */ \
+ if (words + len > wordsEnd) return false; /* malformed instruction, goes past end of data */ \
+ SpvOp op = (SpvOp)(words[0] & 0xFFFF)
+
+
+bool smolv::Encode(const void* spirvData, size_t spirvSize, ByteArray& outSmolv, uint32_t flags, StripOpNameFilterFunc stripFilter)
+{
+ const size_t wordCount = spirvSize / 4;
+ if (wordCount * 4 != spirvSize)
+ return false;
+ const uint32_t* words = (const uint32_t*)spirvData;
+ const uint32_t* wordsEnd = words + wordCount;
+ if (!smolv_CheckSpirVHeader(words, wordCount))
+ return false;
+
+ // reserve space in output (typical compression is to about 30%; reserve half of input space)
+ outSmolv.reserve(outSmolv.size() + spirvSize/2);
+
+ // header (matches SPIR-V one, except different magic)
+ smolv_Write4(outSmolv, kSmolHeaderMagic);
+ smolv_Write4(outSmolv, (words[1] & 0x00FFFFFF) + (kSmolCurrEncodingVersion<<24)); // SPIR-V version (_XXX) + SMOL-V version (X___)
+ smolv_Write4(outSmolv, words[2]); // generator
+ smolv_Write4(outSmolv, words[3]); // bound
+ smolv_Write4(outSmolv, words[4]); // schema
+
+ const size_t headerSpirvSizeOffset = outSmolv.size(); // size field may get updated later if stripping is enabled
+ smolv_Write4(outSmolv, (uint32_t)spirvSize); // space needed to decode (i.e. original SPIR-V size)
+
+ size_t strippedSpirvWordCount = wordCount;
+ uint32_t prevResult = 0;
+ uint32_t prevDecorate = 0;
+
+ const int knownOpsCount = smolv_GetKnownOpsCount(kSmolCurrEncodingVersion);
+
+ words += 5;
+ while (words < wordsEnd)
+ {
+ _SMOLV_READ_OP(instrLen, words, op);
+
+ if ((flags & kEncodeFlagStripDebugInfo) && smolv_OpDebugInfo(op, knownOpsCount))
+ {
+ if (!stripFilter || op != SpvOpName || !stripFilter(reinterpret_cast<const char*>(&words[2])))
+ {
+ strippedSpirvWordCount -= instrLen;
+ words += instrLen;
+ continue;
+ }
+ }
+
+ // A usual case of vector shuffle, with less than 4 components, each with a value
+ // in [0..3] range: encode it in a more compact form, with the swizzle pattern in one byte.
+ // Turn this into a VectorShuffleCompact instruction, that takes up unused slot in Ops.
+ uint32_t swizzle = 0;
+ if (op == SpvOpVectorShuffle && instrLen <= 9)
+ {
+ uint32_t swz0 = instrLen > 5 ? words[5] : 0;
+ uint32_t swz1 = instrLen > 6 ? words[6] : 0;
+ uint32_t swz2 = instrLen > 7 ? words[7] : 0;
+ uint32_t swz3 = instrLen > 8 ? words[8] : 0;
+ if (swz0 < 4 && swz1 < 4 && swz2 < 4 && swz3 < 4)
+ {
+ op = SpvOpVectorShuffleCompact;
+ swizzle = (swz0 << 6) | (swz1 << 4) | (swz2 << 2) | (swz3);
+ }
+ }
+
+ // length + opcode
+ if (!smolv_WriteLengthOp(outSmolv, instrLen, op))
+ return false;
+
+ size_t ioffs = 1;
+ // write type as varint, if we have it
+ if (smolv_OpHasType(op, knownOpsCount))
+ {
+ if (ioffs >= instrLen)
+ return false;
+ smolv_WriteVarint(outSmolv, words[ioffs]);
+ ioffs++;
+ }
+ // write result as delta+zig+varint, if we have it
+ if (smolv_OpHasResult(op, knownOpsCount))
+ {
+ if (ioffs >= instrLen)
+ return false;
+ uint32_t v = words[ioffs];
+ smolv_WriteVarint(outSmolv, smolv_ZigEncode(v - prevResult)); // some deltas are negative, use zig
+ prevResult = v;
+ ioffs++;
+ }
+
+ // Decorate & MemberDecorate: IDs relative to previous decorate
+ if (op == SpvOpDecorate || op == SpvOpMemberDecorate)
+ {
+ if (ioffs >= instrLen)
+ return false;
+ uint32_t v = words[ioffs];
+ smolv_WriteVarint(outSmolv, smolv_ZigEncode(v - prevDecorate)); // spirv-remapped deltas often negative, use zig
+ prevDecorate = v;
+ ioffs++;
+ }
+
+ // MemberDecorate special encoding: whole row of MemberDecorate instructions is often referring
+ // to the same type and linearly increasing member indices. Scan ahead to see how many we have,
+ // and encode whole bunch as one.
+ if (op == SpvOpMemberDecorate)
+ {
+ // scan ahead until we reach end, non-member-decoration or different type
+ const uint32_t decorationType = words[ioffs-1];
+ const uint32_t* memberWords = words;
+ uint32_t prevIndex = 0;
+ uint32_t prevOffset = 0;
+ // write a byte on how many we have encoded as a bunch
+ size_t countLocation = outSmolv.size();
+ outSmolv.push_back(0);
+ int count = 0;
+ while (memberWords < wordsEnd && count < 255)
+ {
+ _SMOLV_READ_OP(memberLen, memberWords, memberOp);
+ if (memberOp != SpvOpMemberDecorate)
+ break;
+ if (memberLen < 4)
+ return false; // invalid input
+ if (memberWords[1] != decorationType)
+ break;
+
+ // write member index as delta from previous
+ uint32_t memberIndex = memberWords[2];
+ smolv_WriteVarint(outSmolv, memberIndex - prevIndex);
+ prevIndex = memberIndex;
+
+ // decoration (and length if not common/known)
+ uint32_t memberDec = memberWords[3];
+ smolv_WriteVarint(outSmolv, memberDec);
+ const int knownExtraOps = smolv_DecorationExtraOps(memberDec);
+ if (knownExtraOps == -1)
+ smolv_WriteVarint(outSmolv, memberLen-4);
+ else if (unsigned(knownExtraOps) + 4 != memberLen)
+ return false; // invalid input
+
+ // Offset decorations are most often linearly increasing, so encode as deltas
+ if (memberDec == 35) // Offset
+ {
+ if (memberLen != 5)
+ return false;
+ smolv_WriteVarint(outSmolv, memberWords[4]-prevOffset);
+ prevOffset = memberWords[4];
+ }
+ else
+ {
+ // write rest of decorations as varint
+ for (uint32_t i = 4; i < memberLen; ++i)
+ smolv_WriteVarint(outSmolv, memberWords[i]);
+ }
+
+ memberWords += memberLen;
+ ++count;
+ }
+ outSmolv[countLocation] = uint8_t(count);
+ words = memberWords;
+ continue;
+ }
+
+ // Write out this many IDs, encoding them relative+zigzag to result ID
+ int relativeCount = smolv_OpDeltaFromResult(op, knownOpsCount);
+ for (int i = 0; i < relativeCount && ioffs < instrLen; ++i, ++ioffs)
+ {
+ if (ioffs >= instrLen)
+ return false;
+ uint32_t delta = prevResult - words[ioffs];
+ // some deltas are negative (often on branches, or if program was processed by spirv-remap),
+ // so use zig encoding
+ smolv_WriteVarint(outSmolv, smolv_ZigEncode(delta));
+ }
+
+ if (op == SpvOpVectorShuffleCompact)
+ {
+ // compact vector shuffle, just write out single swizzle byte
+ outSmolv.push_back(uint8_t(swizzle));
+ ioffs = instrLen;
+ }
+ else if (smolv_OpVarRest(op, knownOpsCount))
+ {
+ // write out rest of words with variable encoding (expected to be small integers)
+ for (; ioffs < instrLen; ++ioffs)
+ smolv_WriteVarint(outSmolv, words[ioffs]);
+ }
+ else
+ {
+ // write out rest of words without any encoding
+ for (; ioffs < instrLen; ++ioffs)
+ smolv_Write4(outSmolv, words[ioffs]);
+ }
+
+ words += instrLen;
+ }
+
+ if (strippedSpirvWordCount != wordCount)
+ {
+ uint8_t* headerSpirvSize = &outSmolv[headerSpirvSizeOffset];
+ smolv_Write4(headerSpirvSize, (uint32_t)strippedSpirvWordCount * 4);
+ }
+
+ return true;
+}
+
+
+size_t smolv::GetDecodedBufferSize(const void* smolvData, size_t smolvSize)
+{
+ if (!smolv_CheckSmolHeader((const uint8_t*)smolvData, smolvSize))
+ return 0;
+ const uint32_t* words = (const uint32_t*)smolvData;
+ return words[5];
+}
+
+
+bool smolv::Decode(const void* smolvData, size_t smolvSize, void* spirvOutputBuffer, size_t spirvOutputBufferSize, uint32_t flags)
+{
+ // check header, and whether we have enough output buffer space
+ const size_t neededBufferSize = GetDecodedBufferSize(smolvData, smolvSize);
+ if (neededBufferSize == 0)
+ return false; // invalid SMOL-V
+ if (spirvOutputBufferSize < neededBufferSize)
+ return false; // not enough space in output buffer
+ if (spirvOutputBuffer == NULL)
+ return false; // output buffer is null
+
+ const uint8_t* bytes = (const uint8_t*)smolvData;
+ const uint8_t* bytesEnd = bytes + smolvSize;
+
+ uint8_t* outSpirv = (uint8_t*)spirvOutputBuffer;
+
+ uint32_t val;
+ int smolVersion = 0;
+
+ // header
+ smolv_Write4(outSpirv, kSpirVHeaderMagic); bytes += 4;
+ smolv_Read4(bytes, bytesEnd, val); smolVersion = val >> 24; val &= 0x00FFFFFF; smolv_Write4(outSpirv, val); // version
+ smolv_Read4(bytes, bytesEnd, val); smolv_Write4(outSpirv, val); // generator
+ smolv_Read4(bytes, bytesEnd, val); smolv_Write4(outSpirv, val); // bound
+ smolv_Read4(bytes, bytesEnd, val); smolv_Write4(outSpirv, val); // schema
+ bytes += 4; // decode buffer size
+
+ // there are two SMOL-V encoding versions, both not indicating anything in their header version field:
+ // one that is called "before zero" here (2016-08-31 code). Support decoding that one only by presence
+ // of this special flag.
+ const bool beforeZeroVersion = smolVersion == 0 && (flags & kDecodeFlagUse20160831AsZeroVersion) != 0;
+
+ const int knownOpsCount = smolv_GetKnownOpsCount(smolVersion);
+
+ uint32_t prevResult = 0;
+ uint32_t prevDecorate = 0;
+
+ while (bytes < bytesEnd)
+ {
+ // read length + opcode
+ uint32_t instrLen;
+ SpvOp op;
+ if (!smolv_ReadLengthOp(bytes, bytesEnd, instrLen, op))
+ return false;
+ const bool wasSwizzle = (op == SpvOpVectorShuffleCompact);
+ if (wasSwizzle)
+ op = SpvOpVectorShuffle;
+ smolv_Write4(outSpirv, (instrLen << 16) | op);
+
+ size_t ioffs = 1;
+
+ // read type as varint, if we have it
+ if (smolv_OpHasType(op, knownOpsCount))
+ {
+ if (!smolv_ReadVarint(bytes, bytesEnd, val)) return false;
+ smolv_Write4(outSpirv, val);
+ ioffs++;
+ }
+ // read result as delta+varint, if we have it
+ if (smolv_OpHasResult(op, knownOpsCount))
+ {
+ if (!smolv_ReadVarint(bytes, bytesEnd, val)) return false;
+ val = prevResult + smolv_ZigDecode(val);
+ smolv_Write4(outSpirv, val);
+ prevResult = val;
+ ioffs++;
+ }
+
+ // Decorate: IDs relative to previous decorate
+ if (op == SpvOpDecorate || op == SpvOpMemberDecorate)
+ {
+ if (!smolv_ReadVarint(bytes, bytesEnd, val)) return false;
+ // "before zero" version did not use zig encoding for the value
+ val = prevDecorate + (beforeZeroVersion ? val : smolv_ZigDecode(val));
+ smolv_Write4(outSpirv, val);
+ prevDecorate = val;
+ ioffs++;
+ }
+
+ // MemberDecorate special decoding
+ if (op == SpvOpMemberDecorate && !beforeZeroVersion)
+ {
+ if (bytes >= bytesEnd)
+ return false; // broken input
+ int count = *bytes++;
+ int prevIndex = 0;
+ int prevOffset = 0;
+ for (int m = 0; m < count; ++m)
+ {
+ // read member index
+ uint32_t memberIndex;
+ if (!smolv_ReadVarint(bytes, bytesEnd, memberIndex)) return false;
+ memberIndex += prevIndex;
+ prevIndex = memberIndex;
+
+ // decoration (and length if not common/known)
+ uint32_t memberDec;
+ if (!smolv_ReadVarint(bytes, bytesEnd, memberDec)) return false;
+ const int knownExtraOps = smolv_DecorationExtraOps(memberDec);
+ uint32_t memberLen;
+ if (knownExtraOps == -1)
+ {
+ if (!smolv_ReadVarint(bytes, bytesEnd, memberLen)) return false;
+ memberLen += 4;
+ }
+ else
+ memberLen = 4 + knownExtraOps;
+
+ // write SPIR-V op+length (unless it's first member decoration, in which case it was written before)
+ if (m != 0)
+ {
+ smolv_Write4(outSpirv, (memberLen << 16) | op);
+ smolv_Write4(outSpirv, prevDecorate);
+ }
+ smolv_Write4(outSpirv, memberIndex);
+ smolv_Write4(outSpirv, memberDec);
+ // Special case for Offset decorations
+ if (memberDec == 35) // Offset
+ {
+ if (memberLen != 5)
+ return false;
+ if (!smolv_ReadVarint(bytes, bytesEnd, val)) return false;
+ val += prevOffset;
+ smolv_Write4(outSpirv, val);
+ prevOffset = val;
+ }
+ else
+ {
+ for (uint32_t i = 4; i < memberLen; ++i)
+ {
+ if (!smolv_ReadVarint(bytes, bytesEnd, val)) return false;
+ smolv_Write4(outSpirv, val);
+ }
+ }
+ }
+ continue;
+ }
+
+ // Read this many IDs, that are relative to result ID
+ int relativeCount = smolv_OpDeltaFromResult(op, knownOpsCount);
+ // "before zero" version only used zig encoding for IDs of several ops; after
+ // that ops got zig encoding for their IDs
+ bool zigDecodeVals = true;
+ if (beforeZeroVersion)
+ {
+ if (op != SpvOpControlBarrier && op != SpvOpMemoryBarrier && op != SpvOpLoopMerge && op != SpvOpSelectionMerge && op != SpvOpBranch && op != SpvOpBranchConditional && op != SpvOpMemoryNamedBarrier)
+ zigDecodeVals = false;
+ }
+ for (int i = 0; i < relativeCount && ioffs < instrLen; ++i, ++ioffs)
+ {
+ if (!smolv_ReadVarint(bytes, bytesEnd, val)) return false;
+ if (zigDecodeVals)
+ val = smolv_ZigDecode(val);
+ smolv_Write4(outSpirv, prevResult - val);
+ }
+
+ if (wasSwizzle && instrLen <= 9)
+ {
+ uint32_t swizzle = *bytes++;
+ if (instrLen > 5) smolv_Write4(outSpirv, (swizzle >> 6) & 3);
+ if (instrLen > 6) smolv_Write4(outSpirv, (swizzle >> 4) & 3);
+ if (instrLen > 7) smolv_Write4(outSpirv, (swizzle >> 2) & 3);
+ if (instrLen > 8) smolv_Write4(outSpirv, swizzle & 3);
+ }
+ else if (smolv_OpVarRest(op, knownOpsCount))
+ {
+ // read rest of words with variable encoding
+ for (; ioffs < instrLen; ++ioffs)
+ {
+ if (!smolv_ReadVarint(bytes, bytesEnd, val)) return false;
+ smolv_Write4(outSpirv, val);
+ }
+ }
+ else
+ {
+ // read rest of words without any encoding
+ for (; ioffs < instrLen; ++ioffs)
+ {
+ if (!smolv_Read4(bytes, bytesEnd, val)) return false;
+ smolv_Write4(outSpirv, val);
+ }
+ }
+ }
+
+ if ((uint8_t*)spirvOutputBuffer + neededBufferSize != outSpirv)
+ return false; // something went wrong during decoding? we should have decoded to exact output size
+
+ return true;
+}
+
+
+
+// --------------------------------------------------------------------------------------------
+// Calculating instruction count / space stats on SPIR-V and SMOL-V
+
+
+struct smolv::Stats
+{
+ Stats() { memset(this, 0, sizeof(*this)); }
+ size_t opCounts[kKnownOpsCount];
+ size_t opSizes[kKnownOpsCount];
+ size_t smolOpSizes[kKnownOpsCount];
+ size_t varintCountsOp[6];
+ size_t varintCountsType[6];
+ size_t varintCountsRes[6];
+ size_t varintCountsOther[6];
+ size_t totalOps;
+ size_t totalSize;
+ size_t totalSizeSmol;
+ size_t inputCount;
+};
+
+
+smolv::Stats* smolv::StatsCreate()
+{
+ return new Stats();
+}
+
+void smolv::StatsDelete(smolv::Stats *s)
+{
+ delete s;
+}
+
+
+bool smolv::StatsCalculate(smolv::Stats* stats, const void* spirvData, size_t spirvSize)
+{
+ if (!stats)
+ return false;
+
+ const size_t wordCount = spirvSize / 4;
+ if (wordCount * 4 != spirvSize)
+ return false;
+ const uint32_t* words = (const uint32_t*)spirvData;
+ const uint32_t* wordsEnd = words + wordCount;
+ if (!smolv_CheckSpirVHeader(words, wordCount))
+ return false;
+ words += 5;
+
+ stats->inputCount++;
+ stats->totalSize += wordCount;
+
+ while (words < wordsEnd)
+ {
+ _SMOLV_READ_OP(instrLen, words, op);
+
+ if (op < kKnownOpsCount)
+ {
+ stats->opCounts[op]++;
+ stats->opSizes[op] += instrLen;
+ }
+ words += instrLen;
+ stats->totalOps++;
+ }
+
+ return true;
+}
+
+
+bool smolv::StatsCalculateSmol(smolv::Stats* stats, const void* smolvData, size_t smolvSize)
+{
+ if (!stats)
+ return false;
+
+ // debugging helper to dump all encoded bytes to stdout, keep at "if 0"
+# if 0
+# define _SMOLV_DEBUG_PRINT_ENCODED_BYTES() { \
+ printf("Op %-22s ", op < kKnownOpsCount ? kSpirvOpNames[op] : "???"); \
+ for (const uint8_t* b = instrBegin; b < bytes; ++b) \
+ printf("%02x ", *b); \
+ printf("\n"); \
+ }
+# else
+# define _SMOLV_DEBUG_PRINT_ENCODED_BYTES() {}
+# endif
+
+ const uint8_t* bytes = (const uint8_t*)smolvData;
+ const uint8_t* bytesEnd = bytes + smolvSize;
+ if (!smolv_CheckSmolHeader(bytes, smolvSize))
+ return false;
+
+ uint32_t val;
+ int smolVersion;
+ bytes += 4;
+ smolv_Read4(bytes, bytesEnd, val); smolVersion = val >> 24;
+ const int knownOpsCount = smolv_GetKnownOpsCount(smolVersion);
+ bytes += 16;
+
+ stats->totalSizeSmol += smolvSize;
+
+ while (bytes < bytesEnd)
+ {
+ const uint8_t* instrBegin = bytes;
+ const uint8_t* varBegin;
+
+ // read length + opcode
+ uint32_t instrLen;
+ SpvOp op;
+ varBegin = bytes;
+ if (!smolv_ReadLengthOp(bytes, bytesEnd, instrLen, op))
+ return false;
+ const bool wasSwizzle = (op == SpvOpVectorShuffleCompact);
+ if (wasSwizzle)
+ op = SpvOpVectorShuffle;
+ stats->varintCountsOp[bytes-varBegin]++;
+
+ size_t ioffs = 1;
+ if (smolv_OpHasType(op, knownOpsCount))
+ {
+ varBegin = bytes;
+ if (!smolv_ReadVarint(bytes, bytesEnd, val)) return false;
+ stats->varintCountsType[bytes-varBegin]++;
+ ioffs++;
+ }
+ if (smolv_OpHasResult(op, knownOpsCount))
+ {
+ varBegin = bytes;
+ if (!smolv_ReadVarint(bytes, bytesEnd, val)) return false;
+ stats->varintCountsRes[bytes-varBegin]++;
+ ioffs++;
+ }
+
+ if (op == SpvOpDecorate || op == SpvOpMemberDecorate)
+ {
+ if (!smolv_ReadVarint(bytes, bytesEnd, val)) return false;
+ ioffs++;
+ }
+ // MemberDecorate special decoding
+ if (op == SpvOpMemberDecorate)
+ {
+ if (bytes >= bytesEnd)
+ return false; // broken input
+ int count = *bytes++;
+ for (int m = 0; m < count; ++m)
+ {
+ uint32_t memberIndex;
+ if (!smolv_ReadVarint(bytes, bytesEnd, memberIndex)) return false;
+ uint32_t memberDec;
+ if (!smolv_ReadVarint(bytes, bytesEnd, memberDec)) return false;
+ const int knownExtraOps = smolv_DecorationExtraOps(memberDec);
+ uint32_t memberLen;
+ if (knownExtraOps == -1)
+ {
+ if (!smolv_ReadVarint(bytes, bytesEnd, memberLen)) return false;
+ memberLen += 4;
+ }
+ else
+ memberLen = 4 + knownExtraOps;
+ for (uint32_t i = 4; i < memberLen; ++i)
+ {
+ if (!smolv_ReadVarint(bytes, bytesEnd, val)) return false;
+ }
+ }
+ stats->smolOpSizes[op] += bytes - instrBegin;
+ _SMOLV_DEBUG_PRINT_ENCODED_BYTES();
+ continue;
+ }
+
+ int relativeCount = smolv_OpDeltaFromResult(op, knownOpsCount);
+ for (int i = 0; i < relativeCount && ioffs < instrLen; ++i, ++ioffs)
+ {
+ varBegin = bytes;
+ if (!smolv_ReadVarint(bytes, bytesEnd, val)) return false;
+ stats->varintCountsRes[bytes-varBegin]++;
+ }
+
+ if (wasSwizzle && instrLen <= 9)
+ {
+ bytes++;
+ }
+ else if (smolv_OpVarRest(op, knownOpsCount))
+ {
+ for (; ioffs < instrLen; ++ioffs)
+ {
+ varBegin = bytes;
+ if (!smolv_ReadVarint(bytes, bytesEnd, val)) return false;
+ stats->varintCountsOther[bytes-varBegin]++;
+ }
+ }
+ else
+ {
+ for (; ioffs < instrLen; ++ioffs)
+ {
+ if (!smolv_Read4(bytes, bytesEnd, val)) return false;
+ }
+ }
+
+ if (op < kKnownOpsCount)
+ {
+ stats->smolOpSizes[op] += bytes - instrBegin;
+ }
+ _SMOLV_DEBUG_PRINT_ENCODED_BYTES();
+ }
+
+ return true;
+}
+
+static bool CompareOpCounters (std::pair<SpvOp,size_t> a, std::pair<SpvOp,size_t> b)
+{
+ return a.second > b.second;
+}
+
+void smolv::StatsPrint(const Stats* stats)
+{
+ if (!stats)
+ return;
+
+ typedef std::pair<SpvOp,size_t> OpCounter;
+ OpCounter counts[kKnownOpsCount];
+ OpCounter sizes[kKnownOpsCount];
+ OpCounter sizesSmol[kKnownOpsCount];
+ for (int i = 0; i < kKnownOpsCount; ++i)
+ {
+ counts[i].first = (SpvOp)i;
+ counts[i].second = stats->opCounts[i];
+ sizes[i].first = (SpvOp)i;
+ sizes[i].second = stats->opSizes[i];
+ sizesSmol[i].first = (SpvOp)i;
+ sizesSmol[i].second = stats->smolOpSizes[i];
+ }
+ std::sort(counts, counts + kKnownOpsCount, CompareOpCounters);
+ std::sort(sizes, sizes + kKnownOpsCount, CompareOpCounters);
+ std::sort(sizesSmol, sizesSmol + kKnownOpsCount, CompareOpCounters);
+
+ printf("Stats for %i SPIR-V inputs, total size %i words (%.1fKB):\n", (int)stats->inputCount, (int)stats->totalSize, stats->totalSize * 4.0f / 1024.0f);
+ printf("Most occuring ops:\n");
+ for (int i = 0; i < 30; ++i)
+ {
+ SpvOp op = counts[i].first;
+ printf(" #%2i: %4i %-20s %4i (%4.1f%%)\n", i, op, kSpirvOpNames[op], (int)counts[i].second, (float)counts[i].second / (float)stats->totalOps * 100.0f);
+ }
+ printf("Largest total size of ops:\n");
+ for (int i = 0; i < 30; ++i)
+ {
+ SpvOp op = sizes[i].first;
+ printf(" #%2i: %-22s %6i (%4.1f%%) avg len %.1f\n",
+ i,
+ kSpirvOpNames[op],
+ (int)sizes[i].second*4,
+ (float)sizes[i].second / (float)stats->totalSize * 100.0f,
+ (float)sizes[i].second*4 / (float)stats->opCounts[op]
+ );
+ }
+ printf("SMOL varint encoding counts per byte length:\n");
+ printf(" B: %6s %6s %6s %6s\n", "Op", "Type", "Result", "Other");
+ for (int i = 1; i < 6; ++i)
+ {
+ printf(" %i: %6i %6i %6i %6i\n", i, (int)stats->varintCountsOp[i], (int)stats->varintCountsType[i], (int)stats->varintCountsRes[i], (int)stats->varintCountsOther[i]);
+ }
+ printf("Largest total size of ops in SMOL:\n");
+ for (int i = 0; i < 30; ++i)
+ {
+ SpvOp op = sizesSmol[i].first;
+ printf(" #%2i: %-22s %6i (%4.1f%%) avg len %.1f\n",
+ i,
+ kSpirvOpNames[op],
+ (int)sizesSmol[i].second,
+ (float)sizesSmol[i].second / (float)stats->totalSizeSmol * 100.0f,
+ (float)sizesSmol[i].second / (float)stats->opCounts[op]
+ );
+ }
+}
+
+
+// ------------------------------------------------------------------------------
+// This software is available under 2 licenses -- choose whichever you prefer.
+// ------------------------------------------------------------------------------
+// ALTERNATIVE A - MIT License
+// Copyright (c) 2016-2020 Aras Pranckevicius
+// Permission is hereby granted, free of charge, to any person obtaining a copy of
+// this software and associated documentation files (the "Software"), to deal in
+// the Software without restriction, including without limitation the rights to
+// use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
+// of the Software, and to permit persons to whom the Software is furnished to do
+// so, subject to the following conditions:
+// The above copyright notice and this permission notice shall be included in all
+// copies or substantial portions of the Software.
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+// SOFTWARE.
+// ------------------------------------------------------------------------------
+// ALTERNATIVE B - Public Domain (www.unlicense.org)
+// This is free and unencumbered software released into the public domain.
+// Anyone is free to copy, modify, publish, use, compile, sell, or distribute this
+// software, either in source code form or as a compiled binary, for any purpose,
+// commercial or non-commercial, and by any means.
+// In jurisdictions that recognize copyright laws, the author or authors of this
+// software dedicate any and all copyright interest in the software to the public
+// domain. We make this dedication for the benefit of the public at large and to
+// the detriment of our heirs and successors. We intend this dedication to be an
+// overt act of relinquishment in perpetuity of all present and future rights to
+// this software under copyright law.
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+// AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
+// ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+// ------------------------------------------------------------------------------
diff --git a/thirdparty/misc/smolv.h b/thirdparty/misc/smolv.h
new file mode 100644
index 0000000000..798ee4126f
--- /dev/null
+++ b/thirdparty/misc/smolv.h
@@ -0,0 +1,169 @@
+// smol-v - public domain - https://github.com/aras-p/smol-v
+// authored 2016-2020 by Aras Pranckevicius
+// no warranty implied; use at your own risk
+// See end of file for license information.
+//
+//
+// ### OVERVIEW:
+//
+// SMOL-V encodes Vulkan/Khronos SPIR-V format programs into a form that is smaller, and is more
+// compressible. Normally no changes to the programs are done; they decode
+// into exactly same program as what was encoded. Optionally, debug information
+// can be removed too.
+//
+// SPIR-V is a very verbose format, several times larger than same programs expressed in other
+// shader formats (e.g. DX11 bytecode, GLSL, DX9 bytecode etc.). The SSA-form with ever increasing
+// IDs is not very appreciated by regular data compressors either. SMOL-V does several things
+// to improve this:
+// - Many words, especially ones that most often have small values, are encoded using
+// "varint" scheme (1-5 bytes per word, with just one byte for values in 0..127 range).
+// See https://developers.google.com/protocol-buffers/docs/encoding
+// - Some IDs used in the program are delta-encoded, relative to previously seen IDs (e.g. Result
+// IDs). Often instructions reference things that were computed just before, so this results in
+// small deltas. These values are also encoded using "varint" scheme.
+// - Reordering instruction opcodes so that the most common ones are the smallest values, for smaller
+// varint encoding.
+// - Encoding several instructions in a more compact form, e.g. the "typical <=4 component swizzle"
+// shape of a VectorShuffle instruction, or sequences of MemberDecorate instructions.
+//
+// A somewhat similar utility is spirv-remap from glslang, see
+// https://github.com/KhronosGroup/glslang/blob/master/README-spirv-remap.txt
+//
+//
+// ### USAGE:
+//
+// Add source/smolv.h and source/smolv.cpp to your C++ project build.
+// Currently it might require C++11 or somesuch; I only tested with Visual Studio 2017/2019, Mac Xcode 11 and Gcc 5.4.
+//
+// smolv::Encode and smolv::Decode is the basic functionality.
+//
+// Other functions are for development/statistics purposes, to figure out frequencies and
+// distributions of the instructions.
+//
+// There's a test + compression benchmarking suite in testing/testmain.cpp; using that needs adding
+// other files under testing/external to the build too (3rd party code: glslang remapper, Zstd, LZ4).
+//
+//
+// ### LIMITATIONS / TODO:
+//
+// - SPIR-V where the words got stored in big-endian layout is not supported yet.
+// - The whole thing might not work on Big-Endian CPUs. It might, but I'm not 100% sure.
+// - Not much prevention is done against malformed/corrupted inputs, TODO.
+// - Out of memory cases are not handled. The code will either throw exception
+// or crash, depending on your compilation flags.
+
+#pragma once
+
+#include <stdint.h>
+#include <vector>
+#include <cstddef>
+
+namespace smolv
+{
+ typedef std::vector<uint8_t> ByteArray;
+
+ enum EncodeFlags
+ {
+ kEncodeFlagNone = 0,
+ kEncodeFlagStripDebugInfo = (1<<0), // Strip all optional SPIR-V instructions (debug names etc.)
+ };
+ enum DecodeFlags
+ {
+ kDecodeFlagNone = 0,
+ kDecodeFlagUse20160831AsZeroVersion = (1 << 0), // For "version zero" of SMOL-V encoding, use 2016 08 31 code path (this is what happens to be used by Unity 2017-2020)
+ };
+
+ // Preserve *some* OpName debug names.
+ // Return true to preserve, false to strip.
+ // This is really only used to implement a workaround for problems with some Vulkan drivers.
+ typedef bool(*StripOpNameFilterFunc)(const char* name);
+
+ // -------------------------------------------------------------------
+ // Encoding / Decoding
+
+ // Encode SPIR-V into SMOL-V.
+ //
+ // Resulting data is appended to outSmolv array (the array is not cleared).
+ //
+ // flags is bitset of EncodeFlags values.
+ //
+ // Returns false on malformed SPIR-V input; if that happens the output array might get
+ // partial/broken SMOL-V program.
+ bool Encode(const void* spirvData, size_t spirvSize, ByteArray& outSmolv, uint32_t flags = kEncodeFlagNone, StripOpNameFilterFunc stripFilter = 0);
+
+
+ // Decode SMOL-V into SPIR-V.
+ //
+ // Resulting data is written into the passed buffer. Get required buffer space with
+ // GetDecodeBufferSize; this is the size of decoded SPIR-V program.
+ //
+ // flags is bitset of DecodeFlags values.
+
+ // Decoding does no memory allocations.
+ //
+ // Returns false on malformed input; if that happens the output buffer might be only partially
+ // written to.
+ bool Decode(const void* smolvData, size_t smolvSize, void* spirvOutputBuffer, size_t spirvOutputBufferSize, uint32_t flags = kDecodeFlagNone);
+
+
+ // Given a SMOL-V program, get size of the decoded SPIR-V program.
+ // This is the buffer size that Decode expects.
+ //
+ // Returns zero on malformed input (just checks the header, not the full input).
+ size_t GetDecodedBufferSize(const void* smolvData, size_t smolvSize);
+
+
+ // -------------------------------------------------------------------
+ // Computing instruction statistics on SPIR-V/SMOL-V programs
+
+ struct Stats;
+
+ Stats* StatsCreate();
+ void StatsDelete(Stats* s);
+
+ bool StatsCalculate(Stats* stats, const void* spirvData, size_t spirvSize);
+ bool StatsCalculateSmol(Stats* stats, const void* smolvData, size_t smolvSize);
+ void StatsPrint(const Stats* stats);
+
+} // namespace smolv
+
+
+// ------------------------------------------------------------------------------
+// This software is available under 2 licenses -- choose whichever you prefer.
+// ------------------------------------------------------------------------------
+// ALTERNATIVE A - MIT License
+// Copyright (c) 2016-2020 Aras Pranckevicius
+// Permission is hereby granted, free of charge, to any person obtaining a copy of
+// this software and associated documentation files (the "Software"), to deal in
+// the Software without restriction, including without limitation the rights to
+// use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
+// of the Software, and to permit persons to whom the Software is furnished to do
+// so, subject to the following conditions:
+// The above copyright notice and this permission notice shall be included in all
+// copies or substantial portions of the Software.
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+// SOFTWARE.
+// ------------------------------------------------------------------------------
+// ALTERNATIVE B - Public Domain (www.unlicense.org)
+// This is free and unencumbered software released into the public domain.
+// Anyone is free to copy, modify, publish, use, compile, sell, or distribute this
+// software, either in source code form or as a compiled binary, for any purpose,
+// commercial or non-commercial, and by any means.
+// In jurisdictions that recognize copyright laws, the author or authors of this
+// software dedicate any and all copyright interest in the software to the public
+// domain. We make this dedication for the benefit of the public at large and to
+// the detriment of our heirs and successors. We intend this dedication to be an
+// overt act of relinquishment in perpetuity of all present and future rights to
+// this software under copyright law.
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+// AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
+// ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+// ------------------------------------------------------------------------------
diff --git a/thirdparty/misc/stb_vorbis.c b/thirdparty/misc/stb_vorbis.c
index b0d79b1724..a8cbfa6c23 100644
--- a/thirdparty/misc/stb_vorbis.c
+++ b/thirdparty/misc/stb_vorbis.c
@@ -1,4 +1,4 @@
-// Ogg Vorbis audio decoder - v1.19 - public domain
+// Ogg Vorbis audio decoder - v1.20 - public domain
// http://nothings.org/stb_vorbis/
//
// Original version written by Sean Barrett in 2007.
@@ -31,9 +31,11 @@
// Phillip Bennefall Rohit Thiago Goulart
// github:manxorist saga musix github:infatum
// Timur Gagiev Maxwell Koo Peter Waller
-// github:audinowho Dougall Johnson
+// github:audinowho Dougall Johnson David Reid
+// github:Clownacy Pedro J. Estebanez Remi Verschelde
//
// Partial history:
+// 1.20 - 2020-07-11 - several small fixes
// 1.19 - 2020-02-05 - warnings
// 1.18 - 2020-02-02 - fix seek bugs; parse header comments; misc warnings etc.
// 1.17 - 2019-07-08 - fix CVE-2019-13217..CVE-2019-13223 (by ForAllSecure)
@@ -577,7 +579,7 @@ enum STBVorbisError
#if defined(_MSC_VER) || defined(__MINGW32__)
#include <malloc.h>
#endif
- #if defined(__linux__) || defined(__linux) || defined(__EMSCRIPTEN__)
+ #if defined(__linux__) || defined(__linux) || defined(__EMSCRIPTEN__) || defined(__NEWLIB__)
#include <alloca.h>
#endif
#else // STB_VORBIS_NO_CRT
@@ -599,7 +601,9 @@ enum STBVorbisError
#undef __forceinline
#endif
#define __forceinline
+ #ifndef alloca
#define alloca __builtin_alloca
+ #endif
#elif !defined(_MSC_VER)
#if __GNUC__
#define __forceinline inline
@@ -1600,7 +1604,8 @@ static uint32 get_bits(vorb *f, int n)
f->valid_bits += 8;
}
}
- if (f->valid_bits < 0) return 0;
+
+ assert(f->valid_bits >= n);
z = f->acc & ((1 << n)-1);
f->acc >>= n;
f->valid_bits -= n;
@@ -3630,6 +3635,7 @@ static int start_decoder(vorb *f)
//file vendor
len = get32_packet(f);
f->vendor = (char*)setup_malloc(f, sizeof(char) * (len+1));
+ if (f->vendor == NULL) return error(f, VORBIS_outofmem);
for(i=0; i < len; ++i) {
f->vendor[i] = get8_packet(f);
}
@@ -3637,10 +3643,12 @@ static int start_decoder(vorb *f)
//user comments
f->comment_list_length = get32_packet(f);
f->comment_list = (char**)setup_malloc(f, sizeof(char*) * (f->comment_list_length));
+ if (f->comment_list == NULL) return error(f, VORBIS_outofmem);
for(i=0; i < f->comment_list_length; ++i) {
len = get32_packet(f);
f->comment_list[i] = (char*)setup_malloc(f, sizeof(char) * (len+1));
+ if (f->comment_list[i] == NULL) return error(f, VORBIS_outofmem);
for(j=0; j < len; ++j) {
f->comment_list[i][j] = get8_packet(f);
@@ -4253,7 +4261,7 @@ static void vorbis_init(stb_vorbis *p, const stb_vorbis_alloc *z)
memset(p, 0, sizeof(*p)); // NULL out all malloc'd pointers to start
if (z) {
p->alloc = *z;
- p->alloc.alloc_buffer_length_in_bytes = (p->alloc.alloc_buffer_length_in_bytes+3) & ~3;
+ p->alloc.alloc_buffer_length_in_bytes &= ~7;
p->temp_offset = p->alloc.alloc_buffer_length_in_bytes;
}
p->eof = 0;
diff --git a/thirdparty/misc/triangulator.cpp b/thirdparty/misc/triangulator.cpp
deleted file mode 100644
index 75b2b064c4..0000000000
--- a/thirdparty/misc/triangulator.cpp
+++ /dev/null
@@ -1,1550 +0,0 @@
-//Copyright (C) 2011 by Ivan Fratric
-//
-//Permission is hereby granted, free of charge, to any person obtaining a copy
-//of this software and associated documentation files (the "Software"), to deal
-//in the Software without restriction, including without limitation the rights
-//to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
-//copies of the Software, and to permit persons to whom the Software is
-//furnished to do so, subject to the following conditions:
-//
-//The above copyright notice and this permission notice shall be included in
-//all copies or substantial portions of the Software.
-//
-//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
-//IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
-//FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
-//AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
-//LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
-//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
-//THE SOFTWARE.
-
-
-#include <stdio.h>
-#include <string.h>
-#include <math.h>
-
-#include "triangulator.h"
-
-
-#define TRIANGULATOR_VERTEXTYPE_REGULAR 0
-#define TRIANGULATOR_VERTEXTYPE_START 1
-#define TRIANGULATOR_VERTEXTYPE_END 2
-#define TRIANGULATOR_VERTEXTYPE_SPLIT 3
-#define TRIANGULATOR_VERTEXTYPE_MERGE 4
-
-TriangulatorPoly::TriangulatorPoly() {
- hole = false;
- numpoints = 0;
- points = NULL;
-}
-
-TriangulatorPoly::~TriangulatorPoly() {
- if(points) delete [] points;
-}
-
-void TriangulatorPoly::Clear() {
- if(points) delete [] points;
- hole = false;
- numpoints = 0;
- points = NULL;
-}
-
-void TriangulatorPoly::Init(long numpoints) {
- Clear();
- this->numpoints = numpoints;
- points = new Vector2[numpoints];
-}
-
-void TriangulatorPoly::Triangle(Vector2 &p1, Vector2 &p2, Vector2 &p3) {
- Init(3);
- points[0] = p1;
- points[1] = p2;
- points[2] = p3;
-}
-
-TriangulatorPoly::TriangulatorPoly(const TriangulatorPoly &src) {
- hole = src.hole;
- numpoints = src.numpoints;
- points = new Vector2[numpoints];
- memcpy(points, src.points, numpoints*sizeof(Vector2));
-}
-
-TriangulatorPoly& TriangulatorPoly::operator=(const TriangulatorPoly &src) {
- Clear();
- hole = src.hole;
- numpoints = src.numpoints;
- points = new Vector2[numpoints];
- memcpy(points, src.points, numpoints*sizeof(Vector2));
- return *this;
-}
-
-int TriangulatorPoly::GetOrientation() {
- long i1,i2;
- real_t area = 0;
- for(i1=0; i1<numpoints; i1++) {
- i2 = i1+1;
- if(i2 == numpoints) i2 = 0;
- area += points[i1].x * points[i2].y - points[i1].y * points[i2].x;
- }
- if(area>0) return TRIANGULATOR_CCW;
- if(area<0) return TRIANGULATOR_CW;
- return 0;
-}
-
-void TriangulatorPoly::SetOrientation(int orientation) {
- int polyorientation = GetOrientation();
- if(polyorientation&&(polyorientation!=orientation)) {
- Invert();
- }
-}
-
-void TriangulatorPoly::Invert() {
- long i;
- Vector2 *invpoints;
-
- invpoints = new Vector2[numpoints];
- for(i=0;i<numpoints;i++) {
- invpoints[i] = points[numpoints-i-1];
- }
-
- delete [] points;
- points = invpoints;
-}
-
-Vector2 TriangulatorPartition::Normalize(const Vector2 &p) {
- Vector2 r;
- real_t n = sqrt(p.x*p.x + p.y*p.y);
- if(n!=0) {
- r = p/n;
- } else {
- r.x = 0;
- r.y = 0;
- }
- return r;
-}
-
-real_t TriangulatorPartition::Distance(const Vector2 &p1, const Vector2 &p2) {
- real_t dx,dy;
- dx = p2.x - p1.x;
- dy = p2.y - p1.y;
- return(sqrt(dx*dx + dy*dy));
-}
-
-//checks if two lines intersect
-int TriangulatorPartition::Intersects(Vector2 &p11, Vector2 &p12, Vector2 &p21, Vector2 &p22) {
- if((p11.x == p21.x)&&(p11.y == p21.y)) return 0;
- if((p11.x == p22.x)&&(p11.y == p22.y)) return 0;
- if((p12.x == p21.x)&&(p12.y == p21.y)) return 0;
- if((p12.x == p22.x)&&(p12.y == p22.y)) return 0;
-
- Vector2 v1ort,v2ort,v;
- real_t dot11,dot12,dot21,dot22;
-
- v1ort.x = p12.y-p11.y;
- v1ort.y = p11.x-p12.x;
-
- v2ort.x = p22.y-p21.y;
- v2ort.y = p21.x-p22.x;
-
- v = p21-p11;
- dot21 = v.x*v1ort.x + v.y*v1ort.y;
- v = p22-p11;
- dot22 = v.x*v1ort.x + v.y*v1ort.y;
-
- v = p11-p21;
- dot11 = v.x*v2ort.x + v.y*v2ort.y;
- v = p12-p21;
- dot12 = v.x*v2ort.x + v.y*v2ort.y;
-
- if(dot11*dot12>0) return 0;
- if(dot21*dot22>0) return 0;
-
- return 1;
-}
-
-//removes holes from inpolys by merging them with non-holes
-int TriangulatorPartition::RemoveHoles(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *outpolys) {
- List<TriangulatorPoly> polys;
- List<TriangulatorPoly>::Element *holeiter,*polyiter,*iter,*iter2;
- long i,i2,holepointindex,polypointindex;
- Vector2 holepoint,polypoint,bestpolypoint;
- Vector2 linep1,linep2;
- Vector2 v1,v2;
- TriangulatorPoly newpoly;
- bool hasholes;
- bool pointvisible;
- bool pointfound;
-
- //check for trivial case (no holes)
- hasholes = false;
- for(iter = inpolys->front(); iter; iter=iter->next()) {
- if(iter->get().IsHole()) {
- hasholes = true;
- break;
- }
- }
- if(!hasholes) {
- for(iter = inpolys->front(); iter; iter=iter->next()) {
- outpolys->push_back(iter->get());
- }
- return 1;
- }
-
- polys = *inpolys;
-
- while(1) {
- //find the hole point with the largest x
- hasholes = false;
- for(iter = polys.front(); iter; iter=iter->next()) {
- if(!iter->get().IsHole()) continue;
-
- if(!hasholes) {
- hasholes = true;
- holeiter = iter;
- holepointindex = 0;
- }
-
- for(i=0; i < iter->get().GetNumPoints(); i++) {
- if(iter->get().GetPoint(i).x > holeiter->get().GetPoint(holepointindex).x) {
- holeiter = iter;
- holepointindex = i;
- }
- }
- }
- if(!hasholes) break;
- holepoint = holeiter->get().GetPoint(holepointindex);
-
- pointfound = false;
- for(iter = polys.front(); iter; iter=iter->next()) {
- if(iter->get().IsHole()) continue;
- for(i=0; i < iter->get().GetNumPoints(); i++) {
- if(iter->get().GetPoint(i).x <= holepoint.x) continue;
- if(!InCone(iter->get().GetPoint((i+iter->get().GetNumPoints()-1)%(iter->get().GetNumPoints())),
- iter->get().GetPoint(i),
- iter->get().GetPoint((i+1)%(iter->get().GetNumPoints())),
- holepoint))
- continue;
- polypoint = iter->get().GetPoint(i);
- if(pointfound) {
- v1 = Normalize(polypoint-holepoint);
- v2 = Normalize(bestpolypoint-holepoint);
- if(v2.x > v1.x) continue;
- }
- pointvisible = true;
- for(iter2 = polys.front(); iter2; iter2=iter2->next()) {
- if(iter2->get().IsHole()) continue;
- for(i2=0; i2 < iter2->get().GetNumPoints(); i2++) {
- linep1 = iter2->get().GetPoint(i2);
- linep2 = iter2->get().GetPoint((i2+1)%(iter2->get().GetNumPoints()));
- if(Intersects(holepoint,polypoint,linep1,linep2)) {
- pointvisible = false;
- break;
- }
- }
- if(!pointvisible) break;
- }
- if(pointvisible) {
- pointfound = true;
- bestpolypoint = polypoint;
- polyiter = iter;
- polypointindex = i;
- }
- }
- }
-
- if(!pointfound) return 0;
-
- newpoly.Init(holeiter->get().GetNumPoints() + polyiter->get().GetNumPoints() + 2);
- i2 = 0;
- for(i=0;i<=polypointindex;i++) {
- newpoly[i2] = polyiter->get().GetPoint(i);
- i2++;
- }
- for(i=0;i<=holeiter->get().GetNumPoints();i++) {
- newpoly[i2] = holeiter->get().GetPoint((i+holepointindex)%holeiter->get().GetNumPoints());
- i2++;
- }
- for(i=polypointindex;i<polyiter->get().GetNumPoints();i++) {
- newpoly[i2] = polyiter->get().GetPoint(i);
- i2++;
- }
-
- polys.erase(holeiter);
- polys.erase(polyiter);
- polys.push_back(newpoly);
- }
-
- for(iter = polys.front(); iter; iter=iter->next()) {
- outpolys->push_back(iter->get());
- }
-
- return 1;
-}
-
-bool TriangulatorPartition::IsConvex(Vector2& p1, Vector2& p2, Vector2& p3) {
- real_t tmp;
- tmp = (p3.y-p1.y)*(p2.x-p1.x)-(p3.x-p1.x)*(p2.y-p1.y);
- if(tmp>0) return 1;
- else return 0;
-}
-
-bool TriangulatorPartition::IsReflex(Vector2& p1, Vector2& p2, Vector2& p3) {
- real_t tmp;
- tmp = (p3.y-p1.y)*(p2.x-p1.x)-(p3.x-p1.x)*(p2.y-p1.y);
- if(tmp<0) return 1;
- else return 0;
-}
-
-bool TriangulatorPartition::IsInside(Vector2& p1, Vector2& p2, Vector2& p3, Vector2 &p) {
- if(IsConvex(p1,p,p2)) return false;
- if(IsConvex(p2,p,p3)) return false;
- if(IsConvex(p3,p,p1)) return false;
- return true;
-}
-
-bool TriangulatorPartition::InCone(Vector2 &p1, Vector2 &p2, Vector2 &p3, Vector2 &p) {
- bool convex;
-
- convex = IsConvex(p1,p2,p3);
-
- if(convex) {
- if(!IsConvex(p1,p2,p)) return false;
- if(!IsConvex(p2,p3,p)) return false;
- return true;
- } else {
- if(IsConvex(p1,p2,p)) return true;
- if(IsConvex(p2,p3,p)) return true;
- return false;
- }
-}
-
-bool TriangulatorPartition::InCone(PartitionVertex *v, Vector2 &p) {
- Vector2 p1,p2,p3;
-
- p1 = v->previous->p;
- p2 = v->p;
- p3 = v->next->p;
-
- return InCone(p1,p2,p3,p);
-}
-
-void TriangulatorPartition::UpdateVertexReflexity(PartitionVertex *v) {
- PartitionVertex *v1,*v3;
- v1 = v->previous;
- v3 = v->next;
- v->isConvex = !IsReflex(v1->p,v->p,v3->p);
-}
-
-void TriangulatorPartition::UpdateVertex(PartitionVertex *v, PartitionVertex *vertices, long numvertices) {
- long i;
- PartitionVertex *v1,*v3;
- Vector2 vec1,vec3;
-
- v1 = v->previous;
- v3 = v->next;
-
- v->isConvex = IsConvex(v1->p,v->p,v3->p);
-
- vec1 = Normalize(v1->p - v->p);
- vec3 = Normalize(v3->p - v->p);
- v->angle = vec1.x*vec3.x + vec1.y*vec3.y;
-
- if(v->isConvex) {
- v->isEar = true;
- for(i=0;i<numvertices;i++) {
- if((vertices[i].p.x==v->p.x)&&(vertices[i].p.y==v->p.y)) continue;
- if((vertices[i].p.x==v1->p.x)&&(vertices[i].p.y==v1->p.y)) continue;
- if((vertices[i].p.x==v3->p.x)&&(vertices[i].p.y==v3->p.y)) continue;
- if(IsInside(v1->p,v->p,v3->p,vertices[i].p)) {
- v->isEar = false;
- break;
- }
- }
- } else {
- v->isEar = false;
- }
-}
-
-//triangulation by ear removal
-int TriangulatorPartition::Triangulate_EC(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles) {
- long numvertices;
- PartitionVertex *vertices;
- PartitionVertex *ear;
- TriangulatorPoly triangle;
- long i,j;
- bool earfound;
-
- if(poly->GetNumPoints() < 3) return 0;
- if(poly->GetNumPoints() == 3) {
- triangles->push_back(*poly);
- return 1;
- }
-
- numvertices = poly->GetNumPoints();
-
- vertices = new PartitionVertex[numvertices];
- for(i=0;i<numvertices;i++) {
- vertices[i].isActive = true;
- vertices[i].p = poly->GetPoint(i);
- if(i==(numvertices-1)) vertices[i].next=&(vertices[0]);
- else vertices[i].next=&(vertices[i+1]);
- if(i==0) vertices[i].previous = &(vertices[numvertices-1]);
- else vertices[i].previous = &(vertices[i-1]);
- }
- for(i=0;i<numvertices;i++) {
- UpdateVertex(&vertices[i],vertices,numvertices);
- }
-
- for(i=0;i<numvertices-3;i++) {
- earfound = false;
- //find the most extruded ear
- for(j=0;j<numvertices;j++) {
- if(!vertices[j].isActive) continue;
- if(!vertices[j].isEar) continue;
- if(!earfound) {
- earfound = true;
- ear = &(vertices[j]);
- } else {
- if(vertices[j].angle > ear->angle) {
- ear = &(vertices[j]);
- }
- }
- }
- if(!earfound) {
- delete [] vertices;
- return 0;
- }
-
- triangle.Triangle(ear->previous->p,ear->p,ear->next->p);
- triangles->push_back(triangle);
-
- ear->isActive = false;
- ear->previous->next = ear->next;
- ear->next->previous = ear->previous;
-
- if(i==numvertices-4) break;
-
- UpdateVertex(ear->previous,vertices,numvertices);
- UpdateVertex(ear->next,vertices,numvertices);
- }
- for(i=0;i<numvertices;i++) {
- if(vertices[i].isActive) {
- triangle.Triangle(vertices[i].previous->p,vertices[i].p,vertices[i].next->p);
- triangles->push_back(triangle);
- break;
- }
- }
-
- delete [] vertices;
-
- return 1;
-}
-
-int TriangulatorPartition::Triangulate_EC(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *triangles) {
- List<TriangulatorPoly> outpolys;
- List<TriangulatorPoly>::Element*iter;
-
- if(!RemoveHoles(inpolys,&outpolys)) return 0;
- for(iter=outpolys.front();iter;iter=iter->next()) {
- if(!Triangulate_EC(&(iter->get()),triangles)) return 0;
- }
- return 1;
-}
-
-int TriangulatorPartition::ConvexPartition_HM(TriangulatorPoly *poly, List<TriangulatorPoly> *parts) {
- List<TriangulatorPoly> triangles;
- List<TriangulatorPoly>::Element *iter1,*iter2;
- TriangulatorPoly *poly1,*poly2;
- TriangulatorPoly newpoly;
- Vector2 d1,d2,p1,p2,p3;
- long i11,i12,i21,i22,i13,i23,j,k;
- bool isdiagonal;
- long numreflex;
-
- //check if the poly is already convex
- numreflex = 0;
- for(i11=0;i11<poly->GetNumPoints();i11++) {
- if(i11==0) i12 = poly->GetNumPoints()-1;
- else i12=i11-1;
- if(i11==(poly->GetNumPoints()-1)) i13=0;
- else i13=i11+1;
- if(IsReflex(poly->GetPoint(i12),poly->GetPoint(i11),poly->GetPoint(i13))) {
- numreflex = 1;
- break;
- }
- }
- if(numreflex == 0) {
- parts->push_back(*poly);
- return 1;
- }
-
- if(!Triangulate_EC(poly,&triangles)) return 0;
-
- for(iter1 = triangles.front(); iter1 ; iter1=iter1->next()) {
- poly1 = &(iter1->get());
- for(i11=0;i11<poly1->GetNumPoints();i11++) {
- d1 = poly1->GetPoint(i11);
- i12 = (i11+1)%(poly1->GetNumPoints());
- d2 = poly1->GetPoint(i12);
-
- isdiagonal = false;
- for(iter2 = iter1; iter2 ; iter2=iter2->next()) {
- if(iter1 == iter2) continue;
- poly2 = &(iter2->get());
-
- for(i21=0;i21<poly2->GetNumPoints();i21++) {
- if((d2.x != poly2->GetPoint(i21).x)||(d2.y != poly2->GetPoint(i21).y)) continue;
- i22 = (i21+1)%(poly2->GetNumPoints());
- if((d1.x != poly2->GetPoint(i22).x)||(d1.y != poly2->GetPoint(i22).y)) continue;
- isdiagonal = true;
- break;
- }
- if(isdiagonal) break;
- }
-
- if(!isdiagonal) continue;
-
- p2 = poly1->GetPoint(i11);
- if(i11 == 0) i13 = poly1->GetNumPoints()-1;
- else i13 = i11-1;
- p1 = poly1->GetPoint(i13);
- if(i22 == (poly2->GetNumPoints()-1)) i23 = 0;
- else i23 = i22+1;
- p3 = poly2->GetPoint(i23);
-
- if(!IsConvex(p1,p2,p3)) continue;
-
- p2 = poly1->GetPoint(i12);
- if(i12 == (poly1->GetNumPoints()-1)) i13 = 0;
- else i13 = i12+1;
- p3 = poly1->GetPoint(i13);
- if(i21 == 0) i23 = poly2->GetNumPoints()-1;
- else i23 = i21-1;
- p1 = poly2->GetPoint(i23);
-
- if(!IsConvex(p1,p2,p3)) continue;
-
- newpoly.Init(poly1->GetNumPoints()+poly2->GetNumPoints()-2);
- k = 0;
- for(j=i12;j!=i11;j=(j+1)%(poly1->GetNumPoints())) {
- newpoly[k] = poly1->GetPoint(j);
- k++;
- }
- for(j=i22;j!=i21;j=(j+1)%(poly2->GetNumPoints())) {
- newpoly[k] = poly2->GetPoint(j);
- k++;
- }
-
- triangles.erase(iter2);
- iter1->get() = newpoly;
- poly1 = &(iter1->get());
- i11 = -1;
-
- continue;
- }
- }
-
- for(iter1 = triangles.front(); iter1 ; iter1=iter1->next()) {
- parts->push_back(iter1->get());
- }
-
- return 1;
-}
-
-int TriangulatorPartition::ConvexPartition_HM(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *parts) {
- List<TriangulatorPoly> outpolys;
- List<TriangulatorPoly>::Element* iter;
-
- if(!RemoveHoles(inpolys,&outpolys)) return 0;
- for(iter=outpolys.front();iter;iter=iter->next()) {
- if(!ConvexPartition_HM(&(iter->get()),parts)) return 0;
- }
- return 1;
-}
-
-//minimum-weight polygon triangulation by dynamic programming
-//O(n^3) time complexity
-//O(n^2) space complexity
-int TriangulatorPartition::Triangulate_OPT(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles) {
- long i,j,k,gap,n;
- DPState **dpstates;
- Vector2 p1,p2,p3,p4;
- long bestvertex;
- real_t weight,minweight,d1,d2;
- Diagonal diagonal,newdiagonal;
- List<Diagonal> diagonals;
- TriangulatorPoly triangle;
- int ret = 1;
-
- n = poly->GetNumPoints();
- dpstates = new DPState *[n];
- for(i=1;i<n;i++) {
- dpstates[i] = new DPState[i];
- }
-
- //init states and visibility
- for(i=0;i<(n-1);i++) {
- p1 = poly->GetPoint(i);
- for(j=i+1;j<n;j++) {
- dpstates[j][i].visible = true;
- dpstates[j][i].weight = 0;
- dpstates[j][i].bestvertex = -1;
- if(j!=(i+1)) {
- p2 = poly->GetPoint(j);
-
- //visibility check
- if(i==0) p3 = poly->GetPoint(n-1);
- else p3 = poly->GetPoint(i-1);
- if(i==(n-1)) p4 = poly->GetPoint(0);
- else p4 = poly->GetPoint(i+1);
- if(!InCone(p3,p1,p4,p2)) {
- dpstates[j][i].visible = false;
- continue;
- }
-
- if(j==0) p3 = poly->GetPoint(n-1);
- else p3 = poly->GetPoint(j-1);
- if(j==(n-1)) p4 = poly->GetPoint(0);
- else p4 = poly->GetPoint(j+1);
- if(!InCone(p3,p2,p4,p1)) {
- dpstates[j][i].visible = false;
- continue;
- }
-
- for(k=0;k<n;k++) {
- p3 = poly->GetPoint(k);
- if(k==(n-1)) p4 = poly->GetPoint(0);
- else p4 = poly->GetPoint(k+1);
- if(Intersects(p1,p2,p3,p4)) {
- dpstates[j][i].visible = false;
- break;
- }
- }
- }
- }
- }
- dpstates[n-1][0].visible = true;
- dpstates[n-1][0].weight = 0;
- dpstates[n-1][0].bestvertex = -1;
-
- for(gap = 2; gap<n; gap++) {
- for(i=0; i<(n-gap); i++) {
- j = i+gap;
- if(!dpstates[j][i].visible) continue;
- bestvertex = -1;
- for(k=(i+1);k<j;k++) {
- if(!dpstates[k][i].visible) continue;
- if(!dpstates[j][k].visible) continue;
-
- if(k<=(i+1)) d1=0;
- else d1 = Distance(poly->GetPoint(i),poly->GetPoint(k));
- if(j<=(k+1)) d2=0;
- else d2 = Distance(poly->GetPoint(k),poly->GetPoint(j));
-
- weight = dpstates[k][i].weight + dpstates[j][k].weight + d1 + d2;
-
- if((bestvertex == -1)||(weight<minweight)) {
- bestvertex = k;
- minweight = weight;
- }
- }
- if(bestvertex == -1) {
- for(i=1;i<n;i++) {
- delete [] dpstates[i];
- }
- delete [] dpstates;
-
- return 0;
- }
-
- dpstates[j][i].bestvertex = bestvertex;
- dpstates[j][i].weight = minweight;
- }
- }
-
- newdiagonal.index1 = 0;
- newdiagonal.index2 = n-1;
- diagonals.push_back(newdiagonal);
- while(!diagonals.empty()) {
- diagonal = (diagonals.front()->get());
- diagonals.pop_front();
- bestvertex = dpstates[diagonal.index2][diagonal.index1].bestvertex;
- if(bestvertex == -1) {
- ret = 0;
- break;
- }
- triangle.Triangle(poly->GetPoint(diagonal.index1),poly->GetPoint(bestvertex),poly->GetPoint(diagonal.index2));
- triangles->push_back(triangle);
- if(bestvertex > (diagonal.index1+1)) {
- newdiagonal.index1 = diagonal.index1;
- newdiagonal.index2 = bestvertex;
- diagonals.push_back(newdiagonal);
- }
- if(diagonal.index2 > (bestvertex+1)) {
- newdiagonal.index1 = bestvertex;
- newdiagonal.index2 = diagonal.index2;
- diagonals.push_back(newdiagonal);
- }
- }
-
- for(i=1;i<n;i++) {
- delete [] dpstates[i];
- }
- delete [] dpstates;
-
- return ret;
-}
-
-void TriangulatorPartition::UpdateState(long a, long b, long w, long i, long j, DPState2 **dpstates) {
- Diagonal newdiagonal;
- List<Diagonal> *pairs;
- long w2;
-
- w2 = dpstates[a][b].weight;
- if(w>w2) return;
-
- pairs = &(dpstates[a][b].pairs);
- newdiagonal.index1 = i;
- newdiagonal.index2 = j;
-
- if(w<w2) {
- pairs->clear();
- pairs->push_front(newdiagonal);
- dpstates[a][b].weight = w;
- } else {
- if((!pairs->empty())&&(i <= pairs->front()->get().index1)) return;
- while((!pairs->empty())&&(pairs->front()->get().index2 >= j)) pairs->pop_front();
- pairs->push_front(newdiagonal);
- }
-}
-
-void TriangulatorPartition::TypeA(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates) {
- List<Diagonal> *pairs;
- List<Diagonal>::Element *iter,*lastiter;
- long top;
- long w;
-
- if(!dpstates[i][j].visible) return;
- top = j;
- w = dpstates[i][j].weight;
- if(k-j > 1) {
- if (!dpstates[j][k].visible) return;
- w += dpstates[j][k].weight + 1;
- }
- if(j-i > 1) {
- pairs = &(dpstates[i][j].pairs);
- iter = NULL;
- lastiter = NULL;
- while(iter!=pairs->front()) {
- if (!iter)
- iter=pairs->back();
- else
- iter=iter->prev();
-
- if(!IsReflex(vertices[iter->get().index2].p,vertices[j].p,vertices[k].p)) lastiter = iter;
- else break;
- }
- if(lastiter == NULL) w++;
- else {
- if(IsReflex(vertices[k].p,vertices[i].p,vertices[lastiter->get().index1].p)) w++;
- else top = lastiter->get().index1;
- }
- }
- UpdateState(i,k,w,top,j,dpstates);
-}
-
-void TriangulatorPartition::TypeB(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates) {
- List<Diagonal> *pairs;
- List<Diagonal>::Element* iter,*lastiter;
- long top;
- long w;
-
- if(!dpstates[j][k].visible) return;
- top = j;
- w = dpstates[j][k].weight;
-
- if (j-i > 1) {
- if (!dpstates[i][j].visible) return;
- w += dpstates[i][j].weight + 1;
- }
- if (k-j > 1) {
- pairs = &(dpstates[j][k].pairs);
-
- iter = pairs->front();
- if((!pairs->empty())&&(!IsReflex(vertices[i].p,vertices[j].p,vertices[iter->get().index1].p))) {
- lastiter = iter;
- while(iter!=NULL) {
- if(!IsReflex(vertices[i].p,vertices[j].p,vertices[iter->get().index1].p)) {
- lastiter = iter;
- iter=iter->next();
- }
- else break;
- }
- if(IsReflex(vertices[lastiter->get().index2].p,vertices[k].p,vertices[i].p)) w++;
- else top = lastiter->get().index2;
- } else w++;
- }
- UpdateState(i,k,w,j,top,dpstates);
-}
-
-int TriangulatorPartition::ConvexPartition_OPT(TriangulatorPoly *poly, List<TriangulatorPoly> *parts) {
- Vector2 p1,p2,p3,p4;
- PartitionVertex *vertices;
- DPState2 **dpstates;
- long i,j,k,n,gap;
- List<Diagonal> diagonals,diagonals2;
- Diagonal diagonal,newdiagonal;
- List<Diagonal> *pairs,*pairs2;
- List<Diagonal>::Element* iter,*iter2;
- int ret;
- TriangulatorPoly newpoly;
- List<long> indices;
- List<long>::Element* iiter;
- bool ijreal,jkreal;
-
- n = poly->GetNumPoints();
- vertices = new PartitionVertex[n];
-
- dpstates = new DPState2 *[n];
- for(i=0;i<n;i++) {
- dpstates[i] = new DPState2[n];
- }
-
- //init vertex information
- for(i=0;i<n;i++) {
- vertices[i].p = poly->GetPoint(i);
- vertices[i].isActive = true;
- if(i==0) vertices[i].previous = &(vertices[n-1]);
- else vertices[i].previous = &(vertices[i-1]);
- if(i==(poly->GetNumPoints()-1)) vertices[i].next = &(vertices[0]);
- else vertices[i].next = &(vertices[i+1]);
- }
- for(i=1;i<n;i++) {
- UpdateVertexReflexity(&(vertices[i]));
- }
-
- //init states and visibility
- for(i=0;i<(n-1);i++) {
- p1 = poly->GetPoint(i);
- for(j=i+1;j<n;j++) {
- dpstates[i][j].visible = true;
- if(j==i+1) {
- dpstates[i][j].weight = 0;
- } else {
- dpstates[i][j].weight = 2147483647;
- }
- if(j!=(i+1)) {
- p2 = poly->GetPoint(j);
-
- //visibility check
- if(!InCone(&vertices[i],p2)) {
- dpstates[i][j].visible = false;
- continue;
- }
- if(!InCone(&vertices[j],p1)) {
- dpstates[i][j].visible = false;
- continue;
- }
-
- for(k=0;k<n;k++) {
- p3 = poly->GetPoint(k);
- if(k==(n-1)) p4 = poly->GetPoint(0);
- else p4 = poly->GetPoint(k+1);
- if(Intersects(p1,p2,p3,p4)) {
- dpstates[i][j].visible = false;
- break;
- }
- }
- }
- }
- }
- for(i=0;i<(n-2);i++) {
- j = i+2;
- if(dpstates[i][j].visible) {
- dpstates[i][j].weight = 0;
- newdiagonal.index1 = i+1;
- newdiagonal.index2 = i+1;
- dpstates[i][j].pairs.push_back(newdiagonal);
- }
- }
-
- dpstates[0][n-1].visible = true;
- vertices[0].isConvex = false; //by convention
-
- for(gap=3; gap<n; gap++) {
- for(i=0;i<n-gap;i++) {
- if(vertices[i].isConvex) continue;
- k = i+gap;
- if(dpstates[i][k].visible) {
- if(!vertices[k].isConvex) {
- for(j=i+1;j<k;j++) TypeA(i,j,k,vertices,dpstates);
- } else {
- for(j=i+1;j<(k-1);j++) {
- if(vertices[j].isConvex) continue;
- TypeA(i,j,k,vertices,dpstates);
- }
- TypeA(i,k-1,k,vertices,dpstates);
- }
- }
- }
- for(k=gap;k<n;k++) {
- if(vertices[k].isConvex) continue;
- i = k-gap;
- if((vertices[i].isConvex)&&(dpstates[i][k].visible)) {
- TypeB(i,i+1,k,vertices,dpstates);
- for(j=i+2;j<k;j++) {
- if(vertices[j].isConvex) continue;
- TypeB(i,j,k,vertices,dpstates);
- }
- }
- }
- }
-
-
- //recover solution
- ret = 1;
- newdiagonal.index1 = 0;
- newdiagonal.index2 = n-1;
- diagonals.push_front(newdiagonal);
- while(!diagonals.empty()) {
- diagonal = (diagonals.front()->get());
- diagonals.pop_front();
- if((diagonal.index2 - diagonal.index1) <=1) continue;
- pairs = &(dpstates[diagonal.index1][diagonal.index2].pairs);
- if(pairs->empty()) {
- ret = 0;
- break;
- }
- if(!vertices[diagonal.index1].isConvex) {
- iter = pairs->back();
-
- j = iter->get().index2;
- newdiagonal.index1 = j;
- newdiagonal.index2 = diagonal.index2;
- diagonals.push_front(newdiagonal);
- if((j - diagonal.index1)>1) {
- if(iter->get().index1 != iter->get().index2) {
- pairs2 = &(dpstates[diagonal.index1][j].pairs);
- while(1) {
- if(pairs2->empty()) {
- ret = 0;
- break;
- }
- iter2 = pairs2->back();
-
- if(iter->get().index1 != iter2->get().index1) pairs2->pop_back();
- else break;
- }
- if(ret == 0) break;
- }
- newdiagonal.index1 = diagonal.index1;
- newdiagonal.index2 = j;
- diagonals.push_front(newdiagonal);
- }
- } else {
- iter = pairs->front();
- j = iter->get().index1;
- newdiagonal.index1 = diagonal.index1;
- newdiagonal.index2 = j;
- diagonals.push_front(newdiagonal);
- if((diagonal.index2 - j) > 1) {
- if(iter->get().index1 != iter->get().index2) {
- pairs2 = &(dpstates[j][diagonal.index2].pairs);
- while(1) {
- if(pairs2->empty()) {
- ret = 0;
- break;
- }
- iter2 = pairs2->front();
- if(iter->get().index2 != iter2->get().index2) pairs2->pop_front();
- else break;
- }
- if(ret == 0) break;
- }
- newdiagonal.index1 = j;
- newdiagonal.index2 = diagonal.index2;
- diagonals.push_front(newdiagonal);
- }
- }
- }
-
- if(ret == 0) {
- for(i=0;i<n;i++) {
- delete [] dpstates[i];
- }
- delete [] dpstates;
- delete [] vertices;
-
- return ret;
- }
-
- newdiagonal.index1 = 0;
- newdiagonal.index2 = n-1;
- diagonals.push_front(newdiagonal);
- while(!diagonals.empty()) {
- diagonal = (diagonals.front())->get();
- diagonals.pop_front();
- if((diagonal.index2 - diagonal.index1) <= 1) continue;
-
- indices.clear();
- diagonals2.clear();
- indices.push_back(diagonal.index1);
- indices.push_back(diagonal.index2);
- diagonals2.push_front(diagonal);
-
- while(!diagonals2.empty()) {
- diagonal = (diagonals2.front()->get());
- diagonals2.pop_front();
- if((diagonal.index2 - diagonal.index1) <= 1) continue;
- ijreal = true;
- jkreal = true;
- pairs = &(dpstates[diagonal.index1][diagonal.index2].pairs);
- if(!vertices[diagonal.index1].isConvex) {
- iter = pairs->back();
- j = iter->get().index2;
- if(iter->get().index1 != iter->get().index2) ijreal = false;
- } else {
- iter = pairs->front();
- j = iter->get().index1;
- if(iter->get().index1 != iter->get().index2) jkreal = false;
- }
-
- newdiagonal.index1 = diagonal.index1;
- newdiagonal.index2 = j;
- if(ijreal) {
- diagonals.push_back(newdiagonal);
- } else {
- diagonals2.push_back(newdiagonal);
- }
-
- newdiagonal.index1 = j;
- newdiagonal.index2 = diagonal.index2;
- if(jkreal) {
- diagonals.push_back(newdiagonal);
- } else {
- diagonals2.push_back(newdiagonal);
- }
-
- indices.push_back(j);
- }
-
- indices.sort();
- newpoly.Init((long)indices.size());
- k=0;
- for(iiter = indices.front();iiter;iiter=iiter->next()) {
- newpoly[k] = vertices[iiter->get()].p;
- k++;
- }
- parts->push_back(newpoly);
- }
-
- for(i=0;i<n;i++) {
- delete [] dpstates[i];
- }
- delete [] dpstates;
- delete [] vertices;
-
- return ret;
-}
-
-//triangulates a set of polygons by first partitioning them into monotone polygons
-//O(n*log(n)) time complexity, O(n) space complexity
-//the algorithm used here is outlined in the book
-//"Computational Geometry: Algorithms and Applications"
-//by Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars
-int TriangulatorPartition::MonotonePartition(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *monotonePolys) {
- List<TriangulatorPoly>::Element *iter;
- MonotoneVertex *vertices;
- long i,numvertices,vindex,vindex2,newnumvertices,maxnumvertices;
- long polystartindex, polyendindex;
- TriangulatorPoly *poly;
- MonotoneVertex *v,*v2,*vprev,*vnext;
- ScanLineEdge newedge;
- bool error = false;
-
- numvertices = 0;
- for(iter = inpolys->front(); iter ; iter=iter->next()) {
- numvertices += iter->get().GetNumPoints();
- }
-
- maxnumvertices = numvertices*3;
- vertices = new MonotoneVertex[maxnumvertices];
- newnumvertices = numvertices;
-
- polystartindex = 0;
- for(iter = inpolys->front(); iter ; iter=iter->next()) {
- poly = &(iter->get());
- polyendindex = polystartindex + poly->GetNumPoints()-1;
- for(i=0;i<poly->GetNumPoints();i++) {
- vertices[i+polystartindex].p = poly->GetPoint(i);
- if(i==0) vertices[i+polystartindex].previous = polyendindex;
- else vertices[i+polystartindex].previous = i+polystartindex-1;
- if(i==(poly->GetNumPoints()-1)) vertices[i+polystartindex].next = polystartindex;
- else vertices[i+polystartindex].next = i+polystartindex+1;
- }
- polystartindex = polyendindex+1;
- }
-
- //construct the priority queue
- long *priority = new long [numvertices];
- for(i=0;i<numvertices;i++) priority[i] = i;
- SortArray<long,VertexSorter> sorter;
- sorter.compare.vertices=vertices;
- sorter.sort(priority,numvertices);
-
- //determine vertex types
- char *vertextypes = new char[maxnumvertices];
- for(i=0;i<numvertices;i++) {
- v = &(vertices[i]);
- vprev = &(vertices[v->previous]);
- vnext = &(vertices[v->next]);
-
- if(Below(vprev->p,v->p)&&Below(vnext->p,v->p)) {
- if(IsConvex(vnext->p,vprev->p,v->p)) {
- vertextypes[i] = TRIANGULATOR_VERTEXTYPE_START;
- } else {
- vertextypes[i] = TRIANGULATOR_VERTEXTYPE_SPLIT;
- }
- } else if(Below(v->p,vprev->p)&&Below(v->p,vnext->p)) {
- if(IsConvex(vnext->p,vprev->p,v->p))
- {
- vertextypes[i] = TRIANGULATOR_VERTEXTYPE_END;
- } else {
- vertextypes[i] = TRIANGULATOR_VERTEXTYPE_MERGE;
- }
- } else {
- vertextypes[i] = TRIANGULATOR_VERTEXTYPE_REGULAR;
- }
- }
-
- //helpers
- long *helpers = new long[maxnumvertices];
-
- //binary search tree that holds edges intersecting the scanline
- //note that while set doesn't actually have to be implemented as a tree
- //complexity requirements for operations are the same as for the balanced binary search tree
- Set<ScanLineEdge> edgeTree;
- //store iterators to the edge tree elements
- //this makes deleting existing edges much faster
- Set<ScanLineEdge>::Element **edgeTreeIterators,*edgeIter;
- edgeTreeIterators = new Set<ScanLineEdge>::Element*[maxnumvertices];
- //Pair<Set<ScanLineEdge>::Element*,bool> edgeTreeRet;
- for(i = 0; i<numvertices; i++) edgeTreeIterators[i] = NULL;
-
- //for each vertex
- for(i=0;i<numvertices;i++) {
- vindex = priority[i];
- v = &(vertices[vindex]);
- vindex2 = vindex;
- v2 = v;
-
- //depending on the vertex type, do the appropriate action
- //comments in the following sections are copied from "Computational Geometry: Algorithms and Applications"
- switch(vertextypes[vindex]) {
- case TRIANGULATOR_VERTEXTYPE_START:
- //Insert ei in T and set helper(ei) to vi.
- newedge.p1 = v->p;
- newedge.p2 = vertices[v->next].p;
- newedge.index = vindex;
- edgeTreeIterators[vindex] = edgeTree.insert(newedge);
- helpers[vindex] = vindex;
- break;
-
- case TRIANGULATOR_VERTEXTYPE_END:
- //if helper(ei-1) is a merge vertex
- if(vertextypes[helpers[v->previous]]==TRIANGULATOR_VERTEXTYPE_MERGE) {
- //Insert the diagonal connecting vi to helper(ei-1) in D.
- AddDiagonal(vertices,&newnumvertices,vindex,helpers[v->previous],
- vertextypes, edgeTreeIterators, &edgeTree, helpers);
- }
- //Delete ei-1 from T
- edgeTree.erase(edgeTreeIterators[v->previous]);
- break;
-
- case TRIANGULATOR_VERTEXTYPE_SPLIT:
- //Search in T to find the edge e j directly left of vi.
- newedge.p1 = v->p;
- newedge.p2 = v->p;
- edgeIter = edgeTree.lower_bound(newedge);
- if(edgeIter == edgeTree.front()) {
- error = true;
- break;
- }
- edgeIter=edgeIter->prev();
- //Insert the diagonal connecting vi to helper(ej) in D.
- AddDiagonal(vertices,&newnumvertices,vindex,helpers[edgeIter->get().index],
- vertextypes, edgeTreeIterators, &edgeTree, helpers);
- vindex2 = newnumvertices-2;
- v2 = &(vertices[vindex2]);
- //helper(e j)�vi
- helpers[edgeIter->get().index] = vindex;
- //Insert ei in T and set helper(ei) to vi.
- newedge.p1 = v2->p;
- newedge.p2 = vertices[v2->next].p;
- newedge.index = vindex2;
-
- edgeTreeIterators[vindex2] = edgeTree.insert(newedge);
- helpers[vindex2] = vindex2;
- break;
-
- case TRIANGULATOR_VERTEXTYPE_MERGE:
- //if helper(ei-1) is a merge vertex
- if(vertextypes[helpers[v->previous]]==TRIANGULATOR_VERTEXTYPE_MERGE) {
- //Insert the diagonal connecting vi to helper(ei-1) in D.
- AddDiagonal(vertices,&newnumvertices,vindex,helpers[v->previous],
- vertextypes, edgeTreeIterators, &edgeTree, helpers);
- vindex2 = newnumvertices-2;
- v2 = &(vertices[vindex2]);
- }
- //Delete ei-1 from T.
- edgeTree.erase(edgeTreeIterators[v->previous]);
- //Search in T to find the edge e j directly left of vi.
- newedge.p1 = v->p;
- newedge.p2 = v->p;
- edgeIter = edgeTree.lower_bound(newedge);
- if(edgeIter == edgeTree.front()) {
- error = true;
- break;
- }
- edgeIter=edgeIter->prev();
- //if helper(ej) is a merge vertex
- if(vertextypes[helpers[edgeIter->get().index]]==TRIANGULATOR_VERTEXTYPE_MERGE) {
- //Insert the diagonal connecting vi to helper(e j) in D.
- AddDiagonal(vertices,&newnumvertices,vindex2,helpers[edgeIter->get().index],
- vertextypes, edgeTreeIterators, &edgeTree, helpers);
- }
- //helper(e j)�vi
- helpers[edgeIter->get().index] = vindex2;
- break;
-
- case TRIANGULATOR_VERTEXTYPE_REGULAR:
- //if the interior of P lies to the right of vi
- if(Below(v->p,vertices[v->previous].p)) {
- //if helper(ei-1) is a merge vertex
- if(vertextypes[helpers[v->previous]]==TRIANGULATOR_VERTEXTYPE_MERGE) {
- //Insert the diagonal connecting vi to helper(ei-1) in D.
- AddDiagonal(vertices,&newnumvertices,vindex,helpers[v->previous],
- vertextypes, edgeTreeIterators, &edgeTree, helpers);
- vindex2 = newnumvertices-2;
- v2 = &(vertices[vindex2]);
- }
- //Delete ei-1 from T.
- edgeTree.erase(edgeTreeIterators[v->previous]);
- //Insert ei in T and set helper(ei) to vi.
- newedge.p1 = v2->p;
- newedge.p2 = vertices[v2->next].p;
- newedge.index = vindex2;
- edgeTreeIterators[vindex2] = edgeTree.insert(newedge);
- helpers[vindex2] = vindex;
- } else {
- //Search in T to find the edge ej directly left of vi.
- newedge.p1 = v->p;
- newedge.p2 = v->p;
- edgeIter = edgeTree.lower_bound(newedge);
- if(edgeIter == edgeTree.front()) {
- error = true;
- break;
- }
- edgeIter=edgeIter->prev();
- //if helper(ej) is a merge vertex
- if(vertextypes[helpers[edgeIter->get().index]]==TRIANGULATOR_VERTEXTYPE_MERGE) {
- //Insert the diagonal connecting vi to helper(e j) in D.
- AddDiagonal(vertices,&newnumvertices,vindex,helpers[edgeIter->get().index],
- vertextypes, edgeTreeIterators, &edgeTree, helpers);
- }
- //helper(e j)�vi
- helpers[edgeIter->get().index] = vindex;
- }
- break;
- }
-
- if(error) break;
- }
-
- char *used = new char[newnumvertices];
- memset(used,0,newnumvertices*sizeof(char));
-
- if(!error) {
- //return result
- long size;
- TriangulatorPoly mpoly;
- for(i=0;i<newnumvertices;i++) {
- if(used[i]) continue;
- v = &(vertices[i]);
- vnext = &(vertices[v->next]);
- size = 1;
- while(vnext!=v) {
- vnext = &(vertices[vnext->next]);
- size++;
- }
- mpoly.Init(size);
- v = &(vertices[i]);
- mpoly[0] = v->p;
- vnext = &(vertices[v->next]);
- size = 1;
- used[i] = 1;
- used[v->next] = 1;
- while(vnext!=v) {
- mpoly[size] = vnext->p;
- used[vnext->next] = 1;
- vnext = &(vertices[vnext->next]);
- size++;
- }
- monotonePolys->push_back(mpoly);
- }
- }
-
- //cleanup
- delete [] vertices;
- delete [] priority;
- delete [] vertextypes;
- delete [] edgeTreeIterators;
- delete [] helpers;
- delete [] used;
-
- if(error) {
- return 0;
- } else {
- return 1;
- }
-}
-
-//adds a diagonal to the doubly-connected list of vertices
-void TriangulatorPartition::AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2,
- char *vertextypes, Set<ScanLineEdge>::Element **edgeTreeIterators,
- Set<ScanLineEdge> *edgeTree, long *helpers)
-{
- long newindex1,newindex2;
-
- newindex1 = *numvertices;
- (*numvertices)++;
- newindex2 = *numvertices;
- (*numvertices)++;
-
- vertices[newindex1].p = vertices[index1].p;
- vertices[newindex2].p = vertices[index2].p;
-
- vertices[newindex2].next = vertices[index2].next;
- vertices[newindex1].next = vertices[index1].next;
-
- vertices[vertices[index2].next].previous = newindex2;
- vertices[vertices[index1].next].previous = newindex1;
-
- vertices[index1].next = newindex2;
- vertices[newindex2].previous = index1;
-
- vertices[index2].next = newindex1;
- vertices[newindex1].previous = index2;
-
- //update all relevant structures
- vertextypes[newindex1] = vertextypes[index1];
- edgeTreeIterators[newindex1] = edgeTreeIterators[index1];
- helpers[newindex1] = helpers[index1];
- if(edgeTreeIterators[newindex1] != NULL)
- edgeTreeIterators[newindex1]->get().index = newindex1;
- vertextypes[newindex2] = vertextypes[index2];
- edgeTreeIterators[newindex2] = edgeTreeIterators[index2];
- helpers[newindex2] = helpers[index2];
- if(edgeTreeIterators[newindex2] != NULL)
- edgeTreeIterators[newindex2]->get().index = newindex2;
-}
-
-bool TriangulatorPartition::Below(Vector2 &p1, Vector2 &p2) {
- if(p1.y < p2.y) return true;
- else if(p1.y == p2.y) {
- if(p1.x < p2.x) return true;
- }
- return false;
-}
-
-
-
-
-
-//sorts in the falling order of y values, if y is equal, x is used instead
-bool TriangulatorPartition::VertexSorter::operator() (long index1, long index2) const {
- if(vertices[index1].p.y > vertices[index2].p.y) return true;
- else if(vertices[index1].p.y == vertices[index2].p.y) {
- if(vertices[index1].p.x > vertices[index2].p.x) return true;
- }
- return false;
-}
-
-bool TriangulatorPartition::ScanLineEdge::IsConvex(const Vector2& p1, const Vector2& p2, const Vector2& p3) const {
- real_t tmp;
- tmp = (p3.y-p1.y)*(p2.x-p1.x)-(p3.x-p1.x)*(p2.y-p1.y);
- if(tmp>0) return 1;
- else return 0;
-}
-
-bool TriangulatorPartition::ScanLineEdge::operator < (const ScanLineEdge & other) const {
- if(other.p1.y == other.p2.y) {
- if(p1.y == p2.y) {
- if(p1.y < other.p1.y) return true;
- else return false;
- }
- if(IsConvex(p1,p2,other.p1)) return true;
- else return false;
- } else if(p1.y == p2.y) {
- if(IsConvex(other.p1,other.p2,p1)) return false;
- else return true;
- } else if(p1.y < other.p1.y) {
- if(IsConvex(other.p1,other.p2,p1)) return false;
- else return true;
- } else {
- if(IsConvex(p1,p2,other.p1)) return true;
- else return false;
- }
-}
-
-//triangulates monotone polygon
-//O(n) time, O(n) space complexity
-int TriangulatorPartition::TriangulateMonotone(TriangulatorPoly *inPoly, List<TriangulatorPoly> *triangles) {
- long i,i2,j,topindex,bottomindex,leftindex,rightindex,vindex;
- Vector2 *points;
- long numpoints;
- TriangulatorPoly triangle;
-
- numpoints = inPoly->GetNumPoints();
- points = inPoly->GetPoints();
-
- //trivial calses
- if(numpoints < 3) return 0;
- if(numpoints == 3) {
- triangles->push_back(*inPoly);
- }
-
- topindex = 0; bottomindex=0;
- for(i=1;i<numpoints;i++) {
- if(Below(points[i],points[bottomindex])) bottomindex = i;
- if(Below(points[topindex],points[i])) topindex = i;
- }
-
- //check if the poly is really monotone
- i = topindex;
- while(i!=bottomindex) {
- i2 = i+1; if(i2>=numpoints) i2 = 0;
- if(!Below(points[i2],points[i])) return 0;
- i = i2;
- }
- i = bottomindex;
- while(i!=topindex) {
- i2 = i+1; if(i2>=numpoints) i2 = 0;
- if(!Below(points[i],points[i2])) return 0;
- i = i2;
- }
-
- char *vertextypes = new char[numpoints];
- long *priority = new long[numpoints];
-
- //merge left and right vertex chains
- priority[0] = topindex;
- vertextypes[topindex] = 0;
- leftindex = topindex+1; if(leftindex>=numpoints) leftindex = 0;
- rightindex = topindex-1; if(rightindex<0) rightindex = numpoints-1;
- for(i=1;i<(numpoints-1);i++) {
- if(leftindex==bottomindex) {
- priority[i] = rightindex;
- rightindex--; if(rightindex<0) rightindex = numpoints-1;
- vertextypes[priority[i]] = -1;
- } else if(rightindex==bottomindex) {
- priority[i] = leftindex;
- leftindex++; if(leftindex>=numpoints) leftindex = 0;
- vertextypes[priority[i]] = 1;
- } else {
- if(Below(points[leftindex],points[rightindex])) {
- priority[i] = rightindex;
- rightindex--; if(rightindex<0) rightindex = numpoints-1;
- vertextypes[priority[i]] = -1;
- } else {
- priority[i] = leftindex;
- leftindex++; if(leftindex>=numpoints) leftindex = 0;
- vertextypes[priority[i]] = 1;
- }
- }
- }
- priority[i] = bottomindex;
- vertextypes[bottomindex] = 0;
-
- long *stack = new long[numpoints];
- long stackptr = 0;
-
- stack[0] = priority[0];
- stack[1] = priority[1];
- stackptr = 2;
-
- //for each vertex from top to bottom trim as many triangles as possible
- for(i=2;i<(numpoints-1);i++) {
- vindex = priority[i];
- if(vertextypes[vindex]!=vertextypes[stack[stackptr-1]]) {
- for(j=0;j<(stackptr-1);j++) {
- if(vertextypes[vindex]==1) {
- triangle.Triangle(points[stack[j+1]],points[stack[j]],points[vindex]);
- } else {
- triangle.Triangle(points[stack[j]],points[stack[j+1]],points[vindex]);
- }
- triangles->push_back(triangle);
- }
- stack[0] = priority[i-1];
- stack[1] = priority[i];
- stackptr = 2;
- } else {
- stackptr--;
- while(stackptr>0) {
- if(vertextypes[vindex]==1) {
- if(IsConvex(points[vindex],points[stack[stackptr-1]],points[stack[stackptr]])) {
- triangle.Triangle(points[vindex],points[stack[stackptr-1]],points[stack[stackptr]]);
- triangles->push_back(triangle);
- stackptr--;
- } else {
- break;
- }
- } else {
- if(IsConvex(points[vindex],points[stack[stackptr]],points[stack[stackptr-1]])) {
- triangle.Triangle(points[vindex],points[stack[stackptr]],points[stack[stackptr-1]]);
- triangles->push_back(triangle);
- stackptr--;
- } else {
- break;
- }
- }
- }
- stackptr++;
- stack[stackptr] = vindex;
- stackptr++;
- }
- }
- vindex = priority[i];
- for(j=0;j<(stackptr-1);j++) {
- if(vertextypes[stack[j+1]]==1) {
- triangle.Triangle(points[stack[j]],points[stack[j+1]],points[vindex]);
- } else {
- triangle.Triangle(points[stack[j+1]],points[stack[j]],points[vindex]);
- }
- triangles->push_back(triangle);
- }
-
- delete [] priority;
- delete [] vertextypes;
- delete [] stack;
-
- return 1;
-}
-
-int TriangulatorPartition::Triangulate_MONO(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *triangles) {
- List<TriangulatorPoly> monotone;
- List<TriangulatorPoly>::Element* iter;
-
- if(!MonotonePartition(inpolys,&monotone)) return 0;
- for(iter = monotone.front(); iter;iter=iter->next()) {
- if(!TriangulateMonotone(&(iter->get()),triangles)) return 0;
- }
- return 1;
-}
-
-int TriangulatorPartition::Triangulate_MONO(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles) {
- List<TriangulatorPoly> polys;
- polys.push_back(*poly);
-
- return Triangulate_MONO(&polys, triangles);
-}
diff --git a/thirdparty/misc/triangulator.h b/thirdparty/misc/triangulator.h
deleted file mode 100644
index c85792fd50..0000000000
--- a/thirdparty/misc/triangulator.h
+++ /dev/null
@@ -1,306 +0,0 @@
-//Copyright (C) 2011 by Ivan Fratric
-//
-//Permission is hereby granted, free of charge, to any person obtaining a copy
-//of this software and associated documentation files (the "Software"), to deal
-//in the Software without restriction, including without limitation the rights
-//to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
-//copies of the Software, and to permit persons to whom the Software is
-//furnished to do so, subject to the following conditions:
-//
-//The above copyright notice and this permission notice shall be included in
-//all copies or substantial portions of the Software.
-//
-//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
-//IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
-//FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
-//AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
-//LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
-//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
-//THE SOFTWARE.
-
-#ifndef TRIANGULATOR_H
-#define TRIANGULATOR_H
-
-#include "core/list.h"
-#include "core/math/vector2.h"
-#include "core/set.h"
-
-//2D point structure
-
-#define TRIANGULATOR_CCW 1
-#define TRIANGULATOR_CW -1
-//Polygon implemented as an array of points with a 'hole' flag
-class TriangulatorPoly {
-protected:
-
-
-
- Vector2 *points;
- long numpoints;
- bool hole;
-
-public:
-
- //constructors/destructors
- TriangulatorPoly();
- ~TriangulatorPoly();
-
- TriangulatorPoly(const TriangulatorPoly &src);
- TriangulatorPoly& operator=(const TriangulatorPoly &src);
-
- //getters and setters
- long GetNumPoints() {
- return numpoints;
- }
-
- bool IsHole() {
- return hole;
- }
-
- void SetHole(bool hole) {
- this->hole = hole;
- }
-
- Vector2 &GetPoint(long i) {
- return points[i];
- }
-
- Vector2 *GetPoints() {
- return points;
- }
-
- Vector2& operator[] (int i) {
- return points[i];
- }
-
- //clears the polygon points
- void Clear();
-
- //inits the polygon with numpoints vertices
- void Init(long numpoints);
-
- //creates a triangle with points p1,p2,p3
- void Triangle(Vector2 &p1, Vector2 &p2, Vector2 &p3);
-
- //inverts the orfer of vertices
- void Invert();
-
- //returns the orientation of the polygon
- //possible values:
- // Triangulator_CCW : polygon vertices are in counter-clockwise order
- // Triangulator_CW : polygon vertices are in clockwise order
- // 0 : the polygon has no (measurable) area
- int GetOrientation();
-
- //sets the polygon orientation
- //orientation can be
- // Triangulator_CCW : sets vertices in counter-clockwise order
- // Triangulator_CW : sets vertices in clockwise order
- void SetOrientation(int orientation);
-};
-
-class TriangulatorPartition {
-protected:
- struct PartitionVertex {
- bool isActive;
- bool isConvex;
- bool isEar;
-
- Vector2 p;
- real_t angle;
- PartitionVertex *previous;
- PartitionVertex *next;
- };
-
- struct MonotoneVertex {
- Vector2 p;
- long previous;
- long next;
- };
-
- struct VertexSorter{
- mutable MonotoneVertex *vertices;
- bool operator() (long index1, long index2) const;
- };
-
- struct Diagonal {
- long index1;
- long index2;
- };
-
- //dynamic programming state for minimum-weight triangulation
- struct DPState {
- bool visible;
- real_t weight;
- long bestvertex;
- };
-
- //dynamic programming state for convex partitioning
- struct DPState2 {
- bool visible;
- long weight;
- List<Diagonal> pairs;
- };
-
- //edge that intersects the scanline
- struct ScanLineEdge {
- mutable long index;
- Vector2 p1;
- Vector2 p2;
-
- //determines if the edge is to the left of another edge
- bool operator< (const ScanLineEdge & other) const;
-
- bool IsConvex(const Vector2& p1, const Vector2& p2, const Vector2& p3) const;
- };
-
- //standard helper functions
- bool IsConvex(Vector2& p1, Vector2& p2, Vector2& p3);
- bool IsReflex(Vector2& p1, Vector2& p2, Vector2& p3);
- bool IsInside(Vector2& p1, Vector2& p2, Vector2& p3, Vector2 &p);
-
- bool InCone(Vector2 &p1, Vector2 &p2, Vector2 &p3, Vector2 &p);
- bool InCone(PartitionVertex *v, Vector2 &p);
-
- int Intersects(Vector2 &p11, Vector2 &p12, Vector2 &p21, Vector2 &p22);
-
- Vector2 Normalize(const Vector2 &p);
- real_t Distance(const Vector2 &p1, const Vector2 &p2);
-
- //helper functions for Triangulate_EC
- void UpdateVertexReflexity(PartitionVertex *v);
- void UpdateVertex(PartitionVertex *v,PartitionVertex *vertices, long numvertices);
-
- //helper functions for ConvexPartition_OPT
- void UpdateState(long a, long b, long w, long i, long j, DPState2 **dpstates);
- void TypeA(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates);
- void TypeB(long i, long j, long k, PartitionVertex *vertices, DPState2 **dpstates);
-
- //helper functions for MonotonePartition
- bool Below(Vector2 &p1, Vector2 &p2);
- void AddDiagonal(MonotoneVertex *vertices, long *numvertices, long index1, long index2,
- char *vertextypes, Set<ScanLineEdge>::Element **edgeTreeIterators,
- Set<ScanLineEdge> *edgeTree, long *helpers);
-
- //triangulates a monotone polygon, used in Triangulate_MONO
- int TriangulateMonotone(TriangulatorPoly *inPoly, List<TriangulatorPoly> *triangles);
-
-public:
-
- //simple heuristic procedure for removing holes from a list of polygons
- //works by creating a diagonal from the rightmost hole vertex to some visible vertex
- //time complexity: O(h*(n^2)), h is the number of holes, n is the number of vertices
- //space complexity: O(n)
- //params:
- // inpolys : a list of polygons that can contain holes
- // vertices of all non-hole polys have to be in counter-clockwise order
- // vertices of all hole polys have to be in clockwise order
- // outpolys : a list of polygons without holes
- //returns 1 on success, 0 on failure
- int RemoveHoles(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *outpolys);
-
- //triangulates a polygon by ear clipping
- //time complexity O(n^2), n is the number of vertices
- //space complexity: O(n)
- //params:
- // poly : an input polygon to be triangulated
- // vertices have to be in counter-clockwise order
- // triangles : a list of triangles (result)
- //returns 1 on success, 0 on failure
- int Triangulate_EC(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles);
-
- //triangulates a list of polygons that may contain holes by ear clipping algorithm
- //first calls RemoveHoles to get rid of the holes, and then Triangulate_EC for each resulting polygon
- //time complexity: O(h*(n^2)), h is the number of holes, n is the number of vertices
- //space complexity: O(n)
- //params:
- // inpolys : a list of polygons to be triangulated (can contain holes)
- // vertices of all non-hole polys have to be in counter-clockwise order
- // vertices of all hole polys have to be in clockwise order
- // triangles : a list of triangles (result)
- //returns 1 on success, 0 on failure
- int Triangulate_EC(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *triangles);
-
- //creates an optimal polygon triangulation in terms of minimal edge length
- //time complexity: O(n^3), n is the number of vertices
- //space complexity: O(n^2)
- //params:
- // poly : an input polygon to be triangulated
- // vertices have to be in counter-clockwise order
- // triangles : a list of triangles (result)
- //returns 1 on success, 0 on failure
- int Triangulate_OPT(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles);
-
- //triangulates a polygons by firstly partitioning it into monotone polygons
- //time complexity: O(n*log(n)), n is the number of vertices
- //space complexity: O(n)
- //params:
- // poly : an input polygon to be triangulated
- // vertices have to be in counter-clockwise order
- // triangles : a list of triangles (result)
- //returns 1 on success, 0 on failure
- int Triangulate_MONO(TriangulatorPoly *poly, List<TriangulatorPoly> *triangles);
-
- //triangulates a list of polygons by firstly partitioning them into monotone polygons
- //time complexity: O(n*log(n)), n is the number of vertices
- //space complexity: O(n)
- //params:
- // inpolys : a list of polygons to be triangulated (can contain holes)
- // vertices of all non-hole polys have to be in counter-clockwise order
- // vertices of all hole polys have to be in clockwise order
- // triangles : a list of triangles (result)
- //returns 1 on success, 0 on failure
- int Triangulate_MONO(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *triangles);
-
- //creates a monotone partition of a list of polygons that can contain holes
- //time complexity: O(n*log(n)), n is the number of vertices
- //space complexity: O(n)
- //params:
- // inpolys : a list of polygons to be triangulated (can contain holes)
- // vertices of all non-hole polys have to be in counter-clockwise order
- // vertices of all hole polys have to be in clockwise order
- // monotonePolys : a list of monotone polygons (result)
- //returns 1 on success, 0 on failure
- int MonotonePartition(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *monotonePolys);
-
- //partitions a polygon into convex polygons by using Hertel-Mehlhorn algorithm
- //the algorithm gives at most four times the number of parts as the optimal algorithm
- //however, in practice it works much better than that and often gives optimal partition
- //uses triangulation obtained by ear clipping as intermediate result
- //time complexity O(n^2), n is the number of vertices
- //space complexity: O(n)
- //params:
- // poly : an input polygon to be partitioned
- // vertices have to be in counter-clockwise order
- // parts : resulting list of convex polygons
- //returns 1 on success, 0 on failure
- int ConvexPartition_HM(TriangulatorPoly *poly, List<TriangulatorPoly> *parts);
-
- //partitions a list of polygons into convex parts by using Hertel-Mehlhorn algorithm
- //the algorithm gives at most four times the number of parts as the optimal algorithm
- //however, in practice it works much better than that and often gives optimal partition
- //uses triangulation obtained by ear clipping as intermediate result
- //time complexity O(n^2), n is the number of vertices
- //space complexity: O(n)
- //params:
- // inpolys : an input list of polygons to be partitioned
- // vertices of all non-hole polys have to be in counter-clockwise order
- // vertices of all hole polys have to be in clockwise order
- // parts : resulting list of convex polygons
- //returns 1 on success, 0 on failure
- int ConvexPartition_HM(List<TriangulatorPoly> *inpolys, List<TriangulatorPoly> *parts);
-
- //optimal convex partitioning (in terms of number of resulting convex polygons)
- //using the Keil-Snoeyink algorithm
- //M. Keil, J. Snoeyink, "On the time bound for convex decomposition of simple polygons", 1998
- //time complexity O(n^3), n is the number of vertices
- //space complexity: O(n^3)
- // poly : an input polygon to be partitioned
- // vertices have to be in counter-clockwise order
- // parts : resulting list of convex polygons
- //returns 1 on success, 0 on failure
- int ConvexPartition_OPT(TriangulatorPoly *poly, List<TriangulatorPoly> *parts);
-};
-
-
-#endif
generated by cgit v1.2.3 (git 2.25.1) at 2025-02-22 01:15:48 +0000