Fractals to Forests – Creating Reasonable 3D Timber with Three.js

Ever since I began programming on the younger age of 14, I’ve been fascinated by how code can be utilized to simulate the true world. In my sophomore 12 months of college, I challenged myself with attempting to give you an algorithm that might generate a 3D mannequin of a tree. It was a enjoyable experiment that yielded some fascinating outcomes, however in the end the code was relegated to the darkish recesses of my exterior drive.

Quick ahead a couple of years, I re-discovered that unique code and determined to port it to JavaScript (together with a couple of enhancements!) so I might run it on the net.

The result’s EZ-Tree, a web-based utility the place you may design your personal 3D tree and export it to GLB or PNG for use in your personal 2D/3D tasks. You could find the GitHub repo right here. EZ-Tree makes use of Three.js for 3D rendering, which is a well-liked library that sits on prime of WebGL.

On this article, I’ll be breaking down the algorithms I exploit to generate these timber, explaining how every half contributes to the ultimate tree mannequin.

What’s procedural era?

First, it would assist to grasp precisely what procedural era is.

Procedural era is solely creating “one thing” from a set of mathematical guidelines. Utilizing a tree as our instance, one of many first issues we observe is a tree has a trunk which splits into a number of branches, and every of these branches break up into a number of branches, and so forth, lastly terminating in a set of leaves. From a math/laptop science perspective, we might mannequin this as a recursive course of.

Let’s hold going with our instance.

If we have a look at a single department of a tree in nature, we are able to discover a couple of issues

• A department has a smaller radius and size than the department it originates from.
• The thickness of the department tapers in direction of its finish.
• Relying on the kind of tree, branches may be straight or twist and switch in all instructions.
• Branches are inclined to develop in direction of daylight.
• As branches lengthen out horizontally from the tree, gravity tends to tug them down in direction of the bottom. The quantity of pressure can relies on the thickness of the branches and variety of leaves.

All of those observations may be codified into their very own mathematical guidelines. We are able to then mix all of guidelines collectively to create one thing that appears like a tree department. It is a idea referred to as emergent habits, the place many easy guidelines may be mixed collectively to create one thing extra complicated than the person elements.

L-Techniques

One space of arithmetic that makes an attempt to formalize this sort of pure course of is named Lindenmayer techniques, or extra generally L-systems. L-Techniques are a easy method to create complicated patterns, usually used for simulating the expansion of vegetation, timber, and different pure phenomena. They begin with an preliminary string (referred to as an axiom) and apply a algorithm repeatedly to rewrite the string. These guidelines outline how every a part of the string transforms into a brand new sequence. The ensuing string can then be became visible patterns utilizing drawing directions.

Whereas the code I’m about to point out you doesn’t use L-systems (I merely wasn’t conscious of them on the time), the ideas are very related and each are based mostly on recursive processes.

Sufficient idea, let’s dive into the code!

The Tree Era Course of

The tree era course of begins with the generate() methodology. This methodology initializes the information constructions for storing the department and leaf geometry, units up the random quantity generator (RNG), and begins the method by including the trunk to the department queue.

// The place to begin for the tree era course of
generate() {
  // Initialize geometry information
  this.branches = { };
  this.leaves = { };

  // Initialize RNG
  this.rng = new RNG(this.choices.seed);

  // Begin with the trunk
  this.branchQueue.push(
    new Department(
      new THREE.Vector3(),              // Origin
      new THREE.Euler(),                // Orientation
      this.choices.department.size[0],    // Size
      this.choices.department.radius[0],    // Radius
      0,                                // Recursion degree
      this.choices.department.sections[0],  // # of sections
      this.choices.department.segments[0],  // # of segments
    ),
  );

  // Course of branches within the queue
  whereas (this.branchQueue.size > 0) {
    const department = this.branchQueue.shift();
    this.generateBranch(department);
  }
}

Department Information Construction

The Department information construction holds the enter parameters required for producing a department. Every department is represented utilizing the next parameters:

• origin – Defines the place to begin of the department in 3D house (x, y, z).
• orientation – Specifies the rotation of the department utilizing Euler angles (pitch, yaw, roll).
• size – The general size of the department from base to tip
• radius – Units the thickness of the department
• degree – Signifies the depth of recursion, with the trunk beging at degree 0.
• sectionCount – Defines what number of occasions trunk is subdivided alongside its size.
• segmentCount – Controls the smoothness by setting the variety of segments across the trunk’s circumference.

