Sign in to follow this  
jswill100

C++ STL Map for vertex normals. SOLVED

Recommended Posts

Hello all, Am having a small problem - right now I am exporting a large scene from 3ds into opengl using the .3ds format - and this does not contain any vertex normal information so i need to calculate it myself. Before you see some code you should know my vertices (and vert normals) are organised into vector<Vector3f> where Vector3f is my own structure for a vertex. The verts are organised so that there are repeated vertex, i.e. verts 1,2,3 are for the first triangle, and 3,4,5 are for the second, but none, 1 or 2 of these vertices may in reality be the same as 1,2 or 3. I started out using an extremely extremely time consuming method as below
void calculateSharedVerts(vector<Vector3f>& verts, vector<Vector3f>& vertNormals)
{
Vector3f temp;


        //here I set the intial vertex normals to that of the face normal for the face they belong to. 
	for(int i=0; i< verts.size(); i+=3)
	{
		temp.calculateNormal_2(verts[i], verts[i+1], verts[i+2]);

		vertNormals.push_back(temp);
		vertNormals.push_back(temp);
		vertNormals.push_back(temp);
	}


        //Now I loop through and whenever we find a shared vertex, we add the face normals from both
	for(int i=0; i< verts.size(); i++)
	{

		for(int j=0; j< verts.size(); j++)
		{
			if(i!=j)
			{
				if(verts[i]==verts[j])
				{
					vertNormals[i]+= vertNormals[j];
				}
			}
			
		}
	}

        //normalise the results
	for(int i=0; i< vertNormals.size(); i++)
	{
		vertNormals[i].normalise();
	}
}



The above worked entirely correctly, but because of the size of my scene, even just computing these normals once and writing to a file to be read later takes hours on end and so I searched for a better way of doing it. I realised I could use the stl Map so that whenever I was addressing a shared vertex, I only needed to use that one value so no looping to find shared verts is required. Because the other definition I use for Vector3f "less than" does not meet the requirements of "strict weak ordering" I define a new comparison function vect3fCompare to use. Basically the normals are coming out far from correct and was hoping someone might be able to give me some insight into what I might be doing wrong here.
	bool vect3fCompare(Vector3f p1, Vector3f p2) {

	Vector3f zero(0,0,0);

	//the below SHOULD satisfy strict weak ordering, which I read was is nessecery for this to work, defined by
		//1) a<a is false 
		//2) equality given by (!(a<b) && !(b<a)) - i.e. less than can be used to determine equality
		//3) If a<b and b<c, then a<c must be true.
	if(p1.distance(zero) < p2.distance(zero))
		return true;



	return false;
 }	

void addNormals(vector<Vector3f>& verts, vector<Vector3f>& vertNormals) {
	
		map<Vector3f, Vector3f, bool(*)(Vector3f, Vector3f)> myMap(vect3fCompare);

		Vector3f temp;

		//calculate the face normal, and set each vert to that face normal.
		for(int i=0; i< verts.size(); i+=3)
		{
			temp.calculateNormal_2(verts[i], verts[i+1], verts[i+2]);

			vertNormals.push_back(temp);
			vertNormals.push_back(temp);
			vertNormals.push_back(temp);
		}

		Vector3f zero(0,0,0);

                //fill it up with 0s.
		for(int i=0; i< verts.size(); i++)
			myMap[verts[i]] = zero;


		//for every shared vertex, myMap will now collect all the proper face normals together to make individual vert normals.
		for(int i=0; i< verts.size(); i++)
		{
			myMap[verts[i]] += vertNormals[i];
		}

                //now we loop back through, setting each vertNormal to the value calculated in the map.
		for(int i=0; i< verts.size(); i++)
			vertNormals[i] = myMap[verts[i]]; //addition of all verts same as verts[i]
			
                //and finally normalise
		for(int i=0; i< vertNormals.size(); i++)
		{
			vertNormals[i].normalise();
		}
}





[Edited by - jswill100 on August 13, 2007 6:11:24 AM]

Share this post


Link to post
Share on other sites
Quote:
//2) equality given by (!(a<b) && !(b<a)) - i.e. less than can be used to determine equality


Not quite. You're confusing equality and equivalence.

(1, 0, 0) is equivalent to (0, 0, 1) under your predicate.

This is the cause of your problem:

