Рубрики

Scan-line полигональная заливка с использованием OPENGL в C

Рисунки на экране компьютера могут быть нарисованы с помощью полигонов. Чтобы залить эти цифры цветом, нам нужно разработать некоторый алгоритм. Для этого есть два известных алгоритма: заполнение границ и алгоритмы заполнения Scanline.

Заполнение границ требует большой обработки и, таким образом, сталкивается с небольшими проблемами в режиме реального времени. Таким образом, жизнеспособной альтернативой является заполнение сканлайн, поскольку оно очень устойчивое по своей природе. В этой статье обсуждается, как использовать алгоритм заполнения Scanline для заливки цветов в изображении.

Алгоритм заполнения полигонов Scanline

Заполнение Scanline — это в основном заполнение полигонов горизонтальными линиями или линиями сканирования. Цель алгоритма SLPF — заполнить (покрасить) внутренние пиксели многоугольника, учитывая только вершины фигуры. Чтобы понять Scanline, представьте, что изображение нарисовано одной ручкой, начиная с нижнего левого края и продолжая направо, рисуя только точки, в которых есть точка на изображении, а когда линия завершена, начните со следующей строки и Продолжить.
Этот алгоритм работает путем пересечения линии сканирования с ребрами многоугольника и заполняет многоугольник между парами пересечений.

Частные случаи вершин многоугольника:

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

Компоненты многоугольной заливки:

  1. Edge Buckets: содержит информацию о ребре. Записи краевого сегмента варьируются в зависимости от используемой структуры данных. В приведенном ниже примере есть три краевых сегмента, а именно: ymax, xofymin,
    slopeinverse.
  2. Таблица ребер : состоит из нескольких списков ребер -> содержит все ребра, составляющие фигуру. При создании ребер вершины ребра необходимо упорядочивать слева направо, а ребра сохраняются в порядке возрастания yMin. Заполнение завершено, как только все края удалены из ET
  3. Активный список: IT поддерживает текущие ребра, используемые для заполнения многоугольника. Края вставляются в AL из таблицы ребер, когда yMin ребра равен текущей обрабатываемой линии сканирования.
    Активный список будет пересортирован после каждого прохода.

Структура данных:

Algorithm:

1. We will process the polygon edge after edge, and store in the edge Table.
2. Storing is done by storing the edge in the same scanline edge tuple as 
   the lowermost point's y-coordinate value of the edge.
3. After addition of any edge in an edge tuple, the tuple is 
   sorted using insertion sort, according to its xofymin value.
4. After the whole polygon is added to the edge table, 
   the figure is now filled.
5. Filling is started from the first scanline at the bottom,
   and continued till the top.
6. Now the active edge table is taken and the following things 
   are repeated for each scanline:
       i. Copy all edge buckets of the designated scanline 
          to the active edge tuple
       ii. Perform an insertion sort according
          to the xofymin values
       iii. Remove all edge buckets whose ymax is equal 
            or greater than the scanline
       iv. Fillup pairs of edges in active tuple, if any vertex is got, 
           follow these instructions:
            o If both lines intersecting at the vertex are on
              the same side of the scanline, consider it as two points.
            o If lines intersecting at the vertex are at 
              opposite sides of the scanline, consider it as only one point.
       v. Update the xofymin by adding slopeinverse for each bucket.
   

Образец изображения

Мы используем пример многоугольника динозавра. Вставьте следующее в текстовый файл в той же папке, что и исполняемый файл, и переименуйте его в PolyDino.txt.
Ссылка: PolyDino.txt

// Программа CPP для иллюстрации
// 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;

  
// Начинаем с левого нижнего угла

typedef struct edgebucket 

{

    int ymax;   // max y-координата ребра

    float xofymin;  // координата x нижней точки обновляется только в aet

    float slopeinverse;

}EdgeBucket;

  

typedef struct edgetabletup

{

    // массив выдаст номер строки

    // Таблица ребер (ET) с отсортированными записями ребер

    // в увеличении y и x нижнего конца

      

    int countEdgeBucket;    нет // нет. краев

    EdgeBucket buckets[maxVer];

}EdgeTableTuple;

  
EdgeTableTuple EdgeTable[maxHt], ActiveEdgeTuple;

  

  
// Функция Scanline

void 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("\nCount %d-----\n",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("\nScanline %d", i);

              

        printTuple(&EdgeTable[i]);

    

}

  

  
/ * Функция для сортировки массива с использованием вставки 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)

{

    // оба используются для таблицы ребер и активной таблицы ребер.

    // Кортеж ребер отсортирован по возрастанию ymax и x нижнего конца.

    (receiver->buckets[(receiver)->countEdgeBucket]).ymax = ym;

    (receiver->buckets[(receiver)->countEdgeBucket]).xofymin = (float)xm;

    (receiver->buckets[(receiver)->countEdgeBucket]).slopeinverse = slopInv;

              

    // сортируем ведра

    insertionSort(receiver);

          

    (receiver->countEdgeBucket)++; 

      

      
}

  

void storeEdgeInTable (int x1,int y1, int x2, int y2)

