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

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

Конечно, для описания поверхности можно использовать не только изолинии высоты, но и другие изолинии, например я:- или у-изолинии.

Рис. 4.13. Поверхность задана изолиниями и отметками высоты

Рис. 4.14. Та же поверхность в аксонометрической проекции

В компьютерных системах изолинии часто описываются векторно — поли­линиями. Используются также изолинии в виде онлайновых кривых. Точки, которые составляют изолинии, и отдельные опорные точки распола­гаются неравномерно. Это усложняет расчет координат точек поверхности. В графических компьютерных системах для выполнения многих операций, и в первую очередь — для показа поверхности, обычно необходимо преобразо­вывать описание поверхности в другую форму. Преобразование изолиний в полигональную модель также выполняется методами триангуляции (здесь алгоритмы триангуляции сложнее, чем для триангуляции отдельных точек). Для преобразования неравномерной сетки в равномерную используют специ­альную интерполяцию.

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

Недостатки: невозможность или сложность выполнения многих операций над поверхностями; сложные алгоритмы преобразования в другие формы описания поверхностей.

Преобразование моделей описания поверхности

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

Для решения данной задачи можно использовать алгоритм, предложенный автором этой книги и реализованный в геоинформационной системе ГИС "ОКО" в 1996 году [57].

Сначала рассмотрим аспекты точности алгоритма и ограничения для его ис­пользования.

Равномерную сетку можно рассматривать как растр. Расстояние между узла­ми сетки в плоскости (хОу) обуславливает разрешающую способность такого растра и определяет точность моделирования по осям х и у. Конечно, чем меньше расстояние между узлами, тем больше точность моделирования, но это ведет к возрастанию количества узлов и соответственно увеличивает раз­меры растра. Таким образом, мы определили размер растра по горизонтали (c_x) и вертикали (с_у).

Необходимо также учесть дискретность представления чисел в компьютере при хранении в памяти значений в узлах сетки. В современных цифровых компьютерах числа обычно представляются в форматах с разрядностью, кратной 8 (байт). Однобайтовые целые числа дают 256 градаций, двухбайто­вые — 65 536 и так далее. Можно также использовать и форматы с плаваю­щей точкой.

Выбираем формат чисел для кодирования пикселов растра. Одной из основ­ных особенностей предложенного алгоритма является то, что число 0 для каждого пиксела указывает на неопределенное значение высоты (пустоты до интерполяции). Это означает, что, например, для однобайтовых пикселов высота имеет не 256, а 255 градаций. Дискретность значений высоты = = диапазон значений /255.

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

П = сх -су (байтов на пиксел).

Все это необходимо учитывать для построения равномерной сетки поверхно­сти с необходимой точностью.

Общая схема алгоритма

1. Открываются два массива для растров: А и В. Каждый растр имеет размер сх х су пикселов.

2. В растре А обнуляются все его пикселы.

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

4. Заполняются пустоты. В процессе заполнения пикселы результата записы­ваются в растр В. В ходе заполнения пустот вычисляется R_max.

5. Если R_max < 2, то интерполяция закончена. Результат— равномерная сет­ка — находится в массивах растра В.

6. Проводятся контуры на границах раздела областей заполнения. В процес­се оконтуривания пикселы результата записываются в растр А.

7. Переход к пункту 4.

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

Продолжим описание алгоритма согласно приведенной выше общей схеме. В пункте 3 точечные, линейные и площадные изообласти высоты отобража­ются как обычные пикселы, линии и полигоны. При таком отображении су­ществует проблема "одного пиксела". Она обусловлена тем, что некоторые алгоритмы растеризации могут различно располагать пикселы, например, для линии. Для линии необходимо использовать алгоритмы, способные отраба­тывать нецелые координаты вершин. Это касается и полигонов. Конечно, использование таких алгоритмов приводит к уменьшению скорости, но глав­ное здесь — точность. Точность растеризации в значительной степени пред­определяет точность преобразования в равномерную сетку.

Заполнение пустот выполняется следующим образом:

1. R_max = 0;

2. for (у = 0; у < су; у++)

3. for (х = 0; х < сх; х++)

4. Если пиксел (х,у) растра А ненулевой, то копируем в растр В. Иначе:

{

5. Поиск ближайшего ненулевого пиксела. В результате поиска становятся известными значение пиксела (цвет) и его расстояние (r) до точки (х,у) .

6. Если ненулевой пиксел не найден, то прекращаем весь процесс и делаем сообщения об ошибке.

7. Записываем в растр В по координатам (х,у) цвет найденного пиксела.

8. ЕСЛИ R max < r, ТО R max = r

)

В ходе заполнения анализируются пикселы рабочего растра, и результаты записываются в другой растр. Для этого и предусмотрены два массива. Не­обходимо отметить, что пункт 4 алгоритма заполнения можно упростить, ес­ли при его выполнении не копировать ненулевые пикселы, а перед началом сканирования растра (п. 2) сразу скопировать весь рабочий растр в другой массив. Это позволяет ускорить работу при условии, что групповое копиро­вание блоков памяти выполняется быстрее.

Проведение контуров. Оконтуривание можно выполнить методами локаль­ной фильтрации изображения растра. Например, таким способом:

В процессе оконтуривания в растре А появляются новые контуры на границ областей заполнения. Линии контуров образовываются пикселами, значение

(цвет) которых равно полусумме пикселов областей заполнения, а распола­гаются новые контуры посредине старых, то есть, выполняется линейная ин­терполяция высоты. В растре А также хранятся предыдущие линии контуров. Таким образом, с каждым циклом заполнения-оконтуривания количество контуров изолинии удваивается. Так длится до тех пор, пока контурные ли­нии не сомкнутся — нечего будет заполнять. Количество циклов интерполя­ции оценивается как двоичный логарифм расстояния между ненулевыми пикселами растра, на котором отображены исходные данные.

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

Быстро и просто этот поиск можно осуществить, если идти по контуру квад­рата (рис. 4.15). Однако точки на периметре квадрата имеют различное рас­стояние до центра. Решение этой проблемы заключается в организации двухэтапного цикла поиска. Сначала последовательно увеличиваем размер квад­рата с центром в точке (х, у) до тех пор, пока на периметре не обнаружится ненулевой (значащий) пиксел растра. Рассчитываем расстояние R1 Если это расстояние больше, чем (размер квадрата + 1), то начинаем второй этап по­иска. Для этого продолжаем увеличивать размер квадрата вплоть до значения R₁,. Если при этом находятся новые точки с расстоянием R₂< R₁, то поиск продолжается, но максимальный размер окрестности ограничиваем уже R₂. Здесь необходимо пояснить, что в качестве размера квадрата здесь считается половина его стороны.

Рис. 4.15. Поиск по периметру квадратов

Дадим запись алгоритма поиска ближайшей точки:

Процедура поиска пикселов по периметру квадрата названа здесь ППК(l, х_c, у_c, r), где l— половинный размер квадрата; x_c и y_c — координаты центра квадрата; r — расстояние для сравнения — если находится пиксел с большим расстоянием, то он не учитывается. В результате работы процеду­ры ППК определяется цвет найденного пиксела (с) и рассчитывается рас­стояние до центра (R).