Intrinsic Triangulation basis: `FlipEdgeNetwork` validates after shortening but `getPathPolyline()` reports an imperfect trace when endpoints are inserted vertices

[JeffreyLayton]

Description

I am constructing a temporary SignpostIntrinsicTriangulation, inserting two fixed interior surface points as vertices, and using those vertices as the endpoints of a FlipEdgeNetwork. Now this system probably is intended to be used directly on extrinsic meshes or free intrinsic meshes, thus the issue might lie with the double management of SignpostIntrinsicTriangulation (internal to FlipEdgeNetwork) ontop of a SignpostIntrinsicTriangulation. The reason im doing this is to test the feasbility of this type of system on surface based particle system (which has a custom managed intrinsic triangulation beyond the toy example here).

The network is valid both before and after iterativeShorten(), but path extraction fails:

network->validate();
network->iterativeShorten();
network->validate();

bool good = false;
const auto paths = network->getPathPolyline(good);

// good == false

Without calling iterativeShorten(), getPathPolyline() succeeds. The failure therefore appears after the flip-geodesic shortening creates new intrinsic edges.

Minimal reproduction

Assume:

• mesh is a compressed ManifoldSurfaceMesh;
• geometry is its corresponding VertexPositionGeometry;
• point_a and point_b are fixed SurfacePoints on mesh;
• both points are valid and distinct.

SignpostIntrinsicTriangulation temp_it(mesh, geometry);

const auto materialize_endpoint =
    [&temp_it](const SurfacePoint& point_on_input) -> Vertex {
    const SurfacePoint point_on_intrinsic =
        temp_it.equivalentPointOnIntrinsic(point_on_input);

    if (point_on_intrinsic.type == SurfacePointType::Vertex) {
        return point_on_intrinsic.vertex;
    }

    return temp_it.insertVertex(point_on_intrinsic);
};

Vertex endpoint_a = materialize_endpoint(point_a);

// Map B after inserting A because the intrinsic connectivity changed.
Vertex endpoint_b = materialize_endpoint(point_b);

if (endpoint_a == Vertex() || endpoint_b == Vertex()) {
    throw std::runtime_error("Failed to insert endpoints");
}

VertexData<std::uint8_t> endpoint_labels(
    *temp_it.intrinsicMesh,
    std::uint8_t{0}
);

endpoint_labels[endpoint_a] = 1;
endpoint_labels[endpoint_b] = 2;

temp_it.intrinsicMesh->compress();
temp_it.refreshQuantities();

endpoint_a = Vertex();
endpoint_b = Vertex();

for (Vertex v : temp_it.intrinsicMesh->vertices()) {
    if (endpoint_labels[v] == 1) {
        endpoint_a = v;
    } else if (endpoint_labels[v] == 2) {
        endpoint_b = v;
    }
}

if (endpoint_a == Vertex() || endpoint_b == Vertex()) {
    throw std::runtime_error(
        "Failed to recover endpoints after compression"
    );
}

auto network =
    FlipEdgeNetwork::constructFromDijkstraPath(
        *temp_it.intrinsicMesh,
        temp_it,
        endpoint_a,
        endpoint_b
    );

if (!network) {
    throw std::runtime_error(
        "Failed to construct the initial Dijkstra path"
    );
}

network->validate();

network->iterativeShorten();

network->validate();

bool trace_was_perfect = false;
const auto paths =
    network->getPathPolyline(trace_was_perfect);

if (!trace_was_perfect) {
    throw std::runtime_error(
        "Shortened path could not be traced onto the "
        "input triangulation"
    );
}

Observed behaviour

• Endpoint insertion succeeds.
• Endpoint handles are recovered after compression.
• constructFromDijkstraPath() succeeds.
• network->validate() succeeds before shortening.
• network->iterativeShorten() completes.
• network->validate() succeeds after shortening. (So its somehow a valid)
• network->getPathPolyline(trace_was_perfect) sets trace_was_perfect to false.

If iterativeShorten() is omitted, path extraction succeeds.