Voronoi tessellation on a surface

[bobtato]

I needed to tile an arbitrary closed SubD surface with (mostly) hexagons, so I set up the Grasshopper / Kangaroo / C# solution below.

geodeye.gh (15.2 KB)

I’m populating the brep with random points, then using a SphereCollide goal to spread them out uniformly while keeping them on the surface with an OnMesh goal. The C# script generates the Voronoi diagram of the points, which are mostly hexagonal since that is the most efficient way to pack spheres on a plane.

That pretty much works, and I’m partly posting this as it may be useful to others. But…

What I was hoping for was almost all regular hexagons, with a small number of pentagons to accommodate the curvature, like you’d see in a spherical geodesic dome (i.e. the dual of a subdivided icosahedron). But you can see there are quite a lot of irregular polygons, and they are clustered together. Interestingly, changing the cell density doesn’t seem to make much difference.

I should add that I am specifying an average cell spacing S, and using that to calculate both the number of points (=Area/(S²*√3/2)) and the SphereCollide radius (=S/2). These would be the exact values for a flat surface, and I believe that’s the only reason this works at all.

If I make the SphereCollide radius smaller, it just doesn’t do anything, and if I make it significantly bigger it doesn’t settle at all. At right around (0.7*S), there is a second minimum dominated by square cells, which is super interesting when you think about what’s happening:

…but even less useful to me.

I think the problem is that SphereCollide calculates hard “on/off” interactions, when what I really want is a continuous force field through space (or even along the surface). I can’t find a way to do this using Kangaroo, though…?

I did try using the Soft & Hard solver, but that just gave odd results. Maybe there is some clever way of placing anchor points to force a more regular solution?

[11165 (Deer)]

This is such a masterpiece.

I think kangaroo + voronoi can not meet your demand on hex + penta(on curvature).
To have majority of the polygon being hex you will have to ensure points layout after kangaroo are very close to triangular layout.
There is very limited way to ensure that in kangaroo by using Sphere collide after random population.

PS: you forgot to internalize brep in GH file.

[DanielPiker]

Hi @bobtato
Have you looked at the dual output of triremesh?

Introducing TriRemesh - high quality triangular and hexagonal remeshing and shrink wrapping

Happy New Year everyone! Wishing all of you and your families a healthy and joyful 2021 I’m pleased to share a new tool for fast and robust generation of high quality isotropic triangular meshes (and their duals) from a Brep or mesh input. The resulting meshes consist of triangles with similar edge lengths, angles and areas. [creases] [conformingfleur] [dragon_remesh] [tennyson] [hand_remesh] This will be included in Grasshopper in the next Rhino 7 service release candidate. The n…

As you noticed - hard spheres will naturally tend to pack in regions of regular hexagonal arrangement, with grain boundaries between them.

For doing it with repulsion (a continuous force field through space like you mention), have a look at

Is there an easy way to create uniform point distributions on a sphere, such as the endpoints of an icosohedron, but more points?

Here’s an example of using electrostatic type repulsion to distribute a large number of points (shown here with 10,000). This approach can be useful if you require a specific number of points, since with the subdivision method you are limited to the jumps in vertex count between levels of subdivision. repulsion_distribute_sphere.gh (14.3 KB)

Also - something that I think isn’t always immediately obvious is that equal spacing between neighbours and topological regularity (i.e. a smaller number of pentagons and heptagons) are actually conflicting goals.
As you subdivide an icosahedron you will always have just 12 irregular vertices (12 pentagons in the dual), even when you have hundreds of vertices. For the same number of vertices it is generally possible to form a less topologically regular arrangement with more than 12 pentagons and some heptagons, but with better regularity of distance between nearest neighbours.
If your priority is topological regularity on a freeform surface, what you can do is generate a distribution with a smaller number of points, form the mesh, then subdivide that.

[11165 (Deer)]

TriRemesh is so OP

[bobtato]

Thanks, that’s very helpful! I guess the moral is I should google harder, because not only had I not seen the thread with the charged particles goal, I didn’t even know about TriRemesh. If I did, I would have just gone with that from the start.

But replacing SphereCollide with the charged particles script did improve my original solution (on the left), and I think I subjectively prefer that to the TriRemesh result (right), so my time wasn’t completely wasted.

geodeye.gh (78.0 KB)

I’m now interested in the idea of making custom Kangaroo goals – does any kind of reference exist for that API?

[DanielPiker]

I agree that the distributions from electrostatic repulsion can be very nice.

Here’s another example of that repulsion goal, but also including the ngon mesh/polygon generation based on proximity within the goal.

One issue with Voronoi cells is that even for good distributions of the point sites, the cells often have some rather short edges. Using a different dual of the triangulation such as the barycentric dual (instead of the circumcentric dual, which the Voronoi cells are equivalent to) often gives nicer cell shapes.
repulsion_distribute_surface_mesh.gh (16.0 KB)

As for making custom goals, there isn’t an official reference document as such but the best place to start is to look at the code for the existing goals here, and feel free to ask any questions you run into.

(one other advantage over this sort of point distribution based meshing is that unlike remeshing, you don’t need any mesh to start with, so it can even be used for implicits, like I just showed here
Chair Surface - implicit equation to parametric equation - #2 by DanielPiker)

[bobtato]

Thanks again – that barycentric algorithm is obviously better than what I’d come up with!

I notice you also changed the (formerly) electrostatic force law, and made that goal 10x stronger than the OnMesh, which seems to make an improvement even by itself.

[guido]

If what you’re after is an effect rather than a tessellation you could simply intersect your shape with a weaire phelan structure.
Faces are not going to be planar but the result is interesting.