Updating center positions directly during collision-checking inhibits parallelization efforts.

[tugrul512bit]

void DynamicShapeArray::Move(int index) {
	float* speed = shapeArray[index].speed;
	if (speed[0] || speed[1] || speed[2]) {
		CheckCollision(index);
		shapeArray[index].Model = glm::translate(glm::mat4{1.f}, glm::vec3(speed[0] * (speedUP * globalSpeed), speed[1] * (speedUP * globalSpeed), speed[2] * (speedUP * globalSpeed))) * shapeArray[index].Model;
		shapeArray[index].center[0] += speed[0] * (speedUP * globalSpeed);
		shapeArray[index].center[1] += speed[1] * (speedUP * globalSpeed);
		shapeArray[index].center[2] += speed[2] * (speedUP * globalSpeed);
	}
}

in the current code, center x, y, z are directly updated after CheckCollision(index) call which directly affects results of other objects without giving them a chance to find their intended original solution. And because of the order of objects processed, it creates a bias towards one of the objects. For example, the last object to be computed can simply push other objects to make them collide each other again. So the last computed object has the highest bias.

If the collision system could be implemented using a temporary array without altering the original data, it would be able to parallelize the operation using vectorization, multithreading and more. The dependency chain created by the immediate updates makes parallelization a different behavior.

Another issue about collision is that each collision is updating both objects and both objects are calculated which results in duplicated work (object i goes from 0 to n, object j goes from 0 to n, but i,j is same as j,i).

---

Is the following index check intended for a special object?

	if (... index < 2) {
		return;
	}

Looks like index = 0 and index = 1 are special objects, perhaps player-controlled?

[tugrul512bit]

Also having different branches for each shape type's collision-check would be harder to convert to GPU kernel because GPU cores would expect similar codes between neighbor threads. So, when thread-257 computing collision between a sphere and a ring, thread-258 will be masked out by warp-scheduler if its cube-cube collision. This has inefficient mapping for GPU.

Possible optimizations are:

• sorting the objects by their types
• representing the objects by a number of spheres (such as a cube made of 8 spheres and a ring made of N ring-placed spheres)
• separating object blocks to their own buffers and doing sphere array vs sphere array collision checking, sphere array vs cube array collision checking, etc

Just sorting is simplest (maybe 1 liner using a functor + std::sort if its AOS type but more complex for SOA which is faster during collision checking) but it would make neighboring gpu threads work on same code path and be accelerated efficiently.

Representing object collidables from only spheres would avoid the sorting for a lower latency solution but it uses more shapes (many spheres) in total so its scaling would not be good.

Separating object types would be fastest for 3-5 types but the more object types would cause the more type vs type checking involved. If there are 200 shape types, it would become inefficient again due to 40000 different checks not efficiently parallelizable / not enough work per type vs type.

I think for the effort per speedup, sorting is best. For max performance, depends on number of shape types.

[StamatisMat]

First of all thanks for your input!! Your feedback is very valuable, as it provides another perspective we need!

in the current code, center x, y, z are directly updated after CheckCollision(index) call which directly affects results of other objects without giving them a chance to find their intended original solution. And because of the order of objects processed, it creates a bias towards one of the objects. For example, the last object to be computed can simply push other objects to make them collide each other again. So the last computed object has the highest bias.

When an object "A" collides with another "B", the Collide call is called for both A&B and B&A exactly for that reason. The core issue that I found and will add to the README is that speed is changed for Object A in Collide(A,B) but when Collide(B,A) is called, speedA has already changed, so the collision is improperly calculated.

If the collision system could be implemented using a temporary array without altering the original data, it would be able to parallelize the operation using vectorization, multithreading and more. The dependency chain created by the immediate updates makes parallelization a different behavior.

That's a great idea. We've thought about adding a temp center and speed vec3, and update it using atomic operations, but we need to think about conservation of energy, because if using speedA, object B and object C collides with objectA, they both add speed to A, while the kinetic energy of A is given to both B and C, because speed is updated later. With current methodology, one collision would be prioritized, leading to better results for B and C.

The best would be to spatial sort depending on distance between objects, and CheckCollision only when needed, and with the correct order.

We plan on the far future to rewrite the whole collision system using modern methods like GPU calculated spatial partitioning. For now, temp speed will be a bandage to the current code.

Another issue about collision is that each collision is updating both objects and both objects are calculated which results in duplicated work (object i goes from 0 to n, object j goes from 0 to n, but i,j is same as j,i).

The non-collision code is quite fast, and if a collision is caught in the duplicated work, not between j,i but j,k or j,l, because of the immediate changes to speed, the collision would be instead calculated next frame, so it's not duplicate work. It's probably poor coding practice, but needed. This collision method is O(n^2).

Is the following index check intended for a special object?

if (... index < 2) {
return;
}

Looks like index = 0 and index = 1 are special objects, perhaps player-controlled?

Yes, it's the big semi-transparent cube that all objects spawn in, and the sphere in the middle of the screen that's textured and can be moved using arrow keys. They cannot be moved using collisions. It's probably already fixed(documented) by the time you read this.

[tugrul512bit]

You're welcome. A relatively accurate method to compute a fair collision response (like when an object is in collision with 15 other objects) is:

• Take one object that has multiple collisions
• Calculate the error for +/-X, +/-Y, +/-Z steps around the point to know the derivatives and second-order derivatives of the error because the object can go only 3 dimensional new position. Let's call this as gradient of error. We need to find minima of this gradient of error.
• Newton-Raphson method is like this: x_new = x_old - f(x_old)/f'(x_old)
• • Since we can't divide a value by a gradient matrix, we need to find inverse of it (since its only 3-6 degrees of freedom) using Gaussian-Elimination method or something that's fast for 6x6 matrix
• • Now the division by derivative(f'(x) = H) becomes inverse(H) or H^(-1)
• • x_new = x_old - (H^(-1)) * f(x)
• • then just repeat like 3-5 times (so it involves 3-5 matrix inverses, 3-5 matrix - vector multiplications, etc, because the derivatives would change on every different displacement)

the operations are totally independent from other objects' solutions so its a local solution per object, propagated to others through timesteps globally (much faster than a global solution using 60000000 x 60000000 global matrix).

This collision response calculation is only one part of solution. It requires to know what are constraints per object-pair (which objects are in collision), which is already calculated by Lab1-Graphics (accelerating the collision detection is a matter of choosing an acceleration algorithm like sorting + binary search, spatial-hashing, tree + AABB or similar, with AVX2, AVX512, GPU, etc).

---

But, if realism isn't a concern, then you can just bump the objects back with a ratio of the masses in collision like sum_of_masses/mass_current or something similar using the error vector directly without any extra calculation. For this "bump" version, I'd suggest at least a Verlet-Integration (fast, simple) or maybe RK4-Integration (expensive, more realistic). First-order Euler-Integration is not good with the collision responses.