2
$\begingroup$

I have a complicated equation that defines a shape in 3D, and I would like to generate a surface mesh. The shape is defined by an isosurface, i.e. the function is positive inside the shape and negative outside it.

The standard basic technique for this is the 'marching cubes' algorithm. However, it has a few disadvantages for me:

  • It generates meshes that are not particularly good, in ways that are well known.

  • At least with the most naïve implementation, I have to evaluate my function at every single point in a 3D grid, even though many of these are far away from the surface. I would rather have an algorithm that makes fewer evaluations of the function.

  • Marching cubes doesn't take advantage of any information about derivatives, which I can easily provide since I know the function.

Are there known, 'recommended' algorithms for this kind of case? There are many, many variations on marching cubes, but it's pretty hard to get an overview of their comparative advantages, and many of them seem only to address the first point above, not the second two.

This is for a little hobby project, so ideally I'm looking for something that's comparatively easy to implement.

Improve this question
$\endgroup$
6
  • $\begingroup$ Without any a-priori information, i suppose that you have to evaluate at every gridpoint. The meshing algorithm does not know whether there are "islands" somewhere, so the only rigorous way of testing is to test all points. If you have the information that there is only one volume/shape, then you might actually search inward-out and then stop or walk along the surface (continuation). $\endgroup$
    – MPIchael
    Jul 4, 2019 at 9:10
  • $\begingroup$ @MPIchael in the general case that's true of course, but in my case my surfaces should generally be pretty well-behaved - in most cases there should be only a single surface (no islands) and the boundary is mostly smooth with just the occasional sharp edge - the details are at a predictable scale. So the methods you suggest should work, or one could start with a coarse grid and refine it. The question is really in the details of how best to achieve these things. $\endgroup$
    – N. Virgo
    Jul 4, 2019 at 10:49
  • 1
    $\begingroup$ I suppose that numerical continuation could work in your case, but I can not make a statement whether or not that is overkill in terms of complexity. The idea would be to start from a point (x,y,z) where your function F(x,y,z)=0, with one spatial coordinate fixed, then walk along the border (numerical continuation) all the way around your volume. increase the fixed spatial coordinate and repeat. That way you would get a cloud of points on your surface which you might use for meshing. That -should- work in theory. (I am aware that this is vague, so no answer, just a comment) $\endgroup$
    – MPIchael
    Jul 4, 2019 at 11:17
  • $\begingroup$ That would also have some pitfalls, say your volume is a donut, then the above method would fail miserably. $\endgroup$
    – MPIchael
    Jul 4, 2019 at 11:20
  • $\begingroup$ @MPIchael it'll also fail if the shape has a hook-like protrusion. That might be fixable though, and I can think of various ways to iteratively improve the point cloud, so it could be a way to go. (Of course then I need a way to generate a good mesh from a point cloud, but that's a different question.) I've a feeling I might be re-inventing the wheel a bit though, if I come up with my own solution along those lines. $\endgroup$
    – N. Virgo
    Jul 4, 2019 at 13:02

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.