// you have this (which i assume is not what you want)
&some_map[Vector3f(0, 0, 1)] == &some_map[Vector3f(1, 0, 0)]


Edd

Share this post


Link to post
Share on other sites
Thanks for your reply!

Hm yes I see what you mean. I could see that the problem probably stemmed from my comparison function as opposed to something else, but I have tried quite a range of things and am not totally sure what I should be using to meet the requirements for strict weak ordering with a Vector3f (float x,y,z).

I'm sure this is simple i will have a closer look at it later, but any further input is appreciated.

John

Share this post


Link to post
Share on other sites
Just to address the question of a map-friendly comparator for geometric vectors, it's probably lexicographical comparison that you're looking for (the easiest way to implement this for your vector class is probably just to just wrap std::lexicographical_compare()).

[Edit: If your vector is in 'float x, y, z' form, you can probably get away with e.g. '&x, &x + 3' for the call to std::lexicographical_compare(). Strictly speaking though, this isn't portable (at least not AFAIK), so it might be best to copy the vector data to an array, or to just write your own comparison function. (On a side note, storing your vector data in array form from the get-go nicely bypasses this and other similar issues.)]

Share this post


Link to post
Share on other sites
Quote:
Original post by jswill100
Thanks for your reply!

Hm yes I see what you mean. I could see that the problem probably stemmed from my comparison function as opposed to something else, but I have tried quite a range of things and am not totally sure what I should be using to meet the requirements for strict weak ordering with a Vector3f (float x,y,z).


Well your predicate does indeed define a strict weak ordering. Everything you're doing is well defined in terms of the language. It's just that the program isn't behaving as you'd like it to :) You need a predicate where the implied equivalence is transitive. EDIT: You need a predicate where the implied equivalence relation is actually equality.

So you'll need to either change your predicate or do something else entirely. jyk's suggestion of a lexicographical comparison sounds sensible, given your situation.

However, if you wanted to treat very-closely-positioned vectors as equal, you'd need something more robust. Something like a bounding volume hierarchy, perhaps.

Edd

[Edited by - the_edd on August 11, 2007 8:19:48 PM]

Share this post


Link to post
Share on other sites
Some general suggestions:

1) Add a default constructor for Vector3f which sets each member to zero. (Actually, you must already have some kind of default constructor if you're storing these things in standard library containers :) ) Then you can rely on...

2) std::map::operator[] automatically adds not-found entries, associating a default-constructed value with the key. This means you don't need to go through and initialize things first.

3) 'calculateNormal_2' is a somewhat strange-looking function.
a) It seems to be used to initialize a Vector3f; why not return one instead, and make it a static member of the class (factory pattern)? (Making it a constructor would be a little strange too :) )
b) Why '_2'? And for that matter, it's a little strange to have words like 'calculate' in the names of functions that return a value (see (a) again) - of course they are performing a calculation :)

4) Instead of accumulating the corresponding "initial" normals and then inserting them into the map, it makes sense to just insert (add) them directly on the first pass. Similarly, we can normalise the results in the same breath that we collect them.

5) There's an (IMHO :) ) slightly neater way to do the initial iteration.

6) You seem to be relying on the output vertNormals to be empty to start out with. It's cleaner (possibly slower, but modern compilers should be able to do the necessary NRVO work here) to just return your return values.

7) Const correctness :)


typedef vector<Vector3f> vertContainer;

vertContainer addNormals(const vertContainer& verts) {
map<Vector3f, Vector3f, bool(*)(Vector3f, Vector3f)> myMap(vect3fCompare);

typedef vertContainer::const_iterator iterator;
iterator v1 = verts.begin();
iterator v2 = v1 + 1;
iterator v3 = v1 + 2;
for (; v1 != verts.end(); v1 += 3, v2 += 3, v3 += 3) {
Vector3f temp = Vector3f::faceNormal(*v1, *v2, *v3);

myMap[*v1] += temp;
myMap[*v2] += temp;
myMap[*v3] += temp;
}

vertContainer result(verts.size());

for (v1 = verts.begin(); v1 != verts.end(); ++v1) {
result.push_back(myMap[*v1].normalise());
}

return result;
}



(EDIT: typedefs added to show some of the benefit of using iterators. Also, *proper* const-correctness, assuming I'm thinking straight.)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this