Cтраница 3
В список XSORT входят все отрезки, которые рассматривались на предыдущей сканирующей строке. [31]
После начала обработки некоторой сканирующей строки элемент YENTER, соответствующий этой строке, используется для нахождения ребер, которые необходимо добавить к текущему списку отрезков. Если ребро принадлежит двум многоугольникам, то при появлении этого ребра на сканирующей строке могут быть построены отрезки для каждого из многоугольников. [32]
Есть одна тонкость при сравнении значений координат Ха ребер: если два ребра имеют точно совпадающие координаты Xs, то вместо собственно координат сравниваются приращенияDX ] eft или DXright-В этом случае для двух ребер, входящих в рассмотрение точно в одной и той же точке ( что имеет место для большинства ребер), будет сое-тавдено правильное описание отрезков. Например, оба ребра Е2 и ЕЗ ( рис. ШЛО) начинаются на одной сканирующей строке. [33]
В результате создаются изображения, отличающиеся от требуемого только искажениями изображений трехмерных объектов и теней от них. В требуемых условиях наблюдения и освещения, которые были уже однажды использованы для трансформирования, методом сканирующей строки строят синтезированное изображение ( рис. 6.5.3 е) трехмерных объектов, отдельно храня участки изображений объектов с собственными тенями и участки падающих теней. Так как изображения ( рис. 6.5.3 г е) порождены при одних и тех же условиях, то они геометрически совпадают, и задача сводится к их комбинированию. Последнее производится путем замещения участков мощности участками изображений объектов с собственными тенями и понижением яркости изображения местности в зонах падающих теней. [34]
На рисунке можно увидеть отношение глубины обоих отрезков, а также их части, закрытые другими частями. Но ситуация может оказаться и очень сложной, что показано на рис. 14.25. В этом случае недетерминированная процедура обработки сканирующих строк выдает отказ. Тогда сканирующая строка может быть разделена по всей длине на более мелкие отрезки, или пробные интервалы. Каждый интервал определен его левым и правым концами, что в экранных координатах соответствует SPANleft и SPANright. Затем к этим интервалам применяется та же самая процедура. [35]
При использовании в алгоритме свойства подобия сканирующих строк может быть достигнута значительная экономия времени вычисления. Вполне разумно предположить, что если в некотором интервале от одной граничной точки отрезка до другой ( рис. 14.36) налицо простой случай для k - й сканирующей строки, то и для ( k 1) - й линии имеет место тот же случай. [36]
Алгоритм построчного сканирования с использованием z - буфера также может использоваться для изображения сцен, составленных из многоугольников. В отличие от интервального алгоритма, вде освещенность на сканирующей строке определяется большими прыжками - от интервала к интервалу, здесь анализируется каждый пиксел. Сканирующая строка пересекается с каждым многоугольником ( выпуклым) дважды: один раз при входе и один раз при выходе. До этапа определения видимости для каждой сканирующей строки буфер освещенности заполняется некоторым фоновым значением, а текущее значение глубины от рецептора до наблюдаемой точки фона заносится в z - буфер. Оба буфера представляют собой матрицы-строки с числом элементов, равным числу пикселов в строке. Далее анализируется каждый пиксел на сканирующей строке в интервале между входом в треугольник и выходом из него путем сравнения глубины этого пиксела с глубиной, содержащейся в z - буфере. Если рассматриваемый пиксел лежит ближе к наблюдателю, чем буферное значение, то отрезок, на котором лежит пиксел, будет невидимым. По параметрам соответствующего многоугольника вычисляют освещенность и новое значение глубины заносят в z - буфер. [37]
На рисунке можно увидеть отношение глубины обоих отрезков, а также их части, закрытые другими частями. Но ситуация может оказаться и очень сложной, что показано на рис. 14.25. В этом случае недетерминированная процедура обработки сканирующих строк выдает отказ. Тогда сканирующая строка может быть разделена по всей длине на более мелкие отрезки, или пробные интервалы. Каждый интервал определен его левым и правым концами, что в экранных координатах соответствует SPANleft и SPANright. Затем к этим интервалам применяется та же самая процедура. [38]
Геометрическим местом пересечения окна сканирующей строки с плоским многоугольником будет набор прямолинейных отрезков. На рис. 14.21 показан вид этих отрезков в плоскости Xs - Ys. На заданной сканирующей строке многоугольник может быть описан параметрами отрезков пересечения. Например, многоугольник имеет один отрезок пересечения с окном сканирующей строки, имеющим координату Ys - а. Этот отрезок задается координатами Xs сторон многоугольника, ограничивающих отрезок. Например, при Ys а отрезок ограничен сторонами AD и АВ. [39]
Приведенных выше подробностей достаточно для построения программы удаления невидимых линий. Скорость работы программы можно значительно повысить за счет использования связности сканирующих строк. Составим список значений величин SPANrlgbi пробных точек, которые делят сканирующую строку на интервалы, каждый из которых уже не подвергается дальнейшему делению. [40]
В примере, рассмотренном на рис. 14.37, точки подразделяют каждую сканирующую строку на предсказанные пробные интервалы. Точки называются предсказанными пробными точками. При хорошей связности между сканирующими строками вычисление точки подразделения интервалов производится редко. [41]
Алгоритм построчного сканирования с использованием z - буфера также может использоваться для изображения сцен, составленных из многоугольников. В отличие от интервального алгоритма, вде освещенность на сканирующей строке определяется большими прыжками - от интервала к интервалу, здесь анализируется каждый пиксел. Сканирующая строка пересекается с каждым многоугольником ( выпуклым) дважды: один раз при входе и один раз при выходе. До этапа определения видимости для каждой сканирующей строки буфер освещенности заполняется некоторым фоновым значением, а текущее значение глубины от рецептора до наблюдаемой точки фона заносится в z - буфер. Оба буфера представляют собой матрицы-строки с числом элементов, равным числу пикселов в строке. Далее анализируется каждый пиксел на сканирующей строке в интервале между входом в треугольник и выходом из него путем сравнения глубины этого пиксела с глубиной, содержащейся в z - буфере. Если рассматриваемый пиксел лежит ближе к наблюдателю, чем буферное значение, то отрезок, на котором лежит пиксел, будет невидимым. По параметрам соответствующего многоугольника вычисляют освещенность и новое значение глубины заносят в z - буфер. [42]
Таким образом, экран покрывают множеством точек, соответствующих положению на изображении вершин выпуклых многогранников. Объединение точек 21 - 1, 21, N4 - 21 - 1, N21 отрезками прямых в такой последовательности является границей изображения 1-го бокового прямоугольника в томографическом срезе. В результате задействования этого алгоритма для каждого чггрезка сканирующей строки становится известна информация о номере видимой плоскости - прямоугольника или номере торцевой плоскости, ограничивающей томографический срез. Для вычисления освещенности изображения на каждом участке сканирующей линии необходимо определить нормальный вектор к поверхностям каждого 1-го прямоугольника и к поверхностям торцевых плоскостей. [43]
На рис. 6.5.4 - 6.5.6 приведены результаты компьютерного моделирования изображений застройки на фоне конкретной местности. Изображения на рис. 6.5.4 и 6.5.5 получены методом трассирования лучей с использованием процедур, приведенных в приложении. Третья сцена ( рис. 6.5.6) получена методом сканирующей строки. Технология ее производства включает следующие этапы: получение аэрофотоизображения, определение формы зданий и их высот, интерактивное удаление изображений зданий с оцифрованного аэрофотоизображения, построение математической модели зданий, создание модели сцены из зданий и естественного ландшафта, компьютерное моделирование синтезированного изображения. [44]
Геометрическим местом пересечения окна сканирующей строки с плоским многоугольником будет набор прямолинейных отрезков. На рис. 14.21 показан вид этих отрезков в плоскости Xs - Ys. На заданной сканирующей строке многоугольник может быть описан параметрами отрезков пересечения. Например, многоугольник имеет один отрезок пересечения с окном сканирующей строки, имеющим координату Ys - а. Этот отрезок задается координатами Xs сторон многоугольника, ограничивающих отрезок. Например, при Ys а отрезок ограничен сторонами AD и АВ. [45]