# algorithm to traverse triangles in a snake-like fashion

This topic is 3626 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I have a large right angled triangle made up by smaller right angled triangles as shown above, does anyone know a generic algorithm where I can traverse through them as shown in the picture? You can think of the triangle end points as vertices, ie in the top line (0,0), (2,0), (4,0), (6,0), (8,0) in the next line (1,1) (3,1) (5,1) (7,1)

##### Share on other sites
Are you trying to do "triangle stripping" ?

##### Share on other sites
Quote:
 Original post by fpsgamerAre you trying to do "triangle stripping" ?

well, no, I don't want to create triangle strips. these smaller triangles are actually patches made up by the actual vertices / triangles. so, a triangle showed in the picture will usually contain 16x16 vertices or more. the patches are stored in a binary tree, with different levels for different resolutions (next higher level will have half the patches, two such triangles will be simplified into one)

I think I should research space filling curves.

##### Share on other sites
Generic algorithm might be a bit difficult, or yield unexpected results.

If your mesh can always be decomposed into triangles and squares, then you've only got two different cases to consider, and you can find recursive solution.

+---+---+    +--+--+| 3 | 4 |    |2 | 3/|   |   |    |  | /+---+---+    +---/|   |   |    |1 /| 2 | 1 |    | /+---+---+    +/

If you look at your sketch, it should be obvious how to traverse these two. You can then just decompose your entire mesh into these sections, and select proper faces/vertices.

##### Share on other sites
The correct way of getting the results, is using a Sierpinski curve, as I've just learned. I guess I should be able to implement it with some brain power and coffee :)

http://users.swing.be/TGMSoft/curvesierpinski.htm

The image I posted above would be a Sierpinski curve with the level of 2.

I use this for the out of core representation / data-layout of the binary tree on the hd. An entire bintree level will be saved in this way. This is good because the right node follows just after the left node in the filestream.

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 14
• 12
• 9
• 12
• 37
• ### Forum Statistics

• Total Topics
631426
• Total Posts
3000019
×