Hi my name is Kevin Yudi Utama. I'm from Indonesia. Around one year ago I found my passion on gamedev. I am mesmerized by the sand effects on Journey. I though that it is related to physics. So I decide to have a physics engine as my final year project at college. Physics Engine is perfect because the only abstraction that I use is C++ and compiler so I can learn many things by doing everything from scratch. You can found my physics engine here Falton Physics Engine
. I use many algorithm and techniques from existing physics engine like chipmunk, Box2d and bullet. My physics engine aim to let user choose various broadphase algorithm and decide which broadphase method suit their games. Currently I have implemented four broadphase algo: Uniform Grid, Hierarchical Grid, BVH and Quad Tree.
I have read many articles about data oriented design and I find it hard to apply it to physics engine. My question about this issue can be found here Data oriented design in physics engine.
I am new to data oriented design and I am currently developing a physics engine as a hobby project. I am really interested in data orinted design but I am not sure how to apply data oriented design to my physics engine. I am using Box2D as a reference and when I look at the source code, erin catto use linked list as a container for rigid bodies. The reason why he use linked list over array is stated here. This is what he stated at the forum
I could use an array of body pointers. That would have worse cache performance. First you have to get the array element, then the element data. I would also need some extra logic to ensure the array is big enough.
I'm not sure how I would use an array of bodies. If I resize the array, the pointers become invalid. I could return an index when you create a body, but then the array would have holes as bodies are freed. Traversing the body array would then involve extra logic to see if the body is allocated or destroyed. Also, it may be cumbersome for users to have to use an index rather than the object itself. If I return the current body pointer from the index, there will likely be many bugs where users hold onto that pointer and it becomes invalid.
Finally, when islands are created the set of bodies is likely no to be contiguous in memory.
I will add that when the physics engine do a broadphase collision detection, It will return a list of collider pairs that will most likely located randomly at memory. From what I understand, you need something like handle so the data can be moved around in memory. With handle, you only need to move the last object to the slot that holds the deleted object. Using handle over pointer will add an extra level of indirection which results in more cache misses. So is it really beneficial to store a set of rigid bodies or their components as array?
Edit: I believe there are parts of physics engine that benefit from storing rigid body using array. For example the integration phase. But I am not sure if the benefits outweight the disadvantages