Showing posts with label Math. Show all posts
Showing posts with label Math. Show all posts

02 March 2021

Math - Normalize a 3D vector

This method is part of the Vector3 class, and changes the vector into a unit vector.
void Normalize() {
  if (IsZero) return; //X, Y and Z are 0: it would set each component to NaN.
  float length = (float)Math.Sqrt(X * X + Y * Y + Z * Z);
  X /= length;
  Y /= length;
  Z /= length;
}

Math - Calculate a normal vector from three position vectors

This Vector3 constructor calculates a surface normal from three 3D vectors.
public Vector3(Vector3 a, Vector3 b, Vector3 c) {
  var u = b - a; //Requires an overloaded minus
  var v = c - a; //operator for two vector3's.
  X = (u.Y * v.Z) - (u.Z * v.Y);
  Y = (u.Z * v.X) - (u.X * v.Z);
  Z = (u.X * v.Y) - (u.Y * v.X);
  Normalize();
}

21 July 2020

Math - Calculate a look-at matrix for OpenGL (II)

This is a simplification of the method to create a look-at or camera matrix from 2017. Based on DirectX documentation, it creates the matrix in one step, without multiplication. The matrix is created transposed for OpenGL. This method takes in a Vector3 Position and Direction.

This matrix doesn't work when looking straight up or down, because in that case the x-axis cross product fails. To solve this, manually set the x-axis in that case.

bool isVertical = direction.X == 0 && direction.Z == 0;
var up = new Vector3(0, 1, 0);
var zAxis = direction.Normalized();
var xAxis = isVertical ? new Vector3(1, 0, 0) : Vector3.CrossProduct(up, zAxis).Normalized();
var yAxis = Vector3.CrossProduct(zAxis, xAxis);

return new Matrix(
    xAxis.X, xAxis.Y, xAxis.Z, -Vector3.DotProduct(xAxis, position),
    yAxis.X, yAxis.Y, yAxis.Z, -Vector3.DotProduct(yAxis, position),
    zAxis.X, zAxis.Y, zAxis.Z, -Vector3.DotProduct(zAxis, position),
    0, 0, 0, 1
);

31 December 2019

Math - Interpolating a value

Here's how to interpolate a value from one range to another:

Range 1: 100.....550.....1000
Range 2: 300..... x .....3000

This formula will do it:

public static float Interpolate(this float value, float minValue, float maxValue, float minScale, float maxScale) =>
  (((value - minValue) / (maxValue - minValue)) * (maxScale - minScale)) + minScale;

float x = 550.Interpolate(100, 1000, 300, 3000); //x = 1650

Try it

Range 1
Range 2 ...

See also

Scaling a value

16 July 2019

Math - Calculate the 3D world position of a 2D window vector

I render a 3D triangle. When I click on it, I want to know the point on the triangle that was clicked. To calculate this point, you need:
  • Point position: the window position of the mouse click. You get this point directly from the event raised by the operating system.
  • Matrix projection and camera (also called modelview): the matrices used to transform from object space to world space and then to 2D clip coordinates.
  • Rectangle viewport: the position and size of the viewport on which to project.
  • An InvertMatrix method. You can find an implementation here.
Then you calculate the line that contains all the points that project to the clicked position as follows:
public (Vector3 near, Vector3 far) GetWorldPosition(Point position)
{
    position.Y = viewport.Height - position.Y; //For OpenGL, the bottom is the origin.
    position -= viewport.Position; //Adjust to the viewport's position on the window.
    var p = position.Normalized(Size); //Normalize the point to the range [-1;1].
    var inv = (Projection * Camera).Invert(); //Calculate the inverse matrix.
    var near = new Vector4(p.X, p.Y, -1, 1) * inv;
    var far = new Vector4(p.X, p.Y, 1, 1) * inv;
    near.PerspectiveDivide(); //Divide X, Y and Z by the W component.
    far.PerspectiveDivide();
    return (near, far);
}
If you draw this line, it should appear as a dot until you move the camera, because every vector on this line projects on the same screen pixel.
Intersecting this line with the triangle then gives me the 3D point I'm looking for.

