Mesh Vertex Neighbours

I'm trying to write a Shortest Path Algorithm for Meshes, and finding neighbouring vertices of any given Mesh vertex is something I am having a hard time with. Is there some method in the SDK that retrieves the neighbours of any vertex of the Mesh in an array/list format?

Not having this functionality is currently limiting me to only rectangular meshes (just as Nurbs), and a lot of cumbersome code for edges/corners/holes/etc. Which makes me think surely there is a more elegant way to go about this.

Suggestions?

Replies to This Discussion

Permalink Reply by Damien Alomar on October 2, 2009 at 10:51am

What are you considering a neighbor? Are you only interested in verts that make up an edge with a given vertex, or any vertex which is a part of a face that belongs to a given vertex, or perhaps something else? What you're probably going to have to do is rely on the list of face vertices to extract the information that you're looking for. That list will tell you which vertices are used by which faces, which you can then use to see which other faces use the vertex in question and therefore which vertices might possibly be connected to your vertex.

Permalink Reply by Suryansh Chandra on October 2, 2009 at 11:01am

Hmm..

The algorithm I'm trying to write is something like finding the shortest route from ptA to B on a city map, where streets are mesh edges, and destinations are mesh vertices. So neighbours to me are all those vertices that share an edge with the vertex in question.

I was scrolling through intellisense to see if there is a native method to do so, and nothing seemed to be too obvious. The SDK help as we all know is the most user-friendly document to come across on the planet, so I am still trying to decipher the various object types that spring from the OnMesh type.

I am already in the process of doing exactly what you mentioned up there with the mesh faces to find the neighbours.. but I am just about 25% through.

Permalink Reply by Damien Alomar on October 2, 2009 at 11:54am

Thanks for the better description on what you're trying to do...However, now I'm scratching my head as to what's the best way to actually approach this situation...I'll think about it a bit and get back to you if I come up with anything that seams promising.

Permalink Reply by Suryansh Chandra on October 2, 2009 at 12:49pm

Alright.. Got it going. Works perfectly, but the code is annoyingly long. And I am thinking for big meshes, this is going to really slow things down. I am sure there is a more elegant & faster way to do this.. David/Rajaa/Giulio.. any inputs on this?

This is to become a part of a much longer definition that finds shortest paths.. so I am getting concerned about the speed. Just re-reading my explanation about what I am doing, I made it sound like I am doing some geo-mapping and route finding code... that was just an example. I'll post some results to explain better when this is up and running.

Attachments: