Алгоритмы визуализации.

Алгоритмы визуализации. Отсечение, развертка, удаление невидимых линий и поверхностей, закраска.

ОТСЕЧЕНИЕ ОТРЕЗКОВ

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

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

Программное исполнение отсечения достаточно медленный процесс, поэтому, естественно, в мощные дисплеи встраивается соответствующая аппаратура. Первое сообщение об аппаратуре отсечения, использующей алгоритм отсечения делением отрезка пополам и реализованной в устройстве Clipping Divider, появилось в 1968 г. Этот алгоритм был рассмотрен при изучении технических средств.

Отсекаемые отрезки могут быть трех классов - целиком видимые, целиком невидимые и пересекающие окно. Очевидно, что целесообразно возможно более рано, без выполнения большого объема вычислений принять решение о видимости целиком или отбрасывании. По способу выбора простого решения об отбрасывании невидимого отрезка целиком или принятия его существует два основных типа алгоритмов отсечения - алгоритмы, использующие кодирование концов отрезка или всего отрезка и алгоритмы, использующие параметрическое представление отсекаемых отрезков и окна отсечения. Представители первого типа алгоритмов - алгоритм Коэна-Сазерленда (Cohen-Sutherland, CS-алгоритм) и FC-алгоритм (Fast Clipping - алгоритм). Представители алгоритмов второго типа - алгоритм Кируса-Бека (Curus-Beck, CB - алгоритм) и более поздний алгоритм Лианга-Барски (Liang-Barsky, LB-алгоритм).

Алгоритмы с кодированием применимы для прямоугольного окна, стороны которого параллельны осям координат, в то время как алгоритмы с параметрическим представлением применимы для произвольного окна.
Алгоритм Коэна-Сазерленда, являющийся стандартом алгоритма отсечения линий и обладающий одним из лучших быстродействий при компактной реализации. Наиболее быстрый, но и чрезвычайно громоздкий FC-алгоритм. Алгоритм Лианга-Барски для отсечения прямоугольным окном с использованием параметрического представления. Быстродействие этого алгоритма сравнимо с быстродействием алгоритма Коэна-Сазерленда при большей компактности и наличии 3D и 4D реализаций. Алгоритм Кируса-Бека использует параметрическое представление и позволяет отсекать произвольным выпуклым окном.

ЧЕРЕССТРОЧНАЯ И ПРОГРЕССИВНАЯ РАЗВЕРТКА

Прогрессивная и чересстрочная развертки – это методы отображения изображения на экране монитора или его формирования в видеокамере. За одну секунду на экране телевизора «пробегает» 25* кадров в секунду, метод формирования каждого и которых определяет прогрессивная или чересстрочная развёртки. Аналоговые камеры и мониторы используют метод чересстрочной развертки.

Чересстрочная развертка.

Рассмотрим принцип формирования обыкновенного телевизионного кадра. ТВ кадр состоит из 625 строк, 576 из которых являются видимыми (несущими информацию об изображении), а 49 – служебными. Строки выводятся (отображаются) на экран не последовательно (1-я, 2-я, 3-я и т.д.), как естественно было бы предположить, а через одну – в начале выводятся четные строки (2-я, 4-я, 6-я и т.д.), а затем нечетные (1-я, 2-я, 3-я и т.д.), что называется чересстрочной разверткой. Таким образом кадр делится на два полукадра состоящих из четных и нечетных строк. Каждый такой полукадр называется полем. Причем, поле, состоящее из нечетных строк, называется нечетным или верхним, а поле, состоящее из четных строк – четным или нижним.

Т.е. телевизионное изображение обновляется не 25 раз в секунду (частота кадров), а 50 раз в секунду. Теперь мы подошли к самому главному. Видеокамеры снимают 50 полей (полукадров) в секунду и кадр формируется путем сложения обоих полей. Т.е. каждую 1/50 секунды с матрицы видеокамеры считываются и записываются по переменно четные и нечетные строки. Рассмотрим процесс видеосъемки подробнее. При перемещении объекта слева направо в первый момент времени видеокамера фиксирует на матрице изображение и считывает четные строки, формируя нижнее поле. Через 1/50 секунды видеокамера считывает нечетные строки, формируя верхнее поле. Сложим два поля – получим кадр.

