Polygon Classes

This Article

If you have ever worked on a 3D app/game, you will know the importance of the 3D polygon structure. If you have never worked on a 3D app or game, then you might been having a few worries about how to organise such an important structure. This tutorial will describe how a polygon structure should work, what to do and not, and will provide a base for other more advanced tutorials.

Choices...

The structure of polygons in your application may vary; depending on whatever purpose you have in mind. If you want an application solely for viewing wireframes, you can have a structure different to one for viewing solid polygons. However, I am going to describe the most common method, and the one that I think is easiest to work with and most extensible.

Back To Basics

Firstly, imagine a 3D polygon in your head. What do you see? Just a collection of vertices, connected to each other?

With a confident gleam in your eye, you might start of like this:

class CPolygon
{
public:
	CPolygon() : m_pVertices(NULL), m_nVertexCount(0) {}
	~CPolygon() {delete [] m_pVertices;}

	VERTEX*	m_pVertices;
	int	m_nVertexCount;	
};

OK, most of you will have seen the problem by now. How do you draw a polygon like this? There is just an array of vertices; there are no actual faces. With a groan, you realize; this is going to be a little more complicated than you imagined

Faces, Edges, Vertices, Indices And Other Nightmares

A Polygon structure will need and array of vertices, certainly. However, it will need either:

An Array of Edges, each edge having a pair of Indices into the vertex array. With this layout you would dray a series of lines.
An Array of Faces, each one having a variable array of Indices into the vertex array. With this setup, you would iterate through the index array, drawing a polygon for each face.

The edge setup immediately looks more attractive, but there is a problem. Without some difficult coding, there is no way for one edge to know if it is next to another one, so you can only draw wireframes. If this is all you intend to do, then that is fine.

struct EDGE
{
int nStartIndex, nEndIndex;
};

class CPolygon
{
public:
	CPolygon() : m_pVertices(NULL), m_nVertexCount(0), m_pEdges(NULL, m_nEdgeCount(0){}
	~CPolygon() {delete [] m_pVertices, delete [] m_pEdges;}
	
	VERTEX*	m_pVertices;
	int	m_nVertexCount;
	EDGE*	m_pEdges;
	int 	m_nEdgeCount;	
};

However, you will come against problems if you ever want to draw solid bodies. The best thing to do if you dont want to deviate from this basic structure, is have another array, of faces, each with an array of indices into the edge array.

Whew!

Thats tough stuff, and I myself wouldnt recommend it. There are other problems too, if you are making a modeling app, how the heck do you triangulate a polygon, when all you have is its edges?

The way to go is almost certainly the face array. When you think about it, it is much better. Look at the code below.

struct VERTEX {
	float x,y,z;
};

struct INDEX {
	int nVertex;
};

struct FACE {
	INDEX* pIndices;
	int nCount;
};

class CPolygon
{
public:
	CPolygon() : m_pVertices(NULL), m_pFaces(NULL), m_nFaces(0), m_nVertices(0) {}
	~CPolygon() {delete [] m_pVertices, delete m_pFaces;}

	virtual void Draw();

