Разделение 3D-модели по контуру кромки

Question

У меня есть 3D-модель, представленная примерно так:

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

Конечно, это может быть преобразовано в любое наиболее удобное представление.

Я хочу разделить эту модель на несколько несвязанных частей вдоль нескольких петель соединенных краев и создать новые грани, чтобы закрыть концы.Пример с одним циклом:

Новые грани должны находиться в том же положении и быть идентичными, за исключением их соединений с другими гранями, но для этого примера я раздвинул их.Как я мог это сделать?

Не имеет значения, являются ли вершины общими для других несвязанных частей.

Поскольку каждое ребро соединяет ровно две грани, я попробовал разделить каждое ребро по отдельности на две копии (по одной для каждой грани).Это действительно отделяет модель по мере необходимости, но тогда я не вижу способа правильно добавить новые грани.

Этот вопрос помечен как graph-algorithm, потому что кажется, что эта проблема каким-то образом связана с теорией графов.

Answer 1

• Исправьте свою модель. class Edge должны содержать указатели на Face и Vertex вместо ценностей.
• Вы хотите использовать какой-то вид set вместо List внутри вашего class Model.Это помогает находить и удалять файлы, и вы убедитесь, что в них нет дубликатов.

• Придумайте прототип вашей функции.Я предлагаю

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

• создайте две новые пустые модели, скажем ma и mb.Добавьте края из loop к каждому из них.
• выберите один край из loop.Давайте назовем две грани, прикрепленные к нему fa и fb.
• добавлять fa к модели ma.Начиная с fa, выполните полный поиск по графу , следуя по всем ребрам , прикрепленным к fa, и все грани, прикрепленные к этим краям, и так далее.Все встречающиеся грани и ребра должны быть прослежены и добавлены в модель ma.Если вы столкнетесь с гранями или ребрами, которые уже являются частью ma вы не следуете им.В частности, это то, что происходит всякий раз, когда вы сталкиваетесь с ребром, принадлежащим loop так что вы никогда не пересекаете границу.Таким образом, вы выполняете полный поиск по всем ребрам и граням с одной стороны и в итоге получаете законченную модель ma.Наконец, вы добавляете грань, представляющую разрез.Вершины здесь в основном можно игнорировать, но, конечно, в конце вы, вероятно, захотите добавить все вершины, которые принадлежат добавленным вами граням.
• Повторите этот шаг, начиная с лица fb чтобы создать модель mb представляющий другую часть.