Заливка полигона в строке развертки с использованием OPENGL в C
Опубликовано: 19 Января, 2022
Фигуры на экране компьютера можно рисовать с помощью многоугольников. Чтобы заполнить эти фигуры цветом, нам нужно разработать некоторый алгоритм. Для этого есть два известных алгоритма: алгоритмы заливки границы и заливки развертки.
Заполнение границ требует большой обработки и, следовательно, вызывает несколько проблем в реальном времени. Таким образом, жизнеспособной альтернативой является заполнение строк развертки, поскольку оно очень надежно по своей природе. В этой статье рассказывается, как использовать алгоритм заливки Scanline для заливки цвета изображения.
Алгоритм заполнения Scanline Polygon
Заполнение строк развертки - это заполнение полигонов горизонтальными линиями или строками развертки. Цель алгоритма SLPF - заполнить (раскрасить) внутренние пиксели многоугольника с учетом только вершин фигуры. Чтобы понять линию развертки, представьте, что изображение рисуется одним пером, начиная с нижнего левого угла, продолжая вправо, вычерчивая только те точки, в которых есть точка на изображении, а когда линия будет завершена, начните со следующей строки и Продолжить.
Этот алгоритм работает, пересекая линию развертки с краями многоугольника и заполняя многоугольник между парами пересечений.
Частные случаи вершин многоугольника:
- Если обе линии, пересекающиеся в вершине, находятся на одной стороне линии сканирования, считайте это двумя точками.
- Если линии, пересекающиеся в вершине, находятся на противоположных сторонах линии сканирования, считайте это только одной точкой.
Компоненты заливки полигона:
- Edge Buckets: он содержит информацию о ребре. Записи в граничном сегменте различаются в зависимости от структуры данных, которую вы использовали. В приведенном ниже примере есть три граничных сегмента, а именно: ymax, xofymin,
наклон обратный. - Таблица ребер: состоит из нескольких списков ребер -> содержит все ребра, составляющие фигуру. При создании рёбер необходимо упорядочить вершины рёбер слева направо, а три рёбра сохраняются в порядке возрастания yMin. Заполнение завершено, когда все края удалены из ET.
- Активный список: ИТ поддерживает текущие ребра, используемые для заполнения многоугольника. Ребра вставляются в AL из таблицы ребер, когда yMin ребра равен текущей обрабатываемой строке развертки.
Активный список будет пересортирован после каждого прохода.
Структура данных:
Алгоритм:
1. Мы будем обрабатывать ребро многоугольника за ребром и сохранять в таблице ребер.
2. Сохранение выполняется путем сохранения края в том же кортеже краев строки сканирования, что и
значение y-координаты края самой нижней точки.
3. После добавления любого ребра в набор ребер кортеж становится
отсортировано с использованием сортировки вставкой в соответствии с его значением xofymin.
4. После добавления всего многоугольника в таблицу ребер
фигура теперь заполнена.
5. Заполнение начинается с первой строки сканирования внизу,
и продолжал до самого верха.
6. Теперь активная таблица ребер занята и следующие вещи
повторяются для каждой строки сканирования:
я. Скопируйте все крайние сегменты указанной строки сканирования
в активный крайний кортеж
II. Выполните сортировку вставкой в соответствии с
к ценностям xofymin
iii. Удалите все краевые сегменты, у которых ymax равен
или больше, чем строка сканирования
iv. Заполнить пары ребер в активном кортеже, если есть вершина,
следуйте этим инструкциям:
o Если обе линии, пересекающиеся в вершине, находятся на
с той же стороны линии сканирования, считайте ее двумя точками.
o Если пересекающиеся в вершине прямые
противоположные стороны линии сканирования, считайте ее только одной точкой.
v. Обновите xofymin, добавив slopeinverse для каждого сегмента.
Образец изображения
Мы используем пример многоугольного динозавра. Вставьте следующее в текстовый файл в ту же папку, что и исполняемый файл, и переименуйте его в PolyDino.txt.
Ссылка: PolyDino.txt
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
// CPP program to illustrate// Scanline Polygon fill Algorithm #include <stdio.h>#include <math.h>#include <GL/glut.h>#define maxHt 800#define maxWd 600#define maxVer 10000 FILE *fp; // Start from lower left cornertypedef struct edgebucket { int ymax; //max y-coordinate of edge float xofymin; //x-coordinate of lowest edge point updated only in aet float slopeinverse;}EdgeBucket; typedef struct edgetabletup{ // the array will give the scanline number // The edge table (ET) with edges entries sorted // in increasing y and x of the lower end int countEdgeBucket; //no. of edgebuckets EdgeBucket buckets[maxVer];}EdgeTableTuple; EdgeTableTuple EdgeTable[maxHt], ActiveEdgeTuple; // Scanline Functionvoid initEdgeTable(){ int i; for (i=0; i<maxHt; i++) { EdgeTable[i].countEdgeBucket = 0; } ActiveEdgeTuple.countEdgeBucket = 0;} void printTuple(EdgeTableTuple *tup){ int j; if (tup->countEdgeBucket) printf("
Count %d-----
",tup->countEdgeBucket); for (j=0; j<tup->countEdgeBucket; j++) { printf(" %d+%.2f+%.2f", tup->buckets[j].ymax, tup->buckets[j].xofymin,tup->buckets[j].slopeinverse); }} void printTable(){ int i,j; for (i=0; i<maxHt; i++) { if (EdgeTable[i].countEdgeBucket) printf("
Scanline %d", i); printTuple(&EdgeTable[i]); } } /* Function to sort an array using insertion sort*/void insertionSort(EdgeTableTuple *ett){ int i,j; EdgeBucket temp; for (i = 1; i < ett->countEdgeBucket; i++) { temp.ymax = ett->buckets[i].ymax; temp.xofymin = ett->buckets[i].xofymin; temp.slopeinverse = ett->buckets[i].slopeinverse; j = i - 1; while ((temp.xofymin < ett->buckets[j].xofymin) && (j >= 0)) { ett->buckets[j + 1].ymax = ett->buckets[j].ymax; ett->buckets[j + 1].xofymin = ett->buckets[j].xofymin; ett->buckets[j + 1].slopeinverse = ett->buckets[j].slopeinverse; j = j - 1; } ett->buckets[j + 1].ymax = temp.ymax; ett->buckets[j + 1].xofymin = temp.xofymin; ett->buckets[j + 1].slopeinverse = temp.slopeinverse; }} void storeEdgeInTuple (EdgeTableTuple *receiver,int ym,int xm,float slopInv){ // both used for edgetable and active edge table.. // The edge tuple sorted in increasing ymax and x of the lower end. (receiver->buckets[(receiver)->countEdgeBucket]).ymax = ym; (receiver->buckets[(receiver)->countEdgeBucket]).xofymin = (float)xm; (receiver->buckets[(receiver)->countEdgeBucket]).slopeinverse = slopInv; // sort the buckets insertionSort(receiver); (receiver->countEdgeBucket)++; } void storeEdgeInTable (int x1,int y1, int x2, int y2){ float m,minv; int ymaxTS,xwithyminTS, scanline; //ts stands for to store if (x2==x1) { minv=0.000000; } else { m = ((float)(y2-y1))/((float)(x2-x1)); // horizontal lines are not stored in edge table if (y2==y1) return; minv = (float)1.0/m; printf("
Slope string for %d %d & %d %d: %f",x1,y1,x2,y2,minv); } if (y1>y2) { scanline=y2; ymaxTS=y1; xwithyminTS=x2; } else { scanline=y1; ymaxTS=y2; xwithyminTS=x1; } // the assignment part is done..now storage.. storeEdgeInTuple(&EdgeTable[scanline],ymaxTS,xwithyminTS,minv); } void removeEdgeByYmax(EdgeTableTuple *Tup,int yy){ int i,j; for (i=0; i< Tup->countEdgeBucket; i++) { if (Tup->buckets[i].ymax == yy) { printf("
Removed at %d",yy); for ( j = i ; j < Tup->countEdgeBucket -1 ; j++ ) { Tup->buckets[j].ymax =Tup->buckets[j+1].ymax; Tup->buckets[j].xofymin =Tup->buckets[j+1].xofymin; Tup->buckets[j].slopeinverse = Tup->buckets[j+1].slopeinverse; } Tup->countEdgeBucket--; i--; } }} void updatexbyslopeinv(EdgeTableTuple *Tup){ int i; for (i=0; i<Tup->countEdgeBucket; i++) { (Tup->buckets[i]).xofymin =(Tup->buckets[i]).xofymin + (Tup->buckets[i]).slopeinverse; }} void ScanlineFill(){ /* Follow the following rules: 1. Horizontal edges: Do not include in edge table 2. Horizontal edges: Drawn either on the bottom or on the top. 3. Vertices: If local max or min, then count twice, else count once. 4. Either vertices at local minima or at local maxima are drawn.*/ int i, j, x1, ymax1, x2, ymax2, FillFlag = 0, coordCount; // we will start from scanline 0; // Repeat until last scanline: for (i=0; i<maxHt; i++)//4. Increment y by 1 (next scan line) { // 1. Move from ET bucket y to the // AET those edges whose ymin = y (entering edges) for (j=0; j<EdgeTable[i].countEdgeBucket; j++) { storeEdgeInTuple(&ActiveEdgeTuple,EdgeTable[i].buckets[j]. ymax,EdgeTable[i].buckets[j].xofymin, EdgeTable[i].buckets[j].slopeinverse); } printTuple(&ActiveEdgeTuple); // 2. Remove from AET those edges for // which y=ymax (not involved in next scan line) removeEdgeByYmax(&ActiveEdgeTuple, i); //sort AET (remember: ET is presorted) insertionSort(&ActiveEdgeTuple); printTuple(&ActiveEdgeTuple); //3. Fill lines on scan line y by using pairs of x-coords from AET j = 0; FillFlag = 0; coordCount = 0; x1 = 0; x2 = 0; ymax1 = 0; ymax2 = 0; while (j<ActiveEdgeTuple.countEdgeBucket) { if (coordCount%2==0) { x1 = (int)(ActiveEdgeTuple.buckets[j].xofymin); ymax1 = ActiveEdgeTuple.buckets[j].ymax; if (x1==x2) { /* three cases can arrive- 1. lines are towards top of the intersection 2. lines are towards bottom 3. one line is towards top and other is towards bottom */ if (((x1==ymax1)&&(x2!=ymax2))||((x1!=ymax1)&&(x2==ymax2))) { x2 = x1; ymax2 = ymax1; } else { coordCount++; } } else { coordCount++; } } else { x2 = (int)ActiveEdgeTuple.buckets[j].xofymin; ymax2 = ActiveEdgeTuple.buckets[j].ymax; FillFlag = 0; // checking for intersection... if (x1==x2) { /*three cases can arive- 1. lines are towards top of the intersection 2. lines are towards bottom 3. one line is towards top and other is towards bottom */ if (((x1==ymax1)&&(x2!=ymax2))||((x1!=ymax1)&&(x2==ymax2))) { x1 = x2; ymax1 = ymax2; } else { coordCount++; FillFlag = 1; } } else { coordCount++; FillFlag = 1; } if(FillFlag) { //drawing actual lines... glColor3f(0.0f,0.7f,0.0f); glBegin(GL_LINES); glVertex2i(x1,i); glVertex2i(x2,i); glEnd(); glFlush(); // printf("
Line drawn from %d,%d to %d,%d",x1,i,x2,i); } } j++; } // 5. For each nonvertical edge remaining in AET, update x for new y updatexbyslopeinv(&ActiveEdgeTuple);} printf("
Scanline filling complete"); } void myInit(void){
РЕКОМЕНДУЕМЫЕ СТАТЬИ |