# Poisson Sampling Example

Poisson Disk Sampling is a common method in graphics for placing points with “even” spacing. Whereas just using random numbers can cause two points to be placed very close to eachother, poisson disk sampling guarantees a minimum distance. This algorithm is very useful for procedural generation:

I’ve implemented this from the algorithm described here: https://www.cs.ubc.ca/~rbridson/docs/bridson-siggraph07-poissondisk.pdf

I have drawn extra lines between points and their “parent”, this is the random active point xi described in the algorithm. This could be useful for generating things like rivers and branches. There is a lot of room for exploration in placement bias and initial active points.

Source code:

``````--Placement prototype
local partProt = Instance.new("Part")
partProt.Anchored = true
partProt.Size = Vector3.one
partProt.BrickColor = BrickColor.new("Lime green")
partProt.TopSurface = Enum.SurfaceType.Smooth

--Poisson sampling
local nextIndex = 0
local r = 5
local k = 30

local gridsize = 100
local grid = {}

--Init grid
for i = 1, gridsize do
grid[i] = {}

for j = 1, gridsize do
grid[i][j] = -1
end
end

--Active elements
local active = {}

--Place nextIndex at point in grid
local function PlaceActive(i, j)
grid[i][j] = nextIndex

local t = {i = i, j = j}

table.insert(active, t)
nextIndex += 1
end

--Check if a point is far enough away from active elements
local function CheckActiveClearance(i, j)

--Always fail to check points outside grid
if i < 1 or i > gridsize or j < 1 or j > gridsize then
return false
end

for x = i - r, i + r do
for y = j - r, j + r do
--Dont care about points outside the grid
if x < 1 or x > gridsize or y < 1 or y > gridsize then
continue
end

--Dont care about points out of radius
local dist = math.sqrt(math.pow(x - i, 2) + math.pow(y - j, 2))

if dist > r then
continue
end

--Point in this area
if grid[x][y] ~= -1 then
return false
end
end
end

return true
end

--Place initial element always at the center
local x = math.round(gridsize / 2)
local z = math.round(gridsize / 2)

PlaceActive(x, z)

--Main algorithm
while #active > 0 do
--Pick random active element
local activeIndex = math.random(1, #active)
local selActive = active[activeIndex]

local placedAtLeastOne = false

--Try k times
for _ = 1, k do
--Try to place new point between r and 2r
local randomAngle = math.random() * math.pi * 2
local randomRange = r * (math.random() + 1)

local x = math.round(selActive.i + math.cos(randomAngle) * randomRange)
local y = math.round(selActive.j + math.sin(randomAngle) * randomRange)

if CheckActiveClearance(x, y) then
--Placement ok
PlaceActive(x, y)

--Place part
local part = partProt:Clone()
part.Parent = workspace
part.Position = Vector3.new(x, 1, y)

--Draw a line from the previous point
local dist = math.sqrt(math.pow(selActive.i - x, 2) + math.pow(selActive.j - y, 2))
local prevPoint = Vector3.new(selActive.i, 1, selActive.j)

local line = partProt:Clone()
line.Parent = workspace
line.Size = Vector3.new(0.5, 0.5, dist)
line.CFrame = CFrame.lookAt((prevPoint + part.Position) / 2, part.Position)

placedAtLeastOne = true
end
end

if not placedAtLeastOne then
--Remove active
table.remove(active, activeIndex)
end
end
``````
15 Likes