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

У меня есть 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;
}

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

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

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

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

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

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


algorithm computational-geometry graph-algorithm 3d-model
person user253751    schedule 25.02.2014    source источник

Ответы (1)


arrow_upward
2
arrow_downward

  • Исправьте свою модель. 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, представляющую другую часть.
person pentadecagon    schedule 25.02.2014