## Making a nice long triangle strip

### Making a nice long triangle strip

Ok, I have a 3d object and I want to turn it into a nice long triangle
strip. Can any 3d object be represented by a single strip? I've got a hunch
that nearly all of them can be, but my maths isn't good enough to convince
me. Also, is there an amazingly good algorithm for producing the strip? I
was just going look for common edges and do some kind of triplely linked
list, then attempt to generate the strip from that.

Hope you can help!

Peter

### Making a nice long triangle strip

>Ok, I have a 3d object and I want to turn it into a nice long triangle
>strip. Can any 3d object be represented by a single strip? I've got a hunch
>that nearly all of them can be, but my maths isn't good enough to convince
>me. Also, is there an amazingly good algorithm for producing the strip? I
>was just going look for common edges and do some kind of triplely linked
>list, then attempt to generate the strip from that.

Oh yeah, by 3d object I mean a group of triangles; each vertex is the vertex
of at least two triangles in total. Obviously there are thousands of
examples
of shapes not following these rules having to be split into several strips.

Any help on the *best* (ie fastest producing smallest number of strips)
algorithm for splitting such an object into triangle strips would be
greatly appreciated.

Peter

### Making a nice long triangle strip

>> Ok, I have a 3d object and I want to turn it into a nice long triangle
>> strip. Can any 3d object be represented by a single strip? I've got a
hunch
>> that nearly all of them can be, but my maths isn't good enough to
convince
>> me. Also, is there an amazingly good algorithm for producing the strip? I
>> was just going look for common edges and do some kind of triplely linked
>> list, then attempt to generate the strip from that.

>> Hope you can help!

>> Peter

>Oh wow! You have no idea! Ok, the branch of math you're dealing with now
>is known by most as Deformations (I believe). Now, Lots of shapes can be
>reduced to a flat triangle mesh, however, many can't. To find out more,
>you need to find a weekend with a few hours to kill, a good book on
>deforming, and some strong coffee (or jolt cola).

>+-----------------------------+
>| Mark Haase                 /

>+----------------------------+

I have the time at the moment (exam leave followed by long summer holiday).
Any particular titles/web pages which anyone can recommend?

Peter

### Making a nice long triangle strip

> > Ok, I have a 3d object and I want to turn it into a nice long triangle
> > strip. Can any 3d object be represented by a single strip? I've got a hunch
> > that nearly all of them can be, but my maths isn't good enough to convince
> > me. Also, is there an amazingly good algorithm for producing the strip? I
> > was just going look for common edges and do some kind of triplely linked
> > list, then attempt to generate the strip from that.

> Oh wow! You have no idea! Ok, the branch of math you're dealing with now
> is known by most as Deformations (I believe). Now, Lots of shapes can be
> reduced to a flat triangle mesh, however, many can't. To find out more,
> you need to find a weekend with a few hours to kill, a good book on
> deforming, and some strong coffee (or jolt cola).

Er, I don't think that's quite the right pointer.

I believe that stripping meshes is an NP-complete; thus, coming up with a
single long strip (if such a thing even exists for a given model) is likely
to be... time consuming.  Some folks at SUNY Stonybrook have done some work
in this area (and made the NP-completeness finding, I think) and have
written some nice papers; for code and papers, see:
<URL:http://www.cs.sunysb.edu/~stripe/>

Also, I believe that the Visualization Toolkit has an implementation of a
stripping algorithm (I don't know if it's the same as the SUNY SB one or
not): <URL:http://www.kitware.com/vtk>.

-matt
--

<URL:http://graphics.stanford.edu/~mmp>

### Making a nice long triangle strip

>> > Ok, I have a 3d object and I want to turn it into a nice long triangle
>> > strip. Can any 3d object be represented by a single strip? I've got a
hunch
>> > that nearly all of them can be, but my maths isn't good enough to
convince
>> > me. Also, is there an amazingly good algorithm for producing the strip?
I
>> > was just going look for common edges and do some kind of triplely
>> > list, then attempt to generate the strip from that.

>> <snip info on deforms>

>Er, I don't think that's quite the right pointer.

Phew.

Quote:>I believe that stripping meshes is an NP-complete; thus, coming up with a
>single long strip (if such a thing even exists for a given model) is likely
>to be... time consuming.

Mmmm... Thankfully I'm only going to be dealing with relatively low poly
count models. I was afraid of that though. Still, it is possible to do all
of
this before the object is loaded up by my program and it only needs to
be done once for every object.

Quote:>Some folks at SUNY Stonybrook have done some work
>in this area (and made the NP-completeness finding, I think) and have
>written some nice papers; for code and papers, see:
><URL:http://www.cs.sunysb.edu/~stripe/>

>Also, I believe that the Visualization Toolkit has an implementation of a
>stripping algorithm (I don't know if it's the same as the SUNY SB one or
>not): <URL:http://www.kitware.com/vtk>.

Thanks! I'll check out those URLs as soon as possible.

Peter

Hey Guys

I have a paper and demo on a new alternative to ROAM and other CLOD
algorithms for terrain LOD. I call it T-Strip LOD and it basicly subdivides
complete lines instead of triangles, esentially giving you the same
structure of a quad tree, except that blocks form a contigious line across
one axis which give you the contigious trinagle strip. It's relativly simple
and takes advantage of the high processing power of todays hardware
graphics, but with less CPU usage than conventional LOD algorithms. Perhaps
not as effective as VIPM, it may still prove to be relavent in certain
environments where there is deforming terrain, extensive terrain collision,
and mapping objects to the visble terrain mesh is required. It's more of a
cross between brute force triangle strip rendering  and CLOD.

Anyhow, the paper and demo are up at
http://chat.carleton.ca/~eszoka/tstriplod/tstrip.htm, note the demo takes 30
seconds or so to generate the terrain texture, read the readme.txt for the
keys to operate the various features and controls.

Any thoughs or comments would be appreciated.

Ernest Szoka
http://chat.carleton.ca/~eszoka/