[ODE] Question about Performance using quadspace collision

[Pierre Terdiman]

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
>
>
>