Skip to main content
 首页 » 编程设计

python之我对 Bridson 算法 Poisson-Disk Sampling 的实现似乎陷入了无限循环

2024年11月01日14mfrbuaa

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

过度简化,

  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.

我基本上在 Python 3.7.2 和 pygame 1.7~ 中写下了同样的东西,但正如标题所说,我陷入了递归炼狱。

我为该算法使用了一个 Point() 类,考虑到 pygame.Vector2() 存在,这似乎是多余的,但我需要一些元素用于需要此类才能工作的单独算法(Delaunay 的无限顶点算法)。

为了简单起见,我将删除所有特定于 Delaunay 的元素,并展示该算法所需的此类的基本内容:

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 

与Bridson算法相关的代码是:

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 

请帮忙。

请您参考如下方法:

您的代码中可能缺少最重要的步骤:

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

我建议将点添加到 cellGrid如果有效:

if isValid: 
 
    cellGrid[newPointIndex[0]][newPointIndex[1]] = newPoint 
 
    points.append(newPoint) 
    spawnpoints.append(newPoint) 
    spawned = True 
    break 

此外,您必须验证索引为 newPointIndex 的单元格是否为在可以添加点之前尚未被占用:

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

函数终于有问题了 FindNeighbours . range(start, stop)在 start <= x < stop 中为 x 创建一个范围.
所以止损点必须是index[0]+3而不是 index[0]+2 .

进一步控制 2 个嵌套的范围 for循环,从 x-2 运行至 y+2而不是来自 x-2至 x+2分别来自y-2至 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))) 

固定函数必须是:

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 

查看结果,尺寸为 300 x 300,半径为 15:


如果始终是 spawnpoints 的第一个点,则可以获得更好的结果。用于而不是随机点:

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