28. Алгоритм Робертса. Удаление отрезков, экранируемых другими телами.

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

Второй этап (самый интересный), удаление невидимых ребер, экранируемых другими телами сцены.

Введем новый вектор (типа), координаты точки в которой находится наблюдатель:

g = (0, 0, 1, 0)

Исследуем какое-нибудь ребро, чтобы определить его видимость начинаем "пускать лучи", если наблюдатель на +бесконечности, то лучи распространяются параллельно оси Z.

Точка, на этом отрезке, является невидимой, если луч встретил преграду из тела, то есть прошел через него.

Если луч располагается по положительную сторону от каждой грани тела, значит он проходит сквозь тело.

Для того чтобы найти все невидимые точки рассмотрим наше ребро в параметрической форме:

p(t) = P1 + (P2 - P1) * t, где P1 и P2 начало и конец ребра, a 0 <= t <= 1.

Используя его запишем уравнение луча (которое можно считать уравнением плоскости проходящим через луч и отрезок, так Куров сказал)

Q(t, alpha) = P(t) + alpha * g, где P(t) произвольная точка на ребре, а alpha >= 0 (что означает что наблюдать находится перед телом, при отрицательных значениях наблюдатель расположен с другой стороны тела)

Уравнение луча соединяет точку наблюдателя с произвольной точкой на луче.

Н = Q * V, h_j > 0, j=1,n (то есть луч располагается по положительную сторону от каждой грани тела)

Невидимым точкам ребра P1P2 соответствуют такие значения параметров t и alpha, при которых выполняются все неравенства.

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

Нам надо найти в этой области минимальное и максимальное значение параметра t.

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

В этой области найти минимальные и максимальные значения параметра t. t->min и t->max.

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

Вот что об этом пишет Куров (я ниче не понял простите мужики...(d - директрисса)):

Задача сложно решается программно: всего уравнений n + 3 (где n - количество граней, 3-количество ограничений, накладываемых на t и al: al >= 0, 0 <= t <= 1). Неизвестных больше чем уравнений, поэтому следует воспользоваться следующей процедурой:

1. Сформировать все возможные системы уравнений из k уравнений по 2 уравнения
2. Решить очередное уравнение
3. Полученные корни подставить во все другие уравнения.
4. Если полученные корни являются решениями всех уравнений, то они принимают участие в нахождении tmax, tmin.

Следующий вопрос: . Удаление невидимых линий и поверхностей в пространстве изображений. Алгоритм Варнока (разбиение окнами): последовательность действий и основные принципы.

Предыдущий вопрос: 27. Алгоритм Робертса. Формирование матрицы тела. Удаление нелицевых граней.