Sign in to follow this  
Rasmadrak

Creating/Finding indexed vertices?

Recommended Posts

Hi, I'm trying to create a smart method of creating indexed meshes, but I believe my current implementation takes too much time to process... Is there a better way of doing this other than my method below? I would also like to know if there's a nice way of calculating neighbours to each vertex? I'm currently thinking of passing the current vertex's neighbours and add these as neighbours if they don't already exits. P.s sorry about the nasty formatting/coding/etc... And please note this is not actual code, just pseudo...

//Pseudo

Vertex
{
...
   void addToList(meshList, indicesList)
   {
        search meshList for a match (currently checking if vertex A and B are less than a certain threshold apart.
              if found, add to indices and return.

       //not found
       add to meshList and indices.
   }
}


...  
createMesh()
{
//create mesh from input array.
  for each vertex V in input array
  {
      V.addToList(finalmesh, indices);
  }
}

int main()
{
    Mesh mesh = createMesh( someNonIndexedVertexList)
    
   mesh.render() ;  //etc...
}


Share this post


Link to post
Share on other sites
I think that's the only way you're going to be able to generate the index list.

As for finding neighbouring vertices, I don't think you can 'calculate' them other than infering the neighbours from the vertex list.

Share this post


Link to post
Share on other sites
Hi!

Thanks for your reply, it makes sense now. No reason to "auto-magically" find neighbours since you already know which vertices are connected and can get the neighbours from them. :) After all, this wasn't intended for a vertex-soup but a triangle soup.

Another question - what would be faster?


if (A.squaredDistanceTo(B) < EPSILON) do stuff.

//or

if (fabs(A.x-B.x) < EPSILON && fabs(A.y-B.y) < EPSILPON && fabs(A.z-B.z) < EPSILON) do stuff.



Share this post


Link to post
Share on other sites
You could optimize the "search meshList for a match". I assume you currently use a linear search over all vertices already in the meshlist, wich is O(n) per vertex. For huge models, you could add the vertices to some spatial structure, such as an kd-tree, which when done correct would give on average O( log n ) per vertex. Also a tricky method I used once was with a hash map, mapping each vertex to a single bucket and when matching a vertex look up the 2,4 or 8 nearest buckets. This could be really fast near to O(1), but gives some trouble with the mapping and floating point precision.

Which method works best depends on your application and the size of you models. For small models, linear search is probably still the fastest.

Dietger

Share this post


Link to post
Share on other sites
Hi,

Spot on with the linear search (still developing the function, thou. :) )
The current usage is for procedurally generated meshes, which could contain potentially millions of vertices.
I'll check out hash-tables and/or faster search implementations once I've laid down the basic framework for the indicer.

Thanks again!

Share this post


Link to post
Share on other sites
You can also trade off size for speed - only do your linear search over the last 32 or so vertices that were added. The hardware vertex cache is fairly small anyway so you shouldn't lose much if anything in rendering speed.

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