Calculating Vertex Normals for OGL. omg lots of calcs
Author
Hello all,
I have a great big scene imported from 3ds max using the .3ds file format. Unfortunately this file format (oddly) does not contain normal information so I have to calculate it myself.
I understand the basic algorithm is this:
for each vertex
set a temporary vector3f to (0, 0, 0)
for each polygon
if one of the polygon's vertices is equal to the current vertex,
add that polygon's normal to the temporary vector
next
normalize the temporary vector
(no need to divide by the total polygons)
this is now the vertex normal
next
However, this is a beast - its checking every vertex against every single other vertex. I work with about 4 million vertices and my scene will eventually be around 6-8 million. Thats a great, great, great deal of work to get my normals. Im not even sure I can pronounce the number of checks nessecery here. It will all be done as a preprocess and the info written to file, so once i've done it once (for each scene im currently working on) its all good, but isnt this madness?
Does anyone know how I could possibly make this faster, without having to dump the .3ds format altogether which I dont really want to do at this stage.
My only one thought is to use my BSP tree which holds the whole scene. I could work from the bottom of the tree and perhaps only check vertices in a node against one another if the nodes bounding spheres are overlapping, and if no other spheres overlap only check the contents of that node, or something like that.
Cheers
John
I'd say, write a stand alone translator that stores your in-game representation directly. when you export a 3DS model just run your tool which then calcs the normals once and stores it in your new file format. Doing this at runtime is a bad idea.
The better solution would be to write a maxscript exporter that gives you exactly what you want in the precise format that you want.
-me
The better solution would be to write a maxscript exporter that gives you exactly what you want in the precise format that you want.
-me
Author
Ah, for some reason it hadnt dawned on me to write my own exporter for max. Thats probably a good idea! although I dont really have any experience writing in maxscript what so ever.
Pending any further thoughts on the subject generally, anyone happen to know of such a bit of 3ds kit floating around already, or perhaps some good links to maxscript exporter writing stuff? :)
Pending any further thoughts on the subject generally, anyone happen to know of such a bit of 3ds kit floating around already, or perhaps some good links to maxscript exporter writing stuff? :)
How about going the other way:
1. Define array of normals, one for each vertex. Normal index equals vertex index.
2. Zero all normals.
3. For each face:
3.1. For each vertex of that face (I'm assuming you know which vertices make up the face), add the face normal to the corresponding vertex normal.
4. Normalize all normals.
1. Define array of normals, one for each vertex. Normal index equals vertex index.
2. Zero all normals.
3. For each face:
3.1. For each vertex of that face (I'm assuming you know which vertices make up the face), add the face normal to the corresponding vertex normal.
4. Normalize all normals.
Quote:Original post by jswill100
Ah, for some reason it hadnt dawned on me to write my own exporter for max. Thats probably a good idea! although I dont really have any experience writing in maxscript what so ever.
Pending any further thoughts on the subject generally, anyone happen to know of such a bit of 3ds kit floating around already, or perhaps some good links to maxscript exporter writing stuff? :)
I took this route many years ago, and while I had almost just started with programming at the time, I found writing a max script to export a scene easier than I thought. I suggest you to do this, because the 3ds format is very limited and writing a import library for some other format is a lot of work. Using a script you can easily add textures, uv coordinates, and so on.
Yeah getting normals from a 3DS is tricky. I am using 3DS format myself and my algo looks like this:
Calculate normal for each face. determine connectivity between faces and vertices: i.e. For each vertex have a list of all the polygons which contain it.
Then when you come to calculating the normal for a specific vertex on a specific polygon, sum the normals of all the faces connected to that vertex, which are also in the same smoothing group as the current polygon. This leaves hard edges correct.
Also when you are calculating the face normals, do not normalize them. Normalize only as the very end (after summing for all polygons on a vertex), as you then get polygon area weighted normals for free.
Calculate normal for each face. determine connectivity between faces and vertices: i.e. For each vertex have a list of all the polygons which contain it.
Then when you come to calculating the normal for a specific vertex on a specific polygon, sum the normals of all the faces connected to that vertex, which are also in the same smoothing group as the current polygon. This leaves hard edges correct.
Also when you are calculating the face normals, do not normalize them. Normalize only as the very end (after summing for all polygons on a vertex), as you then get polygon area weighted normals for free.
Author
Still kind of labouring on with this. Right now the problem is that while I know what verts make up a face, the way my verts are stored I dont know anything about shared verts.
So I end up having to go through and find all the shared verts so I can sum up all their faces normals. Which means ive got an O(n^2) still. Just worked out normals for a scene with I think 400k verts, saving them to file for use later. It probably took me an hour lol.
When I go up to 10 million verts+, this wont be possible (well, it kind of will, but ill have to give up my computer for like days lol. This might be ok on my final run when my scene will never change, but untill then its screwed).
Im struggling with a maxscript exporter, I cant seem to find alot of straight forward online tuts for someone whos never used it before. Would it be simple to write out a binary file .dat file from max holding vertex, UV, normal and texture info? its a fully static scene so I dont really need anything more.
So I end up having to go through and find all the shared verts so I can sum up all their faces normals. Which means ive got an O(n^2) still. Just worked out normals for a scene with I think 400k verts, saving them to file for use later. It probably took me an hour lol.
When I go up to 10 million verts+, this wont be possible (well, it kind of will, but ill have to give up my computer for like days lol. This might be ok on my final run when my scene will never change, but untill then its screwed).
Im struggling with a maxscript exporter, I cant seem to find alot of straight forward online tuts for someone whos never used it before. Would it be simple to write out a binary file .dat file from max holding vertex, UV, normal and texture info? its a fully static scene so I dont really need anything more.
To determine the connectivity is not O(n^2) its O(n) where n is the number of polygons:
If the vertices are unwelded then you will have to weld them. Use a hashset of vertices to determine duplicates then remap the indices in the polygons to the new set of vertices.
Any operation on a mesh with 10mil polys is going to be slow!
/edit
Also obviously you can combine the above loop over the polys with the calculation of the polygon normal, and kill two birds with one stone.
So your final psudocode for getting the smoothed normals from a 3ds looks like this:
There may be a problem with this, as in my models some of them seem to have seams along UV splits. I think this is because 3DS has precicely one UV per vertex, so anywhere where the same vertex has more than one UV, the vertex has to be split. This can be solved by first parsing into a more flexible storage for the mesh data (that can allow the same vertex to have more than one uv, i.e. specify uvs and vert indices sperately on polygons), and then welding the vertices that lie on top of each other, then applying the above normal calculation.
[Edited by - bluntman on July 17, 2007 2:22:06 PM]
(hash?)map<int, vector<int>> vertsToPolys;foreach(poly){ foreach(vert in poly) { vertsToPolys[vert].push_back(poly); }}If the vertices are unwelded then you will have to weld them. Use a hashset of vertices to determine duplicates then remap the indices in the polygons to the new set of vertices.
Any operation on a mesh with 10mil polys is going to be slow!
/edit
Also obviously you can combine the above loop over the polys with the calculation of the polygon normal, and kill two birds with one stone.
So your final psudocode for getting the smoothed normals from a 3ds looks like this:
map<int, vector<int>> vertsToPolys;vector<normal> faceNormals(polys.size());foreach(poly in polys){ foreach(vert in poly) { vertsToPolys[vert].push_back(poly); } // Assuming only triangles (thats what 3ds contains). // Note no normalization at this stage as we get polygon // area weighted normals for free faceNormals[poly] = crossProduct(verts[poly.vert[1]]-verts[poly.vert[0]], verts[poly.vert[2]]-verts[poly.vert[0]]);}foreach(poly in polys){ foreach(vert in poly) { normal = <0.0, 0.0, 0.0> foreach(connectedPoly in vertsToPolys[vert]) { if(smoothingGroup[connectedPoly] == smoothingGroup[poly]) { normal += faceNormals[connectedPoly]; } } normal.normalize(); // You now have your final smoothed normal // for this vertex on this polygon }}There may be a problem with this, as in my models some of them seem to have seams along UV splits. I think this is because 3DS has precicely one UV per vertex, so anywhere where the same vertex has more than one UV, the vertex has to be split. This can be solved by first parsing into a more flexible storage for the mesh data (that can allow the same vertex to have more than one uv, i.e. specify uvs and vert indices sperately on polygons), and then welding the vertices that lie on top of each other, then applying the above normal calculation.
[Edited by - bluntman on July 17, 2007 2:22:06 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
