Computação Interactiva e em GPU
Interactive and GPU Computing
11494: Mestrado em Engenharia Informática
Chap. 2 — Ray Casting
Ray Casting
Chapter 2: Ray Casting
Outline
…:
– Parametric and implicit objects: a reminder.
– Implicit surfaces
– Ray casting: the basic idea
– Constructing rays through pixels
– Finding intersection points between rays and objects
– Pixel color computation: Lambertian model reminder
Chapter 2: Ray Casting
Parametric and implicit objects:
a short reminder
parametric circle
implicit circle
f (x, y) = x 2 + y 2 − r 2 = 0
# x = r cos θ
$ f (x, y) < 0 (inside)
% y = r sin θ
f (x, y) > 0 (outside)
€
€
Chapter 2: Ray Casting
IMPLICIT SURFACES
Chapter 2: Ray Casting
Implicit surfaces
Definition:
– An implicit surface is a zero set of a function:
f (x, y,z) = 0
– Example: the radius-r sphere
f (x, y,z) = x 2 + y 2 + z 2 − r 2 = 0
Other designations:
€
– Isosurface / Level set
€ $ ∂f '
Unit surface normal:
& )
& ∂x )
∇f ∂f
– It is the normalized gradient vector
n= where ∇f = & )
∇f & ∂y )
Advantages:
& ∂f )
&% ∂z )(
– The entire surface is represented by a single function.
– We can perform interesting operations with this function.
– Example: adding multiple surface functions
€ together
Chapter 2: Ray Casting
Implicit as solids
Representation of solids:
– Implicit functions represent important classes of solids, which are not necessarily
bounded.
– Example:
§ Ellipsoid: is a closed, manifold surface that encloses a solid.
– The surface of such a solid is said to be its boundary, which separates the interior
from the exterior of the solid.
Chapter 2: Ray Casting
http://en.wikipedia.org/wiki/Quadric
Quadric surfaces
They are a particular case of implicit surfaces.
Definition:
– Every quadric surface is defined by the 2nd degree polynomial:
f (x, y,z) = Ax 2 + 2Bxy + 2Cxz + 2Dx + Ey 2 + 2Fyz + 2Gy + Hz 2 + 2Iz + J = 0
"A B C D% " x %
$ '$ '
€ B E F G '$ y '
Matrix form:
f (x, y,z) = v T Mv = [ x y z 1] $
$C F H I '$ z '
$ '$ '
#D G I J & #1 &
€
Chapter 2: Ray Casting
http://en.wikipedia.org/wiki/Gaussian_function
Gaussian blob surfaces
They are another particular case of implicit surfaces.
Definition:
– A Gaussian blob surface is defined by summing up Gaussian functions for a given
threshold T, each one of which is associated to a point (e.g., center of an atom) in
3D space
$ (x −x )2 (y −y )2 (z −z )2 '
0 0 0
N −&& 2
+ 2
+ 2 )
)
2σ 2σ 2σ
– f (x, y,z) = ∑ f i − T = 0 with
f i (x, y,z) = ae
% x y z (
i=1
€
€
N =1 N =2 N =3
€ € €
Chapter 2: Ray Casting
RAY CASTING
Chapter 2: Ray Casting
http://en.wikipedia.org/wiki/Ray_tracing_(graphics)
Ray casting
Arthur Appel (1968). Some techniques for shading machine
rendering of solids. AFIPS Conference Proc. 32, pp. 37-45.
Key idea:
– The idea behind ray casting is to shoot rays from the eye, one per pixel, and find
the closest object blocking the path of that ray.
– The color of each pixel on the view plane depends on the radiance emanating from
visible surfaces.
Algorithm:
– For each pixel
§ Calculate ray from viewer point through pixel
§ Find intersection points with scene objects (e.g., a sphere)
§ Calculate the color at the intersection point near to viewer (e.g., Phong illumination
model)
Chapter 2: Ray Casting
http://www.unknownroad.com/rtfm/graphics/rt_eyerays.html
Step 1: Constructing a ray through each pixel
Equation of the ray passing through a pixel:
x(t) = o + tv x[i, j]
where:
– o is the camera (eye) position;
€ €
– v is the vector that stands for the direction of
the ray starting at o and passing through pixel
(i,j):
x −o
v=
x −o
where x is the float-point location of the
window corresponding to the pixel (i,j) of a
discrete
€ view screen (in the view plane) of
resolution (W,H):
Chapter 2: Ray Casting
Step 1: Constructing a ray through each pixel
http://www.unknownroad.com/rtfm/graphics/rt_eyerays.html
(cont’d)
P1
!
u
Side view of camera at o:
€
!
– Position of the i-th pixel x[i]?
θ l d
€ h
– Let us first agree that:
!
! ! ! o
P0 = o + d l - d tan(θ )u
! € €
! ! x[i]
P1 = o + d l + d tan(θ )u
h = 2d tan(θ ) €
€ ! P0
– Also:
o : origin of camera
€ (pinhole)
€ !
l : look vector
i+0.5 !
€ x[i] = (P1 − P0 ) u : up vector
H €
€ H : discrete height of screen (in pixels)
so
€ h : height of screen
i+0.5 ! d : distance to screen
x[i] = hu €
H
€ θ : field of view (FOV) or frustum halfangle
€
€
€
Chapter 2: Ray Casting
Step 1: Constructing a ray through each pixel
http://www.unknownroad.com/rtfm/graphics/rt_eyerays.html
(cont’d)
Q1
!
v
Top view of camera at o:
€
!
– Position of the j-th pixel x[j]?
φ l d
€ w
– Analogously, we have:
!
o
j+0.5 !
x[ j] = wv € €
W x[ j]
€
! Q0
o : origin of camera (pinhole)
! €
l : look vector
!
u : up/side vector
€
€ W : discrete width of screen (in pixels)
€ w : width of screen
€ d : distance to screen
€ φ : field of view (FOV) or frustum halfangle
€
€
€
Chapter 2: Ray Casting
Step 1: Constructing a ray through each pixel
http://www.unknownroad.com/rtfm/graphics/rt_eyerays.html
(cont’d)
P1
!
u
€
!
θ l d
In conclusion:
€ h
!
– The equation of the ray through each o
pixel (i,j) is given by:
€ €
x[i]
€
P0
€ Q1
! i +0.5 ! j +0.5 !
x[i, j] = o + hu + wv
H W !
v €
€
!
€ φ l d
€ w
!
o
€ €
x[ j]
€
Q0
€
Chapter 2: Ray Casting
Step 2: Finding intersection points
http://www.realtimerendering.com/int/
between rays and implicitly-defined objects
General algorithm:
– Given the equation of the ray:
x(t) = o + tv
– Given a surface in implicit form f(x,y,z)=0:
§ Plane
f (x) = ax + by + cz + d = n • x+d = 0, with n = (a, b, c) and x = (x, y, z)
€
§ Sphere
f (x) = x 2 + y 2 + z 2 −1 = 0
§ Cylinder
f (x) = x 2 + y 2 −1 = 0 and 0 < z < 1
€
– We know that all points on the surface satisfy f(x,y,z)=0.
– Therefore, for a ray x(t) to intersect the surface, we have to solve:
f (x(t)) = f (o + tv) = 0
Chapter 2: Ray Casting
Ray-plane intersection
Algorithm:
– Given the equation of a generic ray:
x(t) = x 0 + tv
– Given the equation of the plane:
f (x) = ax + by + cz + d = n • x + d = 0
€
where
§ n is the normal to the plane
€
§ d is the distance of the plane from the origin
– Substituting and solving for t, we obtain:
f (x(t))
=
f (x
0 + tv)
= 0
or
f (x(t)) = n • (x 0 + tv) + d = 0
so, the ray hits the plane at
€ t=
−(n • x 0 + d)
€
n• v
Chapter 2: Ray Casting
http://www.lighthouse3d.com/opengl/maths/index.php?raytriint
Ray-triangle intersection
Tomas Möller and Ben Trumbore, “Fast, minimum storage ray-
triangle intersection”, Journal of Graphics Tools, 2(1):21-28, 1997
Algorithm:
– Given the equation of a generic ray:
x(t) = o + tv
– Given the equation:
x = (1 − u − v)x 0 + ux1 + vx 2 u,v ≥ 0, u + v ≤ 1
€
that expresses x in barycentric coordinates (u,v) as a point in a triangle with vertices
x0, x1, x2
€
– If the intersection point belongs to both ray line and triangle, we have:
x(t)
=
o
+ tv = (1 − u − v)x 0 + ux1 + vx 2
– Thus, solve the previous equation system for (t,u,v) in terms of (x,y,z).
€
Chapter 2: Ray Casting
Testing ray-triangle intersection
•R. J. Segura, F. R. Feito,”Algorithms to test Ray-
triangle Intersection Comparative Study”,WSCG
2001.
Chapter 2: Ray Casting
Ray-sphere intersection
Algorithm:
– Implicit form of sphere given center (a,b,c) and radius r:
2
x − c = r2 x = (x, y,z), c = (a,b,c)
– Intersection with the ray x(t)=o+tv gives:
2
o + tv − c = r 2
€ 2 2 2
– Taking into account the identity
a + b = a + b + 2(a • b)
§ the intersection is a quadratic equation in t:
€ 2 2 2
o + tv − c − r 2 = t 2 v + 2tv • (o − c) + ( o − c − r 2 )
€
– Solving for t:
2 2
−v • (o − c) ± (v • (o − c)) 2 − v ( o − c −r 2 )
t= 2
v
€
§ Real solutions indicate one point (tangent point) or two intersection points
§ Negative solutions are behind the eye
§ €
If discriminant is negative, the ray misses the sphere
Chapter 2: Ray Casting
Pixel color computation
Two major possibilities:
– The Lambertian/Phong illumination model of OpenGL.
§ It does not require implementation because it already comes with OpenGL.
– The Lambertian/Phong illumination output to a pixel matrix of some image file
format (e.g., TGA)
§ It requires implementation.
Chapter 2: Ray Casting
Pixel color computation:
diffuse light
! ! !
ID = K D ( N • L)I N
θ! !
L
€
Lambertian model for diffuse light:
– Specify how material reflects light:
object surface P
– Bind material to each object in a scene
– Calculates the Lambert coefficient at // list of lights!
each hit point of the object surface.
Light!
{!
– Calculates the color at each hit point of Position = 0.0, 240.0, -100.0;!
Intensity = 1.0, 1.0, 1.0 ;!
the object surface:
}!
// list of materials !
Material!
{!
Reflection coefficient
Id = 0;!
Normal vector
Diffuse = 1.0, 1.0, 0.0;!
Reflection = 0.5;!
Light vector
}!
// calculates the Lambert coefficient! // list of objects!
float K = KD * (NL); ! Sphere!
// calculates the RGB color! {!
red += K * Light.red * Material.red; ! Center = 20.0, 20.0, 0.0;!
Radius = 9.0;!
green += K * Light.green * Material.green;! Material.Id = 0;!
blue += K * Light.blue * Material.blue;! }!
Chapter 2: Ray Casting
Ray casting algorithm: review
Courtesy F.S. Hill, “Computer Graphics using OpenGL”
Algorithm:
– Define the objects and light sources in the scene
– Set up the camera
– for (int i=0; i<nRows; i++)!
– for (int j=0; j<nCols; j++)!
1. Build the (i,j)th ray
2. Find intersections of the (i,j)th ray with the objects in the scene
3. Identify the intersection that lies closest to, and in front of, the eye
4. Compute the hit point where the ray hits this object, and the normal at that point
5. Find the color of the light returning to the eye along the ray from the hit point
6. Place the color at the (i,j)th pixel
Chapter 2: Ray Casting
Summary:
…:
– Parametric and implicit objects: a reminder.
– Implicit surfaces
– Ray casting: the basic idea
– Constructing rays through pixels
– Finding intersection points between rays and objects
– Pixel color computation: Lambertian model reminder
