# Given values on a mesh, what algorithm can I use to construct efficiently level set contours?

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?

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

• Why the downvote? – Graviton Feb 18 '12 at 4:18
• 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 Answer

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.

• 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