Need help to understand this STL code.

This is a discussion on Need help to understand this STL code. within the C++ Programming forums, part of the General Programming Boards category; First of all, I must say I'm just starting to use STL, in fact I started a day ago to ...

  1. #1
    Registered User
    Join Date
    Oct 2003
    Posts
    97

    Need help to understand this STL code.

    First of all, I must say I'm just starting to use STL, in fact I started a day ago to get into it. Now, I'm having some problems to understand some STL code someone wrote. Here is the header code:
    Code:
    class varrays_normalizer
    {
    public:
    	varrays_normalizer(gl_mesh & Mesh);
    
    	size_t Normalize();
    
    private:
    	typedef unsigned int index;
    	typedef std::vector<index> indices;
    	typedef std::vector<float> varray;
    
    	class cmp_lt_vertex
    	{
    	public:
    		cmp_lt_vertex(const varray & Vertex, const varray & Normal, const varray & TexCoord);
    		bool operator () (const index & a, const index & b) const;
    
    	private:
    		const varray & m_Vertex;
    		const varray & m_Normal;
    		const varray & m_TexCoord;
    	};
    
    	gl_mesh & m_Mesh;
    };
    
    inline varrays_normalizer::varrays_normalizer(gl_mesh & Mesh) : m_Mesh(Mesh) { }
    
    
    inline varrays_normalizer::cmp_lt_vertex::cmp_lt_vertex(const varray & Vertex, const varray & Normal, const varray & TexCoord)
    	: m_Vertex(Vertex), m_Normal(Normal), m_TexCoord(TexCoord) { }
    And the CPP code is here:
    Code:
    size_t varrays_normalizer::Normalize()
    {
    	typedef std::vector<index *> indices_pointers;
    	typedef std::map<index, indices_pointers, cmp_lt_vertex> vertex_map;
    	typedef vertex_map::const_iterator vertex_map_const_iterator;
    
    	if (m_Mesh.m_VArrays[gl_mesh::vertex].empty() || m_Mesh.m_VArrays[gl_mesh::normal].empty() || m_Mesh.m_VArrays[gl_mesh::texture_coord0].empty())
    		throw ("Normalizer: one of the vertex arrays is empty (need vertex/normal/texcoord0)");
    
    
    	cmp_lt_vertex CmpFct(
    		m_Mesh.m_VArrays[gl_mesh::vertex],
    		m_Mesh.m_VArrays[gl_mesh::normal],
    		m_Mesh.m_VArrays[gl_mesh::texture_coord0]
    	);
    
    	vertex_map VertexMap(CmpFct);
    
    
    	for (size_t i = 0; i < m_Mesh.m_SubMeshes.size(); ++i) {
    
    		const indices & Indices = m_Mesh.m_SubMeshes[i].Indices();
    
    		for (size_t j = 0; j < Indices.size(); ++j)
    			VertexMap[Indices[j]].push_back((index *) &(Indices[j]));
    	}
    
    	size_t NewVASize = VertexMap.size();
    
    	varray Vertex;		Vertex.reserve(NewVASize);
    	varray Normal;		Normal.reserve(NewVASize);
    	varray TexCoord;	TexCoord.reserve(NewVASize);
    
    	varray & OldVertex = m_Mesh.m_VArrays[gl_mesh::vertex];
    	varray & OldNormal = m_Mesh.m_VArrays[gl_mesh::normal];
    	varray & OldTexCoord = m_Mesh.m_VArrays[gl_mesh::texture_coord0];
    
    	for (vertex_map_const_iterator It = VertexMap.begin(); It != VertexMap.end(); ++It) {
    
    		const index VAPos = (* It).first;
    		const indices_pointers & IndicesPtr = (* It).second;
    		const index NewIndex = index(Vertex.size() / 3);
    
    		Vertex.push_back(OldVertex[VAPos * 3 + 0]);
    		Vertex.push_back(OldVertex[VAPos * 3 + 1]);
    		Vertex.push_back(OldVertex[VAPos * 3 + 2]);
    
    		Normal.push_back(OldNormal[VAPos * 3 + 0]);
    		Normal.push_back(OldNormal[VAPos * 3 + 1]);
    		Normal.push_back(OldNormal[VAPos * 3 + 2]);
    
    		TexCoord.push_back(OldTexCoord[VAPos * 2 + 0]);
    		TexCoord.push_back(OldTexCoord[VAPos * 2 + 1]);
    
    		for (indices_pointers::const_iterator IndIt = IndicesPtr.begin(); IndIt != IndicesPtr.end(); ++IndIt)
    			** IndIt = NewIndex;
    	}
    
    
    	// Replace the old arrays with the new ones
    	std::swap(Vertex, OldVertex);
    	std::swap(Normal, OldNormal);
    	std::swap(TexCoord, OldTexCoord);
    
    	return NewVASize;
    }
    
    bool varrays_normalizer::cmp_lt_vertex::operator () (const index & a, const index & b) const {
    	// Compare the vertex coords
    	if (m_Vertex[a * 3 + 0] < m_Vertex[b * 3 + 0])
    		return true;
    	else if (m_Vertex[a * 3 + 0] > m_Vertex[b * 3 + 0])
    		return false;
    
    	else if (m_Vertex[a * 3 + 1] < m_Vertex[b * 3 + 1])
    		return true;
    	else if (m_Vertex[a * 3 + 1] > m_Vertex[b * 3 + 1])
    		return false;
    
    	else if (m_Vertex[a * 3 + 2] < m_Vertex[b * 3 + 2])
    		return true;
    	else if (m_Vertex[a * 3 + 2] > m_Vertex[b * 3 + 2])
    		return false;
    
    	// Compare the normal vector coords
    	if (m_Normal[a * 3 + 0] < m_Normal[b * 3 + 0])
    		return true;
    	else if (m_Normal[a * 3 + 0] > m_Normal[b * 3 + 0])
    		return false;
    
    	else if (m_Normal[a * 3 + 1] < m_Normal[b * 3 + 1])
    		return true;
    	else if (m_Normal[a * 3 + 1] > m_Normal[b * 3 + 1])
    		return false;
    
    	else if (m_Normal[a * 3 + 2] < m_Normal[b * 3 + 2])
    		return true;
    	else if (m_Normal[a * 3 + 2] > m_Normal[b * 3 + 2])
    		return false;
    
    	// Compare the texture coords
    	if (m_TexCoord[a * 2 + 0] < m_TexCoord[b * 2 + 0])
    		return true;
    	else if (m_TexCoord[a * 2 + 0] > m_TexCoord[b * 2 + 0])
    		return false;
    
    	else if (m_TexCoord[a * 2 + 1] < m_TexCoord[b * 2 + 1])
    		return true;
    	else if (m_TexCoord[a * 2 + 1] > m_TexCoord[b * 2 + 1])
    		return false;
    
    	return false;
    }
    First of all, I need to explain what's the idea of this code. The idea is to normalize a list of vertices, that means that every single vertex has unique information, if two vertices have the same information, then one is removed. Now with that list of vertex you make triangles, so you have ints which point to what vertices in the list make up that face (or triangle) in the model. This means that for example, if a face is made up by the indices [1 2 3] and another face is made up with the indices [4 5 6], then if 2 and 6 have the same information (vertex position, texture coordinate and normal) then the second face should be [4 5 2]. To normalize the list of vertices also means that all those vertices that don't belong to any face are removed. I hope that helps.
    Now, the only thing I understand is that this code is trying to use one of the properties of the STL maps and its the fact that two keys can't be equal. What I don't understand is how is the structure set up, what is the key and the value in the map, what is the purpose of the compare value (I know it gets called three times when the push_back is done). Can anyone help me with this problem?

    Thanks in advance.

  2. #2
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    typedef std::map<index, indices_pointers, cmp_lt_vertex> vertex_map;

    The type vertex_map uses the type index as the key and the type indices_pointers as the data. Each element of the map map is actually a pair where the the first value of the pair is the key and the second is the data. Each element of the map is stored in the map in sorted order according to the cmp_lt_vertex function.

    INMO, using this example to learn STL maps, or other aspects of STL, is like using Hoefstaders "Goedel, Escher, and Bach" to learn English---it can be done, but only with extreme measures.
    You're only born perfect.

  3. #3
    Registered User
    Join Date
    Oct 2003
    Posts
    97
    Quote Originally Posted by elad
    typedef std::map<index, indices_pointers, cmp_lt_vertex> vertex_map;

    The type vertex_map uses the type index as the key and the type indices_pointers as the data. Each element of the map map is actually a pair where the the first value of the pair is the key and the second is the data.
    Yeah, I realized that, what I don't understand is for example, is the following line:
    Code:
    VertexMap[Indices[j]].push_back((index *) &(Indices[j]));
    I haven't seen any stl map example that uses the push_back function. I suppose that this line stores Indices[j] as the key, and (index *) &(Indices[j]) as the value, is that right?

    Quote Originally Posted by elad
    Each element of the map is stored in the map in sorted order according to the cmp_lt_vertex function.
    I don't understand this one either. How does the compare function works? I know that it has to return a bool, what does it mean if it returns true and what does it mean when it returns false?

    Quote Originally Posted by elad
    INMO, using this example to learn STL maps, or other aspects of STL, is like using Hoefstaders "Goedel, Escher, and Bach" to learn English---it can be done, but only with extreme measures.
    Yeah, too bad I had to bump into this code to realize I had to learn STL. Anyway I got myself a book(STL Tutorial and Reference Guide: C++ Programming with the Standard Template Library (2nd Edition)) that's helping me a bit, but its not enough.

    Thanks a lot for the help.

  4. #4
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Quote Originally Posted by Hulag
    Yeah, I realized that, what I don't understand is for example, is the following line:
    Code:
    VertexMap[Indices[j]].push_back((index *) &(Indices[j]));
    I haven't seen any stl map example that uses the push_back function. I suppose that this line stores Indices[j] as the key, and (index *) &(Indices[j]) as the value, is that right?
    Wrong. VertexMap[Indices[j]] looks up the element of the map with the key Indices[j]. This element is of the type indices_pointers, which is a typedef for vector<index *>. push_back is then called on this vector.

    I don't understand this one either. How does the compare function works? I know that it has to return a bool, what does it mean if it returns true and what does it mean when it returns false?
    Depends on the function. This particular functor has "lt" in the name, which I guess means "less than". Thus, if the function returns true then the first argument is "less than" the second, whatever that means.
    It's not important what exactly it means, what's important is that it creates a strict weak ordering for the keys.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Proposal: Code colouring
    By Perspective in forum A Brief History of Cprogramming.com
    Replies: 28
    Last Post: 05-14-2007, 08:23 AM
  2. Values changing without reason?
    By subtled in forum C Programming
    Replies: 2
    Last Post: 04-19-2007, 11:20 AM
  3. Array of Vectors amd other STL questions
    By kolistivra in forum C++ Programming
    Replies: 16
    Last Post: 04-12-2007, 10:11 AM
  4. Updated sound engine code
    By VirtualAce in forum Game Programming
    Replies: 8
    Last Post: 11-18-2004, 12:38 PM
  5. Replies: 4
    Last Post: 01-16-2002, 12:04 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21