Ruchit
Nov 14, 2010
Post id: 306110 Report Item

Hello Friends,Currently i m working on one project releted to dynamics stuff And in that i want to find nearest nearest neighbor particle of every particle.After searching too much on google i found two inersting link.
1.http://www.creativecrash.com/maya/downloads/scripts-plugins/c/kdtree
2.http://sites.google.com/a/compgeom.com/stann/
Now first of all i have no idea on how to pull this source code in maya,so first help me to compile(i have MS VC++ 2010 Express with windows SDK v7.1 to compile for 64 bit App).Reply ASAP
Thank you


Dashboard_avatar
Nov 14, 2010
Post id: 306114 Report Item

Because you do them all a sort should suffice in most cases for a quick and drity implementation. A quad/octree is probably easier to understand and implement at first. Theres nothing very special about KD trees tough, its just a octree with a alternating split direction.  Thing is this method he uses is in 2D only. And the kd tree may not be optimally suited for nearest neighbouthood search when you execute it for all nodes. IT is quite fast for random search in form search all closest to this point.

>> Now first of all i have no idea on how to pull this source code in maya,so first help me to compile

have you ever compiled ANYTHING before into maya?

Anyway your going to need to do some work to the code if you try to compile it to maya 2011.

Not much worth salvaging tough As if yoru looking for speed you really really need to rewirte major protions of the code to get it working optimally. And to be honest id try something different first. I mean if you have less than say 100,000 particles you could just use a simple sort and the do a bounding box search. As the act of finding all nearest neighbors would need you to reconstructuire anyway. 

Now if you sort in x y z order you will get a very simple structure thast still nlogn fast and searching in one go IS extremely easy*. So ist probably fast enough for a quick implementation. And since you can just pick all code ready made its rather fast as well (and you can spend the time on makeing it a node that fills in the array directly to the particle system).

* the kd tree is basically the same thing, its just optimized for random lookup. Yeah its skigthly faster because it buckets nice and all but see you may end up searching many buckets anyway for each hit.

Ruchit
Nov 15, 2010
Post id: 306124 Report Item

>>>>>>>>Because you do them all a sort should suffice in most cases for a quick and drity implementation. A quad/octree is probably easier to understand and implement at first. Theres nothing very special about KD trees tough, its just a octree with a alternating split direction.  Thing is this method he uses is in 2D only. And the kd tree may not be optimally suited for nearest neighbouthood search when you execute it for all nodes. IT is quite fast for random search in form search all closest to this point.

i made choice for Kd tree bcz it is Approximate Nearest Neighbor searching,So i think it will be like super fast train.see this
http://hosok2.com/project/dataExpansion_2/dataExpansion_2.html
i m trying to do this.


>>>>>have you ever compiled ANYTHING before into maya?

Yup, recently i compiled this source code http://dneg.github.com/dnPtcViewerNode/ for maya 2011 x64 using MS VC++ 2010 express.

 

Dashboard_avatar
Nov 15, 2010
Post id: 306128 Report Item

Yeah I'm aware of this guy. He is not the worlds most brilliant algorithms designer, ive had a chance to speak with him. For example in the example:

http://hosok2.com/project/slice/slice.html

he was using a algorithm that was O(n*log(n)) but he could have used a bucket sort for a O(n) because he was under the false assumption that this is the best one can do, which is abviously false (lucky for us or youd never get mail). He equated the statement that the fastest comparasion sort is n*log(n) but there are sorts that are based on noncomparasion.

Anwyay the KD tree is fast for random lookup of nearest neigbourhood like raytracing for instance. However since your going to test each particle against each particle ANYWAY, you can do this much faster with with a carefully selected insertion sort and some bucketisation. Ive tested this and its about 1.2-2  times faster for most data. AND its way easier to implement.

Why? Well because you need to go up and down in the kd tree. to find the nearest neighbour. This takes time IF the bucket happens to split where the neigbour is. A KD tree is fabulous when the data doesnt need to be all mined or the lookup is random like in raytracing however.

So inside one bucket the insertion sort is n*log*n + a worst case of n*n.

wheras the kd tree is n*log*n + works cas eof n*n + a additional b*n*n.

Since a tensional search is never going to go into the worst case scenario insertion sort wins on most random data. However it may in some ordered data be VERY bad indeed which is why you introduce bucketing. In the primary and secondary directions. THis way you allways have minimal amount of inter bucket comparasion need. Tryue granted the kd tree is againg slightly better in worst case scenario, but simple sort beats most situations better.

