Advanced vector math

    Unit vectors that are perpendicular to a surface (so, they describe the orientation of the surface) are called unit normal vectors. Though, usually they are just abbreviated as normals. Normals appear in planes, 3D geometry (to determine where each face or vertex is siding), etc. A normal is a unit vector, but it’s called normal because of its usage. (Just like we call (0,0) the Origin!).

    It’s as simple as it looks. The plane passes by the origin and the surface of it is perpendicular to the unit vector (or normal). The side towards the vector points to is the positive half-space, while the other side is the negative half-space. In 3D this is exactly the same, except that the plane is an infinite surface (imagine an infinite, flat sheet of paper that you can orient and is pinned to the origin) instead of a line.

    Now that it’s clear what a plane is, let’s go back to the dot product. The dot product between a unit vector and any point in space (yes, this time we do dot product between vector and position), returns the distance from the point to the plane:

    GDScript

    C#

    But not just the absolute distance, if the point is in the negative half space the distance will be negative, too:

    ../../_images/tutovec11.png

    This allows us to tell which side of the plane a point is.

    I know what you are thinking! So far this is nice, but real planes are everywhere in space, not only passing through the origin. You want real plane action and you want it now.

    Remember that planes not only split space in two, but they also have polarity. This means that it is possible to have perfectly overlapping planes, but their negative and positive half-spaces are swapped.

    With this in mind, let’s describe a full plane as a normal N and a distance from the origin scalar D. Thus, our plane is represented by N and D. For example:

    For 3D math, Godot provides a built-in type that handles this.

    Basically, N and D can represent any plane in space, be it for 2D or 3D (depending on the amount of dimensions of N) and the math is the same for both. It’s the same as before, but D is the distance from the origin to the plane, travelling in N direction. As an example, imagine you want to reach a point in the plane, you will just do:

    GDScript

    C#

    1. var point_in_plane = N*D
    1. var pointInPlane = N * D;

    This will stretch (resize) the normal vector and make it touch the plane. This math might seem confusing, but it’s actually much simpler than it seems. If we want to tell, again, the distance from the point to the plane, we do the same but adjusting for distance:

    GDScript

    C#

    1. var distance = N.dot(point) - D
    1. var distance = N.Dot(point) - D;

    The same thing, using a built-in function:

    GDScript

    1. var distance = plane.distance_to(point)
    1. var distance = plane.DistanceTo(point);

    This will, again, return either a positive or negative distance.

    Flipping the polarity of the plane can be done by negating both N and D. This will result in a plane in the same position, but with inverted negative and positive half spaces:

    GDScript

    C#

    1. N = -N;
    2. D = -D;

    Of course, Godot also implements this operator in Plane, so doing:

    GDScript

    C#

    1. var inverted_plane = -plane
    1. var invertedPlane = -plane;

    Will work as expected.

    So, remember, a plane is just that and its main practical use is calculating the distance to it. So, why is it useful to calculate the distance from a point to a plane? It’s extremely useful! Let’s see some simple examples..

    Planes clearly don’t come out of nowhere, so they must be built. Constructing them in 2D is easy, this can be done from either a normal (unit vector) and a point, or from two points in space.

    In the case of a normal and a point, most of the work is done, as the normal is already computed, so just calculate D from the dot product of the normal and the point.

    GDScript

    C#

    1. var N = normal
    2. var D = normal.dot(point)
    1. var N = normal;
    2. var D = normal.Dot(point);

    For two points in space, there are actually two planes that pass through them, sharing the same space but with normal pointing to the opposite directions. To compute the normal from the two points, the direction vector must be obtained first, and then it needs to be rotated 90° degrees to either side:

    GDScript

    C#

    1. # calculate vector from a to b
    2. var dvec = (point_b - point_a).normalized()
    3. # rotate 90 degrees
    4. var normal = Vector2(dvec.y, -dvec.x)
    5. # or alternatively
    6. # var normal = Vector2(-dvec.y, dvec.x)
    7. # depending the desired side of the normal
    1. // calculate vector from a to b
    2. var dvec = (pointB - pointA).Normalized();
    3. // rotate 90 degrees
    4. var normal = new Vector2(dvec.y, -dvec.x);
    5. // or alternatively
    6. // var normal = new Vector2(-dvec.y, dvec.x);
    7. // depending the desired side of the normal

    The rest is the same as the previous example, either point_a or point_b will work since they are in the same plane:

    GDScript

    C#

    1. var N = normal;
    2. var D = normal.Dot(pointA);
    3. // this works the same
    4. // var D = normal.Dot(pointB);

    Doing the same in 3D is a little more complex and will be explained further down.

    Here is a simple example of what planes are useful for. Imagine you have a polygon. For example, a rectangle, a trapezoid, a triangle, or just any polygon where no faces bend inwards.

    For every segment of the polygon, we compute the plane that passes by that segment. Once we have the list of planes, we can do neat things, for example checking if a point is inside the polygon.

    ../../_images/tutovec13.png

    Code should be something like this:

    GDScript

    C#

    1. var inside = true
    2. for p in planes:
    3.     # check if distance to plane is positive
    4.     if (p.distance_to(point) > 0):
    5.         inside = false
    6.         break # with one that fails, it's enough
    1. var inside = true;
    2. foreach (var p in planes)
    3. {
    4.     // check if distance to plane is positive
    5.     if (p.DistanceTo(point) > 0)
    6.     {
    7.         inside = false;
    8.         break; // with one that fails, it's enough
    9.     }
    10. }

    Pretty cool, huh? But this gets much better! With a little more effort, similar logic will let us know when two convex polygons are overlapping too. This is called the Separating Axis Theorem (or SAT) and most physics engines use this to detect collision.

    With a point, just checking if a plane returns a positive distance is enough to tell if the point is outside. With another polygon, we must find a plane where all the other polygon points return a positive distance to it. This check is performed with the planes of A against the points of B, and then with the planes of B against the points of A:

    Code should be something like this:

    GDScript

    C#

    1. var overlapping = true
    3. for p in planes_of_A:
    4.     var all_out = true
    5.     for v in points_of_B:
    6.         if (p.distance_to(v) < 0):
    7.             all_out = false
    8.             break
    10.     if (all_out):
    11.         # a separating plane was found
    12.         # do not continue testing
    13.         overlapping = false
    14.         break
    16. if (overlapping):
    17.     # only do this check if no separating plane
    18.     # was found in planes of A
    19.     for p in planes_of_B:
    20.         var all_out = true
    21.         for v in points_of_A:
    22.             if (p.distance_to(v) < 0):
    23.                 all_out = false
    24.                 break
    26.         if (all_out):
    27.             overlapping = false
    28.             break
    30. if (overlapping):
    31.     print("Polygons Collided!")
    1. var overlapping = true;
    3. foreach (Plane plane in planesOfA)
    4. {
    5.     var allOut = true;
    6.     foreach (Vector3 point in pointsOfB)
    7.     {
    8.         if (plane.DistanceTo(point) < 0)
    9.         {
    10.             allOut = false;
    11.             break;
    12.         }
    13.     }
    15.     if (allOut)
    16.     {
    17.         // do not continue testing
    18.         overlapping = false;
    19.         break;
    21. }
    23. if (overlapping)
    24. {
    25.     // only do this check if no separating plane
    26.     // was found in planes of A
    27.     foreach (Plane plane in planesOfB)
    28.     {
    29.         var allOut = true;
    30.         foreach (Vector3 point in pointsOfA)
    31.         {
    32.             if (plane.DistanceTo(point) < 0)
    33.             {
    34.                 allOut = false;
    35.                 break;
    36.             }
    37.         }
    39.         if (allOut)
    40.         {
    41.             overlapping = false;
    42.             break;
    43.         }
    44.     }
    45. }
    47. if (overlapping)
    48. {
    49.     GD.Print("Polygons Collided!");
    50. }

    As you can see, planes are quite useful, and this is the tip of the iceberg. You might be wondering what happens with non convex polygons. This is usually just handled by splitting the concave polygon into smaller convex polygons, or using a technique such as BSP (which is not used much nowadays).

    Collision detection in 3D

    This is another bonus bit, a reward for being patient and keeping up with this long tutorial. Here is another piece of wisdom. This might not be something with a direct use case (Godot already does collision detection pretty well) but it’s used by almost all physics engines and collision detection libraries :)

    Remember that converting a convex shape in 2D to an array of 2D planes was useful for collision detection? You could detect if a point was inside any convex shape, or if two 2D convex shapes were overlapping.

    Well, this works in 3D too, if two 3D polyhedral shapes are colliding, you won’t be able to find a separating plane. If a separating plane is found, then the shapes are definitely not colliding.

    To refresh a bit a separating plane means that all vertices of polygon A are in one side of the plane, and all vertices of polygon B are in the other side. This plane is always one of the face-planes of either polygon A or polygon B.

    In 3D though, there is a problem to this approach, because it is possible that, in some cases a separating plane can’t be found. This is an example of such situation:

    ../../_images/tutovec22.png

    To avoid it, some extra planes need to be tested as separators, these planes are the cross product between the edges of polygon A and the edges of polygon B

    So the final algorithm is something like:

    GDScript

    C#

    1. var overlapping = true
    3. for p in planes_of_A:
    4.     var all_out = true
    5.     for v in points_of_B:
    6.         if (p.distance_to(v) < 0):
    7.             all_out = false
    8.             break
    10.     if (all_out):
    11.         # a separating plane was found
    12.         # do not continue testing
    13.         overlapping = false
    14.         break
    16. if (overlapping):
    17.     # only do this check if no separating plane
    18.     # was found in planes of A
    19.     for p in planes_of_B:
    20.         var all_out = true
    21.         for v in points_of_A:
    22.             if (p.distance_to(v) < 0):
    23.                 all_out = false
    24.                 break
    26.         if (all_out):
    27.             overlapping = false
    28.             break
    30. if (overlapping):
    31.     for ea in edges_of_A:
    32.         for eb in edges_of_B:
    33.             var n = ea.cross(eb)
    34.             if (n.length() == 0):
    35.                 continue
    37.             var max_A = -1e20 # tiny number
    38.             var min_A = 1e20 # huge number
    40.             # we are using the dot product directly
    41.             # so we can map a maximum and minimum range
    42.             # for each polygon, then check if they
    43.             # overlap.
    45.             for v in points_of_A:
    46.                 var d = n.dot(v)
    47.                 max_A = max(max_A, d)
    48.                 min_A = min(min_A, d)
    50.             var max_B = -1e20 # tiny number
    51.             var min_B = 1e20 # huge number
    53.             for v in points_of_B:
    54.                 var d = n.dot(v)
    55.                 max_B = max(max_B, d)
    56.                 min_B = min(min_B, d)
    58.             if (min_A > max_B or min_B > max_A):
    59.                 # not overlapping!
    60.                 overlapping = false
    61.                 break
    63.         if (not overlapping):
    64.             break
    66. if (overlapping):
    67.    print("Polygons collided!")
    1. var overlapping = true;
    3. {
    4.     var allOut = true;
    5.     foreach (Vector3 point in pointsOfB)
    6.     {
    7.         if (plane.DistanceTo(point) < 0)
    8.         {
    9.             allOut = false;
    10.             break;
    11.         }
    12.     }
    14.     if (allOut)
    15.     {
    16.         // a separating plane was found
    17.         // do not continue testing
    18.         overlapping = false;
    19.         break;
    20.     }
    21. }
    23. if (overlapping)
    24. {
    25.     // only do this check if no separating plane
    26.     // was found in planes of A
    27.     foreach (Plane plane in planesOfB)
    28.     {
    29.         var allOut = true;
    30.         foreach (Vector3 point in pointsOfA)
    31.         {
    32.             if (plane.DistanceTo(point) < 0)
    33.             {
    34.                 allOut = false;
    35.                 break;
    36.             }
    37.         }
    39.         if (allOut)
    40.         {
    41.             overlapping = false;
    42.             break;
    43.         }
    44.     }
    45. }
    47. if (overlapping)
    48. {
    49.     foreach (Vector3 edgeA in edgesOfA)
    50.     {
    51.         foreach (Vector3 edgeB in edgesOfB)
    52.         {
    53.             var normal = edgeA.Cross(edgeB);
    54.             if (normal.Length() == 0)
    55.             {
    56.                 continue;
    57.             }
    59.             var maxA = float.MinValue; // tiny number
    60.             var minA = float.MaxValue; // huge number
    62.             // we are using the dot product directly
    63.             // so we can map a maximum and minimum range
    64.             // for each polygon, then check if they
    65.             // overlap.
    67.             foreach (Vector3 point in pointsOfA)
    68.             {
    69.                 var distance = normal.Dot(point);
    70.                 maxA = Mathf.Max(maxA, distance);
    71.                 minA = Mathf.Min(minA, distance);
    72.             }
    74.             var maxB = float.MinValue; // tiny number
    75.             var minB = float.MaxValue; // huge number
    77.             foreach (Vector3 point in pointsOfB)
    78.             {
    79.                 var distance = normal.Dot(point);
    80.                 maxB = Mathf.Max(maxB, distance);
    81.                 minB = Mathf.Min(minB, distance);
    82.             }
    84.             if (minA > maxB || minB > maxA)
    85.             {
    86.                 // not overlapping!
    87.                 overlapping = false;
    88.                 break;
    89.             }
    90.         }
    92.         if (!overlapping)
    93.         {
    94.             break;
    95.         }
    97.     }
    98. }
    100. if (overlapping)
    101. {
    103. }