Help With Procedural Tree Algorithm

Nick

Sage

Posts: 1,066
Joined: 2004.07

Post: #1

Jul 26, 2006 — 10:43 AM

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;

}

unknown

Sage

Posts: 1,403
Joined: 2005.07

Post: #2

Jul 26, 2006 — 10:56 AM

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!

Possibly Related Threads...

Thread:		Author	Replies:	Views:	Last Post
	Procedural graphics	kam187	4	7,952	Jan 8, 2012 08:58 PM Last Post: bronxbomber92
	Need help with 2D algorithm	neigaard	7	3,541	Jan 30, 2009 08:02 AM Last Post: neigaard
	Tree Culling	Jake	13	5,310	Jan 7, 2005 02:44 AM Last Post: arekkusu
	Algorithm for sorting Vertices	LongJumper	7	4,897	Jul 30, 2004 12:41 AM Last Post: Bames53
	tree rendering	NYGhost	9	3,820	Jan 9, 2004 02:43 PM Last Post: NYGhost