KDTree or OcTree with C4D Python

gheyret

Hi everyone~
In my recent research in C4D python, I needed to do some algorithms to find nearest points.
During my research, I noticed that while the C++ SDK provides native KDTree implementation , but not in python SDK.
It would require me to build similar algorithms manually, but that's not something I'm good at, and python's performance also is a limitation. Although there are some third-party libraries available, which I think makes things more complicated.
So I'd like to ask the SDK Team if it's possible to add KDTree to python, or something like that?
Cheers!
Gheyret.

m_adam

Hey @gheyret this is on my bucket list of things I want to port it since a long time, but to be honest it's rather low-priority.

But I will keep it in mind.With that's said depending on what you want to do you may find ViewportSelect Interesting.

Cheers,
Maxime.

gheyret

Hi @m_adam , It's nice to hear that! And hope we can use it in future version in some day.

I just looked at the GetNearestPoint method of ViewportSelect, it seems to only work in Viewport coordinates? I wonder if it is possible to work in 3D space, I haven't tried it yet.

In terms of what I want to do, I want to implement Space Colonization Algorithm in Cinema 4D.
I have already implemented an inefficient version with brute force search, but its performance is too low.
I'm not sure ViewportSelect.GetNearestPoint () whether can do it.
By the way, should I start a new post on this topic?

ferdinand

Hey @gheyret,

you can project a world space coordinate into screen space with BaseView. But ViewportSelect is more meant for user interactions as its name implies.

We had this morning a quick talk about your subject, and my stance was mostly that it does not make too much sense to port something like KDTree to Python. Because while porting itself is entirely technically possible and the result is then performant (enough), it implies a technical complexity which is not. So, you are then basically able to process point neighbour hood blazingly fast in Python, but that implies processing a lot of points (at which Python sucks). Which is why I recommended ViewportSelect as a workaround for cases where you only have to lookup the neighbor of a handful of points. But for your case, you will not get very far with ViewportSelect.

Because in the end remains the fact that the popular computational geometry algorithms which could use something like a KDTree: differential growth, shortest path on a mesh, heat maps, optimal coverage (e.g., space colonization), etc., tend to be very complex computationally and therefore not very sensible to be implemented in Python. Going over ViewportSelect would make things even slower (and also imprecise).

Maxime has this still on his agenda and you might get lucky. I am of course aware that there is a wide range of what people would consider "acceptable" computation times. Technical artists are sometimes fine with a script running for 5, 10, 20 minutes; i.e., just brute forcing something. And in the end you can also write yourself at least an octree relatively easily in Python (with a then to be expected performance).

Cheers,
Ferdinand

gheyret

tend to be very complex computationally and therefore not very sensible to be implemented in Python.

yeah, I forgot the BaseView, but whatever, I agree whit you.
And this is just the beginning, I'm still in the research and testing phase.
My final goal is to write a procedural tree generator, so maybe combine L-System to improve some performance, I'll also try to write an Octree.
Thank you for your suggestion and reply.

Cheers!
Gheyret