Рисование столкновения на экране

Question

А вот и мы по другому вопросу.

После предыдущего я, наконец, завершил систему kDop и все, что с ней связано. (Иерархическое дерево kDop и др.) Все отлично работает.

Теперь я хочу нарисовать на экране столкновение с целью отладки и увидеть результат работы. (Чтобы проверить, подходит ли иерархический выбор, который я сделал в определенном режиме, или нет)

Для AABB / Sphere нет проблем, его довольно легко создать. Проблема с kDOP ...

У меня есть:

осях (1,0,0) (0,1,0) (0,0,1) (1,1,1) (- 1,1,1) (1, -1,1) (1,1, - 1) (1,1,0) (1,0,1), (0,1,1), (1, -1,0), (1,0, -1), (0,1, -1 ) и значения Min / Max, рассчитанные с использованием осей.

Как я могу создать серию многоугольников (на самом деле простая сетка) с этими данными? (Меня не волнует реализация, я просто хочу понять это теоретически, чтобы я мог реализовать это)

Большое спасибо за ответы !!!

РЕДАКТИРОВАТЬ: Я могу легко вычислить нормали сетки, потому что у меня уже есть ось. Проблема в расчете позиции вершины ...

РЕДАКТИРОВАТЬ 2: Я нашел в сети этот код, который кажется полезным (или, по крайней мере, в документе, где написано, что он создает отладочную сетку), но я не знаю, как его использовать, чтобы найти позицию вершины. :

    real Kdop::getDistanceOfPlaneToOrigin(int k) const {
        if (k < 0 || k >= mK) {
            return 0.0f;
        }
        if (k >= mK/2) {
            return (real) (mDistances[k] * -1.0);
        }
        return mDistances[k];
    }

РЕДАКТИРОВАТЬ 3: Я думал и имея нормальные точки и точку (начало координат, я уверен, что самолет перешел), я могу построить все самолеты, связанные с операцией ... Теперь мне нужно что-то еще ... .

Answer 1

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

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

Да, и чтобы вычислить фактические вершины на основе плоскостей, посмотрите эту страницу математического мира .

[edit:] - На самом деле, вы можете значительно упростить поиск, если точно знаете, что ни один из ваших самолетов не является избыточным (т.е. если ни один из них не находится полностью вне вашего kDop). В этом случае ваш kDop имеет стандартную структуру, каждый полигон имеет фиксированную конфигурацию соседей; в этом случае вы можете просто подключить свои плоскости, вычислить фиксированный набор вершин и нарисовать с ними стандартную фигуру. Вы можете легко (хотя и несколько утомительно) проработать все детали вручную.

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

[edit2:] - В дальнейшем я думаю, что ваша конфигурация может быть не полностью исправлена. Например, скажем, есть 4 соседних самолета; и исходя из их глубины, грань между ними может идти так или иначе, например:

plane A     |    plane B
            |
           / \
          /   \
         /     \
________/       \
        |        \
        |         \
plane C | plane D  \

        vs.

plane A |    plane B
        |
        |
________|
         \
          \
          |\
          | \
          |  \
          |   \
          |    \
          |     \
          |      \
          |       \
          |        \
plane C   | plane D \

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

Answer 2

Вы смотрели на алгоритм марширующего куба? (http://en.wikipedia.org/wiki/Marching_cubes)

Я не знаю, можно ли использовать его как есть, но вы, вероятно, можете вдохновить себя на это.