On 04/07/2013 at 02:51, xxxxxxxx wrote:
User Information:
Cinema 4D Version: R14
Platform: Windows ;
Language(s) : C++ ;
---------
Hi!
I'm pretty new to the C4D C++ SDK and I was wondering if there are any built in acceleration structures for doing nearest-neighbour searches (e.g. some kind of BSP tree)?
It feels like pretty basic functionality but I've searched both the SDK help and this forum without finding anything. Maybe I'm just blind ;)
Best Regards,
Vidar
On 04/07/2013 at 02:59, xxxxxxxx wrote:
To be precise, I'd like to be able to take any location in space and find the closest point in a PointObject (within reasonable time ;).
On 04/07/2013 at 03:05, xxxxxxxx wrote:
Afaik there is nothing like this in the SDK. When your point object does not have more than quadrillion
points or you're not doing the search more than once, it's not a big deal to just iterate over them.
And if you need a BSP Tree, you can build your own. For a point-cloud, it is fairly simple to implement.
Best,
-Niklas
On 04/07/2013 at 04:35, xxxxxxxx wrote:
Thanks a lot for the reply Niklas!
Yeah, I'll write a simple BSP tree myself then. I just figured I'd use the default tools if there were any.
Best Regards,
Vidar
On 04/07/2013 at 09:01, xxxxxxxx wrote:
A good approach is an AABB Tree (Axis-Aligned Bounding Box Tree). This is good since GeRayCollider and most ray collider code expects the ray and normal direction to be in object space which makes it a good fit for the object and the tree doesn't need to be updated if the object changes transformation with respect to global space. So, you can translate and rotate the object without rebuilding the tree!
If you need code to build and use one, I have it for one of my plugins.
P.S.: Yes, many other 3D CG applications have de facto space partitioning for ray intersections/collisions. On my wish list is for them to include a GeRayCollider with options for this built in.
On 05/07/2013 at 03:29, xxxxxxxx wrote:
I went with a k-d tree since the implementation is quite simple and I'm just dealing with nearest neighbor searches in a point cloud.
What you said about using a BVH and not needing to update the tree when the global transformation changes is a great advantage. However, isn't this true for BSP trees too as long as they're built in object space? I might have misunderstood what you were saying :)
I'd love to take a look at the AABB Tree code if you're willing to share it. It would be great to see some code (apart from the SDK samples) written by someone who's experienced with the SDK.
Best Regards,
Vidar
On 05/07/2013 at 05:07, xxxxxxxx wrote:
An AABB Tree is a type of BVH and BSP. It is just a specific type where the tree starts at the object's local bounding box and subdivides from there.
The code, with sample usage code, can be downloaded here:
http://www.kuroyumes-developmentzone.com/wp-content/uploads/2013/07/KDZAABBTree.zip
It has some specializations in the raycollider but you can always substitute the GeRayCollider by making the appropriate changes in the KDZAABBTree files.
On 06/07/2013 at 04:23, xxxxxxxx wrote:
Thanks a lot for the code Robert!
To clarify my last post, when I wrote BVH I was refering to the AABB tree (which I understood as being a BVH). Sorry for the confusion :)
As a minor note I don't think a data structure can be both a BSP tree and a BVH at the same time, can it?.
With that said I haven't had time to read your code thoroughly yet so I could be talking out of my ass.
Best Regards,
Vidar