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

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

Рис. 8.12 – Одна и та же сцена до и после удаления скрытых линий.

Рис. 8.13 – Схема удаления скрытых линий.

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

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

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


а)	б)	в)

Рис. 8.14 – Варианты взаимного расположения ребра и грани.

а) ребро перед гранью; б) ребро за гранью; в) ребро пересекает грань

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

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

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

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

1. Заполнить буфер кадрафоновым изображением.

2. Заполнить буфер глубины значениями глубины фона.

3. Для каждой грани сцены последовательно:

- преобразовать проекцию грани в растровую форму (например, при помощи алгоритма Брэзенхема);

- для каждого пиксела проекции вычислить его глубину z=z(x,y);

- сравнить значение z(x,y) с соответствующим значением буфера глубины Z(x,y);

- Если z(x,y)< Z(x,y), то:

- записать этот пиксел в буфер кадра;

- записать значение z(x,y) в соответствующую позицию буфера глубины Z(x,y).

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