Re: Multiple material marching cubes (M3C) algorithm - triangulating closed polylines

On Jul 19, 8:31 pm, Stuart Golodetz
<sgolod...@xxxxxxxxxxxxxxxxxxxxxxxxxx> wrote:
Hi guys,

Hope this is the right place to ask this. I'm getting myself a bit
confused trying to figure out how to triangulate non-planar closed
polylines and wondered if anyone could point me in the right direction
please?

The reason I want to do this is that I'm writing an implementation of
the "Multiple material marching cubes algorithm" (Wu and Sullivan) in
order to visualize segmented medical imaging data, and it produces
closed loops which need triangulating.

It says that "A simple divide-and-conquer triangulation works fine", but
I was having a look around the net and found a post by Dave Eberly in
which he gave an example which made it seem as if the general case was
ambiguous? Namely: "Consider the closed polyline with ordered vertices
(0,0,0), (1,0,0), (1,0,1), (0,0,1), (0,1,1), (1,1,1), (1,1,0), (0,1,0),
(0,0,0). One interpretation leads to a triangulation that produces three
faces of a cube. Another interpreations leads to a triangulation that
produces three different faces of a cube."

Is anyone familiar with the algorithm at all by any chance? I noticed
that the standard marching cubes algorithm was mentioned in the FAQ, so
I thought someone might well have come across the multiple material
version too. My gut feeling is that the polylines to be triangulated
here might be a restricted subset which are tractable - does anyone know
whether that's the case please?

Incidentally, I did find one algorithm to do something like this in a
paper called "Decimation of Triangle Meshes", but it wasn't guaranteed
to work in all cases. (That's fine for their algorithm, where the
triangulation didn't absolutely need to happen, but it's not enough for
what I need unfortunately.)

Confused! :-s

Thanks in advance for any insight :-)
Stu

Hi,

we did some work in this area some years ago. Perhaps this reading
(http://pc2.iam.fmph.uniba.sk/amuc/_contributed/algo2005/varnuska-
parus-kolingerova.pdf , Section 3.2) might help you a little.
Unfortunately, I'm afraid it will not work in all cases.

Regards,

Jindra
.

Relevant Pages

  • Multiple material marching cubes (M3C) algorithm - triangulating closed polylines
    ... I'm getting myself a bit confused trying to figure out how to triangulate non-planar closed polylines and wondered if anyone could point me in the right direction please? ... The reason I want to do this is that I'm writing an implementation of the "Multiple material marching cubes algorithm" in order to visualize segmented medical imaging data, and it produces closed loops which need triangulating. ... It says that "A simple divide-and-conquer triangulation works fine", but I was having a look around the net and found a post by Dave Eberly in which he gave an example which made it seem as if the general case was ambiguous? ... One interpretation leads to a triangulation that produces three faces of a cube. ...
    (comp.graphics.algorithms)
  • Re: Multiple material marching cubes (M3C) algorithm - triangulating closed polylines
    ... One interpretation leads to a triangulation that produces three ... that the standard marching cubes algorithm was mentioned in the FAQ, ... My gut feeling is that the polylines to be triangulated ...
    (comp.graphics.algorithms)