Graph Search

Setup

We convert the curve network into a routing system by finding all possible corner mappings $C_i$ at each vertex $v_i$. Then we compute the edge cost of the graph as follows:

1. For each triplet of consecutive curves, we compute its intra-bridge cost. In particular, we loop through $N$ equi-angularly spaced normals and set the intra-bridge cost of the bridge to be the smallest intra-bridge cost attained by parallel transporting the normals across the triplet of curves.
2. For each curve $b$ with vertices $v_1$ and $v_2$, we find all combinations of corner mappings $(c_1, c_2)$ at $v_1$ and $v_2$. For each combination, we compute the inter-bridge cost using the normals computed when finding the intra-bridge cost.
3. Set the cost of an edge between two corner mappings $(c_i, c_j)$ to be the lowest sum of intra-bridge cost and inter-bridge cost.

Search

We use a classic graph search algorithm to find the optimal set of cycles. Starting from an empty set $V$ of vertices, we expand to a new vertex one at a time. At every step, we compute the minimum-weight subgraph of $G$ that cover $V$. We stop when $V$ covers all vertices in the curve network.

Meshing

The output of the graph search is a routing system, namely a corner mapping per vertex and a bridge mapping per curve. We convert this routing system into a set of cycles by following paths along the corner mapping and bridge mapping. For each cycle we run the classic triangulation algorithms (Liepa 2003) to establish a closed mesh patch, and then run isotropic remeshing algorithm (Botsch and Kobbelt 2004) to optimize the triangulation. Finally, we stitch the mesh patches together to form a closed mesh, which is the output of the sketch-to-mesh algorithm.