Collision Detection, Linear Algebra, and Panda3D

[Hippo]

I've been learning linear algebra to build a more robust collision detection system (one that relies on vectors, points, rays, spheres, and cubes); I got it up and working about three or four days ago. Then, while exploring some code for camera controls, I landed upon the Vec3 object--and realized that Panda3D already handles a lot of linear algebra equations for you. On top of that, it's got premade collision tests for a ton of primitives!

So, crap. Now I'm kind of stuck between a decision of trying to understand Panda3D's related class objects or just relying on my own code. The former has the advantage of deeper integration--no need to make any messy wrappers to turn my points and vectors into formats that Python3D objects will understand (not that it's hard; the objects understand tuples, after all!). There's also probably the simple fact that Panda3D is very likely to do all the stuff I'm doing with higher levels of efficiency (at the moment, my collision engine can handle about 600-700 cubes--each with a volume of 10--moving within a 500x500x1000 space by a random vector of three 'units' length every frame--without noticeable slowdown, and no apparent collisions. I have no idea if this is good or bad. The number flies up when the majority of those objects aren't moving, of course).

In trying to understand the Panda3D API in reference to these objects, though, I'm encountering some problems. Like the Hpr setting--I get that it's a rotation, but how can I set it to a normalized vector without getting weird results? I know lookAt() will get me whatever rotation I need, but I'd like to know how to set the rotation of an object by a vector manually. EDIT: Actually, reading Vec3 now, I bet it's not working because I'm not making it a zero-length Vector before attempting to assign it to the camera's Hpr!

Another question--one of the optimization methods I set up for collision detection of cubes was creating an inner and outer sphere for each cube (inner is contained by the cube; outer contains the cube) and, for every collision test, asking whether or not the given object's outer sphere overlaps with the outer sphere (no? no collision) and the inner (yes? collision). I figure checking for sphere collisions is way cheaper than more complex primitives since it's basically just a quick and dirty radius check (is the vector between their two points greater or smaller than their combined radii?). But if I switch over to Panda3D's collision API, I don't want to do this check if it's already instituted (or if there are better, quicker checks already in place). Does the collision API for cubes include such a check? Is there any worth in instituting it?

Sorry for the abundance of questions; I realize I could find the answers myself by experimenting, but that would take a lot of time, and the answers to some of these questions is directly relevant toward my decision whether or not to switch over to Panda3D's vector, point, and primitive classes instead of using my own!

[Thaumaturge]

I think that I might be able to help with an explanation of "Hpr".

First of all, based on my reading of your post, you seem to expect it to be a spacial vector - perhaps a vector oriented in the direction represented by the orientation in question? If so, then, if I'm not much mistaken, this is incorrect.

As I understand it:
The letters of "hpr" stand for "Heading", "Pitch" and "Roll", and represent three angles, one each about each of the three main axes. If I recall correctly, "Heading" is rotation about the z-axis, "roll" rotation about the y-axis and "pitch" rotation about the x-axis. (Note that these axes are relative to a given NodePath's coordinate system; I'm not sure, offhand, of what the default is - presumably either the NodePath being modified or render.)

The analogy, I believe, is that of an aircraft, and using a z-up, y-forward coordinate system: one's heading is the direction in which one is moving - that is to say, one's rotation about the up- (i.e. z-) axis. Pitch is the degree to which one's nose is pointing up or down - that is to say, one's rotation about the x-axis. Roll, finally, is the degree to which one's body and wings are tipped to one side or another - that is to say, one's rotation about the y-axis.

