top of page

Hearth.

OVERVIEW.

  • Role -

​​

​

  • Tools -

​

  • Team Size -

​

  • Timeline -

Systems and Physics Programmer​

​

C++

​

1

​

3 Months Ongoing

Hearth is an impulse based rigid body and particle physics engine developed in C++.
The project started as a game idea about soft body physics. During the research phase, this idea slowly devolved into a full physics engine.

 

The engine is renderer agnostic and the results on this page are rendered using Unreal Engine.


The project is still in active development.

LINKS.

GITHUB

ENGINE FEATURES.

  • Rigid body and particle physics simulation using Newton - Euler approximation

  • Physical links and constraints

  • Collision detection using primitive shapes

  • Collision handling and contact generation

  • Contact resolution for friction and frictionless contacts

  • Resting contacts

  • Sleep functionality for inactive bodies for performance optimization

  • Collision detection performance optimization using binary trees (bounding volume hierarchy) 

  • Essential math library

  • Soft body simulation (in development)

ENGINE ARCHITECTURE.

The diagram represents how a typical frame is processed. The main intention behind the architecture was to keep the different modules separate from each other by sharing data that is not dependent on algorithm implementations.

A Typical Physics Frame

  • The frame enters the PhysicsWorld class. This class holds a list of all the rigid bodies in a linked list as well a registry of force generators and contact generators.

    • A force generator is a helper base class that can be inherited from to create a force application rule (e.g., springs)

    • A contact generator is a helper class that can be inherited from to model link-like behavior between two bodies. It generates a contact similar to a collision contact and adds it to the list of contacts to be processed later.​

​

  • StartFrame() - Internal data for all rigid bodies is calculated. Most significant of this data is the inverse inertial tensor of the rigid body in world space.

​

  • RunPhysics() -

    • All force generators are processed and the forces and torques are accumulated.

    • PerformPhysicsUpdate() - Uses the Newton - Euler approximation to process the forces and torques on the body and applies the results as linear and angular position changes

    • ​Then all the contact generators are processed to check for link violations.​

    • The CollisionCoarse class is a binary tree that holds rigid bodies at leaf nodes and each node is a BoundingSphere. This class helps rule out obvious non colliding cases.

    • The potential contacts generated by CollisionCoarse are passed on to CollisionFine

      • CollisionFine first uses the seperating axis theorem to rule out obvious cases​

      • Then each potential contact is tested using PrimitiveA to PrimitiveB collision tests and contacts are generated

    • The ContactResolver then loops through all the contacts in the order of decreasing severity.

      • Each contact needs to be resolved for two violations. First the linear and angular velocity change due to the actual collision. This is calculated with the help of friction and restitution values and obeying the rules of inelastic collisions.​

      • Then any penetrations happened during the frame are dealt with as linear and angular position changes, inversely proportional to the bodies total inertia

    • Once the ContactResolver processes a contact, it needs to loop through and find all the contacts affected by this resolution and recalculate their data before looping through to resolve the remaining contacts.

Engine Architecture

NOTABLE IMPLEMENTATIONS.

The​ full source code is available on GitHub. These are examples of some algorithms I found interesting to implement.

1. Bounding Volume Hierarchies 

  • The complexity of checking every body in the world against every other body for collision detection is O(n^2). This operation becomes very expensive with increase in number of bodies in the world. Thus, a need to rule out obvious non overlapping bodies arises.

​

  • Hearth uses a bounding volume hierarchy to rule out non overlapping volumes. In this data structure, rigid bodies are recursively pushed down a binary tree and always occupy leaf nodes.

BVH.png

  • The diagram shows a bounding volume hierarchy using bounding spheres. In the diagram, the bounding sphere of body C does not overlap with the Red bounding sphere. So, we can safely rule out any kind of collision between C and children of Red (i.e., E and A)

Inserts a RigidBody into the hierarchy

Recursively checks if Other can overlap with anything down the hierarchy from this node.

2. Impulse Calculation Post Collision 

  • First, a set of coordinates in the contact space is calculated. This makes the mathematics involved in impulse calculations much simpler.

  • Based on the inertia tensors, we can work out the change in linear and angular velocity the body suffers as a result of a unit impulse.

  • The desired separating velocity at the point of contact after the contact is resolved can be calculated using the coefficient of restitution.

  • The difference between current velocity of the contact point and the desired velocity after collision is the result of the impulse acting per inverse inertia tensor.

  • After considering the effects of static and dynamic friction in the YZ plane of the contact space, the impulse can be split into linear and angular components.

