Генерализация 3d опционного диска выборки - PullRequest
Новая
       62

Генерализация 3d опционного диска выборки

0 голосов
/ 25 июня 2019

Я хочу создать выборку диска Пуассона для трехмерной сетки.Я использовал реализацию https://github.com/emulbreh/bridson, чтобы обобщить ее в 3D.Однако кажется, что я что-то упустил, и я не могу найти проблему.Эта реализация следует алгоритму Роберта Бридсона (https://www.cs.ubc.ca/~rbridson/docs/bridson-siggraph07-poissondisk.pdf)

. Я сделал так, чтобы каждый 2-й объект превратился в 3d и создал новую точку со сферическими координатами. 

from random import random
from math import cos, sin, floor, sqrt, pi, ceil


def euclidean_distance(a, b):
    dx = a[0] - b[0]
    dy = a[1] - b[1]
    dz = a[2] - b[2]

    return sqrt(dx * dx + dy * dy + dz * dz)


def poisson_disc_samples(width, height,thick, r, k=5, distance=euclidean_distance, random=random):
    tau = 2 * pi
    cellsize = r / sqrt(2)

    grid_width = int(ceil(width / cellsize))
    grid_height = int(ceil(height / cellsize))
    grid_thick = int(ceil(thick / cellsize))

    grid = [None] * (grid_width * grid_height * grid_thick)
    def grid_coords(p):
        return int(floor(p[0] / cellsize)), int(floor(p[1] / cellsize)), int(floor(p[2] / cellsize))

    def fits(p, gx, gy, gz):
        yrange = list(range(max(gy - 2, 0), min(gy + 3, grid_height)))
        zrange = list(range(max(gz - 2, 0), min(gz + 3, grid_thick)))
        for x in range(max(gx - 2, 0), min(gx + 3, grid_width)):
            for y in yrange:
                for z in zrange:
                    g = grid[x + y + z  * grid_width]
                    if g is None:
                        continue
                    if distance(p, g) <= r:
                        return False
        return True
    p = width * random(), height * random(), thick * random()
    queue = [p]
    grid_x, grid_y, grid_z = grid_coords(p)
    grid[grid_x + grid_y + grid_z * grid_width] = p

    while queue:
        qi = int(random() * len(queue))
        qx, qy, qz = queue[qi]
        queue[qi] = queue[-1]
        queue.pop()
        for _ in range(k):
            alpha = tau * random()
            theta = tau * random()
            d = r * sqrt(3 * random() + 1)
            px = qx + d * cos(alpha) * sin(theta)
            py = qy + d * sin(alpha) * sin(theta)
            pz = qz + d * cos(theta)
            if not (0 <= px < width and 0 <= py < height):
                continue
            p = (px, py, pz)
            grid_x, grid_y, grid_z = grid_coords(p)
            if not fits(p, grid_x, grid_y,grid_z):
                continue
            queue.append(p)
            grid[grid_x + grid_y + grid_z * grid_width] = p
    return [p for p in grid if p is not None]

r = 10
samples = poisson_disc_samples(100, 100, 100, r=10, random=random)

print(samples)

Результаты, которые яЯ смотрю только на печать выбранных трехмерных точек, однако программа не печатает никаких ошибок, и я чувствую, что это потому, что она не находит образцы, а после этого происходит сбой компьютера.

Я думаю, что это можетбыть подходящей функцией (именно она отвечает за проверку, пустые или нет сетки), которая вызывает проблему.

1 Ответ

1 голос
/ 25 июня 2019

Я думаю, что ваши изменения в коде в порядке ... моя единственная проблема с оригиналом - вызов queue.pop(), а не break выход из цикла, когда найденная точка выглядит немного подозрительно.если вы заботитесь о порядке вывода сэмплов, это будет отличаться от опубликованного алгоритма, но в противном случае это, вероятно, не будет иметь значения

. Ваша основная проблема - просто попытка сгенерировать лот * 1006.* баллов и метод должен выполнить довольно много работы на балл, поэтому для его завершения требуется время!если я изменю код на yield точек по мере их генерирования (т.е. добавлю yield p около queue.append(p)) вместо того, чтобы просто возвращать их все в конце, тогда я получу то, что выглядит как разумный вывод

...