Skip to main content
GameDev.net gamedev.net
🔒 Locked

Physics on Tree Model

Started by bensmith87 Sep 23, 2008 at 5:21 PM 16 replies 3.1k views
Original Post
bensmith87
bensmith87
Hi, I've written a short program that simulates a tree growing, it is based on one of Hugo Elias's tutorials (they are all amazing). http://freespace.virgin.net/hugo.elias/models/m_p_tree.htm I'm using a "tree" data structure to store all the branches (duh), and I'm using a polar coordinate system. What I want to do is add soft body physics to it, but am not sure how to do that. I want them to be droopy, blow in the wind etc... I'm using a lot of glMatrixPush and Pop functions, and when the depth of the branches gets too great funky stuff begins to happen, is there a solution to this. 
typedef struct sBranch
{
    float angleX;   // this is how much the branch angles away from the previous branch
    float angleY;   // and this angle rotates the previous angle, it is between 0 and 360

    float length;   // the length of the branch at the current time
    float radius;   // the radius of the branch at the current time

    float lengthSprout; // the lenght of the branch when it initially splits into 2
    float growSpeed;    // the speed of growth of both the length and radius
    
    struct sBranch *left, *right;   // pointers to sibling branchs
} tBranch;

tBranch *newBranch(float angleX, float angleY, float length, float radius, float lengthSprout, float growSpeed)
{
    tBranch *branch;

    branch = malloc(sizeof(tBranch));
    if(!branch)
        return NULL;

    branch->angleX = angleX;
    branch->angleY = angleY;
    
    branch->length = length;
    branch->radius = radius;

    branch->lengthSprout = lengthSprout;
    branch->growSpeed = growSpeed;

    branch->left = NULL;
    branch->right = NULL;

    return branch;
}

void growBranch(tBranch *branch, float dt)
{
    float angleXleft, angleYleft;
    float angleXright, angleYright;
    float growLeft, growRight;
    float lengthSproutLeft, lengthSproutRight;
    float radiusLeft, radiusRight;

    if(branch == NULL) return;

    branch->length += branch->growSpeed * dt;
    branch->radius += branch->growSpeed * 0.1f * dt;

    if(branch->length > branch->lengthSprout)
    {
        if(!branch->left)                    // if has no children yet, generate 2 new branchs
        {
            angleXleft = ((double)rand() / (double)(RAND_MAX)) * 90.0f;
            angleYleft = ((double)rand() / (double)(RAND_MAX)) * 360.0f;
            angleXright = angleXleft - 90;
            angleYright = angleYleft - 180;

            growLeft = cos(angleXleft / 57.2f) * branch->growSpeed;
            growRight = cos(angleXright / 57.2f) * branch->growSpeed;
            
            lengthSproutLeft = ((double)rand() / (double)(RAND_MAX)) * 0.1f;
            lengthSproutRight = ((double)rand() / (double)(RAND_MAX)) * 0.1f;
            
            radiusLeft = growLeft * branch->radius;
            radiusRight = growRight * branch->radius;
            
            branch->left = newBranch(angleXleft, angleYleft, 0.0f, radiusLeft, lengthSproutLeft, growLeft);
            branch->right = newBranch(angleXright, angleYright, 0.0f, radiusRight, lengthSproutRight, growRight);
        }
    }

    growBranch(branch->left, dt);
    growBranch(branch->right, dt);
}

void renderBranch(tBranch *branch, GLUquadricObj *quad)
{
    if(branch == NULL)
        return;

    glPushMatrix();
    glRotatef(branch->angleX, 1.0f, 0.0f, 0.0f);
    glRotatef(branch->angleY, 0.0f, 1.0f, 0.0f);

    glPushMatrix();
    glRotatef(-90.0f, 1.0f, 0.0f, 0.0f);        // required to orientate the cylinder along the y-axis
    gluCylinder(quad, branch->radius, branch->radius, branch->length, 8, 1);
    glPopMatrix();

    glTranslatef(0.0f, branch->length, 0.0f);   // translate to the end of the branch, so the next ones start in the correct place */

    renderBranch(branch->left, quad);
    renderBranch(branch->right, quad);
    glPopMatrix();
}
So, there is some of the source, I thought it be very cool, use it if you want, and if you have any tips/ideas on how it could be improved, much appreciated.
bensmith87
bensmith87
I fixed the funky stuff with the matrix push and pull, all I do is reverse the rotation and translation at the end of the function. Now there is nothing limiting the size of the tree, apart from processing time, and maybe memory, but I don't think so.

