Annulus – Developer Diary – Week 8

Here is a summary of what I did this week!

  • Implemented Contact class, its objects are generated and managed by CollisionDetector. These objects represent collisions with their associated data, and are handled by the world.
  • Implemented Collider class, a base for all types of objects that can enter into collisions in the simulation. Implemented Circle, a type of Collider. Implemented management of colliders through the World.
  • Implemented CollisionDetector, the collision detection system which runs the appropriate tests to check for collisions, generates contacts associated with collisions and forwards them to the world for being handled.
  • Implemented a test scene with a demo of collision between two Circles.
  • Reviewed theory on collision detection using Separating Axis Theorem, and how to extend the theorem to derive contact data such as contact normal, contact point and interpenetration depth.
Advertisements

Annulus – Developer Diary – Week 7

Here is a summary of what I did in this week!

  • Implemented the World class for rigid bodies with its fixed time stepping.
  • Implemented a reset feature to all the demos. Pressing R would reset a demo.
  • Implemented Demo class for rigid bodies and set up a demo scene for visualizing rigid body dynamics.
  • Implemented the RigidBody and Orientation classes with the rotation math.
  • Implemented the integrator for rigid bodies with logic to handle both, forces and torque.
  • Visualized the performance of the integrator by adding impulses to a rigid body in the Torque Demo.
  • Implemented Force Generators for rigid bodies and tested the Gravity force generator.
  • Implemented Anchored Spring force generator. Visualized the anchored spring in the Torque Demo.
  • Implemented memory management of force generators and rigid bodies and their registration to the associated World.

World

The World class is the core class which manages the simulation. A world (exactly one) must be created before creating any rigid bodies, force generators, etc. Once the world is created it will share pointers to all the entities in the simulation and perform their update.

For now, the responsibility of the world is to update the forces generated through all the force generators registered to it each physics update. And while applying to forces to the rigid bodies, call the integrator on each rigid body. Later, the world would also perform collision detection, contact detection and collision resolution. Thus, the world update performs the update on all the physics entities in this simulation.

Rigid Body

A rigid body is the base class for all the physical objects in the simulation. It is analogous to the Particle class in the mass-aggregate engine. However, it is different from particles in its very nature. We treat rigid bodies as point masses at their center of mass. Thus, the position of the rigid body is at the location of its center of mass. However, a rigid body can have an orientation apart from its position, which I’ll talk more about in detail. Analogous to particles, it has a inverse of mass, linear damping and velocity in it. But due to the role of force which can act along paths other than the one which passes through the center of mass, it also has inverse of inertia, angular damping and angular velocity (rotation) to account for.

Similar to particles, forces can be added to the rigid body, these forces are accumulated in the force accumulator. However, rigid body’s also support adding force at a specific point on it in the world space, and this can introduce torque. Thus we have a torque accumulator as well, which can be used to solve for angular acceleration using D’Alembert’s law for rotation.

The integrator for rigid bodies works the same as for particles. However, it also estimates angular acceleration along with linear acceleration. And uses it to estimate angular velocity and the orientation for the rigid body.  Once the rotation and rotation are updated, the acceleration (both angular and linear) and cached and the accumulators are cleared for the next update call.

Orientation

In 2D, the Orientation may be represented as a real number with the value as the angle between the rigid body and the positive x-axis which increases along with counterclockwise direction. However, it is more useful to store the angle as a vector of its cosine and sine.

The orientation class provide the angle between the x-axis and the rigid body in degrees in the ranges between [0,2π]. And the user can set or get the orientation in both degrees or as a orientation vector with the x-component as the cosine of the angle, and y-component as the sine of the angle. The orientation class also has a method to transform an orientation by certain degrees.

Each rigid body has a position and orientation which together represent its transform.

Force Generators

The force generators are a mechanism to add forces to rigid body on each update call. I have implemented gravity and anchored spring force generators for the torque demo.

