I am using Poisson Sampling technique to spawn some trees, but to make it easier I want to use a box Collider to easily define the areas where I want to spawn the trees.
Im was using a Rect because its easy and it was being used by the Sampler by default to check if a value is inside of it using
bool isInsideRect = Rect.Contains(Vector2 point)
However the Rect is apparently a 2D UI element, thats only using x, y coordinates, width and height, no depth.
I however want to use a 3D BoxCollider to easily visualize and change the size of the Area that I want to use, in my case for spawning trees inside a rectangular area.
So the main thing Im trying to figure out is how to take the values from a BoxCollider and find out if my samples are within those bounds.
I think the sampler is the problem here. Because it spits out one random sample outside the box and nothing more after that.
Heres how I use that Sampler:
// Iterate over all tree spawning areas on that Island
foreach (BoxCollider spawningArea in island.GetTreeSpawningBoxes())
{
// i = 0; // bug fix?
i = -1; // nope unfortunately it wont do it
// Maybe because Samples() is an IEnumerable???
// Initialize a new Poisson Disc Sampler
PoissonDiscSampler sampler = new PoissonDiscSampler(spawningArea, 18);
// Get Samples and Iterate over all of them
foreach (Vector2 sample in sampler.Samples())
{
// Ignore half of the samples
//if (i % 2 != 0) return; // I thought bug
if (i++ % 2 != 0) return; // But this still doesnt work
// Its unrelated to the question though just noticed it
// Poisson Disc Sampled Position
Vector3 pos = new Vector3(sample.x, 0, sample.y);
// Random Y-axis rotation (0 - 359)
Quaternion rot = Quaternion.identity;
rot.eulerAngles = new Vector3(0, Random.Range(0, 360), 0);
// Spawn the tree
var tree = Instantiate
(
StaticResources.instance.SailingTrees[Random.Range
(0, StaticResources.instance.SailingTrees.Length - 1)],
pos,
rot
);
tree.transform.SetParent(island.transform);
}
}
If there is another way instead of using a Box Collider for each area, or maybe another solution so I dont need to use the Rect, then Im all ears!
I setup an island with the BoxCollider and tried using those bounds to see if its inside and spawn the tree, however it is ony spawning 1 tree, randomly way outside the BoxCollider and then nothing else, which leads me to believe thats the very first random sample, and after that it cant find any more because the first one is already outside the box.
Heres the code:
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
/// Poisson-disc sampling using Bridson's algorithm.
/// Adapted from Mike Bostock's Javascript source: http://bl.ocks.org /mbostock/19168c663618b7f07158
///
/// See here for more information about this algorithm:
/// http://devmag.org.za/2009/05/03/poisson-disk-sampling/
/// http://bl.ocks.org/mbostock/dbb02448b0f93e4c82c3
///
/// Usage:
/// PoissonDiscSampler sampler = new PoissonDiscSampler(10, 5, 0.3f);
/// foreach (Vector2 sample in sampler.Samples()) {
/// // ... do something, like instantiate an object at (sample.x, sample.y) for example:
/// Instantiate(someObject, new Vector3(sample.x, 0, sample.y), Quaternion.identity);
/// }
///
/// Author: Gregory Schlomoff ([email protected])
/// Released in the public domain
/// <summary>
/// Poisson-disc sampling using Bridson's algorithm.
/// </summary>
///
/// --------------------------------------------------------------------
///
/// Improved and Optimized by Me
///
/// New Usage:
/// PoissonDiscSampler sampler = new PoissonDiscSampler(BoxCollider box, float radius);
///
public class PoissonDiscSampler
{
private const int k = 30; // Maximum number of attempts before marking a sample as inactive.
private BoxCollider box;
private readonly float radius2; // radius squared
private readonly float cellSize;
private Vector2[,] grid;
private List<Vector2> activeSamples = new List<Vector2>();
/// Create a sampler with the following parameters:
///
/// width: each sample's x coordinate will be between [0, width]
/// height: each sample's y coordinate will be between [0, height]
/// radius: each sample will be at least `radius` units away from any other sample, and at most 2 * `radius`.
public PoissonDiscSampler(BoxCollider box, float radius)
{
this.box = box;
radius2 = radius * radius;
cellSize = radius / Mathf.Sqrt(2);
grid = new Vector2[Mathf.CeilToInt(box.size.x / cellSize),
Mathf.CeilToInt(box.size.z / cellSize)];
}
/// Return a lazy sequence of samples. You typically want to call this in a foreach loop, like so:
/// foreach (Vector2 sample in sampler.Samples()) { ... }
public IEnumerable<Vector2> Samples()
{
// First sample is choosen randomly
yield return AddSample(new Vector2(Random.value * box.size.x, Random.value * box.size.z));
while (activeSamples.Count > 0)
{
// Pick a random active sample
int i = (int)Random.value * activeSamples.Count;
Vector2 sample = activeSamples[i];
// Try `k` random candidates between [radius, 2 * radius] from that sample.
bool found = false;
for (int j = 0; j < k; ++j)
{
float angle = 2 * Mathf.PI * Random.value;
float r = Mathf.Sqrt(Random.value * 3 * radius2 + radius2);
// See: http://stackoverflow.com/questions/9048095/create-random-number-within-an-annulus/9048443#9048443
Vector2 candidate = sample + r * new Vector2(Mathf.Cos(angle), Mathf.Sin(angle));
// Accept candidates if it's inside the rect and farther than 2 * radius to any existing sample.
if (box.bounds.Contains(candidate) && IsFarEnough(candidate))
{
found = true;
yield return AddSample(candidate);
break;
}
}
// If we couldn't find a valid candidate after k attempts, remove this sample from the active samples queue
if (!found)
{
activeSamples[i] = activeSamples[activeSamples.Count - 1];
activeSamples.RemoveAt(activeSamples.Count - 1);
}
}
}
private bool IsFarEnough(Vector2 sample)
{
GridPos pos = new GridPos(sample, cellSize);
int xmin = Mathf.Max(pos.x - 2, 0);
int ymin = Mathf.Max(pos.y - 2, 0);
int xmax = Mathf.Min(pos.x + 2, grid.GetLength(0) - 1);
int ymax = Mathf.Min(pos.y + 2, grid.GetLength(1) - 1);
for (int y = ymin; y <= ymax; y++)
{
for (int x = xmin; x <= xmax; x++)
{
Vector2 s = grid[x, y];
if (s != Vector2.zero)
{
Vector2 d = s - sample;
if (d.x * d.x + d.y * d.y < radius2) return false;
}
}
}
return true;
// Note: we use the zero vector to denote an unfilled cell in the grid. This means that if we were
// to randomly pick (0, 0) as a sample, it would be ignored for the purposes of proximity-testing
// and we might end up with another sample too close from (0, 0). This is a very minor issue.
}
/// Adds the sample to the active samples queue and the grid before returning it
private Vector2 AddSample(Vector2 sample)
{
activeSamples.Add(sample);
GridPos pos = new GridPos(sample, cellSize);
grid[pos.x, pos.y] = sample;
return sample;
}
/// Helper struct to calculate the x and y indices of a sample in the grid
private struct GridPos
{
public int x;
public int y;
public GridPos(Vector2 sample, float cellSize)
{
x = (int)(sample.x / cellSize);
y = (int)(sample.y / cellSize);
}
}
}
Thank you!
P.S. I know I can use raytracing but Id rather not as its quite expensive. Im really looking for a mathematical way, using the box.bounds.Contains() seems the cheapest way..
However the Rect is apparently a 2D UI element, thats only using x, y coordinates, width and height, no depth.
Indeed ;) That is what a Rect (short for rectangle is).
Using the Collider.bounds yields one disadvantage: It is not very precise as further explained here.
This seems to be a valid option.
Just translated it into an extension method:
public static class ColliderExtensions
{
public static bool Contains(this Collider collider, Vector3 worldPosition)
{
var direction = collider.bounds.center - worldPosition;
var ray = new Ray(worldPosition, direction);
var contains = collider.Raycast(ray, out var hit, direction.magnitude));
return contains;
}
}
The idea here
The last point in particular is true as raycasts in Unity do not detect if you already started within a collider.
The Collider.Raycast is way cheaper than Physics.Raycast since it only raycasts against this one specific collider which will usually mean the ray is first converted into the local space of that specific collider and then you basically raycast against an axis aligned box which is of course easier to do.