3.3. ОПРЕДЕЛЕНИЕ ВИДИМЫХ И ЗАТЕНЕННЫХ ТОЧЕК

Для определения освещенности изображения необходимо установить для каждого рецептора, какую точку объекта он "видит", каковы ориентация нормали в этой точке, отражательную способность и другие необходимые данные. Пусть объект  содержит  примитивов , которые пространственно комбинируются друг с другом в форме (3.2.2), (3.2.3). Обозначим  число поверхностей, слагающих -й примитив; соответственно – текущая -я поверхность в примитиве под номером ; . Степень функции -й поверхности обозначим . В этих обозначениях определим пересечения светового луча: сначала с каждым примитивом, а затем со всем объектом.

3.3.1. ПЕРЕСЕЧЕНИЯ СВЕТОВОГО ЛУЧА С ПРИМИТИВОМ

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

                 (3.3.1)

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

Исключим последнюю группу решений из-за неопределенности положения точки пересечения. В общем же случае каждая -я система может давать  решений. Но все точки-решения принадлежат поверхности примитива. Точка решения , принадлежащая поверхности , принадлежит поверхности -го примитива при выполнении условия  – номер текущего решения для -й поверхности, ;  – текущий номер поверхности в -м примитиве.

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

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

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

и матрицы номеров поверхностей, которым принадлежат точки  и :

.

Для случая одинаковых решений (одного решения) каждая матрица имеет одну строку.

Ключевые элементы алгоритма определения точек пересечения прямой и примитива выглядят следующим образом.

1. Устанавливают , где  – номер обрабатываемой поверхности в составе примитива . Устанавливают , где  – индикатор отсутствия (0), наличия (1) решений.

2. Решают систему (3.3.1).

3. Если решений нет, то  (пока ) и возврат на шаг 2.

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

5. Для всех  поверхностей, кроме -й проверяют условие  , .

6. Если условие не выполняется, то  (пока ) и возврат на шаг 5.

7. Если условие 5 выполняется и , то точка  размещается в две первые строки матрицы , а WHO заполняется: .

8. Если условие 5 выполняется и , то алгоритм ветвится: если  ближе к точке , чем точка из первой строки матрицы , то , ; если же  дальше от , чем точка во второй строке матрицы , то , .

9. ,  (пока ), возврат на шаг 2.

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