0. Parametrization

1. Computation of the integer grid map

The first step is the computation of the integer grid map, done by computing the intersections (in the sketch space) of each triangle with parametric integer isolines.

2. Trace segments and grid nodes

We start the tracing by looking at all triangles with estimated tangent directions (u or v). For each triangle t with the direction d, we find all isoline segments in the direction d in the triangle t, and we add these isoline segments to the list of seeds. Then, while the list of seeds is not empty, we pop a seed, mark the corresponding isoline segment as traced, and continue the tracing by placing more seeds to the adjacent triangles. The tracing stops if the seed segment is not inside of a triangle, or if the non-integer part of the translational part of the transition function between triangles is bigger than a threshold.

Afterwards, all grid nodes lying on a traced segment are marked as traced.

3. Cluster grid nodes

The traced grid nodes are locally organized into clusters. Two grid nodes are in the same cluster if they correspond to the same grid node in the parametric space.

4. Construct the dual graph over traced segments

We construct a dual graph over the traced segments. In this graph, two traced segments are connected by an edge if they were extracted from the same isoline.

We also construct a subgraph of this graph (a partial dual graph) in which two traced segments are connected by an edge if they were extracted from the same isoline segment [i,i+1].

5. Disambiguate curves

[WORK IN PROGRESS]

Each connected component of the partial dual graph defines a base curve (that corresponds to some isoline segment [i,i+1]). However, some of these curves might have incorrect topology (e.g. they form a Y as the one on the screenshot) – these need to be split into multiple curves.

6. Correct curve parametrization

At this stage, we have extraced a bunch of line segments and grid nodes (step 2) and we have organized them into curves (step 4, 5). Next, we assign a value t in [0,1] to each line segment in a given curve based on the compute global parametrization (step 0).

In this step, we make sure that this parametrization is consistent for each curve by flipping the value of the parameter (t := 1-t) for inconsistent segments.

Corrected parametrization:

Flipped segments:

7. Pixel assignment

At this point, the candidate curves are computed. Now, for each pixel, we find and store the set of nearest curves (primary, secondary, etc.)

8. Curve removal

[TODO : implement a scheme for interative removal]
[TODO : update assigned pixels when a curve is removed]

Having computed the pixel-curve assignment, we proceed to remove curves that have weak support. The main criteria for removing a curve are the following:

  1. Number of pixels for which the curve is the nearest curve (primary pixels)
  2. Cost of removing this curve, measured by taking the aggregate difference of distances of primary pixels to the second nearest curve.
  3. Parametric coverage of the curve: maximal coverage is [0.0, 1.0], if it’s smaller, e.g. [0.0, 0.2] or [0.7, 1.0], we know that the curve has an open end, and is a good candidate for removal.
  4. Length of the curve chain to which the curve belongs: short chains are likely just noise.

9. Bezier fitting and simplification

[TODO : implement Bezier fitting]
[TODO : implement Bezier merging]

The above process essentially gives us the topology of the output curve network. In the last step, we fit a network of Bezier curves to this topology.

We can further simplify the result by iteratively merging adjacent Bezier curves.