find vertex groups in a mesh buffer for convex hulls

[bitplane]

here's a snippet for finding groups of joined vertices inside a mesh buffer, for convex hull creation. in case you've exported your meshes and they are all joined together into one buffer

Code: Select all

//! Finds groups of joined vertices
//! \param buffer: Mesh buffer to search
//! \param dp: accuracy in decimal places (for fast search)
//! \Return: Returns an array of pointers to arrays of 3d vectors
core::array< core::array<core::vector3df>* > findVertexGroups(scene::IMeshBuffer* buffer, s32 dp=1 )
{
	core::array< core::array<core::vector3df>* > ret;

	if (!buffer)
		return ret;

	core::array< core::array<u16>* > searchList;

	core::array< core::vector3di > vertexPositions;
	core::array< u16 > newIndices;

	u16 i=0;

	// add vertex positions as ints, for fast searching
	vertexPositions.set_used(buffer->getVertexCount());
	c8 *p = (c8*) buffer->getVertices();
	u16 stride = buffer->getVertexPitch();
	for (i=0; i < buffer->getVertexCount(); ++i)
	{
		video::S3DVertex *v = (video::S3DVertex*)p;
		core::vector3di roundedPos( (s32)round(v->Pos.X * (f32)((dp+1)*10)), 
									(s32)round(v->Pos.Y * (f32)((dp+1)*10)), 
									(s32)round(v->Pos.Z * (f32)((dp+1)*10)));
		vertexPositions[i] = roundedPos;
		p += stride;
	}

	// make unique index list
	u16 *ip = buffer->getIndices();
	for (i=0; i < buffer->getIndexCount(); ++i)
	{
		core::vector3di vpos = vertexPositions[ ip[i] ];
		s32 newIndex = vertexPositions.linear_reverse_search(vpos); 
		newIndices.push_back((u16)newIndex); 
	}

	// loop through each triangle
	for (i=0; i < buffer->getIndexCount(); i+=3)
	{
		s32 found = -1;

		// loop through all groups
		for (u16 j=0; j < searchList.size(); ++j)
		{
			if ( searchList[j]->linear_reverse_search(newIndices[i]  ) != -1 || 
				 searchList[j]->linear_reverse_search(newIndices[i+1]) != -1 || 
				 searchList[j]->linear_reverse_search(newIndices[i+2]) != -1 )
			{
				if (found == -1)
				{
					// add to this group
					searchList[j]->set_used(searchList[j]->size()+3);
					(*searchList[j])[ searchList[j]->size()-3 ] = newIndices[i];
					(*searchList[j])[ searchList[j]->size()-2 ] = newIndices[i+1];
					(*searchList[j])[ searchList[j]->size()-1 ] = newIndices[i+2];
					found = j;
				}
				else
				{
					// found in another group, merge groups
					u16 s = searchList[j]->size();
					searchList[j]->set_used(s + searchList[found]->size() + 3);
					memcpy(	(void*)(searchList[j]->pointer() + s), 
							(void*)(searchList[found]->pointer()), 
							(size_t)(sizeof(u16)*searchList[found]->size()));
					searchList[found]->set_used(0);
					(*searchList[j])[ searchList[j]->size()-3 ] = newIndices[i];
					(*searchList[j])[ searchList[j]->size()-2 ] = newIndices[i+1];
					(*searchList[j])[ searchList[j]->size()-1 ] = newIndices[i+2];
					found = j;
				}
			}
		}

		if (found==-1)
		{
			// start a new group
			u16 pos = searchList.size();
			searchList.push_back( new core::array<u16>() );
			searchList[pos]->set_used(buffer->getIndexCount()); // allocate them all for speed
			searchList[pos]->set_used(3);
			(*searchList[pos])[0] = newIndices[i  ];
			(*searchList[pos])[1] = newIndices[i+1];
			(*searchList[pos])[2] = newIndices[i+2];
		}

	}
	// build output position lists
	for (u16 k=0; k < searchList.size(); ++k)
	{
		if (searchList[k]->size())
		{
			u16 pos = ret.size();
			ret.push_back(new core::array<core::vector3df>);
			ret[pos]->set_used(searchList[k]->size());

			c8 *firstVertex = (c8*)buffer->getVertices();
			for (u16 l = 0; l < searchList[k]->size(); ++l)
			{
				s32 max = searchList[k]->size();
				u16 index = (*searchList[k])[l];
				core::vector3df vec = ((video::S3DVertex*)(firstVertex + stride*index ))->Pos;
				(*ret[pos])[l] = vec;
			}

		}

		delete searchList[k];
		searchList[k] = 0;
	}

	return ret;
}

