Poisson Disk Sampling not working

I am trying to implement Poisson Disk Sampling algorithm to place trees on my map. I have been trying to implement for hours but it does not seem to work. The activeGrid array only increases, which means the function never ends to run. Any help would be appreciated.

Here is the function to generate the points:

function GeneratePoints(radius, sampleRegionSize, k)
	local cellSize = radius / math.sqrt(2)
	
	local columns = math.floor(sampleRegionSize.X / cellSize)
	local rows = math.floor(sampleRegionSize.Y / cellSize)
	local grid = table.create(rows, table.create(columns, -1))
	local activeGrid = {}
	local points = {}

	local initialPos = sampleRegionSize / 2
	table.insert(activeGrid, initialPos)
	
	while #activeGrid > 0 do
		local randIndex = math.random(1, #activeGrid)
		local randPoint = activeGrid[randIndex]
		local isPointFound = false
		for n = 1, k do
			local angle = math.random() * math.pi * 2
			local dir = Vector2.new(math.cos(angle), math.sin(angle))
			local mag = math.random(radius, 2 * radius)
			local sample = randPoint + dir * mag
			
			if IsSampleValid(sample, sampleRegionSize, cellSize, radius, points, grid) then
				table.insert(points, sample)
				table.insert(activeGrid, sample)
				
				local sampleIndexX = math.clamp(math.round(sample.X / cellSize), 1, math.huge) 
				local sampleIndexY = math.clamp(math.round(sample.Y / cellSize), 1, math.huge) 
				grid[sampleIndexX][sampleIndexY] = #points

				isPointFound = true
				
				break
			end
		end
		
		if not isPointFound then
			table.remove(activeGrid, randIndex)
		end
		
		wait()
	end

        return points
end

Here is the code to check if point is valid:

function IsSampleValid(sample, sampleRegionSize, cellSize, radius, points, grid)
	if sample.X > 0 and sample.X <= sampleRegionSize.X and sample.Y > 0 and sample.Y <= sampleRegionSize.Y then
		local cellX = math.clamp(math.round(sample.X / cellSize), 1, math.huge) 
		local cellY = math.clamp(math.round(sample.Y / cellSize), 1, math.huge) 
		local searchStartX = math.max(1, cellX - 2)
		local searchEndX = math.min(cellX + 2, #grid)
		local searchStartY = math.max(1, cellY - 2)
		local searchEndY = math.min(cellY + 2, #grid[1])

		for x = searchStartX, searchEndX do
			for y = searchStartY, searchEndY do
				local pointIndex = grid[x][y]
				if pointIndex ~= -1 then
					local dist = (sample - points[pointIndex]).Magnitude
					if dist < radius then
						return false
					end
				end
			end
		end
		
		return true
	end
	
	return false
end

The way you create your grid 2D array (array of arrays, actually) is incorrect. Your code creates one array with length columns and that array is assigned to every index in the array with length rows. This means that each row in the grid array uses the same array. Adding a point index (#points) to one row will add it to the same y-index (sampleIndexY) in every row.

Because of this, when you have a point and you add another point that has the same y-index, the new point’s index will overwrite the old index.

You could instead use a separate function for creating the 2D array.

local function create2DArray(rows, columns, initialValue)
	local main = table.create(rows)
	for int rowInd = 1, rows do
		main[rowInd] = table.create(columns, initialValue)
	end
end

And to create the grid 2D array, you’d just write the following:

local grid = create2DArray(rows, columns, -1)

I also have another suggestion that doesn’t change the behavior of your code. I noticed that you use math.clamp when you apparently don’t need a maximum value. I think you could replace these lines

local sampleIndexX = math.clamp(math.round(sample.X / cellSize), 1, math.huge) 
local sampleIndexY = math.clamp(math.round(sample.Y / cellSize), 1, math.huge)

with these

local sampleIndexX = math.max(math.round(sample.X / cellSize), 1) 
local sampleIndexY = math.max(math.round(sample.Y / cellSize), 1)
1 Like

I already noticed my array creation and fixed it yesterday, which solved the problem. Also the clamp optimization is also a nice suggestion. Thanks for the help!

1 Like