Satharis, on 16 Feb 2013 - 06:07, said:
It's not about memory it's about how much CPU time doing a lot of ray casting takes really.
One thing I've learned about collision and pretty much anything in games is that there is no one bill fits all way of doing things. A lot of things have cost vs precision as well as just differing in ways that apply better to a type of game, there is no real "standard" way of checking collision that is good for every type of object or gameplay. Bounding boxes are a big one but they obviously have precision issues in many cases and can have tunneling problems.
yep.
luckily, in an FPS like setting or similar, "most" objects work pretty well as bounding-boxes (and fancier objects are usually mostly cosmetic).
Quote
Anyway the broad phase and narrow phase go hand in hand, if you eliminate a lot of objects but then do a thousand ray casts you're still gonna get awful performance, especially since the way broad phase algorithms tend to work is that the collision detection multiplies in complexity as more objects move within collision range of each other, that's rather unavoidable unfortunately.
bounding boxes are often used in my case for first-pass elimination for more expensive collision checks (following the broad BSP query or similar).
most of the time, the bounding box can eliminate the collision well before having to doing any more expensive checks, and is one of the computationally cheaper checks (along with a sphere, but typically an AABB is a better fit than a sphere, so will eliminate a lot more "false positives").
like, you don't need to check collisions against an object precisely, when it is across the room, only to quickly eliminate it.
even in a large pile (say, a pile of bricks or similar), usually each brick is only in close proximity only to those bricks it is touching, so, something like an AABB can still separate each brick from most other bricks in the pile.
the BSP will not often clearly separate individual bricks, but more just eliminate checking between bricks in one brick-pile, and another similar pile elsewhere in the map.
luckily there is also a trick that if an object's net velocity gets low enough, an option is to "freeze" it and take away its internal velocity (it becomes non-moving until interacted with again by a faster-moving object), which both saves CPU cycles, and helps avoids some ugly effects (things just endlessly wobbling around, and piles of things just randomly "exploding"), but does make a slight issue if things can sometimes settle in an obviously "not physically plausible" manner (can happen if this freezing occurs too aggressively, an object can freeze leaning over an edge, or result in stacks which "should" reasonably fall over, ...).
Quote
Generally cheaper is better unless it causes major glitches, thats why a lot of games especially older ones have special areas on maps you can abuse the collision and get through the geometry, n64 was big on that.
yep, and also why I typically very rarely use meshes for non-static objects. mesh/mesh collision checks are very expensive.
most other checks against meshes are also expensive, but them being static means they can be excluded from "dynamic" checks (*1).
so, a ranking I think (for straight collision checks):
sphere: cheap (single compares), often a poor fit, usually better for "worst case"(but with a few partial exceptions);
AABB: still cheap (6 compares), often a much better fit than a sphere;
OBB: costs more than an AABB (up to 12 axis projections/24 compares), but can rotate freely (very useful for things like crates, bricks, ...);
convex polyhedra: typically cost a little more than an OBB (n*m projections, 2*n*m compares, where usually n,m>=6), but can match arbitrary convex shapes, and can usefully approximate most small non-convex objects (both work on the "separating axis theorem");
mesh object: expensive, but can represent arbitrary shapes.
so, with these later forms, a person can keep a radius and a bounding-box around, for first-pass elimination.
there are also cylinders and capsules, but they are rarely used in my case, and not particularly stable (it is easier to get good contact behavior from face-based solids, like OBBs or polyhedra, via the use of CSG operations). (mesh/mesh object collisions are also a little problematic, as I am not currently aware of a particularly good way to calculate contact forces, so IIRC they just directly push away from each other, more like spheres).
*1: in my engine:
"static" means "object will not move". it is not checked against anything else, but moving (dynamic) objects may check against it (typically, this is for things like world-geometry).
"semi-static" means "object does not move on its own", but rather its movement is controlled externally (by program code), and typically will only check against dynamic objects (most typical entities fall in this camp, which currently includes pretty much everything from players/AIs/doors/platforms/rockets/... which are instead under the control of their "movetype", *2);
"dynamic" means "object moves freely and responds to physical forces".
*2: the "movetype" system is a nasty jury-rigged mess, but ironically, was written much later than the fancier physics (simpler Quake-like physics works a lot better / more-reliably for a lot of things, where originally I tried using fancy-physics for pretty much everything), and depends a lot more on the server-side game logic (not currently available to the physics engine). note that "solidtype" deals with both sets of solids (as far as the server-end is concerned).
sadly, my fancy physics code (its own evil mess of sorts) hasn't been updated to deal with voxel terrain, so ATM it isn't really all that useful (try to drop a brick or crate directly onto voxel terrain, and it will just keep on going). I have considered fixing this, but haven't gotten to it (hasn't seemed like a huge priority). likely, as-is, it would require API-level modifications to the physics engine (API is, errm, sort-of structured in mostly the same sort of way as legacy OpenGL, as it "seemed like a good idea at the time").
admittedly, I am almost tempted more to just rewrite it all into something hopefully less of a nasty mess, like a single unified physics engine that both deals with both types of physics, and hopefully improve the API design some (great evils lurk here...), but am presently torn some between the possible options (and, otherwise, just haven't really gotten around to it).
