当前位置：网站首页>Poisson disk sampling for procedural placement

Poisson disk sampling for procedural placement

2022-06-12 06:02:00 【Senior brother Dai Dai】

Procedural object placement (Procedural Placement)

In the open world game , Lots of little things ( Item box , Impurity , The grass , Cask ) It takes a lot of work to place , It is unrealistic to place manually , In order to save work , The engineer explored Various algorithms for programmatically placing objects .

In the game, the position of an object in the world can be represented by a point , The distribution of all objects constitutes a density map (density map)

For now , There are three algorithms for generating object density maps ( Do not take the noise map into account ), Uniform random (Uniofrm Random), Shake the grid (Jitter Grid), Poisson hard disk sampling (Possion Disk Sample)

Uniform random (Uniofrm Random)

The uniform random algorithm is simple , Ideas : The sampling points are obtained by measuring the width and height of the density map .

Code implementation

void GenerateUniformRandom(int width, int height, int newPointsCount, vector<Point2D>& sampleList)
{
	sampleList.clear();
	
	for (int i = 0; i < newPointsCount; ++i)
	{
		sampleList.push_back(Point2D(Randf(width), Randf(height)));
	}
}

Results show

width = 128, height = 128, sampleCount = 1400

Shake the grid (Jitter Grid)

Dithering grid is to divide the whole picture according to the fixed grid size , It's classified as N x M Lattice of , Then random points are generated in different grids at random

Grid division

Random in the grid

Code implementation

void GenerateJitterGrid(int width, int height, int newPointsCount, float gridSize, vector<Point2D>& sampleList)
{
	sampleList.clear();
	int GridNumX = (float)width / gridSize;
	int GridNumY = (float)height / gridSize;
	TRandomVector<Point2DInt> sampleGrids;

	for (int x = 0; x < GridNumX; ++x)
	{
		for (int y = 0; y < GridNumY; ++y)
		{
			sampleGrids.push_back(Point2DInt(x, y));
		}
	}

	int num = min(sampleGrids.Size(), newPointsCount);
	while (sampleList.size() < num)
	{
		Point2DInt gridPos = sampleGrids.pop();
		float LeftTopX = (float)gridPos.x * gridSize;
		float LeftTopY = (float)gridPos.y * gridSize;
		float RightBottomX = (float)(gridPos.x + 1) * gridSize;
		float RightBottomY = (float)(gridPos.y + 1) * gridSize;
		float randomX = RandRangef(LeftTopX, RightBottomX);
		float randomY = RandRangef(LeftTopY, RightBottomY);
		sampleList.push_back(Point2D(randomX, randomY));
	}
}

Results show

width = 128, height = 128, gridSize = 6.0, sampleCount = 1400

Poisson hard disk sampling (Possion Disk Sample)

There are many kinds of Poisson hard sampling algorithms , At present, this paper introduces a kind of : Random first point from the whole graph , And then start at this point and do multiple random divergences “ Random offset of distance and angle ”, Get a batch of sampling points , Then these sampling points are added to the random array for recursive random divergence , Finally, the most sufficient samples are generated

Random first point , Add to a random array

	TRandomVector<Point2D> processList;
	Point2D firstPoint = Point2D(Randf(width), Randf(height));
	processList.push_back(firstPoint);
	sampleList.push_back(firstPoint);

Random offset of angle and distance from the initial point , Offset distance = random(minDistance, random(1.0,2.0) * minDistance), Offset angle = random(0, 2 * PI)

Point2D point = processList.pop();

for (int i = 0; i < newPointsCount; ++i)
{
	Point2D newPoint = GenerateRandomPointAround(point, minDistance);
	if (IsInRect(newPoint, width, height) && !IsNeighbourhood(grid, newPoint, minDistance, cellSize, 2))
	{
		processList.push_back(newPoint);
		sampleList.push_back(newPoint);
		grid.Push(newPoint);
	}
}


