Triangle Strips in Shape Files

Talk about your new mod or map here

Moderators: bert_the_turtle, jelco

brice
level2
level2
Posts: 167
Joined: Fri Feb 23, 2007 6:04 am

Triangle Strips in Shape Files

Postby brice » 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:
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.
Last edited by brice on Mon May 07, 2007 2:27 am, edited 1 time in total.
brice
level2
level2
Posts: 167
Joined: Fri Feb 23, 2007 6:04 am

Postby brice » Fri Mar 16, 2007 11:45 pm

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
User avatar
Lowell
level3
level3
Posts: 428
Joined: Mon Jan 02, 2006 8:03 pm
Location: Atlanta, Georgia
Contact:

Postby Lowell » Sat Mar 17, 2007 3:56 am

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
level2
level2
Posts: 167
Joined: Fri Feb 23, 2007 6:04 am

Postby brice » Sat Mar 17, 2007 4:03 pm

Lowell wrote: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.

Return to “Mod Projects”

Who is online

Users browsing this forum: No registered users and 26 guests