[ODE] Question about Performance using quadspace collision

[Erwin de Vries]

You could also try calling dSpaceClean() after adding all your geoms. It
does about the same.

----- Original Message ----- 
From: "Olle Persson" <ollep8934 at hotmail.com>
To: <ode at q12.org>
Sent: Monday, January 12, 2004 6:32 PM
Subject: Re: [ODE] Question about Performance using quadspace collision


> 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
>
> _______________________________________________
> ODE mailing list
> ODE at q12.org
> http://q12.org/mailman/listinfo/ode
>