Swizec Teller - a geek with a hatswizec.com

    Using prime numbers to generate pretty trees

    Have you ever tried to generate a natural-ish looking tree? I did it for a coursework assignment and turns out it's both incredibly simple while being full of strange little twists.


    Generally the assignment was about manipulating 3D objects in OpenGL through user action. Otherwise known as: make a game, if it isn't a game, you're likely doing it wrong.

    Since we had the whole semester to work on it, I spent nearly all of it on a little piece of the whole puzzle that seemed the most interesting - Generating trees.

    Of course me and my partner both being avid dislikers of Java and Java sort of being what the class is taught in ... well we decided both to pick our favourite dialect of a functional language running on a JVM.

    Scala and Clojure.

    Fun ensued, but we actually did get it working and now half the project is in one language, half is in another and neither of us can read the other's code.

    While @hairyfotr took care of pretty much anything, I took it upon myself to generate the data for having pretty trees that are a bit random, but always manage to look like a beautiful beautiful tree.

    A night of hacking or three later, we had this:

    Not a tree isn't a treet
    Not a tree isn't a treet

    As you can see, it wasn't so much a tree as a bunch of weird random looking lines without any sort of order to them.

    Turns out not only was I calculating the tree all wrong and possibly even providing the incorrect data structure, @hairyfotr wasn't very adept at drawing what I did manage to generate either.

    But eventually after quite a bit of hacking, it got better. I learned a lot about linear algebra and not being an idiot, @hairyfotr learned how to traverse a tree data structure. In the end, everyone is happier and this is what the final trees look like ... I reckon they're pretty damn shiny.


    The generator

    In general the idea on how to generate trees is pretty simple. You take a vector representing the direction of a branch and its length. Then you move to the end of the branch, make N new directional vectors and give them a length. Then you simply repeat the process on every branch.

    Simple right?

    PS: lest your eyes glaze over, there's a sketch explaining all of this at the bottom

    It is. But it gets a bit complicated when you want this bunch of vectors to actually resemble something. The first concern is spacing child branches out evenly. You can think of this as a problem of evenly dividing a half sphere into N chunks.

    My first approach to this failed spectacularly. I tried to take the current branch as a normal to a plane, then drawing a vector between the end of the current branch and the made up point. This would give me a perpendicular vector to the original branch. Then all you need to do is rotate this perpendicular vector around X times, using the original branch as the rotation axis.

    This gives you an evenly sliced plane perched on top of the current branch. Then all you have to do is slant each new branch upwards by a certain angle and you're done. Since upwards can mean anything, you take it to mean the direction the original branch was pointing in.

    Turns out this approach is brilliant, except for that calculating a plane and points and such. That is just way too concrete and not abstract enough. It doesn't really work ... to make it work you'd need data outside of the "direction of current branch" scope.

    So what you do instead is this: take the current branch and make up a vector. It doesn't really matter what it is, as long as it's different from the branch. Then you calculate the cross product between the branch and the made up vector and voila. You have your first perpendicular child branch.

    Then you just do the whole rotation bit.

    This approach works surprisingly well. But it only ever gives you one tree and that doesn't do.

    So in order to get random trees that still look like trees I made use of a very simple trick. When choosing the angle by which to turn a branch upwards, just make the angle be chosen by some sort of weighted random choice. A bit of twiddling around and everything was nice and shiny. When everything conspires just right, you even get those long branches with others splitting off of them ... even though the tree itself thinks on every level all the branches split.

    It's just bloody elegant I tell you!

    And when doing the rotations around the original branch I add a little noise to the angles, just a few degrees so the spacing isn't always perfectly even.

    But, here comes the real beauty. When choosing how many new branches to create on every level, I just follow the progression of prime numbers. So, on the first level there are two branches, then three, then five and so on.

    I use a similar progression for calculating the length of every next branch. There it's actually 1-0.prime. It works marvelously.

    But this is quite a bit of text that probably doesn't make any sense to anyone. So here's a quick whiteboard sketch of what's going on:


    Next step in making it even awesomer is probably applying some randomness to branch lengths.

    You can also see the source for this on github.

    Enhanced by Zemanta

    Did you enjoy this article?

    Published on May 10th, 2011 in Business, Clojure, Java, Linear algebra, OpenGL, Plants, Tree, Uncategorized

    Learned something new?
    Want to become an expert?

    Here's how it works 👇

    Leave your email and I'll send you thoughtfully written emails every week about React, JavaScript, and your career. Lessons learned over 20 years in the industry working with companies ranging from tiny startups to Fortune5 behemoths.

    Join Swizec's Newsletter

    And get thoughtful letters 💌 on mindsets, tactics, and technical skills for your career. Real lessons from building production software. No bullshit.

    "Man, love your simple writing! Yours is the only newsletter I open and only blog that I give a fuck to read & scroll till the end. And wow always take away lessons with me. Inspiring! And very relatable. 👌"

    ~ Ashish Kumar

    Join over 14,000 engineers just like you already improving their careers with my letters, workshops, courses, and talks. ✌️

    Have a burning question that you think I can answer? I don't have all of the answers, but I have some! Hit me up on twitter or book a 30min ama for in-depth help.

    Ready to Stop copy pasting D3 examples and create data visualizations of your own?  Learn how to build scalable dataviz components your whole team can understand with React for Data Visualization

    Curious about Serverless and the modern backend? Check out Serverless Handbook, modern backend for the frontend engineer.

    Ready to learn how it all fits together and build a modern webapp from scratch? Learn how to launch a webapp and make your first 💰 on the side with ServerlessReact.Dev

    Want to brush up on your modern JavaScript syntax? Check out my interactive cheatsheet: es6cheatsheet.com

    By the way, just in case no one has told you it yet today: I love and appreciate you for who you are ❤️

    Created bySwizecwith ❤️