For a while, I've been writing a custom LDraw to Collada converter for Bricklink Studio, as the one currently in the program is, to put it lightly, sucks

Have a problem with it's performance of finding and merging same vertex positions

Here's the code for one I have currently:

In short, it subdivides space in sections, in each of which it checks each pair of vertices on if they are close enough to be considered the same, or not. Wonder if there is a way to make it faster

Have a problem with it's performance of finding and merging same vertex positions

Here's the code for one I have currently:

Code:

`static void MergeCell1(List<Vector3> cell)`

{

for (int i = 0; i < cell.Count - 1; i++)

{

for (int j = i + 1; j < cell.Count; j++)

if (Vector3.Distance(cell[i], cell[j]) < MERGE_RADIUS)

cell[j] = cell[i];

}

}

static void MergeCell2(List<Vector3> cell, List<Vector3> sharpCell)

{

for (int i = 0; i < cell.Count; i++)

{

for (int j = 0; j < sharpCell.Count; j++)

if (Vector3.Distance(cell[i], sharpCell[j]) < MERGE_RADIUS)

sharpCell[j] = cell[i];

}

}

static void MergeCell3(List<Vector3> sharpCell)

{

for (int i = 0; i < sharpCell.Count - 1; i++)

{

for (int j = i + 1; j < sharpCell.Count; j++)

if (Vector3.Distance(sharpCell[i], sharpCell[j]) < MERGE_RADIUS)

sharpCell[j] = sharpCell[i];

}

}

static void MergeCell4(List<Vector3> cell, List<Vector3> sharpCell)

{

for (int i = 0; i < sharpCell.Count; i++)

{

for (int j = 0; j < cell.Count; j++)

if (Vector3.Distance(sharpCell[i], cell[j]) < MERGE_RADIUS)

cell[j] = sharpCell[i];

}

}

static void MergePoints(string model)

{

if (preBuilt.ContainsKey(model)) return;

float maxX = subMeshes[model].MaxBy(x => x.X).X;

float maxY = subMeshes[model].MaxBy(x => x.Y).Y;

float maxZ = subMeshes[model].MaxBy(x => x.Z).Z;

float minX = subMeshes[model].MinBy(x => x.X).X;

float minY = subMeshes[model].MinBy(x => x.Y).Y;

float minZ = subMeshes[model].MinBy(x => x.Z).Z;

int step = (int)Math.Round(Math.Pow(subMeshes.Count, 1.0 / 3.0));

float stepX = (maxX - minX) / step;

float stepY = (maxY - minY) / step;

float stepZ = (maxZ - minZ) / step;

List<Vector3>[,,] cells = new List<Vector3>[step, step, step];

List<Vector3>[,,] cellsLines = new List<Vector3>[step, step, step];

for (int i = 0; i < step; i++)

for (int j = 0; j < step; j++)

for (int k = 0; k < step; k++)

{

cells[i, j, k] = (from a in subMeshes[model]

where

a.X <= minX + (i * stepX) && a.X > minX + (i + 1 * stepX) &&

a.Y <= minY + (i * stepY) && a.X > minY + (i + 1 * stepY) &&

a.Z <= minZ + (i * stepZ) && a.X > minZ + (i + 1 * stepZ)

select a).ToList();

}

for (int i = 0; i < step; i++)

for (int j = 0; j < step; j++)

for (int k = 0; k < step; k++)

{

cellsLines[i, j, k] = (from a in subSharps[model]

where

a.X <= minX + (i * stepX) && a.X > minX + (i + 1 * stepX) &&

a.Y <= minY + (i * stepY) && a.X > minY + (i + 1 * stepY) &&

a.Z <= minZ + (i * stepZ) && a.X > minZ + (i + 1 * stepZ)

select a).ToList();

}

Console.WriteLine("Merging points of model " + model + ", step 1 - " + subMeshes[model].Count + " points");

Parallel.ForEach(cells.Cast<List<Vector3>>(), MergeCell1);

Console.WriteLine("Merging points of model " + model + ", step 2 - " + subMeshes[model].Count + " points");

Parallel.ForEach(cells.Cast<List<Vector3>>(), x => Parallel.ForEach(cellsLines.Cast<List<Vector3>>(), y => MergeCell2(x, y)));

Console.WriteLine("Merging points of model " + model + ", step 3 - " + subSharps[model].Count + " points");

Parallel.ForEach(cellsLines.Cast<List<Vector3>>(), MergeCell3);

Console.WriteLine("Merging points of model " + model + ", step 4 - " + subSharps[model].Count + " points");

Parallel.ForEach(cells.Cast<List<Vector3>>(), x => Parallel.ForEach(cellsLines.Cast<List<Vector3>>(), y => MergeCell4(x, y)));

/*for (int i = 0; i < subMeshes[model].Count - 1; i++)

{

for (int j = i + 1; j < subMeshes[model].Count; j++)

if (Vector3.Distance(subMeshes[model][i], subMeshes[model][j]) < MERGE_RADIUS)

subMeshes[model][j] = subMeshes[model][i];

//if (i % (subMeshes[model].Count / 100) == 0 && i != 0) Console.WriteLine("Merging points of model " + model + ", step 1: " + i / (subMeshes[model].Count / 100) + " % ");

}

Console.WriteLine("Merging points of model " + model + ", step 2 - " + subMeshes[model].Count + " points");

for (int i = 0; i < subMeshes[model].Count; i++)

{

for (int j = 0; j < subSharps[model].Count; j++)

if (Vector3.Distance(subMeshes[model][i], subSharps[model][j]) < MERGE_RADIUS)

subSharps[model][j] = subMeshes[model][i];

//if (i % (subMeshes[model].Count / 100) == 0 && i != 0) Console.WriteLine("Merging points of model " + model + ", step 2: " + i / (subMeshes[model].Count / 100) + " % ");

}

Console.WriteLine("Merging points of model " + model + ", step 3 - " + subSharps[model].Count + " points");

for (int i = 0; i < subSharps[model].Count - 1; i++)

{

for (int j = i + 1; j < subSharps[model].Count; j++)

if (Vector3.Distance(subSharps[model][i], subSharps[model][j]) < MERGE_RADIUS)

subSharps[model][j] = subSharps[model][i];

//if (i % (subSharps[model].Count / 100) == 0 && i != 0) Console.WriteLine("Merging points of model " + model + ", step 3: " + i / (subMeshes[model].Count / 100) + " % ");

}

Console.WriteLine("Merging points of model " + model + ", step 4 - " + subSharps[model].Count + " points");

for (int i = 0; i < subSharps[model].Count; i++)

{

for (int j = 0; j < subMeshes[model].Count; j++)

if (Vector3.Distance(subSharps[model][i], subMeshes[model][j]) < MERGE_RADIUS)

subMeshes[model][j] = subSharps[model][i];

//if (i % (subSharps[model].Count / 100) == 0 && i != 0) Console.WriteLine("Merging points of model " + model + ", step 4: " + i / (subMeshes[model].Count / 100) + " % ");

}*/

}

In short, it subdivides space in sections, in each of which it checks each pair of vertices on if they are close enough to be considered the same, or not. Wonder if there is a way to make it faster