[PyOpenGL-Users] Collision Detections

[Yannick Gingras]

Hi guys,
just a quick question, how do you do your collision detections ?

I made a few quick tests with pure python implementation based on
map() and lists to store vertex coordinates. The performance is
understandably really bad, I drop to 1/5 of the FPS I had before
collision detection.

Is there a way to implement a decent collision detection in pure
python or will I have to rely on C++ binding ?

Regards,

- --
Yannick Gingras "Do not attempt to think or depression may occur"
Coder for OBB : Over-the-hill Bookable Bruin -- Jello Biafra
http://OpenBeatBox.org

[Richard Jones]

Post by Yannick Gingras
just a quick question, how do you do your collision detections ?

Personally, I've not implemented such a beast yet. I believe a standard
approach is to have several levels of accuracy:

1. for all objects, determine a bounding sphere or box (your preference),
2. group those bounding objects in space using an octree to do broad
elimination of objects that are too far apart to bother each other,
3. for all objects that may be close enough, use the bounding object to see
whether they're close enough to collide,
4. if you're a) using boxes and b) the boxes are a good enough approximation
for you, then you're done, otherwise
5. perform per-plane/line/vertex collision detection.

Post by Yannick Gingras
I made a few quick tests with pure python implementation based on
map() and lists to store vertex coordinates. The performance is
understandably really bad, I drop to 1/5 of the FPS I had before
collision detection.

Note that any implementation using map() will incur a function call overhead,
which is slow if you're not using a builtin function. Use a for loop instead.
For some other optimisation techniques, see:

http://www.py3d.org/py3d_zwiki/OptimisationHints

and the links from:

http://simon.incutio.com/archive/2003/10/28/optimisingPython

Post by Yannick Gingras
Is there a way to implement a decent collision detection in pure
python or will I have to rely on C++ binding ?

I'd recommend that you first look at your algorithm - it's almost always
easier (and better) to optimise your code than to push it off to C or C++.
I've previously gone down the path of reimplementing core functionality in C
with some gain, but then a different approach proved to give a much better
gain, with no C code.

BTW, you don't *need* to use C++, unless you have a particular liking for it.
C will do fine.


Richard

[Yannick Gingras]

Post by Richard Jones
Note that any implementation using map() will incur a function call
overhead, which is slow if you're not using a builtin function. Use a for
loop instead

Strange, I thought that the map() version was alway the more efficient
as long as the lambda form was not invloved...

Sure I can kick most of my map()s to rewrite in-line. I like to
substract vectors like that:

v1 = (0.0, 0.0,-0.5)
v2 = (1.0, 0.0, 0.5)
v3 = map(sub, v1, v2)

And it help to keep some code in 2D and 3D but I guess that there is
no easy win...

Thanks for the pointers. I never tried to subdivide my world into
sectors, I guess it's time.

- --
Yannick Gingras "Do not attempt to think or depression may occur"
Coder for OBB : Old-maidish Biflagellate Brahmaputra -- Jello Biafra
http://OpenBeatBox.org

[Richard Jones]

Post by Yannick Gingras

Post by Richard Jones
Note that any implementation using map() will incur a function call
overhead, which is slow if you're not using a builtin function. Use a for
loop instead

Strange, I thought that the map() version was alway the more efficient
as long as the lambda form was not invloved...
Sure I can kick most of my map()s to rewrite in-line. I like to
v1 = (0.0, 0.0,-0.5)
v2 = (1.0, 0.0, 0.5)
v3 = map(sub, v1, v2)

Well, the performance of that approach depends a lot on what "sub" is. If it's
a function defined by you in Python, it's going to be as slow as a lambda
call. If it's a Python builtin function (say, operator.sub) then it'll be
very fast.

Note that you may want to look into Numeric Python to perform array
operations, as they're generally much faster than even using operator.sub (as
the former is highly optimised, whereas the latter is as general as it can
be).

Post by Yannick Gingras
Thanks for the pointers. I never tried to subdivide my world into
sectors, I guess it's time.

Subdividing and bounds-checking are definitely worth the effort before you get
into code optimisation like we're talking about above :)


Richard