Attention: Here be dragons

This is the latest (unstable) version of this documentation, which may document features not available in or compatible with released stable versions of Godot.

Checking the stable version of the documentation...

Matematica vettoriale avanzata

Piani

Il prodotto scalare ha un'altra proprietà interessante con i vettori unitari. Immagina che la perpendicolare a quel vettore (e passante per l'origine) passi un piano. I piani dividono l'intero spazio in positivo (sopra il piano) e negativo (sotto il piano), e (contrariamente a quanto si pensa) puoi utilizzare la loro matematica anche in 2D:

I vettori unitari perpendicolari a una superficie (che quindi ne descrivono l'orientamento) sono chiamati vettori normali unitari (o versori). Tuttavia, di solito sono semplicemente abbreviati in normali. Le normali compaiono nei piani, nella geometria 3D (per determinare dove è rivolta ogni faccia o vertice), ecc. Una normale è un vettore unitario, ma si chiama normale per via del suo utilizzo. (Proprio come chiamiamo (0,0) l'Origine!).

Il piano passa per l'origine e la sua superficie è perpendicolare al vettore unitario (o normale). Il lato verso cui punta il vettore è il semispazio positivo, mentre l'altro lato è il semispazio negativo. In 3D è esattamente la stessa cosa, tranne per il fatto che il piano è una superficie infinita (immagina un foglio di carta piatto, infinito, fissato all'origine e che puoi orientare) invece di una linea.

Distanza dal piano

Ora che è chiaro cos'è un piano, torniamo al prodotto scalare. Il prodotto scalare tra un vettore unitario e un qualsiasi punto nello spazio (sì, questa volta facciamo il prodotto scalare tra vettore e posizione), restituisce la distanza dal punto al piano:

var distance = normal.dot(point)

var distance = normal.Dot(point);

Ma non solo la distanza assoluta, se il punto si trova nel semispazio negativo anche la distanza sarà negativa:

Questo ci permette di stabilire da quale lato del piano si trova un punto.

Lontano dall'origine

So cosa stai pensando! Fin qui tutto bene, ma i piani reali sono ovunque nello spazio, non passano solo per l'origine. Vuoi vera azione sui piani e la vuoi adesso.

Ricorda che i piani non solo dividono lo spazio in due, ma hanno anche una polarità. Ciò significa che è possibile avere piani perfettamente sovrapposti, ma i loro semispazi negativo e positivo sono invertiti.

Con questo in mente, descriviamo un piano completo come una normale N e uno scalare distanza dall'origine D. Quindi, il nostro piano è rappresentato da N e D. Per esempio:

Per la matematica 3D, Godot fornisce un tipo integrato Plane che gestisce questo.

In sostanza, N e D possono rappresentare qualsiasi piano nello spazio, sia in 2D sia in 3D (a seconda del numero di dimensioni di N) e la matematica è la stessa per entrambi. È la stessa di prima, ma D è la distanza dall'origine al piano, che si muove nella direzione N. Ad esempio, immagina di voler raggiungere un punto nel piano:

var point_in_plane = N*D

var pointInPlane = N * D;

Questo allungherà (ridimensionerà) il vettore normale e lo farà toccare il piano. Questo calcolo potrebbe sembrare complicato, ma in realtà è molto più semplice di quanto sembri. Se vogliamo calcolare, ancora una volta, la distanza dal punto al piano, facciamo lo stessa cosa, ma compensando per la distanza:

var distance = N.dot(point) - D

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

La stessa cosa, utilizzando una funzione integrata:

var distance = plane.distance_to(point)

var distance = plane.DistanceTo(point);

Anche in questo caso, la distanza restituita sarà positiva o negativa.

L'inversione della polarità del piano può essere ottenuta negando sia N sia D. Questo si tradurrà in un piano nella stessa posizione, ma con i semispazi negativo e positivo invertiti:

N = -N
D = -D

N = -N;
D = -D;

Godot implementa questo operatore anche in Plane. Quindi, utilizzando il formato seguente funzionerà come previsto:

var inverted_plane = -plane

var invertedPlane = -plane;

Perciò, ricorda, il principale uso pratico del piano è calcolarne la distanza. Allora, quando è utile calcolare la distanza da un punto a un piano? Vediamo alcuni esempi.

Costruire un piano in 2D

I piani chiaramente non nascono dal nulla, quindi si devono costruire. Costruirli in 2D è facile: si può fare partendo da una normale (vettore unitario) e un punto, oppure da due punti nello spazio.

Nel caso di una normale e un punto, la maggior parte del lavoro è già stata fatta, poiché la normale è già calcolata, quindi calcola D dal prodotto scalare della normale e del punto.

var N = normal
var D = normal.dot(point)

var N = normal;
var D = normal.Dot(point);

Per due punti nello spazio, ci sono in realtà due piani che li attraversano, condividendo lo stesso spazio ma con la normale rivolta in direzioni opposte. Per calcolare la normale ai due punti, bisogna prima ricavare il vettore direzione, e poi ruotarlo di 90 gradi da un lato o dall'altro:

# Calculate vector from `a` to `b`.
var dvec = point_a.direction_to(point_b)
# Rotate 90 degrees.
var normal = Vector2(dvec.y, -dvec.x)
# Alternatively (depending the desired side of the normal):
# var normal = Vector2(-dvec.y, dvec.x)

// Calculate vector from `a` to `b`.
var dvec = pointA.DirectionTo(pointB);
// Rotate 90 degrees.
var normal = new Vector2(dvec.Y, -dvec.X);
// Alternatively (depending the desired side of the normal):
// var normal = new Vector2(-dvec.Y, dvec.X);

Il resto è identico all'esempio precedente. Sia point_a sia point_b funzioneranno, poiché si trovano sullo stesso piano:

var N = normal
var D = normal.dot(point_a)
# this works the same
# var D = normal.dot(point_b)

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

Fare lo stesso in 3D è un po' più complesso ed è spiegato più avanti.

Qualche esempio di piano

Ecco un esempio su cosa servono i piani. Immagina di avere un poligono convesso. Ad esempio, un rettangolo, un trapezio, un triangolo o qualsiasi altro poligono in cui nessuna faccia si pieghi verso l'interno.

Per ogni segmento del poligono, calcoliamo il piano che passa per quel segmento. Una volta ottenuta la lista dei piani, possiamo fare cose interessanti, ad esempio verificare se un punto è interno al poligono.

Passiamo attraverso tutti i piani: se riusciamo a trovare un piano la cui distanza dal punto sia positiva, allora il punto è esterno al poligono. Se non ci riusciamo, allora il punto è interno.

Il codice dovrebbe assomigliare a questo:

var inside = true
for p in planes:
    # check if distance to plane is positive
    if (p.distance_to(point) > 0):
        inside = false
        break # with one that fails, it's enough

var inside = true;
foreach (var p in planes)
{
    // check if distance to plane is positive
    if (p.DistanceTo(point) > 0)
    {
        inside = false;
        break; // with one that fails, it's enough
    }
}

Davvero geniale, eh? Ma c'è di meglio! Con un po' più di impegno, una logica simile ci permette di sapere anche quando due poligoni convessi si sovrappongono. Questo è chiamato il teorema dell'asse di separazione (o SAT) e gran parte dei motori di fisica lo utilizza per rilevare le collisioni.

Con un punto, è sufficiente verificare se un piano restituisce una distanza positiva per stabilire se il punto è esterno. Con un altro poligono, dobbiamo trovare un piano in cui tutti gli altri punti del poligono restituiscano una distanza positiva. Questa verifica è effettuata con i piani di A contro i punti di B, e poi con i piani di B contro i punti di A:

Il codice dovrebbe assomigliare a questo:

var overlapping = true

for p in planes_of_A:
    var all_out = true
    for v in points_of_B:
        if (p.distance_to(v) < 0):
            all_out = false
            break

    if (all_out):
        # a separating plane was found
        # do not continue testing
        overlapping = false
        break

if (overlapping):
    # only do this check if no separating plane
    # was found in planes of A
    for p in planes_of_B:
        var all_out = true
        for v in points_of_A:
            if (p.distance_to(v) < 0):
                all_out = false
                break

        if (all_out):
            overlapping = false
            break

if (overlapping):
    print("Polygons Collided!")

var overlapping = true;

foreach (Plane plane in planesOfA)
{
    var allOut = true;
    foreach (Vector3 point in pointsOfB)
    {
        if (plane.DistanceTo(point) < 0)
        {
            allOut = false;
            break;
        }
    }

    if (allOut)
    {
        // a separating plane was found
        // do not continue testing
        overlapping = false;
        break;
    }
}

if (overlapping)
{
    // only do this check if no separating plane
    // was found in planes of A
    foreach (Plane plane in planesOfB)
    {
        var allOut = true;
        foreach (Vector3 point in pointsOfA)
        {
            if (plane.DistanceTo(point) < 0)
            {
                allOut = false;
                break;
            }
        }

        if (allOut)
        {
            overlapping = false;
            break;
        }
    }
}

if (overlapping)
{
    GD.Print("Polygons Collided!");
}

Come puoi vedere, i piani sono piuttosto utili, e questa è solo la punta dell'iceberg. Potreste chiedervi cosa succede con un poligono non convesso. Di solito è gestito dividendo il poligono concavo in poligoni convessi più piccoli, o utilizzando una tecnica come BSP (la quale non è molto comune al giorno d'oggi).

