17.4. РАСТРОВЫЙ АЛГОРИТМ ПОСТРОЧНОГО РАЗДЕЛЕНИЯ ВИДИМЫХ И НЕВИДИМЫХ ЭЛЕМЕНТОВ СЦЕНЫ

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

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

Рис. 17.7. Иллюстрация к работе алгоритма построчного разделения видимых и невидимых элементов сцены: а — проекция куба, изображение которого должно быть воспроизведено, и плоскости, задаваемой уравнением постоянная, на плоскость — проекция фигуры, полученной в результате пересечения, на плоскость и на строку развертки

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

Этот подход реализован в алгоритме 17.2. Основную часть алгоритма составляют шаги 3—6; лаконичность описания алгоритма связана с тем, что на некоторых его шагах выполняются операции, которые были подробно описаны в предыдущей части нашей книги. Если воспроизводимая сцена изменяется во времени, то необходимо для каждого значения у найти пересечения всех граней с плоскостями, задаваемыми уравнениями постоянная. Эта операция выполняется на шаге 4. При ее реализации необходимо использовать алгоритм разрезания типа алгоритма 15.1 (или алгоритма 15.3, если грани невыпуклые). Разрезаемый многоугольник представляет собой проекцию грани на плоскость а разрезающая прямая определяется пересечением плоскости постоянная с плоскостью проекции. Результатом работы алгоритма является множество сегментов, расположенных на плоскости

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

После выполнения шага 4 необходимо установить, какие сегменты затеняют другие сегменты (эта процедура была рассмотрена в подразд. 14.4.4). Описанный там подход можно использовать непосредственно и получать в результате некоторый список видимых сегментов. В алгоритме 17.2 применен иной способ. Заводятся два массива COLOR (ЦВЕТ) и DEPTH (ГЛУБИНА), элементы которых соответствуют пикселам, расположенным вдоль строки развертки. В массиве COLOR хранится цвет определенного пиксела, а в массиве DEPTH — значение координаты сегмента, расположенного ближе всех остальных по отношению к наблюдателю. Для каждой строки развертки в качестве начального значения массива COLOR задается цвет фона, а в качестве начального значения массива DEPTH-максимально допустимое значение координаты Алгоритм при обработке сегмента, расположенного на плоскости (например, сегмента ВС на рис. 17.7), сравнивает значения координаты z точек этого сегмента со значением х, соответствующим тому же значению координаты х и хранящимся в массиве DEPTH. Если значение точки меньше

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

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

Обозначения. Массив COLOR является буфером для хранения значения цвета воспроизводимого пиксела. Массив DEPTH содержит значение точки, расположенной ближе всего к наблюдателю, для каждого значения х строки развертки. Р — отрезок прямой, образованный пересечением грани со строкой развертки — координаты точек и Р соответственно.

(см. скан)