Now algorithmically they both produce the same kind of lookup. They are jsut organized differently with the sort method designed for this purpose alone. The kd tree optimizes buildup, while i optimize the organisation for searching systematically, which is what yiu want to do.

Anyway that code needs a lot of whacking to get it working so its not optimal. I just pointed out thet there are easier methods. Since youd need to change the code much anyway.

Dashboard_avatar
Nov 24, 2010
Post id: 306243 Report Item

Joojaa
This takes time IF the bucket happens to split where the neigbour is. A KD tree is fabulous when the data doesnt need to be all mined or the lookup is random like in raytracing however.


When I've used Kd trees in the past, I always stored particles as lines between their last and current positions....   

Dashboard_avatar
Nov 24, 2010
Post id: 306244 Report Item

:) Nice of you to jump in.


Hmm... not sure if that helps?* Anyway theres indeed many ways to do and use a kd tree. You can just use the kd tree to split into cells and then use those cells as buckets. A bit like youd use a octree. This is what a raytracer would do creating independent cubic areas of interest

Or in the case of finding the closest point what you do is you choose the point chosen as the exact center of the divison plane. Thsiway your doing something akin to a insertion sort of the data (but topologically different in form but can be reduced to insertion sort as my firend points it out), youd compare all points to the first athen put the closest on one side of plane in list 1 and the closets other on other side of plane**, now your testing and split coencide. Since each object now needs to just go and chek the tree for closet one a very short distance around the locality nn the tree its quite efficent most poinst would find tehir closest one in the immediate child or parent or just one or 2 step further (the closest may be on the other side of the parents split plane).

* tough that was sort of what i was doing and thst why i was slower. But then i was really using a bad example as by basis it was relly doing something WAY different.

** the thing where the kd formality of the kd tree hits in is that the comparasion AND the split is calculated simultaneously.

Dashboard_avatar
Nov 15, 2010
Post id: 306129 Report Item

If i werer you then id experiment with making a binary space partition tree thats balanced somehow, Taht might be the best solution in general.

Remeber you dont need to optimize all now. optimize good enough. Because you can waste time making perfect solutions.

Ruchit
Nov 15, 2010
Post id: 306131 Report Item

Jooja you know i m ready to cook good but problem is i don't have ingredients to start something.i trust your above post but bcz of no idea on how to make use oh that tell me wht to do.Will appreciate if you can provide Source code.




I saw three option in Mental ray for binary space partition(BSP2,Large BSP,Regular BSP),Jooja tell me r u talking abt this algorithm.Also found java applet related to this http://symbolcraft.com/graphics/bsp/

Dashboard_avatar
Nov 16, 2010
Post id: 306136 Report Item

Well if you really need a quicly done solution install numpy package it contains a kdtree algorithm thats implemented in c. So only the wwrapper would be costly. Now because you woudl dump the entire search in one go into the particle node in your node* it woudlnt matter all that much

* yes make a node. If you make a command you will suffer a very big slowdown.

PS: my KD tree was optimized for a different kind of search. when I reverted it back to original setting i indeed did get same kind of speeds if not marginally better than my tensional search with bucketing**. Because they indeed did revert to a very similliar function. Still at a quick glance it seems to me that a more complex binary space partition tree could be slightly faster, tough harder to implement

** but it was still faster when merging points that were very close, and needs no bucketing, but tahst to be expected as it can bail out so early.

Ruchit
Nov 16, 2010
Post id: 306144 Report Item

Joojaa,i know BSP tree is harder to implement for average user but i think nothing is impossible.So,lets try something great.I m starting to google it ,if you also have any good link then plz put here.
Thank you So much



Wht mean by this Error
C:\Program Files (x86)\MSBuild\Microsoft.Cpp\v4.0\Microsoft.CppBuild.targets(1026,23): error MSB4023: Cannot evaluate the item metadata "%(RootDir)". The item metadata "%(RootDir)" cannot be applied to the path "MayaAPIFromEmptyProj.lib     MayaAPIFromEmptyProj.lib". Illegal characters in path.

Ruchit
Dec 08, 2010
Post id: 306415 Report Item

Jooja finaly i made decision  to use this ANN
And also want to compile both exactly & approximate search sepreatly.can you help me for compilation??