Getting random int values not corresponding to any point defined.

[Hideman85]

Dear prof Chris Rycroft,

I am currently using voro++ for biome selection in a procedural generator made out of noise functions. Therefore, I define a weighted list in 3D space representing biome over elevation, temperature, humidity and the weight is there for the rarity. Note that the point could be close to another one, but then the rarity/radius differ.

I found out from another open issue that dev contains a thread version of your algorithm and this is indeed really fast. Unfortunately, I'm getting some values completely random instead to be an index of my registered points. The value is inside the bbox and I even tried if the issue come from the dev branch, but I'm getting the same weird behavior on master branch.

So I'm reaching you out because while I have an understanding of the voronoi algorithm, I dont have a deep understanding of your implementation. Do you have any idea what would cause the output of random number while calling find cell from the poly(3D) container with values properly inside bbox?

I'm looking forward from any help from your side 🙏

EDIT: I'm noticing a second difference between put and put_parallel, from my side it correspond to different biomes, I guess it means that the radius is differently interpreted. The second one has a better fit to the values provided.

The first one is produced on dev branch using put method while the right one is also on dev but using put_parallel, the same noise values are outputted and the black areas correspond to where voro++ for some reason return random numbers instead of a valid index.




[chr1shr]

I haven't seen this behavior before and I am not sure what is going on here. There are definitely more potential issues with the threaded version (and this one reason it's still in the dev branch). In particular if you are using add_parallel to add points, then you should make a call to put_reconcile_overflows before doing any computations. With the threaded version, the code can't dynamically reallocate memory if it runs out of space for particles. Hence it uses an overflow buffer, which can then be resolved afterward by put_reconcile_overflows.

But this can't be the only issue given that you see the same things with the master branch. Also, as far as I know, radii shouldn't be interpreted any differently between any versions of the code, master or dev, parallel or serial.

It sounds like you are primarily using the find_voronoi_cell function, to associate a given point with a particle. This function doesn't actually do any geometrical construction of Voronoi cells. It just searches for nearest neighbors, which involves relatively simple scans and distance checks. If radii are given then there's an additional weighting applied.

It's difficult for me to know exactly what is happening in your picture. It looks as though the bulk of the problem is confined the black+purple regions. Perhaps there is something different about that input data. The blocky structure might be manifesting because Voro++ internally sorts particles into a grid of blocks.

Could you check the input data associated with those black+purple regions? If you remove it, does it work as expected? If you switch off the radius information, does that solve the problem?

[Hideman85]

Thank you for your detailed response 🙏

I paid more attention to why the black regions were appearing, and I figured out one mistake in my own implementation, therefore nothing related to voro++.

Additionally, I checked with put_reconcile_overflows call after each insertion, and you were right the outcome now is same as the original 🙌

I have a question on how is working the distance function with the weighted version? If I imagine two points very close together (or even the same point in 3D space) how are you using the weight/radius to match one or the other? Cause right now I'm doing the Euclidean distance in 3D space and I divide by the radius, but I'm not sure if this is the right way 🤔

[chr1shr]

In a monodisperse particle packing with particle positions x_i, and a Euclidean distance metric d(x,y), the Voronoi cell for a particle i is the space x that satisfies

d(x,x_i) < d(x,x_j)

for all j ≠ i. Hence, given a position y, the find_voronoi_cell function returns back the i where d(y,x_i) is minimized.

In a polydisperse packing where you have particle positions x_i and radii r_i, the library uses the radical Voronoi tessellation. (There is overlapping terminology in the scientific literature, and this is also called the Laguerre map in some situations.) In this case, the Voronoi cell for a particle i is the space x that satisfies

d(x,x_i)² - (r_i)² < d(x,x_j)² - (r_j)²

for all j ≠ i. For a position y, the find_voronoi_cell function returns back the i where d(y,x_i)² - (r_i)² is minimized.

The reason for the square weighting is that it leads to radical Voronoi cells that are irregular polyhedra. If one drops the squares in the definition, then the cells can have curved boundaries, which is a lot more difficult to compute and represent. For more information, see the introduction of the paper by Pinheiro et al.

It is worth noting that with the radical Voronoi tessellation, it is possible for some cells to completely disappear. Suppose that you set one r_i to a huge number, and all other r_j to zero. In that case, looking at the definition, you can see that the Voronoi cell for particle i could fill the whole domain (due to the -(r_i)² term) and all other Voronoi cells could be lost.