Q(a,t) = u = v + ga = s + dt + ga 0 £ t £1, a ³ 0

Здесь a и t выполняют аналогичные функции. Заданное значение t ука­зывает точку на отрезке P(t), а a указывает точку на отрезке, прове­денном от точки P(t) до точки наблюдения. Фактически Q(a,t) представляет собой плоскость в трехмерном пространстве. Пара (a,t) определяет точку на этой плоскости. Значение a положительно, по­скольку тела, экранирующие P(t) могут находиться только в той части этой плоскости, которая заключена между отрезком P(t) и точкой наблюдения.

Скалярное произведение любой точки, лежащей внутри тела, на матрицу тела положительно. Если же точка лежит внутри тела, то она невидима. Поэтому для определения части от­резка, которая экранируется телом, достаточно найти те значения a и t, для которых скалярное произведение Q(a,t) = u на матрицу тела положительно. Это скалярное произведение равно:

h = u * [VT] = s * [VT] + td * [VT] + ag * [VT] >0 0 £ t £ 1, a ³ 0

Если все компоненты h неотрицательны для некоторых t и a, отрезок при этих значениях t экранируется данным телом. Обозначим

p = s * [VT]

q = d * [VT]

w = g * [VT]

запишем условия в виде

hj = pj + tqj + awj 0 £ t £ 1, a ³ 0

где j - номер столбца в матрице тела. Эти условия должны выполняться при всех значениях j, т. е. для всех плоскостей, ограничивающих объем тела. Пограничный случай между видимостью и невидимостью возникает, когда hj = 0. При hj = 0 точка лежит на плоскости. Полагая hj = 0 для всех плоскостей, мы

получим систему уравнений относительно a и t, которые должны удовлетворяться одновременно. Результат можно получить путем совместного решения всевозможных пар уравнений из этой системы, при этом будут найдены все значения a и t, при которых изменяется значение видимости отрезка. Схема решения показана на рис. 3.10. Число возможных решений при j уравнениях (плоскостях) равно j(j - 1)/2. Каждое решение в диапазонах 0 £ t £ 1, a ³ 0, подставляется во все остальные уравнения для проверки того, что условие hj ³ 0 выполнено. Поиск корректных решений производится для того, чтобы найти минимальное среди максимальных значений параметра t(tminmax)

и максимальное среди минимальных значений t(tmaxmin). Отрезок невидим при (tmaxmin) < t < (tminmax). Последнее требование является простым следствием из классической задачи линейного программирования.

Решение на границе a = 0 возникает в случае протыкания (объектов).

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

Из практики известно, что решения удовлетворяющие неравенствам hj > 0, могут существовать и за пределами области, ограниченной условиями 0 £ t £ 1 и a = 0. Поэтому три уравнения, описывающие эти границы, т.е. t = 0, t - 1 = 0 и a = 0, нужно добавить к множеству уравнений hj = 0. Теперь число решений равно (j + 2)(j + 3)/2, где j - количество плоскостей, ограничивающих выпуклый объем тела.

Как упоминалось ранее, выбор максимального из минимального и минимального из максимальных значений t среди возможных корректных решений указанной системы уравнений является простой задачей линейного программирования. Ее решение эквивалент­но определению корректной ограниченной области, получающейся в результате графического решения. Предпо­лагается, что этот алгоритм используется только для таких отрез­ков, о которых известно, что они частично или полностью невидимы. Все нелицевые и все полностью видимые отрезки выявлены и удалены до начала работы алгоритма. Алгоритм начинает работу с такими значениями t и a, которые являются решениями пары ли­нейных уравнений с номерами е1и е2, а также с tmin и tmax (текущими минимальным и максимальным значениями t) и с n (мощностью множества уравнений). На первом этапе алгоритма проверяется выполнение условий hj > 0. Если эти условия выполнены, то на втором этапе вычисляются значения tmin и tmax. Результатом являются значения tmaxmin и tminmax.

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

u = s + td + ag

При a = 0 значение u задает сам отрезок. Далее, если a = 0, при t = 0 и t = 1 получаются концевые точки отрезка. Также известно, что

hj = u *[VT] = pj + qjt+ wja

и заметим, что при t = 0 pj является скалярным произведением концевой точки отрезка и j-й плоскости, ограничивающей тело. Аналогично pj + qj является скалярным произведением другой концевой точки отрезка и j-й плоскости, ограничивающей тело. Наконец, напомним, что j-я плоскость, ограничивающая тело, видима, если wj = 0. Поэтому, если wj £ О и pj£ 0, то один конец отрезка лежит или на видимой плоскости или между видимой плоскостью и точкой наблюдения. Если же pj + qj £ 0, то другой конец отрезка также лежит либо на видимой плоскости, либо между этой плоскостью и точкой наблюдения. Следовательно, отрезок полностью видим, если для любого j

wj £ О и pj£ 0 и pj + qj £ 0.

Эти условия гарантируют, что неравенства hj £ 0 не могут быть выполнены ни при каких a ³ 0 и 0 £ t £ 1. Поэтому никакая часть отрезка не может быть невидимой, т. е. отрезок полностью видим.

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