Each force generator registers and unregisters itself from the world and on each update call of the world, they update the forces acting on their associated rigid bodies. Since the rigid bodies have a mechanism to add forces at specific positions, they may produce torque as well. Thus, these force generators also act as torque generators. The force generators act on rigid bodies at the start of each physics update, before they are integrated.

Anchored Spring Visualization

Anchored-Spring-Demo

Annulus – Developer Diary – Week 5 and 6

Here is a summary of what I did in the last two weeks!

  • Reviewed theory on separating velocity, restitution, contact normals and impulses in order to implement contact/collision resolution for particles.
  • Reviewed resolution of collisions, resolving for both velocity and interpenetration due to collisions.
  • Implemented a particle contact resolver which resolves contacts by prioritizing them appropriately.
  • Implemented logic for accounting for resting contacts in the contact resolution in order to prevent jittering of particles.
  • Implemented contact generators which will queue contacts to the world. Implemented contact generators for rods and cables. Visualized them in a demo with particles connecting a rod and hanging through cables under the influence of gravity.
  • Structured and finished the mass-aggregate engine with memory management of particles, force generators and contact generators.
  • Reviewed concepts of physics such as Euler angles,  axis-angles, quaternions, angular velocity, angular acceleration and center of mass.
  • Started working on the architecture of rigid body dynamics.

Impulses

I had discussed in my previous post that in nature, all collisions are resolved as if they were spring-like forces. However, modelling collision resolution in form of spring like forces isn’t any useful to us as it either produces completely unacceptable results as we cannot implement extremely stiff springs (in case of solids) in any engine. This is where the role of impulse comes in. Till now I have been modelling spring forces which would affect the acceleration of an object, which should in turn affects its velocity and position. However, if we use an impulse instead, I can overcome the issue regarding stiff springs.  An impulse a force which acts on a object for a very small time which results in an instantaneous change in velocity. Mathematically, it is the product of the force and the change in time over which it is acting on the object. Furthermore, this is equivalent to the product of mass and change in velocity i.e. change in momentum.

Collision Resolution

Any collision would be generated in form a objects called Particle contacts which will be resolved by a ParticleContactResolver. A particle contact will have the contact normal and restitution alongwith the particle pointers in its data.

The contact resolver routine iterates through all the contacts produced in a physics update call in order to resolve contacts based on their priority. The priority is decided on which contact has interpenetrating particles with the minimum separating velocity. And contacts are resolved in the order of maximum priority first, since the contact resolver routine has limited number of iterations it may use while resolving contacts in order to have a good performance during the physics update.

Once the resolver routine finds a contact that should be resolved, it calls the resolve method on the ParticleContact. This takes place in form of resolving velocity, followed by resolving of interpenetration. Resolving velocity involves estimation of new velocities based on the separation velocity and coefficient of restitution for the contact. While resolving for interpenetration involves updating of positions accounting for the relative masses of the two particles in order to separate the two particles along the contact normal.

In resolving the velocity for a contact, added additional logic to check if the velocity of the particles in contact are only due to the forces acting on them (such as gravity), if yes then the separating velocity should be 0 since the two participants in the contact are in contact and at rest with respect to one another. The importance of this logic can be visualized in form of a book resting on a table. If the velocity is updated each frame due to contact resolving, then the book would bounce off the table, enter the table and be resolved for interpenetration in the upcoming frames. This jittering can be prevented through this logic.

Contact Generators

Contact generators act as collision-like things in a particle system. Logically speaking, the concept of contact normals and interpenetration is kind of absurd for particles. But treating these constraints we can simulate particle pairs which behave as rods, cables, etc.

I have implemented two types of contact generators. Rods and cables. A cable generates a contact if the two particles end up having a distance between them more than the length of the cable. This contact has a inverted contact normal which leads to resolution which pulls the two particles rather than separating them. Similarly, the rod generator generates a contact if the distance between particles is not equal to the length of the rod, also, in this case, the coefficient of restitution for the generated contact is 0, thus resulting in no separating velocity. Hence, there is just a position fix-up based on interpenetration in this case.

