Here is the code for the basic skeleton: tree_basicSkeleton.bas
Before defining our classes and setting up variables for the tree information we should set up some limits on our output.
CONST MAX_NODES = 13, MAX_BRANCHES = 13, MAX_LEAVES = 5, MAX_SEGS = 3
MAX_NODES basically refers to the max number of segments along the branch. After defining this we will be able to determine how far along one branch another one occurs enabling us to determine how many nodes this new branch will have.
MAX_BRANCHES, MAX_LEAVES - how many branches and leaf planes our tree will have
MAX_SEGS defines how many segments the cylinder of the branches has. The higher the number, the round they will be.
Next we develop our types. For our Branch Type we'll need to keep track of each branches parent branch and node location on the parent branch. We will need to know how many nodes our branch has as well as the node information (location / angle).
In our Node type, we need to keep track of the node x/y/z location as well as the global node location is for this node. What this means is, if the max nodes is set to 13, and you're node 3 on a branch that's close to the end of another branch, on the global scale you're really node 12 because you're 12 nodes away from the base of the tree. This is important for determining how long node segments need to be as well as their diameter. We also have an array called plane. This stores a set of x/y/z coordinates that stick out perpendicular to the node segment. There will be one of these points circling each node point for each of the cylinder segments.
Lastly we have our nodeAngle type. This has an x/y/z angle for our branch. Yes we could use spherical coordinates also. >)
type pointType
x as single
y as single
z as single
end type
TYPE nodeType
x AS SINGLE
y AS SINGLE
z AS SINGLE
globalNode as integer
plane(MAX_SEGS - 1) as pointType
END TYPE
TYPE nodeAngleType
x AS SINGLE
y AS SINGLE
z AS SINGLE
end type
TYPE branchType
nNodes AS INTEGER
nodes(MAX_NODES) as nodeType
nodeAngle(MAX_NODES) as nodeAngleType
root as nodeType
END TYPE
These are some basic variables that we will be incorporating to help give us some control of the tree's look
baseBranches = 1 sag! = 10 growth! = 0 scale! = .5 twistyness = 30 trunkLength = 4 twigLength = 1.5 branchLengthInter! = (twigLength - trunkLength) / totalNodes trunkWidth = 1.4 twigWidth = 0 branchWidthInter! = (twigWidth - trunkWidth) / totalNodes
baseBranches determines how many trunks the tree will have.
sag! determines how much the branches want to curve downward. It is directly counteracted by growth! Due to the angle of curving being compounded each node a small value of growth is enough to make the branches resist curving and point more upwards.
scale! is a multiplier that is used to control how long the branches end up being. It is not necessary required.
twistyness is used to control how much the branches want to curve side to side not just downward.
branchLengthInter! and branchWidthInter! are used to produce a linear reduction in the branch width/length based on each node's global location
Loop for each of the branches and initialize the branch information
for branch = 0 to nBranches - 1
for i = 0 to totalNodes - 1
branches(branch).nodes(i).globalNode = 0
branches(branch).nodeAngle(i).x = 0
branches(branch).nodeAngle(i).y = 0
branches(branch).nodeAngle(i).z = 0
branches(branch).nodes(i).x = 0
branches(branch).nodes(i).y = 0
branches(branch).nodes(i).z = 0
'branches(branch).nodes(i).connected = 0
next
We're going to randomly select a parent location for our branch. When parentBranch is set to -1, the generator recognizes this as the branch sticking out of the base x/y/z location. If we have not created each of our trunks then we will create these first. This is accomplished by subtracting 1 from the # of baseBranches for each one that we've created. This way once baseBranches = 0 we're allowed to start creating sub-branches.
do
parentBranch = int(rnd * branch)
if baseBranches > 0 then parentBranch = -1
During this loop we will set parentNode to the desired node. We initially set it to -1 that way if its > -1 we know that we were successful in finding a valid spot for our node.
If parentBranch is > -1 we're allowed to use a node from another branch as our starting point. We'll find a random node, set the branch's root x/y/z to the location of the node point on the parent. We align our branch to the same angle as the parent node and then have it point outward at a random y angle.
Here is where we set our globalNode value for the base node. We use globalNode to determine how many nodes this branch will have as well as the starting point for each of the branch's node's globalNode value.
parentNode = -1
if parentBranch > -1 then
parentNode = int(rnd * branches(parentBranch).nNodes)
branches(branch).root.x = branches(parentBranch).nodes(parentNode).x
branches(branch).root.y = branches(parentBranch).nodes(parentNode).y
branches(branch).root.z = branches(parentBranch).nodes(parentNode).z
branches(branch).nodeAngle(0).x = branches(parentBranch).nodeAngle(parentNode).x
branches(branch).nodeAngle(0).y = branches(parentBranch).nodeAngle(parentNode).y + rnd * 180 - 90
branches(branch).nodeAngle(0).z = branches(parentBranch).nodeAngle(parentNode).z
globalNode = branches(parentBranch).nodes(parentNode).globalNode
else
branches(branch).root.x = 0
branches(branch).root.y = 0
branches(branch).root.z = 0
branches(branch).nodeAngle(0).x = 0
branches(branch).nodeAngle(0).y = rnd * 360
branches(branch).nodeAngle(0).z = 0
globalNode = 0
baseBranches = baseBranches - 1
end if
nNodes = totalNodes - globalNode
branches(branch).nNodes = nNodes
if nNodes > 0 and parentNode <> 0 then exit do
loop
This next section of code is where the real math comes into play when determining how the branches curve and where the x/y/z location for each node will be at.
ox!, oy!, oz! are used to keep track of the previous node's location so that our new node is sticking out of it.
globalNode is incremented for each node and used for calculating how long the node is.
the sub rotpnt takes a vector x/y/z and rotates it by angles rx/ry/rz then spits out the final point in nx/ny/nz. We are using this to rotate a vector from pointing directly upwards to be pointing in the direction of the branch.
ox! = branches(branch).root.x
oy! = branches(branch).root.y
oz! = branches(branch).root.z
for node = 0 to nNodes - 1
globalNode = globalNode + 1
rx! = branches(branch).nodeAngle(node).x + rnd * twistyness - twistyness / 2
ry! = branches(branch).nodeAngle(node).y + rnd * twistyness - twistyness / 2
rz! = branches(branch).nodeAngle(node).z + rnd * twistyness - twistyness / 2
rz! = rz! + rnd * sag! * rz! / 90 + sag! / 5
rz! = rz! - rnd * growth! * rz! / 90 - growth! / 5
rotpnt 0, (trunkLength + globalNode * branchLengthInter!) * scale!, 0, 0, 0, rz!, nx!, ny!, nz!
rotpnt nx!, ny!, nz!, rx!, 0, 0, nx!, ny!, nz!
rotpnt nx!, ny!, nz!, 0, ry!, 0, nx!, ny!, nz!
branches(branch).nodes(node).x = ox! + nx!
branches(branch).nodes(node).y = oy! + ny!
branches(branch).nodes(node).z = oz! + nz!
branches(branch).nodeAngle(node+1).x = rx!
branches(branch).nodeAngle(node+1).y = ry!
branches(branch).nodeAngle(node+1).z = rz!
branches(branch).nodes(node).globalNode = globalNode
ox! = branches(branch).nodes(node).x
oy! = branches(branch).nodes(node).y
oz! = branches(branch).nodes(node).z
next
next
Here is some very basic code looping through each node on each base, drawing a line from the node x/y/z to the previous node's x/y/z. If the previous node is -1, we'll use the branch's root x/y/z location. Again we use getXY to convert the 3d coordinates to screen coordinates. This is placed in the main loop.
for branch = 0 to nBranches - 1
nNodes = branches(branch).nNodes
for node = 0 to nNodes - 1
x0! = branches(branch).nodes(node).x
y0! = branches(branch).nodes(node).y
z0! = branches(branch).nodes(node).z
if node > 0 then
x1! = branches(branch).nodes(node - 1).x
y1! = branches(branch).nodes(node - 1).y
z1! = branches(branch).nodes(node - 1).z
else
x1! = branches(branch).root.x
y1! = branches(branch).root.y
z1! = branches(branch).root.z
end if
getXY x0!, y0!, z0!, screenX0, screenY0
getXY x1!, y1!, z1!, screenX1, screenY1
line (screenX0, screenY0) - (screenX1, screenY1), 6
next
next
Here is the code for the basic skeleton: tree_basicSkeleton.bas
In order to create the cylinders that follow the branch we will need to generate points perpendicular to each node and connect these to form planes parallel to each branch. First we use rotpnt to rotate a vector pointing forward in a circle around the y axis. Then we use rotpnt again to rotate the circle of points to the same direction as the branch. Originally our branch vector pointed straight up then was rotated to the direction of the branch, since we started with a vector pointing forward before rotating we'll have a new point that is perpendicular to the branch.
In our formula for the z vector we include some calculation to make the radius of the circle smaller as you get closer to the last node.
This code is added after ox!, oy!, oz! in the tree generation section:
for p = 0 to MAX_SEGS - 1
rotpnt 0, 0, (trunkWidth * cos(3.14159 / 2 * globalNode / totalNodes)) * scale!, 0, p * 360/MAX_SEGS, 0, nx!, ny!, nz!
rotpnt nx!, ny!, nz!, 0, 0, rz!, nx!, ny!, nz!
rotpnt nx!, ny!, nz!, rx!, 0, 0, nx!, ny!, nz!
rotpnt nx!, ny!, nz!, 0, ry!, 0, nx!, ny!, nz!
branches(branch).nodes(node).plane(p).x = ox! + nx!
branches(branch).nodes(node).plane(p).y = oy! + ny!
branches(branch).nodes(node).plane(p).z = oz! + nz!
next
Next is the new display code to replace the original single lines
for branch = 0 to nBranches - 1
nNodes = branches(branch).nNodes
for node = 0 to nNodes - 1
for p = 0 to MAX_SEGS - 1
n = p + 1
if n = MAX_SEGS then n = 0
nx! = branches(branch).nodes(node).plane(n).x
ny! = branches(branch).nodes(node).plane(n).y
nz! = branches(branch).nodes(node).plane(n).z
getXY nx!, ny!, nz!, pnti(0,0), pnti(0,1)
n = p
nx! = branches(branch).nodes(node).plane(n).x
ny! = branches(branch).nodes(node).plane(n).y
nz! = branches(branch).nodes(node).plane(n).z
getXY nx!, ny!, nz!, pnti(3,0), pnti(3,1)
nn = node - 1
if nn > -1 then
n = p + 1
if n = MAX_SEGS then n = 0
nx! = branches(branch).nodes(nn).plane(n).x
ny! = branches(branch).nodes(nn).plane(n).y
nz! = branches(branch).nodes(nn).plane(n).z
getXY nx!, ny!, nz!, pnti(1,0), pnti(1,1)
n = p
nx! = branches(branch).nodes(nn).plane(n).x
ny! = branches(branch).nodes(nn).plane(n).y
nz! = branches(branch).nodes(nn).plane(n).z
getXY nx!, ny!, nz!, pnti(2,0), pnti(2,1)
refs = 4
else
nx! = branches(branch).root.x
ny! = branches(branch).root.y
nz! = branches(branch).root.z
getXY nx!, ny!, nz!, pnti(1,0), pnti(1,1)
refs = 3
end if
c = 6
if refs = 3 then
line (pnti(0,0), pnti(0,1)) - (pnti(1,0), pnti(1,1)), c
line (pnti(0,0), pnti(0,1)) - (pnti(3,0), pnti(3,1)), c
line (pnti(1,0), pnti(1,1)) - (pnti(3,0), pnti(3,1)), c
else
line (pnti(0,0), pnti(0,1)) - (pnti(1,0), pnti(1,1)), c
line (pnti(2,0), pnti(2,1)) - (pnti(1,0), pnti(1,1)), c
line (pnti(2,0), pnti(2,1)) - (pnti(3,0), pnti(3,1)), c
line (pnti(0,0), pnti(0,1)) - (pnti(3,0), pnti(3,1)), c
end if
next
next
next
First we grab 2 points on a plane perpendicular to our node. Next we get the same 2 points on the previous node for the bottom of the plane. If the previous node is the root we draw a cone instead of a cylinder to make the branch look like it's sticking inside the parent. refs holds the number of points on our polygon. Then at the end of the loop we render the polygon.
Here we have it. The finished tree skeleton. In the next section we'll look at making the leaf planes.
Our goal is to have a collection of planes that are always facing the camera that will hold our leaf texture. Basically all we need to know is where to place the center of the plane, and how large it should be. When it comes time to drawing the plane, setup a matrix that contains the opposite rotations of the camera, multiply the plane points by this matrix, then use GetXY to project the leaf plane coordinates to the screen.
To add some character to the trees the leaf planes are going to get larger when they are centered over a node the has multiple branches coming out of it to show a denser distribution of leaves in that area.
First is our leaf type. This holds the coordinates for the center of the leaf plane and a relative size for the plane.
type leafType
x as single
y as single
z as single
size as single
end type
Next we have a small addition to our node type. connected as integer. This will be used to keep track of the number of children a node has for determining leaf plane size. This is followed up by a small addition to the tree generation code where we add
branches(branch).nodes(node).connected = branches(branch).nodes(node).connected + 1
this increments the connected variable for the parent node in the event a leaf plane is generated here.
After the tree generation code we have the leaf plane generation code.
There is another do-loop sequence in this section. First we find a random branch and node on branch to attach to. Next we check to see if this point is in the upper half of the tree. Our last check is to make sure this node is not the location of any other leaf plane. Once we find a good location for our plane the loop is exited. Lastly we set the plane's location to the node coordinate and put a limit on the size of the plane.
for leaf = 0 to MAX_LEAVES
try = 0
do
try = try + 1
if try = 100 then exit do
branch = int(rnd * nBranches)
node = int(rnd * branches(branch).nNodes)
globalNode = branches(branch).nodes(node).globalNode
pass = 0
if globalNode > MAX_NODES / 2 and globalNode < MAX_NODES - 1 then pass = 1
for i = 0 to leaf - 1
ff = 0
if leaves(i).x = branches(branch).nodes(node).x then ff = ff + 1
if leaves(i).y = branches(branch).nodes(node).y then ff = ff + 1
if leaves(i).z = branches(branch).nodes(node).z then ff = ff + 1
if ff = 3 then pass = 0
next
if pass = 1 then exit do
loop
leaves(leaf).x = branches(branch).nodes(node).x
leaves(leaf).y = branches(branch).nodes(node).y
leaves(leaf).z = branches(branch).nodes(node).z
leaves(leaf).size = branches(branch).nodes(node).connected
if leaves(leaf).size > 2 then leaves(leaf).size = 2
next
Here is the final part of the tutorial. This section of code was probably the most tricky to write and I didn't quite understand the technique until i spent some time working with opengl. For this area of the code we need to have a routine to push and pop our matrix so that we can perform new rotations on it without losing our original camera setup. These new routines are pushMatrix () and popMatrix ().
The theory is quite simple. You're rotating opposite the direction of the camera first so that when you use getXY and multiply the camera rotation against the points you effectively don't rotate them at all and you just get the 3d perspective applied to the points and receive the 2d screen coordinates.
pnt(0,0) = -.5
pnt(0,1) = -.5
pnt(1,0) = -.5
pnt(1,1) = .5
pnt(2,0) = .5
pnt(2,1) = .5
pnt(3,0) = .5
pnt(3,1) = -.5
for leaf = 0 to MAX_LEAVES
pushMatrix
mIdentity
mRotate -xan!, xplane
mRotate -yan!, yplane
for p = 0 to 3
x0! = pnt(p,0) * leaves(leaf).size * leafscale!
y0! = pnt(p,1) * leaves(leaf).size * leafscale!
z0! = 0
pnt(p,2) = x0! * matrix(0) + y0! * matrix(3) + z0! * matrix(6) + leaves(leaf).x
pnt(p,3) = x0! * matrix(1) + y0! * matrix(4) + z0! * matrix(7) + leaves(leaf).y
pnt(p,4) = x0! * matrix(2) + y0! * matrix(5) + z0! * matrix(8) + leaves(leaf).z
next
popMatrix
for p = 0 to 3
getXY pnt(p,2), pnt(p,3), pnt(p,4), sx, sy
pnt(p,5) = sx
pnt(p,6) = sy
next
line (pnt(0,5), pnt(0,6)) - (pnt(1,5), pnt(1,6)), 2
line (pnt(0,5), pnt(0,6)) - (pnt(3,5), pnt(3,6)), 2
line (pnt(2,5), pnt(2,6)) - (pnt(1,5), pnt(1,6)), 2
line (pnt(2,5), pnt(2,6)) - (pnt(3,5), pnt(3,6)), 2
next
The pnt() array stores a set of x/y coordinates for our leaf square. This array will also store our screen coordinates for each point for drawing. The 2d coordinates are multiplied first by the size of the leaf plane which was dependant on the number of branches connected to the node. Next the point is multiplied by a scalar to control how large the planes end up being. I have this set to 3.5.
The plane points are rotated by the matrix and stored in a new section of the pnt array. We pop the matrix to restore our original camera matrix and use getXY to find the screen coordinates. Lastly we draw our plane.
That's all for our tree generator. In the last 2 sections we'll look at setting up an opengl scene and getting our tree to display properly inside it. If you have any questions about this tutorial, please drop me a line at syn9_at_dev9.net or leave a message on the forum at syn9.thingie.net and I'll get back to you as soon as I can.
