iniTree - draw your own recursion tree

LukeNeo's picture

Hello there, I just want to share with you a simple that draws a ternary tree. The algorithm is very simple and uses recursion. Here is what it does in pseudocode (for n-ary tree):

  1. main{
  2.    …
  3.    max_levels = 10      //the max num of levels
  4.    tree(initLenght, 1);
  5.    …
  6. }
  7.  
  8. tree(length, level){
  9.    …
  10.    if(level<max_levels){   //is the end of the recursion?
  11.       n = 3      //it is a ternary tree
  12.       for(x=0; x<n; <++){   
  13.          pushMatrix()
  14.          rotate ((360 / n)*x) along y axis
  15.          rotate (aperture) along z axis
  16.          drawLine(0,0,0, 0,length,0)   //from 0,0,0 to 0,length,0
  17.          translate(0,length,0)
  18.          tree(lenght/2, level+1)      //recursive call
  19.          popMatrix()
  20.       }
  21.    }
  22. }

As you can see, I used glRotate/glTranslate and glBegin(GL_LINES)/glEnd() calls, in old OpenGL style. Maybe this is the reason why with more than 8/9 levels I don't obtain good performance. Using vbo will result in better performance, but I'm still not sure about how to do that.

It is a very simple plugin, but if used in audio-reaction compositions I think it can produce interesting results. So let me know if someone use it in some cool way! :)

Download(plugin and example composition)

cybero's picture
Re: iniTree - draw your own recursion tree

Cool Stuff indeed LukeNeo :-)

benoitlahoz's picture
Re: iniTree - draw your own recursion tree

Wow ! Great !

Thanks for sharing !

gtoledo3's picture
Re: iniTree - draw your own recursion tree

This is really nice looking, I love it.

You can really do a lot of push/pop matrix stuff to move things around and get pretty good performance, for high iteration counts.

Some things that maybe you could do are to examine if anything that's strictly unnecessary to happen in the loop isn't happening there - that will sap fps for sure.

Also, GL_Lines generally don't perform as well as some other objects, but I guess this can be a bit gpu specific... there's been a decent amount of noise about this on various apple developer lists recently. I've actually had quads (and quad strip) perform quicker, which is sort of crazy considering that you have to emit more vertices. That's not a QC thing, but a mac thing (and maybe just a "thing" in general?).

Apple tends to use what's called a GFList for this kind of thing, and theoretically that should give some better performance, but I've rewritten some stuff to take advantage that, and haven't seen tremendous gain, and sometimes no gain.

... I think an interesting first test on the fps issue might be for you to try rendering points instead of lines and see if the fps picks up alot.

It would also be interesting to totally re-do this as a provider (I can see that will require a decent amount of re-jiggering...basically a total rewrite). Once you've generated the structure, the plugin won't have to execute again until an input changes - it will just hang on to that last struct you generated, and maybe you can take advantage of other renderers, like the mesh creator/mesh renderer, which is pretty stupidly fast most of the time (for some darn reason), or gl tools structure stuff.

LukeNeo's picture
Re: iniTree - draw your own recursion tree

gtoledo3 wrote:
This is really nice looking, I love it.

Thak you George! :)

gtoledo3 wrote:
Some things that maybe you could do are to examine if anything that's strictly unnecessary to happen in the loop isn't happening there - that will sap fps for sure.

..I don't think to do something other than strictly necessary to draw the tree: the code is very simple. :\

gtoledo3 wrote:
Also, GL_Lines generally don't perform as well as some other objects, but I guess this can be a bit gpu specific... there's been a decent amount of noise about this on various apple developer lists recently. I've actually had quads (and quad strip) perform quicker, which is sort of crazy considering that you have to emit more vertices. That's not a QC thing, but a mac thing (and maybe just a "thing" in general?). ... I think an interesting first test on the fps issue might be for you to try rendering points instead of lines and see if the fps picks up alot.

That's true. In the attachment you can see that I updated the plugin with a new input: primitiveType (0:GL__LINES, 1:GL_QUADS, 2:GL_POINTS). And.. performance are near the same for all three primitives, even if the amount of vertices in the scene are two times in case of lines or four times in case of quads!

gtoledo3 wrote:
It would also be interesting to totally re-do this as a provider (I can see that will require a decent amount of re-jiggering...basically a total rewrite).

That's a good test. Yes, it would be a grate change in the code, but I'm not sure about how to manage a custom-plugin structure output in the right way: according to Apple, I need to create an NSDictionary with 3 NSArray - one for each coord - containing vertices positions, am I right?.

I'd like to start also with a basic custom plugin that renders N vertices using VBO in the right way, and see how many vertices QC can manage without lose performance.

PreviewAttachmentSize
iniTree_with_primitiveType.png
iniTree_with_primitiveType.png622.18 KB
iniTree_with_primitiveType.zip16.63 KB

LukeNeo's picture
Re: iniTree - draw your own recursion tree

gtoledo3 wrote:
It would also be interesting to totally re-do this as a provider (I can see that will require a decent amount of re-jiggering...basically a total rewrite).

iniTreeStructure is what you suggested. :)