Определение выпуклости трехмерного тела

Трехмерное отсечение

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

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

- в первый бит, если конец ребра левее объема;

- во второй бит, если конец ребра правее объема;

- в третий бит, если конец ребра ниже объема;

- в четвертый бит, если конец ребра выше объема;

- в пятый бит, если конец ребра ближе объема;

- в шестой бит, если конец ребра дальше объема.

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

Поиск кодов точки пересечения относительно отсекающего прямоугольного параллелепипеда является прямым обобщением соответствующего двумерного алгоритма. Двумерный алгоритм разбиения средней точкой, рассмотренный ранее, непосредственно обобщается на случай трех измерений. При программной реализации этого алгоритма нужно изменить размерности массивов. В двухмерном варианте алгоритма Кируса-Бека на форму отсекателя не накладывалось никаких ограничений, за исключением выпуклости. Поэтому и в трехмерном варианте отсекатель может быть произвольным выпуклым объемом. Все векторы будут иметь по 3 компоненты (x,y,z).

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

Для каждой грани тела выполнить:

1) перенести тело так, чтобы одна из вершин граней оказалась в начале координат;

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

3) повернуть тело вокруг выбранной оси так, чтобы выбранная грань легла на координатную плоскость (плоскость z=0);

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

- если эти знаки для всех вершин совпадают или равны нулю, то тело будет выпуклым относительно выбранной грани. Если тело выпукло относительно всех своих граней, то оно считается выпуклым, в противном случае – тело не выпукло;

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

5) вектор внутренней нормали к выбранной плоскости заданный в повернутой системе координат имеет все нулевые компоненты, кроме той, которая перпендикулярна этой плоскости. Знак этой компоненты для выпуклой грани будет совпадать с раннее найденным знаком;

6) для определения искомой ориентации внутренней нормали в исходной системе координат необходимо применить к ней обратное преобразование поворотов.