15.9. Алгоритмы для криволинейных поверхностей
Рассмотренные выше алгоритмы применимы лишь к объектам, состоящим из плоских граней. Чтобы воспользоваться любым из них для изображения объектов, ограниченных криволинейными поверхностями, необходимо предварительно аппроксимировать эти объекты большим числом мелких граней. Хотя это можно сделать, часто удобнее работать непосредственно с криволинейными поверхностями.
Квадратичные поверхности в общем случае являются неплоскими и могут быть записаны в аналитическом виде
Если коэффициенты а^—а6 равны нулю, поверхность вырождается в плоскость. Хорошо известными объектами, состоящими из квадратичных поверхностей, являются сфера (одна поверхность), закрытый цилиндр (три поверхности), закрытый конус (две поверхности) и эллипсоид (одна поверхность). В работе [303] рассмотрен полный набор программ для описания и изображения объектов, составленных из квадратичных поверхностей. Объект, изображенный на вклейке 14, составлен из квадратичных поверхностей.
Вейс [496], Вун 1512], Мол [297] и Левин [283] разработали несколько алгоритмов, которые позволяют удалять скрытые поверхности у объектов, заданных квадратичными поверхностями. В этих алгоритмах определяются пересечения двух квадратичных поверхностей, что приводит к уравнению четвертого порядка относительно х, у и г, корни которого находятся численными методами. Левину удалось понизить порядок уравнения до второго путем параметризации кривых пересечения.
Со сферами, которые являются частным случаем квадратичных поверхностей, работать легче и, кроме того, они заслуживают особого внимания, поскольку молекулы обычно изображаются в виде совокупностей раскрашенных в разные цвета сфер (цветная вкладка, 15). Существует ряд алгоритмов, предназначенных для изображения молекул [269, 306, 377, 378, 442].
Более универсальными являются параметрические бикубические поверхности, рассмотренные в гл. 13, поскольку обладают большей общностью и обеспечивают непрерывность касательной на границах куска. Алгоритм, позволяющий изображать такие поверхности, впервые предложен Кэтмулом [82]. Разбиение куска (по s и по t) производится до тех пор, пока его проекция на плоскость экрана не станет примерно равной размеру пэла. Определение видимости такой маленькой области (относительно всех ранее рассмотренных кусков) выполняется с помощью алгоритма, использующего z-буфер. Вычисляется закраска этой области, и соответствующее значение помещается в буфер регенерации. Метод Кэтмула не очень быстр, но весьма эффективен. Этот подход оказал значительное влияние на выбор направлений дальнейших исследований; примерами могут служить работы [42] и [506].
Блинн и Уиттед разработали два различных алгоритма построчного сканирования [46]. Алгоритм Блинна работает непосредственно с параметрическим представлением. Для сканирующей строки у=а определяются все значения s и t, удовлетворяющие уравнению
Затем эти значения используются для вычисления x(s, t) и 2(s, t). К сожалению, уравнение (15.9) не решается в общем виде, поэтому его корни определяются численно с помощью метода Ньютона. В частных случаях, когда корни не существуют, алгоритм не работает. В алгоритме Уиттеда также применяются численные методы в совокупности с аппроксимациями кривой, расположенной в плоскости хг и задаваемой пересечением плоскости у=а с бикубическим куском поверхности.
На сегодняшний день наиболее плодотворным является подход, который основан на адаптивном процессе разбиения бикубических кусков, продолжающемся до тех пор, пока каждый из получающихся в результате деления кусочков не станет достаточно плоским. Допустимые отклонения определяются разрешающей способностью дисплея, а также ориентацией подразделяемой области относительно картинной плоскости. Поэтому разбиения, в которых нет необходимости, не производятся. После завершения процесса разбиения мелкие многоугольники, задаваемые четырьмя угловыми точками каждого из получившихся в результате деления кусков, обрабатываются при помощи алгоритма построчного сканирования. Тем самым мы получаем возможность одновременно использовать многогранные и бикубические поверхности.
Карпентер и Лэйн [46, 279], а также Кларк, используя этот подход, разработали другие алгоритмы, которые отличаются выбором базовых функций, используемых для получения разностных уравнений (последние описывают разбиение кусков поверхности), а также проверками на «спрямленность». В алгоритме Карпентера и Лейна разбиения производятся только в случае необходимости, т. е. когда обрабатываемая сканирующая строка пересекает кусок поверхности. Тем самым в алгоритме Кларка этот процесс выполняется заранее, при проведении предварительной обработки. Первый метод существенно экономнее в отношении памяти, однако, используя второй метод, можно обойтись меньшим числом разбиений и, кроме того, гарантировать, что в кусок бикубической поверхности в процессе разбиения будут внесены разрывы.
Развивая идеи, высказанные в работах [12, 306], Уиттед предложил изящный и простой (хотя медленный) алгоритм, позволяющий обрабатывать полигональные, бикубические, квадратичные и другие куски (гл. 16). С помощью этого алгоритма вычисляется закраска и выводятся на экран прозрачные и полупрозрачные поверхности.
- 1. Векторные дисплеи.
- 2. Растровые дисплеи.
- Программистская модель интерактивной графики
- Лекция 2
- 640X480
- Лекция 4. Анимация
- Лекция 7. Алгоритмы растровой графики. Растровая графика.
- Лекция 9
- Перспективные проекции
- 15.1. Введение
- 15.2. Упрощение сравнений по глубине: перспективное преобразование
- 15.3. Исключение сравнений по глубине. Оболочки
- 15.4. Алгоритм сортировки по глубине
- 15.5. Алгоритм, использующий z-буфер
- 15.6. Алгоритмы построчного сканирования
- 15.7. Алгоритмы разбиения области
- 15.8. Эффективность алгоритма
- 15.9. Алгоритмы для криволинейных поверхностей
- Введение в OpenGl
- Void glVertex[2 3 4][s I f d] (type coords)
- Void glVertex[2 3 4][s I f d]V (type *coords)
- Gl_points каждая вершина задает координаты некоторой точки. Gl_lines каждая отдельная пара вершин определяет отрезок; ес-ли задано нечетное число вершин, то последняя вершина игнорируется.
- Gl_polygon последовательно задаются вершины выпуклог многоугольника.
- OpenGl в Delphi
- Событие. Сообщение. Контекст.