[ODE] Question about Performance using quadspace collision

[Erwin de Vries]

One more thing. The advised way of adding a geom to the space is by setting
its position and rotation first, and then add it to the space. This is the
easiest way to ensure performance. Another way is by optimizing the
traversal code. It is sub-optimal. Take a look at the comments in the
Traverse() function. However i dont think you can squeeze much more out of
it.

----- Original Message ----- 
From: "Erwin de Vries" <erwin at vo.com>
To: <ode at q12.org>
Sent: Monday, January 12, 2004 7:31 PM
Subject: Re: [ODE] Question about Performance using quadspace collision


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