КГ_4глава (Компьютерная графика), страница 2

Блокирование повторного рисования линий контуров смежных граней позволяет решить также проблему искажения стиля линий, если линии контуров не! сплошные, а, например, пунктирные.

Топологический аспект. Представим, что имеется несколько смежных гра­ней. Что будет, если изменить координаты одной вершины в структурах дан­ных? Результат приведен на рис. 4.8.

Рис. 4.8. Результат изменения координат одной вершины

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

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

Иначе говоря, поддержка такой операции может быть обеспечена как струк­турами данных, так и алгоритмически.

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

Положительные черты векторной полигональной модели:

□ удобство масштабирования объектов. При увеличении или уменьшении объекты выглядят более качественно, чем при растровых моделях описа­ния. Диапазон масштабирования определяется точностью аппроксимации и разрядностью чисел для представления координат вершин;

□ небольшой объем данных для описания простых поверхностей, которые адекватно аппроксимируются плоскими гранями;

□ необходимость вычислять только координаты вершин при преобразовани­ях систем координат или перемещении объектов;

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

Недостатки полигональной модели:

□ сложные алгоритмы визуализации для создания реалистичных изображе­ний; сложные алгоритмы выполнения топологических операций, таких, например, как разрезы;

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

Воксельная модель

Воксельная модель — это трехмерный растр. Подобно тому, как пикселы располагаются на плоскости 2О-изображения, так и вокселы образовывают трехмерные объекты в определенном объеме (рис. 4.9). Воксел— это эле­мент объема (voxel — volume element).

Как мы знаем, каждый пиксел должен иметь свой цвет. Каждый воксел также имеет свой цвет, а, кроме того, прозрачность. Полная прозрачность воксела

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

Рис. 4.9. Пикселы и вокселы

Для современной КГ вексельный метод считается одним из перспективных. Его используют в компьютерных системах для медицины. Например, при сканировании томографом (computer tomography) получаются изображения срезов объекта, которые потом объединяются в виде объемной модели для дальнейшего анализа [53]. Вексельный метод используется в геологии, сейс­мологии, в компьютерных играх [50, 56]. Вокселы также используются для графических устройств отображения, которые создают действительно объ­емные изображения [37].

Положительные черты вексельной модели:

□ позволяет достаточно просто описывать сложные объекты и сцены; про­стая процедура отображения объемных сцен;

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

Недостатки воксельной модели:

□ большое количество информации, необходимой для представления объ­емных данных. Например, объем 256x256x256 имеет небольшую разре­шающую способность, но требует свыше 16 миллионов вокселов;

□ значительные затраты памяти ограничивают разрешающую способность, точность моделирования; большое количество вокселов обусловливает малую скорость создания изображений объемных сцен;

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

Равномерная сетка

| Эта модель описывает координаты отдельных точек поверхности следующим I. способом (рис. 4.10). Каждому узлу сетки с индексами (i, j) приписывается значение высоты z_ij. Индексам (i, j) отвечают определенные значения коор­динат (х, у). Расстояние между узлами одинаковое— dx по оси х и dy по

оси_у.

Рис. 4.10. Узлы равномерной сетки

Фактически, такая модель— двумерный массив, растр, матрица, каждый элемент которой сохраняет значение высоты.

Не каждая поверхность может быть представлена этой моделью. Если в каж­дом узле записывается только одно значение высоты, то это означает, что поверхность описывается однозначной функцией z = f (x, у). Иначе говоря, это такая поверхность, которую любая вертикаль пересекает только один раз. Не могут моделироваться также вертикальные грани. Необходимо заметить, что для сетки не обязательно использовать только декартовые координаты. Например, для того чтобы описать поверхность шара однозначной функцией, можно использовать полярные координаты. Равномерная сетка часто исполь­зуется для описания рельефа земной поверхности.

Рассмотрим, как можно вычислить значения высоты для любой точки внутри границ сетки. Пусть ее координаты равны (х, у). Надо найти соответствую-

щее значение z. Решением такой задачи является интерполяция значений ко­ординат z ближайших узлов (рис. 4.11).

Рис, 4.11. Точка в сетке с координатами (х, у,z)

Сначала необходимо вычислить индексы i и j одного из узлов:

где ]а[ — целая часть числа а, то есть наибольшее целое, которое не превы­шает а.

Далее используем, например, линейную интерполяцию. Для этого сначала найдем значения z в точках А и Б. Из пропорции

учитывая, что , получим

Аналогично найдем

Теперь можно найти нужное значение z, поделив отрезок АВ пропорциональ­но значению у:

Получим

Положительные черты равномерной сетки:

□ простота описания поверхностей;

О возможность быстро узнать высоту любой точки поверхности простой ин­терполяцией.

Недостатки равномерной сетки:

□ поверхности, которые соответствуют неоднозначной функции высоты в узлах сетки, не могут моделироваться;

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

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

Неравномерная сетка. Изолинии

Неравномерной сеткой назовем модель описания поверхности в виде множе­ства отдельных точек {(х₀, у₀, z₀), (x₁ , y₁ , z₁), ..., (х_n-1 у _n-1, z _n-1)}, принадлежа­щих поверхности. Эти точки могут быть получены, например, в результате измерений поверхности какого-нибудь объекта с помощью определенного оборудования.

Такую модель можно считать обобщением для некоторых рассмотренных нами моделей. Например, векторная полигональная модель и равномерная сетка могут считаться разновидностями неравномерной сетки. Эти разновид­ности мы рассмотрели в отдельности, так как они играют важную роль для решения задач КГ. А вообще, может существовать много вариантов класси­фикации способов описания поверхностей. Следует учитывать определенную условность нашего перечня моделей поверхностей, последовательность пе­речисления таких моделей может быть и другой.

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

Эту задачу можно решать несколькими способами, в том числе триангуля­цией. Процесс триангуляции можно представить себе так (рис. 4.12). Сначала находим первые три самые близкие друг другу точки— и получаем одну плоскую треугольную грань. Потом находим точку, ближайшую к этой гра­ни, и образовываем смежную грань. И так далее, пока не останется ни одной отдельной точки. Это общая схема, в литературе описано много разных спо­собов триангуляции. Довольно часты ссылки на триангуляцию Делоне [48].

Рис. 4.12. Триангуляция неравномерной сетки

Описание поверхности треугольными гранями можно уже считать разновид­ностью векторной полигональной модели. В англоязычной литературе для нее встречается такое название: TIN (Triangulated Irregular Network). После триангуляции получаем полигональную поверхность, отображение которой сделать уже достаточно просто.

Рассмотрим еще один из вариантов описания поверхности— изолинии высоты. Любая изолиния состоит из точек, представляющих одно числовое значение какого-то показателя, в данном случае— значение высоты (рис. 4.13, 4.14). Изолинии высоты также можно вообразить себе как контуры разреза поверхности горизонтальными плоскостями (поэтому для изолиний высоты часто применяется название "горизонтали").