	//	Member Data
	VERTEX* m_pVertices;
	int	m_nVertices;
	FACE*	m_pFaces;
	int	m_nFaces;
};

It looks very similar to the previous class. Do not underestimate the importance of the INDEX structure; you will later update it to index into an UV array as well. It is also a good place to put vertex colour values if you want them.

void CPolygon::Draw()
{
	for(int n=0; n<m_nVertices; n++)
	{
		FACE& face = m_pFaces[n];

		glBegin(GL_POLYGON);
		for(int f=0; f<face.nCount; f++)
			glVertex3fv(& m_pVertices[ face.nIndices[f].nVertex ] );
		glEnd();
	}
}

At the end of the article I have included a faster drawing function, this one is really to show what is happening.

Other Notes

This is not a complete polygon class, but it is a good base. It wont take much work to add persistence (saving and loading) and drawing the polygons is a breeze.

Here are a few dos and donts.

Do Not

Put vertices into something like a vector or linked list. These containers are fast, but they are not fast enough. Iterators are fast, but they wont go fast enough when you are drawing 14,000 polys, 20 times a second!

Make faces that instead of having a variable number of indices, have a variable number of vertices. If you do this, each face will take up a lot more space, and you wont be able to do some of the cooler modeling functions like smoothing, and triangulating. Do

Extend this class! This is a base for you to work from, and is fast. Apart from the OpenGL draw routine I showed you, it needs nothing to work with. You can make a fast powerful CPolygon class without one include file in the header.

Use C++. Im sorry, but with C++ and especially polymorphism, you can create extraordinarily extensible applications, plugins and render engines can be added easily, and the code looks much better than C code. I started out on C, and I used to think it wasnt much different, but it is, C++ is the most powerful language Ive ever used, and it is fast. The Faster Drawing Routine

void CPolygon::Draw()
{
FACE* ptrFace = m_pFaces[0];
	INDEX* ptrIndex = NULL;
	int nFaceCount = m_nFaces, nIndexCount = 0;
	
while(nFaceCount--)
{
	ptrIndex = ptrFace++->pIndices;
	nIndexCount = ptrFace->nCount;
	glBegin(GL_POLYGON);
	while(nIndexCount--)
		glVertex3fv(&m_pVertices[ptrIndex++->nVertex]);
	glEnd();
}
}

This may not look faster, but the while(x--) loops are a bit faster than for loops. Also, incrementing pointers (ptrFace++->) is faster than accessing the array each time. This isnt much faster, but you will notice the difference when you are drawing a lot in your scene.

In the Future

I will be writing more, advanced articles soon. It would be a pain to describe the polygon structure before each one, so it the basic structure outlined above that will be used. If you start off with this structure, you will be able to extend it with each new article.

Notes On Raytracing And Raycasting

Raytracing is a magic word amongst those new to 3D, but I designed this class with Raytracing in mind. When you raytrace, you (basically) cast a ray from youre eye through every pixel on the screen, and see what it hits. The Polygon class can easily support ray-tracing, so look out for more later on.

Check out my website, http://www.focus.esmartweb.com.

E-mail me: Dave Kerr


HOME TWITTER FACEBOOK RSS ATOM FORUM
Polygon Classes This Article If you have ever worked on a 3D app/game, you will know the importance of the 3D polygon structure. If you have never worked on a 3D app or game, then you might been having a few worries about how to organise such an important structure. This tutorial will describe how a polygon structure should work, what to do and not, and will provide a base for other more advanced tutorials. Choices... The structure of polygons in your application may vary; depending on whatever purpose you have in mind. If you want an application solely for viewing wireframes, you can have a structure different to one for viewing solid polygons. However, I am going to describe the most common method, and the one that I think is easiest to work with and most extensible. Back To Basics Firstly, imagine a 3D polygon in your head. What do you see? Just a collection of vertices, connected to each other? With a confident gleam in your eye, you might start of like this: class CPolygon { public: CPolygon() : m_pVertices(NULL), m_nVertexCount(0) {} ~CPolygon() {delete [] m_pVertices;} VERTEX* m_pVertices; int m_nVertexCount; }; OK, most of you will have seen the problem by now. How do you draw a polygon like this? There is just an array of vertices; there are no actual faces. With a groan, you realize; this is going to be a little more complicated than you imagined Faces, Edges, Vertices, Indices And Other Nightmares A Polygon structure will need and array of vertices, certainly. However, it will need either: An Array of Edges, each edge having a pair of Indices into the vertex array. With this layout you would dray a series of lines. An Array of Faces, each one having a variable array of Indices into the vertex array. With this setup, you would iterate through the index array, drawing a polygon for each face. The edge setup immediately looks more attractive, but there is a problem. Without some difficult coding, there is no way for one edge to know if it is next to another one, so you can only draw wireframes. If this is all you intend to do, then that is fine. struct EDGE { int nStartIndex, nEndIndex; }; class CPolygon { public: CPolygon() : m_pVertices(NULL), m_nVertexCount(0), m_pEdges(NULL, m_nEdgeCount(0){} ~CPolygon() {delete [] m_pVertices, delete [] m_pEdges;} VERTEX* m_pVertices; int m_nVertexCount; EDGE* m_pEdges; int m_nEdgeCount; }; However, you will come against problems if you ever want to draw solid bodies. The best thing to do if you dont want to deviate from this basic structure, is have another array, of faces, each with an array of indices into the edge array. Whew! Thats tough stuff, and I myself wouldnt recommend it. There are other problems too, if you are making a modeling app, how the heck do you triangulate a polygon, when all you have is its edges? The way to go is almost certainly the face array. When you think about it, it is much better. Look at the code below. struct VERTEX { float x,y,z; }; struct INDEX { int nVertex; }; struct FACE { INDEX* pIndices; int nCount; }; class CPolygon { public: CPolygon() : m_pVertices(NULL), m_pFaces(NULL), m_nFaces(0), m_nVertices(0) {} ~CPolygon() {delete [] m_pVertices, delete m_pFaces;} virtual void Draw(); // Member Data VERTEX* m_pVertices; int m_nVertices; FACE* m_pFaces; int m_nFaces; }; It looks very similar to the previous class. Do not underestimate the importance of the INDEX structure; you will later update it to index into an UV array as well. It is also a good place to put vertex colour values if you want them. void CPolygon::Draw() { for(int n=0; n<m_nVertices; n++) { FACE& face = m_pFaces[n]; glBegin(GL_POLYGON); for(int f=0; f<face.nCount; f++) glVertex3fv(& m_pVertices[ face.nIndices[f].nVertex ] ); glEnd(); } } At the end of the article I have included a faster drawing function, this one is really to show what is happening. Other Notes This is not a complete polygon class, but it is a good base. It wont take much work to add persistence (saving and loading) and drawing the polygons is a breeze. Here are a few dos and donts. *Do Not* Put vertices into something like a vector or linked list. These containers are fast, but they are not fast enough. Iterators are fast, but they wont go fast enough when you are drawing 14,000 polys, 20 times a second! Make faces that instead of having a variable number of indices, have a variable number of vertices. If you do this, each face will take up a lot more space, and you wont be able to do some of the cooler modeling functions like smoothing, and triangulating. Do Extend this class! This is a base for you to work from, and is fast. Apart from the OpenGL draw routine I showed you, it needs nothing to work with. You can make a fast powerful CPolygon class without one include file in the header. Use C++. Im sorry, but with C++ and especially polymorphism, you can create extraordinarily extensible applications, plugins and render engines can be added easily, and the code looks much better than C code. I started out on C, and I used to think it wasnt much different, but it is, C++ is the most powerful language Ive ever used, and it is fast. The Faster Drawing Routine void CPolygon::Draw() { FACE* ptrFace = m_pFaces[0]; INDEX* ptrIndex = NULL; int nFaceCount = m_nFaces, nIndexCount = 0; while(nFaceCount--) { ptrIndex = ptrFace++->pIndices; nIndexCount = ptrFace->nCount; glBegin(GL_POLYGON); while(nIndexCount--) glVertex3fv(&m_pVertices[ptrIndex++->nVertex]); glEnd(); } } This may not look faster, but the while(x--) loops are a bit faster than for loops. Also, incrementing pointers (ptrFace++->) is faster than accessing the array each time. This isnt much faster, but you will notice the difference when you are drawing a lot in your scene. In the Future I will be writing more, advanced articles soon. It would be a pain to describe the polygon structure before each one, so it the basic structure outlined above that will be used. If you start off with this structure, you will be able to extend it with each new article. Notes On Raytracing And Raycasting Raytracing is a magic word amongst those new to 3D, but I designed this class with Raytracing in mind. When you raytrace, you (basically) cast a ray from youre eye through every pixel on the screen, and see what it hits. The Polygon class can easily support ray-tracing, so look out for more later on. Check out my website, http://www.focus.esmartweb.com. E-mail me: Dave Kerr