9

I have a mesh, faces $F$, edges $E$, and vertices $V$, and I have a list of predefined level set contours.

What algorithm can I use to construct contours in the most efficient manner?

enter image description here

A plot of the contour is shown above. Lines with the same color have the same $z$ value.

Geoff Oxberry
  • 30,394
  • 9
  • 64
  • 127
Graviton
  • 488
  • 5
  • 16
  • 1
    Why the downvote? – Graviton Feb 18 '12 at 04:18
  • 1
    not sure, it seems like a relevant question to me. Downvoter? One issue is that isolines don't seem particularly well-defined for mesh data. Could you perhaps give a graphical example of the problem you are trying to solve? – Aron Ahmadia Feb 18 '12 at 13:15

1 Answers1

4

It can be done by a loop over each element and then for each element a loop over the edges. Then for each edge determine the coordinate for a given contour if it cross the edge, i.e. check if the contour takes a value in the interval spanned by the vertices values. If the contour crosses two edges, then draw the a line between the coordinates between detected crossing points at the edges.

Doing this for all elements will create the contours. It is also an option to refine to a finer mesh via interpolation on each triangle and then use a delaunay triangulations of the refined mesh and then apply the routine as described above for achieving a sufficiently fine resolution.

Allan P. Engsig-Karup
  • 3,226
  • 19
  • 31
  • The runtime for this is $O(F*n)$, where $F$ is the face number and $n$ is the number of contour, is there anyway to improve on this algorithm's runtime? – Graviton Feb 19 '12 at 14:43
  • @Graviton: I doen't think you can expect to be much better than linear scaling with problem size... – Allan P. Engsig-Karup Feb 19 '12 at 15:18