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.

    Onf49

    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.

    NlQkb
    Tree
    VFX7p
    Tree
    avoQP
    Tree
    Onf49
    Tree
    csDVD
    Tree

    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:

    83sOz
    Sketch

    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?
    Read more Software Engineering Lessons from Production

    I write articles with real insight into the career and skills of a modern software engineer. "Raw and honest from the heart!" as one reader described them. Fueled by lessons learned over 20 years of building production code for side-projects, small businesses, and hyper growth startups. Both successful and not.

    Subscribe below 👇

    Software Engineering Lessons from Production

    Join Swizec's Newsletter and get insightful emails 💌 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 15,883+ engineers learning lessons from my "raw and honest from the heart" emails.

    ⭐️⭐️⭐️⭐️✨
    4.5 stars average rating

    Have a burning question that you think I can answer? Hit me up on twitter and I'll do my best.

    Who am I and who do I help? I'm Swizec Teller and I turn coders into engineers with "Raw and honest from the heart!" writing. No bullshit. Real insights into the career and skills of a modern software engineer.

    Want to become a true senior engineer? Take ownership, have autonomy, and be a force multiplier on your team. The Senior Engineer Mindset ebook can help 👉 swizec.com/senior-mindset. These are the shifts in mindset that unlocked my career.

    Curious about Serverless and the modern backend? Check out Serverless Handbook, for frontend engineers 👉 ServerlessHandbook.dev

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

    Want to get my best emails on JavaScript, React, Serverless, Fullstack Web, or Indie Hacking? Check out swizec.com/collections

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

    Did someone amazing share this letter with you? Wonderful! You can sign up for my weekly letters for software engineers on their path to greatness, here: swizec.com/blog

    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 by Swizec with ❤️