Day 156: Collision testing

Today I tested the collision detector. Or at least I started to, because I've not tested plane collisions yet, and also I've just tested if the collisions occur, not if the contact point is correct.
I'll probably do these things tomorrow.

So, today I checked sphere-sphere, box-box and box-sphere collisions. Each one of them uses a different technique, so it is a very good result that all of them are working nicely.

This testing also forced me to put together different parts of the engine, and I found problems and things that needed to be changed, and it's good to found them early on. I also spent a bit of time fixing a bug in the box-box collision, which also allowed me to better understand the SAT.

In the gif you can see 2 spheres and 2 boxes, and how well the collision engine detects the collisions.

Day 155: Testing

Today I started to study the basics of contact resolution for rotating rigidbodies, but I decided to stop for a moment in order to test a few of the system I've already implemented.

I started by creating a scene in which a few gameobjects are moved through their rigidbodies, and everything went fine. I also applied spring forces to them, and they work perfectly even if the attach points are not centers (which means that the integration of the torque is working as well).

I also implemented a InertiaTensorGenerator class that returns the tensor for the most common shapes (only box and sphere for now).

The main change I made today was moving the Primitive class inside the rigidbody as a vector. Basically each rigidbody now contains an array of primitives, while in the book I'm following it's up to the programmer to create both the bodies and the primitives, and handle them separately.

Tomorrow I'll probably test the collision system, which is the part that scares me the most. I will not test the BVH, because I've postponed that work to the end, along with the octrees. In the gif it is possible to see 2 springs that connects 3 cubes, and the corrent integration of both position and orientation.

Day 154: SAT

Today I implemented the box - box collision with the SAT theorem.
The idea behind it is to check whether two objects are intersecting when projected onto an axis. If they do on every relevant axis, then they are colliding. The relevant axis are quite a lot: all the axis parallel to each face of the two objects, or to the cross product of each pair of edges. Thankfully for a cube the number of axis to check is just 15 because many of them are duplicated.

Honestly this was the hardest part until now, and I struggled to understand exactly what was going on. In the end I understood almost everything about the SAT, but the real problem was after that: i didn't quite get the function to find the contact point between two colliding edges. I struggle with it quite a bit, then decided to just use it as it is, and go back to focus on it while the engine will be running (i will probably also try to add other pair collisions, like box and point, because I really don't feel confident that I've understood enough of this part, so it will be a good excercise)

Day 153: Narrow collision detection

After a few days studying octrees, I decided that I will do them later for a few reasons:

- it is a pretty time consuming job, especially to optimize
- it is hard to test, and with a working engine it would be way easier
- the engine will work without them: if I just remove the broad phase collision detection I will get O(n^2) contacts, but otherwise everything will work.

For these reasons I'll implement them when everything will be up and running.
Today I started to work on the narrow phase collision detection, which consists in writing a lot of different collision cases, one for each possible pair of colliders. Today I wrote:

1) Sphere vs sphere
2) Box vs sphere
3) Box vs half plane
4) Sphere vs plane
5) Sphere vs half plane

These are the easier ones, tomorrow I'll get my hands on the separating axis theorem, which should enable to extend to more complex cases, first one being the collision between two boxes.

Day 152: Starting to work on octrees

Today I noticed that the book I'm following only introduces octrees, and doesn't provide the full implementation. Today I spent quite a bit of time researching how to implement them.
I'm not talking about the struct itself, which is pretty easy, but about those grey areas where more than one approach might be possible.
I'm talking about:

1) How to store an object with a shape:
The possible alternatives seems to be: store it in more than one leaf, or store them in the smaller inner node that contains it all.

2) How to handle memory:
Is it better to preallocate all the nodes up to a certain depth, or dinamically malloc / dealloc nodes that are used / removed?

Until I figure the best overall implementation choices I'll avoid to jump into implementation. Today I just wrote the skeleton of the class.

Day 151: Building the hierarchy

Today I added a few functionalities to the BVH in order to create the hierarchy automatically.
Instead of creating it at the beginning of the game manually, the process is completely automatic. It is possible to insert a node and delete it. The tree will automatically insert the node in the best position (the one that minimizes the size of the parent bounding volume). When the node is deleted, it is removed from the BVH tree, and the bounding volumes are automatically updated.
I've not tested the class because it requires quite a lot of test code, so I'll take its good functioning for granted, and eventually fix bugs when I'll actually use it.

Right now the class works only with spheres, but being it a template class it is pretty easy to adapt it to boxes as well, maybe I'll do it in the future if the need arises.

Tomorrow I'll start to work on spatial partitioning.

Day 150: Bounding Volume Hierarchy (BVH)