Understanding the Department Queue

The branchQueue is a vital a part of the tree era course of. It holds the entire branches ready to be generated. The primary department is pulled from the queue and its geometry is generated. We then recursively generate the Department objects for the kid branches and add them to the queue to be processed in a while. This course of continues till the queue is exhausted.

Producing Branches

The generateBranch() perform is the center and soul of the tree era course of. This incorporates the entire guidelines wanted to create the geometry for a single department based mostly on the inputs contained within the Department object.

Let’s check out the important thing elements of this perform.

A Primer on 3D Geometry

Earlier than we are able to generate a tree department, we first want to grasp how the 3D geometry is saved in Three.js.

When representing a 3D object, we usually accomplish that utilizing listed geometry, which optimizes rendering by lowering redundancy. The geometry consists of 4 foremost parts:

1. Vertices – A listing of factors in 3D house that outline the form of the thing. Every vertex is represented by a THREE.Vector3 containing its x, y, and z coordinates. These factors kind the “constructing blocks” of the geometry.
2. Indices – A listing of integers that outline how the vertices are related to kind faces (usually triangles). As an alternative of storing duplicate vertices for every face, indices reference the prevailing vertices, considerably lowering reminiscence utilization. For instance, three indices [0, 1, 2] kind a single triangle utilizing the primary, second, and third vertices within the vertex listing.
3. Normals – A “regular” vector describes how the vertex is oriented in 3D house; mainly, which method the floor is pointing. Normals are essential for lighting calculations, as they decide how gentle interacts with the floor, creating life like shading and highlights.
4. UV Coordinates – A set of 2D coordinates that map textures onto the geometry. Every vertex is assigned a pair of UV values between 0.0 and 1.0 that decide how a picture or materials wraps across the floor of the thing. These coordinates permit textures to align appropriately with the geometry’s form.

The generateBranch() perform generates the department vertices, indices, normals and UV coordinates part by part and appends the outcomes to their respective arrays.

this.branches = {
  verts: [],
  indices: [],
  normals: [],
  uvs: []
};

As soon as the entire geometry has been generated, the arrays are mixed collectively right into a mesh which is the entire illustration of the tree geometry plus its materials.

Trying on the above picture, we are able to see how the department consists of 10 particular person sections alongside its size, with every part having 5 sides (or segments). We are able to tune specify the variety of sections and segments of the branches to manage the element of the ultimate mannequin. Larger values produce a smoother mannequin on the expense of efficiency.

With that out of the best way, let’s dive into the tree era algorithms!

Initialization

let sectionOrigin = department.origin.clone();
let sectionOrientation = department.orientation.clone();
let sectionLength = department.size / department.sectionCount;

let sections = [];

for (let i = 0; i <= department.sectionCount; i++) {
  // Calculate part radius
  // Construct part geometry
}

We start by initialize the origin, orientation and size of the department. Subsequent, we outline an array that can retailer the department sections. Lastly, we loop over every part and generate its geometry information. The sectionOrigin and sectionOrientation variables are up to date as we loop over every part.

Department Part Radius

To calculate the part’s radius, we begin with the general radius of the department. If it’s the final part of the department, we set the radius to successfully zero since we wish our tree branches to finish in some extent. For all different sections, we compute the how a lot to taper the department based mostly on the part’s place alongside the size of the department (as we transfer nearer to the top, the quantity of taper will increase) and multiply that by the earlier part radius.

let sectionRadius = department.radius;

// If final part, set radius to successfully zero
if (i === department.sectionCount) {
  sectionRadius = 0.001;
} else {
  sectionRadius *=
    1 - this.choices.department.taper[branch.level] * (i / department.sectionCount);
}

Construct Part Geometry

We now have sufficient info to construct the part geometry That is the place the maths begins to get a bit complicated! All you could know is that we’re utilizing the beforehand computed part origin, orientation and radius to create every vertex, regular and UV coordinate.

// Create the segments that make up this part.
for (let j = 0; j < department.segmentCount; j++) {
  let angle = (2.0 * Math.PI * j) / department.segmentCount;

  const vertex = new THREE.Vector3(Math.cos(angle), 0, Math.sin(angle))
    .multiplyScalar(sectionRadius)
    .applyEuler(sectionOrientation)
    .add(sectionOrigin);

  const regular = new THREE.Vector3(Math.cos(angle), 0, Math.sin(angle))
    .applyEuler(sectionOrientation)
    .normalize();

  const uv = new THREE.Vector2(
    j / department.segmentCount,
    (i % 2 === 0) ? 0 : 1,
  );

  this.branches.verts.push(...Object.values(vertex));
  this.branches.normals.push(...Object.values(regular));
  this.branches.uvs.push(...Object.values(uv));
}

