pyopengl-users

[PyOpenGL-Users] Collision Detections

[Yannick G. <ygi...@yg...>]

=2D----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


Hi guys,=20
   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,=20

=2D --=20
Yannick Gingras             "Do not attempt to think or depression may occu=
r"
Coder for OBB : Over-the-hill Bookable Bruin                  -- Jello Biaf=
ra
http://OpenBeatBox.org

=2D----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (GNU/Linux)

iD8DBQE/9LuyZJ8/OobqizMRAsr2AJ9O0KRny3tjeVha32XJ/qxZmIisoACeJspH
goGaNEddae4L6D9hqrp8eAE=3D
=3DqS7u
=2D----END PGP SIGNATURE-----

Re: [PyOpenGL-Users] Collision Detections

[Richard J. <ric...@op...>]

On Friday 02 January 2004 11:30, Yannick Gingras wrote:
> just a quick question, how do you do your collision detections ?

Personally, I've not implemented such a beast yet. I believe a standard=20
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=20
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=
=20
whether they're close enough to collide,
4. if you're a) using boxes and b) the boxes are a good enough approximatio=
n=20
for you, then you're done, otherwise
5. perform per-plane/line/vertex collision detection.


> I made a few quick tests with pure python implementation based on
> map() and lists to store vertex coordinates. The performance is=20
> 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 overhea=
d,=20
which is slow if you're not using a builtin function. Use a for loop instea=
d.=20
=46or 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


> 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=20
easier (and better) to optimise your code than to push it off to C or C++.=
=20
I've previously gone down the path of reimplementing core functionality in =
C=20
with some gain, but then a different approach proved to give a much better=
=20
gain, with no C code.

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


     Richard

Re: [PyOpenGL-Users] Collision Detections

[Yannick G. <ygi...@yg...>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On January 1, 2004 20:00, Richard Jones wrote:
> 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

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (GNU/Linux)

iD8DBQE/9MzfZJ8/OobqizMRAo80AKC8Q9o1Tn3pIHjgpS7hSa44CAZabACfSRzH
4vX2p67+B+ZJ66Qyy7yD7KA=
=QhW2
-----END PGP SIGNATURE-----

Re: [PyOpenGL-Users] Collision Detections

[Richard J. <ric...@op...>]

On Friday 02 January 2004 12:43, Yannick Gingras wrote:
> On January 1, 2004 20:00, Richard Jones wrote:
> > 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 f=
or
> > 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 =3D (0.0, 0.0,-0.5)
>   v2 =3D (1.0, 0.0, 0.5)
>   v3 =3D map(sub, v1, v2)

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

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


> 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=20
into code optimisation like we're talking about above :)


    Richard