Grasshopper

generative modeling for Rhino

# 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) ;)

Tags: 3d, convex, hull, incremental

Views: 2480

### Replies to This Discussion

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

I detected some annoying bugs, and fixed them.

Here is new version of this script.

100 groups - 100 points per group = 4 seconds

Attachments:

SUPER!!!

:)

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

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?

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...

Thanks again,

Though I hope its actually a geodesic dome,

angelos.

Attachments:

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 :)

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:

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...

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.

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.

by 筑梦NARUTO