Uranium-and-Waffles/Dec2017-Script-Dump
3
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
Files
main
Dec2017-Script-Dump/Triangle/Algorithm/Dwyer.cs
T
niko e720b98cd1 scripts
2026-06-04 11:42:34 +02:00

570 lines
15 KiB
C#
Raw Permalink Blame History

using System;
using TriangleNet.Data;
using TriangleNet.Log;
namespace TriangleNet.Algorithm
{
// Token: 0x0200003C RID: 60
internal class Dwyer
{
// Token: 0x06000221 RID: 545 RVA: 0x00019578 File Offset: 0x00017778
private void VertexSort(int left, int right)
{
int num = left;
int num2 = right;
if (right - left + 1 < 32)
{
for (int i = left + 1; i <= right; i++)
{
Vertex vertex = this.sortarray[i];
int num3 = i - 1;
while (num3 >= left && (this.sortarray[num3].x > vertex.x || (this.sortarray[num3].x == vertex.x && this.sortarray[num3].y > vertex.y)))
{
this.sortarray[num3 + 1] = this.sortarray[num3];
num3--;
}
this.sortarray[num3 + 1] = vertex;
}
return;
}
int num4 = Dwyer.rand.Next(left, right);
double x = this.sortarray[num4].x;
double y = this.sortarray[num4].y;
left--;
right++;
while (left < right)
{
do
{
left++;
}
while (left <= right && (this.sortarray[left].x < x || (this.sortarray[left].x == x && this.sortarray[left].y < y)));
do
{
right--;
}
while (left <= right && (this.sortarray[right].x > x || (this.sortarray[right].x == x && this.sortarray[right].y > y)));
if (left < right)
{
Vertex vertex2 = this.sortarray[left];
this.sortarray[left] = this.sortarray[right];
this.sortarray[right] = vertex2;
}
}
if (left > num)
{
this.VertexSort(num, left);
}
if (num2 > right + 1)
{
this.VertexSort(right + 1, num2);
}
}
// Token: 0x06000222 RID: 546 RVA: 0x0001972C File Offset: 0x0001792C
private void VertexMedian(int left, int right, int median, int axis)
{
int num = right - left + 1;
int num2 = left;
int num3 = right;
if (num == 2)
{
if (this.sortarray[left][axis] > this.sortarray[right][axis] || (this.sortarray[left][axis] == this.sortarray[right][axis] && this.sortarray[left][1 - axis] > this.sortarray[right][1 - axis]))
{
Vertex vertex = this.sortarray[right];
this.sortarray[right] = this.sortarray[left];
this.sortarray[left] = vertex;
}
return;
}
int num4 = Dwyer.rand.Next(left, right);
double num5 = this.sortarray[num4][axis];
double num6 = this.sortarray[num4][1 - axis];
left--;
right++;
while (left < right)
{
do
{
left++;
}
while (left <= right && (this.sortarray[left][axis] < num5 || (this.sortarray[left][axis] == num5 && this.sortarray[left][1 - axis] < num6)));
do
{
right--;
}
while (left <= right && (this.sortarray[right][axis] > num5 || (this.sortarray[right][axis] == num5 && this.sortarray[right][1 - axis] > num6)));
if (left < right)
{
Vertex vertex = this.sortarray[left];
this.sortarray[left] = this.sortarray[right];
this.sortarray[right] = vertex;
}
}
if (left > median)
{
this.VertexMedian(num2, left - 1, median, axis);
}
if (right < median - 1)
{
this.VertexMedian(right + 1, num3, median, axis);
}
}
// Token: 0x06000223 RID: 547 RVA: 0x000198E8 File Offset: 0x00017AE8
private void AlternateAxes(int left, int right, int axis)
{
int num = right - left + 1;
int num2 = num >> 1;
if (num <= 3)
{
axis = 0;
}
this.VertexMedian(left, right, left + num2, axis);
if (num - num2 >= 2)
{
if (num2 >= 2)
{
this.AlternateAxes(left, left + num2 - 1, 1 - axis);
}
this.AlternateAxes(left + num2, right, 1 - axis);
}
}
// Token: 0x06000224 RID: 548 RVA: 0x00019938 File Offset: 0x00017B38
private void MergeHulls(ref Otri farleft, ref Otri innerleft, ref Otri innerright, ref Otri farright, int axis)
{
Otri otri = default(Otri);
Otri otri2 = default(Otri);
Otri otri3 = default(Otri);
Otri otri4 = default(Otri);
Otri otri5 = default(Otri);
Otri otri6 = default(Otri);
Otri otri7 = default(Otri);
Otri otri8 = default(Otri);
Vertex vertex = innerleft.Dest();
Vertex vertex2 = innerleft.Apex();
Vertex vertex3 = innerright.Org();
Vertex vertex4 = innerright.Apex();
Vertex vertex5;
Vertex vertex7;
if (this.useDwyer && axis == 1)
{
vertex5 = farleft.Org();
Vertex vertex6 = farleft.Apex();
vertex7 = farright.Dest();
Vertex vertex8 = farright.Apex();
while (vertex6.y < vertex5.y)
{
farleft.LnextSelf();
farleft.SymSelf();
vertex5 = vertex6;
vertex6 = farleft.Apex();
}
innerleft.Sym(ref otri7);
Vertex vertex9 = otri7.Apex();
while (vertex9.y > vertex.y)
{
otri7.Lnext(ref innerleft);
vertex2 = vertex;
vertex = vertex9;
innerleft.Sym(ref otri7);
vertex9 = otri7.Apex();
}
while (vertex4.y < vertex3.y)
{
innerright.LnextSelf();
innerright.SymSelf();
vertex3 = vertex4;
vertex4 = innerright.Apex();
}
farright.Sym(ref otri7);
vertex9 = otri7.Apex();
while (vertex9.y > vertex7.y)
{
otri7.Lnext(ref farright);
vertex7 = vertex9;
farright.Sym(ref otri7);
vertex9 = otri7.Apex();
}
}
bool flag;
do
{
flag = false;
if (Primitives.CounterClockwise(vertex, vertex2, vertex3) > 0.0)
{
innerleft.LprevSelf();
innerleft.SymSelf();
vertex = vertex2;
vertex2 = innerleft.Apex();
flag = true;
}
if (Primitives.CounterClockwise(vertex4, vertex3, vertex) > 0.0)
{
innerright.LnextSelf();
innerright.SymSelf();
vertex3 = vertex4;
vertex4 = innerright.Apex();
flag = true;
}
}
while (flag);
innerleft.Sym(ref otri);
innerright.Sym(ref otri2);
this.mesh.MakeTriangle(ref otri8);
otri8.Bond(ref innerleft);
otri8.LnextSelf();
otri8.Bond(ref innerright);
otri8.LnextSelf();
otri8.SetOrg(vertex3);
otri8.SetDest(vertex);
vertex5 = farleft.Org();
if (vertex == vertex5)
{
otri8.Lnext(ref farleft);
}
vertex7 = farright.Dest();
if (vertex3 == vertex7)
{
otri8.Lprev(ref farright);
}
Vertex vertex10 = vertex;
Vertex vertex11 = vertex3;
Vertex vertex12 = otri.Apex();
Vertex vertex13 = otri2.Apex();
for (;;)
{
bool flag2 = Primitives.CounterClockwise(vertex12, vertex10, vertex11) <= 0.0;
bool flag3 = Primitives.CounterClockwise(vertex13, vertex10, vertex11) <= 0.0;
if (flag2 && flag3)
{
break;
}
if (!flag2)
{
otri.Lprev(ref otri3);
otri3.SymSelf();
Vertex vertex14 = otri3.Apex();
if (vertex14 != null)
{
bool flag4 = Primitives.InCircle(vertex10, vertex11, vertex12, vertex14) > 0.0;
while (flag4)
{
otri3.LnextSelf();
otri3.Sym(ref otri5);
otri3.LnextSelf();
otri3.Sym(ref otri4);
otri3.Bond(ref otri5);
otri.Bond(ref otri4);
otri.LnextSelf();
otri.Sym(ref otri6);
otri3.LprevSelf();
otri3.Bond(ref otri6);
otri.SetOrg(vertex10);
otri.SetDest(null);
otri.SetApex(vertex14);
otri3.SetOrg(null);
otri3.SetDest(vertex12);
otri3.SetApex(vertex14);
vertex12 = vertex14;
otri4.Copy(ref otri3);
vertex14 = otri3.Apex();
flag4 = vertex14 != null && Primitives.InCircle(vertex10, vertex11, vertex12, vertex14) > 0.0;
}
}
}
if (!flag3)
{
otri2.Lnext(ref otri3);
otri3.SymSelf();
Vertex vertex14 = otri3.Apex();
if (vertex14 != null)
{
bool flag4 = Primitives.InCircle(vertex10, vertex11, vertex13, vertex14) > 0.0;
while (flag4)
{
otri3.LprevSelf();
otri3.Sym(ref otri5);
otri3.LprevSelf();
otri3.Sym(ref otri4);
otri3.Bond(ref otri5);
otri2.Bond(ref otri4);
otri2.LprevSelf();
otri2.Sym(ref otri6);
otri3.LnextSelf();
otri3.Bond(ref otri6);
otri2.SetOrg(null);
otri2.SetDest(vertex11);
otri2.SetApex(vertex14);
otri3.SetOrg(vertex13);
otri3.SetDest(null);
otri3.SetApex(vertex14);
vertex13 = vertex14;
otri4.Copy(ref otri3);
vertex14 = otri3.Apex();
flag4 = vertex14 != null && Primitives.InCircle(vertex10, vertex11, vertex13, vertex14) > 0.0;
}
}
}
if (flag2 || (!flag3 && Primitives.InCircle(vertex12, vertex10, vertex11, vertex13) > 0.0))
{
otri8.Bond(ref otri2);
otri2.Lprev(ref otri8);
otri8.SetDest(vertex10);
vertex11 = vertex13;
otri8.Sym(ref otri2);
vertex13 = otri2.Apex();
}
else
{
otri8.Bond(ref otri);
otri.Lnext(ref otri8);
otri8.SetOrg(vertex11);
vertex10 = vertex12;
otri8.Sym(ref otri);
vertex12 = otri.Apex();
}
}
this.mesh.MakeTriangle(ref otri3);
otri3.SetOrg(vertex10);
otri3.SetDest(vertex11);
otri3.Bond(ref otri8);
otri3.LnextSelf();
otri3.Bond(ref otri2);
otri3.LnextSelf();
otri3.Bond(ref otri);
if (this.useDwyer && axis == 1)
{
vertex5 = farleft.Org();
Vertex vertex6 = farleft.Apex();
vertex7 = farright.Dest();
Vertex vertex8 = farright.Apex();
farleft.Sym(ref otri7);
Vertex vertex9 = otri7.Apex();
while (vertex9.x < vertex5.x)
{
otri7.Lprev(ref farleft);
vertex5 = vertex9;
farleft.Sym(ref otri7);
vertex9 = otri7.Apex();
}
while (vertex8.x > vertex7.x)
{
farright.LprevSelf();
farright.SymSelf();
vertex7 = vertex8;
vertex8 = farright.Apex();
}
}
}
// Token: 0x06000225 RID: 549 RVA: 0x00019FAC File Offset: 0x000181AC
private void DivconqRecurse(int left, int right, int axis, ref Otri farleft, ref Otri farright)
{
Otri otri = default(Otri);
Otri otri2 = default(Otri);
Otri otri3 = default(Otri);
Otri otri4 = default(Otri);
Otri otri5 = default(Otri);
Otri otri6 = default(Otri);
int num = right - left + 1;
if (num == 2)
{
this.mesh.MakeTriangle(ref farleft);
farleft.SetOrg(this.sortarray[left]);
farleft.SetDest(this.sortarray[left + 1]);
this.mesh.MakeTriangle(ref farright);
farright.SetOrg(this.sortarray[left + 1]);
farright.SetDest(this.sortarray[left]);
farleft.Bond(ref farright);
farleft.LprevSelf();
farright.LnextSelf();
farleft.Bond(ref farright);
farleft.LprevSelf();
farright.LnextSelf();
farleft.Bond(ref farright);
farright.Lprev(ref farleft);
return;
}
if (num != 3)
{
int num2 = num >> 1;
this.DivconqRecurse(left, left + num2 - 1, 1 - axis, ref farleft, ref otri5);
this.DivconqRecurse(left + num2, right, 1 - axis, ref otri6, ref farright);
this.MergeHulls(ref farleft, ref otri5, ref otri6, ref farright, axis);
return;
}
this.mesh.MakeTriangle(ref otri);
this.mesh.MakeTriangle(ref otri2);
this.mesh.MakeTriangle(ref otri3);
this.mesh.MakeTriangle(ref otri4);
double num3 = Primitives.CounterClockwise(this.sortarray[left], this.sortarray[left + 1], this.sortarray[left + 2]);
if (num3 == 0.0)
{
otri.SetOrg(this.sortarray[left]);
otri.SetDest(this.sortarray[left + 1]);
otri2.SetOrg(this.sortarray[left + 1]);
otri2.SetDest(this.sortarray[left]);
otri3.SetOrg(this.sortarray[left + 2]);
otri3.SetDest(this.sortarray[left + 1]);
otri4.SetOrg(this.sortarray[left + 1]);
otri4.SetDest(this.sortarray[left + 2]);
otri.Bond(ref otri2);
otri3.Bond(ref otri4);
otri.LnextSelf();
otri2.LprevSelf();
otri3.LnextSelf();
otri4.LprevSelf();
otri.Bond(ref otri4);
otri2.Bond(ref otri3);
otri.LnextSelf();
otri2.LprevSelf();
otri3.LnextSelf();
otri4.LprevSelf();
otri.Bond(ref otri2);
otri3.Bond(ref otri4);
otri2.Copy(ref farleft);
otri3.Copy(ref farright);
return;
}
otri.SetOrg(this.sortarray[left]);
otri2.SetDest(this.sortarray[left]);
otri4.SetOrg(this.sortarray[left]);
if (num3 > 0.0)
{
otri.SetDest(this.sortarray[left + 1]);
otri2.SetOrg(this.sortarray[left + 1]);
otri3.SetDest(this.sortarray[left + 1]);
otri.SetApex(this.sortarray[left + 2]);
otri3.SetOrg(this.sortarray[left + 2]);
otri4.SetDest(this.sortarray[left + 2]);
}
else
{
otri.SetDest(this.sortarray[left + 2]);
otri2.SetOrg(this.sortarray[left + 2]);
otri3.SetDest(this.sortarray[left + 2]);
otri.SetApex(this.sortarray[left + 1]);
otri3.SetOrg(this.sortarray[left + 1]);
otri4.SetDest(this.sortarray[left + 1]);
}
otri.Bond(ref otri2);
otri.LnextSelf();
otri.Bond(ref otri3);
otri.LnextSelf();
otri.Bond(ref otri4);
otri2.LprevSelf();
otri3.LnextSelf();
otri2.Bond(ref otri3);
otri2.LprevSelf();
otri4.LprevSelf();
otri2.Bond(ref otri4);
otri3.LnextSelf();
otri4.LprevSelf();
otri3.Bond(ref otri4);
otri2.Copy(ref farleft);
if (num3 > 0.0)
{
otri3.Copy(ref farright);
return;
}
farleft.Lnext(ref farright);
}
// Token: 0x06000226 RID: 550 RVA: 0x0001A3E4 File Offset: 0x000185E4
private int RemoveGhosts(ref Otri startghost)
{
Otri otri = default(Otri);
Otri otri2 = default(Otri);
Otri otri3 = default(Otri);
bool flag = !this.mesh.behavior.Poly;
startghost.Lprev(ref otri);
otri.SymSelf();
Mesh.dummytri.neighbors[0] = otri;
startghost.Copy(ref otri2);
int num = 0;
do
{
num++;
otri2.Lnext(ref otri3);
otri2.LprevSelf();
otri2.SymSelf();
if (flag && otri2.triangle != Mesh.dummytri)
{
Vertex vertex = otri2.Org();
if (vertex.mark == 0)
{
vertex.mark = 1;
}
}
otri2.Dissolve();
otri3.Sym(ref otri2);
this.mesh.TriangleDealloc(otri3.triangle);
}
while (!otri2.Equal(startghost));
return num;
}
// Token: 0x06000227 RID: 551 RVA: 0x0001A4C0 File Offset: 0x000186C0
public int Triangulate(Mesh m)
{
Otri otri = default(Otri);
Otri otri2 = default(Otri);
this.mesh = m;
this.sortarray = new Vertex[m.invertices];
int num = 0;
foreach (Vertex vertex in m.vertices.Values)
{
this.sortarray[num++] = vertex;
}
this.VertexSort(0, m.invertices - 1);
num = 0;
for (int i = 1; i < m.invertices; i++)
{
if (this.sortarray[num].x == this.sortarray[i].x && this.sortarray[num].y == this.sortarray[i].y)
{
if (Behavior.Verbose)
{
SimpleLog.Instance.Warning(string.Format("A duplicate vertex appeared and was ignored (ID {0}).", this.sortarray[i].hash), "DivConquer.DivconqDelaunay()");
}
this.sortarray[i].type = VertexType.UndeadVertex;
m.undeads++;
}
else
{
num++;
this.sortarray[num] = this.sortarray[i];
}
}
num++;
if (this.useDwyer)
{
int num2 = num >> 1;
if (num - num2 >= 2)
{
if (num2 >= 2)
{
this.AlternateAxes(0, num2 - 1, 1);
}
this.AlternateAxes(num2, num - 1, 1);
}
}
this.DivconqRecurse(0, num - 1, 0, ref otri, ref otri2);
return this.RemoveGhosts(ref otri);
}
// Token: 0x0400012C RID: 300
private static Random rand = new Random(DateTime.Now.Millisecond);
// Token: 0x0400012D RID: 301
private bool useDwyer = true;
// Token: 0x0400012E RID: 302
private Vertex[] sortarray;
// Token: 0x0400012F RID: 303
private Mesh mesh;
}
}
Reference in New Issue View Git Blame Copy Permalink