• Advertisement
Sign in to follow this  

Adjacency Matrix from 3D Model?

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Is there any file format or way to export the adjacency matrix describing the connectivity of vertices? Or is there any way I can do this easily?

Edited by DevLiquidKnight

Share this post


Link to post
Share on other sites
Advertisement

Do you mean a list of adjacent triangle edges? I've never seen a model format include that, you'd typically build it up yourself by examining the triangle list and searching for any triangles that share 2 vertices.

Share this post


Link to post
Share on other sites

Basically if two vertices share the same edge the matrix entry would contain a 1 otherwise it would contain 0. Not much different then that used for a graph algorithm. I realize this isn't very common request I just wondered if anyone has any idea how I could go about doing this.

Edited by DevLiquidKnight

Share this post


Link to post
Share on other sites

It's not usually stored since it takes a lot of space (in O(n^2) of the number of vertices) and is fairly cheap to recreate on demand. To create the matrix just create a square nxn matrix, and run through each entry (x, y), setting it to 1 if there exists an edge between the two vertices x and y. The "is there an edge" question may be hard to answer depending on your data format, so what format are your models in? What does your adjacency information look like in raw form (not matrix form)?

Share this post


Link to post
Share on other sites

I could put them in any format something like blender supports? I was hoping to just use obj file format if possible. And you are right its a very large matrix hence why I would like to automate this process. I can see how to iterate through the matrix but the "is there a edge" question seems hardest to me.

Edited by DevLiquidKnight

Share this post


Link to post
Share on other sites

I could put them in any format something like blender supports? I was hoping to just use obj file format if possible. And you are right its a very large matrix hence why I would like to automate this process. I can see how to iterate through the matrix but the "is there a edge" question seems hardest to me.

 

If you're using obj format then it's pretty much already done for you. The faces section of the file defines the list of triangles, read that in then for each vertex initialize a list which is then populated with every other vertex that shares a triangle with that vertex (by iterating over triangles). If that is so then the two are obviously adjacent. Once you're done, it's just a matter of interpreting the list of vertices to create the matrix, since the answer "is there an edge from u to v" then becomes "does list[u] contain v", or "does list[v] contain u" (if your edges are undirected).

 

Triangles aren't the only faces supported by the format, for arbitrary polygons you would triangulate it and proceed as usual. Though in practice I have yet to come across an obj file that used anything more complex than quads (four vertices per face) instead of NURBS or similar.

Share this post


Link to post
Share on other sites

What are you trying to do?

 

Considering the (common?) case of a 2-manifold mesh the number of edges is actually O(number of vertices). So storing the adj. matrix seems like a waste of space. Consider adj. lists instead.

 

If you are interested in the connectivity of your mesh (eg. what are the adj. faces of this edge, loop through all edges of a face...) there

are more suitable data structures like the [url=http://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtml]half edge DS[/url].

 

If you really need the adj. matrix, ignore this post.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement