Get into GameDev:
cheat-codes for gamedev interviews
━ Maths - Planes ━
Introduction
Work - In - Progress
Hi, you're early! I haven't ported this page over from my draft just yet but you can preview it at the link below for early-access:
tinyurl.com/gamedevStudySheet
tinyurl.com/gamedevStudySheet
Planes
Planes are 2D structures that stretch out into infinity. Below is the formula for a plane:
ax + by + cz = d
Before we continue further, I'd like to address that planes can alternatively be represented by....
ax + by + cz = d
- n ≡ [a, b, c] is a vector representing the norm of the plane
- d / |n| is the signed distance from Origin
- In the above equation, d is the positive distance from the origin. Sometimes you will see the equation in this form Ax + By + Cz - D = 0. In those cases, d is the negative distance form the origin.
Before we continue further, I'd like to address that planes can alternatively be represented by....
- the formula above
- three points within the plane (aka a triangle), as long as they are not all on the same line
- one point and two vectors within the plane (parametric form)
- one point "P" and a vector norm "n", using the formula: n•(X-P)=0. X is any input and P is a known point on the plane. Or you can simplify to n•X=d, d = n•P where d is the distance of plane from the origin if n is a normalized. if you multiply n and P out you get the equation: ax+by+cz-d = 0 which is the classical plane formula.
Practice Question: Consider the formula for a plane: ax + by + cz = d. Consider if any one of these values (a, b, c, or d) were 0, what would that mean geometrically for the plane?
Answer:
- if d == 0, plane passes through origin
- If a == 0, then the plane extends parallel to the x-axis, aka no constraint on that axis
- if a == 0 and b == 0, then the plane contains lines that are parallel to the x and y axis and the z-axis is parallel to the plane’s norm
Answer:
- if d == 0, plane passes through origin
- If a == 0, then the plane extends parallel to the x-axis, aka no constraint on that axis
- if a == 0 and b == 0, then the plane contains lines that are parallel to the x and y axis and the z-axis is parallel to the plane’s norm
An unsigned int-32 would have all 32 bits to represent its value, but we need to remember to subtract one because one combination of bits is used to represent 0. Therefore the max value of a uint-32 is 2^32-1.
But I asked for a signed int-32 which requires the first bit to represent the sign. Therefore the max value of a uint-32 is 2^31-1.
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Given two planes expressed in the form ax + by + cz = d, we can compare the ratios of each plane's terms to reach the following conclusions:
Planes: Practice Problems
Practice Question: Given a plane defined by a, b, c, and d, derive a point "P" that lies on the plane.
Answer:
First let's construct the norm of the plane using a, b, and c. n = [ a, b, c ]. This norm is not normalized, that's next step.
Normalize n by dividing it by it's own magnitude. n ≡ n / |n|. This n that we have derived is very powerful, it's a normalized normal vector that is perpendicular to the plane. And since the shortest distance from any point is a straight line, that means the shortest distance from any point to this plane is along this vector.
Remember, d / |n| is the signed distance from origin. So if we calculate this value:
d' = d / |n|
Then d' is our distance from the origin to the plane.
Now if we combine these two pieces of information we can determine that if we add n to the origin, scaled by d' then we will get a point on the plane. Not just any point, but the point on the plane closest to the origin. I like to this of this as the 'center' point of the plane but that is kind of silly since a plane is infinite and therefore doesn't really have a center.
P = [ 0,0,0 ] + ( n * d' )
Answer:
First let's construct the norm of the plane using a, b, and c. n = [ a, b, c ]. This norm is not normalized, that's next step.
Normalize n by dividing it by it's own magnitude. n ≡ n / |n|. This n that we have derived is very powerful, it's a normalized normal vector that is perpendicular to the plane. And since the shortest distance from any point is a straight line, that means the shortest distance from any point to this plane is along this vector.
Remember, d / |n| is the signed distance from origin. So if we calculate this value:
d' = d / |n|
Then d' is our distance from the origin to the plane.
Now if we combine these two pieces of information we can determine that if we add n to the origin, scaled by d' then we will get a point on the plane. Not just any point, but the point on the plane closest to the origin. I like to this of this as the 'center' point of the plane but that is kind of silly since a plane is infinite and therefore doesn't really have a center.
P = [ 0,0,0 ] + ( n * d' )
An unsigned int-32 would have all 32 bits to represent its value, but we need to remember to subtract one because one combination of bits is used to represent 0. Therefore the max value of a uint-32 is 2^32-1.
But I asked for a signed int-32 which requires the first bit to represent the sign. Therefore the max value of a uint-32 is 2^31-1.
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Practice Question: Given a plane defined by a, b, c, and d, and a point "P1" that is on the plane. Derive a different point "P2" that also lies on the plane.
Answer: As a natural follow up to the previous question, we are now tasked to derive an additional point within the plane. The key here is to solve the equation ax + by + cz = d with an arbitrary input value for one of the variables.
- If a, b, and c are zero then this plane is a malformed and we can return a bogus value, probably (0,0,0).
- If all but one of the values are zero then we have a line and again the plane is malformed so we can return a bogus value, probably by taking the non-zero component (let's say it is x) and making that value non-zero such as (P1.x * 2, 0, 0). I did *2 because only a P1.x of zero would result in zero and we just said P1.x is not zero so I am sure this point will be the least bogus it can be.
- If 2 or more values are non-zero then we have an actual plane, let's get started!
We want to zero one of the values to simplify the equation but we need at least two non-zero values. So if a and b are non-zero we can zero z. By that I mean we are trying to construct a 3D point on the plane and we can choose zero to be the z value for our point. This would simplify the formula:
ax + by + cz = d
z ≡ 0
ax + by = d
Now we can rearrange the formula to solve for x and y. We earlier made sure to confirm that both a and b were non-zero so that this step would be possible. If a or b were zero, then we would pair whatever the non-zero values of abc were such as "b and c" or "a and c".
ax + by = d
ax = d - by
x = ( d - by ) / a
Now we already have chosen the value of 0 for z, we just need to choose a value for y and we can solve for x. We want to make sure P2 does not become P1 so we can make y = P1.y * 2. Or something like that. If P1.y is zero then just do y = P1.y + 1. It doesn't really matter what P2.y is as long as it is not P1.y.
y ≡ P1.y * 2
x = ( d - b * P1.y * 2 ) / a
P2 = [ ( d - b * P1.y * 2 ) / a, P1.y * 2, 0]
Answer: As a natural follow up to the previous question, we are now tasked to derive an additional point within the plane. The key here is to solve the equation ax + by + cz = d with an arbitrary input value for one of the variables.
- If a, b, and c are zero then this plane is a malformed and we can return a bogus value, probably (0,0,0).
- If all but one of the values are zero then we have a line and again the plane is malformed so we can return a bogus value, probably by taking the non-zero component (let's say it is x) and making that value non-zero such as (P1.x * 2, 0, 0). I did *2 because only a P1.x of zero would result in zero and we just said P1.x is not zero so I am sure this point will be the least bogus it can be.
- If 2 or more values are non-zero then we have an actual plane, let's get started!
We want to zero one of the values to simplify the equation but we need at least two non-zero values. So if a and b are non-zero we can zero z. By that I mean we are trying to construct a 3D point on the plane and we can choose zero to be the z value for our point. This would simplify the formula:
ax + by + cz = d
z ≡ 0
ax + by = d
Now we can rearrange the formula to solve for x and y. We earlier made sure to confirm that both a and b were non-zero so that this step would be possible. If a or b were zero, then we would pair whatever the non-zero values of abc were such as "b and c" or "a and c".
ax + by = d
ax = d - by
x = ( d - by ) / a
Now we already have chosen the value of 0 for z, we just need to choose a value for y and we can solve for x. We want to make sure P2 does not become P1 so we can make y = P1.y * 2. Or something like that. If P1.y is zero then just do y = P1.y + 1. It doesn't really matter what P2.y is as long as it is not P1.y.
y ≡ P1.y * 2
x = ( d - b * P1.y * 2 ) / a
P2 = [ ( d - b * P1.y * 2 ) / a, P1.y * 2, 0]
An unsigned int-32 would have all 32 bits to represent its value, but we need to remember to subtract one because one combination of bits is used to represent 0. Therefore the max value of a uint-32 is 2^32-1.
But I asked for a signed int-32 which requires the first bit to represent the sign. Therefore the max value of a uint-32 is 2^31-1.
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Practice Question: Given a plane defined by a, b, c, and d, and a point "P1", determine if P1 is above, below, or on the plane.
Answer: Checking if the point is on the plane is easy, just plug it into the formula.
ax + by + cz == d
a( P1.x ) + b (P1.y ) + c ( P1.z ) == d
^ If the two sides are not equal, then P1 is not on the plane.
If P1 is not a part of the plane, then we are going to need a point on the plane to proceed. Solve the subproblem to finding a point on the plane. We have explored the solution to this subproblem in a previous question (see above). This will result in P2, a point on the plane.
Construct vector P2P1 (going from the plane to P1) and now we can do a dot product between this vector and the plane's normal. From the dot product, we can determine the angle between these vectors. If the vector is acute, then we know the point is on the side of the plane that the normal points towards this is generally regarded as the "top" of the plane or "above" the plane. If the angle is obtuse then the point is below the plane. The angle will not be right because we already determine the point is not in the plane.
Answer: Checking if the point is on the plane is easy, just plug it into the formula.
ax + by + cz == d
a( P1.x ) + b (P1.y ) + c ( P1.z ) == d
^ If the two sides are not equal, then P1 is not on the plane.
If P1 is not a part of the plane, then we are going to need a point on the plane to proceed. Solve the subproblem to finding a point on the plane. We have explored the solution to this subproblem in a previous question (see above). This will result in P2, a point on the plane.
Construct vector P2P1 (going from the plane to P1) and now we can do a dot product between this vector and the plane's normal. From the dot product, we can determine the angle between these vectors. If the vector is acute, then we know the point is on the side of the plane that the normal points towards this is generally regarded as the "top" of the plane or "above" the plane. If the angle is obtuse then the point is below the plane. The angle will not be right because we already determine the point is not in the plane.
An unsigned int-32 would have all 32 bits to represent its value, but we need to remember to subtract one because one combination of bits is used to represent 0. Therefore the max value of a uint-32 is 2^32-1.
But I asked for a signed int-32 which requires the first bit to represent the sign. Therefore the max value of a uint-32 is 2^31-1.
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Practice Question: Given a plane defined by a, b, c, and d, and a vector v, project v onto the plane.
Answer: Any vector can be broken into component vectors. For example the vector [ x, y, z ] can be broken into [x, 0, 0] + [0, y, 0] + [0, 0, z]. In this problem we want the component of v that are within the plane.
In 3D, a plane is a hyperspace. If we are dealing with a n dimensional subspace then a hyperspace is any n-1 dimensional subspace. In this case since we are in 3D, aka "R3", so n=3. A plane is a 2 dimensional subspace so a plane is a hyperspace of R3.
The reason why this matters is because that means if we remove the component of v that is not in the plane, we will be left with the components of v that are in the plane. To first get the part of v that is not in the plane, project v onto the plane's normal. Let's call this v'. Now we just remove those component from v which is as easy as v - v' = v'' and that's our solution.
Answer: Any vector can be broken into component vectors. For example the vector [ x, y, z ] can be broken into [x, 0, 0] + [0, y, 0] + [0, 0, z]. In this problem we want the component of v that are within the plane.
In 3D, a plane is a hyperspace. If we are dealing with a n dimensional subspace then a hyperspace is any n-1 dimensional subspace. In this case since we are in 3D, aka "R3", so n=3. A plane is a 2 dimensional subspace so a plane is a hyperspace of R3.
The reason why this matters is because that means if we remove the component of v that is not in the plane, we will be left with the components of v that are in the plane. To first get the part of v that is not in the plane, project v onto the plane's normal. Let's call this v'. Now we just remove those component from v which is as easy as v - v' = v'' and that's our solution.
An unsigned int-32 would have all 32 bits to represent its value, but we need to remember to subtract one because one combination of bits is used to represent 0. Therefore the max value of a uint-32 is 2^32-1.
But I asked for a signed int-32 which requires the first bit to represent the sign. Therefore the max value of a uint-32 is 2^31-1.
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Practice Question: Given a plane defined by a, b, c, and d, and a point "P1", determine "P2": the closest point to P1 that lies within the plane.
Answer: Find any point on the plane, call it P3. Project line segment P1P3 onto the plane and it will point to P2.
https://i.gyazo.com/4e00a511705d86765fa14a316b60d81b.png
Answer: Find any point on the plane, call it P3. Project line segment P1P3 onto the plane and it will point to P2.
https://i.gyazo.com/4e00a511705d86765fa14a316b60d81b.png
An unsigned int-32 would have all 32 bits to represent its value, but we need to remember to subtract one because one combination of bits is used to represent 0. Therefore the max value of a uint-32 is 2^32-1.
But I asked for a signed int-32 which requires the first bit to represent the sign. Therefore the max value of a uint-32 is 2^31-1.
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Practice Question: Given a plane defined by a, b, c, and d, and a point P1, find a line that is parallel to the plane and contains P1.
Answer: For our first approach we can find the closest point on the plane's normal to P1. This is the basic question "find the point closest to a point on a line" we solved it in the previous chapter in the practice question "Find the distance between a line segment, BC, and point, A." Now that we have the closest point to P1 on the planes normal, let's call it P2. The line P1P2 will be parallel to the plane and it will also contain P1. Can you think of any limitations with this approach? If P2 is P1 then we will not have a line ;P If that is that case we just need to push P1 away from the plane's normal in the direction of a vector parallel to the plane.
The subproblem here would be "find any vector parallel to the plane" and add it to P1. To find a vector parallel to the plane, just find two distinct points in the plane and subtract them. In previous questions above we have discussed how to find two distinct points in a plane.
--------------------------
Here is a second approach contributed by reader Amir Azmi, it does have the same limitation as the first approach: if P is on the plane's normal you will need to push it off. Also note the variable names are different.
Find point on plane, call it Y, get normalized vector call it N
Create Vector YP (P - Y)
Project YP onto N
Get point E which is the projected point P onto N by adding Y + NP
Get Vector PE which is the parallel line to the plane (E - P)
https://i.gyazo.com/37779eaffd75f5e8af3679e0a66f5144.png
----------------------------
A third approach! First we solve the subproblem "find the closest point to P1 that lies within the plane", call this P2. That means P1P2 will be normal to the plane. Find any point on the plane that is not P2, call it P3 (we have discussed how to do this in a previous subproblem). P2P3 is a line on the plane if we offset it by P1P2 it will be pushed off of the plane to include P1 and since P1P2 is normal we know that it will still be parallel to the plane. In this diagram, P2P3 (black arrow) and it is pushed by P1P2 (red arrow) to get the solution vector (blue arrow):
https://i.gyazo.com/ea5f7f235296a2428fa7b922a97f1bc3.png
Answer: For our first approach we can find the closest point on the plane's normal to P1. This is the basic question "find the point closest to a point on a line" we solved it in the previous chapter in the practice question "Find the distance between a line segment, BC, and point, A." Now that we have the closest point to P1 on the planes normal, let's call it P2. The line P1P2 will be parallel to the plane and it will also contain P1. Can you think of any limitations with this approach? If P2 is P1 then we will not have a line ;P If that is that case we just need to push P1 away from the plane's normal in the direction of a vector parallel to the plane.
The subproblem here would be "find any vector parallel to the plane" and add it to P1. To find a vector parallel to the plane, just find two distinct points in the plane and subtract them. In previous questions above we have discussed how to find two distinct points in a plane.
--------------------------
Here is a second approach contributed by reader Amir Azmi, it does have the same limitation as the first approach: if P is on the plane's normal you will need to push it off. Also note the variable names are different.
Find point on plane, call it Y, get normalized vector call it N
Create Vector YP (P - Y)
Project YP onto N
Get point E which is the projected point P onto N by adding Y + NP
Get Vector PE which is the parallel line to the plane (E - P)
https://i.gyazo.com/37779eaffd75f5e8af3679e0a66f5144.png
----------------------------
A third approach! First we solve the subproblem "find the closest point to P1 that lies within the plane", call this P2. That means P1P2 will be normal to the plane. Find any point on the plane that is not P2, call it P3 (we have discussed how to do this in a previous subproblem). P2P3 is a line on the plane if we offset it by P1P2 it will be pushed off of the plane to include P1 and since P1P2 is normal we know that it will still be parallel to the plane. In this diagram, P2P3 (black arrow) and it is pushed by P1P2 (red arrow) to get the solution vector (blue arrow):
https://i.gyazo.com/ea5f7f235296a2428fa7b922a97f1bc3.png
An unsigned int-32 would have all 32 bits to represent its value, but we need to remember to subtract one because one combination of bits is used to represent 0. Therefore the max value of a uint-32 is 2^32-1.
But I asked for a signed int-32 which requires the first bit to represent the sign. Therefore the max value of a uint-32 is 2^31-1.
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Practice Question: Given a plane defined by a, b, c, and d, and a point P1, find the distance from the point to the plane.
Answer: Find the normalized norm of the plane, call it n. Find any point on the plane, call it P2. Project P2P1 onto n. The resulting vector, v, is the shortest vector from the plane to the point. Calculate the magnitude of the vector for the distance.
https://i.gyazo.com/f9e4d75b17da0335813de52aff665877.png
Answer: Find the normalized norm of the plane, call it n. Find any point on the plane, call it P2. Project P2P1 onto n. The resulting vector, v, is the shortest vector from the plane to the point. Calculate the magnitude of the vector for the distance.
https://i.gyazo.com/f9e4d75b17da0335813de52aff665877.png
An unsigned int-32 would have all 32 bits to represent its value, but we need to remember to subtract one because one combination of bits is used to represent 0. Therefore the max value of a uint-32 is 2^32-1.
But I asked for a signed int-32 which requires the first bit to represent the sign. Therefore the max value of a uint-32 is 2^31-1.
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Practice Question: Given a plane defined by a, b, c, and d, and a line L, determine their intersection.
Answer: The first insight is that if a line is not parallel to a plane, then it must be intersecting the plane. This is because a plane is defined by 2 orthogonal vectors and if we add a third vector then we will have a basis in R3 (3-dimensional space). Remember that your set of vectors does not need to be orthogonal to be a basis, they need only be non-collinear. For example, β={(1,0),(1,1)} forms a basis for R2 but is not an orthogonal basis.
So our first test is to determine if the line is parallel to the plane, can you remember how to determine that? Here's a hint: in order to see if a line is parallel to the plane, that's the same as checking if the line is perpendicular to something perpendicular to the plane. We can take the plane's normal vector, which is perpendicular to the plane, and if that vector is perpendicular to our line then the line is parallel to the plane. Construct the normal vector using a, b, and c: v = [ a, b, c ]. v • L = ?.
If the result is 0, then the line is parallel to the plane. So that means we can have a coincident case (0 intersections) or a disjoint case (infinite intersections if the plane contains the line). To determine which of these cases we have, take a point from the line and see if it satisfies the plane's formula.
If the result of the dot product was non-zero, then we know the line intersects the plane and we just need to find the intersection point. Convert the plane and line into their parametric equations and we will combine them to solve for a point.
( X - Q ) • n = 0
This is the plane parametric formula where Q is a point on the plane and X is an input point.
P + t d
This is the parametric formula for a line where P is a start point and d is the direction vector.
Let us now combine these formulas to solve for t, the time of intersection.
( X - Q ) • n = 0
( ( P + t d ) - Q ) • n = 0
( P - Q + t d ) • n = 0
( P - Q ) • n + t d • n = 0
Now we subtract “( P - Q ) • n” from both sides...
t d • n = ( Q - P ) • n
t = ( Q - P ) • n / ( d • n )
Aha, we have solved for t! But beware, there is a division here so we should be careful to not divide by zero. The denominator will only be zero when the plane normal and the line direction vector have a dot product of zero. And as you will recall, we earlier made sure that was not the case, so we can rest assured that we will not have a zero denominator.
If this line was instead a ray or line segment, we would just need to verify that our t result lies within a valid range for the structure.
Alternative approach:
Jorge here takes a geometric approach instead of an algebraic approach. Check out his video to see if that approach makes more sense for you. It is useful to try many ways to approach the same problem as future problems may be easier to think of in different ways.
https://www.youtube.com/watch?v=fIu_8b2n8ZM&list=PLW3Zl3wyJwWN6V7IEb2BojFYOlgpryp1-&index=4&ab_channel=JorgeRodriguez
Answer: The first insight is that if a line is not parallel to a plane, then it must be intersecting the plane. This is because a plane is defined by 2 orthogonal vectors and if we add a third vector then we will have a basis in R3 (3-dimensional space). Remember that your set of vectors does not need to be orthogonal to be a basis, they need only be non-collinear. For example, β={(1,0),(1,1)} forms a basis for R2 but is not an orthogonal basis.
So our first test is to determine if the line is parallel to the plane, can you remember how to determine that? Here's a hint: in order to see if a line is parallel to the plane, that's the same as checking if the line is perpendicular to something perpendicular to the plane. We can take the plane's normal vector, which is perpendicular to the plane, and if that vector is perpendicular to our line then the line is parallel to the plane. Construct the normal vector using a, b, and c: v = [ a, b, c ]. v • L = ?.
If the result is 0, then the line is parallel to the plane. So that means we can have a coincident case (0 intersections) or a disjoint case (infinite intersections if the plane contains the line). To determine which of these cases we have, take a point from the line and see if it satisfies the plane's formula.
If the result of the dot product was non-zero, then we know the line intersects the plane and we just need to find the intersection point. Convert the plane and line into their parametric equations and we will combine them to solve for a point.
( X - Q ) • n = 0
This is the plane parametric formula where Q is a point on the plane and X is an input point.
P + t d
This is the parametric formula for a line where P is a start point and d is the direction vector.
Let us now combine these formulas to solve for t, the time of intersection.
( X - Q ) • n = 0
( ( P + t d ) - Q ) • n = 0
( P - Q + t d ) • n = 0
( P - Q ) • n + t d • n = 0
Now we subtract “( P - Q ) • n” from both sides...
t d • n = ( Q - P ) • n
t = ( Q - P ) • n / ( d • n )
Aha, we have solved for t! But beware, there is a division here so we should be careful to not divide by zero. The denominator will only be zero when the plane normal and the line direction vector have a dot product of zero. And as you will recall, we earlier made sure that was not the case, so we can rest assured that we will not have a zero denominator.
If this line was instead a ray or line segment, we would just need to verify that our t result lies within a valid range for the structure.
Alternative approach:
Jorge here takes a geometric approach instead of an algebraic approach. Check out his video to see if that approach makes more sense for you. It is useful to try many ways to approach the same problem as future problems may be easier to think of in different ways.
https://www.youtube.com/watch?v=fIu_8b2n8ZM&list=PLW3Zl3wyJwWN6V7IEb2BojFYOlgpryp1-&index=4&ab_channel=JorgeRodriguez
An unsigned int-32 would have all 32 bits to represent its value, but we need to remember to subtract one because one combination of bits is used to represent 0. Therefore the max value of a uint-32 is 2^32-1.
But I asked for a signed int-32 which requires the first bit to represent the sign. Therefore the max value of a uint-32 is 2^31-1.
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Practice Question: Given a plane defined by a1, b1, c1, and d1, and another plane defined by a2, b2, c2, and d2, determine their intersection.
Answer: Similar to the last problem, we first want to determine if these planes are parallel. Derive the plane norms n1 and n2. If the planes are parallel, then so too will these normals be parallel. To check if the normals are parallel, we can use the cross product and check if the result is the zero vector: n1 x n2 = v.
If the resulting vector v is 0, test a point to see if the planes are coincident. If they are, then the planes lie within each other and any one of the planes may define their intersection. If they are not coincident, then they are disjoint and have no intersection.
If the resulting vector v is NOT 0, then v defines the direction vector of the line of intersection between the two points.
Diagram: https://i.gyazo.com/a853401b47cea3ec5e265719aedef034.png
But we are not done, since a direction vector is only half of the information we need to define a line. The other half is at least one point. So now we just need to determine a point that lies on both planes. Sadly, between all of each plane's variables, we have too many unknowns to solve this problem outright. But since we now have v, we can use it to safely simplify the problem. Any component of v that is non-zero can be used to safely zero the corresponding components of the plane formulas. For example, if our plane formulas are...
a1X + b1Y + c1Z - d = 0 AND a1X + b1Y + c1Z - d= 0
Then if the v.z != 0, we can zero the z components of our formula:
a1X + b1Y + c1 ( 0 ) - d = 0 AND a1X + b1Y + c1 ( 0 ) - d= 0
a1X + b1Y - d = 0 AND a1X + b1Y - d= 0
If v.z was zero then we would have chosen the x or y component instead. We know that at least one component is not zero because the earlier part of this problem was determining that v != 0.
Once we have simplified the formulas, we can combine them to express x and y using only the terms of the planes.
X = ( b1 * d2 - b2 * d1 ) / ( a1 * b2 - e1 * b1 )
Y = ( b2 * d1 - a1 * d2 ) / ( a1 * b2 - e1 * b1 )
Z = 0
We solve to determine point P = [ X, Y, Z ].
Then we have completed the problem and determined the intersection to be the line defined by v and P.
Answer: Similar to the last problem, we first want to determine if these planes are parallel. Derive the plane norms n1 and n2. If the planes are parallel, then so too will these normals be parallel. To check if the normals are parallel, we can use the cross product and check if the result is the zero vector: n1 x n2 = v.
If the resulting vector v is 0, test a point to see if the planes are coincident. If they are, then the planes lie within each other and any one of the planes may define their intersection. If they are not coincident, then they are disjoint and have no intersection.
If the resulting vector v is NOT 0, then v defines the direction vector of the line of intersection between the two points.
Diagram: https://i.gyazo.com/a853401b47cea3ec5e265719aedef034.png
But we are not done, since a direction vector is only half of the information we need to define a line. The other half is at least one point. So now we just need to determine a point that lies on both planes. Sadly, between all of each plane's variables, we have too many unknowns to solve this problem outright. But since we now have v, we can use it to safely simplify the problem. Any component of v that is non-zero can be used to safely zero the corresponding components of the plane formulas. For example, if our plane formulas are...
a1X + b1Y + c1Z - d = 0 AND a1X + b1Y + c1Z - d= 0
Then if the v.z != 0, we can zero the z components of our formula:
a1X + b1Y + c1 ( 0 ) - d = 0 AND a1X + b1Y + c1 ( 0 ) - d= 0
a1X + b1Y - d = 0 AND a1X + b1Y - d= 0
If v.z was zero then we would have chosen the x or y component instead. We know that at least one component is not zero because the earlier part of this problem was determining that v != 0.
Once we have simplified the formulas, we can combine them to express x and y using only the terms of the planes.
X = ( b1 * d2 - b2 * d1 ) / ( a1 * b2 - e1 * b1 )
Y = ( b2 * d1 - a1 * d2 ) / ( a1 * b2 - e1 * b1 )
Z = 0
We solve to determine point P = [ X, Y, Z ].
Then we have completed the problem and determined the intersection to be the line defined by v and P.
An unsigned int-32 would have all 32 bits to represent its value, but we need to remember to subtract one because one combination of bits is used to represent 0. Therefore the max value of a uint-32 is 2^32-1.
But I asked for a signed int-32 which requires the first bit to represent the sign. Therefore the max value of a uint-32 is 2^31-1.
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Triangles
Triangles are a common form of restricted plane defined by three coplanar points. Triangles are composited to create more complicated 3D geometry. Right triangles in particular, as you have already seen, have some excellent properties for helping us with geometric problems. Often if we can find a right triangle, it can help us. A triangle is considered the 2D simplex, meaning it is the simplest 2D object we can express. A 0D simplex is a point, a 1D simplex is a line, and a 2D simplex is a triangle (btw a 3D simplex is a tetrahedron).
Pythagorean Theorem
A triangle's hypotenuse squared length is equal to the sum of it's other sides' squared lengths.
Pythagorean Theorem
A triangle's hypotenuse squared length is equal to the sum of it's other sides' squared lengths.
45-45-90 Theorem
In the specific case of an isosceles right triangle, the side lengths will always form the ratio 1 : 1 : sqrt( 2 ).
In the specific case of an isosceles right triangle, the side lengths will always form the ratio 1 : 1 : sqrt( 2 ).
Also please see the "Angles" section of the earlier chapter "Maths - Rotations" for a discussion of trigonometric functions such as sine and cosine. In that section we discussed two forms of coordinates: cartesian and polar. Triangles introduce their own form of coordinates called Barycentric coordinates.
Introducing Barycentric coordinates
Barycentric coordinates are a curious concept. The idea behind them is... if we split a mass such that each of the triangle's points has a different portion of the mass, where would the overall triangle's center of mass be? For example, if we put all of the mass on the triangle's first point and zero mass on the others, then that might be expressed as ( 1.0, 0, 0 ). This would result in a center of mass on the first point and would express a coordinate for the first point. Likewise we could express the second point as ( 0, 1.0, 0 ) or the third as ( 0, 0, 1.0 ). Or even the point which lies halfway between the edges of the first two points as ( 0.5, 0.5, 0 ). I should also note that barycentric weights can be negative, in which case the resulting point lies outside of the triangle. Here's a neat tutorial that walks through these coordinates:
https://codeplea.com/triangular-interpolation
Geometric Barycentric coordinates derivation
Remember that Barycentric coordinates are simply an expression of the weight ratios of points. If a point lies in the triangle, it is equivalent to the ratio of areas formed by triangles which contain the point as shown below.
Introducing Barycentric coordinates
Barycentric coordinates are a curious concept. The idea behind them is... if we split a mass such that each of the triangle's points has a different portion of the mass, where would the overall triangle's center of mass be? For example, if we put all of the mass on the triangle's first point and zero mass on the others, then that might be expressed as ( 1.0, 0, 0 ). This would result in a center of mass on the first point and would express a coordinate for the first point. Likewise we could express the second point as ( 0, 1.0, 0 ) or the third as ( 0, 0, 1.0 ). Or even the point which lies halfway between the edges of the first two points as ( 0.5, 0.5, 0 ). I should also note that barycentric weights can be negative, in which case the resulting point lies outside of the triangle. Here's a neat tutorial that walks through these coordinates:
https://codeplea.com/triangular-interpolation
Geometric Barycentric coordinates derivation
Remember that Barycentric coordinates are simply an expression of the weight ratios of points. If a point lies in the triangle, it is equivalent to the ratio of areas formed by triangles which contain the point as shown below.
Algebraic Barycentric coordinates derivation
While the geometric approach is intuitive, it's not performant and it is unable to express points that lie outside of the triangle. The basic idea behind these coordinates is that we are solving the following system of linear equations:
While the geometric approach is intuitive, it's not performant and it is unable to express points that lie outside of the triangle. The basic idea behind these coordinates is that we are solving the following system of linear equations:
And this system of equations can actually be simplified to a very straight forward computation for each weight:
I took these images from Van Winkle's blog post linked above so do remember to check it out for a more detailed explanation of these concepts. I should also note that you can use vector math to derive these weight using Cramer's rule which is an approach for solving systems of equations that uses determinants. Below is a diagram of the basic principle of Cramer's rule.
Here's a discussion of a Barycentric coordinate derivation that uses this approach:
https://gamedev.stackexchange.com/questions/23743/whats-the-most-efficient-way-to-find-barycentric-coordinates
As the comments in that discussion point out, we need to avoid division whenever we can. On a computer, a division is roughly ten times the cost of an addition or subtraction and more than two times the cost of a multiplication. One savvy commenter points out that we can computer the inverse of the denominator: ( 1 / demon ) and replace the "v =" and "w =" lines with a multiplication between the inverse instead of divisions. This would reduce our number of divisions from 2 to 1, good savings! These kinds of tricks are really common in engine development.
https://gamedev.stackexchange.com/questions/23743/whats-the-most-efficient-way-to-find-barycentric-coordinates
As the comments in that discussion point out, we need to avoid division whenever we can. On a computer, a division is roughly ten times the cost of an addition or subtraction and more than two times the cost of a multiplication. One savvy commenter points out that we can computer the inverse of the denominator: ( 1 / demon ) and replace the "v =" and "w =" lines with a multiplication between the inverse instead of divisions. This would reduce our number of divisions from 2 to 1, good savings! These kinds of tricks are really common in engine development.
Medians and Centroids
A triangle median is a line from one of it's vertices that meets the opposite side at a right angle. Since a triangle has three vertices, it also has three medians. A centroid is the point at which all medians meet. A centroid is a triangles center of mass.
Khan Academy has a nice playlist on this topic:
https://www.khanacademy.org/math/geometry-home/triangle-properties/medians-centroids/v/triangle-medians-and-centroids
Triangle Area
You are probably familiar with the classic Area = 1/2 * base * height formula. Sadly, the height of a triangle can be a bitch to compute so it's often easier to use an alternative formula called Heron's formula that uses half of the perimeter called the "semi-perimeter".
A triangle median is a line from one of it's vertices that meets the opposite side at a right angle. Since a triangle has three vertices, it also has three medians. A centroid is the point at which all medians meet. A centroid is a triangles center of mass.
Khan Academy has a nice playlist on this topic:
https://www.khanacademy.org/math/geometry-home/triangle-properties/medians-centroids/v/triangle-medians-and-centroids
Triangle Area
You are probably familiar with the classic Area = 1/2 * base * height formula. Sadly, the height of a triangle can be a bitch to compute so it's often easier to use an alternative formula called Heron's formula that uses half of the perimeter called the "semi-perimeter".
|
|
Practice Question: Determine if point P is lies within the triangle defined by points ABC.
Answer: One method is to derive the barycentric coordinates of P for ABC. If one of those coords is negative, then the point is outside of the triangle.
This is a very common problem, maybe the most common in all of computer graphics so it has been well studied. Here are several alternative approaches you should be aware of:
http://totologic.blogspot.com/2014/01/accurate-point-in-triangle-test.html
https://blackpawn.com/texts/pointinpoly/default.html
I believe the fastest approach uses the 2D cross product which I outlined in the previous chapter "Maths - Vectors". And that approach actually works for all polygons which is convenient!
Answer: One method is to derive the barycentric coordinates of P for ABC. If one of those coords is negative, then the point is outside of the triangle.
This is a very common problem, maybe the most common in all of computer graphics so it has been well studied. Here are several alternative approaches you should be aware of:
http://totologic.blogspot.com/2014/01/accurate-point-in-triangle-test.html
https://blackpawn.com/texts/pointinpoly/default.html
I believe the fastest approach uses the 2D cross product which I outlined in the previous chapter "Maths - Vectors". And that approach actually works for all polygons which is convenient!
An unsigned int-32 would have all 32 bits to represent its value, but we need to remember to subtract one because one combination of bits is used to represent 0. Therefore the max value of a uint-32 is 2^32-1.
But I asked for a signed int-32 which requires the first bit to represent the sign. Therefore the max value of a uint-32 is 2^31-1.
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Practice Question: Given a ray and a triangle, derive their intersection.
Answer: First recognize that this is a constrained version of the generic problem to determine if a line intersects a plane. A ray is just a constrained line, and a triangle is just a constrained plane. Solve that easier subproblem first and if there is an intersection then take that point. We know the point is on the plane which contains the triangle, we just aren't yet sure if it is in the triangle. So all that remains is to check if the point is in the triangle which is another subproblem we have already discussed.
Answer: First recognize that this is a constrained version of the generic problem to determine if a line intersects a plane. A ray is just a constrained line, and a triangle is just a constrained plane. Solve that easier subproblem first and if there is an intersection then take that point. We know the point is on the plane which contains the triangle, we just aren't yet sure if it is in the triangle. So all that remains is to check if the point is in the triangle which is another subproblem we have already discussed.
An unsigned int-32 would have all 32 bits to represent its value, but we need to remember to subtract one because one combination of bits is used to represent 0. Therefore the max value of a uint-32 is 2^32-1.
But I asked for a signed int-32 which requires the first bit to represent the sign. Therefore the max value of a uint-32 is 2^31-1.
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32