Wednesday, July 17, 2019

Dot products and planes

I'm going to write some blog posts to try to help share some insights about geometry. Here I'm starting with the most important basic operations.

The basics

  • origin a point at 0,0,0
  • unit length a vector that has a length of 1
  • normalization scaling a vector so that it's unit length
  • normal a unit vector that is used to describe a direction
  • magnitude the length of a vector

The dot product

So the dot product is an operation that looks like this
Vector3 DotProduct(Vector3 a, Vector3 b)
    return a.x * b.x + a.y * b.y + a.z * b.z;
Okay, sure, that's the code, but what does it do?

The dot-product returns the distance from the origin (0,0,0)
to the projection of point B on vector A, in terms of the length of vector A.

If vector A is unit length, this becomes:

The dot-product returns the distance from the origin (0,0,0)
to the projection of point B on vector A

If both vectors are unit length, then the dot product will return 1 when they're perfectly aligned, -1 when one vector is pointing in the opposite direction, and 0 when the vectors are orthogonal.

So if the length of vector A is twice as long, then the returned dot product is half as big.

Note that a dot product is "Commutative"
this which means you can swap vector A & B and you'll get the same results

Distance of a point along a line

So imagine having a line that is defined by a point lineStart and a normalized lineDirection, and we want to know the distance from a point P to lineStart, how would we do that?

Well if we take the dot product of lineDirection and point P, we have the distance to the origin, which is not what we want. However, if we both move the point P and lineStart so that lineStart is at the origin, we can use the dot-product.

We can simply do this by subtracting lineStart from both points
lineStart - lineStart = 0,0,0 (the origin)
P - lineStart = point P at the same relative distance to lineStart
The final equation then becomes
distanceAlongLine = DotProduct((P - lineStart), lineDirection)

The plane equation

Another important tool in your vector algebra arsenal is the plane equation:
Ax+By+Cz = D
Ax+By+Cz-D = 0
As you can see, a plane is stored as 4 floating point values (ABCD).
The ABC part is the normal, which signifies in what direction the plane is facing.
The D part is the (negative) distance of the plane to the origin, along that normal.

Since a plane is infinite in every direction except the direction of the normal, you can define any 2D plane in 3D space this way.

So this makes the distance of a point to a plane:
signedDistanceToPlane = DotProduct(planeNormal, point) + planeDistance
Note that the distance is signed, meaning that you can tell if a point is in front or behind the plane by checking it's sign.

If you need a point that lies on a plane, you can use:
pointOnPlane = planeNormal * -planeDistance 
And in reverse, if you have a normal for a plane you can find the planeDistance, the D part of the plane equation, with:
planeDistance = -DotProduct(planeNormal, pointOnPlane)
Note that this works with any point that lies on the plane.

If you have 3 points A,B & C, you can calculate the normal by:
normal = Normalize(CrossProduct(B - A, C - A))
Now imagine these 3 points all lying on the same plane, then B-A and C-A are 2 vectors that also lie on this plane. The cross product takes these 2 vectors and returns a vector that is perpendicular to both of them, which would be a vector pointing away from the plane. Normalize scales it to unit length, giving us the plane normal.

Note that if these 3 points lie on the same line, it would result in a zero length normal.

If you want to calculate the normal of a polygon, don't just take the first 3 points and try to create a normal out of them, since they might be aligned even though subsequent points may not be.

For polygons it's better to use Newell's algorithm, this algorithm will work with most polygons as long as they're:
  • not self-intersecting,
  • planar (all points lie on the same plane) 
  • not degenerate (all points lie on the same line or form a singularity)

Next time

I'll write some more posts in the future about

No comments:

Post a Comment