{

    float m,minv;

    int ymaxTS,xwithyminTS, scanline; // тс означает хранить

      

    if (x2==x1)

    {

        minv=0.000000;

    }

    else

    {

    m = ((float)(y2-y1))/((float)(x2-x1));

      

    // горизонтальные линии не сохраняются в таблице ребер

    if (y2==y1)

        return;

          

    minv = (float)1.0/m;

    printf("\nSlope 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;     

    }

    // задание выполнено .. теперь хранилище ..

    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("\nRemoved 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()

{

    / * Следуйте следующим правилам:

    1. Горизонтальные ребра: не включать в таблицу ребер

    2. Горизонтальные края: нарисованы либо снизу, либо сверху.

    3. Вершины: если локальный максимум или минимум, то считайте дважды, иначе считайте

        один раз.

    4. Рисуются либо вершины в локальных минимумах, либо в локальных максимумах. * /

  

  

    int i, j, x1, ymax1, x2, ymax2, FillFlag = 0, coordCount;

      

    // мы начнем с scanline 0;

    // Повторяем до последней строки сканирования:

    for (i=0; i<maxHt; i++)// 4. Увеличьте y на 1 (следующая строка сканирования)

    {

          

        // 1. Переместимся из ET-корзины на

        // AET те ребра, у которых ymin = y (входящие ребра)

        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. Удалить из AET эти края для

        // который y = ymax (не участвует в следующей строке сканирования)

        removeEdgeByYmax(&ActiveEdgeTuple, i);

          

        // сортировка AET (помните: ET предварительно отсортирован)

        insertionSort(&ActiveEdgeTuple);

          

        printTuple(&ActiveEdgeTuple);

          

        // 3. Заполните линии на линии сканирования y, используя пары координат x из 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)

                {

                / * три случая могут прибыть-

                    1. линии к вершине пересечения

                    2. линии направлены вниз

                    3. одна линия направлена вверх, а другая - снизу

                * /

                    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;

                  

                // проверка на пересечение ...

                if (x1==x2)

                {

                / * три случая могут быть

                    1. линии к вершине пересечения

                    2. линии направлены вниз

                    3. одна линия направлена вверх, а другая - снизу

                * /

                    if (((x1==ymax1)&&(x2!=ymax2))||((x1!=ymax1)&&(x2==ymax2)))

                    {

                        x1 = x2;

                        ymax1 = ymax2;

                    }

                    else

                    {

                        coordCount++;

                        FillFlag = 1;

                    }

                }

                else

                {

                        coordCount++;

                        FillFlag = 1;

                

              

              

            if(FillFlag)

            {

                // рисуем реальные линии ...

                glColor3f(0.0f,0.7f,0.0f);

                  

                glBegin(GL_LINES);

                glVertex2i(x1,i);

                glVertex2i(x2,i);

                glEnd();

                glFlush();         

                  

                // printf ("/ nLine рисуется от% d,% d до% d,% d", x1, i, x2, i);

            }

              

        }

              

        j++;

    

              

          

    // 5. Для каждого невертикального ребра, остающегося в AET, обновляем x для нового y

    updatexbyslopeinv(&ActiveEdgeTuple);

}

  

  

printf("\nScanline filling complete");

  
}

  

  

void myInit(void)

{

  

    glClearColor(1.0,1.0,1.0,0.0);

    glMatrixMode(GL_PROJECTION);

      

    glLoadIdentity();

    gluOrtho2D(0,maxHt,0,maxWd);

    glClear(GL_COLOR_BUFFER_BIT);

}

  

void drawPolyDino()

{

  

    glColor3f(1.0f,0.0f,0.0f);

    int count = 0,x1,y1,x2,y2;

    rewind(fp);

    while(!feof(fp) )

    {

        count++;

        if (count>2)

        {

            x1 = x2;

            y1 = y2;

            count=2;

        }

        if (count==1)

        {

            fscanf(fp, "%d,%d", &x1, &y1);

        }

        else

        {

            fscanf(fp, "%d,%d", &x2, &y2);

            printf("\n%d,%d", x2, y2);

            glBegin(GL_LINES);

                glVertex2i( x1, y1);

                glVertex2i( x2, y2);

            glEnd();

            storeEdgeInTable(x1, y1, x2, y2);// хранение ребер в таблице ребер.

              

              

            glFlush();

        }

    }

          

          
}

  

void drawDino(void)

{

    initEdgeTable();

    drawPolyDino();

    printf("\nTable");

    printTable();

      

    ScanlineFill();// фактический вызов заполнения строки

}

  

void main(int argc, char** argv)

{

    fp=fopen ("PolyDino.txt","r");

    if ( fp == NULL )

    {

        printf( "Could not open file" ) ;

        return;

    }

    glutInit(&argc, argv);

    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB); 

    glutInitWindowSize(maxHt,maxWd);

    glutInitWindowPosition(100, 150);

    glutCreateWindow("Scanline filled dinosaur");

    myInit();

    glutDisplayFunc(drawDino);

      

    glutMainLoop();

    fclose(fp);

}

Выход:
Заполненный динозавр:

Примечание: смотрите ваш вывод в окне opengl. Имейте в виду, что вам нужно установить перенасыщение. Вы можете увидеть это видео для просмотра выходных.
Эта статья предоставлена Suprotik Dey . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Scan-line полигональная заливка с использованием OPENGL в C

0.00 (0%) 0 votes