Как извлечь лежащий в основе 2-многообразие из не-многообразия, удалив «свободные грани»? - PullRequest
Новая
       83

Как извлечь лежащий в основе 2-многообразие из не-многообразия, удалив «свободные грани»?

4 голосов
/ 20 мая 2019

Я пытаюсь извлечь базовый 2-коллектор (замкнутую поверхность) из немногообразной сетки. Я использую CGAL для манипуляций с сеткой. Я хочу добиться этого, удалив «свободные лица». Под свободным я подразумеваю лицо, у которого по крайней мере один край является граничным краем. Удаление свободного лица в конечном итоге может создать новые «свободные лица» , Я хочу продолжать удалять их, если у грани нет грани. Например, если у меня есть 2-сфера и структура, похожая на ребро, я хочу получить 2-сферу, удалив все грани ребра.

В CGAL я продолжал перебирать половину ребра, и если я получаю половину ребра, противоположность которой is_border, я удаляю инцидент с гранью (точнее используя make_hole (h)), до половины ребра. Я продолжаю повторять, когда такое удаление невозможно. 

typedef CGAL::Exact_predicates_inexact_constructions_kernel I;
typedef CGAL::Polyhedron_3<I> Polyhedron;
Polyhedron mesh;

//
int in_this_iter = 0;
    do {
        in_this_iter = 0;
        for (auto h = mesh.halfedges_begin(); h != mesh.halfedges_end(); h++) {
            //cout << e->is_border() << endl;

            if (h->opposite()->is_border() && !h->is_border()) {
                mesh.make_hole(h);
                /*CGAL::Euler::remove_face(h,mesh);
                *gives trouble*/
                in_this_iter++;
            }
            else if (h->is_border() && !h->opposite()->is_border()) {
                mesh.make_hole(h->opposite());

                in_this_iter++;
            }

        }
        //mesh.normalize_border();
        count = count + in_this_iter;
        std::cout << "Face Deleted in this iter: " << in_this_iter<<endl;
    } while (in_this_iter != 0);
    std::cout << "Face Deleted: " << count<<endl;

Структура, которую я тестирую: 

OFF
7 8 0
0.0 0.0 0.0
1.0 0.0 0.0
2.0 0.0 0.0
0.0 1.0 0.0
1.0 1.0 0.0
2.0 1.0 0.0
0.0 0.0 1.0
3 0 1 3
3 3 1 4
3 1 4 2
3 2 4 5
3 1 2 4
3 3 1 6
3 3 4 6
3 1 4 6

Мой алгоритм не удаляет любое свободное лицо. Но в идеале нужно захватить 4 грани тетраэдра, удалив остальные. П.С .: Ценю вашу помощь! И, пожалуйста, прости меня, если я не следовал приличию, поскольку это мой первый пост.

1 Ответ

0 голосов
/ 22 мая 2019

Вы не должны изменять структуру, в которой выполняется цикл, так как результаты могут быть неожиданными. Скорее, вы можете просто сделать что-то вроде: 

Find all faces that have an halfedge on the border
Put them in a stack
while(stack not empty)
  take the face 'f' top of the stack
  if('f' is already tagged)
    continue
  else
    tag 'f' as "to_be_removed"
    add all neighboring faces that are not already tagged to the stack
done
Remove all faces that were tagged "to_be_removed"

Обратите внимание, что это примерно то, что делают функции CGAL :: PMP :: connected_components : они перегруппируют все грани вашей структуры в группы так, что все грани одной группы могут достигать друг друга, ходить от одного лица к другому. Таким образом, вы могли бы также использовать эти CGAL::PMP::connected_components функции, чтобы пометить ваши лица в связанных компонентах, а затем отбросить связанные компоненты, которые не образуют замкнутую сетку. Вы можете найти вдохновение в следующей функции , цель которой - разделить данную структуру на независимые связанные компоненты. Это будет первый шаг вашего кода; Ваш второй шаг - просто посмотреть, закрыта ли сетка (CGAL::is_closed()) или нет.

...