OpenGL, Tree as a fractal, trigonometric Approach


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)

1

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

2 copy

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’3right and p’3left by rotating 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,

3 copy 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 called4 copy

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 🙂

Advertisements

10 thoughts on “OpenGL, Tree as a fractal, trigonometric Approach

    1. “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

      Like

  1. 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

    Like

    1. 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.

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s