Thomixioso Show full post »
viki164
Just found out through a friend : 

http://www.creativecrash.com/maya/plugin/kdtree

Quote 0 0
viki164
viki164 wrote: I hope its still not too late to request this stuff from Autodesk.
looks like even 3ds Max has it :
 

Even Nucleus uses KDtree for most particle operations. Don't understand why its not exposed as a command/node for the users. It would be really useful to have it !

Using expression is not always efficient when dealing with high particle count & it is hard to get the indices of the particle that was previously emitted. As being api noob I could only rely on developers to have this integrated or available to us.

 

Quote 0 0
MOAB
Hi Peter and everyone,

Don't really know if that problems has been solved or not but for a good kdTree search library I often use is Nanoflann : https://github.com/jlblancoc/nanoflann.

It's really fast and accurate and you can retrieve the distances, the IDs....
You have two options for queries : knnSearch() or radiusSearch()
Everything is well documented (check exemples on the website)

I also created a quick Maya API command to create particle advection using nanoflann... so maybe it might help you a little bit (it's not perfect but it works)
Quote 0 0
pshipkov
Thanks for the information and the code. Appreciate it.
Adding generic kdtree/octree this functionality is on my to-do list.
So, this comes right on time.
Next SOuP release will be in couple of days and then will take a closer look at that stuff.

The main reason i didn't implement kd-tree functionality in SOuP already is that Maya completely lacks the ability to work with this data. Ideally we need a set of nodes to fully leverage what kdtree/octree provides.
With command we can workaround the lack of such interface and script the logic needed to use the data, but that can quickly get slow and also it goes against many things we enjoy from the procedural nature of nodal graphs.
Why i am saying all this ?
It will be a bigger effort than it looks.
I have an ANN implementation here, but it is not very useful, at least i don't like it.
If you have any ideas about how a set of nodes may look like, functionality, data structure, workflow, etc., please let me know. We need to figure this out first, before working on implementation.

Again, thanks for the info and code.
Quote 0 0
MOAB
I don't know if you know that guy : Jose Esteve http://www.joesfer.com/
If I remenber correctly he developped a bunch of nodes to create "Growing organic structures" (he used kdd tree...) . Maybe it can also help you to implement that with nParticles : http://www.joesfer.com/?p=46

The source code can be found here : https://github.com/joesfer/Grower
Quote 0 0
pshipkov
I have the feeling that i visited Jose's blog in the past.
Thanks for the links.
Quote 0 0
pshipkov
MOAB and Viki,
looking at the calendar here and my SOuP to-do list.
I think i will integrate MOAB's command in the meantime and then take the needed time for a well integrated KDTree system in Maya as part of the nodal graph.
Any concerns ?
Quote 0 0
MOAB
Originally Posted by viki164
I hope its still not too late to request this stuff from Autodesk.
looks like even 3ds Max has it.


This is true that 3dsmax has kdtree search inside ParticleFlow but it's quite limited in fact (the returned values are limited). You can't query values for several particles (only for the closest one). Moreover Particle Flow is not multithreaded. A better alternative but not free is Thinking Particles. You have two interesting nodes that perform kdtree search.

First one is the PSearch :
TP_PSearch.jpg 
Next one is the PPassAB :
TP_PPassAB.jpg 
It would be nice to have the returned values like in the PSearch Node and with the attributes (interface) of the PPassAB.
Quote 0 0
pshipkov

The problem with this approach in Maya is that this is a visual programming graph.
It is executed as a loop for each particle in the array.
As a result you get one set of output values uniquely tied to the current particle in the loop.
In Maya we cannot have that as part of DG. Eventually Bifrost will provide it, but the whole framework is still kind of WIP, so we don't bother with it until it solidifies at some point in the future.
I hope this makes sense to you.

My main concern with the Maya implementation is that we have few options that suck in different ways:

- we have a node that takes point cloud and then outputs values for each point. So we have to have multi-array attributes on the ouput like this:
input with 10 particles      output multi-array:
                                                    point[0]
                                                          array with nearest point ids
                                                          array with nearest distances
                                                          array with furthest point ids
                                                          array with furthest distances
                                                          array with ordered point ids
                                                          array with ordered distances
                                                          ...
                                                          array with point attributes (for example rgbpp)
                                                          ...
                                                          array with point attributes (n-th point attribute)

                                                    point[1]
                                                          array with nearest point ids
                                                          array with nearest distances
                                                          array with furthest point ids
                                                          array with furthest distances
                                                          array with ordered point ids
                                                          array with ordered distances
                                                          ...
                                                          array with point attributes (for example rgbpp)
                                                          ...
                                                          array with point attributes (n-th point attribute)

                                                    point[n]
                                                          array with nearest point ids
                                                          array with nearest distances
                                                          array with furthest point ids
                                                          array with furthest distances
                                                          array with ordered point ids
                                                          array with ordered distances
                                                          ...
                                                          array with point attributes (for example rgbpp)
                                                          ...
                                                          array with point attributes (n-th point attribute)


As you can see the amount of data we have to output will balloon enormously. Allocating these multi-array attributes will cost a lot of cycles. Imaging point cloud with 100000 particles. At every step we have to output data for each point. If we assume that we have 10 mandatory output attributes + arbitrary number of per-point attributes (let's say 15 more) that's 100000*(10+15), or 1,000,000 to 1,500,000 attributes containing arrays !
Also, the format of data will be hard to work with for particle expressions and other procedural things, because it will take logic that is hard to embed in a node or command to extract the data above.
There is stuff like that in SOuP - for example how boundingObjects interact with various other nodes. Another example is multiAttributeTransfer node. List goes on.

- option two is to have a node that takes a single vector (point in space) and a point cloud and then outputs data only for that point. This is more like a command but implemented as a node. Not very useful for iterating on points as part of the procedural graph.

- third option is to keep it as a command - similar to what you have. In this case we have to rely on MEL to interface with the data - this is less than ideal because of performance issues. You have to have an expression, pyExpression or point node where you can implement the logic.

For all options above we have to support not just particles but anything that can be associated as object with components in space - like mesh vertices, fluid container voxels, nurbs curve CVs, etc.


One possible way, that i think will work better than the ones above, is to create a node that handles the point cloud inputs/outputs and also have an input(s) with "lambda" "expressions". I need to take my time to figure out how this will work in a practical way for production cases without the drawbacks of the other mentioned methods.
That's why i proposed that we can slap the kdtree lookup command in the meantime as a temporary solution before starting on something more robust in the future.
Or maybe Bifrost will happen sooner than later and we can do it there in the same manner as Thinking Particles  /  Particle Flow.

Quote 0 0
pshipkov

Ok, here is what i think may be a good solution.

We have a node with 2 inGeometry attributes. Each attribute can accept vectorArray (particles, voxel grid, etc), mesh, nurbs curve, nurbs surface, paintfx - so we can plug stuff in without any additional steps for data conversion.

The node will output the next data sets:
- counts (int array - how many points from input 2 are related to each point of input 1)
- closest point ids (int array)
- closest distances (double array)
- furthest point ids (int array)
- furthest distances (double array)
- average position (vector array)

The outputs in bold font will have varying length based on the "max radius" parameter below.
So for point 1 we may have only 3 related points, but for point 10 they can be 100, etc.
Without using "max radius" these arrays will have length = number of input points * number of related points.
One exception to this rule will be when the second point cloud has less points than the number_of_related_points value. In this case the arrays will have length = number of input points * number of points in the second point cloud.

- number of related points (int)
- max radius (double) - to limit the lookup


From that point it will be up to the user how to use this data. The main application is obviously mapping attributes between the two provided point clouds. There are bunch of tools in SOuP that can be used for that, like - expression/point/pyExpression nodes and other lower level ones.

Let me know if you have any suggestions.

Quote 0 0
rolfcoppter
Hey Peter,

I have been testing the KD node out and it is Awesome. I have a suggestion and question about it. First, i think it would be helpful to add ignore same point option. If I want to look up closest points within the same point cloud it finds the points right on top of each other first. It would be helpful to be able to ignore points right on top of each other if needed. Also, I'm just wondering what the output of outIDPP looks like. Is it outIDPP[0] = (IDX,IDY,IDZ) or can you provide and example/

Thank You,
Jordan
Quote 0 0
pshipkov
I like your suggestion.

About your question:
the kdTree node outputs set of mandatory data that describes the mapping between source and target point clouds.
if for given target point were found 10 source points they will be sorted based on distance to it.
so the outIdPP will contain the point ids accordingly: 5, 3, 10, 100, 1, etc
outDistancePP will contain the distances: 0.1, 5, 10, 11, 25.3, etc
outCountPP will contain the number of found source points for each target one.
So if we have 3 source and 2 target points and the settings don't limit the search we will end up with data like that:
outCountPP: 3, 3 (3 source points for each target one)
outDistancePP: 0.1, 0.2, 0.3, 0.15, 0.2, 0.35 (the first 3 distances are for source points related to the first target point, the second 3 are for the same 3 source points related to the second target point)
outIdPP: 1,0,2, 2,1,0 (3 source points for each target one)

and so on.


Quote 0 0
rolfcoppter
Awesome peter thanks for the explanation that really cleared it up for me.
Quote 0 0
JeremyR
Request: Change KDTree name to nearestNeighbour. 
2 cents
Quote 0 0
pshipkov
That ship sailed already :)
Quote 1 0

Add a Website Forum to your website.