See also

Calculate the 2D window position of a 3D vector

27 January 2019

Math - Calculate the 2D window position of a 3D vector

I render a 3D model as points in a viewport with OpenGL. I want to select points by clicking them. To do this, I calculate the position of the 3D point on the 2D window the same way the shader does. These variables are needed:

  • Vector4 vector: the 3D position in object space of the point + it's W component. W is always 1 in object space, but gets transformed by the projection matrix. It is then used for the perspective divide.
  • Matrix projection and camera (also called modelview): the matrices used to transform from object space to world space and then to 2D clip coordinates.
  • Rectangle viewport: the position and size of the viewport on which to project.
  • Point mouse: the window position of the mouse click. You get this point directly from the event raised by the operating system.

From then, it's actually not that hard. You do need a method to multiply matrices.

public Point GetPosition(Vector4 vector)
{
    var p = Projection * Camera * vector;

    //Perspective divide.
    p.X /= p.W;
    p.Y /= p.W;

    //Scale from [-1; 1] to viewport dimensions.
    p.X = (p.X + 1).Scale(2, viewport.Width);
    p.Y = -(p.Y - 1).Scale(2, viewport.Height); //For OpenGL, the bottom is the origin.

    //Adjust to the viewport's position on the window.
    return new Point((int)p.X + viewport.Left, (int)p.Y + viewport.Top);
}

var pos = GetPosition(vector);
IsSelected = pos.X.Between(mouse.X - 5, mouse.X + 5) && pos.Y.Between(mouse.Y - 5, mouse.Y + 5);

See also

Calculate the 3D world position of a 2D window vector

30 November 2017

Math – 3D line-triangle intersection

The following is a very simple but effective method I found to find the intersection point of a line with a triangle. I used it to determine the height of a point on the terrain.

The first part finds the intersection point:
private float? GetIntersectionY(Vector3 a, Vector3 b, Vector3 c, Vector3 pp) {
  //First, define a ray that will definitely intersect if the triangle lies beneath the point.
  var p = new Vector3(pp.X, 100, pp.Z);
  var q = new Vector3(p.X, p.Y - 100, p.Z);

  //Then, find the intersection.
  var normal = Vector3.CrossProduct(b - a, c - a).Normalized();
  float dist1 = Vector3.DotProduct(p - a, normal);
  float dist2 = Vector3.DotProduct(q - a, normal);

  if (dist1 == dist2 || dist1 * dist2 >= 0) //Parallel; no intersection.
    return null;

  var intersection = p + (q - p) * (-dist1 / (dist2 - dist1));

  //Verify that this point lies inside the triangle.
  if (SameSide(p, a, b, c) && SameSide(p, b, a, c) && SameSide(p, c, a, b))
    return intersection.Y;
  else
    return null;
}

The second part, as the above function already indicates, determines that the point really lies within the triangle, and not just within the mathematical plane. The linked sited explains well how this works.
private static bool SameSide(Vector3 p1, Vector3 p2, Vector3 a, Vector3 b) {
  //It only worked right for me when all the points had the same height though.
  var _p1 = new Vector3(p1.X, 0, p1.Z);
  var _p2 = new Vector3(p2.X, 0, p2.Z);
  var _a = new Vector3(a.X, 0, a.Z);
  var _b = new Vector3(b.X, 0, b.Z);

  //The check.
  var cp1 = Vector3.CrossProduct(_b - _a, _p1 - _a);
  var cp2 = Vector3.CrossProduct(_b - _a, _p2 - _a);
  return Vector3.DotProduct(cp1, cp2) >= 0;
}

21 November 2017

Math – Align a rotation matrix with a normal

Angle and axis

I found this method when I needed to rotate a vehicle to be positioned on the terrain. I had the positions of the wheels, and used those to calculate the vehicle's normal. Then I found the following method to calculate the angle and rotation axis:

