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...

Matemática vetorial avançada

Planos

O produto escalar tem outra propriedade interessante com vetores unitários. Imagine que um plano passa perpendicularmente a esse vetor (e através da origem). Os planos dividem todo o espaço em positivo (acima do plano) e negativo (abaixo do plano) e, (ao contrário da crença popular) você também pode usar a matemática deles em 2D:

Vetores unitários que são perpendiculares a uma superfície (portanto, descrevem a orientação da superfície) são chamados de vetores normais unitários. No entanto, geralmente são abreviados apenas como normais. As normais aparecem em planos, geometria 3D (para determinar para onde cada face ou vértice está voltado), etc. Uma normal é um vetor unitário, mas é chamada de normal por causa de seu uso. (Assim como chamamos (0,0) de Origem!).

O plano passa pela origem e a superfície dele é perpendicular ao vetor unitário (ou normal). O lado para o qual o vetor aponta é o meio-espaço positivo, enquanto o outro lado é o meio-espaço negativo. Em 3D, isso é exatamente igual, exceto que o plano é uma superfície infinita (imagine uma folha de papel plana e infinita que você pode orientar e que está fixada na origem) em vez de uma linha.

Distância do plano

Agora que está claro o que é um plano, vamos voltar ao produto escalar. O produto escalar entre um vetor unitário e qualquer ponto no espaço (sim, desta vez fazemos o produto escalar entre vetor e posição) retorna a distância do ponto ao plano:

var distance = normal.dot(point)

var distance = normal.Dot(point);

Mas não apenas a distância absoluta, se o ponto estiver no meio-espaço negativo, a distância também será negativa:

Isso nos permite dizer de qual lado do plano um ponto está.

Longe da origem

Eu sei o que você está pensando! Até agora isso é legal, mas planos reais estão em toda parte no espaço, não apenas passando pela origem. Você quer ação de plano real e quer isso agora.

Lembre-se de que os planos não apenas dividem o espaço em dois, mas também têm polaridade. Isso significa que é possível ter planos perfeitamente sobrepostos, mas com seus meio-espaços negativos e positivos invertidos.

Com isso em mente, vamos descrever um plano completo como uma normal N e um escalar de distância da origem D. Assim, nosso plano é representado por N e D. Por exemplo:

Para matemática 3D, o Godot fornece um tipo embutido Plane que lida com isso.

Basicamente, N e D podem representar qualquer plano no espaço, seja para 2D ou 3D (dependendo da quantidade de dimensões de N) e a matemática é a mesma para ambos. É o mesmo de antes, mas D é a distância da origem ao plano, viajando na direção N. Como exemplo, imagine que você deseja alcançar um ponto no plano, você faria apenas:

var point_in_plane = N*D

var pointInPlane = N * D;

Isso esticará (redimensionará) o vetor normal e o fará tocar o plano. Essa matemática pode parecer confusa, mas na verdade é muito mais simples do que parece. Se quisermos dizer, novamente, a distância do ponto ao plano, fazemos o mesmo, mas ajustando para a distância:

var distance = N.dot(point) - D

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

A mesma coisa, usando uma função integrada:

var distance = plane.distance_to(point)

var distance = plane.DistanceTo(point);

Isso, novamente, retornará uma distância positiva ou negativa.

Inverter a polaridade do plano pode ser feito negando tanto N quanto D. Isso resultará em um plano na mesma posição, mas com os meio-espaços negativo e positivo invertidos:

N = -N
D = -D

N = -N;
D = -D;

O Godot também implementa esse operador em Plane. Portanto, usar o formato abaixo funcionará conforme o esperado:

var inverted_plane = -plane

var invertedPlane = -plane;

Então, lembre-se, o principal uso prático do plano é que podemos calcular a distância até ele. Então, quando é útil calcular a distância de um ponto a um plano? Vejamos alguns exemplos.

Construindo um plano em 2D

