[ODE] Question about Performance using quadspace collision

[Olle Persson]

Thanks a ton Pierre!
I changed the setup code so that I did dSpaceCollide2() once every 100 
object I added to the quadspace and now the time is down to 47ms instead of 
almost 3000ms!



>From: "Pierre Terdiman" <pierre.terdiman at novodex.com>
>To: "Olle Persson" <ollep8934 at hotmail.com>,<ode at q12.org>
>Subject: Re: [ODE] Question about Performance using quadspace collision
>Date: Mon, 12 Jan 2004 18:01:44 +0100
>
>I don't know if it's related since I didn't look at the "quadspace" code,
>but I already had this problem with a sweep-and-prune algorithm a long time
>ago.
>
>The trouble was the initialization time was not O(n) out there, but O(n^2).
>So while the running time was ok, simply building the structure took a lot
>longer. In particular, if you initialize the structure with your objects
>(say "QuadSpace->AddObject(SomeObject)") *before* setuping the object's
>matrices, they're all initialized with a default matrix value (e.g.
>identity) and each object is guaranteed to "collide" with all other objects
>at insertion time.  This leads to the worst possible O(n^2) running time,
>which can be quite large if n=5000. The number of objects is important, but
>their initial positions is even more so when initializing. That's why 5000
>objects can take less time than 1000 - the object count is only half the
>story.
>
>Now, surprise, that's *exactly* why I use a radix-based sweep-and-prune in
>Opcode 1.3 to initialize the structure, and *only then* an incremental
>version in subsequent runtime calls.....
>
>Note that I don't know if you're actually facing the same issue, but it's a
>possibility.
>
>Pierre Terdiman
>
>- Novodex AG (www.novodex.com)
>- Personal : www.codercorner.com
>
>
>----- Original Message -----
>From: "Olle Persson" <ollep8934 at hotmail.com>
>To: <ode at q12.org>
>Sent: Monday, January 12, 2004 4:22 PM
>Subject: [ODE] Question about Performance using quadspace collision
>
>
> > Hello!
> >
> > Im new to this mailing list and have a question regarding performance.
>Tried
> > to find the answer in the FAQ and mail archives but was unable to find
> > anything.
> >
> > Background: Im using ODE for collision detection only. I have a large
>number
> > (1000+) of objects that is contained in a quadspace. This space 
>represents
> > world geometry (a forest or dungeon walls) I also have another space 
>which
> > only contains one sphere representing a player avatar. When I collide
>these
> > spaces using dSpaceCollide2() function I get very good results compared 
>to
>a
> > simpleSpace. The problem is the "precalc" time to setup the quadspace. I
> > dont know if there is another way to do it but I initalize the quadspace
>by
> > calling dSpaceCollide2() once in the beginning of my application. This
>first
> > call takes a considerable time but the following calls are all very fast
>so
> > I suspect that the quadspace is actually filled with geoms in the first
> > dSpaceCollide2().
> >
> > Anyway. I run in Release mode on Windows XP 866 MHz PentiumIII and the
> > problem is that 5000 objects in quadspace gives a precalc time of 175ms
> > (which is OK) but if I have 10000 objects the precalc time is 2925ms ?!!
> > This seems a bit out of order. It doesnt matter what depth I use. Have
>tried
> > 2, 3, 5, 7 and 10 all gives around 3seconds which is too much for my
>needs.
> > Anyone know whats going on here? Havent found much documentation about 
>the
> > QuadSpace algorithm...
> >
> > _________________________________________________________________
> > The new MSN 8: smart spam protection and 2 months FREE*
> > http://join.msn.com/?page=features/junkmail
> >
> > _______________________________________________
> > ODE mailing list
> > ODE at q12.org
> > http://q12.org/mailman/listinfo/ode
> >
> >
> >
>
>

_________________________________________________________________
The new MSN 8: smart spam protection and 2 months FREE*  
http://join.msn.com/?page=features/junkmail