When setting out to build a physics engine, there's a fundamental building block you simply can't ignore: vectors. Vectors are the DNA of any physics computation—whether it's detecting collisions, applying forces, or calculating rotations. To lay down the foundation for my physics engine, the first logical step was implementing a robust vector class, accompanied by a math class to handle basic vector operations like the cross and dot products, normalization, and obtaining the norm.
Vector2D Struct
The Vector2D struct is the blueprint for creating 2D vector objects and lets you do most of the basic operations such as addition, subtraction, and, scalar multiplication and division. Since these methods are pretty straightforward to implement, I won't go into much detail.
Vector2f Vector2f::Zero()
{
return Vector2f(0.f, 0.f);
}
Vector2f Vector2f::operator+(const Vector2f& a) const
{
return Vector2f(this->x + a.x, this->y + a.y);
}
Vector2f Vector2f::operator+=(const Vector2f& a)
{
this->x += a.x;
this->y += a.y;
return *this;
}
Vector2f Vector2f::operator-=(const Vector2f& a)
{
return *this - a;
}
Vector2f Vector2f::operator-(const Vector2f& a) const
{
return Vector2f(this->x - a.x, this->y - a.y);
}
Vector2f Vector2f::operator-()
{
return Vector2f(-this->x, -this->y);
}
Vector2f Vector2f::operator*(const float scalar) const
{
return Vector2f(this->x * scalar, this->y * scalar);
}
Vector2f Vector2f::operator/(const float scalar) const
{
return Vector2f(this->x / scalar, this->y / scalar);
}
Vector2f Vector2f::operator*=(const float scalar)
{
this->x *= scalar;
this->y *= scalar;
return *this;
}
// EPSILON is a constant value which is set to 0.005f. This value is used for floating point comparison
bool Vector2f::operator==(const Vector2f& a)
{
return std::abs(this->x - a.x) < EPSILON && std::abs(this->y - a.y) < EPSILON;
}
In addition to this, I've added a transform method allowing you to translate and rotate your vector based on the information that your Transform2D object contains. This method came in very handy for updating the position of each vertex, which is given in local coordinates (with respect to the center of mass of the shape). Using the transform allows you to represent the local coordinates in world coordinates.
The 2D transformation of a vector \( \mathbf{v} = \begin{bmatrix} v_x \\ v_y \end{bmatrix} \) including rotation by \( \theta \) degrees and translation by \(\mathbf{t} = \begin{bmatrix} t_x \\ t_y \end{bmatrix}\) can be represented as:
\[ \mathbf{v'} = \begin{bmatrix} \cos(\theta) & -\sin(\theta) \\ \sin(\theta) & \cos(\theta) \end{bmatrix} \mathbf{v} + \mathbf{t} = \begin{bmatrix} \cos(\theta) \cdot v_x - \sin(\theta) \cdot v_y + t_x \\ \sin(\theta) \cdot v_x + \cos(\theta) \cdot v_y + t_y \end{bmatrix} \]
Where \(\mathbf{v'}\) is the transformed vector.
Here is how I implemented in C++:
Vector2f Vector2f::transform(Vector2f& v, Transform2D& transform)
{
// apply rotation and translation to vector v
return Vector2f(transform.cos * v.x - transform.sin * v.y + transform.position_x, transform.sin * v.x + transform.cos * v.y + transform.position_y);
}Math2D Class
The Math2D class serves as a utility class for handling 2D mathematical operations essential for physics simulations. It offers a bunch of methods for tasks such as value clipping, unit conversions between degrees and radians (vice-versa), and various vector operations including Euler norm, normalization, dot product, and cross product.
Value Clipping
A clipping function is a mathematical operation that constrains or "clips" an input value within a predefined range, defined by a lower and an upper boundary. When an input value falls within this range, it remains unchanged. However, if the input exceeds the upper boundary, the function returns the upper boundary value. Conversely, if the input is below the lower boundary, the function returns the lower boundary value. Mathematically speaking, it's this:
\[\text{clip}(x, \text{min}, \text{max}) = \begin{cases} \text{min} & \text{if } x < \text{min}, \\ \text{max} & \text{if } x > \text{max}, \\ x & \text{otherwise}. \end{cases}\]
In essence, a clipping function serves as a "gatekeeper" that prevents values from going beyond the set limits. This is particularly useful in scenarios where an attribute must remain within specific bounds for the system to function correctly.
For example, the restitution value needs to be between 0 and 1, using a clipping function ensures that any calculated restitution will conform to these limits. This can be crucial for maintaining the physical realism or stability of the simulation.
By implementing a clipping function, you can ensure data integrity and prevent potential errors or inconsistencies in your application.
float Math2D::clip(const float value, float min, float max)
{
if (min == max)
return min;
if (min > max)
{
try
{}
catch(const std::exception& e)
{
throw "min is greater than max!";
}
}
if (value > max)
return max;
else if (value < min)
return min;
else
return value;
}From Radian to Degrees & Vice-Versa
The reason why this is important is that the rotation methods provided by the SFML library require degrees, but the \(\cos\) and \(\sin\) functions from the standard C++ library need radians. Thus, it would be handy to have a static function that does this conversion.
To get from degrees to radians, you essentially multiply the value in degrees by \(\frac{\pi}{180}\). If you have radians, you need to multiply it by \(\frac{180}{\pi}\). Below you can find the implementation:
float Math2D::convertToDegree(float radian)
{
return radian * 180.f / M_PI;
}
float Math2D::convertToRadian(float degree)
{
return degree * M_PI / 180.f;
}Dot Product
The dot product is a mathematical operation that takes two vectors and returns a single scalar value. In the context of 2D or 3D geometry, the dot product is frequently used for projections and is an integral part of the Separating Axis Theorem (SAT) for collision detection. In SAT, the dot product helps project polygon vertices onto a candidate separating axis to check for overlaps. If there is no overlap along any of the axes, then it can be conclusively stated that the two polygons do not intersect, thereby optimizing the collision detection process. We talk about this method again in Parts III and IV.
Beyond collision detection, the dot product is also used to determine the relative motion between two objects. Specifically, if the dot product of the velocity vectors of two objects is positive, it indicates that the objects are moving away from each other. Conversely, a negative dot product implies that the objects are moving toward each other. With that knowledge, you only have to compute the impulses for those who actually collide which results in a more computationally efficient physics engine.
The dot product between \(\mathbf{v} = \begin{bmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{bmatrix}\) and \(\mathbf{w} = \begin{bmatrix} w_1 \\ w_2 \\ \vdots \\ w_n \end{bmatrix}\) is defined as follows:
\[\mathbf{v} \cdot \mathbf{w} = \sum_{i=1}^{n} v_i \cdot w_i\]
In C++ you can implement it like this:
float Math2D::dot(const Vector2f& a, const Vector2f& b)
{
return a.x * b.x + a.y * b.y;
}Cross Product
The cross-product is a mathematical operation that takes two vectors in three-dimensional space and returns a vector that is perpendicular to the plane containing the original vectors. In the context of physics simulations and rigid-body dynamics, I frequently used the cross-product to calculate angular velocity based on the impulse applied to an object. Specifically, the cross product of the impulse vector and the radius (or lever arm) vector gives a torque vector, which can be used to update the angular velocity of the object.
The cross product of two vectors \(\mathbf{v} = \begin{bmatrix}v_x \\ v_y \\ v_z \end{bmatrix}\) and \(\mathbf{w} = \begin{bmatrix} w_x \\ w_y \\ w_z \end{bmatrix}\) is calculated as follows:
\[\mathbf{v} \times \mathbf{w} = \begin{bmatrix} v_y \cdot w_z - v_z \cdot w_y \\ v_z \cdot w_x - v_x \cdot w_z \\ v_x \cdot w_y - v_y \cdot w_x \end{bmatrix}\]
Since we are implementing a 2D physics engine we assume \(v_z = w_z = 0\), resulting in the following formulation:
\[\mathbf{v} \times \mathbf{w} = \begin{bmatrix} 0 \\ 0 \\ v_x \cdot w_y - v_y \cdot w_x \end{bmatrix}\]
The same as above but in C++:
float Math2D::cross(const Vector2f& a, const Vector2f& b)
{
return a.x * b.y - a.y * b.x;
}Euler Norm
The Euclidean norm, often simply referred to as the "norm" or "magnitude," is a measure of the length of a vector in Euclidean space. It is calculated using the square root of the sum of the squares of each component of the vector. The Euclidean norm provides a way to quantify the "size" or "length" of a vector.
Mathematically, for a vector \(\mathbf{v} = \begin{bmatrix} v_1 \\ v_2 \\ \vdots \\v_n \end{bmatrix}\) in \(\mathbb{R}^n\), the Euclidean norm is given by:
\[| \mathbf{v} | = \sqrt{\sum_{i=1}^{n} v_i^2}\]
This norm will become essential for operations like normalization and distance measurement.
float Math2D::norm(const Vector2f& a)
{
return std::sqrt(a.x * a.x + a.y * a.y);
}Normalization
Normalization is the process of converting a vector into a unit vector, meaning a vector with a length of one while preserving its original direction. In mathematical terms, a vector \(\mathbf{v}\) is normalized by dividing each of its components by its Euclidean norm. The resulting unit vector \(\mathbf{\hat{v}}\) points in the same direction as \(\mathbf{v}\) but has a magnitude of one.
The formula and code for normalizing \(\mathbf{v}\) is given by:
\[\mathbf{\hat{v}} = \frac{\mathbf{v}}{\| \mathbf{v} \|}\]
Vector2f Math2D::normalize(const Vector2f& a)
{
return a / Math2D::norm(a);
}How to Calculate the Euclidean Distance?
Last, but not least, it is often useful to have the possibility to calculate the distance between two points given in world coordinates. The Euclidean distance serves this purpose by providing a scalar measure of the "straight-line" distance between two points in an Euclidean space. Whether it's for collision detection, pathfinding algorithms, or geometric transformations, calculating the Euclidean distance is a frequent operation in computational geometry and physics simulations.
Mathematically, the Euclidean distance between two points \(\mathbf{v} = \begin{bmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{bmatrix}\) and \(\mathbf{w} = \begin{bmatrix} w_1 \\ w_2 \\ \vdots \\ w_n \end{bmatrix}\) in \(\mathbb{R}^n\) can be calculated using the following formula:
\[\text{Distance}(\mathbf{v}, \mathbf{w}) = \sqrt{\sum_{i=1}^{n} (v_i - w_i)^2}\]
In C++ it looks as follows:
float Math2D::distance(const Vector2f& a, const Vector2f& b)
{
return std::sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}Conclusion
In conclusion, the concepts of clipping, angle conversion, vector operations, and various mathematical norms and products serve as fundamental building blocks in computational physics, particularly in 2D applications like SAT collision detection. The dot product is invaluable for projections and understanding relative motion, while the cross product helps in calculating angular velocities based on applied impulses. The Euclidean norm gives us the length of a vector, which is essential for operations like normalization. Normalization itself plays a critical role in making vectors consistent for comparison, particularly in collision detection algorithms. The Euclidean distance, meanwhile, gives us a simple yet powerful way to calculate the "straight-line" distance between two points, a feature often needed in simulations and geometry-based algorithms. These mathematical tools and techniques are not just theoretical constructs but have direct and impactful applications in various computational domains.
Part II of this series will be coming on September, 18th. So stay tuned!