26. Алгоритм Робертса. Основные этапы и математические основы каждого этапа. - p1xelse/CG GitHub Wiki

Удаляет невидимые линии (ребра), работает в объектном пространстве.

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

Основные этапы решения задачи:
0. Подготовка исходных данных

  1. Удаление рёбер, экранируемых самим телом
  2. Удаление рёбер, экранируемых другими телами
  3. Удаление линий пересечения тел, экранируемых самими телами и другими телами, связанными отношением протыкания*.

*Если тела связаны отношением взаимного протыкания, то образуются новые ребра, соответствующие линиям пересечения тел. Вновь полученные рёбра надо проверить на экранирование самими телами, связанными отношением протыкания. Оставшиеся видимые части ребер надо проверить на экранирование другими телами сцены.

пункт 27 Здесь про формирование матрицы(этап 0) и этап 1

пункт 28 Здесь про этапы 2 и 3

Краткое содержание

Этап 0. Подготовка исходных данных.

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

Любая точка внутри тела должна располагаться по положительную сторону от каждой грани тела. Если для очередной грани это не выполняется, соответствующий столбец надо умножить на -1. Координаты точки внутри тела можно получить усреднением координат всех вершин тела. Находим произведение вектора координат полученной усредненной точки на матрицу тела. В результирующем векторе отрицательные элементы соответствуют столбцам, которые надо умножить на -1.

Этап 1. Удаление ребер, экранируемых самим телом.

Указываем расположение наблюдателя и направление его взгляда: наблюдатель располагается в бесконечности на оси Z и смотрит в сторону начала координат.

E = (0, 0, -1, 0) = вектор взгляда наблюдателя с одной стороны и вектор однородных координат точки в -бесконечности на оси Z.

Невидимые ребра образованы пересечением невидимых граней. Для определения невидимых для наблюдателя граней тела умножаем вектор E на матрицу тела(в итоге получим вектор 1xN):

  • Отрицательные компоненты результирующего вектора соответствуют невидимым граням тела.
  • Нулевые компоненты соответствуют граням на границе видимости/невидимости.
  • Положительные - видимым.

Если тело одно на сцене, достаточно для каждой грани тела найти скалярное произведение вектора взгляда на вектор внутренней нормали к грани. Для видимой грани - произведение положительно, для невидимой - отрицательно. Скалярное произведение = 0: грани находятся на границе видимости/невидимости.

Этап 2. Удаление невидимых рёбер экранируемых другими телами сцены.

Для определения невидимых точек ребра строим луч, соединяющий точку наблюдения с точкой на ребре. Точка невидима, если луч на своём пути встречает в качестве преграды тело, т.е. проходит через него.

Какие мат. объекты используем и как они задаются:

  1. Отрезок (ребро).
    Параметрическое уравнение отрезка: P(t) = P1 + (P2 - P1) * t, 0<=t<=1

  2. Луч. Уравнение луча: Q(t, al) = P(t) + al * g (уравнение плоскости, проходящей через отрезок и луч)

  • g - точка расположения наблюдателя,
  • al указывает с какой стороны от тела расположен наблюдатель:
    • al >= 0 - перед телом,
    • al < 0 - позади тела.

Вводим систему неравенств: H = Q * V hj > 0, j = 1..n
Для каждой компоненты вектора H требуем положительные значения. Невидимым точкам ребра P1P2 соответствуют такие значения параметров t и al, при которых выполняются все неравенства.

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

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

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

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

Этап 3. Удаление невидимых ребер, образованных линиями пересечения тел, связанных отношениями взаимного протыкания.

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

Вновь полученные рёбра надо проверить на экранирование самими телами, связанными отношением протыкания.

Оставшиеся видимые части ребер надо проверить на экранирование другими телами сцены.