تشخیص برخورد ray , و AABB

یکی از راه های تشخیص برخورد ray و AABB این است که شی را بر اساس Slab تعریف کنیم،slab برابر فضای نامتنهای بین دو صفحه (در سه بعد) و یا دو خط (در دو بعد) است، از این تعریف می توانیم برای بیان چند ضلهی های محدب استفاده کنیم، هر slab  دارای  ساختار زیر است :  یک بردار واحد که نماینده جهت slab  است و دو مقدار عددی که هرکدام نماینده فاصله هر ضلع تا مبدا مختصات در جهت داده شده است . چون شکل  ما محدب هست در هر جهت دو برخورد وجود دارد. اگر d نماینده یکی از این فواصل باشد و n بردار عمود بر ضلع یا همان بردار جهت ما باشد؛ برای هر نقطه X روی  ضلع داریم :X.n=d

  

و همچنین از طرفی طبق تعریف ray  ، R(t)=O+D *t که D همان جهت ray و O نقطه مبدا آن می باشد ، برای هر نقطه روی ray یک t وجود دارد که t باید بزرگتر مساوی 0  باشد: 0<t . اگر این معادله را در معادله قبل جایگزین کنیم و t  را بدست آوریم نقطه برخورد ray و آن ضلع بدست می آید:

.البته ابتدا باید چک شود که بردار جهت و ضلع ما موازی نباشند.(n X (a-b)!=0) . همانطور که میدانیم اضلاع AABB دارای 4 ضلع است که برای هر ضلع یک ضلع موازی دیگر وجود دارد، که همچنین برای این اضلاع یک بردار عمود وجود  دارد، بردار یکه این بردار عمود همان بردار جهت slab ما می باشد، بنابر این طبق این تعاریف هر AABB از دو slab تشکیل شده است، چون در AABB ها چرخش وجود ندارد، جهات slab ما در واقع دو محور دستگاه مختصات هستند، یعنی (1,0)Y= ,  (0,1)X= ، بنابراین می توانیم در ضرب بردار ها با این دو  جهت مستقیم پارامتر های بردار  را جایگذین کنیم، برای مثال a.x*1+a.y*0 =a.x = a.dot(1,0)   

در ساختمان داده AABB دو بردار min و max تعریف شده است، مولفه های این دو بردار در واقع همان فواصل ما در تعریف slab  هستند، برای مثال در slab که جهت آن محور X  می باشد فواصل برابر مولفه های x aabb ما هستند. اگر بخواهیم  این دو فاصله را با d1 وd2 نشان دهیم خواهیم داشت d1=min.x و d2=max.x ، و همین قضیه برای محور Y ها صادق هست.

برای هر slab و ray دو برخورد وجود خواهد داشت، که این دو برخورد یک فاصله interval)) را تشکیل می دهند. برای تشخیص برخورد باید چک کنیم که این فواصل با هم همپوشانی دارند یا نه.

برای هر فاصله یا به عنوان دیگر slab  مقادیر min  و max داشته باشیم، اگر ماکس min ها و مین max ها را مقایسه کنیم و مین ما از مکس ما کمتر باشد نتیجه میگیریم برخورد رخ داده است:

     //for direction (1,0)

        var d:Number=aabb.min.x;

        var denom:Number=dir.x

        var t1x:Number=(d-o.x)/denom

        d=aabb.max.x

        var t2x:Number=(d-o.x)/denom

        if(t1x>t2x){

        var tmp:Number=t2x

        t2x=t1x

        t1x=tmp;

        }

        //for direction (0,1)

        d=aabb.min.y

        denom=dir.y

        var t1y:Number=(d-o.y)/denom

        d=aabb.max.y

        var t2y:Number=(d-o.y)/denom

        if(t1y>t2y){

        tmp=t2y

        t2y=t1y

        t1y=tmp;

        }

        var minMax:Number=Math.min(t2x,t2y)

        //set negative multiplier to ZERO

        minMax=minMax<0?0:minMax

        var maxMin:Number=Math.max(t1x,t1y)

        maxMin=maxMin<0?0:maxMin

        if(minMax>maxMin) {

            var s:Vec2D=dir.scaledBy(maxMin)

            s.add(o)

        p.setVec2D(s)

        return true;

        }