Skip to main content
4 of 4
added 202 characters in body
kevinyu
  • 231
  • 1
  • 2
  • 7

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.

kevinyu
  • 231
  • 1
  • 2
  • 7