Dividir modelo 3D por bucle de borde

Question

Tengo un modelo 3D, representado algo como esto:

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;
}

Por supuesto, esto se puede transformar en cualquier representación que sea más conveniente.

Quiero dividir este modelo en varias partes desconectadas, a lo largo de múltiples bucles de bordes conectados, y crear nuevas caras para tapar los extremos.Ejemplo con un bucle:

Las caras nuevas deberían estar en la misma posición y ser idénticas aparte de sus conexiones con otras caras, pero para este ejemplo las he separado.¿Cómo podría hacer esto?

No importa si los vértices se comparten entre las partes que de otro modo estarían desconectadas.

Dado que cada borde conecta exactamente dos caras, intenté dividir cada borde individualmente en dos copias (una para cada cara).Esto separa el modelo según sea necesario, pero no veo una manera de agregar correctamente las nuevas caras.

Esta pregunta está etiquetada como algoritmo de grafos porque este problema parece estar relacionado de alguna manera con la teoría de grafos.

Answer 1

• Arregla tu modelo. class Edge debe contener indicaciones para Face y Vertex en lugar de valores.
• Quieres usar algún tipo de set en lugar de List dentro de tu class Model.Esto ayuda a encontrar y eliminar cosas, y se asegura de que no haya duplicados.

• Crea un prototipo de tu función.yo sugiero

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

• crear dos modelos nuevos y vacíos, digamos ma y mb.Añade los bordes de loop a cada uno de ellos.
• elige un borde del loop.Llamemos a las dos caras adjuntas. fa y fb.
• agregar fa al modelo ma.Empezando desde fa, haga una búsqueda gráfica completa siguiendo todos los bordes adjuntos a fa, y todas las caras adjuntas a esos bordes, y así sucesivamente.Todas las caras y aristas encontradas deben seguirse y agregarse al modelo. ma.Si encuentra caras o aristas que ya forman parte de ma no los sigues.En particular, esto es lo que sucede cada vez que encuentras una ventaja que pertenece a loop para que nunca cruces la frontera.De esta manera haces una búsqueda completa de todas las aristas y caras de un lado y terminas con un modelo completo. ma.Finalmente agregas una cara que representa el corte.La mayoría de los vértices se pueden ignorar aquí, pero, por supuesto, al final probablemente quieras agregar todos los vértices que pertenecen a las caras que agregaste.
• Repita este paso comenzando desde la cara. fb para crear el modelo mb representando la otra parte.