Grasshopper

algorithmic modeling for Rhino

# Medial Packing

An experiment with adaptive sphere packing on a surface with the help of Rhinocommon's RTree class.

A new sphere is added to the population if the average pressure felt by the existing spheres falls below a given threshold. Similarly, if the average pressure exceeds a second higher threshold a sphere is removed.

More @
http://spatial-slur.blogspot.co.uk/2013/10/pack-attack.html

Views: 846

Comment

Join Grasshopper

Comment by Mateusz Zwierzycki on October 17, 2013 at 7:03pm

Aha !

To compute the Delaunay triangulation, project the points to a paraboloid by summing the squares of their coordinates. Then take the convex hull of the projected points. Remove the vertical dimension from the lower envelope of the convex hull. The projected edges are the Delaunay triangulation of the original points.

Notice the 6 co-circular points near the center of the triangulation. They correspond to a flat facet of the convex hull. The program Qhull constructed a hexagon instead of three triangles. The hexagon has an empty circumcircle.

The same process can be used for points in 3-d or higher. In 3-d, each tetrahedron of the Delaunay triangulation has an empty circumsphere, and the corresponding paraboloid sits in 4-d.

Comment by Daniel Piker on October 11, 2013 at 3:19am

@Dave R

The tetrahedral mesh just needs to be checked and edges flipped if necessary at each iteration, not regenerated from scratch (this is what is happening at 0:36 here, but with triangles not tets).

I don't know how the speed/efficiency will compare with other spatial tree structures, but for me the main appeal would be getting the surface triangulation from the same process as the neighbour queries.

I figured someone has probably tried this idea before - did some searching and sure enough, for granular simulations it has been used for detecting collisions in 'discrete element modelling', but not very widely as far as I can tell (and not the part about a changing triangulated surface from the tetrahedra). Some info on this here:

http://www.apprendre-en-ligne.net/auteur/roso/boston.pdf

and in more detail here:

http://infoscience.epfl.ch/record/32908/files/EPFL_TH2432.pdf

(see Fig 2.15)

and a similar approach can even be extended to collision detection between polygons, not just spheres

http://www.apprendre-en-ligne.net/auteur/roso/marseille.pdf

@Dan H

If I understand correctly, what you are suggesting is a little bit like what they use here for splitting the surface when handles get too thin, though in this case based on unflippable edges not aspect ratios:

http://research.microsoft.com/en-us/UM/people/yangliu/publication/c...

(see figure 3)

However, this only works for splits, and won't help 2 blobs which start separate then need to merge.

Another possibility could be to do constant local connectivity updates together with occasional more expensive global checks for topology change by using some spatial tree to check proximity.

Similar to what is described here:

and implemented rather nicely here:

http://stephaneginier.com/

Comment by David Reeves on October 9, 2013 at 7:20pm

@ Mateusz

You'll get a more even point distribution with sphere packing than with divided contour lines so it might still be worth tinkering with. Call me curious.

Comment by Mateusz Zwierzycki on October 9, 2013 at 6:58pm

@David:    Belive me or not, the ball pivoting needs really evenly distributed points, not just fairly. The problem with this algo is that usually this kind of meshing techniques are used to do a rough mesh representation of an object (think medical stuff).

For architecture, where the triangle count is relatively low (up to 10000 - 100000 triangles at most) and the surface quality must be high as hell, we need to search deeper. Think about how many ambiguous situations we can have only with 4 points.

At this moment, imho the only good approach to blob-meshing (which I assume we're talking about right now), is the spring-based model (here Kangaroo) with predefined topology, or as Daniel Piker suggests here - some gentle topological changes made on initial connections.

Comment by David Reeves on October 9, 2013 at 1:34pm

Thanks guys.

@ Daniel P.

Interesting link. So would the flipping remove the need to re-triangulate the whole system at each step? Or would it just happen less often?

Given the fairly even distribution of points, this could be a job for the ball-pivoting algorithm. Although it wouldn't be nearly as clean as extracting the surface directly from the triangulation that drives all the location interactions. As the kids say, that'd be tight.

Comment by Daniel Hambleton on October 9, 2013 at 7:44am

@Daniel

Could you cull triangles that exceed a certain aspect ratio? This would be a naive implementation of an alpha shape, but would serve to create holes.

Or in David's example, you could have a density threshold below which you don't add any more points. But then how do you get a clean boundary....not sure...

Also, very cool David.

Comment by Mateusz Zwierzycki on October 8, 2013 at 6:55pm

@Daniel - In that context it's a really nice approach (keeping up with the local changes).

What I really would like to find is a way to derive 3d delaunay from the "bottom" half of 4d convex hull... My mind is to shallow to tell if that's even possible, I couldn't find that approach anywhere.

As far as I know, in 2d delaunay there are no ambiguous cases. In 3d this is a common situation... wonder if it would be the same while deriving from the 4d convex hull...

Comment by Daniel Piker on October 8, 2013 at 6:21pm

Great work as always David!

and thanks for sharing the example.

Interesting this talk of tetrahedralization...

I got into surface remeshing for similar reasons of avoiding the O(n^2) interactions.

When the particles are already forming a triangulation on a surface, it is nice to be able to limit the interactions to exactly just the local ones needed - by using and updating that connectivity information (and this also means there is no need for any additional step to convert the particle distribution into a mesh).

However, more global methods have the advantage of being able to dynamically alter not just the shape, but also the genus, as you show here.

Something I'd been wondering about is maybe by using a 3d Delaunay mesh (a tetrahedralization) - which can be incrementally updated by similar bistellar flip operations, and then interactions can be kept purely local, while still enabling these topology changes of a surface mesh (which exists as a subset of this volumetric mesh).

Comment by David Reeves on October 8, 2013 at 5:13pm

This one would call for some Delaunay tetrahedralization I'm afraid. I don't think I'm in any shape to be attempting that myself.

To answer your question, I did indeed make use of Rhinocommon's RTree class here. Below is a download link to the surface packing definition. Poke around inside the C# component for an implementation example.

https://www.dropbox.com/s/w699j0iw7xewynw/131008_Surface_Packing_Ex...

Comment by Mateusz Zwierzycki on October 8, 2013 at 11:42am

Well, I wanted to comment under the other of your videos - this one is not a trivial case :D

• View All

## Videos

• ### Tutorial 01: Pattern Generation Using 'Parakeet'; Basics

Added by Esmaeil Mottaghi

• ### Parametric Roof (Grasshopper Tutorial)

Added by Parametric House

• ### Extrusion Path Testing with a KR10 R900

Added by Karl Singline

• ### BearGIS Grsshopper to ArcGIS Pro Live Feed

Added by Nico Azel