Our goal is to,

- Draw a tree using fractals with recursion
- Take user input for:
- Depth of tree/sub-trees
- Angle between leftmost and rightmost branch in same depth

Fractals are useful way of approaching to infinity and for drawing some real life like objects where same pattern recurs. To do so, we are drawing single line and then recurring sub trees.

Recursive definition of such trees might be,

A tree is a line from root point to tree top point followed by two sub-trees, each having the root at the top of parent tree and own top at new calculated point.

The idea of Fractal tree is to build it from two initial points,

*Root of tree*p1(x1,y1)*Tree top*p2(x2,y2)

*Fig 1:* Draw the basis of tree

We draw this part by,

glBegin(GL_LINE_STRIP); glVertex2f(x1,y1);// root of tree glVertex2f(x2,y2);//tree top glEnd();

Now, we should find the two points for each of the sub-trees. To do so, let us first find a point p3 on the line p1p2. This will be done by changing the co-ordinate by placing new origin at p1 and multiplying x2 and y2 by the same multiplication factor. Hence, if the distance between *p1* and *p2* be *l12* and if the multiplication factor is *m* then we need to get *p3* at *l23* distant from p1 such that

It is depicted below in figure 2

*Fig 2:* Find point 3

This is done by the code segment shown below,

x3=(x2-x1)*treeRatio+x1, y3=(y2-y1)*treeRatio+y1;

After that, we can find the tree top points of the sub-trees, *p’3 _{right}* and

*p’3*by rotating

_{left}*p3*in y-axis with respect to

*p2*by

*θ*angle (right sub-tree) and

*– θ*angle (left sub-tree) as done by figure 3 and the pseudo code below,

*Fig 3: *Find the recurring points

x3=x3-x2; y3-=y2; X’3right = x3 * cos(angle) + y3 * sin(angle) + x2; Y’3right = -x3 * sin(angle) + y3 * cos(angle) + y2; X’3left = x3 * cos(-angle) + y3 * sin(-angle) + x2; Y’3left = -x3 * sin(-angle) + y3 * cos(-angle) + y2;

Now, we can recursively call the function for drawing sub-trees, by decreasing depth by one.

Figure 4 below depicts a right sub-tree being called

*Fig 4:* Recursive call to draw right sub-tree

The code segment below, includes the definition of this recursive function in action,

Listing A |

void tree(GLfloat x1, GLfloat y1, //root of tree GLfloat x2, GLfloat y2, //tree top GLfloat angle,//angle/2 between outermost branches of same level GLint n //depth of subtree ) { glBegin(GL_LINE_STRIP); glVertex2f(x1,y1);// root of tree glVertex2f(x2,y2);//tree top glEnd(); if(n<1)return ; //stop criteria of recursion int nn = n-1; //decrement GLfloat //find P3 by x3=(x2-x1)*treeRatio+x1-x2, //translating co-ordinate system to p1 y3=(y2-y1)*treeRatio+y1-y2; //then multiplying p2 by the factor //and position it back to real co-ord //right subtree tree(x2, y2, x3 * cos(angle) + y3 * sin(angle) + x2,// P'3 -x3 * sin(angle) + y3 * cos(angle) + y2,// angle,nn,branchCount); //left subtree tree(x2, y2, x3 * cos(-angle) + y3 * sin(-angle) + x2,// P'3 -x3 * sin(-angle) + y3 * cos(-angle) + y2, angle,nn,branchCount); }

###### Enhanced Branches

If we want to use more than two sub-trees, we can do it by enhancing the function from *listing A*, as depicted in *listing B*. (Changes are highlighted)

Listing B |

void tree(GLfloat x1, GLfloat y1, //root of tree GLfloat x2, GLfloat y2, //tree top GLfloat angle,//angle/2 between outermost branches of same level GLint n, //depth of subtree GLint branchCount) //number of sub-trees per level { glBegin(GL_LINE_STRIP); glVertex2f(x1,y1);// root of tree glVertex2f(x2,y2);//tree top glEnd(); if(n<1)return ; //stop criteria of recursion int nn = n-1; //decrement GLfloat //find P3 by x3=(x2-x1)*treeRatio+x1-x2, //translating co-ordinate system to p1 y3=(y2-y1)*treeRatio+y1-y2; //and then multiplying p2 by the factor //and position it back to real co-ord if(branchCount==2){ //right subtree tree(x2, y2, x3 * cos(angle) + y3 * sin(angle) + x2,// P'3 -x3 * sin(angle) + y3 * cos(angle) + y2,// angle,nn,branchCount); //left subtree tree(x2, y2, x3 * cos(-angle) + y3 * sin(-angle) + x2,// P'3 -x3 * sin(-angle) + y3 * cos(-angle) + y2, angle,nn,branchCount); } else { GLfloat nowAngle = -angle; GLfloat angleTone = angle/(branchCount-1)*2; for(int i=0;i<branchCount;i++,nowAngle+=angleTone){ tree(x2, y2, x3 * cos(nowAngle) + y3 * sin(nowAngle) + x2, -x3 * sin(nowAngle) + y3 * cos(nowAngle) + y2, angle,nn,branchCount); } } }

Many objects have self-similarity. A fractal is a rough or fragmented geometric shape that can be subdivided in parts, each of which is (at least approximately) a smaller copy of the whole. These fractals can be utilized to model such self-similar objects in computer graphics. Recursive functions can be nicely used to design fractals with its self-similar parts. Design of such objects depends on devising a recursion and thus care should be taken to limit the bound and base criteria should be evaluated nicely.

Thanks for your time with me 🙂

Hey, what is “treeRatio” defined as ??

LikeLike

“treeRatio” can be any real value. Say, P1P2 has a length l1, u want that u’r subtree’s all branches will have a length l2… then, treeRatio here determines the ratio of l1 & l2.

In general case, treeRatio is a value between 0&1

LikeLike

Great job!! Is it possible to give the full source code?

LikeLike

all necessary codes are already here in this very post. You can though check posts in http://en.wordpress.com/tag/opengl-computer-graphics-computation/ & https://nafsadh.wordpress.com/category/computer-studies/computer-graphics/opengl-computer-graphics-computation/ to begin from Ground Up.

LikeLike

hello I was luck to seek your subject in baidu

your post is terrific

I get much in your website really thanks very much

btw the theme of you site is really exceptional

where can find it

LikeLike

this theme is a theme of wp.com named “Enterprise by StudioPress”

LikeLike

Nice post.Wat is the running time of your algorithm to generate a reasonably believable tree branches?I have tried like this previously and opengl(actually JOGL) hung up.

LikeLike

ok, this algorithm is not the most efficient on, but is designed in this way coz I intended it to be so. If the

`depth of subtree`

or`branchCount`

cross certain limit (7 or more depending on PC’s capability) then computer might hang for a long while.As this program was made to demonstrate graphic calculation rather than for practical use, I avoided using most of OpenGL library features and used CPU mathematics. For practical use, these jobs should be done using OpenGL support only (rotation and transformation) to use GPU power.

LikeLike

whats the header files to b included for above code segment

LikeLike

please refer to previous articles on this series at http://bit.ly/inOpenGL

LikeLike