sections.push({
  origin: sectionOrigin.clone(),
  orientation: sectionOrientation.clone(),
  radius: sectionRadius,
});

And that’s the way you create the geometry for a single department!

This alone doesn’t make for a really fascinating tree, nonetheless. A lot of what makes a procedurally generated tree look good is the foundations round how sections are oriented relative to at least one one other and the general department placement.

Let’s have a look at two parameters we use to make branches look extra fascinating.

Gnarly, Dude!

One among my favourite parameters is gnarliness. This controls how a lot a department twists and turns. In my view, this has the most important influence on making a tree really feel “alive” as an alternative of sterile and static.

Gnarliness may be expressed mathematically by controlling how a lot the orientation of 1 part deviates from the earlier part. These distinction accumulate over the size of the tree department to provide some fascinating outcomes.

const gnarliness =
  Math.max(1, 1 / Math.sqrt(sectionRadius)) *
  this.choices.department.gnarliness[branch.level];

sectionOrientation.x += this.rng.random(gnarliness, -gnarliness);
sectionOrientation.z += this.rng.random(gnarliness, -gnarliness);

Trying on the expression above, we are able to see that the gnarliness is inversely proportional to the radius of the department. This displays how timber behave in nature; smaller branches have a tendency to curve and twist greater than bigger branches.

We generate a random tilt angle inside the vary [-gnarliness, gnarliness] after which apply that to the orientation of the following part.

Use the Power!

The subsequent parameter is the development pressure, which fashions how timber develop in direction of the daylight to maximise photosynthesis (it can be used to mannequin gravity appearing on the branches, pulling them in direction of the bottom). That is particularly helpful for modeling timber like aspen timber, which are inclined to have branches that develop straight up as an alternative of away from the tree.

We outline a development route (which you’ll be able to consider as a ray pointing in direction of the solar) and a development energy issue. Every part is rotated by a tiny bit to align itself alongside the expansion route. The quantity it’s rotated is proportional to the energy issue and inversely proportional to the department radius, so smaller branches are affected extra.

const qSection = new THREE.Quaternion().setFromEuler(sectionOrientation);

const qTwist = new THREE.Quaternion().setFromAxisAngle(
  new THREE.Vector3(0, 1, 0),
  this.choices.department.twist[branch.level],
);

const qForce = new THREE.Quaternion().setFromUnitVectors(
  new THREE.Vector3(0, 1, 0),
  new THREE.Vector3().copy(this.choices.department.pressure.route),
);

qSection.multiply(qTwist);
qSection.rotateTowards(
  qForce,
  this.choices.department.pressure.energy / sectionRadius,
);

sectionOrientation.setFromQuaternion(qSection);

The above code utilizies quaternions to symbolize rotations, which keep away from some points that happen with the extra generally identified Euler angles (pitch, yaw, roll). Quaternions are past the scope of this text, however simply know they’re a distinct method to symbolize how one thing is oriented in house.

Further Parameters

Gnarliness and Development Power aren’t the one tunable parameters out there. Right here’s an inventory of different parameters that may be tuned to manage the expansion of the tree

• angle – This parameter units the angle at which baby branches develop relative to their mother or father department. By adjusting this worth, you may management whether or not the kid branches develop steeply upward, virtually parallel to the mother or father department, or fan outward at vast angles, mimicking several types of timber.
• kids – This controls the variety of baby branches which can be generated from a single mother or father department. Rising this worth leads to fuller, extra complicated timber with dense branching, whereas lowering it creates sparse, minimalist tree constructions.
• begin – This parameter determines how far alongside a mother or father department the kid branches start to develop. A low worth causes the kid branches to sprout nearer to the bottom of the mother or father department, whereas the next worth makes them seem nearer to the tip, creating totally different development patterns.
• twist – Twist applies a rotational adjustment to the geometry of the department round its axis. By modifying this worth, you may introduce a spiral impact, which provides a dynamic, pure look to the branches, mimicking timber with twisted or curved development patterns.

Are you able to consider any others you’d add?

