I am working on a game making (or really just general program making, but my question applies to games) DLL for opengl. It is almost done but the collision detection is a little bit slow since it has to calculate bounding boxes for each object repeatedly. I was thinking of storing six extra variables for each object (left,right,top,bottom,near,far) to remove the need for those calculations. The thing is that that will add (c++ code, compiler dependant) 6*sizeof(float) bytes to each object. My question is, on average how many objects do most games have in them (an object consisting of a list of triangles in 3d space that are bound together), and how much RAM taken is too much? Basically should I add the six variables to increase speed but increase memory, or not?
The thing is that that will add (c++ code, compiler dependant)
6*sizeof(float)bytes to each object. My question is, on average how many objects do most games have in them (an object consisting of a list of triangles in 3d space that are bound together), and how much RAM taken is too much? Basically should I add the six variables to increase speed but increase memory, or not?
A classic space-time tradeoff... really, it depends on the specific program and what you want out of it. If you require a high framerate, speed is probably more important. I'd say for a game-type situation, you'll probably want to take the memory hit.
For example (if I remember correctly), Chipmunk caches bounding boxes.
A useful approach if you're not sure which is better is to profile two versions of your code--one with the caching, and one without. Measure execution time and memory usage, and see what the difference really is for your hardware.
Some quick back-of-the-envelope calculations might prove educational as well. Let's be pessimistic and assume double-precision floats--that's 48 extra bytes per object, or one megabyte of extra storage for each 21,845 (and 1/3) objects.
I can't quote you statistics on how many objects a typical game might have, but remember: As the number of objects goes up, the number of relationships between them increases exponentially. For large numbers of objects, the dominating factor will be the choice of collision detection algorithm, not the mechanics of comparing two objects.
Getting back on topic... I'd say cache the bounding boxes. If your object count threatens to hit tens of thousands or more, then you might have something to worry about.
Thank you very much... I am wondering what you mean by collision detection algorithm. I am using a ton of math for point-by-point collision detection (using triangle-ray collision algorithms) and very little math for bounding box collisions (obviously). I have no pruning implemented as I do not know of any pruning algorithms... does anybody have any suggestions on good algorithms to help speed up my collision detection?
Thank you very much... I am wondering what you mean by collision detection algorithm. I am using a ton of math for point-by-point collision detection (using triangle-ray collision algorithms) and very little math for bounding box collisions (obviously). I have no pruning implemented as I do not know of any pruning algorithms... does anybody have any suggestions on good algorithms to help speed up my collision detection?
I'm thinking of things like space partitioning, spatial indexing, sweep-and-prune algorithms--anything you can use to avoid actually comparing a pair of objects.
You might investigate some existing physics libraries (for example, ODE and Bullet) to see what kind of approach they take.
Based on what I read, it seems as though the general technique is to sort the objects by proximity to the object being sorted and then starting at the start of the sorted array, check bounding boxes, then if a bounding box intersects check precise collision. I will now implement that. Thank you very much!
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.