PDA

View Full Version : GL_SMOOTH_SHADING and normal vectors



BigRed
08-02-2004, 10:48 PM
Hello! :)

Ive written a program which reads STL-Data to show it with OpenGL on the screen.
An STL-File consists of many triangles WITHOUT ANY ORDER! Each of this triangles has one normal vector and three vertices.

The program shows the object correctly now, but...

My problem is: I want to make a Smooth-Shading. This means that I need to know the normal vector of EVERY vertex. But I have only one per Facet.
I tried it with the medium of all vectors of the neigbours of each facet. But in this case the progam needs many time to order the facets.

My cuestion is:
1.) Is there any solucion for Flat-Shading without using normal vectors for every Vertex??
2.) Is there any data structure which is recomended for OpenGL?? (Im using a list of the facets... very simple)... or much better: Is there any data structure PROVIDED BY OpenGL??



Thanks for helping me...

Greetings from Germany

BigRed

BigRed
08-02-2004, 10:53 PM
Sorry, I made a mistake:

The first question is:

1.)Is there any solucion for SMOOTH-Shading without using normal vectors for every Vertex??

BigRed

satan
08-03-2004, 04:30 AM
Hi,

smooth-shading just interpolates the lighting values across the primitive. With only one normal vector per face there is not much to interpolate so I think the answer to 1) is no.
Your solution to average each per vertex normal vector with its neighbours is the RightThing(tm) to do to get smooth shading. Perhaps there is a faster way to order your triangles and average the normals (prepocessing of the files?).
Or the more advanced people on this forum can give any tips.

hih

Eric
08-03-2004, 05:08 AM
In order to calculate normals properly at each vertex, you'll first need to know the connectivity between your triangles which cannot be done directly with STL files.

In my STL parser, I maintain a list of unique vertices as well as a list of triangles that use indices to the vertex list.The steps I follow are as follows:

1) Read one facet: this is actually 3 vertices (X,Y,Z).
2) For each vertex in the facet, look if it is already present in the list. If yes, use the index found. if not, add the vertex to the list and use this new index.
3) Add the triangle (which now consists of 3 indices to the vertec list) to the triangles list. You should keep the triangle normal in your structure too. You can use the one found in the STL file if you want but it can also be re-calculated easily (cross-product with vectors built from the 3 vertices)

When you've done those 3 steps, you have your list of vertices (X,Y,Z) and your list of triangles (V1,V2,V3) where Vi is an integer (index to the vertices list).

Now you can calculate your vertex normals and there are many ways to do this. Here are two method:

1) Brutal / Not-so-good method: create an array of vectors to keep each vertex normal. Scan through the triangles list. For each vertex of a triangle, add the triangle normal to the vertex normal. You can weigh the normal with the triangle area (or invert of the area, depends on people...). When all triangles are processed, normalize the vertex normals. One drawback is that one vertex only has one normal which means even sharp edges on your model will look smooth. This can be avoided with the second method.

2) Instead of having one big array for the vertex normals, each triangle will now hold one normal per vertex i.e.:

struct sTriangle
{

int m_iV[3]; // indices in vertex list //
C_Vector3Df m_vN[3]; // normal for each vertex //

};

The C_Vector3Df class is one of my own but I suppose you'll figure out what is in there ;) .

Now you need to "double-scan" the triangles list. For each triangle, look for shared vertices. When a shared vertex is found, look at whether the triangle normals are below a certain angle. If they are, add the normals (again, you can weigh them).

This "double-scan" can be avoided if you build a "vertex usage" list when you read the STL file: keeping track of which triangle uses which vertex will speed up the process greatly.

Now, as you may have noticed, I haven't talked about OpenGL yet as your question really isn't related to the API but is more a Maths question.

When you have all your vertices and all your normals you can render the model using immediate mode or indexed Vertex&Normal arrays (if you do this you'll need to "rebuild" your vertex array as the OpenGL mechanism only allows one normal per vertex; you'll have to duplicate vertices that have more than one normal).

Hope this will help.

Regards,

Eric

BigRed
08-04-2004, 04:11 AM
Hello!

Wow, Im very surprised that I find so helpful people here. Thank you very much! :)

I made it nearly like you, but I have a little problem with your second step:


For each vertex in the facet, look if it is already present in the list. ... means to me, that I have to go through all the Vertices that I have in my list (I also have a vertex list and a triangle list now).

My program is ready to use like this... but only with small objects. The problem is, that I also have objects with more than 80 MB. So I need much time to go through all the vertices... and this every time when y read a new facet.
This means:
New Facet -> new
New Facet -> go through 1 Vertice
New Facet -> go through 2 Vertices
New Facet -> go through 3 Vertices

...and so on.

I dont know if there is a barrier in my head. May be...... ;)

I keep thinking in your solucion. Thanks!

Greetings from Germany

BigRed

Relic
08-04-2004, 04:27 AM
Get yourself a good computer algorithm book and look up "hashing".

BigRed
08-04-2004, 04:55 AM
I looked in the Internet.

Thats what Im searching for.... thanks!!!

Eric
08-04-2004, 06:07 AM
Well, I meant to mention this in my original post but I forgot about it by the time I reached the end!

So what I usually do in such case is to sort my vertex list on X, then Y, then Z.

So if I get points like:

1,5,6
3,8,9
3,1,2
3,3,10
1,2,3
2,1,4

I would end up with:

1,2,3
1,5,6
2,1,4
3,1,2
3,3,10
3,8,9

When I get a new vertex, I'll first have a look only at the X coordinate using a dichotomy algorithm. If I don't find a matching X, I insert my new vertex in the list. If I do find a matching X, I proceed onto Y (you first find the first and last vertex using the X of your new vertex!)

There may be even more efficient algorithms though.

BigRed
08-05-2004, 02:05 AM
Yes, there is. Im still trying, but I think that works.

My Englisch isnt very well, so I show it like this first:

I make a Hash-Table:

Point = 23.545454 (I mean the point of a float-Value ;-)

-------------------------------------
first digit after point = 0 |List 1 |
-------------------------------------
fist digit after point = 1 |List 2 |
-------------------------------------
... and so on

So my KEY is the first digit after the Point. If I read a new Facet-Point, I have to look at the first digit and then search in the list (that is very, very, very smaller and because of this very faster)

My structure:

struct POINT {
Vertex v;
Vertex normal;
struct POINT * next;
struct POINT * prev;
} Point;

POINT hash[10][10][10]; //x, y and z (first digit after point of float-value)

Sorry, but with my English its very dificult to explain.

Greetings from Germany

BigRed