как "отсортировать" полигоны 3d?

Question

Я все еще работаю над моим "javascript 3d engine" ( ссылка внутри stackoverflow ).Сначала все мои многоугольники были гранями кубов, поэтому сортировка их по среднему Z работала нормально.но теперь я «эволюционировал» и хочу нарисовать свои полигоны (которые могут содержать более 4 вершин) в правильном порядке, а именно те, кто находится рядом с камерой, будут нарисованы последними.

в основномЯ знаю, как вращать их и «перспективно» изменять их размер в 2D, но не знаю, как нарисовать их в правильном порядке.

просто чтобы уточнить:

//my 3d shape = array of polygons
//polygon = array of vertices
//vertex = point with x,y,z
//rotation is around (0,0,0) and my view point is (0,0,something) I guess.

может кто-нибудь помочь?

ps: некоторые «ловить фразы», ​​которые я придумал, в поисках решения: z-буферизация, приведение лучей (?!), уравнения плоскости, вектор представления и т. д. - угадайте, янужен простой, чтобы понять ответ, поэтому я и спросил этот.спасибо.

p.s2: я не особо беспокоюсь о перекрывающихся или пересекающихся многоугольниках ... так что, возможно, алгоритм художника действительно может быть хорошим.но: что именно?Как я могу определить расстояние многоугольника?у многоугольника много точек.

Answer 1

Подход сортировки полигонов с последующим рисованием их снизу вверх называется «алгоритмом художника».К сожалению, шаг сортировки, как правило, является неразрешимой проблемой, потому что возможно, чтобы 3 многоугольника перекрывали друг друга:

http://i54.tinypic.com/ju8umr.jpg

Таким образом, не обязательно, чтобы какой-либо многоугольник находился "сверху",Альтернативные подходы, такие как использование буфера Z или дерева BSP (которое включает в себя расщепление полигонов), не страдают от этой проблемы.

Answer 2

как мне определить расстояние многоугольника ??у многоугольника много точек.

Алгоритм Painter проще всего реализовать, но он работает только в очень простых случаях, поскольку предполагает, что для каждого многоугольника существует только одно «расстояние» или значение z(который вы можете аппроксимировать как среднее значение z-значений всех точек в многоугольнике).Конечно, это приведет к неправильным результатам, если два многоугольника пересекаются друг с другом.

На самом деле, для многоугольника не существует единого значения расстояния - каждая точка на поверхности многоугольника может находиться на разныхрасстояние от зрителя, поэтому каждая точка имеет свое собственное «расстояние» или глубину.

Вы уже упоминали Z-буферизация , и это один из способов сделать это.Я не думаю, что вы можете реализовать это эффективно на холсте HTML, но вот общая идея:

1. Вам нужно поддерживать дополнительный холст, "z-буфер", где каждыйцвет пикселя представляет собой глубину z соответствующего пикселя на главном холсте.

2. Чтобы нарисовать многоугольник, вы проходите каждую точку на его поверхности и рисуете только те точки, которые ближе ксредство просмотра, чем любые предыдущие объекты, как указано в z-буфере.

Answer 3

Я думаю, у вас будут некоторые идеи, исследуя дерево BSP (дерево разбиения двоичных пространств), даже если алгоритм потребует разбить часть вашего многоугольника на две части.Некоторые примеры могут быть найдены здесь http://www.devmaster.net/articles/bsp-trees/ или Google для дерева BSP.Публиковать код в качестве ответа, на мой взгляд, несерьезно, поскольку это сложная тема.