| СОДЕРЖАНИЕ
1. ПОСТАНОВКА ЗАДАЧИ.. 2
2. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ. 2
2.1 Описание метода. 2
3. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ.. 11
4. Список функций процедур программы. 12
5. ОПИСАНИЕ ПРОГРАММЫ... 13
5.1. Системные требования. 13
5.2. Руководство пользователя. 13
5.3. Листинг программы.. 14
6. ЛИТЕРАТУРА.. 20
1. ПОСТАНОВКА ЗАДАЧИ
Разработать программу, реализующую алгоритм удаления невидимых линий и поверхностей методом Z-буфера.
Реализовать алгоритм для сцены, состоящей из набора плоских многоугольников с произвольным расположением и для построения сечений поверхностей. Для наглядности результата произвести закраску граней различными цветами.
2. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ.
2.1 Описание метода.
Это один из простейших алгоритмов удаления невидимых поверхностей. Впервые он был предложен Кэтмулом. Работает этот алгоритм в пространстве изображения.
Главное преимущество алгоритма — его простота. Кроме того, этот алгоритм решает задачу об удалении невидимых поверхностей и делает тривиальной визуализацию пересечений сложных поверхностей. Сцены могут быть любой сложности. Поскольку габариты пространства изображения фиксированы, оценка вычислительной трудоемкости алгоритма не более чем линейна. Поскольку элементы сцены или картинки можно заносить в буфер кадра или в z-буфер в произвольном порядке, их не нужно предварительно сортировать по приоритету глубины. Поэтому экономится вычислительное время, затрачиваемое на сортировку по глубине.
Основной недостаток алгоритма — большой объем требуемой памяти. Если сцена подвергается видовому преобразованию и отсекается до фиксированного диапазона координат z значений, то можно использовать z-буфер с фиксированной точностью. Информацию о глубине нужно обрабатывать с большей точностью, чем координатную информацию на плоскости (x, y); обычно бывает достаточно 20 бит. Буфер кадра размером 512 * 512 * 24 бит в комбинации с z-буфером размером 512 * 512 * 20 бит требует почти 1.5 мегабайт памяти. Однако снижение цен на память делает экономически оправданным создание специализированных запоминающих устройств для z-буфера и связанной ним аппаратуры.
Альтернативой созданию специальной памяти для z-буфера является использование для этой цели оперативной памяти. Уменьшение требуемой памяти достигается разбиением пространства изображения на 4, 16 или больше квадратов или полос. В предельном варианте можно использовать z-буфер размером в одну строку развертки. Для последнего случая имеется интересный алгоритм построчного сканирования . Поскольку каждый элемент сцены обрабатывается много раз, то сегментирование z-буфера, вообще говоря, приводит к увеличению времени, необходимого для обработки сцены. Однако сортировка на плоскости, позволяющая не обрабатывать все многоугольники в каждом из квадратов или полос, может значительно сократить этот рост.
Другой недостаток алгоритма z-буфера состоит в трудоемкости и высокой стоимости устранения лестничного эффекта, а также реализации эффектов прозрачности и просвечивания. Поскольку алгоритм заносит пикселы в буфер кадра в произвольном порядке, то нелегко получить информацию, необходимую для методов устранения лестничного эффекта, основывающихся на предварительной фильтрации. При реализации эффектов прозрачности и просвечивания пикселы могут заноситься в буфер кадра в некорректном порядке, что ведет к локальным ошибкам.
Хотя реализация методов устранения лестничного эффекта, основывающихся на префильтрации, в принципе возможна, практически это сделать трудно. Однако относительно легко реализуются методы постфильтрации (усреднение подпикселов). Напомним, что в методах устранения лестничного эффекта, основывающихся на постфильтрации, сцена вычисляется в таком пространстве изображения, разрешающая способность которого выше, чем разрешающая способность экрана.
Поэтому возможны два подхода к устранению летничного эффекта на основе постфильтрации. В первом используется буфер кадра, заданный в пространстве изображения, разрешение которого выше, чем у экрана, и z-буфер, разрешение которого совпадает с разрешением экрана. Глубина изображения вычисляется только в центре той группы подпикселов, которая усредняется. Если для имитации расстояния от наблюдателя используется масштабирование интенсивности, то этот метод может оказаться неадекватным.
Во втором методе оба буфера, заданные в пространстве изображения, имеют повышенную разрешающую способность. При визуализации изображения как пикселная информация, так и глубина усредняются. В этом методе требуются очень большие объемы памяти. Например, изображение размером 512 * 512 * 24 бита, использующее z-буфер размером 20 бит на пиксел, разрешение которого повышено в 2 раза по осям x и y и на котором устранена ступенчатость методом равномерного усреднения, требует почти 6 мегабайт памяти.
Более формальное описание алгоритма z-буфера таково:
заполнить буфер кадра фоновым значением интенсивности или цвета;
заполнить z-буфер минимальным значением z;
преобразовать каждый многоугольник в растровую форму в произвольном порядке;
для каждого Пиксел(x, y) в многоугольнике вычислить его глубину z(x, y);
сравнить глубину z(x, y) со значением Zбуфер(x, y), хранящимся в z-буфере в этой же позиции;
если z(x, y) > Zбуфер(x, y), то записать атрибут этого многоугольника (интенсивность, цвет и т. п.) в буфер кадра и заменить Zбуфер(x, y) на z(x, y);
в противном случае никаких действий не производить.
В качестве предварительного шага там, где это целесообразно, применяется удаление нелицевых граней.
Если известно уравнение плоскости, несущей каждый многоугольник, то вычисление глубины каждого пиксела на сканирующей строке можно проделать пошаговым способом. Напомним, что уравнение плоскости имеет вид:
ax + by + cz + d = 0
z = -(ax + by + d)/c <> 0.
Для сканирующей строки y = const. Поэтому глубина пиксела на этой строке, у которого x1 = x + Dх, равна
z1 - z = -(ax1 + d)/c + (ax + d)/с = a(x - x1)/c или
z1 = z - (a/c)Dx.
Но Dx = 1, поэтому z1 = z - (a/c).
Дальнейшей иллюстрацией алгоритма послужит следующий пример.
Пример. Алгоритм, использующий z-буфер. Рассмотрим многоугольник, координаты угловых точек которого равны P1(10, 5, 10), P2(10, 25, 10), P3(25, 25, 10), P4(25, 5, 10) и треугольник с вершинами P5(15, 15, 15), P6(25, 25, 5), P7(30, 10, 5). Треугольник протыкает прямоугольник, как показано на рис. 21.1. Эти многоугольники нужно изобразить на экране с разрешением 32 * 32, используя простой буфер кадра с двумя битовыми плоскостями. В этом буфере фон обозначен через 0, прямоугольник — через 1, а треугольник — через 2. Под z-буфер отводится 4 битовых плоскости размером 32 * 32 бит. Таким образом, содержимое z-буфера окажется в диапазоне от 0 до 16. Точка наблюдения расположена в бесконечности на положительной полуоси z, как показано на рис. 21.1b.
Вначале и в буфере кадра, и в z-буфере содержатся нули. После растровой развертки прямоугольника содержимое буфера кадра будет иметь следующий вид:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Содержимое z-буфера таково:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Напомним, что в левом нижнем углу находится пиксел (0, 0).
Используя метод Ньюэла, получаем уравнение плоскости треугольника 3x + y + 4z - 120 = 0.
Значит, глубина треугольника в любой его точке задается уравнением z = -(3x + у - 120)/4.
Для последовательных пикселов, лежащих на сканирующей строке z1 = z - 3/4.
Вычисление пересечений сторон треугольника со сканирующими строками развертки с учетом соглашения о половине интервала между соседними сканирующими строками дает следующие пары координат (25.2, 24.5), (25.5, 23.5), (25.8, 22.5), (26.2, 21.5), (26.5, 20.5), (26.8, 19.5), (27.2, 18.5), (27,5, 17.5), (27.8, 16.5), (28.2, 15.5), (28.5, 14.5), (28.8, 13.5), (29.2, 12.5), (29.5, 11.5), (29.8, 10.5) для строк от 24 до 10. Напомним, что активируется тот пиксел, у которого центр лежит внутри или на границе треугольника, то есть при x1 <= x <= x2. Преобразование в растровую форму и сравнение глубины каждого пиксела со значением z-буфера дает новое состояние буфера кадра:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 2 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 2 2 1 1 1 1 1 2 2 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 2 2 2 2 1 1 1 1 2 2 2 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 1 1 1 1 2 2 2 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 2 2 2 2 2 2 1 1 1 1 2 2 2 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 1 1 1 2 2 2 2 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 2 2 2 1 1 1 2 2 2 2 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 2 2 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
После обработки треугольника состояние z-буфера таково:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 5 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 5 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 6 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 6 5 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 11 10 10 10 10 10 6 5 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 12 11 10 10 10 10 10 6 6 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 13 12 11 10 10 10 10 10 7 6 5 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 14 13 12 11 11 10 10 10 10 7 6 5 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 15 14 13 12 12 11 10 10 10 10 7 6 6 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 14 13 13 12 11 10 10 10 10 7 7 6 5 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 12 11 11 10 10 10 8 7 6 5 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 8 7 6 6 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 8 7 7 6 5 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 6 5 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Для примера рассмотрим пиксел (20, 15). Оценка z в центре этого пиксела дает
z = -[(3), (20.5) + 15.5 - 120]/4 = 43/4 = 10.75.
Сравнивая его со значением z-буфера в точке (20, 15) после обработки прямоугольника, видим, что треугольник здесь расположен перед прямоугольником. Поэтому значение буфера кадра в точке (20, 15) заменяется на 2. Поскольку в нашем примере z-буфер состоит лишь из 4 битовых плоскостей, он может содержать числа только в диапазоне от 0 до 15. Поэтому значение z округляется до ближайшего целого числа. В результате в ячейку (20, 15) z-буфера заносится число 11.
Линия пересечения треугольника с прямоугольником получается при подстановке z = 10 в уравнение плоскости, несущей треугольник. Результат таков:
3x + y - 80 = 0.
Пересечения этой прямой с ребрами треугольника происходят в точках (20, 20) и (22.5, 12.5). Линия пересечения, на которой треугольник становится видимым, хорошо отражена в буфере кадра.
Алгоритм, использующий z-буфер, можно также применить для построения сечений поверхностей. Изменится только оператор сравнения:
z(x, y) > Zбуфер(x, y) and z(x, y) <= Zсечения
где Zсечения — глубина искомого сечения. Эффект заключается в том, что остаются только такие элементы поверхности, которые лежат на самом сечении или позади него.
2.2 УДАЛЕНИЕ НЕВИДИМЫХ ЧАСТЕЙ
Необходимость в этой процедуре возникает, когда, в конце концов, оказывается, что надо нарисовать грань, у которой часть вершин лежит перед камерой, а часть - за камерой. То есть грань, пересекающуюся с экраном. Сама по себе она правильно не нарисуется.
Поскольку камера видит только то, что перед ней находится, все те точки, для которых z < -dist, рисовать не надо. То есть, каждую грань надо обрезать плоскостью z = -dist. Принципиально различных случаев расположения грани относительно этой плоскости может быть всего четыре; когда перед камерой находятся соответственно 0, 1, 2 или 3 вершины. Первый и последний случаи тривиальны - если перед камерой находится 0 вершин, то грань просто не видна и рисовать ее не надо; если 3 вершины, то грань видна целиком и полностью и ее достаточно просто взять и нарисовать. Рассмотрим оставшиеся два случая.
Случай первый, когда перед камерой находится только одна вершина:
В этом случае перед камерой находится только треугольник CDE. Его и надо будет нарисовать вместо грани.
Случай второй, когда перед камерой находятся две вершины:
Здесь уже надо будет нарисовать трапецию DABE; она разбивается на два треугольника, DAB и DBE. Их и рисуем вместо грани.
Координаты и текстурные координаты для точек D, E считаются совсем просто: с одной стороны, D лежит на AC, с другой стороны, D.z = -dist. Для точки D как лежащей на AC любая величина t (вместо t подставляем x/y/u/v) считается следующим образом:
D.t = A.t + (C.t - A.t) * (D.z - A.z) / (C.z - A.z) = A.t + (C.t - A.t) * (-dist - A.z) / (C.z - A.z)
Все это сводится в следующий алгоритм отрисовки грани:
выясняем, сколько вершин лежит перед камерой; то есть - какой из случаев мы имеем;
ставим точки A, B, C в соответствие с вершинами (то есть, если вершина v0 находится перед камерой, а вершины v1, v2 - нет, то имеем первый случай, где C = v0, A = v1, B = v2);
считаем, если нужно, координаты D, E;
рисуем (или добавляем в список отрисовки) полученные треугольники.
Осталось только добавить, что обрезание на самом деле надо проводить не плокостью z = -dist, а плоскостью z = -dist + smallvalue, smallvalue > 0, чтобы избежать проблем при проецировании.
3. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ
Дадим словесное описание алгоритма z-буфера.
Заполнить буфер кадра фоном, а z-буфер памяти — числом zmin.
Преобразовать многогранник в растровую форму:
ax + by + cz + d = 0 — плоскость.
(x1, y1, z1)
(x2, y2, z2)
...
(xn, yn, zn)
a = S(yi - yi+1) * (zi + zi+1)
b = S(zi - zi+1) * (xi + xi+1)
c = S(xi - xi+1) * (yi + yi+1)
z = -(ax + by + d)/c. Выражаем изменение плоскости вдоль одной из осей.
z - z' = -(ax1 + d)/c + (ax + d)/c = a(x - x1)/c
z1 = z - (a/c)Dx, но Dx = 1, поэтому
z1 = z - (a/c), где z1 — новая координата, а z — старая координата.
Вычислить для каждой точки (x, y) многоугольника значение z(x, y) — глубины нахождения в прямоугольнике.
Сравнить полученное z с соответствующим zбуфера, полученным по координатам в буфере.
Если вычисленное z меньше zбуфера, то изображение помещаем в буфер кадра, а zбуфера присваиваем z.
4. Список функций процедур программы.
procedure StartMainAlgoritmClick(Sender: TObject);
Главная процедура. Удаляет невидимые линии методм z-буфера.
procedure FormCreate(Sender: TObject);
Процедура инициализации формы.
procedure StepBtnClick(Sender: TObject);
Добавляет фигуру к сцене.
procedure ResetBtnClick(Sender: TObject);
Очищает экран.
procedure ExitBtnClick(Sender: TObject);
Выход из приложения
procedure InitZbuffer;
Создаёт z-буфер.
procedure InitScreenBuffer;
Создаёт пустой буфер экрана.
procedure DrawScreenBuffer;
Выводит на экран содержимое буфера.
function InitFigure:TFigures;
Возвращает случайную фигуру.
procedure MainAlgoritm(fig:TFigures);
Процедура реализующая метод z-буфера.
5. ОПИСАНИЕ ПРОГРАММЫ
5.1. Системные требования.
Для нормальной работы программы необходимо:
Процессор Intel 8086/88 или любые более поздние модели
Операционная система Windows
Монитор любой цветной
5.2. Руководство пользователя
Навигации по программе осуществляется с помощью панели управления, имеющей простой и понятный интерфейс:
5.3. Листинг
программы
unit Unit1; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, ExtCtrls, StdCtrls, ComCtrls;type TPoints = record x:integer; y:integer; z:integer; end; TFigures = record P:array[1..3]of TPoints; MinX,MinY,MaxX,MaxY:Word; A,B,C,D:integer; color:TColor; end; type TForm1 = class(TForm) Image: TImage; pb: TProgressBar; GroupBox1: TGroupBox; Label1: TLabel; CountEdit: TEdit; StartMainAlgoritm: TButton; StepBtn: TButton; ResetBtn: TButton; ExitBtn: TButton; GroupBox2: TGroupBox; procedure StartMainAlgoritmClick(Sender: TObject); procedure FormCreate(Sender: TObject); procedure StepBtnClick(Sender: TObject); procedure ResetBtnClick(Sender: TObject); procedure ExitBtnClick(Sender: TObject); procedure AboutBtnClick(Sender: TObject); private { Private declarations }procedure InitZbuffer;procedure InitScreenBuffer;procedure DrawScreenBuffer;function InitFigure:TFigures; public { Public declarations } end; var Form1: TForm1; MaxX,MaxY:Word; MinDepth:byte; Screenbuffer:array[1..400,1..400] of TColor; Zbuffer:array[1..400,1..400]of Byte; fig:TFigures; implementation {$R *.dfm}uses Unit2,Unit3; procedure TForm1.FormCreate(Sender: TObject);beginRandomize;MaxX:=Image.Width;MaxY:=Image.Height;MinDepth:=0;InitZbuffer;InitScreenBuffer;Image.Canvas.Refresh;end; procedure MainAlgoritm(fig:TFigures);vari,j:integer;z:Byte;color:TColor;beginfor j:=1 to MaxY dobegin for i:=1 to MaxX do begin color:=Form1.Image.Canvas.Pixels[i,j]; if(color=fig.color)then begin z:=round(-(fig.A*i + fig.B*j + fig.D)/fig.C); if(z>Zbuffer[i,j])then begin Zbuffer[i,j]:=z; Screenbuffer[i,j]:=color; end; end; end;end; end; procedure TForm1.StartMainAlgoritmClick(Sender: TObject);vari:integer;Count:integer;beginimage.Canvas.TextOut(150,150,'Пожалуйста подождите');try Count:=Strtoint(CountEdit.Text); pb.Max:=Strtoint(CountEdit.Text);except on EConvertError do begin MessageDlg('Введите правильное число!',mtWarning,[mbOK], 0); exit; end;end;pb.Position:=1; for i:=1 to Count do begin fig:=InitFigure; MainAlgoritm(fig); DrawScreenBuffer; pb.Position:=i+1; end; pb.Position:=0;end; procedure TForm1.StepBtnClick(Sender: TObject);begin pb.Max:=1; pb.Position:=1; fig:=InitFigure; MainAlgoritm(fig); DrawScreenBuffer; pb.Position:=0;end; procedure TForm1.ResetBtnClick(Sender: TObject);beginInitZbuffer;InitScreenBuffer;DrawScreenBuffer;end; procedure TForm1.AboutBtnClick(Sender: TObject);beginForm3.ShowModal;end; procedure TForm1.ExitBtnClick(Sender: TObject);beginClose;end; end. procedure InitZbuffer;vari,j:integer;beginfor i:=1 to MaxX dobegin for j:=1 to MaxY do begin Zbuffer[i,j]:=MinDepth; end;end;end; procedure InitScreenBuffer;vari,j:integer;beginfor i:=1 to MaxX dobegin for j:=1 to MaxY do begin ScreenBuffer[i,j]:=clWhite; end;end;end; procedure DrawScreenBuffer;vari,j:integer;beginwith Form1.Image.Canvas dobegin for i:=1 to MaxX do begin for j:=1 to MaxY do begin Pixels[i,j]:=Screenbuffer[i,j]; end; end;end;end; procedure Plane(var fig:TFigures);beginwith fig dobegin A:=p[1].y*(p[2].z-p[3].z) + p[2].y*(p[3].z-p[1].z) + p[3].y*(p[1].z-p[2].z); B:=p[1].z*(p[2].x-p[3].x) + p[2].z*(p[3].x-p[1].x) + p[3].z*(p[1].x-p[2].x); C:=p[1].x*(p[2].y-p[3].y) + p[2].x*(p[3].y-p[1].y) + p[3].x*(p[1].y-p[2].y); D:=-( p[1].x*(p[2].y*p[3].z - p[3].y*p[2].z) + p[2].x*(p[3].y*p[1].z - p[1].y*p[3].z) + p[3].x*(p[1].y*p[2].z - p[2].y*p[1].z) );end;end; procedure BorderPoints(var fig:TFigures);begin with fig do begin MinX:=Min(Min(p[1].x,p[2].x),p[3].x); MinY:=Min(Min(p[1].y,p[2].y),p[3].y); MaxX:=Max(Max(p[1].x,p[2].x),p[3].x); MaxY:=Max(Max(p[1].y,p[2].y),p[3].y); end;end; function InitFigure:TFigures;vari:byte;fig:TFigures;poligon:array[1..3]of TPoint;beginfor i:=1 to 3 dobegin fig.P[i].x:=Random(MaxX);poligon[i].X:=fig.P[i].x; fig.P[i].y:=Random(MaxY);poligon[i].Y:=fig.P[i].y; fig.P[i].z:=Random(254)+1; end;Plane(fig);BorderPoints(fig);fig.color:=Random($FFFFFF);Form1.Image.Canvas.Brush.Color:=fig.color;Form1.Image.Canvas.Pen.Color:=fig.color;Form1.Image.Canvas.Polygon(poligon);Result:=fig;end; end.
6
. ЛИТЕРАТУРА
1. П. В. Вельтмандер. Учебное пособие «Основные алгоритмы компьютерной графики».
2. А. В. Казанцев. Тексты специального курса лекций «Основы компьютерной графики»
3. А. Ю. Дёмин, А.В. Кудинов. Учебное пособие «Компьютерная графика».
4. Ньюмен. У., Спрулл Р. «Основы интерактивной машинной графики»
5. Котов И. И. «Алгоритмы машинной графики»
|
