Incremental 3d Convex Hull

Thanks to some theory on http://www.cse.unsw.edu.au/~lambert/java/3d/incremental.html

I managed to script an incremental 3d convex hull algorithm.

This is a part of "in-progress" script for k-means rationalization.

It's quite fast (1000 points in cloud = 1.1 sec, amd x6), accepts multiple branches/hulls, most complex math operation is sqrt(2) :) , and its really simple to use (one input, one output) ;)

Replies to This Discussion

Permalink Reply by Mateusz Zwierzycki on October 20, 2011 at 7:01pm

Speed really depends on point cloud - if its distributed on spherical surface, its takes really long time to compute. But if point are distributed in any volume - its much faster.

100 points on spherical surface - 200 milisec

200 points on spherical surface - 1.5 sec

300 points on spherical surface - 5 sec

And If points are distributed in volume = 1000 in about 1.5 sec

Permalink Reply by Mateusz Zwierzycki on October 20, 2011 at 8:40pm

I detected some annoying bugs, and fixed them.

Here is new version of this script.

100 groups - 100 points per group = 4 seconds

Attachments:

IncrementHull3d.ghuser, 9 KB

Permalink Reply by ANGELOS on October 21, 2011 at 1:45am

SUPER!!!

Permalink Reply by Luis Fraguada on October 21, 2011 at 2:49am

Super fast test of a couple of quick points and some weaverbird. Very fun to play with! Thanks for sharing.

Permalink Reply by ANGELOS on October 21, 2011 at 3:26am

hi luis,

can you show how to use "quick points & weaverbird"?

question: is there an unroll or flatten surface component in GH (and backwords) like the rhino command?

Permalink Reply by Luis Fraguada on October 23, 2011 at 8:55am

Angelos,

I drew some points in Rhino...just some random points in space. Brought them into GH, and into Mateusz's component. Then I used some weaverbird components to subdivide, offset, thicken, smooth, etc...

Permalink Reply by ANGELOS on October 27, 2011 at 10:20am

Thanks again,

Though I hope its actually a geodesic dome,

angelos.

Attachments:

icosa_0__.gh, 17 KB

Permalink Reply by John Harding on May 1, 2012 at 4:05am

Thank you for sharing this Mateusz. Works very well, nice and concise script.

Co-planar points seem to cause a few headaches for most of the 3d convex hull libraries I've come across before. Adding a tiny bit of noise (if you can live with it) usually circumvents this and I'm pleased to say it works a treat with your script.

Thanks again :)

Permalink Reply by Mateusz Zwierzycki on May 1, 2012 at 6:13am

really nice, I thought about adding some noise, but I found it not as elegant as I would see it (thats only my sick perfectionism ;)).

since then, I made some changes to this script and now it works mostly like it has to.

There are some lacks in rhino common sdk, thats why mesh.ispointinside doesnt work. this function is crucial for inremental hull to work, so I made my own version based on some topics here on forum. My version is sensitive for changes in units precision, so it needs some more scripting.

Now it would be great to add some optimization, but first I need to pass my finals...

Attachments:

hull3d.gh, 8 KB

Permalink Reply by Mateusz Zwierzycki on May 1, 2012 at 6:38am

Its beed a while since I rewrote it so I forgot :

- function isptinside is made by David (as I remember I only made some minor changes..)

- other crucial change is in faces visibility function, particulary calculating dot product. this part needs some more scripting which will read the document precision settings...

Permalink Reply by Mateusz Zwierzycki on May 1, 2012 at 7:06am

Now I think that adding noise is not so inacurate. after you create mesh, you can substract noise values from vertices - this will return vertices to its native position without noise... so far so good, but this attempt will cause some problems - when point which is "in" mesh after adding noise would 'jump' out of mesh, and create a vertice of mesh. this will change mesh topology, but for most uses its a good solution.

Permalink Reply by John Harding on May 4, 2012 at 3:09am

Great idea Mateusz, yes that should work although you will have the topology issues as you say for the odd occasion. I can't think of a way around it because even if you run the algorithm twice (the second time with the 'random' translation in the opposite direction for each node), some "out" nodes may then move "in" and be ignored.

As you say, for most uses a good solution - especially because the random translations can be tiny so it's highly unlikely you would get an incorrect mesh topology.