计算机图形学3——Boundary-Fill Algorithm

图形学实验：边界填充多边形算法

算法原理如下：
种子像素入栈，当栈非空时重复执行如下三步操作：

（1）栈顶像素出栈
（2）将出栈像素置成要填充色
（3）按左、上、右、下顺序检查与栈像素相邻的四个像素，若其中某个像素不在边界且未置成填充色，则把该像素入栈

核心代码如下：

void Boundaryfill (int seedx,int seedy)
{
	CMyStack stk1;
    long color=RGB(255,0,0); //填充颜色 red
	long boundary_color=RGB(255,255,255); //边界颜色 white
	unsigned char params[4]; //保存读取的一个像素点的颜色值
	dcpt p1;
    p1.x=seedx;
	p1.y=seedy;

	stk1.push(p1);
	while(!stk1.isEmpty())
    {
        int next[4][2]={{0,-1},{1,0},{0,1},{-1,0}};
        p1=stk1.gettop();
        stk1.pop();

        glColor3f(1,0,0);
        glBegin(GL_POINTS);
            glVertex2i(p1.x,p1.y);
        glEnd();

        for(int i=0;i<4;i++)
        {
            int tx=p1.x+next[i][0];
            int ty=p1.y+next[i][1];
            glReadPixels(tx,ty,1,1,GL_RGBA,GL_UNSIGNED_BYTE,params);
            long c1=RGB(params[0],params[1],params[2]);
            if(c1==color||c1==boundary_color)
                continue;
            dcpt p2;
            p2.x=tx;
            p2.y=ty;
            stk1.push(p2);
        }
    }
}

MyStack.h（类声明文件）如下：

// MyStack.h: interface for the MyStack class.
#if !defined(AFX_MySTACK_H__3657DC2D_E518_4E5E_9A32_023B2A260ED7__INCLUDED_)
#define AFX_MySTACK_H__3657DC2D_E518_4E5E_9A32_023B2A260ED7__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include <windows.h>
#include <GL/glut.h>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>

struct dcpt
{
	int x;
	int y;
};

struct pointStruct
{
	dcpt point;
	pointStruct * pNext;
};

class CMyStack
{
public:
    CMyStack();
    virtual ~CMyStack();
    BOOL pop();
    void push(dcpt pt);
    void empty();
    dcpt gettop();
    BOOL isEmpty();
private:
    pointStruct *pHead;
    pointStruct *p1;
    pointStruct *pTop;

};
#endif // !defined(AFX_MySTACK_H__3657DC2D_E518_4E5E_9A32_023B2A260ED7__INCLUDED_)

MyStack.cpp(类实现文件）如下：

// MyStack.cpp: implementation of the MyStack class.
#include "MyStack.h"
CMyStack::CMyStack()
{

    pHead=new pointStruct;
    p1=pTop=pHead;
    pHead->pNext=NULL;
}
CMyStack::~CMyStack()
{
    while(pTop!=NULL)
    {
        p1=pTop;
        pTop=pTop->pNext;
        delete p1;
    }
}

BOOL CMyStack::pop()
{
    if(pTop==pHead)
        return 0;
    p1=pTop;
    pTop=pTop->pNext;
    delete p1;
    return 1;
}

void CMyStack::push(dcpt pt)
{
    p1=new pointStruct;
    p1->point=pt;
    p1->pNext=pTop;
    pTop=p1;
}

void CMyStack::empty()
{
    while(pTop!=NULL)
    {
        p1=pTop;
        pTop=pTop->pNext;
        delete p1;
    }

}

dcpt CMyStack::gettop()
{
    return pTop->point;
}

BOOL CMyStack::isEmpty()
{

    if(pTop==pHead)
        return 1;
    return 0;
}

main.cpp(类使用)如下：

// ====== Computer Graphics Experiment #3 ======
// |          Boundary-Fill Algorithm          |
// =============================================
//
// Requirement:
//	Implement Boundary-Fill algorithm to fill polygon.


#include "MyStack.h"
#define WINDOW_HEIGHT 400

void Boundaryfill (int seedx,int seedy)
{
	CMyStack stk1;
    long color=RGB(255,0,0); //填充颜色 red
	long boundary_color=RGB(255,255,255); //边界颜色 white
	unsigned char params[4]; //保存读取的一个像素点的颜色值
	dcpt p1;
    p1.x=seedx;
	p1.y=seedy;

	stk1.push(p1);
	while(!stk1.isEmpty())
    {
        int next[4][2]={{0,-1},{1,0},{0,1},{-1,0}};
        p1=stk1.gettop();
        stk1.pop();

        glColor3f(1,0,0);
        glBegin(GL_POINTS);
            glVertex2i(p1.x,p1.y);
        glEnd();

        for(int i=0;i<4;i++)
        {
            int tx=p1.x+next[i][0];
            int ty=p1.y+next[i][1];
            glReadPixels(tx,ty,1,1,GL_RGBA,GL_UNSIGNED_BYTE,params);
            long c1=RGB(params[0],params[1],params[2]);
            if(c1==color||c1==boundary_color)
                continue;
            dcpt p2;
            p2.x=tx;
            p2.y=ty;
            stk1.push(p2);
        }
    }
}

void MyPolygonFill(int n, dcpt *vertices)
// n --- Number of vertices
// vertices --- vertex coordinates
{
	int max=vertices[0].x;
	int mix=vertices[0].x;
	int may=vertices[0].y;
	int miy=vertices[0].y;
	glColor3f(1.0, 1.0, 1.0);
	glBegin (GL_LINE_LOOP);
	for (int i=0;i<n;i++)
	{
		glVertex2i(vertices[i].x,vertices[i].y);
		if (vertices[i].x>max)
			max=vertices[i].x;
		if (vertices[i].x<mix)
			mix=vertices[i].x;
		if (vertices[i].y>may)
			may=vertices[i].y;
		if (vertices[i].y<miy)
			miy=vertices[i].y;
	}
    glEnd();
    int sx=(max+mix)/2;
	int sy=(may+miy)/2;
	Boundaryfill(sx,sy);

}

// Initialization function
void init(void)
{
	glClearColor (0.0, 0.0, 0.0, 0.0);
    glPixelStorei(GL_PACK_ALIGNMENT, 1);
}

// Display callback function
void display(void)
{
	static dcpt v[4];
	v[0].x = 260, v[0].y = 150;
	v[1].x = 281, v[1].y = 200;
	v[2].x = 340, v[2].y = 230;
	v[3].x = 370, v[3].y = 150;

	glClear(GL_COLOR_BUFFER_BIT);

	MyPolygonFill(4, v);

	glFlush();
}

// Reshape callback function
void reshape(int w, int h)
{
	glViewport (0, 0, w, h);
	glMatrixMode(GL_PROJECTION);
	glLoadIdentity();
	gluOrtho2D(0, w, 0, h);
}

// Keyboard callback function
void keyboard(unsigned char key, int x, int y)
{
	switch (key) {
		case 27: exit(0);
	}
}

// Main program entrance
int main(int argc, char* argv[])
{
	glutInit(&argc, argv);
	glutInitDisplayMode (GLUT_RGB);
	glutInitWindowSize (650, 400);
	glutInitWindowPosition (50, 100);
	glutCreateWindow ("Polygon Fill");
	init ();
	glutDisplayFunc(display);
	glutReshapeFunc(reshape);
	glutKeyboardFunc(keyboard);
	glutMainLoop();
	return 0;
}