Help With Procedural Tree Algorithm

Sage
Posts: 1,066
Joined: 2004.07
Post: #1
I don't know if this algorithm/technique has been used before, but I'm having trouble figuring out how to control the growth more. I figured out how to draw it and have it create the basic tree, but my trees are definitely no where near real looking. I tried to use the current generation to help reduce things like branch divisions and branch lengths, but I still get some awkwardly long looking branches.

Can anyone take a look at this and offer any suggestions as to how to control the tree's growth more? Here's the full code. Just compile it in terminal and run from there. It needs to be linked with the GLUT, OpenGL, and Cocoa frameworks.

Code:
//g++ trees.cpp -o trees -framework GLUT -framework OpenGL -framework Cocoa

#include <GLUT/glut.h>
#include <OpenGL/OpenGL.h>
#include <stdio.h>
#include <list.h>
#include <math.h>
#include <time.h>

class Node
{
public:
    Node( void ):mNext( NULL ) {}
    ~Node( void )
    {
        std::list< Node* >::iterator itr;
        for ( itr = mChildren.begin(); itr != mChildren.end(); ++itr )
            delete ( *itr );
        
        if ( mNext )
            delete mNext;
    }
    
    void draw( void )
    {
        glRotatef( mYaw, 0, 1, 0 );
        glRotatef( mPitch, 0, 0, 1 );
        
        glBegin( GL_LINES );
        
        glColor3f( mR, mG, mB );
        glVertex3f( 0, 0, 0 );
        glVertex3f( 0, mLength, 0 );
        
        glEnd();
        
        glTranslatef( 0, mLength, 0 );
        
        if ( !mChildren.empty() )
        {
            std::list< Node* >::iterator itr;
            for ( itr = mChildren.begin(); itr != mChildren.end(); ++itr )
            {
                glPushMatrix();
        
                ( *itr )->draw();
                
                glPopMatrix();
            }
        }
        
        if ( mNext )
            mNext->draw();
    }
    
    float                mLength;
    float                mPitch, mYaw;
    float                mR, mG, mB;
    std::list< Node* >    mChildren;
    Node                *mNext;
};

// Global Variables
Node                *gRoot = NULL;
float                gYaw = 0.0f;    //make the tree spin
int                    gNumDivisions = 5;    //number of divisions in each branch

#define                MAX_GENERATIONS            3

#define                MIN_LENGTH                0.5f
#define                MAX_LENGTH                1.0f
#define                MIN_PITCH                -5.0f
#define                MAX_PITCH                5.0f
#define                MIN_CHILD_PITCH_ADJUST    45.0f
#define                MAX_CHILD_PITCH_ADJUST    60.0f
// End Global Variables

//simply wrapping the random function
float randFloat( float min, float max )
{
    if ( max <= min )
        return max;
    
    float newRand = ( float )( rand() % ( int )( max * 100 ) );
    newRand *= 0.01f;
    newRand += min;
    return newRand;
}

Node* generateNode( float length, float pitch, float yaw, int division, int numChildren, int generation )
{
    Node *newNode = new Node;
    newNode->mLength = length;
    newNode->mPitch = pitch;
    newNode->mYaw = yaw;
    newNode->mR = randFloat( .3, 1 );
    newNode->mG = randFloat( .3, 1 );
    newNode->mB = randFloat( .3, 1 );
    
    if ( division > 0 )
    {
        newNode->mNext = generateNode( randFloat( MIN_LENGTH, MAX_LENGTH ), randFloat( MIN_PITCH, MAX_PITCH ), randFloat( 0.0f, 360.0f ), division - 1, numChildren, generation );
    
        if ( generation <= MAX_GENERATIONS )
        {
            for ( int i = 0; i < numChildren; i++ )
            {
                newNode->mChildren.push_back( generateNode( randFloat( MIN_LENGTH / ( float )generation, MAX_LENGTH / ( float )generation ), randFloat( MIN_PITCH, MAX_PITCH ) + randFloat( MIN_CHILD_PITCH_ADJUST, MAX_CHILD_PITCH_ADJUST ), randFloat( 0.0f, 360.0f ), gNumDivisions / ( generation + 1 ), numChildren, generation + 1 ) );
            }
        }
    }
    
    return newNode;
}

bool generateTree( void )
{
    srand( time( NULL ) );
    
    gRoot = generateNode( 1, 0, 0, gNumDivisions, 1, 1 );
    
    return true;
}

void display( void )
{
    glClear( GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT );
    glLoadIdentity();
    
    glTranslatef( 0, -3, -10 );
    glRotatef( gYaw, 0, 1, 0 );
    gYaw += .1f;
    if ( gYaw > 360 )
        gYaw -= 360;
    
    glColor3f( 0, 1, 0 );
    gRoot->draw();
    
    glutSwapBuffers();
}

void reshape( int width, int height )
{
    glViewport( 0, 0, width, height );
    
    glMatrixMode( GL_PROJECTION );
    glLoadIdentity();
    gluPerspective( 45.0f, (float)width / (float)height, .01f, 1000.0f );
    
    glMatrixMode( GL_MODELVIEW );
    glLoadIdentity();
}

void idle( void )
{
    glutPostRedisplay();
}

int main( int argc, char *argv[] )
{
    glutInit( &argc, argv );
    
    glutInitDisplayMode( GLUT_RGBA | GLUT_DOUBLE );
    glutInitWindowSize( 800, 600 );
    glutCreateWindow( "Tree Generation" );
    
    glutDisplayFunc( display );
    glutReshapeFunc( reshape );
    glutIdleFunc( idle );
    
    glEnable( GL_LINE_SMOOTH );
    glEnable( GL_DEPTH_FUNC );
    
    if ( !generateTree() )
    {
        delete gRoot;
        return -1;
    }
    
    glutMainLoop();
    
    delete gRoot;
    
    return 0;
}
Quote this message in a reply
Sage
Posts: 1,403
Joined: 2005.07
Post: #2
line 102
Code:
        newNode->mNext = generateNode( randFloat( MIN_LENGTH, [b]length[/b] ), randFloat( MIN_PITCH, MAX_PITCH ), randFloat( 0.0f, 360.0f ), division - 1, numChildren, generation );

Sir, e^iπ + 1 = 0, hence God exists; reply!
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Procedural graphics kam187 4 9,405 Jan 8, 2012 08:58 PM
Last Post: bronxbomber92
  Need help with 2D algorithm neigaard 7 3,999 Jan 30, 2009 08:02 AM
Last Post: neigaard
  Tree Culling Jake 13 5,943 Jan 7, 2005 02:44 AM
Last Post: arekkusu
  Algorithm for sorting Vertices LongJumper 7 5,457 Jul 30, 2004 12:41 AM
Last Post: Bames53
  tree rendering NYGhost 9 4,116 Jan 9, 2004 02:43 PM
Last Post: NYGhost