полигоны из BSP

У меня есть трехмерный том, заданный деревом разделов двоичного пространства. Обычно они сделаны из полигональных моделей, а разделенные полигоны уже хранятся внутри узлов дерева.

А у меня нет, поэтому полигонов у меня нет. Каждый узел не имеет ничего, кроме своей секущей плоскости (например, заданной нормалью и исходным расстоянием). Таким образом, дерево по-прежнему представляет собой сплошной трехмерный объем, определяемый всеми сделанными разрезами. Однако для визуализации мне нужна полигональная сетка такого объема. Как это можно эффективно реконструировать?

Грубый метод состоял бы в том, чтобы преобразовать бесконечные полупространства листьев в достаточно большие многогранники (например, кубы) и подтолкнуть каждый из них вверх по дереву, разрезая его плоскостью каждого узла, которую он проходит. Это кажется очень затратным, так как дерево может быть несбалансированным (например, если тупо сделать из выпуклых многогранников). Есть ли классическое решение?


geometry space-partitioning bsp-tree
person dronus    schedule 17.06.2012    source источник
comment
Я не знаю ответа, но любой, кто работал над построителем узлов для порта DOOM, вероятно, делает, по крайней мере, для 2D случая. Может быть, эти алгоритмы можно распространить на 3D?   -  person finnw    schedule 18.06.2012
comment
Не думаю, что создателям DOOM это нужно. «Зоны» карты DOOM уже сделаны в виде полигонов в редакторе и имеют структуру BSP. Так что полигоны уже есть раньше.   -  person dronus    schedule 19.06.2012
comment
в портах OpenGL (например, zDoom) подсекторы должны быть закрытыми полигонами, поэтому, хотя сектора обычно закрыты, их необходимо разделить и реконструировать.   -  person finnw    schedule 20.06.2012
comment
Хорошо, я немного вник в DOOM, но я все же думаю, что полигоны строятся не из BSP, а берутся из входных вершин, возможно, добавляются вычисляемыми вершинами, чтобы разбить их на выпуклые части. Тем не менее, алгоритм генерирует новые вершины, разделяя существующие ребра (называемые linedef в DOOM, если я правильно понял) и добавляя subsectors. Таким образом, только существующие линии разделяются и соединяются, но никакие новые не рассчитываются только по разделенным плоскостям.   -  person dronus    schedule 22.06.2012

Ответы (1)


arrow_upward
1
arrow_downward

Чтобы восстановить многоугольную поверхность, вам нужно пересечь плоскости. Где каждая вершина многоугольника создается пересечением трех плоскостей, а каждое ребро - пересечением двух плоскостей. Но сделать это эффективным и численно стабильным — нетривиальная задача. Поэтому я предлагаю использовать qhalf, который является частью qhull. Документацию по вводу и выводу qhalf можно найти здесь. Конечно, вы можете использовать qhull (и функции qhalf) в качестве библиотеки.

person AD-530    schedule 23.10.2012