Jump to content
  • Advertisement
Sign in to follow this  
pompoko

algorithm to traverse triangles in a snake-like fashion

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!