A ray is a point : O(ox,oy,oz) and a direction : unit vector D(dx,dy,dz)
A sphere is : center (a,b,c) and radium r
We are looking for the intersection point : I(x,y,z)
There are 2 ways :
We have : (x-a)^2 + (y-b)^2 + (z-c)^2 = r^2 x=ox + t*dx y=oy + t*dy z=oz + t*dz Which mean : (ox+t*dx - a)^2 + (oy+t*dy - b)^2 + (oz+t*dz - c)^2 = r^2 t^2(dx^2+dy^2+dz^2) + t*2( dx(ox-a)+dy(oy-b)+dz(oz-c) ) + (ox-a)^2+(oy-b)^2+(oz-c)^2-r^2 = 0 So A*t^2 + B*t + C=0 With : A = dx^2+dy^2+dz^2=1 car D norm=1 B = 2( dx(ox-a)+dy(oy-b)+dz(oz-c) ) C = (ox-a)^2+(oy-b)^2+(oz-c)^2-r^2 det = B^2-4AC = B^2-4C If det>=0 then there is 1/2 intersection(s) sqdet = sqrt(det) t1 = (-b-sqdet)/2 t2 = (-b+sqdet)/2 if t1<0 then t1=t2 if t2<0 then t2=t1 t = min(t1,t2) P(x,y,z) = O(ox,oy,oz) + t*D(dx,dy,dz)
-> |D | = 1 -> -> OK = D . OC CK^2 = OC^2-OK^2 If 0<CK^2<=r^2 then there is an intersection -> -> OI = D*(ok-sqrt(r^2 - CK^2))
A ray is a point : O(ox,oy,oz), and a direction : unit vector D(dx,dy,dz) ABC is a triangle and N is its unit normal.
-> -> -> -> OO' = (OA . N) * N -> -> OI = OO'/acos( (OO' . D)/OO' ) -> -> OI = OI * D |
A ray is a point : O(ox,oy,oz), and a direction : unit vector D(dx,dy,dz). ABC is a triangle
With the previous method, we find I the intersection of the ray and of the plane (ABC).
For this we need to precompute A',B',C' the base of the "height" line of the triangle (see figure), and G the barycenter of the triangle.
The intersection is inside the triangle if :-> -> A'I . A'G >= 0 -> -> and B'I . B'G >= 0 -> -> and C'I . C'G >= 0 |
This method will work for any polygon, and can even be faster than the previous method in the case of triangles.
Let A(1),...,A(n) be the vertices of the polygon.
For every triangle I,A(i),A(i+1) we'll check if its algebric area is positive :
-> -> -> Area*2 = N . ( IA(i) * IA(i+1) ) -> -> -> Area*2 = N . const_vectorIf every area have the same sign, I is inside the polygon. |
The new direction is : R = D - 2(D.N)*D Just trace a new ray from P with direction R, and add its color
Compute an poly_id buffer : for each pixel, find which polygon/primitive is displayed and get its color from the texture - using for example sbuffer . Then trace a ray only on the proper polygon for each pixel.
Or use a quadtree:
1---2---1---2---1---2---1 |.......|.......|.......| |.......|.......|.......| |.......|.......|.......| 2...2...2...2...2...2...2 |.......|.......|.......| |.......|.......|.......| |.......|.......|.......| 1---2---1---2---1---2---1
Compute a 2D cullbox (2D square around the sphere on the screen):
That does just require a Thales product, x2d = focal*X/Z and y2d = focal*Y/Z. with -1.0<= x2d or y2d <= +1.0. Do alter x2d and y2d so that they are between 0 and the width or heigh of the screen.
Then check if a pixel is inside the sphere's cullbox before casting a ray to it.
-> |D| = 1 -> -> OK = D . OC CK^2 = OC*OC-OK*OKIf CK^2 <= radius*radius, the ray hits the sphere.
Use a BSP tree (in the classic way, in the grid forms - octree, weighted grids...), put sphere around near objects to find quickly which group of objects are not hit by the ray.
Main page | email : Sly |