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