CONTENTS * Abstract * General * Particles * Rigid Bodies * Total Storage * Perl ABSTRACT This file is a set of back of the envelope calculations and related ramblings concerned with determining the memory requirements of a simple computer game physics simulation, under different assumptions for accuracy of the physics and memory requirements per floating point value. Some thought is given to what effect these memory loads will have on consumer level CPU caches. GENERAL In general, all variables used in physics calculations will be stored in the same format, usually single- or double-precision floating point. The memory used to store the physics variables for a physical system will be as follows: mem = s * Nv * No s = size of a single component value (in bytes) Nv = number of variables per object No = number of objects in system Assuming IEEE formats, this comes to: mem = 4 * Nv * No (single-precision) mem = 8 * Nv * No (double-precision) PARTICLES For kinematic particle motion, Nv will be: VARIABLE NUMBER OF COMPONENTS position 3 velocity 3 acceleration 3 For kinetic particle motion, we need to consider also: mass 1 forces 3 * Nf Nf = number of forces acting on the particle Also, most forces will be calculated with at least one constant, such as a drag or spring constant: constants >= 1 * Nf So kinematic motion particles will be represented by 9 values, while kinetic motion will use 10 + 4 * Nf components as a likely minimum. If it is reasonable to recompute the forces from basic data every time they are needed, the components of the forces need not be saved along with the constants they depend on. This reduces the storage requirements to just 10 + 1 * Nf, assuming one constant per force. RIGID BODIES In addition to all variables needed by particles, rigid bodies in kinematic motion must also have: center of mass 3 angular velocity 3 angular acceleration 3 The center of mass is of course not needed if it is fixed to the origin of the local coordinate system. For kinetic motion, we need to consider also: moment of inertia 9 geometric data * The geometric data is used to calculate the radius at which forces will act to create moments; for the simplest rigid body (a sphere) this will be just the sphere's radius (1 component) but will likely be many more variables for other objects. Additional constants may be needed to calculate the various moments acting on the rigid body: constants >= 1 * Nf If the geometric data is sufficient to calculate the moments created by all forces acting on the body, and performance is acceptable, this may be sufficient. But more likely at least the radius at which each force acts will be desired: radii 1 * Nf And perhaps the moments themselves: moments 3 * Nf The worst case is then 18 + 2 * Nf + geometry data, or even 18 + 5 * Nf + geometry data, for just new values specific to rigid bodies. In addition, it may be convenient to represent certain of these variables as more complex data types (such as quaternions) to make the math cleaner; this of course would increase the memory requirements. Of course, free rigid bodies act as particles also. Not including geometric data, if we do not store the actual values of the forces and moments, we have: Nv = (10 + 1 * Nf) + (18 + 2 * Nf) = 28 + 3 * Nf If we do store the forces and moments, this grows to: Nv = (10 + 4 * Nf) + (18 + 5 * Nf) = 28 + 9 * Nf TOTAL STORAGE Plugging these formulae for Nv back into the formula for memory use, we find that between: mem = 4 * (28 + 3 * Nf) * No = (112 + 12 * Nf) * No and: mem = 8 * (28 + 9 * Nf) * No = (224 + 72 * Nf) * No bytes will be used, depending on data precision, and whether forces and moments are stored. If we assume perhaps 5 forces per object and 100 objects in the simulation, we're suddenly using between 17200 and 58400 bytes just to store pure physics data, let alone the geometric and miscellaneous other data required for each object, some or all of which may be needed as input to the physics engine. We can thus expect the physics calculations to completely swamp the L1 cache of a consumer CPU. It may then be desirable to lay out the data such that values used both in physical calculation and in rendering the simulation state can stay packed in the cache. Values used only by the physics step or only by the rendering step can be allowed to flush each other. PERL This is all much worse if native perl data structures are used. Generally all of the values for a given object would be held in individual perl NVs and then collected into an aggregrate structure such as an array or hash. Each NV uses a minimum of 20 bytes, when never used as any non-NV type. The per-object overhead for objects that are implemented as a hash (keys are shared between all similar hashes) is around: hash mem = 60 + 4 * Nb + 12 * Ne Nb = Number of hash buckets Ne = Number of hash entries Assuming that the object has no non-NV data members (an unlikely situation, of course), we can simply add 20 * Ne for the NV storage to that and get: object mem = 60 + 4 * Nb + 32 * Ne Nb should be approximately the same as Ne, rounded up to the nearest power of 2. Going back to our 5 forces / 100 objects example, we find that 64 bins are likely for the non-stored forces variant, and 128 for stored forces. This comes to: mem = (60 + 4 * 64 + 32 * 43) * 100 = 169600 bytes or, for stored forces: mem = (60 + 4 * 128 + 32 * 73) * 100 = 291200 bytes This data alone could purge an L2 cache on a consumer CPU, and is highly likely to compete with the program code itself, as well as the geometry and miscellaneous data.