Both the contact generators end up queuing the generated contacts to the world which are handled by the contact resolver associated with the world.

Memory Management – Mass Aggregate Engine

The memory taken by the particles, force generators and contact generators are owned by the ParticleWorld.

However, I have implemented logic for the user to have their own preference while working with any of the above. They may choose to delete any of the objects when they want to and they will be unregistered from the world. Thus, the user may create force generators like gravity and forget about them since the world would manage their memory. However, if they choose to delete it at point of time, the world will be notified about the deletion of the force generator.

With the implementation of the memory logic, and changes in the update call for the particle world while accounting for the generated contacts and their resolution, the mass aggregate physics engine has been completed.

Annulus – Developer Diary – Week 3 & 4

A brief summary of the progress over the last couple of weeks:

  • Particles don’t have a fixed acceleration anymore, they respond to forces acting on them due to external factors which are updated each frame.
  • Implemented force generators for particles. Force generators may apply forces to particles registered to them each frame.
  • Added force generators for gravity, springs, anchored springs and bungees.
  • Implemented interface to demonstrate the force generators using SFML-2.4.2 in a Testbed project.
  • Visualized the interaction of particles in case of all the above force generators in the Testbed project.

 

Force Generators

Unlike in previous iteration, each particle now estimates its acceleration based on the forces accumulated in the integration step (using D’Alembert’s Principle). At the end of the integration step the accumulator is cleared. See code for Particle class. Thus, at the end of each integration step there is no force acting on the particle and all the continuously applied forces (such as gravity) need to be reapplied each frame.

Force generators are an automated mechanism programmed to apply forces over an extended period of time to particles. Moreover, they apply forces to the particles registered to them based on specific logic which can be programmed for each specialized force generator. I have implemented force generators for gravity, basic spring forces, anchored springs and bungees. Similarly, force generators for drag forces, buoyancy and harmonic motion can be implemented.

Each of these specialized force generators can be constructed by the user of the engine and they will automatically register to a static manager contained in the ParticleForceGenerator class. When the World calls the UpdateForces method contained in the static manager, the static manager iterates over the list of force generators contained in it and calls the UpdateForce method on each particle associated with each and every one of them.

 

Spring-Like Forces

Springs and particles can produce a range of effects such as ropes, water ripples, bridges, etc. Rather, in nature almost everything acts as springs. Collisions between solids are supposed to compress them and act as they act as if they are extremely stiff springs which try to push away each other. This approach to modeling collisions is called the penalty method.

However, if we model everything as springs, the interactions would look extremely spongy for low value of spring constants. At the same time, if we try to implement collision between solids with high spring constants, they spring constants would be really high. This is not feasible since for high spring constants, the forces acting on the particles would be enormous enough to create ever increasing oscillations which would end up sending the particles to infinity. This would also be affected by the frame rate. The worse the frame rate, the worse the oscillations would be.

 

Visualizing In Testbed Project

Any demo can be created by extending the Demo class in the Testbed project. The user can override the initialize, update and draw methods in the derived class and use it in the main program for demoing. Beware, the version of SFML used in the Testbed project only supports x86 platform.

Apart from this interface to demo different features of the engine, I have implemented three demos which are as follows:

  • The ParticleSpringDemo demonstrates forces acting between two particles connected by a spring.
  • The ParticleAnchoredSpringDemo demonstrates a particle anchored by a spring to the center of the screen and being influenced by gravity at the same time.
  • The ParticleBungeeDemo shows a particle connect to another through a bungee while only one of them is being influenced by gravity.

Annulus – Developer Diary – Week 2

Before talking about my progress in depth, I would summarize everything I did in this week below:

  • Understood what are various approaches towards implementing a physics engine.
  • Reviewed concepts of 3D math and calculus which will be required throughout the development of this engine.
  • Reviewed concepts of physics such as laws of motion which would be required to implement physics for point masses.
  • Implemented physics for point masses (particles), using Newton-Euler integration method and laws of motion.
  • Tested the damping of the motion of particles and their behavior under uniform acceleration by logging their state on the console.

