Конспект лекций по дисциплине «Компьютерная геометрия и графика» Лекция 3

Тема 4 - Геометрические модели

Растровая модель – часть плоскости или пространства (рис.1.2) в виде прямоугольной матрицы в системе координат с направлениями осей x ,y, z и конечным числом элементов по осям i, k, l соответственно. Элементом плоской матрицы является пиксел, а элементом объемной матрицы является воксел. Общее число элементов в плоской матрице , общее число элементов в объемной матрице .

Рис.1.2

В растровой модели элементы записываются последовательно в виде чисел в порядке следования (рис.1.3) от начала системы координат вначале по оси x, затем с переходом на следующую строку по оси z, а после прохождения плоскости xz, с переходом на следующую плоскость по оси y.

Рис.1.3

Там, где в пространстве отсутствует записываемый графический объект, пиксел или воксел имеет значение нуль, там, где присутствует объект, пишется число, характеризующее элемент записываемого графического объекта. Например, в двоичной системе элементы, принадлежащие графическому объекту, записываются как единицы, в цветовой гамме записываются как номер цвета (отличный от нуля, так как нуль это отсутствие в данном месте графического объекта), в температурной гамме записывается значение температуры и т.п. Таким образом, мы имеем запись всех элементов выделенного пространства, и принадлежащих графическому объекту, и пустых.

Математическое описание трехмерной растровой модели имеет вид .

В компьютерной модели в массив описания последовательно записываются значения . Порядок записи, чтения и объем данных определяется записью в начале массива значений i, k, l.

Растровая модель может иметь записи, как элементов поверхности графического объекта, так и его тела.

Точность описания графического объекта растет с увеличением общего числа элементов растровой модели.

Когда элемент матрицы принимает только двоичное значение ноль или 1, то такую модель называют рецепторной (рецептор либо возбужден, либо нет). Такая модель наиболее экономична в записи, но описывает только наличие объекта.

Элемент матрицы может содержать описание свойств объекта в данной точке, например, цвет, температуру, твердость и т.п., но при этом будет резко возрастать объем записи модели.

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

Точечная модель – последовательная запись n – числа точек с координатами x,y,z и их свойствами c, d ,t… (цвет, плотность, температура и т.п.), из которых состоит поверхность или тело графического объекта.

Математическая формула описания точек поверхности или тела точечной модели .

В компьютерной модели точки записываются в массив описания в произвольном порядке.

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

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

Аппроксимация - соединение контрольных точек поверхности между собой отрезками прямых линий (векторами). Моделирование поверхности с использованием метода аппроксимации дает нам линейную каркасную модель.

Интерполяция – соединение контрольных точек поверхности между собой отрезками кривых линий с условием гладкости и сохранением в местах сшивки непрерывности более или менее высокого порядка (сплайнами). Моделирование поверхности с использованием метода интерполяции дает нам нелинейную каркасную модель.

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

Линейные каркасные модели дают граненые поверхности, а нелинейные каркасные модели дают гладкие поверхности. И линейные, и нелинейные каркасные модели отличаются от поверхности-оригинала.

Увеличение точности приближения поверхности каркасных моделей к криволинейной поверхности-оригиналу требует увеличения числа линий каркасной модели.

Линейная каркасная модель. Она известна и под другими названиями: векторная модель, треугольные сети, полигональная модель. В плоскости кривые линии задаются отрезками прямых линий (векторов), а в пространстве кривые поверхности задаются кусочками плоскостей (треугольниками, многоугольниками, ряд авторов называет их полигонами).

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

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

