УДАЛЕНИЕ НЕВИДИМЫХ ЧАСТЕЙ
3.1. Отброс нелицевых граней

Пусть у нас есть объект, внутри которого камера заведомо не окажется. Обычно такие объекты составляют большую часть или всю сцену. Тогда для каждой грани мы можем увидеть только одну ее сторону - лицевую. Грань - плоскость, она делит все 3D пространство на два полупространства. Так вот, лицевую сторону видно только из одного полупространства, из того, в которое "смотрит" нормаль к этой грани, направленная *из* объекта. Проверив, в какое полупространство попадает камера, можно сразу определить, является ли грань лицевой (то есть, может ли камера увидеть лицевую сторону этой грани) и надо ли ее рисовать.

Пусть грань имеет вершины v1, v2, v3 и нормаль (nx,ny,nz). Тогда уравнение плоскости, в которой она лежит, будет иметь вид

nx*x+ny*y+nz*z+d = 0.

d находим из того факта, что v1 в плоскости лежит:

nx*v1.x+ny*v1.y+nz*v1.z+d = 0,
d = -(nx*v1.x+ny*v1.y+nz*v1.z).

Функция nx*x+ny*y+nz*z+d принимает положительные значения по одну сторону от плоскости, отрицательные по другую и равна нулю на самой плоскости. Точка (v1.x+nx,v1.y+ny,v1.z+nz) лежит, очевидно, в том полупространстве, откуда грань видно. Значение функции (назовем ее функцией видимости) в этой точке равно

nx*(v1.x+nx)+ny*(v1.y+ny)+nz*(v1.z+nz)+d =
nx*(v1.x+nx)+ny*(v1.y+ny)+nz*(v1.z+nz)-(nx*v1.x+ny*v1.y+nz*v1.z) =
nx*nx+ny*ny+nz*nz > 0.

Таким образом, если значение функции в какой-то точке больше нуля, то грань из этой точки потенциально видна. Нас интересует видимость грани из нашей камеры, а камера у нас зафиксирована в точке (0,0,-dist). Таким образом, получаем, что грани, для которых

-nz*dist-(nx*v1.x+ny*v1.y+nz*v1.z) < 0,

или, что равносильно,

nz*dist+nx*v1.x+ny*v1.y+nz*v1.z > 0,

заведомо не видны и время на их обработку и отрисовку тратить не стоит.

Отдельный вопрос - как считать нормали к граням. Точнее, как выбрать одну из двух нормалей, которая будет смотреть из объекта. Обычно эта проблема решается еще на этапе построения 3D моделей - например, пакет 3D Studio записывает вершины граней в порядке A-B-C так, чтобы векторное произведение BA*CA и было нормалью. Еще один способ - выбрать внутренную точку для объекта (либо вручную, либо взять его центр тяжести, либо еще как-нибудь - методов может быть придумано сколько угодно) и использовать ее: если для этой точки функция видимости положительна, то есть грань якобы видна, то надо поменять знак nx, ny и nz.

Осталось отметить, что для выпуклых объектов этот метод полностью решает задачу об удалении невидимых частей. Для невыпуклых же он позволяет быстро и просто сократить число граней, подлежащих дальнейшей проверке на видимость и собственно отрисовке.