The first thing to consider while making a physics engine is how to approach it and what assumptions to operate under. The first choice is regarding how to treat objects. Whether it should treat objects as a whole rigid body or as a collection of point masses (a mass aggregate engine). Developing a mass aggregate engine has the advantage of not requiring to take care of rotations, for this reason, I will start with implementing a mass aggregate system which I would be extended into a rigid body system. The second thing to consider is how to handle contact resolution, either use an iterative approach to resolve contacts without accounting for their collective effect or use a Jacobian-based approach to resolve their collective influence. The second approach is computationally expensive and might not even succeed in all the cases, for the simplicity and speed of the first approach, I will be using it instead of this Jacobian-based approach. The third and last consideration is regarding whether to use forces or impulses to resolve contacts. Some engines use forces to resolve for contacts while using impulses for collisions. I will be approaching this engine by implementing both collisions and contacts as impulses since the math for impulses is easier than the math for handling forces. Also, this impulse-based approach is suitable in terms of flexibility and can be used as foundation for experimenting with other approaches (Source).

 

Particle Physics

In a particle (point mass) system, each particle must have a position, velocity and acceleration which we will keep a track of. Refer to Particle.h inside the source code at the end of this blog post. Apart from the member variables mentioned above, each particle has a damping factor and a inverse of mass stored in it.

The damping factor is an alternate to drag in motion of any particle. This factor to the power of time passed since last update is multiplied by the velocity at the end of each velocity calculation in the integrator. Refer to the Integrate method in Particle.cpp. As in the equation, if the damping factor is 1, it means there will be no damping, and as per Newton’s first law, if there were no force acting on a particle which was in a state of motion, because of no damping, it will remain in the state of motion with the same velocity. Similarly, if the damping factor is 0, a particle will stop as soon as there is no force acting on it.

Each particle / point mass has a mass associated with it. However, we are storing the inverse of mass for several reasons. Firstly, all the equations we use, such as the second law of motion to integrate, employ inverse of mass, thus making our calculations faster. Secondly, practically there is implication of using infinite mass, i.e. something with so much mass that no force could possibly move it, if we use inverse of mass, then the expression evaluates to 0 and satisfies the second law of motion. Also, if m = 0, then this expression cannot be evaluated, this is sensible as well since there cannot be anything with practically no mass. If m = 0, then any force would make the acceleration infinite and this isn’t possible. Thus, to account for both calculation speed and theoretical logic, we store the inverse of mass inside Particle class, while making accessors and mutators for manipulating its value.

Lastly, lets discuss the integrator for which estimates the velocity and position for each particle given their uniform acceleration. As mentioned earlier, the method for integrator can be found in Particle.cpp.

 

Using integration on the expression for acceleration as per the second law, the position should be given by the formula in our integrator:

mPosition += mVelocity * deltaTime + mAcceleartion * deltaTime * deltaTime * 0.5;

However, since deltaTime, i.e. the time since last update is very small. Thus square of deltaTime is almost 0. For this reason, we can simply the equation as:

mPosition += mVelocity * deltaTime; (Used in the integrator code)

 

Also, by using the integration on second law for updating velocity, we have the formula,

ṗ’ = ṗ + at;

where, p is position, ṗ is velocity (dp / dt), a is acceleration and t is the amount of time passed.

We can update the equation above with damping factor as follows:

ṗ’ = ṗd + at;

However, the equation above is affected by the frame rate, thus we need to make the damping time dependent, we can further modift the equation as follows:

ṗ’ = ṗdt + at; (Used in the integrator code)

 

Engine Progress

  • Added Particle class with all the logic for particle physics explained above.
  • Updated World class to add support for creation Particles. It also manages the memory for the particles added into the world.
  • Added Body and Shape classes which will be used in the future when working on rigid bodies.

 

 