Rilevamento di collisioni in 3D

Questo è un altro bonus, una ricompensa per la pazienza e per aver seguito questo lungo tutorial. Ecco un altra perla di saggezza. Potrebbe non essere utile direttamente (Godot già rileva le collisioni piuttosto bene), ma è utilizzato da quasi tutti i motori di fisica e le librerie di rilevamento delle collisioni :)

Ricordi che la conversione di una forma convessa in 2D in una matrice di piani 2D era utile per rilevare il rilevamento delle collisioni? Potevi rilevare se un punto si trovava all'interno di una qualsiasi forma convessa, o se due forme convesse 2D si sovrapponevano.

Beh, ciò funziona anche in 3D: se due forme poliedriche 3D entrano in collisione, non riuscirai a trovare un piano di separazione. Se ci riesci, allora le forme non sono entrate in collisione, decisamente.

Per rinfrescare un po' la memoria, un piano di separazione significa che tutti i vertici del poligono A si trovano su un lato del piano, e tutti i vertici del poligono B si trovano sull'altro lato. Questo piano è sempre uno dei piani delle facce del poligono A o del poligono B.

In 3D, tuttavia, c'è un problema con questo approccio, perché è possibile che, in alcuni casi, non sia possibile trovare un piano di separazione. Ecco un esempio di tale situazione:

