by Dan Wyszynski

How to visualize random distribution algorithms in Swift and ARKit

https://xkcd.com/221/

A tree in the forest

I was recently working on a prototype where I needed to place a large amount of objects in 3D space. This was an AR project, and the thought was that these objects would be placed around you in a random fashion, scattering around you as they dropped in from the sky.

This brings up a few problems. First, we don’t know the current surroundings of the user, so we have to limit the radius of the dropped items to something that we can configure based on location or other factors.

Next, we know that built-in random generators are not very random unless specific precautions are taken.

Lastly, generating points with random generators, no matter how random, results in clustering, where many of the generated points can fall in close areas to one another, and leave you with spots that are bald of any points. And nobody wants bald spots: trust me, I know.

There are a number of ways to accomplish random equal distribution. Like any developer worth his salt, I found a couple which have simple implementations that work well for our purpose. Let’s examine each one, and implement them in Swift using ARKit and SceneKit.

Roll them dice!

Before we get to the “good” algorithms, we should look to see what we get by using just random numbers to place our points. In doing this, we’ll get our app put together and use it to test out the other implementations in the same form.

Let’s create our app and get some of the basic stuff in place. Open up Xcode and create a new project using the Augmented Reality App template. Build and run the app to make sure everything is working and you see the default ship appear in front of your phone when running the app.

Next, we’re going set up our project like we did for the first tutorial in my ARKit series. Follow the steps in that tutorial, with the one difference being the name of the scene file. Instead of naming it HoverScene, we’ll name it MainScene instead. Add the render delegate as described in the tutorial, and follow the Extra Credits section where the tap gesture recognizer is created.

At this point the project is almost ready, but we don’t have (nor need) the addSphere method that is referenced in that tutorial. Instead, we will begin creating our algorithm generators.

Create a file called PointGenerator.swift. In here we’ll put several iterations of our algorithms. Let’s begin with the random number point generator. We’ll create a protocol that our algorithms will adhere to, making it easy to switch between algorithms in our source later on.

Our protocol is simple. Given a number of points to generate and a width and length to limit the points to, give back an array of points:

Our RandomPointGenerator will adhere to this class and output our first set of results:

The code here is simple. We iterate and create points that lie within the width and length limits, placing points on either side of the midpoint of those limits. We add the created points to an array then simply return the points.

Create a class called Visualizer derived from SCNNode. This class will serve as the container that holds the objects that we’ll place in the world to visualize the point set. For the moment, we’re going to create small spheres at each point generated by our algorithms.

This is what our class should look like:

Alright, now we’re ready to create our points. Let’s go back to our MainScene class and add a method called createPointField, which takes in a SCNVector3 position:

We’re going to call this from our ViewController when we tap on the screen. Let’s go to our didTapScreen method and make the part where we previously created a sphere (in that first tutorial) look like the following:

Build and run, and we now have our first algorithm implemented.

Random placement of points. Not great.

Notice how the spheres are clustered in certain spots. This is exactly what we want to avoid.

I won’t get into detailed descriptions of each algorithm, but I’ll provide links to the sites that I found informative and gave me the inspiration to implement in Swift and AR.

Poisson Sampling and Mitchell’s best-candidate

What we need as an alternative to the random number generator way is an algorithm which returns a set of points that are close to each other, but no closer than some specified minimum distance. That’s where Poisson-disc sampling comes into the picture. There are several ways of implementing the Poisson-disc algorithm. The one we’re going to be implementing in our code is called Mitchell’s best-candidate algorithm. It’s easy to implement and runs fast.

The idea behind the algorithm is to place down points, and as you place them, check whether they meet the requirement of being at least the minimum distance away from the points already placed. To do this, you sample the point as you place it, by looking at the distance that nearby points have. If there are no points within the minimum requirement, place the new point, otherwise, try to find another location. You can read more about the algorithm here.

To implement, we’re going to create another implementation of our PointGenerator protocol:

Let’s head back to our MainScene class, comment out the random generator lines, and add these new lines in:

Run the app again, and let’s look at our results.

Poisson-disc using Mitchell’s best candidate method

Much better! There are no big clusters or barren areas. This is now something we can use to place items in the world. Other uses for this algorithm include things like dynamically generating textures at runtime or noise generators.

We have what we need with this implementation, and we’re going to make use of it later. But what if we wanted to have something a bit different, where we need uniform distribution within a circular boundary? This is where the Sunflower Seed algorithm comes in.