and here's mr dwarf's mesh buffer, split in to several groups and sketched out with draw3dline.

Code: Select all

	IAnimatedMesh* mesh = smgr->getMesh("../../media/dwarf.x");
	core::array< core::array<core::vector3df>* > ret;
	ret = findVertexGroups(mesh->getMesh(0)->getMeshBuffer(1), 1);

...

	core::matrix4 m4;
	video::SMaterial mat;
	mat.Lighting = false;
	driver->setMaterial(mat);
	driver->setTransform(ETS_WORLD, m4);
	for (u32 m=0; m<ret.size(); ++m)
	{
		u32 c = (255/ret.size())*m;
		for (u32 n=0; n<ret[m]->size()-1; ++n)
		{
			driver->draw3DLine( (*ret[m])[n], (*ret[m])[n+1], video::SColor(c,c,c,c));
		}
	}

there's room for improvements, like the search lists would be better as an array of pointers, but i guess this should really be done as a pre-processing step anyway.

[BlindSide]

wow thats cool, so it splits them up according to which vertices are joined together? or is there some information stored in the mesh about groups like they are named in blender?

[fnf]

Sorry for replying this late. That code helped . I fixed a bug which leaves several groups (which should be cleared) hanging around. It can be seen with a simple 2-cubes scene graph. Here is my refined version in proper C++:

Code: Select all

    template <typename T> int linear_reverse_search (vector<T> const& vect, T const& elem)
    {
        return find (vect.rbegin (), vect.rend (), elem).base () - 1 - vect.begin ();
    }
    template <> int linear_reverse_search (vector<NxVec3> const& vect, NxVec3 const& elem)
    {
        // NOTE: We are reinventing find with the reverse_iterator here as I don't
        // want to create a class just to use find.

        int ret = -1;

        NxReal const EPSILON = 0.001;
        for (vector<NxVec3>::const_reverse_iterator iter = vect.rbegin (); iter != vect.rend (); ++iter)
            if (iter->equals (elem, EPSILON))
            {
                ret = iter.base () - 1 - vect.begin ();
                break;
            }

        return ret;
    }
    //! Finds groups of joined vertices
    //! Original thread: http://irrlicht.sourceforge.net/phpBB2/viewtopic.php?t=22578
    //! \param irr_vertices: A vector of vertices taken straight from the mesh buffer
    //! \param mesh_compound: A collection of convex meshes harvested from the original scene graph
    //! \Return: Nothing
    void PhysXConfigParser::findVertexGroups (vector<NxVec3> const& irr_vertices, vector<vector<NxVec3> >& mesh_compound)
    {
        // Makes unique index list
        vector<NxU32> indices;
        {
            // Irrlicht indices format: 0, 2, 1, 3, 5, 4, 6, 8, 7 ...
            vector<NxU32> irr_indices;
            for (vector<NxVec3>::size_type i = 0; i != irr_vertices.size (); i += 3)
            {
                irr_indices.push_back (i + 0);
                irr_indices.push_back (i + 2);
                irr_indices.push_back (i + 1);
            }

            // NOTE: newIndex can never be -1, should have some assertions here
            for (vector<NxU32>::const_iterator iter = irr_indices.begin (); iter != irr_indices.end (); ++iter)
                indices.push_back (linear_reverse_search (irr_vertices, irr_vertices[*iter]));
        }

        // Loops through each triangle
        vector<vector<NxU32> > searchList;
        for (vector<NxU32>::const_iterator iter = indices.begin (); iter != indices.end (); iter += 3)
        {
            vector<vector<NxU32> >::iterator found_group = searchList.end (); // searchList.end () indicates not found status

            // Loops through all groups
            for (vector<vector<NxU32> >::iterator iter1 = searchList.begin (); iter1 != searchList.end (); ++iter1)
                if ((linear_reverse_search (*iter1, *(iter + 0)) != -1) ||
                    (linear_reverse_search (*iter1, *(iter + 1)) != -1) ||
                    (linear_reverse_search (*iter1, *(iter + 2)) != -1))
                {
                    if (found_group == searchList.end ())
                    {
                        // Adds to this group
                        for (NxU32 i = 0; i != 3; ++i)
                            iter1->push_back (*(iter + i));
                    }
                    else
                    {
                        // Found in another group, merges groups by adding all elements of
                        // the old group (already included the triangle) to the new group
                        // and clearing the old group.
                        for (vector<NxU32>::const_iterator iter2 = found_group->begin (); iter2 != found_group->end (); ++iter2)
                            iter1->push_back (*iter2);
                        found_group->clear ();
                    }

                    found_group = iter1;
                }

            if (found_group == searchList.end ())
            {
                // Starts a new group
                searchList.push_back (vector<NxU32> ());
                vector<NxU32>& new_group = searchList.back ();
                for (NxU32 i = 0; i != 3; ++i)
                    new_group.push_back (*(iter + i));
            }
        }

        // Builds output position lists
        for (vector<vector<NxU32> >::const_iterator iter = searchList.begin (); iter != searchList.end (); ++iter)
            if (iter->size () != 0)
            {
                mesh_compound.push_back (vector<NxVec3> ());
                vector<NxVec3>& new_mesh = mesh_compound.back ();
                for (vector<NxU32>::const_iterator iter1 = iter->begin (); iter1 != iter->end (); ++iter1)
                    new_mesh.push_back (irr_vertices[*iter1]);
            }
    } 

