Dividir modelo 3D por loop de aresta

Question

Eu tenho um modelo 3D, representado mais ou menos assim:

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

É claro que isto pode ser transformado em qualquer representação que seja mais conveniente.

Quero dividir este modelo em várias partes desconectadas, ao longo de vários loops de arestas conectadas, e criar novas faces para cobrir as extremidades.Exemplo com um loop:

As novas faces devem estar na mesma posição e idênticas, exceto por suas conexões com outras faces, mas neste exemplo eu as separei.Como eu poderia fazer isso?

Não importa se os vértices são compartilhados entre as partes desconectadas.

Como cada aresta conecta exatamente duas faces, tentei dividir cada aresta individualmente em duas cópias (uma para cada face).Isso separa o modelo conforme necessário, mas não consigo ver uma maneira de adicionar corretamente as novas faces.

Esta questão é marcada como algoritmo de grafos porque este problema parece estar de alguma forma relacionado à teoria dos grafos.

Answer 1

• Corrija seu modelo. class Edge deve conter ponteiros para Face e Vertex em vez de valores.
• Você quer usar algum tipo de set em vez de List dentro do seu class Model.Isso ajuda a encontrar e remover coisas e garante que não haja duplicatas.

• Crie um protótipo de sua função.Eu sugiro

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

• crie dois modelos novos e vazios, digamos ma e mb.Adicione as bordas de loop para cada um deles.
• escolha uma borda do loop.Vamos chamar as duas faces ligadas a ele fa e fb.
• adicionar fa para o modelo ma.Começando de fa, faça uma pesquisa completa no gráfico seguindo todas as arestas anexadas a fa, e todas as faces anexadas a essas arestas e assim por diante.Todas as faces e arestas encontradas devem ser seguidas e adicionadas ao modelo ma.Se você encontrar faces ou arestas que já fazem parte ma você não os segue.Em particular, isso é o que acontece sempre que você encontra uma aresta que pertence a loop então você nunca cruza a fronteira.Desta forma você faz uma pesquisa completa de todas as arestas e faces de um lado e acaba com um modelo completo ma.Finalmente você adiciona uma face representando o corte.Os vértices podem ser ignorados aqui, mas é claro que no final você provavelmente desejará adicionar todos os vértices que pertencem às faces que você adicionou.
• Repita este passo começando pelo rosto fb para criar o modelo mb representando a outra parte.