Трехмерное отсечение отрезков

Рис. 4.5

Существуют 2 наиболее распространенные формы трехмерных отсекателей:

¾ Прямоугольный параллелепипед (см. рис а);

¾ усеченная пирамида. (см. рис б);

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

— если конец отрезка левее объема;

— если конец отрезка правее объема;

— если конец отрезка ниже объема;

— если конец отрезка выше объема;

— если конец отрезка ближе объема;

— если конец отрезка дальше объема.

В противном случае в соответствующие биты заносятся нули.

Далее производится анализ кодов.

· если коды обоих концов отрезка равны 0, то оба конца видимы и отрезок тоже будет полностью видим;

· если коды содержат единичный бит в одной и той же позиции, то отрезок полностью невидим.

В остальных случаях отрезок может быть частично видим или полностью невидим. Необходимо определить пересечения отрезка с гранями отсекающего объема.

Поиск точки пересечения с гранями параллелепипеда является обобщением соответствующего двумерного алгоритма.

Сложнее ситуация, когда отсекатель — усеченная пирамида.

Вид усеченной пирамиды сверху:

Рис. 4.6

Теперь легко найти уравнение прямой на плоскости XZ, несущей проекцию правой грани отсекателя:

,

где .

Зная это уравнение, можно определить местоположение точки: справа (вне), на, или слева (внутри) от прямой. Подстановка координат x и z точки Р в функцию правой грани, дает результат:

	> 0, если Р справа от плоскости
=0, если Р на плоскости
< 0, если Р слева от плоскости

Аналогично находятся функции для других 5 граней.

	> 0, если Р справа от плоскости
=0, если Р на плоскости
< 0, если Р слева от плоскости

	> 0, если Р выше плоскости
=0, если Р на плоскости
< 0, если Р ниже плоскости

	> 0, если Р выше плоскости
=0, если Р на плоскости
< 0, если Р ниже плоскости

	> 0, если Р ближе к плоскости
=0, если Р на плоскости
< 0, если Р дальше от плоскости
	> 0, если Р ближе к плоскости
=0, если Р на плоскости
< 0, если Р дальше от плоскости

При , формы отсекателя стремятся к прямоугольному параллелепипеду, функции стремятся к функциям прямого параллелепипеда.

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