GH2 Octrees

Today is the first time GH2 code is running as a Rhino plugin. I just finished writing a new OcTree class and UnitTesting just doesn't cut it.

Don't get excited, there is no interface at all yet, it's just a test command using regular Rhino interfacing.

33 members like this

View Full Size

Tags:

Comment

You need to be a member of Grasshopper to add comments!

Comment by Arend on December 4, 2014 at 5:26pm: I've just found a relevant and interesting read about OpenVDB - how do they handle this in in sparse voxelgrids. (Be sure to bring some additional memory banks ) http://www.openvdb.org/documentation/, the introduction PDF is a good read.

Comment by Christian Schmidts on November 13, 2014 at 11:44am: gh2 - sorry cant prevent myself from getting excited :)

Comment by David Reeves on November 13, 2014 at 9:06am: It's alive!

Comment by David Rutten on November 13, 2014 at 4:55am: RTree doesn't allow for nearest (group) search, farthest (group) search, it's not a generic type so you have to keep a separate mapping between your actual data and your spatial data, it doesn't store its items in an indexable fashion, it doesn't allow for exclusion of specific items (which is useful if you want to find the nearest neighbours in an entire pointcloud for example), it doesn't allow for clipping plane exclusions, minimum and maximum search radii, etc. etc.

My goal for this particular class is that it behaves just like List<T>, so that you can use it to just store data as you would normally, and all the spatial bucketing smarts that speed up searches are completely hidden from the user.

Of course the big drawback about OcTrees is that they can only handle point-like data. RTrees can handle data which has a non-zero size, so I'll probably have to implement that as well.

Comment by Nick Tyrer on November 13, 2014 at 4:55am: David S, that was actually going to be my follow up question, using Octree for Marching cubes to reduce value field. When i was doing models like one below, i ended up using spherical shapes as it was easy to limit what points i needed to generate values for. (remove all values that are too close to centre point or too far away).

Comment by Arend on November 13, 2014 at 4:37am: Exciting stuff david! Just curious: what were your considerations to for example not use the RTree from rhinocommon - and to implement your own?

Comment by David Rutten on November 13, 2014 at 3:40am: I'm not storing adjacency. I'm not even storing parent relationships, only child relationships. The tree logic is immutable and so has to be rebuild every time the points change. The idea is that this only really makes sense if you're performing *lots* of searches on the same data. The nodes are also optimized in that empty nodes are missing, node regions have been shrunk to only be as big as they need to be. These optimizations make the concept of adjacency somewhat fuzzy.

If you want to track a dynamic collection of points, it seems to make more sense to have an equisized spatial grid, as points can be inserted and removed from it without degrading the balance.

Comment by David Stasiuk on November 13, 2014 at 3:03am: Does this one track adjacencies between the leaf nodes? I was playing with Octrees when I was working with marching cubes, hoping to integrate the two and limit the sampling grid, but was having a hard time finding good documentation for navigating relationships between leafs.

Comment by yj on November 12, 2014 at 8:17pm: I've always thought that spatial division algorithm would be an amazing way to document design iterations. like each point is a place holder for an instance of a specific parameter set. and it would be so amazing to be able to document iterations in this manner. and since there would be a tree structure between the points one can restructure the tree by a given parameter in a graphic space. for this to be possible, it requires a component that reads and writes information about a geometry. I feel like computation time is a valuable resource that shouldn't be wasted. if google had to evaluate websites in terms of relevancy everytim a user googles, I am not sure if we would be googling as much.