Разложение вогнутой сетки на множество выпуклых сеток

Я хотел бы иметь возможность разложить вогнутую сетку на набор выпуклых сеток по двум причинам:

1. Прозрачный рендеринг
2. Физика фигур

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

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

Я бы сказал, что вы на правильном пути, но придумать оптимальный и / или эффективный алгоритм - это другое дело: это сложная проблема. Однако, если ваш интерес не является академическим, может оказаться достаточно хорошего решения.

Во-первых, если вы не заинтересованы в разработке собственного решения, CGAL уже содержит алгоритм для декомпозиции выпуклых многогранников: http://doc.cgal.org/latest/Convex_decomposition_3/index.html.

Теперь о методе; Как и многие проблемы в 3D, часто полезно рассмотреть проблему 2D, которая легче понять. Для 2D задача состоит в том, чтобы идентифицировать рефлекторные вершины и разбить многоугольник на две части, создав новое ребро (и, возможно, новые вершины) из этой рефлекторной вершины и продолжая, пока у вас не останется никаких рефлекторных вершин (и, следовательно, полностью выпуклых многоугольников). ).

Разложение полигонов Дж. Марка Кейла содержит следующий алгоритм (в неоптимизированном виде):

diags = decomp(poly)
    min, tmp : EdgeList
    ndiags : Integer
    for each reflex vertex i
        for every other vertex j
            if i can see j
                left = the polygon given by vertices i to j
                right = the polygon given by vertices j to i
                tmp = decomp(left) + decomp(right)
                if(tmp.size < ndiags)
                    min = tmp
                    ndiags = tmp.size
                    min += the diagonal i to j
    return min

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

Если вам нужны «более приятные» декомпозиции, то есть те, которые производят более компактные формы, а не вытянутые, вы можете также рассмотреть эту, созданную Марком Баязитом , которая является жадной (следовательно, намного более быстрой) и выглядит лучше, но имеет несколько недостатков. Он в основном работает, пытаясь соединить рефлекторные вершины с лучшей, противоположной ей, обычно с другой рефлекторной вершиной:

Одним из недостатков является то, что он игнорирует «лучшие» декомпозиции, создавая точки Штейнера (точки, которые не существуют на существующем ребре):

Проблема в 3D может быть похожей; вместо рефлекторных вершин вы определяете «края надреза». Наивной реализацией было бы выявить края надрезов и многократно выполнять плоские разрезы на многограннике, пока все многогранники не выпуклые. Проверьте "Выпуклые разбиения многогранников: нижняя граница и оптимальный алгоритм наихудшего случая" Бернарда Шазеля для получения дополнительной информации.

Обратите внимание, что этот подход может привести к наихудшему случаю экспоненциального числа субполиэдров. Это потому, что вы можете иметь вырожденные случаи, подобные этому:

Но если у вас нетривиальная сетка (например, неровная поверхность), вы все равно получите плохие результаты. Весьма вероятно, что вы захотите сделать много упрощений заранее, если вам когда-либо понадобится использовать это для сложных сеток.

Вычисление точного выпуклого разложения поверхности S является NP-сложной задачей и обычно приводит к большому количеству кластеров. Чтобы преодолеть эти ограничения, точное ограничение выпуклости может быть ослаблено, и вместо этого вычислено приблизительное выпуклое разложение S. Здесь цель состоит в том, чтобы определить разбиение треугольников сетки с минимальным количеством кластеров, при этом гарантируя, что каждый кластер имеет вогнутость ниже порога, определенного пользователем.

Проверьте следующие приблизительные выпуклые библиотеки декомпозиции: https://code.google.com/p/v-hacd/ http://sourceforge.net/projects/hacd/

Вот код, который может вам помочь. Он находится в Java, поэтому вам придется конвертировать его в C ++.

Вот еще одна статья, которая может помочь вам