### Triangle Strips in Shape Files

Posted:

**Fri Mar 16, 2007 10:12 pm**EDIT: I was wrong about the linear unwinding of the triangles strips. TGF has discovered that they actually alternate their vertex orders:

which she verifies here: http://forums.introversion.co.uk/darwinia/viewtopic.php?p=39587#39587

This would explain the difficulties I had with inverted normals below...

I figured out the triangle strips. The short answer is: don't bother for anything more complex than a simple cube or three.

Here's a link which explains some of the details: http://www.codercorner.com/Strips.htm

If you know what a Hamiltonian path is, then you are most of the way to understanding triangle strips. You list the veritces in such a way that when you take successive triplets (triangles) you end up visiting every triangle for the shape. The trick is that each triplet overlaps the previous two, so most of the triangle info becomes redundant.

But it can be a very difficult problem. There are always many solutions, and finding the best ones is NP-hard. For a cube you can figure it out with pencil and paper. Beyond that you're better off working with Blender or whatever.

Here's a Fragment listing which paints a small cube:

If you picture this cube, the vertices for the side facing you are 0132, listed clockwise from the upper left. From the same viewing position the vertices on the back face are 6754 in the same order. So vertices 0 and 6 are opposite each other.

The triangle strip I came up with is 0123456715342061. This encodes 14 triangles, with two of them redundant because I painted myself into a corner. For a cube there may be a perfect order which uses just 12 triangles. I don't know. This was just the first path that worked for me.

For my purposes I tried adding a triangle list to a shape file that used strips exclusively. The triangles didn't render. Maybe you can't mix render modes (or I screwed up). If you need to add a simple geometric fragment to a strip file, then paper and pencil should work for you. But anything more complex than a cube or three and this will probably waste your time unless you suffer extreme OCD or enjoy combinatorial puzzles.

However, since you can re-specify triangles multiple times, there is no reason you couldn't come up with a very non-optimal strip in reasonable time. The algorithm essentially works like painting a room. Double and triple painting doesn't harm anything.

edit - ok, contrary to popular believe, strips alternate (apparently o_O), ABCDEFG -> ABC DCB CDE FED EFG, at least according to the screen grab I just got...

which she verifies here: http://forums.introversion.co.uk/darwinia/viewtopic.php?p=39587#39587

This would explain the difficulties I had with inverted normals below...

xander wrote:Luftbauch wrote:works nice, but please can me someone tell how to convert animated models to shapes.

In the animated mine.shp file stands something like

Code: Select all

`137: 136 0`

Strips: 1

Strip: 0

Material: GunMetal

Verts: 490

v50 v51 v52 v51 v13 v51

How to understand that v - thing ?

How to export animations correct or how to manage it manually?

Thanks

Actually, the mines (and other animated buildings) are conglomerations of several shapes. Each of the shapes, themselves, are static, and are rotated or animated by the game engine. Strips are an alternative to triangles. I am not quite sure how they are related, however.

xander

I figured out the triangle strips. The short answer is: don't bother for anything more complex than a simple cube or three.

Here's a link which explains some of the details: http://www.codercorner.com/Strips.htm

Should I care ?

For the happy beginners out there, let’s briefly recall what a triangle strip is. Say your mesh contains a list of connected triangles. A triangle is made of three vertex references, and in case of connected triangles, two of them may be shared from one triangle to another. The list of indices resulting from this sharing forms a triangle strip. For example those triangles :

012

123

234

345

are equivalent to a single strip :

012345

Here’s the standard algorithm :

1) choose a starting face for a strip

2) choose a direction (i.e. an edge) in which you’ll walk along the strip

3) actually extend the strip in the chosen direction until you reach a triangle with no forwards connections

4) go to 1) until all faces have been visited

If you know what a Hamiltonian path is, then you are most of the way to understanding triangle strips. You list the veritces in such a way that when you take successive triplets (triangles) you end up visiting every triangle for the shape. The trick is that each triplet overlaps the previous two, so most of the triangle info becomes redundant.

But it can be a very difficult problem. There are always many solutions, and finding the best ones is NP-hard. For a cube you can figure it out with pencil and paper. Beyond that you're better off working with Blender or whatever.

Here's a Fragment listing which paints a small cube:

Code: Select all

`Fragment: Box`

ParentName: sceneroot

up: 0.00 1.00 0.00

front: 0.00 0.00 1.00

pos: 0.00 50.00 0.00

Positions: 8

0: -5 -5 5

1: 5 -5 5

2: -5 5 5

3: 5 5 5

4: -5 5 -5

5: 5 5 -5

6: -5 -5 -5

7: 5 -5 -5

Normals: 0

Colours: 1

0: 128 128 128

Vertices: 8 # Position ID then Colour ID

0: 0 0

1: 1 0

2: 2 0

3: 3 0

4: 4 0

5: 5 0

6: 6 0

7: 7 0

Strips: 1

Strip: 0

Material: GunMetal

Verts: 14

v0 v1 v2 v3 v4 v5 v6 v7 v1 v5 v3 v4 v2 v0 v6 v1

If you picture this cube, the vertices for the side facing you are 0132, listed clockwise from the upper left. From the same viewing position the vertices on the back face are 6754 in the same order. So vertices 0 and 6 are opposite each other.

The triangle strip I came up with is 0123456715342061. This encodes 14 triangles, with two of them redundant because I painted myself into a corner. For a cube there may be a perfect order which uses just 12 triangles. I don't know. This was just the first path that worked for me.

For my purposes I tried adding a triangle list to a shape file that used strips exclusively. The triangles didn't render. Maybe you can't mix render modes (or I screwed up). If you need to add a simple geometric fragment to a strip file, then paper and pencil should work for you. But anything more complex than a cube or three and this will probably waste your time unless you suffer extreme OCD or enjoy combinatorial puzzles.

However, since you can re-specify triangles multiple times, there is no reason you couldn't come up with a very non-optimal strip in reasonable time. The algorithm essentially works like painting a room. Double and triple painting doesn't harm anything.