Split 3D model by edge loop

Question

I have a 3D model, represented something like this:

class Vertex
{
    double x, y, z;
}

class Edge
{
    Vertex *v1, *v2; // no particular order
    Face *f1, *f2; // no particular order. f2 may be null.
}

class Face
{
    List<Vertex*> vertices; // clockwise order
    List<Edge*> edges; // clockwise order
}

class Model
{
    List<Face*> faces;
    List<Vertex*> vertices;
    List<Edge*> edges;
}

Of course this can be transformed into whatever representation is most convenient.

I want to split this model, into several disconnected parts, along multiple loops of connected edges, and create new faces to cap the ends. Example with one loop:

The new faces should in the same position, and identical apart from their connections to other faces, but for this example I've moved them apart. How could I do this?

It does not matter if vertices are shared between the otherwise-disconnected parts.

Since every edge connects exactly two faces, I tried splitting each edge individually into two copies (one for each face). This does separate the model as required, but then I can't see a way to correctly add the new faces.

This question is tagged graph-algorithm because this problem seems like it's somehow related to graph theory.

Answer 1

• Fix your model. class Edge should hold pointers to Face and Vertex instead of values.
• You want to use some kind of set instead of List within your class Model. This helps with finding and removing things, and you make sure there are no duplicates.

• Come up with a prototype of your function. I suggest

pair<Model*, Model*> split_model( const Model* mx, const List<Edge*>& loop );

• create two new, empty models, say ma and mb. Add the edges from loop to each of them.
• pick one edge from the loop. Let's call the two faces attached to it fa and fb.
• add fa to the model ma. Starting from fa, do a complete graph search by following all edges attached to fa, and all faces attached to those edges, and so on. All faces and edges encountered must be followed and added to model ma. If you encounter faces or edges that are already part of ma you do not follow them. In particular this is what happens whenever you encounter an edge that belongs to loop so you never cross the border. This way you do a complete search of all edges and faces on one side and you end up with a complete model ma. Finally you add a face representing the cut. The vertices can be mostly ignored here, but of course at the end you probably want to add all vertices that belong to the faces you added.
• Repeat this step starting from face fb to create the model mb representing the other part.