# Creating/Finding indexed vertices?

This topic is 3265 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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
{
...
{
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.

}
}

...
createMesh()
{
//create mesh from input array.
for each vertex V in input array
{
}
}

int main()
{
Mesh mesh = createMesh( someNonIndexedVertexList)

mesh.render() ;  //etc...
}



##### 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 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.//orif (fabs(A.x-B.x) < EPSILON && fabs(A.y-B.y) < EPSILPON && fabs(A.z-B.z) < EPSILON) do stuff.

##### 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 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 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.