I'm now starting to work on the collision engine. Until now the collisions were faked (like in the springs for instance). One of the major problems in a complete rigid body system is the collision detection.
It is done in two phases: the broad-phase detection and the narrow phase detection.
The first one detects possible contacts, while the second performs more expensive collision queries in order to find the final contacts.
Right now I'm working on the first phase, and indeed the collisions will be evaluated only with sphere (or at the most box) colliders. The major optimization is to reduce the number of collisions to evaluate, which is Theta(n^2). To do so, it is possible to use two approaches (or even combine them):

- Bounding Volume Hierarchies (BVH): Holds in memory a tree of simple rigidbodies, like spheres. Each parent must be just big enough to contain the children. This is a very good way to reduce contact queries, because if two nodes are not colliding, none of the children will.

Today I wrote a template class to represent this tree, with a method that returns a vector of all the contacts inside a node. The class accept a template collider class, which must satisfy a few conditions, like having a "is_overlapping" method.

What I still don't have is a way to automatically build the BVH, I'll see to that tomorrow.

- Spatial Partitioning: This technique divides the space in a grid, and each cell keeps track of the rigidbodies contained in it. This allows to reduce the number of possible contact.
I'll finish to implement the BVH, then I'll implement it.

Day 149: Integrate function and force generators

Today I implemented the integration function for the rigid bodies.
I also modified the force generators created for the particles, in order to work with rigid bodied. For instance, the spring force generator now receives two points (in local coordinates), which represent the anchoring points of the spring. If these points are not the centers of the two rigidbody, the generated force might produce a torque.

Day 148: Rigid Body

Today I started finally to implement the "real" physics engine, which will be based on rigid bodies with a size and support for rotations.

I started by creating the RigidBody class, which is similar to the Particle class in many aspects, but requires additional information...like the inertia tensor, which is a 3x3 matrix that holds info about the inertia of a rigidbody.

I had to change quite a lot of things compared to the book I'm following, because my engine is deeply connected to the other parts of the engine. For instance I don't need to calculate the transform matrix for a rigidbody because it is already generated by the transform component.

Day 147: Rods

Today I started by adding a few simple but useful functionalities to the engine:
- a command to enable/disable fps logging
- a log function to easily print a glm::vec3

Then I tried once again to figure out why the jitter is happening, and I'm starting to think that there is not a real way to fix it, so I improvised: I added a threshold speed, under which a contact is rendered null. This solves the problem, but it is difficult to determine. For instance, with a gravity of 50g, the treshold should be around 20 m/s, which is clearly not ideal, especially if a real contact is happening.
But still, a better solution than yesterday, I'll continue to research new ways.

After that I implemented the Rod class, which generates collisions when two particles strive away from their predefined distance. This is achieved by setting to zero the separating velocity, and just resolving the interpenetration.
In the gif you can see a chain of cables on the left and a chain of rods on the right. It is quite difficult to see from the gif, but the cables stretch a bit, and allow particles to get closer, while the rods mostly maintain their distance. I say mostly because with this chained disposition the resolver algorithm is often in difficulty, and the resolution behaves in unexpected ways.

Day 146: Cables

Today I implemented the first class to generate contacts.
It is a Cable, which reister two particles, and make them bounce towards each other if they are far away. I've tested it and it works fine.
Obviously the real challenge will be to implement a collision generator between rigidbodies,  but this is really useful to test that the collision resolver is working properly....and long story short, it quite isn't.

As you can see from the gif, the resolution is mostly fine: the impulses are correctly generated, and the engine avoids interpenetrations. However the biggest problem (which is clearly visible at the beginning of the gif) is that the resting code is not working as it should. The particles are interpenetraded, and placed back the next frame, which is the jitter problem that the resting code should avoid. Maybe the problem isn't even there, I'm having troubles understanding what is happening, I'll continue to test it tomorrow.

Day 145: Contact resolver handler

Yesterday I implemented the ability for a contact to resolve its velocity (meaning the resulting velocities after the collision). Today I dealt with the interpenetration, which moves the objects to avoid them from penetrating each other.
I also modified the velocity resolver to deal with resting: it checks if the velocity of a particle is fully generated during the current frame (meaning that it was not moving before). If that's the case, no contact resolution is applied, and the object will not look like it's trembling.

After that I implemented the class to handle contact resolution. Given a list of contacts, they are resolved with the following algorithm:

1) Sort the contacts and pick the one with greater separating velocity (should be resolved first)
2) If there is none, exit.
3) Resolve the picked contact (I'll call it A)
4) For each contact, if it was involved in the contact with A, move it by the correct amount to avoid interpenetration
5) After a certain amount of iterations, quit.

I've a few problems with this algorithm, and the book I'm reading is not clear at all at this point... One of them is step 4. When interpenetrations are resolved inside the contact.resolve function, the resolution takes into account the relative masses, while here this is ignored. I imagine a situation where a very light object interpenetrates another object and it is moved apart. If a block of metal is in contact with it, it will be moved by the same amount, with no respect for it's mass. I hope I'll understand it in the next days.

Day 144: Buoyancy and Contact resolver

