3.4. ИЗОБРАЖЕНИЕ ОСНОВНЫХ ПРИМИТИВОВ МЕТОДОМ ТРАССИРОВАНИЯ ЛУЧЕЙ

Алгоритм синтеза изображений требует конкретного описания правил изображения некоторых стандартных примитивов. К последним можно отнести многоугольники, многогранники, шары и эллипсоиды, параболоиды, цилиндры, конусы; поверхности типа экструзий; бикубические участки. В §3.4.1 - 3.4.4 подробно рассмотрены правила обработки примитивов на основе плоских многоугольников, многогранников, поверхностей второго порядка, бикубических поверхностей. Напомним, что поверхности типа экструзий образуются вращением некоторой ломаной линии вокруг заданной оси или с помощью параллельного переноса ломаной вдоль некоторой прямой. В первом случае поверхность представляют в виде усеченных конусов, соприкасающихся торцами, а во втором – в виде смежно расположенных многоугольников. В этом изложении примитивы такого вида специально не рассматриваются, так как могут быть составлены из независимых комбинационных частей. В [95,74] также могут быть найдены конкретные правила изображения основных примитивов методом трассирования лучей.

3.4.1. ПЛОСКИЕ МНОГОУГОЛЬНИКИ

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

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

(3.4.1)

или в матричном виде , где – координаты любой точки на плоскости; .

Иногда плоский участок задают тремя точками при условии, что они не принадлежат одной прямой. По этой информации можно восстановить уравнение плоскости (3.4.1) как это показано в программе PL3T (см. приложение).

Уравнение (3.4.1) описывает бесконечно простирающуюся плоскость. Реальные плоские детали ограничены замкнутой линией. Рассмотрим наиболее простой с вычислительной позиции случай, когда форма линии – многоугольник. Примерами таких плоских примитивов являются крыло самолета, поверхность стола, обложка книги и т.д. (рис. 3.4.1).

Рис. 3.4.1. Крыло самолета – пример плоского примитива

Граничные точки такого многоугольника оцифруем однообразно по (или против) часовой стрелке и запишем их координаты в матрицу

где – количество вершин многоугольника, .

Матрицы параметров уравнения плоскости и матрица граничных точек однозначно задают плоский участок объекта.

В соответствии с методом трассирования лучей необходимо найти пересечение прямой с данным примитивом. Координаты такого пересечения находят решением системы

где – координаты точки фокуса в системе ; – координаты -того рецептора в системе .

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

, (3.4.2)

где – орты осей соответственно; – знак логического умножения событий.

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

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

. (3.4.3)

Так как информация о поверхности, которой луч касается, но не пересекает, остается неопределенной для приемника света, то справедливо интерпретировать последнее условие как невидимость тонкой поверхности. Объединяя условия (3.4.2), (3.4.3) как условия невидимости, можно установить, что прямая не пересекается с плоскостью, если выполняется условие .

В противном случае решение единственно:

где – координаты пересечения луча и плоскости.

В программах PLOS, DIRECT (см. приложение) приведен пример реализации этого алгоритма на Турбо Паскале.

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

, .

Рис. 3.4.2. Проецирование многоугольника на координатную плоскость

Из проективной геометрии [51] известно, что если точка принадлежит внутренней части многоугольника (1-4), то проекция этой точки также принадлежит внутренней части проективного многоугольника (1'-4') (рис. 3.4.2), т.е. если точка и многоугольник лежат в одной плоскости, а проекция многоугольника не вырождается в отрезок прямой, то оценку принадлежности точки этому многоугольнику можно проводить в двухмерном пространстве (в данном случае на ).

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

. (3.4.4)

Для -ной прямой в последней записи следует заменить индекс на , a на первый.

Рис. 3.4.3. Участок выпуклого многоугольника

Напомним, что для определения факта принадлежности точки пересечения внутренней области многоугольника необходимо так установить знак функции для всех , чтобы значение этой функции во внутренней области многогранника было положительным. Априорно в этом нет уверенности, поэтому следует проверить экспериментально факт положительности внутренней области для всех прямых, а в случае отрицательности – изменить знак на противоположный. Заметим, что для всех точка под номером должна находиться в положительной полуплоскости относительно уравнения -й прямой, а для -й прямой такой точкой является точка под номером 1. Тогда вычислим значение функции и изменим знак функции на противоположный, если , т. е. проведем операцию . Таким образом, удалось добиться положительности внутренней области для первой прямой.

