Упрощение: заполнение «горизонтально-выпуклых» полигонов Алгоритм в листинге 10.8 может быть значительно упрощен, если известно, что полигон, подлежащий заполнению, в каждой строке развертки имеет только одно левое и одно правое ребро. Такие полигоны можно назвать «горизонтально-выпуклыми» («horizontally convex»)1. Очевидно, что каждый выпуклый полигон является также и горизонтально-выпуклым. Горизонтально-выпуклыми являются все треугольники; что же касается четырехугольников, то некоторые из них являются горизонтально-выпуклыми, а некоторые - нет. (Нарисуйте несколько горизонтально-выпуклых полигонов.)
Основное упрощение алгоритма заключается в том, что в случае горизонтально-выпуклых полигонов список AEL всегда содержит ровно два ребра. Это обстоятельство значительно упрощает работу со списком. Подробности рассматриваются в тематическом задании 10.7.
OpenGL способен значительно ускорить визуализацию сложных трехмерных сцен, когда в подпрограмму визуализации поступают только горизонтально-выпуклые прямоугольники. К счастью, большинство программ моделирования представляют формы для визуализации только в виде выпуклых полигонов.
Практические упражнения
10.7.2. Алгоритм плоского закрашивания Алгоритм плоского закрашивания (table-fill algorithm) очень быстро осуществляет заполнение определенного класса полигонов. Каждое ребро такого полигона вначале подвергается, пиксел за пикселом, сканирующему преобразованию (возможно, с помощью алгоритма Брезенхема), в результате которого создаются пары точек (х, у), расположенные вдоль ребер полигона. При формировании каждой такой
1 Полигон является горизонтально-выпуклым, если прямая лшшя между двумя любыми точками внутри полигона, имеющими одну и туже ординату у, целиком лежит внутри этого полигона.
Средства для растровой графики
пары (х, у) производится ее сравнение с двумя массивами min[y] и тах[у], в которых для каждого значения у содержатся минимальное и максимальное значения абсцисс х, встретившиеся до этого момента. Если x<min[y], то в массив min[y] вносится новое значение абсциссы х; аналогичные операции делаются для массива тах[у]. Затем весь полигон закрашивается посредством рисования серий пикселов от min[y] до тах[у] для каждой строки развертки у. Никакой сортировки не требуется, что и обеспечивает быстроту данного алгоритма.