Получите 2D вогнутый многоугольник из 3D-объекта

Question

В настоящее время у меня заканчивается время для моего 3D-проекта, поэтому я решил передать всю физику и столкновения Box2D , так как мой проект будет использовать только 2d-столкновения, но есть 3D-графика.

Мир Box2D был бы сверху, поэтому мне нужно взять мой 3D-объект и свернуть в двумерный многоугольник. Это так же просто, как удаление координаты из каждой вершины, но Box2D не хотела бы кучи вершин перекрывающейся фактический объекта:

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

или ген повысить рейтинг OOBB?

EDIT: Теперь я понимаю, что Box2D принимает только выпуклые формы! Но это может быть полезно для других библиотек с более точной физикой.

Спасибо!

Answer 1

Для вычисления двумерного представления 3D-объекта одним из возможных подходов является растеризация: вы создаете двоичное растровое изображение вашего объекта из вида сверху («двоичный» означает, что каждый пиксель только черный или белый), а затем вы либо используете набор черных пикселей в качестве представления 2D-объекта, либо если вы все еще хотите использовать многоугольник, вы запускаете алгоритм обхода границ, чтобы рассчитать последовательность пикселей, которые составляют границу этого 2D-объекта. Точность этого алгоритма определяется разрешением пикселя. Одной из таких реализаций является OpenCV's findContours (http://docs.opencv.org/2.4/doc/tutorials/imgproc/shapedescriptors/find_contours/find_contours.html).

Как только у вас есть последовательность пикселей, вам может потребоваться упростить полилинию, чтобы сохранить количество вершин, чтобы последующие операции с этой полилинией выполнялись быстрее. (См http://doc.cgal.org/latest/Polyline_simplification_2/index.html)

---

В целом, если вы делаете столкновения, вы должны начать, решая, насколько точным вам необходимо обнаружение столкновений быть. Если вы хотите, чтобы обнаружение столкновения высокой точности 3D, то сглаживание в 2D не является хорошим подходом. Итак, если вам нужна высокая точность и высокая производительность, вам нужно выполнить некоторую предварительную обработку в вашей сетке, например, вычислять иерархическое дерево выровненных по оси ограничивающих прямоугольников или ограничивающих сфер (https://en.wikipedia.org/wiki/Bounding_volume_hierarchy). Если ваши объекты подвергаются жестким преобразованиям, то ограничивающие сферы хороши, потому что сфера остается сферой под жесткими преобразованиями, где, когда ограничивающие прямоугольники не выравниваются по оси после их вращения.