Collision with Friction

Collision without Friction

3. Collision Detection and Contact Generation between Two Primitive Shapes : Box and Sphere

  • This is an example of a fine collision test and contact generation the engine performs.

  • In the diagram, the first case is ruled out using the Separating Axis Theorem

  • If the difference between closest point (red line) and relative center of the circle (the difference represented by the green line) is less than the radius of the circle, it is safe to assume that there has been penetration.

  • Expanding the same concept in the third axis gives us a method for Box - Sphere collision detection.

Circle - Rectangle Overlap

Sphere - Cube Collision

4. Particles and Particle Links

  • Particle Links inherit from the ParticleNonCollisionContactGenerator class. Which means they can generate a collision-like contact when the rules of the rink are violated. Below is an example of a rod link.

  • Particle don't have rotations but they can be linked together to generate a pseudo rigid body in cases where precise rotation and collision detection is not necessary.

Particles Linked with a Rod Link

Directional Burst Particles Simulated with The Particle System

Bounding Volume Hierarchy
Impulse Calculation
Primitive Collisions
Particles and Links
Performance Considerations

PERFORMANCE CONSIDERATIONS.

Although performance has not been the main focus so far during development, I have implemented some features as I came across them. This section showcases some of them.

1. Putting Inactive Bodies To Sleep

  • When a body is at rest, it is put to sleep. If a force is applied to it or if it comes in contacts with an awake body, it is woken up.

  • When a body is asleep, the Newton-Euler integration step does not run which also saves the calculation of inertia tensor matrix in the world space. The body can still be collided with.

  • A recency weighted mean of the body's total motion is used to put it to sleep.

  • A noticeable performance improvement was observed with this implementation. But no specific profiling has been done. 

Motion Check Run During Physics Integration

Sleeping Body Colliding with A Body In Motion

2. Bounding Volume Hierarchy and Early Out Intersection Tests

  • The bounding volume hierarchy has been described in the previous section. Any kind of performance profiling is yet to be done. The hierarchy can be an unnecessary overhead in cases where most of the simulation bodies are grouped together. But such cases are rare. Recalculating the hierarchy every time can also be expensive in case of more complex bounding volumes.

  • The engine uses intersection methods the Separating Axis Theorem to provide cheap early outs for non overlapping bodies.

Rigid Body Sleep
Intersection Tests
Reflections

REFLECTIONS

  1. The original goal of the engine was to be able to perform soft body simulations. The engine has failed miserably on that front so far.

    • The initial idea was to represent mesh vertices as particles and treat edges as springs. Then an outward gas pressure (as force per area) would be applied according to the ideal gas law, PV=nRT. The mesh would be rebuilt after the physics update.

    • But the nature of the forward Euler integration means that the acceleration is assumed to be constant during a frame. This means the springs don't exactly behave like springs and overshoot their target position each time (numerical drift). This becomes highly unstable in a highly interconnected spring mass system. like this -

2. During Collision resolution, when a contact is resolved, the change in body transform means any other contacts involving the body need to be updated for their new contact normals and penetrations. Currently, the resolver loops through each available contact looking for compatible bodies. This can be highly expensive as the number of contacts increases with the complexity of On.


3. The impulse based approach means the simulation uses lots of micro collisions to keep bodies resting against each other. This can get highly unstable in certain configurations like a stack of blocks.

FURTHER DEVELOPMENT

While the engine is fairly stable and can be used in a number of real game mechanics, this project has been a great learning opportunity and I hope to continue to develop it more and learn more as a result. Here is a short list of things I am currently looking into.​

  • Support for more primitive shapes

  • Convex collision meshes

  • Replace the contact iteration algorithm mentioned in the last section. If each rigid body can store a pointer to all it's contacts, then it would be much faster to iterate through the affected contacts.

  • Try more complex methods for the physics integration step, like the implicit Euler integration or the Runga Kutta method. And thus reconsider the approach to soft body simulation (In development).

  • More joint types for rigid bodies.

  • Integrate the engine better with unreal using more tooling.

  • Center of mass prediction for complex shapes

Resources

RESOURCES

bottom of page