# Generate non-overlapping spheres having different diameters in a mesh

I created this setup that does a random distribution of points and relaxes them so that the distance between them tends towards a given distance:

I rely on Index of Nearest node, that gets closest point in a set of points. But I want to improve the setup so that spheres will have random diameter. In that case, Index of Nearest is not suitable for that.

Here is the node setup:

My goal is to make a node group that can distribute random objects over a given surface without (noticeable) intersections. As you see, distributing spheres is easy, so I want to make the next step and pack spheres with random diameters. I should say, that diameters should be given before distribution, overwise it is easy to set random points and setup diameters so that whey will not intersect.

Another approach that I've tried is using Pack UV islands node:

It works pretty well, but has some issues, though. One of them I've already posted here: How to search by attribute?

Another issue is that Pack UV islands works by using bounding boxes, more precise algorithms are presented in Blender, but not in the Geometry nodes. Also, the limit of Pack UV islands is that it works in 2D space and only in square, so that it limits the application of this method

• You've not mentioned it, but point positions are also constrained by the original surface, right? Dec 23, 2023 at 15:16
• @lemon, Yes, sure Dec 23, 2023 at 15:21
• I don't know if I'll find the time in the upcoming days for obvious reasons but the way I'd approach it is to assign all points (representing spheres) to a grid of cells (rounding coordinates to a given increment), obviously this requires some kind of assumption on the range of sizes of the spheres, though you could create multiple resolution grids or grids within cells (octree), then for each point, you can iterate over 9 cells (its cell and neighboring cells), and then iterate over all elements in those cells and this way find the point with the highest score in regards to currently eval. p. Dec 23, 2023 at 16:32
• Obviously you could simulate spheres instead of points, that's more expensive, but you can use internal Blender functionality (BVHTree) of finding the nearest face, and with that face having an ID of the point the instance that it was realized from, you get the sphere with nearest surface as opposed to a sphere with nearest center. Dec 23, 2023 at 16:33
• Oh, just realized the 2nd approach suffers from the common issue of the "nearest" finding self, so you would need to generate a BVHTree for each sphere, by raising the geometry to a square (instance on points with both points and instance being the same input geometry, then remove self from each). Dec 23, 2023 at 16:40

(Using Blender 3.6.5)
NB: This is a very incomplete answer; it is more like a progress report.

Motivated by your challenging question, I oriented my attempts towards constructive techniques instead of dynamic techniques like your's and lemon's proposals. I selected the following paper after a short bibliography review on the subject (sorry, I could not find an open access version in English):

Azeddine Benabbou, Patrick Laug, Houman Borouchaki, Jian Lu. Modélisation géométrique, maillage et simulation des structures granulaires – Application aux nanostructures Partie I. Aspects théoriques et algorithmiques de la modélisation – Cas de la dimension deux. [Rapport de recherche] RR-6414, INRIA. 2008, pp.48. ⟨inria-00203375v3⟩

It describes an advancing-front technique. Blender data structure (mesh with vertices and edges, point cloud) seems adapted to code such techniques.

What started as a quite simple GN graph is now a rather complex thing because of many singular cases to deal with. It is far from complete and optimized. But it shows promises: Left figure: Filling of a rectangular box by a random normal distribution with radius in range [0.1, 0.2]. This distribution is an input to the algorithm, i.e. the current radius is not drawn or selected during the filling process.
Middle figure: Coloring of the successive fronts with sphere index.
Right figure: Coloring of the successive segments connecting spheres during the filling process.

Resources:
This version 0 is using Simulation Zone and frames to simulate the loop. I do not know how it behaves using Repeat Zone instead in Blender 4.0. As expected from the reference paper, it scales linearly in iterations with the number of spheres.

• That's interesting. But it seems to stop at some point (I was not able to reproduce the above images with your file). Also ported it to 4.0 and changed the simulation to repeat, but this is the same. +1 as I'm curious to see the following steps! Jan 3 at 9:42
• @lemon: can you try and change the "Seed" in the very first node named "Fill Disk Tank"? I still have some early breakdowns with some seeds, but for such a small box, 500 steps should be enough for almost all seeds. There is no stopping criteria for the time being, so you can expect that the graph is not changing any more when no room is left to place the next sphere in the queue. Jan 3 at 11:32
• The attached .blend filled less than 30% of the box for the starting settings and 4 other seeds I tested, but what it filled looked good so the technique shows promise. Jan 3 at 15:25
• @StefLAncien, I've tried several seeds, but same: it stops partially filling the surface. But, ok, as you said, this is a wip. When possible, I'll try to understand all that... Jan 3 at 20:01
• The blend file works exactly as shown on the figures. However it starts intersecting substantially with greater differences between min and max of the random circle size. I've found this old YT video youtube.com/watch?v=SSWudanJc7c which reminds me a lot to a boid simulation. Maybe this is a good direction for GN solution. Jan 5 at 22:29

That can be the following:

'Heavy brute force' iterative calculation!!

That's a double loop (nested repeat zones).

The outer one is to repeat the nested one a given amount of times (guessed).

The nested one goes over each sphere S and for it calculates a offset vector testing all other spehere Sn. This vector is the sum of the following:

If the distance between the twos spheres is less than the sum of their radius, takes the vector (S, Sn) multiplyed by a moderation factor (0.5) so that S moves away Sn.

The accululated calculation for all Sn, gives the overall orientation for S to move aways any other sphere.

• it works of course, but performance suffers a bit.... Who's knocking? The performance police! youtu.be/LDhN-JK3U9g?si=ABk_LcdZC7eNlYfz&t=612 Dec 24, 2023 at 22:33
• yes I know it is s l o w ... of course Dec 25, 2023 at 7:19
• In fact comparing with your last question on the subject, (pack uv islands) this is not so slow... if you take around 200 instances and compare the results (and accuracy of the intersections), this is quite fine... set on the timing on the nodes... Dec 31, 2023 at 8:12

This approach is more or less in the direction of the original question (relaxing distances).

You can predict the positions of tightly packed random sized spheres with simulation or good mathematical algorithm. But it requires additional functionality that Geometry Nodes currently lacks.

My solution is imperfect but can be improved further.

More detailed description can be read here:

Geometry Nodes - Circle Packing - ish

Here is a screenshot of the node setup:

and the blend file:

I've omitted the part where you can delete points that are outside of a given shape and used circles instead of spheres, but they are both pretty straightforward to implement after the simulation zone.