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)
algorithm to traverse triangles in a snake-like fashion
Author
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)
Author
Quote:Original post by fpsgamer
Are 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.
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.
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.
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.
Author
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
