我对 Bridson 算法 Poisson-Disk Sampling 的实现似乎陷入了无限循环 [英] My implementation of Bridson's algorithm Poisson-Disk Sampling seems to be stuck in an infinite loop

问题描述

<小时>

如果总是使用 spawnpoints 的第一个点而不是随机点，可以获得更好的结果:

# spawnIndex = random.randint(0,len(spawnpoints)-1)spawnIndex = 0 # 0 而不是随机spawnpoint = spawnpoints[spawnIndex]

A video by Sebastion Lague explained the Bridson's algorithm really well.

To oversimplify,

1. Create cell grid that has sides of radius/sqrt(2).

2. Place initial point and list as spawnpoint.

3. Place point into cell in grid.

4. For any spawnpoint, spawn a point between radius and 2*radius.

5. Look at the cells 2 units away from cell of new point.

6. If contains other points, compare distance.

7. If any point is closer to new point than the radius, new point is invalid.

8. If new point is valid, new point is listed as spawnpoint and placed into cell in grid.

9. If spawnpoint spawns too many invalid points, spawnpoint is removed and turns into point.

10. Repeat until no more spawnpoints exists.

11. Return points.

I basically written the same thing down in Python 3.7.2 and pygame 1.7~, but as said in the title, I'm stuck in recursive purgatory.

I used one Point() class for this algorithm, which might seem redundant given that pygame.Vector2() exists, but I needed some elements for a separate algorithm (Delaunay's with infinite vertices) that required this class to work.

For the sake of simplicity I'm going to cut away all the Delaunay-specific elements and show the bare-bones of this class that is needed for this algorithm:

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def DistanceToSquared(self,other):
        return (self.x-other.x)**2 + (self.y-other.y)**2

The code that is related to the Bridson's algorithm is:

def PoissonDiskSampling(width, height, radius, startPos = None, spawnAttempts = 10):

    if startPos == None:
        startPos = [width//2,height//2]

    cellSize = radius / math.sqrt(2)
    cellNumberX = int(width // cellSize + 1)  # Initialise a cells grid for optimisation
    cellNumberY = int(height // cellSize + 1)
    cellGrid = [[None for x in range(cellNumberX)] for y in range(cellNumberY)]

    startingPoint = Point(startPos[0],startPos[1]) # Add an iniial point for spawning purposes
    cellGrid[startingPoint.x//radius][startingPoint.y//radius] = startingPoint

    points = [startingPoint] # Initialise 2 lists tracking all points and active points
    spawnpoints = [startingPoint]

    while len(spawnpoints) > 0:

        spawnIndex = random.randint(0,len(spawnpoints)-1)
        spawnpoint = spawnpoints[spawnIndex]

        spawned = False
        for i in range(spawnAttempts):

            r = random.uniform(radius,2*radius)
            radian = random.uniform(0,2*math.pi)
            newPoint = Point(spawnpoint.x + r*math.cos(radian),
                            spawnpoint.y + r*math.sin(radian))
            if 0 <= newPoint.x <= width and 0 <= newPoint.y <= height:
                isValid = True
            else:
                continue

            newPointIndex = [int(newPoint.x//cellSize), int(newPoint.y//cellSize)]
            neighbours = FindNeighbours(cellNumberX,cellNumberY,newPointIndex,cellGrid)

            for neighbour in neighbours:
                if newPoint.DistanceToSquared(neighbour) < radius**2:
                    isValid = False
                    break

            if isValid:
                points.append(newPoint)
                spawnpoints.append(newPoint)
                spawned = True
                break
            else:
                continue

        if spawned == False:
            spawnpoints.remove(spawnpoint)

    return points

def FindNeighbours(cellNumberX, cellNumberY, index, cellGrid):
    neighbours = []
    for cellX in range(max(0,(index[0]-2)), min(cellNumberX,(index[1]+2))):
        for cellY in range(max(0,(index[0]-2)), min(cellNumberY,(index[1]+2))):
            if cellGrid[cellX][cellY] != None:
                neighbours.append(cellGrid[cellX][cellY])
    return neighbours

Please help.

解决方案

The probably most important step is missing in your code:

8. If new point is valid, new point is listed as spawnpoint and placed into cell in grid.

I suggest to add the point to the cellGrid if it is valid:

if isValid:

    cellGrid[newPointIndex[0]][newPointIndex[1]] = newPoint

    points.append(newPoint)
    spawnpoints.append(newPoint)
    spawned = True
    break

Further, you have to verify if the cell with the index newPointIndex is not already occupied before a point can be add:

newPointIndex = [int(newPoint.x/cellSize), int(newPoint.y/cellSize)]
if cellGrid[newPointIndex[0]][newPointIndex[1]] != None:
    continue

neighbours = FindNeighbours(cellNumberX,cellNumberY,newPointIndex,cellGrid)

---

Finally there is an issue in the function FindNeighbours. range(start, stop) creates a range for x in start <= x < stop.
So the stop has to be index[0]+3 rather than index[0]+2.

Further the ranges which control the 2 nested for loops, run both from x-2 to y+2 rather than from x-2 to x+2 respectively from y-2 to y+2:

for cellX in range(max(0,(index[0]-2)), min(cellNumberX,(index[1]+2))):
   for cellY in range(max(0,(index[0]-2)), min(cellNumberY,(index[1]+2)))

The fixed function has to be:

def FindNeighbours(cellNumberX, cellNumberY, index, cellGrid):
    neighbours = []
    for cellX in range(max(0, index[0]-2), min(cellNumberX, index[0]+3)):
        for cellY in range(max(0, index[1]-2), min(cellNumberY, index[1]+3)):
            if cellGrid[cellX][cellY] != None:
                neighbours.append(cellGrid[cellX][cellY])
    return neighbours

---

See the result, for a size of 300 x 300 and a radius of 15:

---

An even better result can be achieve, if always the 1st point of spawnpoints is used to rather than a random point:

# spawnIndex = random.randint(0,len(spawnpoints)-1)
spawnIndex = 0 # 0 rather than random
spawnpoint = spawnpoints[spawnIndex] 

这篇关于我对 Bridson 算法 Poisson-Disk Sampling 的实现似乎陷入了无限循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！