Improving the Contour Detection Algorithm

Hi

One of the core algorithm of the QuadPaint tool estimates the amount of closed contours that can be extracted from an arbitrary set of strokes, which can be treated as graphs.

In my first development attempt I successfully implemented an algorithm that extracted the minimum path loops first. It worked very well but soon realized that the condition had very common ill cases:

In the above figure, the minimum path for the outer loops overlaps the inner loop, causing messed geometry in latter stages of the pipeline:

So I must carefully find another solution, another condition that adjacent loops should met:

Filled loops should not overlap , but that term is a bit tricky because we are talking of 3D meshes so some sort of projection or volume intersection test needs to be implemented, and we all know those arbitrary precision intersection mesh calculations are very heavy for close to real-time performance.

I eventually found a very elegant solution: Filled contour areas, non overlapping adjacent contours have minimum area compared to the overlapped ones, In terms of a Set theory, overlapping is equivalent to a Union and non overlapping to a Difference.

And that’s it! after implement that condition, arbitrary graph sets can be decomposed in  minimum area loops or adjacent non overlapping sets.