За 1/50 секунды объект успел переместиться относительно положения зафиксированного в нижнем поле и верхнем поле оказался правее. Кадры, снятые аналоговой камерой, выводятся без искажений на аналоговый монитор, который также работает в режиме чересстрочной развертки. Сейчас совместно со стандартными аналоговыми камерами, в псевдоцифровых системах видеонаблюдения (на базе DVR или плат видеозахвата), используются мониторы с прогрессивной разверткой, в результате на изображении возникает эффект «гребенки» на границах движущихся объектов.

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

Прогрессивная развертка.

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

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

Удаление скрытых линий и поверхностей

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

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

Рис. Неоднозначность восприятия изображения куба

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

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

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

Классификация методов удаления невидимых частей

Методы удаления невидимых частей можно классифицировать:

По выбору удаляемых частей: удаление невидимых линий, ребер, поверхностей, объемов.
По порядку обработки элементов: удаление в произвольном порядке и в порядке, определяемом процессом визуализации.
По системе координат:
- алгоритмы работающие в пространстве объектов, когда каждая из N граней объекта сравнивается с остальными N-1 гранями (объем вычислений растет как N2),
- алгоритмы работающие в пространстве изображения, когда для каждого пиксела изображения определяется какая из N граней объекта видна (при разрешении экрана M×M объем вычислений растет как M2 ×N).

Алгоритмы удаления линий

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

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

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

Алгоритм удаления поверхностей с Z-буфером

Алгоритм предложен Эдом Кэтмулом и представляет собой обобщение буфера кадра. Обычный буфер кадра хранит коды цвета для каждого пиксела в пространстве изображения. Идея алгоритма состоит в том, чтобы для каждого пиксела дополнительно хранить еще и координату Z или глубину. При занесении очередного пиксела в буфер кадра значение его Z-координаты сравнивается с Z-координатой пиксела, который уже находится в буфере. Если Z-координата нового пиксела больше, чем координата старого, т.е. он ближе к наблюдателю, то атрибуты нового пиксела и его Z-координата заносятся в буфер, если нет, то ни чего не делается.

Этот алгоритм наиболее простой из всех алгоритмов удаления невидимых поверхностей, но требует большого объема памяти. Данные о глубине для реалистичности изображения обычно достаточно иметь с разрядностью порядка 20 бит. В этом случае при изображении нормального телевизионного размера в 768×576 пикселов для хранения Z-координат необходим объем памяти порядка 1 Мбайта. Суммарный объем памяти при 3 байтах для значений RGB составит более 2.3 Мбайта.

Время работы алгоритма не зависит от сложности сцены. Многоугольники, составляющие сцену, могут обрабатываться в произвольном порядке. Для сокращения затрат времени нелицевые многоугольники могут быть удалены.

ЗАКРАСКА

В большинстве приложений используется одно из существенных достоинств растровых устройств - возможность заполнения областей экрана.

Существует две разновидности заполнения:

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

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

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

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

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

По способу задания области делятся на два типа:

· гранично-определенные, задаваемые своей (замкнутой) границей такой, что коды пикселов границы отличны от кодов внутренней, перекрашиваемой части области. На коды пикселы внутренней части области налагаются два условия - они должны быть отличны от кода пикселов границы и кода пиксела перекраски. Если внутри гранично-определенной области имеется еще одна граница, нарисованная пикселами с тем же кодом, что и внешняя граница, то соответствующая часть области не должна перекрашиваться;

· внутренне-определенные, нарисованные одним определенным кодом пиксела. При заливке этот код заменяется на новый код закраски.

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

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