UVAtlas is quadratic in the number of boundaries

[bitonic]

In the PrepareProcessing step, this loop

UVAtlas/UVAtlas/isochart/isochartengine.cpp

Line 1264 in 4607a94

while (!m_currentChartHeap.empty())

will essentially run once per boundary. A bit below in the stack, this function

UVAtlas/UVAtlas/isochart/isochartmesh.cpp

Line 2792 in 4607a94

HRESULT CIsochartMesh::CalMinPathBetweenBoundaries(

will run, calculating the minimum path for each boundaries. Moreover, CalMinPathToOtherBoundary loops through all the vertices multiple times.

This makes the complexity of the prepare step O(number_of_boundaries * number_of_boundaries * number_of_vertices)

I have attached a mesh made out of ~150000 vertices and ~5000 boundaries (mostly composed of 0-area holes, but I don't think that matters). In this case the runtime of PrepareProcessing is unbearably slow (I let it run for 4hrs and it did not terminate). The flame graph looks something like this:

I might give a shot at fixing this myself, but I wanted to report this behavior for other users first.

mesh-clean.zip

[bitonic]

Possible more precise implementation idea:

• Store the information about boundaries (allBoundaryList, boundaryRecord, distance between boundary extrema) per-component, rather than globally;
• When cutting a chart by joining two boundary extrema, invalidate only the information for the boundaries in the same component.

This would avoid recomputing boundary distances globally -- you only need to recompute the distances within the same component. This is correct since cutting a chart will only affect boundary distances within the same component.

This would fix the pathological behavior in my case, since it's not the case that a single connected component has 5k boundaries. I suspect this will be the case for most meshes, although I'm not sure. It would definitely be an improvement.

[bitonic]

Actually, even more generally: we can store the boundary information per-chart, and then invalidate information within the same chart.

[walbourn]

If you have a pull request with this optimization, I'd be happy to take a look at it.