3.4.2. ВЫПУКЛЫЕ МНОГОГРАННИКИ

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

,

где  – коэффициент уравнения для -й плоскости, , .

Плоскости, описывающие грани, простираются в бесконечность (рис. 3.4.6). Для того чтобы выделить из этого набора плоскостей центральное ядро-многогранник, зададим последнему особые свойства по сравнению с наружным относительно него полупространством. В соответствии с договоренностью о положительности внутренней области многогранника выберем знак функции каждой плоскости  таким, чтобы для любой точки , лежащей на поверхности или внутри многогранника, значение этой функции было неотрицательным: , где . Тогда для каждой плоскости положительное полупространство включает примитив, а отрицательное находится снаружи примитива.

Рис. 3.4.6. Выпуклый многогранник и образующие его плоскости

В соответствии с методом трассирования лучей необходимо найти координаты точек пересечения светового луча, проходящего через точки  – центр проекции и  – центр рецептора, с многогранником. Так как в общей случае прямая пересекает все плоскости, то сначала найдем решение  систем вида

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

,

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

,

где  – номер плоскости, которой принадлежит точка . Эта информация необходима для вычисления нормали к видимой точке.

Рис. 3.4.7. Пересечение луча с продолжением грани примитива

Некоторые точки пересечения из приведенных в последней матрице  хотя и принадлежат каким-то плоскостям, но могут не принадлежать поверхности многогранника. Такие точки лежат за пределами примитива и следовательно должны быть устранены из последующего анализа, как это необходимо сделать с точкой  на рис. 3.4.8. Осуществим операцию оценки знака функций всех плоскостей последовательно для всех точек. Введем матрицу  размера . Если выполняется условие

,

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

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

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

В программах KOROB и SOME (см. приложение) приведены примеры решений пересечения прямой и шестигранника. Подпрограмма KOROB определяет возможные переселения со всеми шестью плоскостями и среди них выбирает ближайшее решение-точку к центру проекции. Оценка расстояния между точками производится в объектной системе координат по одной-единственной координате , что является частным случаем общего алгоритма поиска ближайших точек. Выбор ближайшей точки осуществляется с помощью подпрограммы SOME. Результат, полученный с помощью подпрограммы KOROB, показан на рис. 3.2.4. Для изображения такого простого объекта нет необходимости обязательно применять столь мощное средство как метод трассирования лучей, однако как только сцена становится сложной: генерируются тени, проявляются криволинейные и прозрачные поверхности и другие эффекты, - применение этого метода становится оправданным. Если же сцена состоит только из выпуклых многогранников, то целесообразно использовать метод сканирующей строки или алгоритм Робертса (см. §4.2, 4.3).

Важной задачей в практике применения методов машинной графики является перемещение многогранника в объектном пространстве. Пусть многогранник задан исходно в правой прямоугольной системе координат  матрицей , тогда если новая система координат  связана со старой  матрицей преобразования : , то в системе  новые параметры плоскостей, сведенные в матрицу

,

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

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

Действительно, известно, что ; ; , тогда можно получить .

Многогранник можно перемещать и вращать относительно его исходного положения с помощью преобразования координат, не опасаясь нарушения общего алгоритма.