Per evitarlo, alcuni piani aggiuntivi si devono testare come separatori. Questi piani sono il prodotto vettoriale tra i bordi del poligono A e i bordi del poligono B

Quindi l'algoritmo finale è qualcosa del genere:

var overlapping = true

for p in planes_of_A:
    var all_out = true
    for v in points_of_B:
        if (p.distance_to(v) < 0):
            all_out = false
            break

    if (all_out):
        # a separating plane was found
        # do not continue testing
        overlapping = false
        break

if (overlapping):
    # only do this check if no separating plane
    # was found in planes of A
    for p in planes_of_B:
        var all_out = true
        for v in points_of_A:
            if (p.distance_to(v) < 0):
                all_out = false
                break

        if (all_out):
            overlapping = false
            break

if (overlapping):
    for ea in edges_of_A:
        for eb in edges_of_B:
            var n = ea.cross(eb)
            if (n.length() == 0):
                continue

            var max_A = -1e20 # tiny number
            var min_A = 1e20 # huge number

            # we are using the dot product directly
            # so we can map a maximum and minimum range
            # for each polygon, then check if they
            # overlap.

            for v in points_of_A:
                var d = n.dot(v)
                max_A = max(max_A, d)
                min_A = min(min_A, d)

            var max_B = -1e20 # tiny number
            var min_B = 1e20 # huge number

            for v in points_of_B:
                var d = n.dot(v)
                max_B = max(max_B, d)
                min_B = min(min_B, d)

            if (min_A > max_B or min_B > max_A):
                # not overlapping!
                overlapping = false
                break

        if (not overlapping):
            break

if (overlapping):
   print("Polygons collided!")

var overlapping = true;

foreach (Plane plane in planesOfA)
{
    var allOut = true;
    foreach (Vector3 point in pointsOfB)
    {
        if (plane.DistanceTo(point) < 0)
        {
            allOut = false;
            break;
        }
    }

    if (allOut)
    {
        // a separating plane was found
        // do not continue testing
        overlapping = false;
        break;
    }
}

if (overlapping)
{
    // only do this check if no separating plane
    // was found in planes of A
    foreach (Plane plane in planesOfB)
    {
        var allOut = true;
        foreach (Vector3 point in pointsOfA)
        {
            if (plane.DistanceTo(point) < 0)
            {
                allOut = false;
                break;
            }
        }

        if (allOut)
        {
            overlapping = false;
            break;
        }
    }
}

if (overlapping)
{
    foreach (Vector3 edgeA in edgesOfA)
    {
        foreach (Vector3 edgeB in edgesOfB)
        {
            var normal = edgeA.Cross(edgeB);
            if (normal.Length() == 0)
            {
                continue;
            }

            var maxA = float.MinValue; // tiny number
            var minA = float.MaxValue; // huge number

            // we are using the dot product directly
            // so we can map a maximum and minimum range
            // for each polygon, then check if they
            // overlap.

            foreach (Vector3 point in pointsOfA)
            {
                var distance = normal.Dot(point);
                maxA = Mathf.Max(maxA, distance);
                minA = Mathf.Min(minA, distance);
            }

            var maxB = float.MinValue; // tiny number
            var minB = float.MaxValue; // huge number

            foreach (Vector3 point in pointsOfB)
            {
                var distance = normal.Dot(point);
                maxB = Mathf.Max(maxB, distance);
                minB = Mathf.Min(minB, distance);
            }

            if (minA > maxB || minB > maxA)
            {
                // not overlapping!
                overlapping = false;
                break;
            }
        }

        if (!overlapping)
        {
            break;
        }

    }
}

if (overlapping)
{
    GD.Print("Polygons Collided!");
}

Maggiori informazioni

Per maggiori informazioni sull'utilizzo della matematica vettoriale in Godot, consulta il seguente articolo:

Matrici e trasformazioni

Se desideri ulteriori spiegazioni, puoi dare un'occhiata all'eccellente serie video di 3Blue1Brown Essence of Linear Algebra.