A while ago I wrote a custom scattering script that is capable of placing objects in the area that is enclosed by a spline. I want to share with you as it was an interesting set of techniques that are used together. This is intended to be language independent and should mostly teach you how you can approach such a tool, as well as give you some resources to understand the different aspects of it better.
Step 1: The spline
I am assuming that wherever you implement this, your environment already has a spline implementation of some sorts. All we need is that the user can nicely place create points within the viewport. For this approach, it doesn’t need to be closed. The only implemented function that is vital is for us to step along the spline so we can get
Step 2: Some Data wrangling
Here we get to the interesting part. The first and probably most important thing is that you design your scattering algorithm with an upper hard limit. For now I’ll choose 5000 but it’s up to your use case and your engine. Just make sure the user can’t accidentally add a 0 too many and crash it ( or you yourself when testing).
const int INSTANCING_LIMIT = 5000;
Next up, we’ll implement is a simplified density approach. Let’s assume the longer the spline, the more instances we want to create. For that I did some tests in my environment and 50 instances per meter of spline seemed pretty good. Very dense but not excessive. This will be our maximum.
const float DENSITY_FACTOR = 50; // the target density is a value between 0 and 1, determined by the user input 1 -> 100 % dense int target_count = Spline.GetLength() * DENSITY_FACTOR * Clamp(targetDensity, 0.f, 1.f);
Now we already know how many objects we’ll place. We should now use that and make sure it’s handled properly. This includes making sure that not a bunch of code is ran without any instances to be placed and not too many.
if( target_count == 0)
{
// telling whoever called this, it was successful, even though nothing happened
Log("The Scatterer didn't place any objects. Check your inputs and the spline length. This tool doesn't support a spline short than X.")
return true;
}
else if(target_count > INSTANCING_LIMIT )
{
LogFormat("The Scatterer intended to place %i but only supports to place %i. If you think that needs adjusting, talk to your tools developer.",target_count,INSTANCING_LIMIT);
target_count = INSTANCING_LIMIT;
}
Step 3 Creating Triangles
Now we’re finally leaving the boring data preparations and create something quite interesting. The problem we need to solve is: how are we gonna scatter points within an n-gon? I chose one of the most classic game development solutions, let’s triangulate that! Having triangles makes the whole calculations way simpler and overall keeps the complexity to a degree that we could even have real-time updates with our tool.
For that we will step along the spline to figure out all the outer positions that we wanna use to create triangles. Like that we will approximate the shape. If you go very low on the SPLINE_STEP, you will get closer and closer to the actual shape but increase the work load quite a bit. To get the tip of the triangle, we will compute the center of all points that we’re finding when stepping along the spline.
Very irregular shapes won’t work so well with this approach, maybe dividing the spline then into several shapes could be a good way in case this doesn’t work for you.
float targetLength = 0;
const float SPLINE_STEP = 0.05;
Vector[] ngonPositions;
Vector center;
// If not reached the end
while (targetLength < 1.0f)
{
Vector currentPosition = spline.Sample(targetLength);
ngonPositions.Add(currentPosition);
center += currentPosition;
targetLength += SPLINE_STEP;
}
// at last let's get the center of all positions after having them added up together, now we need to divide through the overall amount
center /= ngonPositions.Length();
Now let’s create some actual triangles. For that we go through the spline positions we found, use the current, next and central position and put them together. The Triangle struct is nothing else than 3 Vectors coming together in a convenient way.
Triangle[] triangles;
for(int i = 0; i < ngonPositions.Length(); i++)
{
int nextIndex = (i + 1) % ngonPositions.Length();
triangles.Add(Triangle(center, ngonPositions[i], ngonPositions[next_index]));
}
Step 4 Scattering Points
Now we’re getting to the real fun part, scattering points! Here’s a easy to understand tutorial ( that even has some example code) that hopefully helps you understanding the maths behind the scattering of points in triangles:
https://blogs.sas.com/content/iml/2020/10/19/random-points-in-triangle.html
// this will be the index of the next triangle that we are placing a point in
int nextIndex = 0
// all the scattered points in one structure
Vector[] finalPoints;
// we're creating exactly as many points as requested
while(finalPoints.size() < target_count)
{
Triangle& triangle = triangles[nextIndex];
Vector sideA = triangle.m_B - triangle.m_A;
Vector sideB = triangle.m_C - triangle.m_A;
// implement two seeded random generators, I usually use some hashing functions that accept a 3D seed
// just make sure they return values between 0 and 1 and if you need put a global Seed so you can additionally change outcome
float r1 = GetRandomNumberA(triangle.m_B);
float r2 = GetRandomNumberB(triangle.m_B);
// In order for the algorithm to place the random point inside the triangle, this needs to be lower than 1
// but to still make use of the values, let's just minus one them
if (r1 + r2 > 1)
{
r1 = 1 - r1;
r2 = 1 - r2;
}
// the bread and butter of the function, this will give you a random point within a triangle
Vector random_point = (sideA * r1 + sideB * r2) + triangle.m_A;
finalPoints.Add(random_point);
// making the next index random so we never get patterns
nextIndex = r2 * triangles.size();
}
At this point ( no pun intended), I could stop and tell you: congratulations, you have a whole bunch of points! Use them well! And it would totally work. But it seems almost too simple and too random. So let’s add one more aspect of it: minimum distance between points!
Step 5 Let’s add some filtering
For the filtering, one of the most famous and straight forward algorithms is the poisson disk. This page here gives you a good idea about what that actually is and shows some examples.
http://devmag.org.za/2009/05/03/poisson-disk-sampling/
In short, we create a 2D or 3D grid and based on the diameter of the circle / sphere around a cell, we start at a random cell, use the diameter to determine what neighbours are too close and get rid of them. This allows for filtering of ‘illegal’ cells based on the given minimum distance. In my example I used a 3D grid.
// let's create a convenient way to compute the cell of a point in a 3D coordinate system
IntVector GetGridCell(Vector point, float gridCellSize)
{
return IntVector(point.x / gridCellSize, point.y / gridCellSize, point.z / gridCellSize);
}
// Return all 26 neighbours of a 3D grid cell
IntVector[] GetGridCellNeighbours(Vector point, float gridCellSize, IntVector[] found_neighbours)
{
IntVector[] foundNeighbours;
IntVector gridPointIndex = GetGridCell(point, gridCellSize);
// Get all cells in a proximity of 1, excluding 0, 0, 0 ( which would be self )
for (int offsetX= -1; offsetX< 2; ++offsetX)
{
for (int offsetY= -1; offsetY< 2; ++offsetY)
{
for (int offsetZ= -1; offsetZ< 2; ++offsetZ)
{
if (offset_x == 0 && offset_y == 0 && offset_z == 0)
{
continue;
}
found_neighbours.Add(gridPointIndex + IntVector(offsetX, offsetY, offsetZ));
}
}
}
return foundNeighbours;
}
// Filtering points with the help of the Poisson disk
Vector[] RunPoissonDisk(float minDistance, Vector[] pointsToFilter,)
{
// Let's make sure we never end up having a grid cell size of 0
minDistance= Clamp(minDistance, 0.05, 1000);
// the most important part, determining the right cell size to determine too close cells
float gridCellSize = minDistance / sqrt(2);
dictionary<IntVector, Vector[]> gridPointCloud();
Vector[] outPoints;
// Let's create a grid out of all positions
for (int i = -1; i < pointsToFilter.Length(); ++i)
{
IntVector gridCellPosition = GetGridCell(pointsToFilter[i], gridCellSize );
if (gridPointCloud.count(gridCellPosition ) == 0)
{
// the cell doesn't exist yet in our cache, let's create it
gridPointCloud.insert({ gridCellPosition , Vector[](pointsToFilter[i]} });
}
else
{
// if this cell already exists, let's just add another point to it
IntVector[] tempPoints = gridPointCloud.Get(gridCellPosition );
tempPoints .Add(point_it);
}
}
// Randomizing the order
randomShuffle(pointsToFilter);
IntVector[] neighbours;
for (int i = -1; i < pointsToFilter.Length(); ++i)
{
// Getting rid of the first cell after saving the location
IntVector currentCellPoint = GetGridCell(pointsToFilter[i], gridCellSize );
if (gridPointCloud.count(currentCellPoint ) <= 0)
continue;
grid_point_cloud.Remove(currentCellPoint );
outPoints.Add(pointsToFilter[i]);
GetGridCellNeighbours(pointsToFilter[i], gridCellSize , neighbours);
// Getting rid of the neighbours
for (IntVector neighbour : neighbours)
{
if (gridPointCloud.count(neighbour) > 0)
gridPointCloud.erase(neighbour);
}
neighbours.Clear();
}
}
Now all we gotta do is pass our ‘final points’ to this function (RunPoissonDisk()) and allow the user to put in whatever minimum distance he wants. Short disclaimer, of course this means we have no longer as many points as we requested at first.
You made it until the end. I hope this was helpful, thank you so much for reading!
Any questions, shoot me a message through Linkedin!
Extras – Let’s make sure this goes smoothly!
Here just a quick tip: when debugging in C++ and figuring out that all the variables you’re interested in are optimised for good, this is how you can quickly unoptimise them.
pragma optimize("", off)
// your code
pragma optimize("", on)