Алгоритмы построчного сканирования для криволинейных поверхностей

Идея построчного сканирования, предложенная в 1967 г. Уайли, Ромни, Эвансом и Эрдалом, заключалась в том, что сцена обрабатывается в порядке прохождения сканирующей прямой. В объектном пространстве это соответствует проведению секущей плоскости, перпендикулярной пространству изображения. Строго говоря, алгоритм работает именно в пространстве изображения, отыскивая точки пересечения сканирующей прямой с ребрами многоугольников, составляющих картину (для случая изображения многогранников). Но при пересечении очередного элемента рисунка выполняется анализ глубины полученной точки и сравнение ее с глубиной других точек на сканирующей плоскости. В некоторых случаях можно построить список ребер, упорядоченный по глубине, но зачастую это невозможно выполнить корректно. Поэтому сканирование сочетают с другими методами.

Один из таких методов мы уже рассматривали - метод Z–буфера, в котором буфер инициализируется заново для каждой сканирующей строки. Другой метод называют интервальным алгоритмом построчного сканирования. В нем сканирующая строка разбивается проекциями точек пересечения ребер многоугольников на интервалы, затем в каждом из интервалов выбираются видимые отрезки. В этой ситуации их уже можно отсортировать по глубине. Мы остановимся чуть подробнее на методе построчного сканирования для криволинейных поверхностей.

В описании метода приоритетов поверхность задавалась в виде функции двух переменных, здесь мы будем задавать поверхность параметрическими уравнениями:

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

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

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