Вершины хранятся в том порядке, в котором они будут встречаться, обходя вокруг многоугольника. Между соседними вершинами и между первой и последней вершиной располагаются ребра. Для одного многоугольника такое представление эффективно по затратам компьютерной памяти. Для линейной каркасной модели, однако, много компьютерной памяти тратится за счет дублирования записи вершин, разделяемых разными многоугольниками. Хуже того, нет явного представления разделяемых ребер и вершин. Например, чтобы передвинуть вершину и все ее инцидентные ребра интерактивно, мы должны найти все многоугольники, которые разделяют эту вершину. Это требует сравнение троек координат одного многоугольника со всеми другими многоугольниками. Наиболее эффективный путь сделать это – отсортировать все N координатные тройки, но это в лучшем случае процесс сложности, при этом есть опасность, что из-за ошибок точности или округления мы не распознаем вершины, находящиеся в одинаковом положении как одинаковые. Это заставляет трансформировать каждую вершину и отрезать каждое ребро многоугольника. Если выводить на экран или печать ребра, то каждое ребро будет выведено дважды. Это может вызвать искажение изображения.

В представлении указателей на списки вершин, каждую вершину запоминают только один раз .

Список указателей Р определяет, какие вершины (координаты их хранятся в списке вершин) принадлежат данному многоугольнику.

Например, для графического объекта, состоящего из двух треугольников P₁ и P₂, не лежащих в одной плоскости (рис.1.4), список вершин , а списки граней: , , где указаны номера вершин.

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

Рис.1.4

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

В представлении указателей на списки ребер также имеется список вершин V, но представляется многоугольник как список указателей (P) не в список вершин (V), а в список ребер (Е), в котором каждое ребро встречается один раз. В свою очередь, каждое ребро в списке ребер указывает на две вершины в списке вершин, определяющих ребро, а также на один или два многоугольника, которым это ребро принадлежит.

Например (рис.1.5), список вершин представлен, как и в двух первых случаях, V=(V₁, V₂, V₃, V₄)=((x₁, y₁, z₁), ...,(x₄, y₄, z₄)), список ребер: E₁= (V₁, V₂, P₁, ), E₂= (V₂, V₃, P₂, ), E₃= (V₃, V₄, P₂, ), E₄= (V₄, V₂, P₁, P₂),

E₅ = (V₄, V₁, P₁, ), где  - знак отсутствия принадлежности, а список указателей треугольников: P₁ = (E₁, E₄, E₅), P₂ = (E₂, E₃, E₄).

Рис.1.5

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

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

Линейные каркасные модели являются самым распространенным способом описания поверхности. Основная проблема заключается в сравнительно большом объеме данных, необходимых для хранения координат вершин списков ребер и треугольников при точных описаниях криволинейных поверхностей.

Нелинейная каркасная модель – состоит из отрезков плоских кривых линий (сплайнов), которые проходят через определенные (контрольные) точки описываемой поверхности. Сплайн обладает свойством непрерывности и записывается с помощью полиномов различной степени. Это означает, что кривая, проходя через контрольные точки, не будет иметь изломов. Сшивая и пересекая сплайны друг с другом, получаем каркас поверхности, состоящий из набора кривых непрерывных линий, записанных в виде полиномов и проходящих через контрольные точки описываемой поверхности.

Рассмотрим пример построения нелинейной каркасной модели поверхности, заданной контрольными точками в пространстве, с помощью пространственной кривой линии с непрерывными вторыми производными, описываемой полиномами третьей степени (В – сплайн).

Вначале рассмотрим методику формирования пространственной кривой с помощью В-сплайнов.

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

Например, на рис.1.6 и вся кривая состоит из 10 - 3 = 7 сегментов, соответствующих отрезкам прямых 2-3, 3-4, 4-5, 5-6, 6-7, 7-8, 8-9.

Рис. 1.6

Трудность в интерполяции кривой типа В-сплайна заключается в том, что нельзя отличить один сегмент от другого, поскольку вся кривая гладкая. Из рис. 1.6 можно видеть, что первый сегмент начинается вблизи точки 2, так что он должен заканчиваться где-то вблизи точки 3, где начинается второй сегмент, но где этот переход совершается, из кривой совершенно не видно. Но всегда необходимо помнить, что такие граничные точки существуют, поскольку иначе было бы невозможно понять применяемые математические основы.