Producing Youngster Branches

After the department geometry has been generated, it’s time to generate its baby branches.

if (department.degree === this.choices.department.ranges) {
  this.generateLeaves(sections);
} else if (department.degree < this.choices.department.ranges) {
  this.generateChildBranches(
    this.choices.department.kids[branch.level],
    department.degree + 1,
    sections);
}

If we’re on the closing degree of recursion, then we generate leaves as an alternative of branches. We’ll have a look at the leaf era course of in a bit, however it actually doesn’t differ a lot from how we generate baby branches.

If we aren’t on the closing degree of recursion, we name the generateChildBranches() perform.

generateChildBranches(rely, degree, sections) {
  for (let i = 0; i < rely; i++) {

    // Calculate the kid department parameters...

    this.branchQueue.push(
      new Department(
        childBranchOrigin,
        childBranchOrientation,
        childBranchLength,
        childBranchRadius,
        degree,
        this.choices.department.sections[level],
        this.choices.department.segments[level],
      ),
    );
  }
}

This perform loops over every baby department, generates the values must populate the Department information construction, and appends the consequence to the branchQueue, which is able to then be processed by the generateBranch() perform which we have now mentioned within the earlier part.

The generateChildBranches() perform requires a couple of arguments

• rely – The variety of baby branches to generate
• degree – The present degree of recursion, so we all know if we have to name generateChildBranches() once more or if we must always cease right here.
• sections – That is an array of part information for the mother or father department. This incorporates the origins and orientations of the sections, which might be used to assist decide the place to put the kid branches.

Calculating the Youngster Department Parameters

Let’s break down how every of the kid department parameters are calculated.

Origin

// Decide how far alongside the size of the mother or father department the kid
// department ought to originate from (0 to 1)
let childBranchStart = this.rng.random(1.0, this.choices.department.begin[level]);

// Discover which sections are on both facet of the kid department origin level
// so we are able to decide the origin, orientation and radius of the department
const sectionIndex = Math.ground(childBranchStart * (sections.size - 1));
let sectionA, sectionB;
sectionA = sections[sectionIndex];
if (sectionIndex === sections.size - 1) {
  sectionB = sectionA;
} else {
  sectionB = sections[sectionIndex + 1];
}

// Discover normalized distance from part A to part B (0 to 1)
const alpha =
  (childBranchStart - sectionIndex / (sections.size - 1)) /
  (1 / (sections.size - 1));

// Linearly interpolate origin from part A to part B
const childBranchOrigin = new THREE.Vector3().lerpVectors(
  sectionA.origin,
  sectionB.origin,
  alpha,
);

This one isn’t as tough because it seems. When figuring out the place to put a department, we first generate a random quantity between 0.0 and 1.0 that tells us the place alongside the size of the mother or father department we must always place the kid department. We then discover the sections on both facet of that time and interpolate between their origin factors to seek out the origin level of the kid department.

Radius

const childBranchRadius =
  this.choices.department.radius[level] *
  ((1 - alpha) * sectionA.radius + alpha * sectionB.radius);

The radius follows the identical logic because the origin. We have a look at the radius of the sections on both facet of the kid department and interpolate these values to get the kid department radius.

Orientation

// Linearlly interpolate the orientation
const qA = new THREE.Quaternion().setFromEuler(sectionA.orientation);
const qB = new THREE.Quaternion().setFromEuler(sectionB.orientation);
const parentOrientation = new THREE.Euler().setFromQuaternion(
  qB.slerp(qA, alpha),
);

// Calculate the angle offset from the mother or father department and the radial angle
const radialAngle = 2.0 * Math.PI * (radialOffset + i / rely);
const q1 = new THREE.Quaternion().setFromAxisAngle(
  new THREE.Vector3(1, 0, 0),
  this.choices.department.angle[level] / (180 / Math.PI),
);
const q2 = new THREE.Quaternion().setFromAxisAngle(
  new THREE.Vector3(0, 1, 0),
  radialAngle,
);
const q3 = new THREE.Quaternion().setFromEuler(parentOrientation);

const childBranchOrientation = new THREE.Euler().setFromQuaternion(
  q3.multiply(q2.multiply(q1)),
);

Quaternions strike once more! In figuring out the kid department orientation, there are two angles we have to take into account

• The radial angle across the mother or father department. We would like baby branches to be evenly distributed across the circumference of a department so that they aren’t all pointing in a single route.
• The angle between the kid department and mother or father department. This angle is parameterized and may be tuned to get the sure impact we’re in search of.

