Search vertexes within a radius [SOLVED]
-
On 12/05/2016 at 17:18, xxxxxxxx wrote:
User Information:
Cinema 4D Version: 15
Platform: Mac OSX ;
Language(s) : PYTHON ;---------
What is the internal method that Cinema 4D uses to check for the proximity of vertexes, for example, in the Optimize command?
It checks for vertexes within a certain distance in a very fast and efficient way.
It should not be using the "nested loops" method, I guess. -
On 12/05/2016 at 21:10, xxxxxxxx wrote:
Is this related to the viewport (distance from cursor) or a general 3D spherical distance from some 3D point? The best-practice methodology will differ between these circumstances.
-
On 13/05/2016 at 01:34, xxxxxxxx wrote:
Hello,
as usual we cannot disclose any internal details on certain functionality or implementations. But if you search online you will find a lot of information on acceleration structures that are used for such tasks, also by Cinema.
Best wishes,
Sebastian -
On 13/05/2016 at 07:44, xxxxxxxx wrote:
What I did, so far, is to divide the list of the object coordinates in eight quadrants and identify the quadrant where the points are and only check against the list of that quadrant. Not perfect (and some possible candidates are missed) but for what I want, it is working.
With this new method, I already got an 87% speed gain against the old "nested for loop" method.
Can you please tell me what type of things should I search for? Any particular keywords? -
On 13/05/2016 at 08:13, xxxxxxxx wrote:
I've been trying to find the time to have a look at this subject after a few particle system overhead headaches.
I went off looking for acceleration structures after I saw Sebastian's post earlier today and got as far as this before my schedule took over:
The Octree looks interesting. Google image search of Octree shows something perhaps similar to your quadrant logic maybe?
Thanks,
Adaam
-
On 13/05/2016 at 08:54, xxxxxxxx wrote:
What I have so far is this:
I compute the min/max limits of the points coordinates of the object and find the center.
The center is cx,cy,cz
Then I create 8 lists that are the sub-sets of all the points, for 8 quadrants.ls1=[a for a in points_list if a.x<cx and a.y<cy and a.z<cz] ls2=[a for a in points_list if a.x<cx and a.y<cy and a.z>=cz] ls3=[a for a in points_list if a.x<cx and a.y>=cy and a.z<cz] ls4=[a for a in points_list if a.x<cx and a.y>=cy and a.z>=cz] ls5=[a for a in points_list if a.x>=cx and a.y<cy and a.z<cz] ls6=[a for a in points_list if a.x>=cx and a.y<cy and a.z>=cz] ls7=[a for a in points_list if a.x>=cx and a.y>=cy and a.z<cz] ls8=[a for a in points_list if a.x>=cx and a.y>=cy and a.z>=cz] ls=[ls8,ls7,ls6,ls5,ls4,ls3,ls2,ls1]The ls list is a list of all the quadrants lists.
Then, when I want to search for the distance, I calculate the index list with:
index = (4*(p.x<center.x))+(2*(p.y<center.y))+(1*(p.z<center.z))p is the point coordinates and center is the vector(cx,cy,cz)
So, I just need to search in the list ls[index]
This could be improved, right?
-
On 13/05/2016 at 09:22, xxxxxxxx wrote:
As noted by supergeordie, for general 3D distance queries, your best bet is some sort of hierarchical spatial partitioning structure (AABB tree, Octree, OOBB tree). The initial overhead is a bit steep and you must construct it carefully but the speed gains are phenomenally better than any other methods since these structures are basically nested divide-and-conquer machines. You can exclude large swaths of areas that aren't in the search very quickly.
-
On 13/05/2016 at 10:31, xxxxxxxx wrote:
I just had another idea to speed things up.
Will look into it and will report it here if it shows some good results.
Remember, I'm not a pro so all my solutions are very naive
-
On 13/05/2016 at 15:07, xxxxxxxx wrote:
If you are interested, here is a set of classes for constructing and using an AABB tree that I have used a couple times (C++!) :
http://www.kuroyumeszone.com/downloads/KDZAABBTree.zip
AABB is "Axis-Aligned Bounding Box" which means, in this case, that the boxes and sub-boxes are aligned along the World/Global axes. Instead of subdividing a space generically (ala Octree), it divides the object's space based on global splitting planes in all three dimensions. These are split iteratively to a particular grain-level forming a hierarchical tree of bounding boxes.
-
On 14/05/2016 at 03:37, xxxxxxxx wrote:
WOW!!! That is soooo complex.
Anyway, how would this new structure (if I manage to be able to implement it) will speedup the calculation of distances?
What I need is to store all the vertexes that are closer that a given distance, and the corresponding distance.
For speed purposes, I can use the squared distance without any problem.
So:If vertex A is closer to vertex B than a given distance , I must store (A, distance to B).
This for all the vertexes of a mesh.
But if A was stored, I don't need to store (B, distance to A).
However, I can't eliminate the B from the list as soon as I find distance match. Because, maybe vertex C or M or T would also need to be stored, because they are closer than the given distance to B.Is there any data structure that would be able to speed up this calculation? Would the AABB tree be of any use?
-
On 14/05/2016 at 08:08, xxxxxxxx wrote:
Hi Rui,
I don't know if this will help you or not. Because I'm not understanding exactly what you're attempting to do.
But when I wanted to rotate the selected polygons in an object. It was very slow because looping through the points array was very slow.
What I needed was a way to only process the selected polygons. And skip over the other ones that were not selected. Which is called "marking" in the SDK neighbor class.Robert showed me how to make my own marking scheme using a true/false array. And it worked great. It runs very fast even on dense meshes.
I know you're not selecting things. But you're still targeting a small subset of points in the object.
So perhaps using a marking array to skip over and not process most of the points is what you need?-ScottA
-
On 14/05/2016 at 08:45, xxxxxxxx wrote:
Here's the full code (minus serial number related classes) of my defunct CollisionDeformer plugin. It was written for R13 and earlier when people hadn't upgraded to R14+ yet (which has a built-in Collision Deformer object). It has the same AABBTree classes but shows how it was used to do quick deformations between objects. You would just need one tree for one object.
http://www.kuroyumeszone.com/downloads/CollisionDeformer.zip
-
On 14/05/2016 at 14:20, xxxxxxxx wrote:
Thank you all for the help that you are providing.
As I have it right now, it is working fine, but I wish I could make it faster. This is the result:
And, the difference between the old method (nested loops) and the new method (search in eight quadrant sub-lists) is as follows:
My current method, is as follows:
• create a list containing just the selected points or all the points if there is no selection.
• from this list, create eight sub-lists, for values of:
-x,-y,-z
-x,-y,+z
-x,+y,-z
-x,+y,+z
+x,-y,-z
+x,-y,+z
+x,+y,-z
+x,+y,+z• cycle through all the points that are in the initial list (p1).
• based on the signal of the coordinates of the point,calculate the index, to decide what sub-list to use.
• go through all the elements of the sub-list (p2).
• if a distance between p1 and p2 is less than a specific radius, store the points (p1, p2, distance) and leave the inner loop (I just need to find the first point p2 that is close enough to p1).
-----------
Is there any way to make this faster? I can't see how a data structure could improve this
-
On 14/05/2016 at 15:41, xxxxxxxx wrote:
You are basically doing a single-level Octree by dividing the points between octants. Tree-structures just go multiple levels which allow you to reduce the test space even faster. For instance, if all of the points of interest are only in one octant, the other seven octants are removed. If the remaining points are in only one section of the smaller 'octants', the others are removed (and so on). Think of it as having a bunch of nested objects with cumulative bounding boxes. If a higher-order bounding box (for a set of objects) is out of range, that object and all of its objects are ignored. You quickly end up only testing points that are (mostly) in range.
I wish that I had time to get an example using the AABBTree under your circumstances but I am working on the finishing touches for a new commercial plugin at the moment.
-
On 14/05/2016 at 16:44, xxxxxxxx wrote:
Mmmmmmm, so I ended up doing a simple (one level) octree
I will try to make it work with deeper levels, by subdividing each octant into another set of octants.
I came up to this method because I remembered about an article I read when I was 16 or 17 years old, about voxels.
Not bad, for someone who is not a professional programmer
Thank you so much, Robert. I will try to implement a deeper octree. -
On 17/05/2016 at 09:06, xxxxxxxx wrote:
I created my own implementation of octrees. I made them just 3 levels deep (I guess it is enough for what I need) and got huge speed gains
Here is a spreadsheet I created with the results from the old method (nested loops), a 1 level deep octree and 3 level deep octrees.
WOW!!!
-
On 17/05/2016 at 09:26, xxxxxxxx wrote:
I would love to see how you did that if possible Rui.
But only if it's not too much trouble.The theory of Octrees are covered a lot on the internet. But I'm not finding much code that works with C4D geometry so far.
If there is a way to show the process in C4D code it would help the rest of us.
But if it's too much code and too much trouble. Don't worry about it.-ScottA
-
On 17/05/2016 at 09:36, xxxxxxxx wrote:
I will prepare a commented snipped of the code I created.
I could have made it recursive, but I decided to make it linear.
Probably my code is not the cleanest or the most beautiful, but it is working
I have to leave now, But I will prepare a listing to publish here as soon as I get back. -
On 17/05/2016 at 10:17, xxxxxxxx wrote:
OK. Thanks.
It doesn't need to be pretty, fancy, or 100% correct. Whatever post will be good enough and appreciated.-ScottA
-
On 17/05/2016 at 11:16, xxxxxxxx wrote:
Good work, Rui! Now you see what I mean. Awesome stuff.