(In a sense one's "hpr" is a vector, but one in a rotation space, I suppose, rather than a "physical" space.)

[edit]
As to collision, if I may ask, have you looked at the "Physics" section of the manual? You may find at least some of your answers there.

In particular, I believe that Panda3D has integration with the Bullet physics engine, which may suit your purposes.

I also see reference to wrappers for other engines, as well as integration with ODE.

[Hippo]

Oh, yeah--I think I see what you mean with Hpr. I just need to convert the vector into an angle (well, three angles to be precise!). But to do that, I need another vector to use--the vector that represents the camera's default heading, I guess?

I'll start chewing through the documentation for Panda3D's Physics engine--at a glance, it sounds like it'll do everything I'm aiming to do. Thanks!

[coppertop]

But to do that, I need another vector to use--the vector that represents the camera's default heading, I guess?

Pretty much, yes. You should make sure the vector is in the right space, of course.

I'll start chewing through the documentation for Panda3D's Physics engine--at a glance, it sounds like it'll do everything I'm aiming to do. Thanks!

You should probably use Bullet instead, really. It's just better, faster, more feature-complete and more future proof. The Panda's built-in collision detection and physics should have that written on every one of their manual pages -- "it's nice for some stuff, but what you really want 99% of times is Bullet".

[Hippo]

Hm!

With that in mind, one of the methods I was using to optimize the number of collision detections was by culling the list of objects to check through a sort of 'macropoint' scheme. When objects are created, they're added to a set that's stored as a value in a dictionary where the object's point (with all of its components scaled by a fraction, then rounded up into integers) is a key. So if my scale is 1/10, an object at 'Point(30,50,100)' would be stored in the set that's unlocked with the tuple key (3,5,10). When objects are moved, the code checks to make sure the object should still remain a member of that set, and if not, moves it to the set with the proper key.

So object collision consists first of taking an object's 'macropoint'--the fractionally scaled components that correspond to its current point--and generating a set of keys that are adjacent to this macropoint. I call the resulting set of keys a 'macrokey', and it's what you use on the dictionary to get a set containing all the objects which might possibly collide with this one.

The optimization came from the idea of specializing macrokey generation to include vectors--so when you asked to generate a macrokey for a macropoint with a Vector of xyz, it would return a macrokey that only contained the macropoint of the object and macropoints that are in the direction that the object is moving--since we don't need to look at macropoints behind the object.

I'm mentioning all this because I also want to see if, by switching over to Bullet, I'd still include this culling method, or just settle on keeping all my objects in one set and letting Bullet take care of the optimizations (does Bullet do something similar to this? Does it do something better, and would this process interfere with it?).

(Also, I greatly appreciate the help!)

[coppertop]

Bullet is a full featured (well, almost, but I took care of the missing character controller on the Panda side) physics middleware for games. It's optimized and fast. You don't need to do anything else with your scene other than throwing Bullet at it and letting it do its job. Also, it's doubtful that you can come up with something better, faster and more robust given how much time and thought went into Bullet.

From the Bullet manual:

The collision detection provides algorithms and acceleration structures for closest point (distance and
penetration) queries as well as ray and convex sweep tests. The main data structures are:

* btCollisionObject is the object that has a world transform and a collision shape.

* btCollisionShape describes the collision shape of a collision object, such as box, sphere,
convex hull or triangle mesh. A single collision shape can be shared among multiple
collision objects.

* btGhostObject is a special btCollisionObject, useful for fast localized collision
queries.

* btCollisionWorld stores all btCollisionObjects and provides an interface to
perform queries.

The broadphase collision detection provides acceleration structure to quickly reject pairs of objects
based on axis aligned bounding box (AABB) overlap. Several different broadphase acceleration
structures are available:

* btDbvtBroadphase uses a fast dynamic bounding volume hierarchy based on AABB tree

* btAxisSweep3 and bt32BitAxisSweep3 implement incremental 3d sweep and prune

* btCudaBroadphase implements a fast uniform grid using GPU graphics hardware

The broadphase adds and removes overlapping pairs from a pair cache. The developer can choose the
type of pair cache.

A collision dispatcher iterates over each pair, searches for a matching collision algorithm based on the
types of objects involved and executes the collision algorithm computing contact points.

 btPersistentManifold is a contact point cache to store contact points for a given pair of
objects.

Plus, Bullet is equipped with continuous collision detection, which is essential for stable physics simulation in real time. You honestly don't need to worry about speed. Bullet powers Grand Theft Auto 4, it'll be good for you too .

[Hippo]

Oh, yes, I absolutely figured it was way better than any scheme I could come up with--my main concern was whether or not the way my objects were being built and culled would work with it, or would end up working against it. Ie, should I get rid of my scheme entirely and just let Bullet do all the work for me? Or should I let my code do a little of the work and send it to Bullet to do the rest?

But the more I'm learning about Panda3D and its various integrations, the more I'm realizing that a lot of my wrappers and coded objects aren't necessary; Panda3D--and from what I'm extrapolating from your posts, Bullet as well--will take care of everything I'm trying to do. As you said, it's probably going to be more optimal on the order of several magnitudes to just let these programs do their thing, and to design my code to stay the hell out of their way.

My approach so far has been to use wrappers to hammer these things into tools my code can use (creating a NodeWrap object to translate my objects into Panda3D nodes, for example), but from what you and others have implied (and from what my shallow--but slowly increasing!--understanding of Panda3D has taught me), I'll probably get a lot more out of this by rewriting my code to work with them rather than try to command or out-wit them. Ie, rather than making nodewrappers, just use Panda3D's nodes directly.

(Regrettably, doing the latter effectively means understanding other people's code at a much more intuitive level--and that's a big weakness of mine. But it should be good practice nevertheless!)

[Hippo]

Also I am probably really exposing my cluelessness by mentioning this, but when I try to import bullet, I'm told there's no bullet module in panda3d. Ie, the following line at the start:

Code: Select all

from panda3d.bullet import BulletWorld

Nets me the following error:

ImportError: No module named bullet

I'm running panda3d 1.7.2.

[enn0x]

https://www.panda3d.org/manual/index.php/Physics

Bullet integration is available from 1.8.0 on.

[Hippo]

Oops! Missed that; thanks!