Extra Credit

Sunflower Seed Algorithm

Throughout history, we have found mathematical patterns in nature. One of the interesting features in many of these patterns that are mimicked in nature is the existence of the Fibonacci sequence in plants. These features manifest themselves in spiral patterns in leaves, seeds and petal arrangements. The study of these patterns is called Phyllotaxis. The following algorithm implements the mathematical model of one of these spirals. You can find more info here and here.

Let’s go back to our PointGenerator file and create our new implementation:

You’ll notice here that we are ignoring the width and height parameters passed in. This is because instead of constraining the points to a region, we will be evenly distributing the points in a spiral fashion until we run out of points.

Changing the alpha in the parameter passed in to the sunflower method controls the granularity of the points at the edge of the boundary. That is, we can make the boundary smoother or rougher by controlling the point distribution. The above code uses an alpha of 2, which is on the high side, and results in a more even boundary.

Let’s go to our MainScene again, and comment out the previous algorithm. Let’s add in a call to get our Sunflower pattern generating points:

Let’s run our app again and see what we get.

Sunflower Algorithm

As you can see, we have a pattern that mimics the way sunflowers hold their seeds. There is also an interesting variation we can apply to the algorithm, as detailed in one of the comments in this Stack Overflow question.

By changing the theta to a bearing, the commenter turned the algorithm into a geodesic formation.

Change the theta line in our code to the following:

Let’s run our algorithm again and see what it looks like.

Sunflower Algorithm with spiral pattern

Cool! Now we have the pattern as spirals.

Speaking of spirals, let’s check out one last algorithm.

The Vogel Spiral

Here we have another closely related algorithm which also uses a Fibonacci sequence and the Golden Angle. You can read more about the Vogel Spiral here and here.

Let’s implement it, and then we’ll tweak it to see how it influences the results.

In our PointGenerator class, add our implementation of this algorithm.

This algorithm, like the Sunflower Seed algorithm, also ignores the width and height parameters.

Let’s replace the previous algorithm with our new calls.

Let’s give that a run and see what we get.

Vogel Spiral

Nice! Now, let’s try different variations of this algorithm. By changing the formula, we can get different spiral formations. Change the it declaration to the following line:

Run that and check out what we get.

Vogel spiral, looking like the Sunflower

That spiral now looks like a flipped version of our Sunflower spiral with the updated theta. Interesting!

Let’s try it with the following formula:

Vogel spirals

Similar to the first algorithm, but the spirals are separated. Very cool stuff!

We’ve now run through 4 different algorithms, including the not-very-good strictly random number placement. Each one of these has a place in our toolbox, though, and they can be used to fulfill a variety of needs.

Extra Credit, Part Two

It wouldn’t be an article of mine if we didn’t do something cool with what we just learned, now would it?

Download some tree models from a 3D model store like Sketchfab or Turbosquid. Convert them to Collada (DAE) format as needed and add them to your project. You may need to resize them to be the proper scale when putting them in your scene, but you’ll know when you go to use them. Be sure to use a low poly model since we are talking about instantiating dozens and even hundreds of object instances.

Let’s make a Tree class that derives from SceneObject (we created this class back in our previous tutorial). We’ll make it load a random tree from the ones we have added into our app. We make use of the random convenience function we also added in a previous tutorial.

Here’s what my Tree class looks like:

Let’s use the Mitchell algorithm and bring down the number of models (points) we want to generate to 60. Depending on the amount of polygons in your models, this might be too large. I started with a different set of models and it took a while to place 20 models. Start low and work your way up. For the models I used I could go higher, but 60 was dense enough.

In our Visualizer code, let’s change our Tree creation to animate the scaling up a bit.

In my case, with the models I used, I had to scale them down a bit to get them to a reasonable size which is where that 0.45 comes from. I also lowered the position a bit so that they lay on the ground plane. You can adjust these numbers to whatever fits your situation.

Build and run, and now we have a happy little forest created with almost no effort.

Our happy little forest

Hope you enjoyed this little experiment. Feel free to show off your work in the comment section!

Daniel Wyszynski is a developer who’s worked on more platforms and languages than he cares to admit to. He believes in building products that create memorable user experiences. To Dan, the users are first, the platforms are second. Follow Dan on Medium or Twitter to hear more from him. Also check out the s23NYC: Engineering blog, where a lot of great content by Nike’s Digital Innovation team gets posted.

Author’s Note: Views are my own and do not necessarily represent those of my employer