How to Generate Tri-Strips from an Arbitrary Polygon

TheNut 179 Mar 18, 2007 at 16:25

After getting all excited over Vector Graphics in 3D, I decided to one-up my engine. So far so good, but dealing with complex shapes hasn’t been as smooth.

The way I handle this problem is I first create a set of points outlining the Bezier path (ie: resolution). From these points, I generate tri-strips by using a “railroad track” algorithm (ie: jump from one side to the other). This unfortunately does not work well for polygons that swirl back in on themselves. You will notice this at the bottom of the mane in the screenshot where there’s a triangle cutting right across the bottom. I can see why he’s so angry ;)

I’m wondering how I should go about solving this. Is my algorithm ok and I just need to add extra conditions (like intersection testing), or is there a better way to do this? It’s very important that I minimize the number of strips in the mesh though. It’s not like I will need accurate vertex lighting or anything like that.

Left = Firefox render. Right = mine, using tri-strips

5 Replies

Please log in or register to post a reply.

Nils_Pipenbrinck 101 Mar 18, 2007 at 17:23

Hi Nutty,

There is no way around a solid tesselation algorithm for these problems.

The railroad-approach works most of the time, but if it fails depends highly on the geometry. It’s best to just run a tesselator over you data. It won’t give you strips, but you can stripify the results afterwards. With a bit of caching the performance impact is low enough that you can live with it.


TheNut 179 Mar 19, 2007 at 02:22

Well, that takes care of that. There’s still a bit of harshness around the nose, but I don’t really care that much ;)

While I’m happy GLU has a fairly easy tessellation feature, I’m rather disappointed that I’m forced to output triangles to remain consistent throughout the model. I can’t believe GLU would, by default, alternate between fans and strips like that without at least asking the developer what he would want. Such a mess.

Alas, I won’t complain beyond that. It did do a good job optimizing for triangles and I just need to further optimize it. Beggars can’t be choosers ;)

Nils_Pipenbrinck 101 Mar 19, 2007 at 10:45

The opengl reference implementation from sgi has the source code of the glu tesselator.. You can rip out all the stuff you don’t need and get a nice performance boost as well *hint* *hint*

btw- here’s my tiger rendering (was a antialiasing test)


TheNut 179 Mar 19, 2007 at 12:11

Nice! How many triangles do you use to render? Unoptimized, I can go as low as 1x resolution, or 4700 points (\~1566 tris). For decent resolution (10x), it goes as high as 20,000 tris. I’m not selective about it though, so it’s an evenly distributed set.

I’m thinking about adding an option to render to texture, or generating a series of sprites based on any vector animation. This way I can render any resolution I want without a significant impact on performance. To a degree, I’d get free anti-aliasing with the linear filtering ;) Though I do already have my own software approaches should I need them.

Nils_Pipenbrinck 101 Mar 19, 2007 at 14:03

My rendering used exactly 10478 triangles.