Calculating normals from vertices

[Davespice]

Hi folks, I am doing something a bit strange here. Read this carefully! Please bear with me while I explain. I know standard practise is to let the modelling software calculate the normals and then save them as part of your file format. You then load them into an array and use the normal pointer when you submit to ogl for drawing.



I am trying to recreate a retro look and feel for a game I am working on (see above). Specifically I want to have only coloured polygons making up the shape of a space ship but with GL_COLOR_MATERIAL turned on to that there can be some light and shading on the object.

If you're old enough you may recognise the image above to be from Novell Netwars (circa mid 90's). I'm actually using the original model file format from Advanced Netwars. The idea being that if anyone out there still has their custom model (the original game had an editor) they'll be able to immediately load it up in my rewrite and use it for maximum nostalgia.

I should mention that these models are not at all complex. You're allowed 64 vertices and up to 64 polys based on those. So the models look, as you would expect, very simplistic by today's standards. But it kind of makes you very careful about what you do and it gives the ships a kind of retro quality. You were allowed triangles, lines, quads and pentagons as poly types.

So to draw these in opengl es I wrote some code to convert everything down to triangles. Quads get divided into two triangles and pentagons into three. That is all fine and works well. The first snag I hit with this was finding a way to draw single colour polygons. Without using textures I decided to use a vertex colours array. However to actually get a single coloured poly all the vertices making up the corners need to be the same colour, otherwise ogl will give you a colour gradient between them like the image below.



So to avoid this I doubled up on vertices where necessary so that I could assign them separate colours and provide a poly with three vertices of the same colour. I know this wasteful but remember how simple the models are! So anyway this is all working fine and the models draw with the desired single poly colour effect with hard edges between polygons. However I now want to calculate normals so that I can have proper lighting!

The original model data that comes down from Advanced Netwars just has vertices, polys and poly colours; no normals since the original game had no concept of lighting. I consume all this in my conversion code to produce the single poly effect described above.

I am getting there, 100%, thanks if you have read this far! Because I have doubled up on some vertices, some polygons will never actually touch others. If you imagine a red triangle surrounded by grey ones for example. The vertices for the red triangle will not be shared by the grey polys since they need to have a different a vertex colour to make the triangle red. I do let two touching polys of the same colour share vertices in my conversion code though, so I have at least made some attempt at being efficient.

Now here is my question. Because I have done this cludge with the vertex colours have I broke my ability to automatically calculate the normals from the vertices? I am just trying to get the algorithm straight in my head before I attempt to program it. If you can give me any advice I would appreciate it.

I'm going to have to do something clever to work out which vertices are copies and then also work out which polys the copies are used in when averaging the surface normals for all the polys a vertex or vertex copy is used in... arrg my brain hurts.

I hope you get the drift! Anyway, all suggestions welcome. Shoot, go for it.

[AndrewS]

...and from what I remember of my 3D-maths, you need to watch out for the "winding order" of the triangles, because if you get it the wrong way round, your normals will be pointing inwards instead of outwards! (which would obviously make the lighting look wrong)

However as you're making loads of assumptions anyway, and your models are so simple, I guess you could calculate it both ways round, and simply create double-sided faces?

EDIT: And IIRC if you want to keep your "hard edges" you'll actually want to keep your "split vertices" because if you average the normals then I think (at least in lighting terms) OGL will give you rounded edges? So long since I did this kind of thing that I may be talking out of my bum...

[OtherCrashOverride]

http://en.wikipedia.org/wiki/David_Whee ... ientist%29

"All problems in computer science can be solved by another level of indirection."

Pseudo-code for the solution:

Code: Select all

Vector3 points[maxPoints];
Vector3 normals[maxPoints];	// points and normals use the same index
Vector3 colors[maxColors];

struct Vertex
{
	int PointIndex;
	int NormalIndex; // This will be the same as PointIndex and is only included for illustration purposes
	int ColorIndex;
}

Vertex vertices[maxVertexCount];

struct Triangle
{
	int VertexAIndex;
	int VertexBIndex;
	int VertexCIndex;
}

Triangle model[maxTriangles];


// Calculate "smooth" Normals
// Important: normals[] must be initialized to all zeros
foreach(triangle in model)
{
	int pointAIndex = vertex[triangle.VertexAIndex].PointIndex
	int pointBIndex = vertex[triangle.VertexBIndex].PointIndex
	int pointCIndex = vertex[triangle.VertexCIndex].PointIndex
  	
	Vector3 pointA = points[pointAIndex];
	Vector3 pointB = points[pointBIndex];
	Vector3 pointC = points[pointCIndex];

        // TODO: Adjust the normal calculation as needed for your winding order and coord 'handedness'
	Vector3 normal = Normalise(CrossProduct(pointB - pointA, pointC - pointA));
	
	normals[pointAIndex] += normal;
	normals[pointBIndex] += normal;
	normals[pointCIndex] += normal;
}

for (int i = 0; i < maxPoints; ++i)
{
	normals[i] = Normalize(normals[i]);
}

[Twinkletoes]

If you want hard edges then all your normals will be at right angles to the triangle faces, so IIRC that's a cross product of the two sides that meet at the corner. Normalise the length to 1 and you're away.

[OtherCrashOverride]

For hard normals, remove one of the levels of indirection:

Code: Select all

struct Vertex
{
   Vector3 Position
   Vector3 Normal; 
   RGBA Color;
}

Vertex vertices[maxVertexCount];

struct Triangle
{
   int VertexAIndex;
   int VertexBIndex;
   int VertexCIndex;
}

Triangle model[maxTriangles];


// Calculate "hard" Normals
// Important: all Vertex.Normal must be initialized to zeros
foreach(triangle in model)
{
   int vertexAIndex = triangle.VertexAIndex;
   int vertexBIndex = triangle.VertexBIndex;
   int vertexCIndex = triangle.VertexCIndex;
     
   Vector3 pointA = vertex[vertexAIndex];
   Vector3 pointB = vertex[vertexBIndex];
   Vector3 pointC = vertex[vertexCIndex];

        // TODO: Adjust the normal calculation as needed for your winding order and coord 'handedness'
   Vector3 normal = Normalise(CrossProduct(pointB - pointA, pointC - pointA));
   
   vertex[vertexAIndex].Normal += normal;
   vertex[vertexBIndex].Normal += normal;
   vertex[vertexCIndex].Normal += normal;
}

for (int i = 0; i < maxVertexCount; ++i)
{
   vertex[i].Normal = Normalize(vertex[i].Normal);
}