Os planos claramente não surgem do nada, então eles devem ser construídos. Construí-los em 2D é fácil, isso pode ser feito a partir de uma normal (vetor unitário) e um ponto, ou a partir de dois pontos no espaço.

No caso de uma normal e um ponto, a maior parte do trabalho está feita, pois a normal já está calculada, então calcule D a partir do produto escalar da normal e do ponto.

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

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

Para dois pontos no espaço, existem na verdade dois planos que passam por eles, compartilhando o mesmo espaço, mas com a normal apontando para direções opostas. Para calcular a normal a partir dos dois pontos, o vetor de direção deve ser obtido primeiro e, em seguida, precisa ser rotacionado 90 graus para qualquer um dos lados:

# 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);

O resto é igual ao exemplo anterior. Qualquer um dos pontos, point_a ou point_b, funcionará, pois estão no mesmo plano:

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);

Fazer o mesmo em 3D é um pouco mais complexo e é explicado mais abaixo.

Alguns exemplos de planos

Aqui está um exemplo de para que os planos são úteis. Imagine que você tem um polígono convexo. Por exemplo, un retângulo, um trapézio, um triângulo, ou simplesmente qualquer polígono onde nenhuma face se curve para dentro.

Para cada segmento do polígono, calculamos o plano que passa por esse segmento. Assim que tivermos a lista de planos, podemos fazer coisas legais, por exemplo, verificar se um ponto está dentro do polígono.

Passamos por todos os planos; se conseguirmos encontrar um plano onde a distância até o ponto seja positiva, então o ponto está fora do polígono. Se não conseguirmos, então o ponto está dentro.

O código deve ser algo assim:

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
    }
}

Muito legal, não é? Mas isso fica muito melhor! Com um pouco mais de esforço, uma lógica semelhante nos permitirá saber quando dois polígonos convexos estão se sobrepondo também. Isso é chamado de Teorema do Eixo Separador (ou SAT) e a maioria dos motores de física usa isso para detectar colisão.

Com um ponto, apenas verificar se um plano retorna uma distância positiva é suficiente para saber se o ponto está fora. Com outro polígono, devemos encontrar um plano onde todos os outros pontos do polígono retornem uma distância positiva em relação a ele. Esta verificação é realizada com os planos de A contra os pontos de B, e então com os planos de B contra os pontos de A:

O código deve ser algo assim:

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!");
}

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).

Detecção de colisão em 3D

Este é outro trecho de bônus, uma recompensa por ser paciente e acompanhar este longo tutorial. Aqui está outro pedaço de sabedoria. Isso pode não ser algo com um caso de uso direto (o Godot já faz a detecção de colisões muito bem), mas é usado por quase todos os motores de física e bibliotecas de detecção de colisão :)

Lembra que converter uma forma convexa em 2D para uma matriz de planos 2D era útil para a detecção de colisões? Você podia detectar se um ponto estava dentro de qualquer forma convexa, ou se duas formas convexas 2D estavam se sobrepondo.

Bem, isso funciona em 3D também; se duas formas poliédricas 3D estiverem colidindo, você não conseguirá encontrar um plano separador. Se um plano separador for encontrado, então as formas definitivamente não estão colidindo.

Para refrescar um pouco, um plano separador significa que todos os vértices do polígono A estão de um lado do plano, e todos os vértices do polígono B estão do outro lado. Esse plano é sempre um dos planos das faces do polígono A ou do polígono B.

Em 3D, porém, há um problema com essa abordagem, porque é possível que, em alguns casos, um plano separador não possa ser encontrado. Este é um exemplo de tal situação:

Para evitá-la, alguns planos extras precisam ser testados como separadores; esses planos são o produto vetorial entre as arestas do polígono A e as arestas do polígono B

Então, o algoritmo final é algo como:

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!");
}

Mais informações

Para mais informações sobre o uso de matemática vetorial no Godot, consulte o seguinte artigo:

Matrizes e transformações

Se você quiser uma explicação adicional, deve dar uma olhada na excelente série de vídeos do 3Blue1Brown, Essence of Linear Algebra.