სხივის თანაკვეთა AABB-სთან

Ray AABB Intersection

        სხივების მიდევნების მეთოდში AABB-სთან სხივის თანაკვეთის ამოცანა უდაოდ ერთერთი უმნიშვნელოვანესია და შესაბამისამ მისი ოპტიმალური გადაჭრა ძალიან მნიშვნელოვანი საკითხია. როგორც ვიცით AABB(Axis Aligned Bounding Box) წარმოადგენს პარალელეპიპედს, რომლის წახნაგებიც საკოორდინატო სიბრტყეების პარალელურია.

        პირველ ეტაპზე განვიხილოთ სწორედ სხივის საკოორდინატო სიბრტყის პარალელურ სიბრტყესთან თანაკვეთის ამოცანა.

        როგორც სურათზე ჩანს თანაკვეთის წერტილამდე მანძილი არის (y' - y)/sin(α). ნორმალიზებული (dx,dy,dz) ვექტორის შემთხვევაში sin(α) ტოლი იქნება dy-ის.

        მივუბრუნდეთ aabb-სთან თანაკვეთას ამოცანას. სიმარტივისათვის განვიხილავთ შემთხვევას 2 განზომილებაში სადაც aabb მოცემულია [min, max] დიაპაზონით თითოეული განზომილების მიმართ, რომლებიც ჩვენს შემთხვევაში გვაძლევს 4 წრფეს. შესაბამისად თითოეულ ამ წრფესთან თანაკვეთას ვიპოვით შემდეგნაირად:

t0x = (aabb.min.x - ray.origin.x) / ray.dir.x 

t1x = (aabb.max.x - ray.origin.x) / ray.dir.x

t0y = (aabb.min.y - ray.origin.y) / ray.dir.y 

t1y = (aabb.max.y - ray.origin.y) / ray.dir.y

        თუ დავაკვირდებით ქვემოთ მოცემულ ნახაზს, სადაც სხივი ხვდება aabb-ს, სხივი ჯერ კვეთს უახლოეს, y ღერძის პარალელურ წრფეს tx0 მანძილში, შემდეგ უახლოეს, x ღერძის პარალელურ წრფეს ty0 მანძილში, შემდეგ მეორე, y ღერძის პარალელურ წრფეს tx1 მანძილში და ბოლოს მეორე, x ღერძის პარალელურ წრფეს ty1 მანძილში. თუ სხივი რომელიმე ღერძის მიმართ ისე შედის და გადის aabb-ს განმსაზღვრელი დიაპაზონიდან, რომ მათ შორის სხვა რომელიმე ღერძის მიმართ დიაპაზონის კვეთა არ ფიქსირდება, სხივი ცდება aabb-ს. ჩვენ შემთხვევაში თანაკვეთები ლაგდებიან შემდეგნაირად: tx0, ty0, tx1, ty1 საიდანაც ჩანს, რომ tx0-სა და tx1-ს შორის ექცევა თანაკვეთა ty0, ასევე ty0-სა და ty1-ს შორის ექცევა tx1, რის საფუძველზეც შეგვიძლია დავასკვნათ რომ თანაკვეთა მოხდა. 

შემთხვევა, როდესაც სხივი ხვდება aabb-ს.

        ქვემოთ მოცემულია ნახაზი სადაც სხივი ცდება aabb-ს. ამ შემთხვევაში თანაკვეთები ლაგდებიან შემდეგნაირად: tx0, tx1, ty0, ty1, რაც გვეუბნება, რომ სხივმა ჯერ შევიდა x ღერძის მიმართ aabb-ს დიაპაზონში tx0 მანძილში და გავიდა დიაპაზონიდან tx1 მანძილში ისე რომ სხვა ღერძის მიმართ არ შესულა დიაპაზონში, საიდანაც ჩანს რომ თანაკვეთა არ მომხდარა.

შემთხვევა, როდესაც სხივი სცდება aabb-ს.

        მოვიყვანოთ პროგრამული კოდის მაგალითი:

bool ray_aabb_intersection( const Ray& r, const AABB& aabb )
{
        float tmin, tmax;
        //დავითვალოთ თანაკვეთა YoZ საკოორდინატო სიბრტყის პარალელურ წახნაგებთან
        float txmin = (aabb.min.x - r.orig.x) / r.dir.x;
        float txmax = (aabb.max.x - r.orig.x) / r.dir.x;
        txmin = min( txmin , txmax );
        txmax = max( txmin , txmax );
        //დავითვალოთ თანაკვეთა XoZ საკოორდინატო სიბრტყის პარალელურ წახნაგებთან
        float tymin = (aabb.min.y - r.orig.y) / r.dir.y;
        float tymax = (aabb.max.y - r.orig.y) / r.dir.y;
        tymin = min( tymin , tymax );
        tymax = max( tymin , tymax );
        if ((txmin > tymax) || (tymin > txmax))
                return false;
        tmin = max( tymin , txmin );
        tmax = min( tymax, txmax );
        //დავითვალოთ თანაკვეთა XoY საკოორდინატო სიბრტყის პარალელურ წახნაგებთან
        float tzmin = (aabb.min.z - r.orig.z) / r.dir.z;
        float tzmax = (aabb.max.z - r.orig.z) / r.dir.z;
        tzmin = min( tzmin , tzmax );
        tzmax = max( tzmin , tzmax );
        if ((tmin > tzmax) || (tzmin > tmax))
                return false;
        tmin = max( tzmin , tmin );
        tmax = min( tzmax, tmax );
        return true;
}

        როგორც კოდიდან ჩანს, txmin-ის და txmax-ის დათვლის შემდეგ ვირჩევთ მათგან მინიმალურს და მაქსიმალურს, ამ გამოთვლების თავიდან აცილებას შევძლებთ თუ შევამოწმებთ სხივის მიმართულებას:

if ( r.dir.x >= 0 ) {
        txmin = (aabb.min.x - r.orig.x) / ray.dir.x;
        txmax = (aabb.max.x - r.orig.x) / ray.dir.x;
} else {
        txmin = (aabb.max.x - r.orig.x) / ray.dir.x;
        txmax = (aabb.min.x - r.orig.x) / ray.dir.x;
}

        ასეთ შემთხვევაში უკვე ვიცით რომ txmin-ის მნიშვნელობა ნაკლები იქნება txmax-ზე. თუმცა არის ერთი გამონაკლისი შემთხვევა, როდესაც ეს ასე არ მოხდება. IEEE სტანდარტის მიხედვით float-ს აქვს ცალკე 1 ბიტი ნიშნის შესანახად რაც იწვევს 0-ის გაორებას. float რიცხვი შესაძლებელია იყოს როგორც -0 ასევე 0. თუმცა თუ შევადარებთ -0-სა და 0-ს მივიღებთ true-ს. ჩვენს შემთხვევაში პრობლემა იქმნება როდესაც ray.dir.x-ში მოხვდება -0. ამ შემთხვევაში დამოსახულება r.dir.x >= 0 იქნება true და შესრულდება პირველი ბლოკი, რაც საბოლოოდ იმით რასრულდება რომ txmin-ში მივიღებთ +∞-ს ხოლო txmax-ში -∞. ამის თავიდან ასაცილებლად ახდენენ სხივის მიმართულების შებრუნებულის გამოთვლას და შემდეგ გამოთვლებში ხდება მისი გამოყენება. კოდი გადაკეთდება შემდეგნაირად:

Vector3 invdir = 1 / ray.dir; 

if (invdir.x >= 0) { 

        txmin = (aabb.min.x - r.orig.x) * invdir.x; 

        txmax = (aabb.max.x - r.orig.x) * invdir.x; 

} else { 

        txmin = (aabb.max.x - r.orig.x) * invdir.x; 

        txmax = (aabb.min.x - r.orig.x) * invdir.x; 

}

        შესაბამისად როდესაც ray.dir იქნება -0, მაშინ invdir-ში მივიღებთ -∞-ს და გამოსახულება (invdir.x >= 0) იქნება მცდარი, ამიტომ შესრულდება მეორე ბლოკი და txmin-ში და txmax-ში მივიღებთ სასურრველ მნიშვნელობებს.

        იმ შემთხვევაში, როდესაც გვსურს ერთი სხივის თანაკვეთის დათვლა ბევრ aabb-სთან  მომგებიანია, რომ invdir შევინახოთ სხივში. ასევე იმისათვის, რომ ზედმეტი შედარებები(if-ები) თავიდან ავიცილოთ მნიშვნელი ოპტიმიზაცია იქნება თუ (invdir.x >= 0)გამოსახულებასაც გადავითვლით წინასწარ და AABB-შიც [min, max] მნიშვნელობებს მოვათავსებთ მასივში. ასეთ შემთხვევაში სახელის ნაცვლად, ინდექსით შევძლებთ მნიშვნელობებზე წვდომას. კოდი მიიღებს შემდეგ სახეს:

class AABB
{
        Vector3 bound[2];
};
class Ray
{
public:
    Ray(Vector3 orig, Vector3 dir) : orig(orig), dir(dir)
    {
        invdir = 1.0f / dir;
        sign[0] = (invdir.x < 0);
        sign[1] = (invdir.y < 0);
        sign[2] = (invdir.z < 0);
    }
        Vector3 orig;
        Vector3 dir;
 
        Vector3 invdir;
        bool sign[3];
};
bool ray_aabb_intersection(const Ray& r, const AABB& aabb, float& tmin, float& tmax )
{
        float txmin, txmax, tymin, tymax, tzmin, tzmax;
        txmin = (aabb .bounds[r.sign[0]].x - r.orig.x) * r.invdir.x;
        txmax = (aabb .bounds[!r.sign[0]].x - r.orig.x) * r.invdir.x;
        tymin = (aabb .bounds[r.sign[1]].y - r.orig.y) * r.invdir.y;
        tymax = (aabb .bounds[!r.sign[1]].y - r.orig.y) * r.invdir.y;
        if ((txmin > tymax) || (tymin > txmax))
                return false;
        if (tymin > txmin) { tmin = tymin; } else { tmin = txmin; }
        if (tymax < txmax) { tmax = tymax; } else { tmax = txmax; }
        tzmin = (aabb.bounds[r.sign[2]].z - r.orig.z) * r.invdir.z;
        tzmax = (aabb.bounds[1-r.sign[2]].z - r.orig.z) * r.invdir.z;
        if ((tmin > tzmax) || (tzmin > tmax))
                return false;
        if (tzmin > tmin) { tmin = tzmin; }
        if (tzmax < tmax) { tmax = tzmax; }
     
        return true;
}

        მოცემულ კოდში მას შემდეგ რაც ვპოულობთ თანაკვეთებს 4 სიბრტესთან ვბრუნდებით ფუნქციიდან თუ სცდება სხივი კვანძს. თუმცა გარკვეულ შემთხვევაში,(მაგალითად SIMD გამოთვლების დროს) პრობლემას წარმოადგენს ფუნქციიდან ნაადრევი დაბრუნება და ამჯობინებენ ხოლმე, რომ შემოწმებები შეამცირონ და დატოვონ ერთი შემოწმება ბოლოში.

        float-ებთან დაკავშირებული კიდევ ერთი მნიშვნელოვანი პრობლემა იჩენს თავს როდესაც float-ის სიზუსტე ხდება არასაკმარისი და შედეგად ვიღებთ ტყუილ მოხვედრებს ან ტყუილ აცდენებს. საინტერესო და რაც მთავარია მარტივ გადაწყვეტას გვთავაზობს SolidAngle, რაც თავიდან გვაცილებს ტყუილ აცდენებს(რაც მაგალითად ტესტის დროს ბევრად კრიტიკული პრობლემაა ვიდრე ტყუილი მოხვედრა). კოდი გამოიყურება შემდეგნაირად:

const float& min(const float& a, const float& b) {
        return (a < b) ? a : b;
}
const float& max(const float& a, const float& b) {
        return (a > b) ? a : b;
}
bool ray_aabb_intersection( const Ray &r, const AABB& aabb, float& tmin, float& tmax ) {
        float txmin, txmax, tymin, tymax, tzmin, tzmax;
        txmin  = (aabb.bounds[ r.sign[0]].x-r.origin.x) * r.inv_dir.x;
        txmax = (aabb.bounds[!r.sign[0]].x-r.origin.x) * r.inv_dir.x;
        tymin  = (aabb.bounds[ r.sign[1]].y-r.origin.y) * r.inv_dir.y;
        tymax = (aabb.bounds[!r.sign[1]].y-r.origin.y) * r.inv_dir.y;
        tzmin  = (aabb.bounds[ r.sign[2]].z-r.origin.z) * r.inv_dir.z;
        tzmax = (aabb.bounds[!r.sign[2]].z-r.origin.z) * r.inv_dir.z;
        tmin   = max(tzmin, max(tymin, max(txmin, tmin)));
        tmax  = min(tzmax, min(tymax, min(txmax, tmax)));
        tmax *= 1.00000024f;
        return tmin <= tmax;
}

        tmax *= 1.00000024f; ჩანაწერი მცირედით ზრდის tmax-ის მნიშვნელობას(double სიზუსტის დროს იქნება 1.0000000000000004) რაც თავიდან აგვაცილებს სიზუსტის მიერ გამოწვეულ ტყუილ აცდენებს. ამის სანაცვლოდ გაიზრდება ტყუილი მოხვედრები რაც ჩვენთვის ნაკლებას კრიტიკულია.