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.

  • 1
    $\begingroup$ Why the downvote? $\endgroup$ – Graviton Feb 18 '12 at 4:18
  • 1
    $\begingroup$ 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? $\endgroup$ – Aron Ahmadia Feb 18 '12 at 13:15

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.

  • $\begingroup$ 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? $\endgroup$ – Graviton Feb 19 '12 at 14:43
  • $\begingroup$ @Graviton: I doen't think you can expect to be much better than linear scaling with problem size... $\endgroup$ – Allan P. Engsig-Karup Feb 19 '12 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.