Используем полиномы третьей степени в параметрической форме:

(1.1)

Поскольку существует сегментов кривой, то имеем наборов кубических уравнений (каждый "набор" состоит из трех уравнений отдельно для каждой из координат x, y, z). В каждом сегменте кривой, лежащем между точками i и i + 1, переменная t изменяется от 0 до 1, то есть при t = 0 имеем конечную точку вблизи точки i, а при t = 1 производится интерполяция точки i +1.

Для каждого такого сегмента кривой (между точкой i и точкой i +1) можно вычислить коэффициенты по значениям координат четырех соседних точек, а именно точек i - 1, i, i + 1, i + 2.

Выражения для вычисления коэффициентов В-сплайна

(1.2)

Все три набора из четырех уравнений подобны.

В уравнениях (1.1) значения координат x, y, z определяются полиномами от переменной t, а из (1.2) находим коэффициенты этих полиномов. Ради полноты следует упомянуть, что если в (1.1) заменить коэффициенты и так далее на соответствующие выражения из системы (1.2) и выполнить группировку членов в результирующих выражениях, то получим систему

(1.3)

,

в которой стыковочные функции

(1.4)

Каждая новая точка (x, y, z) вычисляется как линейная комбинация заданных соседних точек. Можно получить любые конфигурации гладких кривых, в том числе и замкнутых. Кривая В-сплайна начинается вблизи второй точки (точка 2) и заканчивается вблизи предпоследней точки (точка ). Для замкнутой кривой эти две точки должны совпадать. Также должны совпадать точка 1 с точкой и точка 3 с точкой т, что схематично можно изобразить следующей схемой

Появляются два совпадающих отрезка прямой линии. Могут совпадать и две или более последовательных точек. Это свойство используется в качестве средства для "стягивания" кривой к заданной точке. Если, например, в случае незамкнутой кривой необходимо интерполировать и заданные концевые точки (точка 1 и точка т), то первой точке можно присвоить номера 1, 2, 3, что заставит кривую начинаться точно с этой точки. На первый взгляд это может показаться странным, поскольку в соответствии с выражениями (1.З) каждая вычисляемая точка (x, у, z) определяется по четырем заданным точкам и можно подумать, что кривая будет начинаться с точки 1, если она совпадает еще с тремя точками 2, 3 и 4. Но по (1.З) коэффициент для точки 4 равен , а из уравнений (1.4) следует, что при t = 0 этот коэффициент будет равен нулю и это действительно имеет место для самой первой вычисляемой точки. Поэтому на позицию первой точки эффективно влияют только точки 1, 2 и 3, а поскольку эти точки фактически являются одной точкой, то кривая начинается именно с нее.

Таким образом, формируются пространственные кривые, точки которых имели координаты х(t) , у(t) , z(t) , где t является параметром.

Теперь сформируем каркас поверхности, точки которой имеют координаты х(и, v) , у(и, v) , z(u, v) , где u и v - два независимых параметра. Снова используем интерполяцию с помощью В-сплайна. Вместо последовательности т заданных точек теперь будем задавать набор из пт точек, которые будут образовывать запись в следующем виде:

Р₁₁ Р₁₂ … Р_1m

Р₂₁ Р₂₂ … Р_2m

. . … .

. . … .

P _nl P _n2 … P _nm

Выделим горизонтальные и вертикальные ряды, которые относятся к строкам и столбцам этой записи. Например, можно сказать, что точка P_1m является самой правой точкой в первом горизонтальном ряду.

Запись точек P_ij можно интерпретировать как два набора кривых: для каждой «горизонтальной» кривой параметр i является константой, при этом параметр j изменяется от 1 до т, а для каждой «вертикальной» кривой параметр j -константа, а параметр i изменяется от 1 до п. Первая и самая последняя точки, участвуют в процессе вычислений, но не интерполируются. То же самое относится и к точкам P_ij, для которых i = 1 или i = п, а также для тех точек, для которых j = 1 или j = т. Для вычисления точек сетки на «четырехугольнике» поверхности требуются по четыре точки в каждом направлении, что вместе дает следующие шестнадцать точек:

Все эти точки будут использованы для интерполяции «четырехугольника» в середине (с точкой в верхнем левом углу и с точкой в нижнем правом углу). Этот четырехугольник в середине будет поделен на малых элемента поверхности (можно пересчитать N элементов по вертикальному и M элементов по горизонтальному направлениям).

Формулы для четырех функций , определенные в (1.4), подставим в формулы (3.З) в их двухмерном представлении. Поскольку эти формулы имеют идентичную структуру для всех трех координат х, у, z, то ниже приведем только одну, для координаты х:

.

Так как применяем не формулы (1.З) а их эквивалентные формы (1.1), то получаем суммы шестнадцати членов, в которых содержатся следующие произведения

Входные данные для рассматриваемого примера (рис.1.7) содержат 42 точки, некоторые из которых совпадают.

Рис. 1.7

Рассмотрим следующую запись при п = 6 и т = 7:

1 2 3 4 5 6 7

8 9 10 11 12 13 14

15 16 17 18 19 20 21

22 23 24 25 26 27 28

29 30 31 32 33 34 35

36 37 38 39 40 41 42

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

Таким образом, точка с номером 9 обозначает также точки 1, 2, 8. (Заметим, что реализация этой идеи для совпадающих точек, несомненно, имеет очень существенное значение, хотя можно подумать, что это

лишь ненужное усложнение и можно задавать только несовпадающие точки, но следует вспомнить, что первая и последняя точки не будут интерполированы). Номера точек 16 и 17 исчезли, поскольку эти точки совпадают с точками 23 и 24, но совершенно по иной причине. Ломаная линия, обозначенная номерами 23, 24, 25, 26, 28 была получена из ломаной линии, которой принадлежит точка 18 путем ее поворота на 90⁰ вокруг оси (24-23), что означает совпадение точек 15, 16, 17 с точками 22, 23, 24. При задании N = M = 3 было в результате получено 130 точек, которые изображены на рис.1.8.

Только что упомянутый максимальный номер 130 дает прекрасную возможность проверить соотношение между значениями параметров п, т, N, М, i, j с одной стороны и наибольшим абсолютным значением количества точек k с другой стороны. В общем случае имеем

,

где величина

обозначает количество точек в выходном файле, лежащих на «горизонтальной» линии.

Рис. 1.8

В примере рис.1.8 имеем

т = 7, п = 6, М = 3, N = 3

А = (7- 3) x 3 + 1 = 13

Поскольку параметры i и j используются в цикле, где их максимальные значения равны п - 2 и m - 2 соответственно, то N и М будут максимальными значениями для I и J соответственно, а для нахождения максимального значения k используем значения i = 4, j = 5, I = 3, J= 3, что дает

На рис 1.8 показаны все 130 точек и кривые линии для наглядности представлены отрезками прямых линий, на самом деле кривые, проходящие через эти 130 точек, гладкие непрерывные линии, не имеющие изломов.

Алгебраическая модель – описание поверхности или частей поверхностей графического объекта с помощью алгебраических уравнений.

Алгебраическое уравнение – многочлен, имеющий m переменных, возведенных в n – степень и имеющий одно, несколько или бесконечное число решений (корней).

В общем виде, алгебраическое описание графического объекта с множеством свойств поверхности и тела объекта имеет вид

где a – коэффициенты при переменных алгебраического уравнения поверхности, ограничивающей объект (коэффициенты могут принимать отрицательные, нулевые и положительные значения, целые и дробные значения);

k – номер коэффициента a (текущий номер коэффициента) от максимального до нулевого;

m – набор переменных (x ,y ,z, c,d,t,…) уравнения (свойств объекта);

n – номер высшей степени (порядок уравнения) при переменных (сложность свойств);