AABB

Czyli Axis-Aligned Bound Box. Czyli prostopadłościan umieszczony w przestrzeni 3D o bokach równoległych do osi układu współrzędnych. Zanim przystąpimy do znajdowania intersekcji dla dowolnie skomplikowanego obiektu, bardziej opłacalne czasowo może być dla nas sprawdzanie intersekcji właśnie z jakąś bryłą w której ten obiekt zawiera się, w tym wypadku AABB. AABB są dosyć często używane gdyż badanie intersekcji z nimi jest dosyć szybkie. Są też naturalnym sojusznikiem dla podziału przestrzeni KD-Tree (zgodnie z płaszczyznami układu współrzędnych). Z uwagi na to, że AABB z reguły niezbyt ciasno opinają obiekt możliwa jest duża liczba fałszywych sprawdzeń. Wyliczanie AABB jest wolne, dla każdej transformacji obiektu trzeba je liczyć na nowo. W przeciwieństwie do np. OBB gdzie wystarczy OBB transformować wraz z obiektem. OOB zreguły opina nasz obiekt bardziej niż AABB. Zamiast mówić opina możemy wprowadzić miarę stosunku objętości bryły wpisanej w AABB do objętości AABB.

Do ich reprezentacji wykorzystujemy dwa punkty w przestrzeni: Minimum i Maksimum, gdzie Min <= Max dla każdej ze współrzędnych X, Y, Z.

Intersekcje z promieniem sprawdzamy osobno dla współrzędnych X, Y, Z. Zacznijmy od X. Sprawdzamy dla jakich t promień dany w postaci kierunkowej przecina płaszczyzny wyznaczone przez Min.X i Max.X.

$\begin{align*}
& x = START.X + DIR.X \cdot t \\
\\
& Min.X = START.X + DIR.X \cdot t \\
\\
& t_{MIN} = \frac{Min.X - START.X}{DIR.X} \\
\\
& t_{MAX} = \frac{Max.X - START.X}{DIR.X} \\
\end{align*}$

Teraz wyznaczamy dwie wartości które będą nam towarzyszyć poprzez cały test:

$\begin{align*}
& Far = Max(t_{MIN}, t_{MAX}) \\
& Near = Min(t_{MIN}, t_{MAX}) \\
\end{align*}$

Jeśli $Far<0$ to przecięcie nastąpiło przed punktem startu promienia. Tym samym intersekcji brak. Zauważmy, że Near może być ujemne.

Jeśli współrzędna kierunkowa $DIR.X=0$ to wtedy intersekcja jest możliwa jeśli $Min.X \le START.X \le Max.X$.

Przechodzimy do następnej płaszczyzny Y. Jeśli $DIR.Y=0$ to sprawdzamy czy START.Y leży w zakresie $Min.Y \le START.Y \le Max.Y$. Przeciwnie wyznaczamy podobnie jak poprzednio $t_{MIN}$ i $t_{MAX}$. Wyznaczamy:

$Far_1 = Max(t_{MIN}, t_{MAX})$
$Near_1 = Min(t_{MIN}, t_{MAX})$

I teraz wyliczamy nowa Near i Far:

$Far = Min(Far, Far_1)$
$Near = Max(Near, Near_1)$

Pamiętajmy, że Far i Near to tak naprawdę parametr t promienia. Wyznaczamy więc dwukrotnie wartości parametru t dla którego prosta przecina dane płaszczyzny. Mamy dwie wartości Near i Far z testu dla X i teraz mamy dwie nowe wartości z testy dla Y. Jeśli prosta przetnie AABB to dokona tego dla konkretnych dwóch wartości t. Podstawiając je do wzorów na Near i Far dla konkretnych płaszczyzn powinniśmy otrzymać współrzędne Min i Max. W zakresie t pomiędzy punktem wejścia w AABB, a wyjścia współrzędne punktów prostej leżą pomiędzy Min i Max. Powyższe wyliczenia znajdują nowy wspólny zbiór parametrów t dla których prosta znajduje się jednocześnie pomiędzy Min.X i Max.X oraz pomiędzy Min.Y, a Max.X.