var axis = new Vector3(0, 1, 0); //Up vector
float angle = Vector3.DotProduct(normal, axis).Acos(); //I do like extension methods.
var transformation = new Matrix();

if (angle.Absolute() > 0.001f) {
  axis = Vector3.CrossProduct(normal, axis).Normalized();
  transformation.Rotate(angle, axis); //See below.
}

Rotate the matrix

Then the glRotatef function is used to use these values, but that's from the old fixed pipeline OpenGL, and I was using the new OpenGL with shaders and all that. I then found this function that applies the rotation to a matrix:

float rad = angle.ToRadians();
float c = rad.Cos();
float s = rad.Sin();
float t = 1 - c;

float x = axis.X;
float y = axis.Y;
float z = axis.Z;

var rotation = new Matrix();
rotation.M[0, 0] = c + x * x * t;
rotation.M[0, 1] = y * x * t + z * s;
rotation.M[0, 2] = z * x * t - y * s;

rotation.M[1, 0] = x * y * t - z * s;
rotation.M[1, 1] = c + y * y * t;
rotation.M[1, 2] = z * y * t + x * s;

rotation.M[2, 0] = x * z * t + y * s;
rotation.M[2, 1] = y * z * t - x * s;
rotation.M[2, 2] = z * z * t + c;

SetMatrix((this * rotation).M); //This just overwrites the 16 values of this matrix.

See also

Using quaternions to create a rotation matrix

19 September 2017

Math - rotate a 2D point

I needed a way to rotate a point (x; y) by a certain angle. This turned out to be an easy task:
Vector2 Rotate(Vector2 point, double angle)
{
  double rad = angle * (Math.PI / 180); //First, convert from degrees to radians.
  
  double sin = Math.Sin(rad); //Then, get the sine and
  double cos = Math.Cos(rad); //cosine of this angle.
  
  return new Vector2 //Finally, calculate the rotated point.
  {
    X = point.X * cos - point.Y * sin,
    Y = point.X * sin + point.Y * cos
  };
}

30 August 2017

Math – Calculate the distance between two points in 3D space

Always usefull in 3D development is a method to calculate the distance between two vectors. It's not very hard either, using the Pythagorean theorem. Here is how to do it in C# for two vectors, a and b:
public float Distance(Vector3 a, Vector3 b) =>
  (float)Math.Sqrt(Math.Pow(a.X - b.X, 2) + Math.Pow(a.Y - b.Y, 2) + Math.Pow(a.Z - b.Z, 2));

09 April 2017

Math – Calculate a transformation matrix

Suppose you have a translation, a rotation and a scaling matrix; how do you combine them into one transformation matrix — also model matrix — used to render some object? The order in which they are combined is also important. The following method will first rotate and scale the object, then move it. Rotation is the most complex transformation, and is done with quaternions.

//"Position", "Scale" and "Rotation" are all Vector3's.
Quaternion rot = null;
if (Rotation != null)
{
    var rotX = new Quaternion(Rotation.X, 1, 0, 0);
    var rotY = new Quaternion(Rotation.Y, 0, 1, 0);
    var rotZ = new Quaternion(Rotation.Z, 0, 0, 1);
    rot = rotX * rotY * rotZ;
}

var model = new Matrix();
model.Rotate(rot);
model.Scale(Scale);
model.Translate(Position);

The Matrix class was also mentioned in the post about quaternions. You can find the Matrix.Rotate method there as well. Compared to that, translation and scaling are pretty simple:

//An overload of this method takes a Vector3, and checks it for NULL.
public void Translate(float x, float y, float z)
{
    M[0, 3] += x;
    M[1, 3] += y;
    M[2, 3] += z;
}

//Also has an overload that takes a Vector3.
public void Scale(float x, float y, float z)
{
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            M[i, j] *= x;
            M[i, j] *= y;
            M[i, j] *= z;
        }
    }
}

19 February 2017

Math - Calculate a look-at matrix for OpenGL

The final piece of the puzzle to get my basic OpenGL scene up and running was the camera or look-at matrix. It is calculated from a position vector and a direction vector; the look-at vector.

