Medial Packing

Comment

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.

Source : http://www.geom.uiuc.edu/graphics/pix/Special_Topics/Computational_...

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:

http://hal.inria.fr/docs/00/60/65/16/PDF/Freestyle.pdf (Fig. 6)

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.

How could we get the best of both worlds?

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

• ‹ Previous
• 1
• 2
• Next ›
• Page