Для остальных прямых нет необходимости опытным путем оценивать их знак во внутренней области, так как они относятся к внутренней области точно так, как и первая прямая. Т. е., не только первая, но и все прямые должны быть преобразованы по правилу или, другими словами, при уравнение (3.4.4) изменяется: .

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

Введем знак , означающий или . Тогда справедливо , или .

Приведем доказательство. Рассмотрим участок выпуклого замкнутого многоугольника. Этот участок состоит из трех последовательных отрезков (ребер) под номерами и имеет соответственно угловые точки (вершины) (рис. 3.4.4). Так как многоугольник выпуклый, то и лежат по одну сторону плоскости от прямой I, следовательно

. (3.4.5)

Рис. 3.4.4. Определение факта освещенности или затененности плоскостей

Аналогично и лежат по одну сторону плоскости от отрезка , и тогда

. (3.4.6)

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

В соответствии со значением ; . Сравнивая правые части последних выражений, получаем , тогда из (3.4.5), (3.4.6) следует, что .

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

Процедура AVTOZON (см. приложение) реализует достижение положительности значения внутренней области сразу для нескольких выпуклых многоугольников путем оценки знака функции, описывающей первое по порядку ребро внутри многоугольника. Обработка многих многоугольников в одной процедуре связана с тем, что обычно в сцене присутствуют несколько плоских участков с одинаковым числом ребер.

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

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

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

, или , или .

В более компактном виде указывают двумерную матрицу размера и индикатор , который принимает значения 1, 2, 3. Если , то в матрице задана информация о координатах ; если ; если .

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

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

Для вычисления освещенности в видимой точке необходимо знать направление и ориентацию нормального вектора к плоскости. Известно, что нормальный вектор к плоскости записывается в виде . В соответствии с [44] этот вектор направлен в сторону положительного полупространства относительно плоскости, т.е., если – координаты конца нормального вектора , то . Так как участок плоскости является бесконечно тонким примитивом, т. е. не имеет внутренней области пространства, то при пересечении луча с плоскостью возникает неопределенность: какой же стороне плоскости принадлежит точка пересечения? Определение стороны весьма важно, так как при одном источнике освещения всегда выполняется следующий факт: если одна сторона плоскости освещена, то другая – в тени. Приведем один из возможных алгоритмов разрешения неопределенности, который может быть назван методом адаптивной нормали.

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

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

которая образуется путем присоединения к матрице столбца единиц. Необходимо определить координаты той же плоскости и координаты крайних точек – , но уже в другой системе координат . Данная задача эквивалентна перемещению многоугольника внутри одной и той же системы координат. Известно [60, 19], что для любой точки, имеющей координаты и в системах и соответственно, выполняется соотношение

, (3.4.7)

а для любой плоскости, издаваемой в указанных координатных системах соответственно матрицами и справедливо

. (3.4.8)

Матрица в формуле (3.4.7) имеет вид

(3.4.9)

где – координаты точки в системе ; – углы поворота системы последовательно вокруг осей соответственно до совпадения с осями системы (правое вращение). Тогда можно получить ; .

Рис. 3.4.5. Пример взаимного положения систем координат

При перемещении многоугольника происходит изменение коэффициентов уравнения плоскости и принципиально возможно неуправляемое изменение ориентации нормали, что может привести к грубым ошибкам при вычислении освещенности в тонах. На самом деле этого не происходит, что может быть доказано следующим образом. Покажем, что если в системе координат точка удовлетворяет для плоскости нестрогому неравенству , то знак неравенства сохраняется при перемещении и вращении системы координат по правилу (3.4.7), т. е. , где – координаты точки в новой системе координат ; – координаты уравнения плоскости в системе . Другими словами, знак полупространства относительно плоскости инвариантен к перемещению системы координат.

Действительно, ранее было показано, что справедливы выражения:

; (3.4.10)

. (3.4.11)

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