The position and direction vectors

Here's how the position and direction vectors are calculated. The input comes from the mouse and keyboard. Note that I do use some extension methods to make life easier. Delta time is a time-based value to get the same speed on slow and fast computers.

rotationHorizontal += window.MouseMovement.X * 0.1f;
rotationHorizontal = rotationHorizontal.Circular(0, 359);
rotationVertical += window.MouseMovement.Y * 0.1f;
rotationVertical = rotationVertical.Constrain(-89, 89);

float h = rotationHorizontal.ToRadians();
float v = rotationVertical.ToRadians();
float hs = h.Sin();
float hc = h.Cos();
float vs = v.Sin();
float vc = v.Cos();
float speed = 0.005f * deltaTime;

if (window.KeyDown(Key.Up))
{
    position.X -= hc * speed;
    position.Z -= hs * speed;
}

if (window.KeyDown(Key.Down))
{
    position.X += hc * speed;
    position.Z += hs * speed;
}

if (window.KeyDown(Key.Left))
{
    position.X -= hs * speed;
    position.Z += hc * speed;
}

if (window.KeyDown(Key.Right))
{
    position.X += hs * speed;
    position.Z -= hc * speed;
}

var direction = new Vector(vc * hc, vs, vc * hs);
var camera = new Matrix(position, direction);

The look-at matrix

This one is again implemented as a constructor of the Matrix class. It uses some basic vector operations; the implementations of which can easily be found online.

public Matrix(Vector position, Vector direction)
{
    var up = new Vector(0, 1, 0);
    var zAxis = direction.Normalized();
    var xAxis = Vector.CrossProduct(up.Normalized(), zAxis).Normalized();
    var yAxis = Vector.CrossProduct(zAxis, xAxis);

    var translation = new Matrix();
    translation.Translate(position.Negated());

    var rotation = new Matrix();
    rotation.M[0, 0] = xAxis.X;
    rotation.M[0, 1] = xAxis.Y;
    rotation.M[0, 2] = xAxis.Z;

    rotation.M[1, 0] = yAxis.X;
    rotation.M[1, 1] = yAxis.Y;
    rotation.M[1, 2] = yAxis.Z;

    rotation.M[2, 0] = zAxis.X;
    rotation.M[2, 1] = zAxis.Y;
    rotation.M[2, 2] = zAxis.Z;

    var lookAt = rotation * translation;
    SetMatrix(lookAt.M);
}

See also

Simplified method to create a look-at matrix
Calculate a perspective projection matrix for OpenGL

09 February 2017

Math - Calculate a perspective projection matrix for OpenGL

Another method that took a while to find was the one that calculates a perspective projection matrix from a given field of view, aspect ratio and near and far plane to work with OpenGL. This constructor for a Matrix object does it though:

public Matrix(float fov, float aspect, float near, float far)
{
    Values = new float[4, 4];

    float scale = (float)Math.Tan(fov.ToRadians() * 0.5f) * near;
    float right = aspect * scale;
    float left = -right;
    float top = scale;
    float bottom = -top;

    Values[0, 0] = 2f * near / (right - left);
    Values[1, 1] = 2f * near / (top - bottom);
    Values[0, 2] = (right + left) / (right - left);
    Values[1, 2] = (top + bottom) / (top - bottom);
    Values[2, 2] = -(far + near) / (far - near);
    Values[3, 2] = -1f;
    Values[2, 3] = -2f * far * near / (far - near);
}

Note that this class uses row-major order, while OpenGL uses column-major order. When I pass my matrices to the glUniformMatrix4fv method, I set it's transpose parameter to True.

See also

Calculate a look-at matrix for OpenGL

04 February 2017

Math – Using quaternions to create a rotation matrix

The best way I found to create a rotation matrix with all three axes is with quaternions. The following code is C#:

Initialize

The Quaternion class has four properties: W, X, Y and Z. "W" is the angle, and the other represent the axis. I will only use unit quaternions, meaning the rotation is around one of the three axes only. You initialize an identity quaternion by setting them to (1, 0, 0, 0). I create one for each rotation like so:

