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