Triangle Strips in Shape Files

[brice]

EDIT: I was wrong about the linear unwinding of the triangles strips. TGF has discovered that they actually alternate their vertex orders:

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...

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.

[brice]

SORRY, there are two bugs in the Fragment I posted above.

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.

When the fragment is viewed in Darwinia it is rotated 90 degrees from my drawing. So the vertices are labeled 1320 and 7546 clockwise from the upper left

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.

Because I wasn't paying attention, I missed a couple of holes in the back and bottom of the cube. It was hard to see because some triangles were inside out when viewed inside (through the holes) and my lighting sucks. I fixed it with a few additional triangles. Fortunately strips don't seem to care about the direction of the normals. At least I didn't have to try the different triangle orientations to get the holes to fill up.

So the final fragment is below, with 19 vertices in the strip instead of 16. Also note that the number of Verts = triangles + 2. This was wrong above, but Darwinia doesn't seem to need the Verts count -- it reads every vert listed in the strip regardless of the count.

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: 19
         v0  v1  v2  v3  v4  v5  v6  v7  v1  v5  v3  v4  v2  v0  v6  v4  v0  v6  v1

[Lowell]

Ahh cool...
I need to look deeper into this, I was trying to figure out how to make my strips at the bases of the new building objects I've used and am about to use in part two of my mod.
I had been using the "wall sections" to make the insides "solid" so as the Darwinians wouldn’t get stuck inside, plus virii can slip under walls.

[brice]

I was trying to figure out how to make my strips at the bases of the new building objects

The word "strip" can be very misleading here. Triangle strips are not neccesarily "slices". But if your model is already built by stacking cross-sectional slices, then you could certainly make a strip from each slice. The strips would correspond to a zigzag path around each "hoop" in a cylindrical model. You could continue as a single strip by doing the hoops in order.