Jeśli $Far<0$ to intersekcji brak. Zbiór t dla której są one pomiędzy Min.Y, a Max.Y leży przed punktem startu promienia.

Powyższy rysunek obrazuje różne kombinacje możliwych intersekcji:

Dla promienia 2 współrzędna kierunkowa DIR.Y. Ponieważ nie zachodzi $Min.Y \le START.Y \le Max.Y$ prosta ta nigdy nie przetnie AABB. W przeciwieństwie do promienia 5. Dla promienia 1 zbiory $<Near.X, Far.X>$ oraz $<Near.Y, Far.Y>$ są rozłączne. Promień ten nigdy nie przetnie AABB. W przeciwieństwie do promienia 4, gdzie zbiory te mają część wspólną. Promień 3 jest przykładem promienia dla którego $Near<0$ utrzymuje się przez cały czas obliczeń. I tak ujemna wartość zostanie zwrócona jako odległość do miejsca intersekcji. Wartość oznaczająca brak intersekcji to Double.PositiveInfinity. Wartość ujemna oznacza, że punkt startu promienia znajduje się w AABB. Taki wynik oznacza, że powinniśmy także przetestować na intersekcje wszystkie obiekty w tym AABB.

Jeśli $Far<Near$ to intersekcji brak. Zbiory t są rozłączne, innymi słowy prosta nigdy jednocześnie nie znajduje się pomiędzy Min.X i Max.X oraz Min.Y i Max.Y i tym samym nie może przeciąć AABB.

Podobnie jak dla Y czynimy dla Z.

Ostatecznie otrzymuje segment promienia który przecina AABB, z reguły interesuje nas tylko współrzędna wejścia do AABB.

Kod wyznaczania dystansu do punktu pierwszego punktu intersekcji:

public double GetDist(Ray a_ray)
{
    Debug.Assert(Minimum <= Maximum);

    double n = Double.MinValue;
    double f = Double.MaxValue;

    if (a_ray.Dir.X.AlmostRelativeEquals(0))
    {
        if ((a_ray.Start.X <= Minimum.X) || (a_ray.Start.X >= Maximum.X))
            return Double.PositiveInfinity;
    }
    else
    {
        double d1 = (Minimum.X - a_ray.Start.X) / a_ray.Dir.X;
        double d2 = (Maximum.X - a_ray.Start.X) / a_ray.Dir.X;

        f = Math.Max(d1, d2);

        if (f < 0)
            return double.PositiveInfinity;

        n = Math.Min(d1, d2);
    }

    if (a_ray.Dir.Y.AlmostRelativeEquals(0))
    {
        if ((a_ray.Start.Y <= Minimum.Y) || (a_ray.Start.Y >= Maximum.Y))
            return Double.PositiveInfinity;
    }
    else
    {
        double d1 = (Minimum.Y - a_ray.Start.Y) / a_ray.Dir.Y;
        double d2 = (Maximum.Y - a_ray.Start.Y) / a_ray.Dir.Y;

        f = Math.Min(f, Math.Max(d1, d2));

        if (f < 0)
            return double.PositiveInfinity;

        n = Math.Max(n, Math.Min(d1, d2));

        if (n > f)
            return Double.PositiveInfinity;
    }

    if (a_ray.Dir.Z.AlmostRelativeEquals(0))
    {
        if ((a_ray.Start.Z <= Minimum.Z) || (a_ray.Start.Z >= Maximum.Z))
            return Double.PositiveInfinity;
    }
    else
    {
        double d1 = (Minimum.Z - a_ray.Start.Z) / a_ray.Dir.Z;
        double d2 = (Maximum.Z - a_ray.Start.Z) / a_ray.Dir.Z;

        f = Math.Min(f, Math.Max(d1, d2));

        if (f < 0)
            return double.PositiveInfinity;

        n = Math.Max(n, Math.Min(d1, d2));

        if (n > f)
            return Double.PositiveInfinity;
    }

    return n;
}