var rotx = new Quaternion(Rotation.X, 1, 0, 0);
var roty = new Quaternion(Rotation.Y, 0, 1, 0);
var rotz = new Quaternion(Rotation.Z, 0, 0, 1);

The quaternion's constructor initializes those arguments as:

double r = (angle * (Math.PI / 180));
W = (float)Math.Cos(r / 2);

double s = Math.Sin(r / 2);
X = (float)(x * s);
Y = (float)(y * s);
Z = (float)(z * s);

Multiply

Next, we combine them all into one quaternion:

var rot = rotx * roty * rotz;

The method that multiplies two quaternions is defined as follows:

public static Quaternion operator *(Quaternion a, Quaternion b)
{
    var c = new Quaternion();
    c.W = a.W * b.W - a.X * b.X - a.Y * b.Y - a.Z * b.Z;
    c.X = a.W * b.X + a.X * b.W + a.Y * b.Z - a.Z * b.Y;
    c.Y = a.W * b.Y - a.X * b.Z + a.Y * b.W + a.Z * b.X;
    c.Z = a.W * b.Z + a.X * b.Y - a.Y * b.X + a.Z * b.W;
    return c;
}

Rotate

To get the matrix I needed to pass to OpenGL, I created another class called "Matrix", which is a 4x4 matrix containing a 16 element array. Then a method takes the quaternion and adds the rotation to this matrix. It took a while to find a way to do this that worked with OpenGL, but I finally found it in the .net framework.

var matrix = new Matrix();
matrix.Rotate(rot); //"rot" being the quaternion from before.

public void Rotate(Quaternion rotation)
{
    float x2 = rotation.X + rotation.X;
    float y2 = rotation.Y + rotation.Y;
    float z2 = rotation.Z + rotation.Z;

    float xx = rotation.X * x2;
    float xy = rotation.X * y2;
    float xz = rotation.X * z2;
    float yy = rotation.Y * y2;
    float yz = rotation.Y * z2;
    float zz = rotation.Z * z2;
    float wx = rotation.W * x2;
    float wy = rotation.W * y2;
    float wz = rotation.W * z2;

    Values[0, 0] = 1.0f - (yy + zz);
    Values[0, 1] = xy + wz;
    Values[0, 2] = xz - wy;

    Values[1, 0] = xy - wz;
    Values[1, 1] = 1.0f - (xx + zz);
    Values[1, 2] = yz + wx;

    Values[2, 0] = xz + wy;
    Values[2, 1] = yz - wx;
    Values[2, 2] = 1.0f - (xx + yy);
}

See also

Align a rotation matrix with a normal

23 July 2014

Math - Extract the RGB values from a long color

This is a short little peace of code to extract the RGB components of a color stored in a single long value – like they are in Visual Basic. This code is in Apple's Swift language, but that really doesn't matter. You just need to know it's an extension on the Int type and "self" refers to the variable containing the long color.
extension Int {
  func toColor() -> UIColor {
    let r = self % 256
    let g = ((self - r) % 65536) / 256
    let b = (self - g) / 65536
    return UIColor(red: Float(r), green: Float(g), blue: Float(b), alpha: 1)
  }
}

10 March 2014

MVC - Resize an image

It turns out there is a helper class in the System.Web namespace for treating images. This class, WebImage, makes things like resizing e.g. a user profile picture when it is uploaded very easy:
public void FormatPicture(HttpPostedFileBase file) {
  WebImage image = new WebImage(file.InputStream);
  if (image.Width > 85 || image.Height > 85) {
    int w = image.Width;
    int h = image.Height;
    if (w > h) {
      w = 85;
      h = image.Height * w / image.Width;
    }
    else {
      h = 85;
      w = image.Width * h / image.Height;
    }
    image.Resize(w, h);
  }
  image.Save(PictureFilepath);
}
The HttpPostedFileBase file comes from the view model and contains the uploaded image from the file control. In this example the image is resized to a maximum of 85 pixels, with the smaller dimension interpolated, and stored.

