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 (7) comments

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?