Удаление невидимых ребер и граней (Culling)

объект, в данном случае куб, грани которого непрозрачны, то видим

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

все этапы геометрических преобразований и процедуру отсечения по видимому объему,

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

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

граней, т.е. все верщины объекта «проходят» через систему конвейерной обработки

и алгоритм должен определить в процессе обработки, какие же грани являются видимыми, а какие – закрываются другими гранями. Особую роль в реализации этой процедуры дает возможность использовать предысторию анализа результатов, полученных на предыдущем этапе конвейерной обработки.
Алгоритмы удаления невидимых ребер и граней разделяются на 2 класса:
- алгоритмы, работающие в пространстве объектов (мировая СК) – object-space algorithms;
- алгоритмы, работающие при формировании изображений в поле видимости
(видовая СК) – image-space algorithms.

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

3d-объектов). Обобщенный подход, основанный на анализе пространства объектов, предполагает попарное

сравнение положения всех объектов по отношению к наблюдателю (центру проецирования). Это означает, что для определения видимости данной грани сравнивается ее взаимное расположение со всеми остальными гранями в трехмерной сцене. Рассмотрим 2 таких объекта – грани A и B.
Существует 4 варианта их взаимного расположения:
- A полностью закрывает B – в изображение нужно включить только A.
B полностью закрывает A - в изображение нужно включить только B.
A и B не перекрываются – в изображение включаются оба объекта A и B.
A и B частично перекрываются – необходимо вычислить, какая часть перекрываемого объекта будет видна наблюдателю.
Для построения трехмерной сцены в этом случае необходимо сравнить
положение каждой грани
с оставшимися, что требует
порядка K 2 операций.

пространстве, имеют дело с мировой системой координат, в которой описаны

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

Алгоритм Робертса - Этот алгоритм, предложенный в 1963 г., является первой разработкой такого рода и предназначен для удаления невидимых линий объектов, составленных из выпуклых многогранников. Он относится к алгоритмам, работающим в объектном пространстве. В нем очень удачно сочетаются геометрические методы и методы линейного программирования.
Алгоритм Вейлера-Айзертона – алгоритм (1977г.) выполняет разбиения вдоль границ многоугольников. Для этого используется ими же разработанный алгоритм отсечения многоугольников. Алгоритм работает в объектном пространстве. В самом общем виде он состоит из четырех шагов.
Предварительная сортировка по глубине.
Отсечение по границе ближайшего к точке наблюдения многоугольника, называемое сортировкой многоугольников на плоскости.
Удаление многоугольников, экранируемых более близкими к точке наблюдения многоугольниками.
Если требуется, то рекурсивное разбиение видимого объема и новая сортировка.

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

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

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

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

с системой координат того экрана, на котором объекты визуализируются. При

этом точность вычислений ограничена разрешающей способностью экрана (640х480, 800х600, 1024х768 и т.д.). Результаты, полученные в пространстве изображений, а затем увеличенные в несколько раз, не будут соответствовать исходной сцене(например, могут не совпадать концы отрезков).
Алгоритм Z-буфера;
Алгоритмы(художника,
плавающего горизонта).

поверхностей является алгоритм z-буфера (буфер глубины- the depth buffer). Алгоритм

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

составляют X точек в ширину и Y точек в высоту.

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

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

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

F (x, y, z) = 0
Изображение получается путем изображения кривых,

получаемых при пересечении поверхности F плоскостями Zi = const.
В процессе рисования записываются значения координат (xi ,yi ) в два целочисленных массива: (нижний горизонт) и (верхний горизонт) размерностью, соответствующей горизонтальному размеру экрана в пикселях. Они нужны для анализа видимости участков изображаемых отрезков. Сначала инициализируем верхний горизонт нулем, а нижний - максимальным значением вертикальной координаты на экране. Каждая выводимая на экран точка может закрывать другие точки, которые "скрываются за горизонтом". По мере рисования нижний горизонт "опускается", а верхний "поднимается", постепенно оставляя все меньше незакрытого пространства. В отличие от алгоритма художника, здесь продвигаемся от ближнего угла к дальнему.