void renderBranch(tBranch *branch, GLUquadricObj *quad){    if(branch == NULL)        return;    glRotatef(branch->angleX, 1.0f, 0.0f, 0.0f);    glRotatef(branch->angleY, 0.0f, 1.0f, 0.0f);    glRotatef(-90.0f, 1.0f, 0.0f, 0.0f);        // required to orientate the cylinder along the y-axis    gluCylinder(quad, branch->radius, branch->radius, branch->length, 8, 1);    glRotatef(90.0f, 1.0f, 0.0f, 0.0f);    glTranslatef(0.0f, branch->length, 0.0f);   // translate to the end of the branch, so the next ones start in the correct place */    renderBranch(branch->left, quad);           // render sub branches    renderBranch(branch->right, quad);    glTranslatef(0.0f, -branch->length, 0.0f);    glRotatef(-branch->angleY, 0.0f, 1.0f, 0.0f);    glRotatef(-branch->angleX, 1.0f, 0.0f, 0.0f);}


Halifax2
Halifax2
Wow, that's amazing man. I love that.
Denzel Morris (@drdizzy) :: Software Engineer :: SkyTech Enterprises, Inc.
"When men are most sure and arrogant they are commonly most mistaken, giving views to passion without that proper deliberation which alone can secure them from the grossest absurdities." - David Hume
bensmith87
bensmith87
Thanks for the encouragement.

Here is the code for the whole program if anyone wants to play with it.
It just needs to be linked with the OpenGL and SDL library's, should be cross platform, but haven't tested it.

#include <SDL.h>#include <GL/gl.h>#include <GL/glu.h>#define SCREEN_WIDTH 800#define SCREEN_HEIGHT 600typedef struct sBranch{    float angleX;   // this is how much the branch angles away from the previous branch    float angleY;   // and this angle rotates the previous angle, it is between 0 and 360    float length;   // the length of the branch at the current time    float radius;   // the radius of the branch at the current time    float lengthSprout; // the lenght of the branch when it initially splits into 2    float growSpeed;    // the speed of growth of both the length and radius        struct sBranch *left, *right;   // pointers to sibling branchs} tBranch;int setupWindow(){    if(SDL_Init(SDL_INIT_VIDEO) < 0)    {        SDL_Quit();        return 0;    }    SDL_GL_SetAttribute(SDL_GL_DOUBLEBUFFER, 1);    SDL_GL_SetAttribute(SDL_GL_DEPTH_SIZE, 16);    SDL_GL_SetAttribute(SDL_GL_RED_SIZE, 8);    SDL_GL_SetAttribute(SDL_GL_GREEN_SIZE, 8);    SDL_GL_SetAttribute(SDL_GL_BLUE_SIZE, 8);    SDL_GL_SetAttribute(SDL_GL_ALPHA_SIZE, 8);    if(!SDL_SetVideoMode(SCREEN_WIDTH, SCREEN_HEIGHT, 0, SDL_OPENGL))        return 0;    return 1;}int handelEvents(){    static SDL_Event event;    while(SDL_PollEvent(&event))    {		switch(event.type)        {			case SDL_QUIT:				return 0;				break;            case SDL_KEYDOWN:                if(event.key.keysym.sym == SDLK_ESCAPE)                    return 0;                break;		}	}    return 1;}int setupOpenGL(){ 	glViewport(0, 0, SCREEN_WIDTH, SCREEN_HEIGHT); 	glMatrixMode(GL_PROJECTION); 	glLoadIdentity();	gluPerspective(45.0f, (float)SCREEN_WIDTH / (float)SCREEN_HEIGHT, 0.1f, 1000.0f);	glMatrixMode(GL_MODELVIEW);	glLoadIdentity(); 	    glShadeModel(GL_SMOOTH);    glClearColor(0.0f, 0.0f, 0.0f, 0.0f);    glClearDepth(1.0f);	glEnable(GL_DEPTH_TEST);	glDepthFunc(GL_LEQUAL);    glHint(GL_PERSPECTIVE_CORRECTION_HINT, GL_NICEST);    glEnable(GL_LIGHTING);    glEnable(GL_LIGHT0);        return 1;}tBranch *newBranch(float angleX, float angleY, float length, float radius, float lengthSprout, float growSpeed){    tBranch *branch;    branch = malloc(sizeof(tBranch));    if(!branch)        return NULL;    branch->angleX = angleX;    branch->angleY = angleY;        branch->length = length;    branch->radius = radius;    branch->lengthSprout = lengthSprout;    branch->growSpeed = growSpeed;    branch->left = NULL;    branch->right = NULL;    return branch;}void growBranch(tBranch *branch, float dt){    float angleXleft, angleYleft;    float angleXright, angleYright;    float growLeft, growRight;    float lengthSproutLeft, lengthSproutRight;    float radiusLeft, radiusRight;    if(branch == NULL) return;    branch->length += branch->growSpeed * dt;    branch->radius += branch->growSpeed * 0.1f * dt;    if(branch->length > branch->lengthSprout)    {        if(!branch->left)                    // if has no children yet, generate 2 new branchs        {            angleXleft = ((double)rand() / (double)(RAND_MAX)) * 90.0f;            angleYleft = ((double)rand() / (double)(RAND_MAX)) * 360.0f;            angleXright = angleXleft - 90;            angleYright = angleYleft - 180;            growLeft = cos(angleXleft / 57.2f) * branch->growSpeed;            growRight = cos(angleXright / 57.2f) * branch->growSpeed;                        lengthSproutLeft = ((double)rand() / (double)(RAND_MAX)) * 0.1f;            lengthSproutRight = ((double)rand() / (double)(RAND_MAX)) * 0.1f;                        radiusLeft = growLeft * branch->radius;            radiusRight = growRight * branch->radius;                        branch->left = newBranch(angleXleft, angleYleft, 0.0f, radiusLeft, lengthSproutLeft, growLeft);            branch->right = newBranch(angleXright, angleYright, 0.0f, radiusRight, lengthSproutRight, growRight);        }    }    growBranch(branch->left, dt);    growBranch(branch->right, dt);}void destroyBranch(tBranch *branch){    if(branch == NULL)        return;    destroyBranch(branch->left);    destroyBranch(branch->right);    free(branch);}void renderBranch(tBranch *branch, GLUquadricObj *quad){    if(branch == NULL)        return;    glRotatef(branch->angleX, 1.0f, 0.0f, 0.0f);    glRotatef(branch->angleY, 0.0f, 1.0f, 0.0f);    glRotatef(-90.0f, 1.0f, 0.0f, 0.0f);        // required to orientate the cylinder along the y-axis    gluCylinder(quad, branch->radius, branch->radius, branch->length, 8, 1);    glRotatef(90.0f, 1.0f, 0.0f, 0.0f);    glTranslatef(0.0f, branch->length, 0.0f);   // translate to the end of the branch, so the next ones start in the correct place */    renderBranch(branch->left, quad);           // render sub branches    renderBranch(branch->right, quad);    glTranslatef(0.0f, -branch->length, 0.0f);    glRotatef(-branch->angleY, 0.0f, 1.0f, 0.0f);    glRotatef(-branch->angleX, 1.0f, 0.0f, 0.0f);}int main(int argc, char **argv){    tBranch *tree;    int running = 1;    float angle = 0.0f;    GLUquadricObj *quad;	if(!setupWindow()) return 0;    if(!setupOpenGL()) return 0;    srand(time(NULL));    rand();    tree = newBranch(0.0f, 0.0f, 0.0f, 0.005f, 0.01f, 1.0f);    quad = gluNewQuadric();	gluQuadricNormals(quad, GLU_SMOOTH);	gluQuadricTexture(quad, GL_TRUE);	while(running)    {        running = handelEvents();        growBranch(tree, 0.01f);        glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);        glLoadIdentity();        glTranslatef(0.0f,-16.0f,-64.0f);        glRotatef(angle, 0.0f, 1.0f, 0.0f);        renderBranch(tree, quad);        angle += 0.4f;        SDL_GL_SwapBuffers();    }    destroyBranch(tree);	SDL_Quit();	return 0;}
deadstar
deadstar
How long does it take to generate/render a tree on average?

If you could extend it to three dimentions, maybe add UV coords and leaves to the mix, you could have the foundation for a nice SpeedTree competitor here.

"The right, man, in the wrong, place, can make all the dif-fer-rence in the world..." - GMan, Half-Life 2   A blog of my SEGA Megadrive development adventures: http://www.bigevilcorporation.co.uk
bensmith87
bensmith87
The time it takes to render/create a tree depends on how many branches it has. The creation of the tree happens in real time, as in the tree appears to grow from a single branch. The growing/rendering process doesn't drop below my refresh rate until there are like 2^20 branches, which if each branch is a 8 sided cylinder, makes 16.7 million polys for a single tree. :)
I think that there would need to be massive optimization to compete with speed tree.
And considering I've only put a few days into this project, I cant see it competing. I actually made it for a demo I have an idea of.
It is 3D, and I have just added a quick and dirty texture to it.
Leaves would be nice, I just need to work out the best/easiest way to do it.
deadstar
deadstar
Fantastic!

The point I was trying to make is SpeedTree is expensive and out of reach for us home developers, it would be nice for an open-source alternative.

I've notepad'd your code and I'll have a quick play with adding leaves and things when I get a chance, I'm quite interested in seeing how this would look in a game.

Can you get the same results twice, if the input variables are the same?

"The right, man, in the wrong, place, can make all the dif-fer-rence in the world..." - GMan, Half-Life 2   A blog of my SEGA Megadrive development adventures: http://www.bigevilcorporation.co.uk
bensmith87
bensmith87
Quote:
Can you get the same results twice, if the input variables are the same?

It just uses the standard c function rand() and uses the time as a seed, but if instead you use any old number, the tree should be the same every time.

I've been playing a bit with leaves, basically all that needs to be done is if the branch pointer is null, then just render a quad with some leaves on it.
I don't know how to do masking yet, so it looks a bit dodgy.
And I'm sure the speed of it could be increased if the trees were "pre-grown".


And your not wrong about speed tree being expensive. A free alternative would be excellent.
bensmith87
bensmith87
So, it turns out that blending isn't as hard as I thought.

Here is a lower poly version of a tree, showing off leaves, admire my gimp skilz if you wish.



And the source of the new render function.

void renderBranch(tBranch *branch, GLUquadricObj *quad){    if(!branch)    {        glEnable(GL_BLEND);							// Enable Blending//    	glDisable(GL_DEPTH_TEST);    	    	glBlendFunc(GL_DST_COLOR,GL_ZERO);        glBindTexture(GL_TEXTURE_2D, leafmask);        glBegin(GL_QUADS);        glTexCoord2d(0.0,0.0);        glVertex3f(-10.0f, 0.0f, 0.0f);        glTexCoord2d(0.0,1.0);        glVertex3f(-10.0f,  20.0f, 0.0f);        glTexCoord2d(1.0,1.0);        glVertex3f( 10.0f,  20.0f, 0.0f);        glTexCoord2d(1.0,0.0);        glVertex3f( 10.0f, 0.0f, 0.0f);        glEnd();                glBlendFunc(GL_ONE, GL_ONE);        glBindTexture(GL_TEXTURE_2D, leaf);        glBegin(GL_QUADS);        glTexCoord2d(0.0,0.0);        glVertex3f(-10.0f, 0.0f, 0.0f);        glTexCoord2d(0.0,1.0);        glVertex3f(-10.0f,  20.0f, 0.0f);        glTexCoord2d(1.0,1.0);        glVertex3f( 10.0f,  20.0f, 0.0f);        glTexCoord2d(1.0,0.0);        glVertex3f( 10.0f, 0.0f, 0.0f);        glEnd();//        glEnable(GL_DEPTH_TEST);						// Enable Depth Testing    	glDisable(GL_BLEND);        return;    }    glBindTexture(GL_TEXTURE_2D, bark);            glRotatef(branch->angleX, 1.0f, 0.0f, 0.0f);    glRotatef(branch->angleY, 0.0f, 1.0f, 0.0f);    glRotatef(-90.0f, 1.0f, 0.0f, 0.0f);        // required to orientate the cylinder along the y-axis    gluCylinder(quad, branch->radius, branch->radius, branch->length, 8, 1);    glRotatef(90.0f, 1.0f, 0.0f, 0.0f);    glTranslatef(0.0f, branch->length, 0.0f);   // translate to the end of the branch, so the next ones start in the correct place */    renderBranch(branch->left, quad);           // render sub branches    renderBranch(branch->right, quad);    glTranslatef(0.0f, -branch->length, 0.0f);    glRotatef(-branch->angleY, 0.0f, 1.0f, 0.0f);    glRotatef(-branch->angleX, 1.0f, 0.0f, 0.0f);}


I'm sure this code could be made much prettier :)
deadstar
deadstar
That's brilliant - any restrictions on how I might use this code? I'll probably dig deep into it and rewrite to embed into an engine, I'd work it for the "pre-grown" strategy.

"The right, man, in the wrong, place, can make all the dif-fer-rence in the world..." - GMan, Half-Life 2   A blog of my SEGA Megadrive development adventures: http://www.bigevilcorporation.co.uk
bensmith87
bensmith87
No restrictions, you can use it however you like, send us a message if it goes into something cool.
I'm going to have a play around and see if I can neaten it up and do the pre-grown thing, should be easier than what is there already.
Have fun.
h4tt3n
h4tt3n
Very beautiful. I'll look into this and probably convert it to my mother tongue - Freebasic :)

I once did a tree/shrub simulation based on a mass-spring-damper system including angular springs.

cheers,
Michael
bensmith87
bensmith87
Quote:
I once did a tree/shrub simulation based on a mass-spring-damper system including angular springs.


This was what I was originally thinking, but I'm not to sure on how to implement it. Like do the branches further down the chain effect ones near the base. And how would I get say a gravity vector transformed into the right space, as the branches undergo a lot of transformations.

I might just cheat, and implement some sort of skeletal animation system.

Quote:
I'll look into this and probably convert it to my mother tongue - Freebasic :)


The program uses dynamic memory allocation to create the new branches, does Freebasic support this easily.

Have a good one.
_swx_
_swx_
If you want to create realistic trees, this is not the correct approach. The algorithm used by SpeedTree etc is "Creation and rendering of realistic trees" by Jason Weber et al.

Pictures can be found here: http://www.imonk.com/baboon/trees/

It's very easy to implement and _very_ fast (milliseconds for a game-quality tree)
bensmith87
bensmith87
Quote:
The algorithm used by SpeedTree etc is "Creation and rendering of realistic trees" by Jason Weber et al.

Do you know where I can get a hold of that paper, those trees look great.
EDIT: Looks like I need to purchase a SIGGRAPH Membership.
_swx_
_swx_
PM me your e-mail address and I'll send it to you.

EDIT: A java implementation of the algorithm: http://arbaro.sourceforge.net/
h4tt3n
h4tt3n
Quote:
Original post by bensmith87
Quote:
I once did a tree/shrub simulation based on a mass-spring-damper system including angular springs.


This was what I was originally thinking, but I'm not to sure on how to implement it. Like do the branches further down the chain effect ones near the base. And how would I get say a gravity vector transformed into the right space, as the branches undergo a lot of transformations.

I might just cheat, and implement some sort of skeletal animation system.

Quote:
I'll look into this and probably convert it to my mother tongue - Freebasic :)


The program uses dynamic memory allocation to create the new branches, does Freebasic support this easily.

Have a good one.


Thanks. I wouldn't mind tossing up a tiny example. It's not that hard. But I'm a bit behind on a few things, and my laptop died on me recently, so it might be a couple of days...

And yes, FreeeBasic does support quite a number of things including dynamic memory allocation.

Cheers,
Michael

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.