niko
300 lines
7.2 KiB
C#
300 lines
7.2 KiB
C#
using System;
|
|
using TriangleNet.Log;
|
|
|
|
namespace TriangleNet.Tools
|
|
{
|
|
// Token: 0x02000014 RID: 20
|
|
public class CuthillMcKee
|
|
{
|
|
// Token: 0x060000AE RID: 174 RVA: 0x00012A2C File Offset: 0x00010C2C
|
|
public int[] Renumber(Mesh mesh)
|
|
{
|
|
this.node_num = mesh.vertices.Count;
|
|
mesh.Renumber(NodeNumbering.Linear);
|
|
this.matrix = new AdjacencyMatrix(mesh);
|
|
int num = this.matrix.Bandwidth();
|
|
int[] array = this.GenerateRcm();
|
|
int[] array2 = this.PermInverse(this.node_num, array);
|
|
int num2 = this.PermBandwidth(array, array2);
|
|
if (Behavior.Verbose)
|
|
{
|
|
SimpleLog.Instance.Info(string.Format("Reverse Cuthill-McKee (Bandwidth: {0} > {1})", num, num2));
|
|
}
|
|
return array2;
|
|
}
|
|
|
|
// Token: 0x060000AF RID: 175 RVA: 0x00012AB0 File Offset: 0x00010CB0
|
|
private int PermBandwidth(int[] perm, int[] perm_inv)
|
|
{
|
|
int[] adjacencyRow = this.matrix.AdjacencyRow;
|
|
int[] adjacency = this.matrix.Adjacency;
|
|
int num = 0;
|
|
int num2 = 0;
|
|
for (int i = 0; i < this.node_num; i++)
|
|
{
|
|
for (int j = adjacencyRow[perm[i]]; j <= adjacencyRow[perm[i] + 1] - 1; j++)
|
|
{
|
|
int num3 = perm_inv[adjacency[j - 1]];
|
|
num = Math.Max(num, i - num3);
|
|
num2 = Math.Max(num2, num3 - i);
|
|
}
|
|
}
|
|
return num + 1 + num2;
|
|
}
|
|
|
|
// Token: 0x060000B0 RID: 176 RVA: 0x00012B30 File Offset: 0x00010D30
|
|
private int[] GenerateRcm()
|
|
{
|
|
int[] array = new int[this.node_num];
|
|
int num = 0;
|
|
int num2 = 0;
|
|
int[] array2 = new int[this.node_num + 1];
|
|
int[] array3 = new int[this.node_num];
|
|
for (int i = 0; i < this.node_num; i++)
|
|
{
|
|
array3[i] = 1;
|
|
}
|
|
int num3 = 1;
|
|
for (int i = 0; i < this.node_num; i++)
|
|
{
|
|
if (array3[i] != 0)
|
|
{
|
|
int num4 = i;
|
|
this.FindRoot(ref num4, array3, ref num2, array2, array, num3 - 1);
|
|
this.Rcm(num4, array3, array, num3 - 1, ref num);
|
|
num3 += num;
|
|
if (this.node_num < num3)
|
|
{
|
|
return array;
|
|
}
|
|
}
|
|
}
|
|
return array;
|
|
}
|
|
|
|
// Token: 0x060000B1 RID: 177 RVA: 0x00012BD0 File Offset: 0x00010DD0
|
|
private void Rcm(int root, int[] mask, int[] perm, int offset, ref int iccsze)
|
|
{
|
|
int[] adjacencyRow = this.matrix.AdjacencyRow;
|
|
int[] adjacency = this.matrix.Adjacency;
|
|
int[] array = new int[this.node_num];
|
|
this.Degree(root, mask, array, ref iccsze, perm, offset);
|
|
mask[root] = 0;
|
|
if (iccsze <= 1)
|
|
{
|
|
return;
|
|
}
|
|
int i = 0;
|
|
int num = 1;
|
|
while (i < num)
|
|
{
|
|
int num2 = i + 1;
|
|
i = num;
|
|
for (int j = num2; j <= i; j++)
|
|
{
|
|
int num3 = perm[offset + j - 1];
|
|
int num4 = adjacencyRow[num3];
|
|
int num5 = adjacencyRow[num3 + 1] - 1;
|
|
int k = num + 1;
|
|
for (int l = num4; l <= num5; l++)
|
|
{
|
|
int num6 = adjacency[l - 1];
|
|
if (mask[num6] != 0)
|
|
{
|
|
num++;
|
|
mask[num6] = 0;
|
|
perm[offset + num - 1] = num6;
|
|
}
|
|
}
|
|
if (num > k)
|
|
{
|
|
int m = k;
|
|
while (m < num)
|
|
{
|
|
int num7 = m;
|
|
m++;
|
|
int num6 = perm[offset + m - 1];
|
|
while (k < num7)
|
|
{
|
|
int num8 = perm[offset + num7 - 1];
|
|
if (array[num8 - 1] <= array[num6 - 1])
|
|
{
|
|
break;
|
|
}
|
|
perm[offset + num7] = num8;
|
|
num7--;
|
|
}
|
|
perm[offset + num7] = num6;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
this.ReverseVector(perm, offset, iccsze);
|
|
}
|
|
|
|
// Token: 0x060000B2 RID: 178 RVA: 0x00012D0C File Offset: 0x00010F0C
|
|
private void FindRoot(ref int root, int[] mask, ref int level_num, int[] level_row, int[] level, int offset)
|
|
{
|
|
int[] adjacencyRow = this.matrix.AdjacencyRow;
|
|
int[] adjacency = this.matrix.Adjacency;
|
|
int num = 0;
|
|
this.GetLevelSet(ref root, mask, ref level_num, level_row, level, offset);
|
|
int num2 = level_row[level_num] - 1;
|
|
if (level_num == 1 || level_num == num2)
|
|
{
|
|
return;
|
|
}
|
|
do
|
|
{
|
|
int num3 = num2;
|
|
int num4 = level_row[level_num - 1];
|
|
root = level[offset + num4 - 1];
|
|
if (num4 < num2)
|
|
{
|
|
for (int i = num4; i <= num2; i++)
|
|
{
|
|
int num5 = level[offset + i - 1];
|
|
int num6 = 0;
|
|
int num7 = adjacencyRow[num5 - 1];
|
|
int num8 = adjacencyRow[num5] - 1;
|
|
for (int j = num7; j <= num8; j++)
|
|
{
|
|
int num9 = adjacency[j - 1];
|
|
if (mask[num9] > 0)
|
|
{
|
|
num6++;
|
|
}
|
|
}
|
|
if (num6 < num3)
|
|
{
|
|
root = num5;
|
|
num3 = num6;
|
|
}
|
|
}
|
|
}
|
|
this.GetLevelSet(ref root, mask, ref num, level_row, level, offset);
|
|
if (num <= level_num)
|
|
{
|
|
break;
|
|
}
|
|
level_num = num;
|
|
}
|
|
while (num2 > level_num);
|
|
}
|
|
|
|
// Token: 0x060000B3 RID: 179 RVA: 0x00012DF8 File Offset: 0x00010FF8
|
|
private void GetLevelSet(ref int root, int[] mask, ref int level_num, int[] level_row, int[] level, int offset)
|
|
{
|
|
int[] adjacencyRow = this.matrix.AdjacencyRow;
|
|
int[] adjacency = this.matrix.Adjacency;
|
|
mask[root] = 0;
|
|
level[offset] = root;
|
|
level_num = 0;
|
|
int num = 0;
|
|
int num2 = 1;
|
|
do
|
|
{
|
|
int num3 = num + 1;
|
|
num = num2;
|
|
level_num++;
|
|
level_row[level_num - 1] = num3;
|
|
for (int i = num3; i <= num; i++)
|
|
{
|
|
int num4 = level[offset + i - 1];
|
|
int num5 = adjacencyRow[num4];
|
|
int num6 = adjacencyRow[num4 + 1] - 1;
|
|
for (int j = num5; j <= num6; j++)
|
|
{
|
|
int num7 = adjacency[j - 1];
|
|
if (mask[num7] != 0)
|
|
{
|
|
num2++;
|
|
level[offset + num2 - 1] = num7;
|
|
mask[num7] = 0;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
while (num2 - num > 0);
|
|
level_row[level_num] = num + 1;
|
|
for (int i = 0; i < num2; i++)
|
|
{
|
|
mask[level[offset + i]] = 1;
|
|
}
|
|
}
|
|
|
|
// Token: 0x060000B4 RID: 180 RVA: 0x00012ECC File Offset: 0x000110CC
|
|
private void Degree(int root, int[] mask, int[] deg, ref int iccsze, int[] ls, int offset)
|
|
{
|
|
int[] adjacencyRow = this.matrix.AdjacencyRow;
|
|
int[] adjacency = this.matrix.Adjacency;
|
|
int i = 1;
|
|
ls[offset] = root;
|
|
adjacencyRow[root] = -adjacencyRow[root];
|
|
int num = 0;
|
|
iccsze = 1;
|
|
while (i > 0)
|
|
{
|
|
int num2 = num + 1;
|
|
num = iccsze;
|
|
for (int j = num2; j <= num; j++)
|
|
{
|
|
int num3 = ls[offset + j - 1];
|
|
int num4 = -adjacencyRow[num3];
|
|
int num5 = Math.Abs(adjacencyRow[num3 + 1]) - 1;
|
|
int num6 = 0;
|
|
for (int k = num4; k <= num5; k++)
|
|
{
|
|
int num7 = adjacency[k - 1];
|
|
if (mask[num7] != 0)
|
|
{
|
|
num6++;
|
|
if (0 <= adjacencyRow[num7])
|
|
{
|
|
adjacencyRow[num7] = -adjacencyRow[num7];
|
|
iccsze++;
|
|
ls[offset + iccsze - 1] = num7;
|
|
}
|
|
}
|
|
}
|
|
deg[num3] = num6;
|
|
}
|
|
i = iccsze - num;
|
|
}
|
|
for (int j = 0; j < iccsze; j++)
|
|
{
|
|
int num3 = ls[offset + j];
|
|
adjacencyRow[num3] = -adjacencyRow[num3];
|
|
}
|
|
}
|
|
|
|
// Token: 0x060000B5 RID: 181 RVA: 0x00012FC0 File Offset: 0x000111C0
|
|
private int[] PermInverse(int n, int[] perm)
|
|
{
|
|
int[] array = new int[this.node_num];
|
|
for (int i = 0; i < n; i++)
|
|
{
|
|
array[perm[i]] = i;
|
|
}
|
|
return array;
|
|
}
|
|
|
|
// Token: 0x060000B6 RID: 182 RVA: 0x00012FEC File Offset: 0x000111EC
|
|
private void ReverseVector(int[] a, int offset, int size)
|
|
{
|
|
for (int i = 0; i < size / 2; i++)
|
|
{
|
|
int num = a[offset + i];
|
|
a[offset + i] = a[offset + size - 1 - i];
|
|
a[offset + size - 1 - i] = num;
|
|
}
|
|
}
|
|
|
|
// Token: 0x04000091 RID: 145
|
|
private int node_num;
|
|
|
|
// Token: 0x04000092 RID: 146
|
|
private AdjacencyMatrix matrix;
|
|
}
|
|
}
|