Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
237 views
in Technique[技术] by (71.8m points)

python - My implementation of Bridson's algorithm Poisson-Disk Sampling seems to be stuck in an infinite loop

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.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

The probably most important step is missing in your code:

  1. 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] 


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

1.4m articles

1.4m replys

5 comments

57.0k users

...