28 January 2013

Math - The split-and-merge algorithm

The split-and-merge or (Ramer-)Douglas-Peucker algorithm simplifies a list of points, removing those deemed redundant with respect to a given tolerance. You can read more about it here. I used it to reduce the input of the mouse cursor to a manageable set of points in a drawing application. Next is an implementation in C# in the form of an extension that acts on a List<Point>:

The entry method:

internal static List<Point> SplitAndMerge(this List<Point> points, double tolerance) {
  if (points == null || points.Count < 3) {
    return points;
  }
  else {
    List<int> indices = new List<int>();
    indices.Add(0);
    indices.Add(points.Count - 1);

    points.SplitAndMerge(0, points.Count - 1, tolerance, ref indices);

    List<point> result = new List<Point>();
    indices.Sort();
    foreach (int i in indices)
      result.Add(points[i]);
    return result;
  }
}

The private submethod that handles the recursive calls:

private static void SplitAndMerge(this List<Point> points, int indexFirst, int indexLast, double tolerance, ref List<int> indices) {
  double maxDist = 0d;
  int indexMaxDist = 0;
  double dist = 0d;

  for (int i = indexFirst; i < indexLast; i++) {
    dist = points[i].PerpendicularDistanceFrom(points[indexFirst], points[indexLast]);
    if (dist > maxDist) {
      maxDist = dist;
      indexMaxDist = i;
    }
  }

  if (maxDist > tolerance && indexMaxDist > 0) {
    indices.Add(indexMaxDist);
    points.SplitAndMerge(indexFirst, indexMaxDist, tolerance, ref indices);
    points.SplitAndMerge(indexMaxDist, indexLast, tolerance, ref indices);
  }
}

A helper method that calculates the distance between a point p to the line between a and b:

internal static double PerpendicularDistanceFrom(this Point p, Point a, Point b) {
  double area = Math.Abs(0.5d * (a.X * b.Y + b.X * p.Y + p.X * a.Y - b.X * a.Y - p.X * b.Y - a.X * p.Y));
  double bottom = Math.Sqrt((a.X - b.X) * (a.X - b.X) + (a.Y - b.Y) * (a.Y - b.Y));
  return area / bottom * 2d;
}

31 May 2012

Math - Scaling a value

Sometimes you have this thing where you have two ranges, and you need to scale a value from the one to the other; e.g.:
Range 1: 0.....x.....100   x=50
Range 2: 0.....y.....500   y=?
Thus:
100 > 500
 50 >   ?
  x >   y

C# code

Thus, I want to know the value of y. I wrote this extension to get it:
internal static double Scale(this double value, double maxValue, double maxScale) {
  if (maxValue == 0 || maxScale == 0)
    return 0;
  else if (maxValue == maxScale)
    return value;
  else
    return value / (maxValue / maxScale);
}

result = 50.Scale(100, 500); //Result will be 250

Try it


if (max. value)equals (max. scale)
then (value)is (result)
...

See also

Interpolating a value

24 April 2011

C# - Convert hex color to RGB

To convert a hexadecimal color value like #FF00FF to a RGB color value, I wrote this function:

string color = "#FF00FF"; //This would be a parameter
if (color.StartsWith("#"))
  color = color.Remove(0, 1);
byte r, g, b;
if (color.Length == 3) {
  r = Convert.ToByte(color[0] + "" + color[0], 16);
  g = Convert.ToByte(color[1] + "" + color[1], 16);
  b = Convert.ToByte(color[2] + "" + color[2], 16);
}
else if (color.Length == 6) {
  r = Convert.ToByte(color[0] + "" + color[1], 16);
  g = Convert.ToByte(color[2] + "" + color[3], 16);
  b = Convert.ToByte(color[4] + "" + color[5], 16);
}
else {
  throw new ArgumentException("Hex color " + color + " is invalid.");
}
return new Color.FromArgb(255, r, g, b);