Заполнить отверстие сетки после обрезки против плоскости
Я написал простой алгоритм, который обрезает произвольный трехмерный объект на плоскости:
Алгоритм примерно работает так:
1) Переберите все треугольники
2) Итерировать все ребра для каждого треугольника
3) Если ребро пересекается с плоскостью, генерируется 1 или 2 новых треугольника, старый треугольник отбрасывается
4) Если ребра не пересекаются, треугольник либо остается неповрежденным, либо отбрасывается (в зависимости от того, на какой стороне плоскости он находится)
Конечно, это оставляет отверстие в сетке, где плоскость прорезает его. Какой быстрый способ создать новую сетку для заполнения дыры? Для выпуклой геометрии я мог бы просто использовать одну из новых вершин на плоскости в качестве начальной точки и соединить ее со всеми остальными новыми точками и генерировать треугольники таким образом, однако объект не обязательно выпуклый.
Решение
Если треугольник пересекается плоскостью во время отсечения, то два его ребра обязательно пересекаются, и каждое пересеченное ребро генерирует одну новую вершину, поэтому для этого треугольника создаются две новые вершины (игнорируя случаи, когда плоскость пересекается точно с вершинами треугольника) , Для каждой новой вершины следует отслеживать две другие новые вершины, созданные в двух треугольниках, смежных с краем начальной новой вершины. Затем, просто пройдя все различные цепочки таких соседних новых вершин, можно восстановить (возможно, не выпуклые) заполняющие многоугольники, необходимые для закрытия отверстий обрезанной сетки. Чтобы получить выпуклые многоугольники или простые треугольники из этих многоугольников, примените алгоритм выпуклого разложения или триангуляции многоугольников (см. Триангуляция полигонов). Это предполагает, что входная сетка была водонепроницаемой, с правильными ребрами треугольника (одно ребро разделяется только двумя треугольниками) и игнорирует проблемы, связанные с пересечением вершины / плоскости.
На практике: всякий раз, когда новая вершина создается в одном треугольнике, отслеживайте индекс другой новой вершины, созданной в том же треугольнике (и наоборот). Таким образом, каждый новый идентификатор вершины в конечном итоге отображается на два новых идентификатора вершины, один из которых создан «слева», а другой — «справа» новой вершины. Ориентация «влево» / «вправо» определяется на основе ориентации плоскости и относительной ориентации двух соседних новых вершин. Как только отсечение закончено, выберите одну новую вершину в отображении, обойдите отображение в том же направлении (влево или вправо), чтобы извлечь всю многоугольную цепочку, и как только эта цепочка будет закрыта (возвращаясь к первой выбранной вершине), новая Заполняющий многоугольник может быть добавлен в обрезанную сетку. Продолжайте выбирать неиспользуемые новые вершины в отображении и обходите отображение, пока все новые вершины не будут использованы в многоугольниках заполнения дырок.
Другие решения
Других решений пока нет …