Thanks.

[Edit]: Maybe I missed something, but doesn't creating vertexPositions actually affect performance?. What is the advantages of resizing/copying the array as opposed to just pushing back new elements?.

[bitplane]

yeah there were some dirty hacks in that code! I had pretty good reasons for each one, I should have explained it in the comments I guess-

I just went with memcpy because it was the innermost loop, copying arrays means constructing each element (function calls aren't much overhead, but hey, I was having fun!)

The reason I used linear_reverse_search was because linear_search (in 1.3.1, no longer in svn) uses the < operator which doesn't work for vectors..

and the reason for copying the vertex positions to int vectors, rather than using a proper epsilon value, was to go for fast integer comparisons rather than using floats (early optimization I guess, but I was enjoying the hacking). I figured the inner loops using int comparisons would more than make up for the allocation of the vectors in the long run (search gets called a lot)

doing a set_used with a large value then a small one makes sure that there's only one allocate done, push_back will cause reallocates (the size of the array doubles each time it runs out of space, so there's not many. allocating once is best though even if you never use all the memory)

I was hoping all those hacks would make it fast enough to do it at loading time, but it still took ages to split up a decent sized model

wow thats cool, so it splits them up according to which vertices are joined together? or is there some information stored in the mesh about groups like they are named in blender?

yeah it just finds similar vertex positions shared by triangles to find a group. when you UV map things it creates extra vertices that are in (roughly?) the same position, so triangle membership isn't enough to determine groups.. otherwise it would be lightening fast because we'd only need to check the index list

[omaremad]

i was thinking of making something similar for joining traingles with double vertices to make tri strip genration easier if you only have raw tris. Your search looks complex maybe hasing your tri postions and looping on a per triangle basis would be faster?

FNV hasing is fast

Code: Select all

u32 GenerateHash(char *str, Fnv32_t hval)
{
    unsigned char *s = (unsigned char *)str;	/* unsigned string */

    /*
     * FNV-1 hash each octet in the buffer
     */
    while (*s) {

	/* multiply by the 32 bit FNV magic prime mod 2^32 */

	hval += (hval<<1) + (hval<<4) + (hval<<7) + (hval<<8) + (hval<<24);

	/* xor the bottom with the current octet */
	hval ^= (u32)*s++;
    }

    /* return our new hash value */
    return hval;
}

so if you put your vertices in a gaint hash table then loop through traingles, multiple hits on the smae hash table entry will mean co joined tris.

[bitplane]

yes, good point. hashing the positions to a 32 bit int and then sticking them all in a core::map<hash, pointer> would probably much faster. wanna try it?

ps) when you get on irc, try to stick around for more than 30 secs