Компьютерная геометрия и графика. Лекция 10

План занятия: Алгоритм Робертса.

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

Разбиение произвольного многогранника на выпуклые части.

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

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

Удобно переносом и поворотом системы координат сделать так, чтобы рассматриваемая грань лежала в плоскости Oxy. Почему? Потому что легче находить пересечение не с произвольной плоскостью, а с плоскостью Oxy. Если вершины имеют разные знаки по Z значит они лежат по разные стороны грани. ?

Разбиение на выпуклые многогранники не единственно и зависит от порядка рассмотрения граней.

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

По координатам вершин грани построить плоскость, которая их содержит. Метод Ньюэла.

Для начала по вершинам восстанавливаем положение граней. AX+BY+CZ+D=0 - уравнение плоскости. Метод Ньюэла:

В итоге получаем матрицу V[4xM] (М-число граней): Эта матрица называется матрицей тела.

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

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

Пусть матрица Т - преобразование системы координат. Тогда если мы хотим повернуть или сдвинуть тело, мы заново берем массив координат В, умножаем его на матрицу перехода Т, получаем новый массив координат Вt=В*Т теперь заново придется применять метод Ньюэла, заново находить матрицу тела. Это неудобно. Попробуем понять как связана матрица тела Vt после преобразования, со старой матрицей тела V. BV=B t V t =BTV t V=TV t V t =T -1 V

Грань является видимой тогда, когда знак при подстановке в матрицу отрицательный.

Смотрим из точки W=(0, 0, -1, 0) ; (a i,b i,c i ) направлен внутрь многоугольника, а мы смотрим из точки w. Подстановка в матрицу дает информацию о видимости Если c i >0, то грань видима, иначе невидима. Алгоритм Робертса по сути рисует ребра: Не рисуем только те ребра, которые являются пересечением двух невидимых граней

Если многогранников несколько, то можно для каждого многогранника решить эту задачу. Сколько многогранников, столько матриц. Можно сделать так, чтобы хранить меньше матриц в памяти. Вопрос: какие ребра видимые? Видимое ребро - пересечение двух граней, из которых хотя бы одна видима.

Возьмем ребро одного из многоугольников, получившихся при пересечении видимой и видимой грани, или невидимой и видимой грани. Вводим параметр. Тогда любая точка на этом отрезке определяется как P=(P x,P y,P z ) R=R(t)=P+(Q-P)t t [0,1] Рассматриваем часть плоскости, которая направлена от этого отрезка перпендикулярно экрану. Каждая точка этой плоскости тоже может быть задана параметрически. P Q U V

Это обобщенные координаты точки, которая находится где-то в пространстве перед отрезком. Она как-бы заслоняет точку R от нас. В этой формуле: t [0,1] 0 U, V, W - конкретные значения - каждое по четыре координаты. W - постоянный вектор U+V*t+W*

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

Подставляем в уравнение граней и получаем два уравнения с двумя неизвестными: Из них мы находим t и. Мы нашли точку пересечения ребра многогранника с этой плоскостью. U+V*t+W*

Ищем эту точку. P Q Проверяем, действительно ли t [0,1], 0. Если ДА, то действительно точка пересечения (t, ) Тогда мы нашли точку пересечения. По t и можно восстановить (x, y, z). Допустим точки пересечения получены.

К этим системам надо добавить еще три: Грань t=1 Грань t=0 Грань =1

Находим t min и t max t min < t < t max t - та часть отрезка, которая невидима. Мы нашли часть отрезка, которая заслоняется многогранником. Результат: P Q R Теперь надо продолжить работу, но уже с другими многоугольниками.

Н е обязательно рассматривать для каждого ребра все многогранники. Задачу можно чуть-чуть упростить. Рекомендуется все многогранники упорядочить по расстоянию от нас. Но чаще всего очень трудно определить, какая грань ближе к нам, а какая дальше. Сортируем по самой ближайшей точке. После упорядочения нет гарантии того, что именно в таком порядке надо это изображать. Сортировкой мы добиваемся того, что рассматриваем не все многогранники для данного ребра, а те чья ближайшая вершина ближе чем наше ребро.

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

Допустим мы изобразили все видимые ребра всех видимых многогранников. Очевидно, что в этом изображении присутствует ошибка: не хватает ребер.

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

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

КОНЕЦ