Recursive function to merge 3D objects

Question

I have several 3D items in listOri. For this example:

listOri has A,B,C,D,E.

A overlaps with C.
B overlaps with D.
D overlaps with E.

I have a recursive function which accepts listOri, check if each item overlaps with each other, and generates a final listNew which has AC, BDE.

Iteration 1: Loop through each item in listOri, generates listNew containing AC,B,D,E

Iteration 2: Loop through AC,B,D,E in listNew, generates (new) listNew containing, AC,BD,E

Iteration 3: and so on.

Here is the snippet code which check if each 3D object in a list overlaps, and produces a new list recursively.

 Private Function SimplifyModel2(ByVal listOri As List(Of Mesh3D)) As List(Of Mesh3D) 
 Dim listNew As New List(Of Mesh3D)(listOri)
 Dim indexOut, indexIn, indexInner, PercentProgressCurrent As Integer
 Dim currentMeshOutter, currentMeshInner As Mesh3D
 Dim isExitForCalled As Boolean = False
 totInnerLoops = totInnerLoops + 1 ' increment total number of inner loops
 For indexOut = 0 To (listOri.Count - 1)
 currentMeshOutter = listOri(indexOut)
 indexInner = indexOut + 1
 For indexIn = indexInner To (listOri.Count - indexInner)
 currentMeshInner = listOri(indexIn)
 If Is3DOverlap(currentMeshInner, currentMeshOutter) = True Then
 currentMeshOutter.CombineMerge(currentMeshInner)
 listNew.Remove(currentMeshInner)
 listNew.Remove(currentMeshOutter)
 listNew.Insert(0, currentMeshOutter)
 listNew = SimplifyModel2(listNew) ' recursively call the function
 isExitForCalled = True
 Exit For
 End If
 Next
 If isExitForCalled = True Then
 Exit For
 End If
 Next
 indLoopExit = indLoopExit + 1
 Return listNew
End Function

The function works well with listOri with very few items. However, when there are thousands of 3D items in listOri, the functions takes very long time to produce the listNew.

1. How do I increase the speed of the recursive function?
2. Is there another way to write an algorithm which performs the same task above?

Let me know if you need any information.

Thank you.

Answer 1

I don't think you need recursion. The items in your first loop always "eat" the other ahead of them. Loop all items, for each item check if it can merge into an item ahead of it, if yes, merge and remove the item that was ahead.

Now VB does store the "To" part of a for loop in memory, so you'll need to convert your For into Do loop instead.

If you want your main list to be untouched, you could clone it. But don't forget that it seems each instance will be affected in the two list if you do that.

Private Sub SimplifyModel2(ByVal listOri As List(Of Mesh3D))
 Dim indexOut, indexIn As Integer
 Dim currentMeshOutter, currentMeshInner As Mesh3D
 indexOut = 0
 Do While indexOut < istOri.Count
 currentMeshOutter = listOri(indexOut)
 indexIn = indexOut + 1
 Do While indexIn < istOri.Count
 currentMeshInner = listOri(indexIn)
 If Is3DOverlap(currentMeshInner, currentMeshOutter) Then
 currentMeshOutter.CombineMerge(currentMeshInner)
 istOri.Remove(currentMeshInner)
 Else
 indexIn += 1
 End If
 Loop
 indexOut += 1
 Loop
End Sub