• Create Account

## Adjacency Matrix from 3D Model?

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

6 replies to this topic

### #1DevLiquidKnight  Members

834
Like
0Likes
Like

Posted 08 February 2014 - 10:19 PM

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, 08 February 2014 - 10:48 PM.

### #2C0lumbo  Members

4071
Like
0Likes
Like

Posted 09 February 2014 - 12:04 AM

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.

### #3DevLiquidKnight  Members

834
Like
0Likes
Like

Posted 09 February 2014 - 12:09 AM

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, 09 February 2014 - 12:10 AM.

### #4Bacterius  Members

13100
Like
1Likes
Like

Posted 09 February 2014 - 01:05 AM

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)?

“If I understand the standard right it is legal and safe to do this but the resulting value could be anything.”

### #5DevLiquidKnight  Members

834
Like
0Likes
Like

Posted 09 February 2014 - 01:36 AM

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, 09 February 2014 - 01:39 AM.

### #6Bacterius  Members

13100
Like
1Likes
Like

Posted 09 February 2014 - 01:57 AM

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.

“If I understand the standard right it is legal and safe to do this but the resulting value could be anything.”

### #7plainoldcj  Members

1068
Like
0Likes
Like

Posted 09 February 2014 - 09:04 AM

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 half edge DS.

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

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.