exam26 - MiAneko24/bmstu-cg GitHub Wiki
26. Алгоритм Робертса. Основные этапы и математические основы каждого этапа.
РОБЕРТ КТО ТАКОЙ
У кого этот вопрос, соболезную.
Алгоритм Робертса удаляет невидимые линии. Для него необходимо чтобы все изображаемые тела были выпуклыми. Если тело невыпуклое необходимо разбить его на выпуклые составляющие
Основные этапы решения задачи:
- Подготовка исходных данных
- Удаление рёбер (или граней), экранируемых самим телом
- Удаление рёбер, экранируемых другими телами
- Удаление линий пересечения тел, экранируемых самими телами, связанными отношением протыкания и другими телами
В этом алгоритме выпуклое многогранное тело должно представляться набором пересекающихся плоскостей. Уравнение произвольной плоскости имеет вид:
ax + by + cz + d = 0
Тогда любое выпуклое твердое тело можно выразить матрицей тела, состоящей из коэффициентов уравнений плоскостей
(вот вопрос к вам мужики, надо найти коэффы, а у нас какбы КГ а не вычалг че может не надо про это писать?)
Матрица тела должна быть сформирована корректно, то есть любая точка, расположенная внутри тела, должна располагаться по положительную сторону от каждой грани тела (при подстановке координат точки в уравнение результат положителен). Если для очередной грани это условие не выполняется, то соответствующий столбец матрицы надо умножить на -1.
Как тестирующую точку можно взять барицентр.
Если вдруг необходимо также преобразовать тело, то надо матрицу исходного тела слева умножить на обратную матрицу преобразования:
Cледующий этап, удаление ребер, экранируемых самим телом.
Необходимо определить вектор взгляда наблюдателя, если наблюдатель располагается в +бесконечности на оси Z и смотрит в сторону начала координат:
E = (0, 0, -1, 0) = вектор взгляда наблюдателя.
Для определения невидимых граней следует вектор Е умножить на матрицу тела V. Отрицательные компоненты полученного вектора будут соответствовать невидимым граням. Невидимые ребра образуются пересечением невидимых граней.
Если тело одно, алгоритм закончен.
Второй этап (самый интересный), удаление невидимых ребер, экранируемых другими телами сцены.
Введем новый вектор (типа), координаты точки в которой находится наблюдатель:
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 (то есть луч располагается по положительную сторону от каждой грани тела, hj это нормали походу..)
Невидимым точкам ребра P1P2 соответствуют такие значения параметров t и alpha, при которых выполняются все неравенства.
Система неравенств задает область допустимых решений. Все точки расположенные внутри области определяют координаты невидимых точек отрезка.
Нам надо найти в этой области минимальное и максимальное значение параметра t.
Система неравенств задаёт область допустимых решений. Все точки, расположенные внутри области, дают координаты невидимых точек отрезка. Необходимо найти в этой области минимальное и максимальное значения параметра t - задает координаты начала и конца невидимой части отрезка.
Целевая функция линейна - производная постоянна, поэтому минимальное и максимальное значения достигаются на границах области.
Вот что об этом пишет Куров (я ниче не понял простите мужики...(d - директрисса)):
Задача сложно решается программно: всего уравнений n + 3 (где n - количество граней, 3-количество ограничений, накладываемых на t и al: al >= 0, 0 <= t <= 1). Неизвестных больше чем уравнений, поэтому следует воспользоваться следующей процедурой:
- Сформировать все возможные системы уравнений из k уравнений по 2 уравнения
- Решить очередное уравнение
- Полученные корни подставить во все другие уравнения.
- Если полученные корни являются решениями всех уравнений, то они принимают участие в нахождении tmax, tmin.
Этап 3. Удаление линий пересечения тел, экранируемых самими телами, связанными отношением протыкания и другими телами
Этап 3 Куров тактично пропустил, но вот что известно.
Решения на границе alpha = 0 возникают в случае протыкания, это Куров спрашивает.
Решается протыкание при помощи запоминания всех точек протыкания и добавлении к сцене отрезков, связывающих эти точки. Отрезки образуются путем соединения каждой точки протыкания со всеми остальными точками протыкания для этой пары объектов. Затем проверяется экранирование этих отрезков данными и другими телами. Видимые отрезки образуют структуру протыкания.
Следующий вопрос: 27. Алгоритм Робертса. Формирование матрицы тела. Удаление нелицевых граней.