Максимальное количество вершин после обрезки треугольника против AABB

8

Я обрезаю трехмерный треугольник на трехмерной ограничивающей оси (AABB), чтобы получить самый большой плоский многоугольник треугольника, содержащийся в AABB. Мой алгоритм отсечения является (слегка измененной) версией надежного (например, отсечения плоскостей небольшой конечной толщины) алгоритма Сазерленда-Ходжмана, как описано в «Обнаружении столкновений в реальном времени» К. Эриксона. Я зажимаю треугольник против каждой из 6 плоскостей, составляющих AABB.

Чтобы избежать выделения кучи (de), я заранее выделил точечный буфер фиксированного размера в стеке для всех вершин полученного плоского многоугольника. Теперь у меня вопрос: какое максимальное количество вершин можно получить после обрезки треугольника против AABB?

Основываясь на потоке управления, каждая проверенная вершина может привести к двум вершинам во время отсечения плоскости многоугольника. Таким образом, вершин. Из-за симметрии это становится вершины. Однако на практике я всегда получаю меньше вершин.326323=24

Матиас
источник

Ответы:

9

Как ни странно, я задал этот точный вопрос на Math.SE пару лет назад: максимальное количество вершин в пересечении треугольника с коробкой .

Ответ 9 вершин, потому что каждая из 6 плоскостей прямоугольника может отрезать один угол многоугольника, заменяя одну вершину двумя. Таким образом, 3 вершины + 6 добавленных вершин из-за отсечения = 9 всего.

Натан Рид
источник