CODEWITHSUNDEEP
3dcomputer-sciencemeshscientific-computing
RNs_Ghost
RNs_Ghost

Reputation: 1777

How can I index an unstructured mesh?

I want to import unstructured 2d/3d meshes like this: 3d

or this

enter image description here

into my simulation.

I think unstructured meshes are described with a list of vertices and a list of edges (i.e. which vertices are joined to which other vertices). I don't know how I can get from that to being able to index the subvolumes in the mesh.

I then want to run a simulation on the mesh. In order to do this I need to be able to:

1) Index the mesh 2) Generate a neighbor list

How do I accomplish that?

Upvotes: 0

Views: 968

Answers (1)

wdb
wdb

Reputation: 343

With vertices and edges, you have an undirected graph. There are different data structures for representing graphs and different algorithms for traversing them. It's not really as simple as just traversing the graph, since you want volumes.

It would be nice if you had two lists:

  1. List of coordinates of vertices
  2. List of volumes which would each be described by a list of indices from the first list.

Something like:

LIST 1

0.4 0.7 0.8
0.4 0.8 0.9
0.6 0.8 0.9
0.7 0.7 0.8
....

LIST 2

1 2 3
4 2 3
....

(That assumes that the volumes are tetrahedra. If they are quadralaterals or prisms, you have to indicate which vertices are joined by edges.)

If that's the case, you just index down the second list.

If you just have vertices (coordinate vector) and edges (pairs of vertex indices), then you have to figure out how to convert edges into volumes.

Lists of coordinate vectors for the vertices and integer index pairs (to the first list) for the edges are probably the most efficient ways to store the vertices, but you probably need to use different data structures for efficiency, like a list of coordinate vectors for the vertices and an adjacency matrix stored as a sparse matrix for the edges. Each element in the matrix represents whether there is an edge for a pair of vertices (1 yes, 0 no). The row number is the index of one vertex and the column number is the index of the other vertex. (It is a symmetric matrix.)

You can form a tetrahedron starting at a vertex (0) by finding three vertices (1,2,3) that each share an edge with 0, and the other two, but you don't want to include tetrahedra that intersect, so you have to be careful. Then you can index your tetrahedra by the vertex indices in ascending (or descending) order, so that each tetrahedron has a unique index. For volumes with more vertices, you have to come up with a more complicated indexing scheme like indexing by edges in ascending (or descending) order. For example (42,54) would come before (67,89) in an ascending system. So a volume would consist of several of these ordered pairs, with the pairs listed in order, and vertex indices within a pair in order.

Upvotes: 1

Related Questions