Poisson Sampling Example

Resources Community Resources
#1

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:

image
image581×504 235 KB

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
16 Likes