niko
273 lines
7.2 KiB
C#
273 lines
7.2 KiB
C#
using System;
|
|
using System.Collections.Generic;
|
|
using TriangleNet.Geometry;
|
|
|
|
namespace TriangleNet.Tools
|
|
{
|
|
// Token: 0x02000017 RID: 23
|
|
internal class QuadNode
|
|
{
|
|
// Token: 0x060000BF RID: 191 RVA: 0x0001322D File Offset: 0x0001142D
|
|
public QuadNode(BoundingBox box, QuadTree tree)
|
|
: this(box, tree, false)
|
|
{
|
|
}
|
|
|
|
// Token: 0x060000C0 RID: 192 RVA: 0x00013238 File Offset: 0x00011438
|
|
public QuadNode(BoundingBox box, QuadTree tree, bool init)
|
|
{
|
|
this.tree = tree;
|
|
this.bounds = new BoundingBox(box.MinX, box.MinY, box.MaxX, box.MaxY);
|
|
this.pivot = new Point((box.MinX + box.MaxX) / 2.0, (box.MinY + box.MaxY) / 2.0);
|
|
this.bitRegions = 0;
|
|
this.regions = new QuadNode[4];
|
|
this.triangles = new List<int>();
|
|
if (init)
|
|
{
|
|
int num = tree.triangles.Length;
|
|
this.triangles.Capacity = num;
|
|
for (int i = 0; i < num; i++)
|
|
{
|
|
this.triangles.Add(i);
|
|
}
|
|
}
|
|
}
|
|
|
|
// Token: 0x060000C1 RID: 193 RVA: 0x000132FC File Offset: 0x000114FC
|
|
public List<int> FindTriangles(Point searchPoint)
|
|
{
|
|
int num = this.FindRegion(searchPoint);
|
|
if (this.regions[num] == null)
|
|
{
|
|
return this.triangles;
|
|
}
|
|
return this.regions[num].FindTriangles(searchPoint);
|
|
}
|
|
|
|
// Token: 0x060000C2 RID: 194 RVA: 0x00013330 File Offset: 0x00011530
|
|
public void CreateSubRegion(int currentDepth)
|
|
{
|
|
BoundingBox boundingBox = new BoundingBox(this.bounds.MinX, this.bounds.MinY, this.pivot.X, this.pivot.Y);
|
|
this.regions[0] = new QuadNode(boundingBox, this.tree);
|
|
boundingBox = new BoundingBox(this.pivot.X, this.bounds.MinY, this.bounds.MaxX, this.pivot.Y);
|
|
this.regions[1] = new QuadNode(boundingBox, this.tree);
|
|
boundingBox = new BoundingBox(this.bounds.MinX, this.pivot.Y, this.pivot.X, this.bounds.MaxY);
|
|
this.regions[2] = new QuadNode(boundingBox, this.tree);
|
|
boundingBox = new BoundingBox(this.pivot.X, this.pivot.Y, this.bounds.MaxX, this.bounds.MaxY);
|
|
this.regions[3] = new QuadNode(boundingBox, this.tree);
|
|
Point[] array = new Point[3];
|
|
foreach (int num in this.triangles)
|
|
{
|
|
ITriangle triangle = this.tree.triangles[num];
|
|
array[0] = triangle.GetVertex(0);
|
|
array[1] = triangle.GetVertex(1);
|
|
array[2] = triangle.GetVertex(2);
|
|
this.AddTriangleToRegion(array, num);
|
|
}
|
|
for (int i = 0; i < 4; i++)
|
|
{
|
|
if (this.regions[i].triangles.Count > this.tree.sizeBound && currentDepth < this.tree.maxDepth)
|
|
{
|
|
this.regions[i].CreateSubRegion(currentDepth + 1);
|
|
}
|
|
}
|
|
}
|
|
|
|
// Token: 0x060000C3 RID: 195 RVA: 0x00013524 File Offset: 0x00011724
|
|
private void AddTriangleToRegion(Point[] triangle, int index)
|
|
{
|
|
this.bitRegions = 0;
|
|
if (QuadTree.IsPointInTriangle(this.pivot, triangle[0], triangle[1], triangle[2]))
|
|
{
|
|
this.AddToRegion(index, 0);
|
|
this.AddToRegion(index, 1);
|
|
this.AddToRegion(index, 2);
|
|
this.AddToRegion(index, 3);
|
|
return;
|
|
}
|
|
this.FindTriangleIntersections(triangle, index);
|
|
if (this.bitRegions == 0)
|
|
{
|
|
int num = this.FindRegion(triangle[0]);
|
|
this.regions[num].triangles.Add(index);
|
|
}
|
|
}
|
|
|
|
// Token: 0x060000C4 RID: 196 RVA: 0x0001359C File Offset: 0x0001179C
|
|
private void FindTriangleIntersections(Point[] triangle, int index)
|
|
{
|
|
int num = 2;
|
|
int i = 0;
|
|
while (i < 3)
|
|
{
|
|
double num2 = triangle[i].X - triangle[num].X;
|
|
double num3 = triangle[i].Y - triangle[num].Y;
|
|
if (num2 != 0.0)
|
|
{
|
|
this.FindIntersectionsWithX(num2, num3, triangle, index, num);
|
|
}
|
|
if (num3 != 0.0)
|
|
{
|
|
this.FindIntersectionsWithY(num2, num3, triangle, index, num);
|
|
}
|
|
num = i++;
|
|
}
|
|
}
|
|
|
|
// Token: 0x060000C5 RID: 197 RVA: 0x0001360C File Offset: 0x0001180C
|
|
private void FindIntersectionsWithX(double dx, double dy, Point[] triangle, int index, int k)
|
|
{
|
|
double num = (this.pivot.X - triangle[k].X) / dx;
|
|
if (num < 1.000001 && num > -1E-06)
|
|
{
|
|
double num2 = triangle[k].Y + num * dy;
|
|
if (num2 < this.pivot.Y && num2 >= this.bounds.MinY)
|
|
{
|
|
this.AddToRegion(index, 0);
|
|
this.AddToRegion(index, 1);
|
|
}
|
|
else if (num2 <= this.bounds.MaxY)
|
|
{
|
|
this.AddToRegion(index, 2);
|
|
this.AddToRegion(index, 3);
|
|
}
|
|
}
|
|
num = (this.bounds.MinX - triangle[k].X) / dx;
|
|
if (num < 1.000001 && num > -1E-06)
|
|
{
|
|
double num3 = triangle[k].Y + num * dy;
|
|
if (num3 < this.pivot.Y && num3 >= this.bounds.MinY)
|
|
{
|
|
this.AddToRegion(index, 0);
|
|
}
|
|
else if (num3 <= this.bounds.MaxY)
|
|
{
|
|
this.AddToRegion(index, 2);
|
|
}
|
|
}
|
|
num = (this.bounds.MaxX - triangle[k].X) / dx;
|
|
if (num < 1.000001 && num > -1E-06)
|
|
{
|
|
double num4 = triangle[k].Y + num * dy;
|
|
if (num4 < this.pivot.Y && num4 >= this.bounds.MinY)
|
|
{
|
|
this.AddToRegion(index, 1);
|
|
return;
|
|
}
|
|
if (num4 <= this.bounds.MaxY)
|
|
{
|
|
this.AddToRegion(index, 3);
|
|
}
|
|
}
|
|
}
|
|
|
|
// Token: 0x060000C6 RID: 198 RVA: 0x000137A0 File Offset: 0x000119A0
|
|
private void FindIntersectionsWithY(double dx, double dy, Point[] triangle, int index, int k)
|
|
{
|
|
double num = (this.pivot.Y - triangle[k].Y) / dy;
|
|
if (num < 1.000001 && num > -1E-06)
|
|
{
|
|
double num2 = triangle[k].X + num * dx;
|
|
if (num2 > this.pivot.X && num2 <= this.bounds.MaxX)
|
|
{
|
|
this.AddToRegion(index, 1);
|
|
this.AddToRegion(index, 3);
|
|
}
|
|
else if (num2 >= this.bounds.MinX)
|
|
{
|
|
this.AddToRegion(index, 0);
|
|
this.AddToRegion(index, 2);
|
|
}
|
|
}
|
|
num = (this.bounds.MinY - triangle[k].Y) / dy;
|
|
if (num < 1.000001 && num > -1E-06)
|
|
{
|
|
double num2 = triangle[k].X + num * dx;
|
|
if (num2 > this.pivot.X && num2 <= this.bounds.MaxX)
|
|
{
|
|
this.AddToRegion(index, 1);
|
|
}
|
|
else if (num2 >= this.bounds.MinX)
|
|
{
|
|
this.AddToRegion(index, 0);
|
|
}
|
|
}
|
|
num = (this.bounds.MaxY - triangle[k].Y) / dy;
|
|
if (num < 1.000001 && num > -1E-06)
|
|
{
|
|
double num2 = triangle[k].X + num * dx;
|
|
if (num2 > this.pivot.X && num2 <= this.bounds.MaxX)
|
|
{
|
|
this.AddToRegion(index, 3);
|
|
return;
|
|
}
|
|
if (num2 >= this.bounds.MinX)
|
|
{
|
|
this.AddToRegion(index, 2);
|
|
}
|
|
}
|
|
}
|
|
|
|
// Token: 0x060000C7 RID: 199 RVA: 0x00013934 File Offset: 0x00011B34
|
|
private int FindRegion(Point point)
|
|
{
|
|
int num = 2;
|
|
if (point.Y < this.pivot.Y)
|
|
{
|
|
num = 0;
|
|
}
|
|
if (point.X > this.pivot.X)
|
|
{
|
|
num++;
|
|
}
|
|
return num;
|
|
}
|
|
|
|
// Token: 0x060000C8 RID: 200 RVA: 0x00013970 File Offset: 0x00011B70
|
|
private void AddToRegion(int index, int region)
|
|
{
|
|
if ((this.bitRegions & QuadNode.BITVECTOR[region]) == 0)
|
|
{
|
|
this.regions[region].triangles.Add(index);
|
|
this.bitRegions |= QuadNode.BITVECTOR[region];
|
|
}
|
|
}
|
|
|
|
// Token: 0x04000097 RID: 151
|
|
private const int SW = 0;
|
|
|
|
// Token: 0x04000098 RID: 152
|
|
private const int SE = 1;
|
|
|
|
// Token: 0x04000099 RID: 153
|
|
private const int NW = 2;
|
|
|
|
// Token: 0x0400009A RID: 154
|
|
private const int NE = 3;
|
|
|
|
// Token: 0x0400009B RID: 155
|
|
private const double EPS = 1E-06;
|
|
|
|
// Token: 0x0400009C RID: 156
|
|
private static readonly byte[] BITVECTOR = new byte[] { 1, 2, 4, 8 };
|
|
|
|
// Token: 0x0400009D RID: 157
|
|
private BoundingBox bounds;
|
|
|
|
// Token: 0x0400009E RID: 158
|
|
private Point pivot;
|
|
|
|
// Token: 0x0400009F RID: 159
|
|
private QuadTree tree;
|
|
|
|
// Token: 0x040000A0 RID: 160
|
|
private QuadNode[] regions;
|
|
|
|
// Token: 0x040000A1 RID: 161
|
|
private List<int> triangles;
|
|
|
|
// Token: 0x040000A2 RID: 162
|
|
private byte bitRegions;
|
|
}
|
|
}
|