Links:

Source Code

Annulus – Developer Diary – Week 1

Hello World

Annulus is a personal project I started working on in this week. As a game programming student at FIEA, UCF, it is going to be the project which I will be working on through the following 8 weeks as a part of the curriculum. I will be posting updated weekly on my website and its source code is available on my GitHub.

I have always been curious about game physics and after working on a game engine in the previous semester, I knew that I wanted to attempt to work on a physics engine as since I wanted to learn more about software/engine architecture apart from programming physics. Annulus is going to be my attempt at a platform agnostic 2D physics engine written in C++!

Specifications / Objective

The specifications of the physics engine I am attempting to make are as follows:

  • A 2-D physics engine supporting rigid body dynamics.
  • Support for bodies having material properties including density, restitution and friction.
  • Support for discrete collision detection.
  • Collisions between convex polygons using Separating Axis Theorem (SAT).
  • Support for constraints, and as a stretch goal, support for handling systems of constraints.

I will also visualize the collision system in a Testbed project using SFML, a cross platform software development API.

Progress Report

For the first week, my objective was to conduct as much physics related research as possible. Decide on which algorithms I will be using and what resources I will be using as a reference. Decide an API for visualizing the project and setting it up and get the game loop running.

I was able to achieve most of the above except for some concepts of physics. I still have to read more theory on constraints and Gilbert-Johnson-Keerthi algorithm for collision detection. However, as mentioned earlier, I have concluded that I will be using SFML for visualizing the project and set up the game loop in Visual Studio 2015.

I will be using Erin Catto’s Box2D as my reference physics engine along with his material provided through GDC archives and tutorials. I have made a pass at understanding the architecture of Box2D and referred to other physics based projects as well.

Engine Progress

  • Testbed Project
    • Set up SFML.
    • Implemented the game loop.
    • Tested the update call to for physics engine.
  • Annulus (Static Library Project)
    • World Class – A class which will manage all physics entities, their allocation and releasing of resources. The user will call methods on the world object in their game loop.
    • Settings Class – Defines the settings with which define the behavior of a world, such as the gravity for the world.
    • GameClock and GameTime Class – Classes which use the chorno time library of C++ to encapsulate objects useful for maintaining game clock.
    • Integrated GLM Math library.

Handling Input From Perception Neuron

Perception Neuron is a MOCAP (Motion Capture) hardware which uses 32 little sensors called neurons. I worked on a project in a team of 6, along with another programmer to make a game using the Neuron in its single arm configuration using only 9 neurons. Check out the demo video of the game below.

Handling the input from the neuron is a simple task for both Unreal and Unity. The plugins provided by the Neuron team for both the engines are easy to understand and use. However, the issue a developer might face while developing for the neuron is accuracy of the hardware itself.

Some developers, including me experienced slight issues due to drift in the position and a decline in accuracy due to rapid movements. If a player would perform a certain action repeatedly, the neuron might behave inappropriately after some time. However, calibrating the device again solves the problem. The only issue is that you don’t want a player to have to stop playing just so that they could recalibrate their neuron.

The way I approached to this issue was that I decided to rely on input from the neurons that behave more accurately. For instance, the neurons over the thumb or the little finger seemed to lose accuracy or behave weird even after calibration sometimes.

I logged the rotations of different bones on the index, middle and ring fingers to see how they vary as the player closes and opens his hand. Using the bones that seemed most appropriate to get data on rotation of the fingers, I toggled booleans which represent whether each of these fingers are closed or open. It would be a good idea to have a margin for the rotation thresholds since the closing of hands seems to get worse over time. So the hand won’t close properly with a longer period of time of use without calibration.

Using the input from these three fingers, I toggled a boolean representing whether the hand is closed. If any two of the three fingers are closed, then this boolean is set. After testing for a while, it seemed to be a good approach to handle the player input since we could have multiple playthroughs without requiring to calibrate the hardware.

Contact me here if would like to know more about this project.