Today I started by adding another force generator to simulate the buoyancy. The formula used is a very crude approximation of the actual formula: it doesn't account for the shape of the object, and it behaves basically like a spring, with the difference that, when the object is fully immersed, the force becomes constant.
In the gif the white particle is kept floating thanks to this force, despite the gravity and spring force pulling it down.

I also implemented the first part of the contact resolver. Basically this class holds the info about a contact, and resolves the position of the two particles involved thanks to the "resolve" method. The resolve method calls two functions: resolve_velocity, which adds the resulting velocity after the collision to the particles, and the resolve_interpenetration method, which handles the fact that two particles might already be inside one another. I've implemented only the first method so far, and both of them will be difficult to test for now, because the particles have no shape yet.
An important thing to notice is that this class uses a contact_normal variable, which is the direction of the contact point. This must be provided by some other not-yet-implemented classes of the engine, because the Contact class itself ignores how the contact is generated, it just resolves it.

Day 143: Force generators and force register

Today I implemented the skeleton of the system that handles forces. It is entirely based on three classes (and eventual derived classes):

1) Particle: the physical entity. Each particles has an accumulator, which is the resulting force accumulated every frame. Through the integration the particle status is updated.

2) Force generator: It describes a force. I extended this base class to simulate gravity, drag, spring, anchored spring, "bungee" and "anchored bungee" forces. Each force generator can add its force to the accumulator of the particle

3) Force register: This is the class that wraps everything together. It registers a list of force-particle pairs. Every frame, each force calls it's "add_force" function on the corresponding particle.

With this simple system it is easy to handle an arbitrary number of forces. In the gif there are two particles: an orange one, which is moved manually and not registered with any force, and a white one, which is under the influence of gravity and of a spring connected to the orange particle.

In the evening I also tried to implement the RK4 integration, in order to solve precision errors when using springs. I decided not to do that after a while because it would not resolve every problem, and it will also lower the performances of the engine. And the major problem would be to handle it when I'll need to implement advanced features of the engine, because it introduces more complexity. So for now I'll continue to use the not-so-good, old, Euler integration.

Day 142: Particle and basic integrator

Today I started to build the physical engine. Since I'm quite new to this field I'll follow the book "Game Physics Engine Development" by Ian Millington, which seems to be the best resource to start with. I will not follow exactly the book, and I will adapt and modify the engine to my needs whenever possible.

Today I've written a Particle class, which is the base entity in a physical engine with only point masses. I've also added an integration function (which is the function that updates the particle each frame) which applies the basic Newton laws. However I'm still missing a system to handle multiple particles.

From now on, if I've something to show, I'll publish a gif instead of an image for obvious reasons

Day 141: Attempt to improve the batch class

Today I didn't start to work on physics again because I noted that the sorting in the batch class has a major impact on the performance. Thus I tried to implement a few solution in order to avoid the sorting:

1) keep a sorted list, and insert and remove objects from there

2) keep a normal list, but sort it only if something is modified

In the end I didn't implement either of them, because it is very difficult and overcomplicated to track when an object is to be drawn or not. All of these factors are to be considered:

-Model creation, submodel creation, model modification, submodel modification, add model to game object, add submodel to model, activate object, deactivate object, destructors, etc etc etc

So in the end I just added a property to the batch class to disable the sorting. This will be up to the user. If I find a better solution I'll try to implement it, but for now I'll stick with that.
I tested it and I managed to improve a lot the particles emitter by disabling the useless sorting.

Day 140: Component System finally completed!

Yesterday I decided to quit the idea of refactoring the component system, but today I really felt like that was to be done, so i did.
Now every component inherits from Script, and the class GameObject has only a list of scripts and a transform. A script can be added with:

game_object.add_script();

and retrieved in a similar way. Everything is handled by template functions, and the system feels very user-friendly and Unity-like. This also allows to have multiple scripts of the same type, which was impossible with the previous approach.
Also, each script overrides two functions: bool is_unique() and bool is_copyable(). This allows to put constraint on the uniqueness or the possibility to copy a script.

The main reason that made me do this refactoring is the upcoming physical engine: maybe each object will need more than one collider, and this is fairly straightforward now.

Day 139: Let's start with physics

I've finally decided to start seriously to implement a physical engine. Instead of randomly implement complex algorithms like GJK as I did in the past, I'll proceed step by step, starting with spheres, AABBs and so on. I've also bought a book on the topic to learn things the correct way and to avoid pitfalls.

Today I've created the "Ryno Physics" project inside the visual studio solution, and made all the necessary linkings. I also created an abstract Collider class, with lots of subclasses (like aabb, sphere colliders, OBB and so on).

 I've also tried to refactor the engine in order to improve the component system (and make the lights, model, transform and emitter actual scripts themselves)...In the end I gave up due to the big amount of work, and a little-to-no benefit to the engine.

Finally I created an empty scene in which I'll test the physical engine.