BlenderPeople Development

Tracking the development of the BlenderPeople script suite.

Wednesday, November 01, 2006

Bottlenecks 

With the ground height and color tree searching moved into Python, that leaves the nearest-actor calculation as the single biggest time sucker in BlenderPeople. I know I'm not supposed to be working on this right now, but I think I've come up with a way to do this significantly more efficiently than I have in the past.

The way it works now is that every time an Actor needs to know who is closest to him in the simulation, a distance calculation is done against every other current Actor. An Actor may ask for nearest person up to four different times in a single round. This means that the average number of distance calculations (followed by a non-indexed proximity sort) is (Actors^2)*2 (two times the square of the number of Actors). The "squared" part means that as the number of Actors goes up, efficiency declines not linearly, but as a square. That's bad.

Here's my brainstorm, and what I'm working on (it may turn out to be crap, and not work, but my ideas like this usually pan out): When it moves, an Actor gives itself a three-numeral score, based on the distances from three constant, strategically chosen points within the ground area. These three values locate the actor discretely within the field of play. Then, a sort is done against the whole Actor set three times, using each of the current Actor's values in turn as the zero point for the sort, the difference from the main sort value is cached. The Actor with the lowest cumulative cache after the third round should be the closest, if my mental model is correct. With this model, Actors are required to make three distance checks (Actors*3), then four indexed sorts. On queries, no new distance calculations need to happen -- just the triple-sort.

My guess is that the difference will not be noticable on requests with smaller actor pools (100 actors with old method = 10,000 distance calcs + 200 sorts; new method = 300 distance calcs + 400 sorts), but on larger pools (2,000 actors old = 2,000,000 distance calcs + 4,000 sorts; new = 6,000 distance calcs + 800 sorts).

If this works it will dramatically increase the speed of BlenderPeople, and in turn making it a viable tool for larger and larger numbers of Actors.

posted by Roland  # 11:34 AM
Comments:
Hey thanks, so much for working on this... I have been checking out the progress and trying to learn as much as I can of the new features coming out. Glad to see the progress you are making even if its just in the thought relm. Looking forward to trying this out again when all the new feature are in the cvs. does the new NLA features, and group features help alot? Are you going to make another build? Let the community know if they can help you. Make characters, code, etc. trying to get my coding up to speed so I might be of use. Anyhow thanks....
ibkanat@gmail.com
 
Wooooow!!!
I didn't follow this project for long time (probably since end of 2004); I watch the last video (last one I seen before contain the levitating bots) and was amazed!!! It's seems realistic (except the killing is a bit fast).
I also think your idea of simulate every day life (city life), is really good idea to make present the use of it and will make the project more appealing and functional to variety of 3D artists/ productions.
It's very good to know that something like that exists.
Will continue follow and hope to get involved some time later (need to set it up first and play abit)
 
i just wanted to say how much i like your script. i put up a test of it on http://www.youtube.com/watch?v=GtygVdeStAA&eurl=

are you on blenderartists?
 
Hi,

Have you considered using Oracle Database Express Edition (XE)? It comes with Oracle Locator that allows you to store spatial coordinates, as well as spatial functions, such as nearest neighbour etc. Maybe handy to solve some of your performance issues.

Let me know what I can help with.

BTW Keep up the good work.
 
Hmm, another related problem is one of particle/atom/etc. simulations. It also is amazingly related to the segmented radix (a modified/partial radix) sort algorythm.
Imagine this 1D scenerio:
You have 20 segments, 100 objects, and a number line between 0 and 20.
You keep track of which segment an object is in and only interact based on current and neighboring segments.
Every cycle, each object checks to see if it needs to move to a different segment after interacting.
The segments are stored as 20 lists. :)
Extend to n-Dimensions. Woot.
 
Ooops forgot to leave name. And I can't find your email on here to fix it. :/
 
Hello, I have faced this same problem with games in space. Say you have 28,000 stars and want to know which one is within 10 light years? There is an easy and fast running answer to this problem.

First, in your case, you don't really need to know how high someone is so drop the Z factor.

Next, take the X,Y and divide by some number that works well for your cell size.

Lets say 2 meters but whatever you need. At this point I am not sure what you are after. So you drop the fractions and then make a list of what is in each cell. IE all the actors with the same divided X.Y. Now all you have to do is check what is in your cell and maybe the other 8 around you.

If you code this in C and you are using ints then you could just right shift a few times, that would be very fast.

Anyway, does this work for you? I have some code that you can look at if you like. I don't think it is the best code but it is way better than doing Pythagorean Theorem for every actor every time!

There is another way to do distance that might work for you also, just use trig instead and use look up tables. Also don't bother with the sqrrt, who cares the real number just the relative distance between everyone.
Hope this helps

Douglas
magick.crow@gmail.com
http://journeytothestars.webhop.net/
 
Post a Comment

Archives

02/01/2004 - 03/01/2004   04/01/2004 - 05/01/2004   05/01/2004 - 06/01/2004   06/01/2004 - 07/01/2004   07/01/2004 - 08/01/2004   08/01/2004 - 09/01/2004   09/01/2004 - 10/01/2004   11/01/2004 - 12/01/2004   12/01/2004 - 01/01/2005   01/01/2005 - 02/01/2005   02/01/2005 - 03/01/2005   06/01/2005 - 07/01/2005   09/01/2005 - 10/01/2005   10/01/2005 - 11/01/2005   11/01/2005 - 12/01/2005   12/01/2005 - 01/01/2006   01/01/2006 - 02/01/2006   03/01/2006 - 04/01/2006   04/01/2006 - 05/01/2006   05/01/2006 - 06/01/2006   06/01/2006 - 07/01/2006   07/01/2006 - 08/01/2006   08/01/2006 - 09/01/2006   09/01/2006 - 10/01/2006   10/01/2006 - 11/01/2006   11/01/2006 - 12/01/2006   02/01/2007 - 03/01/2007   08/01/2007 - 09/01/2007   12/01/2007 - 01/01/2008   01/01/2008 - 02/01/2008  

This page is powered by Blogger. Isn't yours?