Point2D GenerateRandomPointAround(const Point2D& point, float minDistance)
{
	float r1 = Randf(1.0);
	float r2 = Randf(1.0);

	//random radius
	float radius = minDistance * (r1 + 1.0);

	//random angle
	float angle = 2.0 * PI * r2;

	float newX = point.x + radius * cos(angle);
	float newY = point.y + radius * sin(angle);
	return Point2D(newX, newY);
}

Note that the distance between the newly generated points and the surrounding sampling points must be greater than minDisatnce

bool IsNeighbourhood(Grid2D& grid, const Point2D& point, float minDistance, float cellSize, int NearSeachCellSize = 2)
{
	Point2DInt gridPoint = ImageToGrid(point, cellSize);
	vector<Point2DInt> aroundCells = SquareAroundPoint(grid, gridPoint, 2);

	for (auto& cell : aroundCells)
	{
		const vector<Point2D> &cellPoints = grid.data[cell];
		for (auto& otherPoint : cellPoints)
		{
			if (point.Distance(otherPoint) < minDistance)
				return true;
		}
	}

	return false;
}

Algorithm example diagram

Results show

width = 128, height = 128, minDisance = 3.0, sampleCount = 1400

Improved Poisson hard disk sampling ------ More reasonable offset distance

In the game , The distribution density of the same object in different areas is different , For example, the distribution density of iron ore in cities is small , The distribution density in the field is large . In other words, if the layout of the iron ore uses Poisson hard disk sampling , The random offset distance in the urban area is generally large , The offset distance of the field area is generally small . Therefore, the distance of random divergence should be flexible , Not fixed Offset distance = random(minDistance, random(1.0,2.0) * minDistance),

Better strategy ： Specify the maximum distance of the object maxDistance And the minimum distance minDisatnce, Based on density pixel value value, Calculate the dynamic minimum distance when generating new sampling points ：newMinDistance = minDistance + (maxDistance - minDistance) * (1.0 - value)

New generation point algorithm


Point2D GenerateRandomPointAroundDensity(const Point2D& point, float minDistance, float maxDistance, float cellSize, FIBITMAP* densityMap, float& newMinDistance)
{
	Point2DInt cellPos = ImageToGrid(point, cellSize);
	RGBQUAD color;
	FreeImage_GetPixelColor(densityMap, int(point.x), int(point.y), &color);
	float r1 = Randf(1.0);
	float r2 = Randf(1.0);

	//random radius
	newMinDistance = minDistance + (maxDistance - minDistance) * (1.0 - (float)color.rgbRed / 255.0f);
	float radius = (r1 + 1.0) * newMinDistance;

	//random angle
	float angle = 2.0 * PI * r2;

	float newX = point.x + radius * cos(angle);
	float newY = point.y + radius * sin(angle);
	return Point2D(newX, newY);
}

void GeneratePoissonRandomDensity(int width, int height, float minDistance, float maxDistance, int newPointsCount, vector<Point2D>& sampleList, FIBITMAP* densityMap)
{
	sampleList.clear();
	float cellSize = maxDistance / sqrt(2.0);
	Grid2D grid = Grid2D(ceilf((float)width / cellSize), ceilf((float)height / cellSize), cellSize);

	TRandomVector<Point2D> processList;
	Point2D firstPoint = Point2D(Randf(width), Randf(height));
	processList.push_back(firstPoint);
	sampleList.push_back(firstPoint);

	while (!processList.isEmpty() && sampleList.size() < newPointsCount)
	{
		Point2D point = processList.pop();

		for (int i = 0; i < newPointsCount; ++i)
		{
			float newMinDistance;
			Point2D newPoint = GenerateRandomPointAroundDensity(point, minDistance, maxDistance, cellSize, densityMap, newMinDistance);
			if (IsInRect(newPoint, width, height) && !IsNeighbourhood(grid, newPoint, newMinDistance, cellSize, 4))
			{
				processList.push_back(newPoint);
				sampleList.push_back(newPoint);
				grid.Push(newPoint);
			}
		}
	}
}

Density distribution