Each of those angles are mixed together with the mother or father department orientation to find out the ultimate orientation of the department in 3D house.

Size

let childBranchLength = this.choices.department.size[level];

Lastly, the size of the department is set by a parameter set on the UI.

As soon as all of those values are calculated, we have now sufficient info wanted to generate the kid department. We repeat this course of for every baby department till all of the baby branches have been generated. The branchQueue is now stuffed with the entire baby department information which might be processed in sequence and handed to the generateBranch() perform.

Producing Leaves

The leaf era course of is sort of an identical to the kid department era course of. The first distinction is that the leaves are rendered as a texture utilized to a quad (i.e., rectangular aircraft), so as an alternative of producing a department, we generate a quad and place and orient it in the identical method as a department.

So as to enhance the fullness of the foliage and make the leaves seen from all angles, we use two quads as an alternative of 1 an orient them perpendicular to one another.

There are a number of parameters for controlling the looks of the leaves

• sort – I discovered a number of totally different leaf textures so a wide range of differing kinds may be generated
• measurement – Controls the general measurement of the leaf quad to make the leaves bigger or smaller
• rely – The variety of leaves to generate per department
• angle – The angle of the leaf relative to the department (very like the department angle parameter)

Atmosphere Design

A good looking tree wants an attractive residence, which is why I put a big quantity of effort into creating a sensible surroundings for EZ-Tree. Whereas not the subject of this text, I believed I might spotlight some environmental options I added to make the scene really feel extra alive.

If you wish to be taught extra about how I created the surroundings, the hyperlink to the supply code is supplied and the highest/backside of this text.

Floor

Step one is including in a floor aircraft. I used a clean noise perform to have it range between a mud texture and grass texture. When modeling something from nature, it’s at all times essential to concentrate to the imperfections; these are what make a scene really feel natural and life like vs. sterile and pretend.

Clouds

Subsequent, I added in some clouds. The clouds are literally simply one other noise texture (see a sample right here?) utilized to an enormous quad which I’ve positioned above the scene. To make the clouds really feel “alive”, the feel is assorted over time to present the looks of shifting clouds. I selected a really muted, barely overcast sky to not distract from the tree which is the main target of the scene.

Foliage and Rocks

To make the bottom extra fascinating, I added in some grass, rocks and flowers. The grass is extra dense close to the tree and fewer dense additional away from the tree to enhance efficiency. I selected a rock fashions with some moss on them so that they blended into the bottom higher. The flowers additionally assist break up the ocean of inexperienced with splotches of colours.

Forest

Our tree feels a bit lonely, so on app load I generate 100 hundred timber (pulling from the listing of presets) and place them round the principle tree.

Wind

Nature is at all times in fixed motion, so it’s essential to mannequin that in our timber and grass. I wrote customized shaders that animate the geometry of the grass, branches and leaves. I outline a wind route after which add collectively a number of sine features of various frequencies and amplitudes after which apply that to every vertex within the geometry to get the specified impact.

Under is an excerpt of GLSL shader code that controls the wind offset utilized to the vertex positions.

vec4 mvPosition = vec4(reworked, 1.0);

float windOffset = 2.0 * 3.14 * simplex3(mvPosition.xyz / uWindScale);
vec3 windSway = uv.y * uWindStrength * (
  0.5 * sin(uTime * uWindFrequency + windOffset) +
  0.3 * sin(2.0 * uTime * uWindFrequency + 1.3 * windOffset) +
  0.2 * sin(5.0 * uTime * uWindFrequency + 1.5 * windOffset)
);
mvPosition.xyz += windSway;

mvPosition = modelViewMatrix * mvPosition;
gl_Position = projectionMatrix * mvPosition;

Conclusion

I hope you loved this breakdown of of my procedural tree generator! Procedural era is a improbable discipline to discover because it permits you to mix each artwork and science to create one thing stunning and helpful.

When you’d prefer to be taught extra about 3D internet growth, be sure you try my YouTube channel the place I put up movies on Three.js, React Three Fiber, recreation growth and extra!

I will even be releasing my very own course web site within the close to future—Three.js Roadmap. The course might be arrange as a set of small, unbiased studying modules, so reasonably than shopping for a whole course, you solely pay for the teachings you have an interest in.

Be a part of the waitlist now to obtain 30% off your first buy!