Edge coloring heuristic improvement about msdfgen HOT 2 CLOSED

Some time ago, I had an idea how to perform the edge coloring in the (presumably) optimal way, although it would be very slow, therefore likely not worth the performance cost in most cases. However, in some circumstances, such as when distance field assets are being pre-generated in advance and quality has priority over everything else, this can be useful. The solution is the following.

1. Adjacent edge segments that connect smoothly (based on angle threshold) would be aggregated into edge groups.
2. The minimum (Euclidean unsigned) distance for all edge group pairs would be computed. - This is the very slow part; The distance between two Bézier curves has to be iteratively approximated, and there are n² pairs for n edge groups. (Not to mention that computing a single distance would involve all pairs of either group's members.)
3. A graph optimization problem would be solved where edge groups are nodes, the graph is fully connected, and the distances are edge lengths. The task is to find a 3-coloring of the graph's nodes such that edge lengths between nodes of the same color are as high as possible. This is potentially another slow part as it's obviously an NP problem.

Notes:

• By using inverse distances as graph edge lengths, the problem can be thought of as partitioning the graph into 3 tight clusters.
• The specific formula to rate a graph coloring is not determined. For example, it is not clear which set of distances between same-colored edge groups is better: [2, 3, 1000] or [8, 10, 12].
• Since the distance between adjacent edge groups is 0, it should guarantee that they will have different colors, ensuring corner preservation implicitly. This property of the algorithm is actually what makes me believe it is the right approach.
• Contours with only one corner would be split into three groups as usual, but the middle group would be excluded from the algorithm and colored white implicitly.
• Contours that only contain one edge group (are smoothly connected) can be excluded from the algorithm and colored white as they are now, but including them may or may not yield better results - this needs to be tested.

from msdfgen.

An initial version of this has been implemented and can be applied by adding the option -coloringstrategy distance, or using the new edgeColoringByDistance function when used as a library. The current implementation is experimental and may be further worked on in the future.

from msdfgen.