程序代写代做代考 algorithm Ray Tracing

Ray Tracing
Lecture: 10
Fall 2016
Computer Graphics (CS3388) Department of Computer Science
University of Western Ontario

Ray Tracing
Outline
Global shading
Camera geometry
Ray-sphere intersection
Ray intersection with other generic objects
Shadow feeler
Recursive ray tracing
Refraction/transparency
materials from R. Yang (Kentucky), J. Bikker (Utrecht Univ.), N. Pollard (CMU), MIT open course material, D.S. Fussell (Texas)
1

Local vs. Global Rendering
Local rendering
Object illuminations are independent
No light scattering between objects
No real shadows, reflection, transmission
Global rendering
Ray tracing (highlights, reflection, transmission) Radiosity (surface interreflections)
2

Ray Tracing
What is Ray Tracing
Trace the path of a ray of light. Model its interactions with the scene
When a ray intersects an object, send off secondary rays (reflection, shadow, transmission) and determine how they interact with the scene
3

Ray Tracing: Examples
4

Ray Tracing: Examples
5

Ray Tracing: Examples
6

Ray Tracing: Examples
7

Ray Tracing: Examples
Projective methods
For each object…
…find and update all pixels that it influences
Ray tracing
For each pixel…
… find all objects that influence it and update it accordingly
8

Forward Ray Tracing
Traces the ray “forward”: from the light source through potentially many scene interactions
Problem: most rays will never even get close to the eye
Very inefficient since it computes many rays that are never seen
9

Backward Ray Tracing
Traces the ray “backward”: from the eye, through a point on the screen
More efficient: computes only visible rays (since we start at eye) Generally, ray tracing refers to backward ray tracing
10

Ray Casting
For every pixel
Construct a ray from the eye
For every object in the scene
Find intersection with the ray
Keep if closest
Shade
11

Ray Tracing: types of rays
Primary rays:
Sent from the eye, through the image plane, and into the scene May or may not intersect an object in the scene
No intersection: set pixel to background color
Intersects object: send out secondary rays and compute lighting model
12

Ray Tracing: types of rays
Secondary rays:
Sent from the point at which the ray intersects an object Multiple types:
Transmission (T): to the direction of refraction
Reflection (R): to the direction of reflection (Phong model)
Shadow (S): towards light source
13

Ray Tracing: types of rays
14

Ray Tree
Ray tree is evaluated from bottom up:
Depth-first traversal
The node color is computed based on its children’s colors.
15

Ray Tracing: coordinate system
We need to “shoot” a ray →−
from the viewpoint e →−
through pixel s on the screen towards the scene objects
16

Ray Tracing: coordinate system
Parametric line (or ray) equation:
→− →− →− →− p(t)= e +t(s − e)
→−
starts at e (t = 0) →−
goes through s (t = 1)
“shoots” towards scene objects (t > 1)
17

Ray Tracing: coordinate system
Camera coordinate system:
camera position e viewing direction −w
→−
→− →−
view up vector t
(Remember stuff from viewing lecture)
18

Ray Tracing: coordinate system
Given
Our scene in world-coordinates
A camera position in world-coordinates (x, y, z) A pixel (i, j) in the viewport
We need to
Compute the point on the view plane window that corresponds to the (i, j) point in the viewport
Transform that point into world-coordinates
19

View-reference coordinates
20

View-reference window
21

Computing Window Point
Reverse the Window-to-Viewport transformation:
22

Viewport Window transform
window-viewport:
(Remember stuff from clipping lecture)
i =(u−umin) imax −imin umax − umin
j = (v −vmin) jmax −jmin vmax − vmin
+imin +jmin
Inverse transform: viewport-window: u=(i−imin)umax −umin +umin
v = (j − jmin)vmax − vmin + vmin jmax − jmin
imax − imin
23

View to world coordinate
We have already done this is viewing lecture,
ux uy uz 01 0 0 −ex
MW2V =vx vy vz 00 1 0 −ey 
wz wy wz 00 0 1 −ez 00010001
Hence, the view to world will be,
us  ux vx wz exus  Sworld =M−1 vs=uy vy wy eyvs
  W2V ws uz vz wz ezws
100011
Sworld =e+usu+vsv+wsw
24

Ray-object intersection
In general, the intersection points of
→−
→− →−
Aray p(t)= e +td and →−
an implicit surface f ( p ) = 0
can be calculated by, or
→−
f ( p (t)) = 0
→−
→−
f(e +td)=0
25

Ray-sphere intersection
The implicit equation of the generic sphere (centred at the origin, with radius equal to 1) is written as,
x2 + y2 + z2 = 1
2 →−
Any point p on the sphere satisfies ||p|| = 1. If p (t) is on the surface of
the sphere,
→− 2 →− →− 2 ||p(t)|| =||e +td|| =1
26

Ray-sphere intersection
We have,
which can be written as,
& solve for t as,
At2 + 2bt + c = 0 √
t=−b± b2−ac aa
→− 2 →− →− →− 2
||e|| +2e dt+||d|| −1=0
b2 − ac < 0 The ray misses the sphere b2 − ac = 0 The ray grazes the sphere at t b2 − ac > 0
2 intersections (enter & leave)
27

Ray-plane intersection
The equation of the generic plane is given by z = 0. The intersection of the ray with the generic plane is straightforwardly obtained with setting the ray equation with z = 0 as a constraint, which implies ez + dz t = 0. This implies,
t = − ez dz
If dz = 0, then the ray is parallel to the plane and does not intersect it
Otherwise the ray hits the plane at.
→− ez→− Phit = e − d d
z
28

Ray-cylinder intersection
The implicit equation for a generic cylinder of infinite extent in z (for z ∈ [−∞, ∞]) is given by,
x2 + y2 = 1 The ray intersects the cylinder if
(ex +dxt)2 +(ey +dyt)2 −1=0
which can be expressed as a quadratic equation at2 + 2bt + c = 0
After solving for t, we find z as (ez + dz t) & verify if z ∈ [−1, 1]
intersect the ray with these two planes z = −1 & z = 1, & verify if the solution is within the circle (of radius equal to 1) defined by the cap on the respective planes.
29

Ray-cone intersection
The implicit equation of the generic implicit cone of infinite wall extent is given by,
x2 + y2 − (1 − z)2 = 0
Similarly as previous cases, substituting the equation of ray we obtain the
quadratic at2 + 2bt + c = 0.
Aftersolvingfort,wefindz=(ez +dzt)&verifyifz∈[−1,1],
which means there is an intersection between the ray & the cone wall.
We also need to verify if the ray intersects with the base of the cone which is contained within the plane z = −1 , as before. The base of the cone is a generic circle (of radius equal to one).
30

Ray-convex polyhedra intersection
Polyhedra are composed of facets that are planar
→−
→−
F(P)= n.(P−B)
→− Whentherayhitstheplane, n.(e +td −B)=0,whichimplies,
→− →− t = n .(B − e )
If the plane has outward-pointing normal n , the equation of the
plane is,
→− →−
→− →−
The ray is passing from inside to outside if n . d > 0, since n and d are less than 90◦ apart
n.d
→−→− →−→−
31

Ray-convex polyhedra intersection
→− →−
Ray from inside to outside
Ray from outside to inside
Ray totally outside
Ray totally inside
n.d>0 →− →−
n.d<0 →− →− →− →− n . d = 0, n .(B − e ) > 0
→− →− →− →−
n . d = 0, n .(B − e ) < 0 32 Surface normal at intersections Given a point P on a generic sphere, the normal to the sphere at this point is simply the point itself, considered as a vector. For planes, the generic equation is z = 0 & the normal is given by →− n =(0,0,1) In the case of a generic cylinder, if the intersection point is on the wall, the normal is computed as, (x, y, 0) n = 􏶣x2 +y2 →− If the intersection is on the base of the cylinder, then n = (0, 0, −1), →− →− Conversely, if it is on the top, the normal is then n = (0, 0, 1). 33 Shading model Remember shading models. The intensity is simply the sum of all the components, i.e., I = IAmbient + ILambertian + IPhong Repeat the same for red, green & blue components to compute Ir , Ig , Ib 34 Basic ray tracing algorithm: revisited 35 Shadows in ray tracing Surface is only illuminated if nothing blocks its view of the light If hit point is in shadow, render using only ambient, leave out specular and diffuse 3 possible cases no other object between hit point and light source (no shadow) another object between hit point and light source (occlusion) object blocks itself from light source (back face) 36 Shadow feelers Shadows can be implemented fairly easy by so called shadow feelers / rays →−→−→− →− Shoot a ray (p +t l ) from point p towards a light source l →− shade (ray, point, normal, light) shadowRay = (point, light.pos point); if (shadowRay not blocked) //compute shading else return black; If ray hits object, p is in the shadow. Otherwise it’s not So far, so good... 37 Implementing shadow: precision issue You might fall into the classic blunder of precision issues! What’s going on? at what t does the shadow ray intersect the surface you’re shading? shadow rays start a tiny distance from the surface add ε and the problem will be solved! *courtesy: K. Bala, Cornell Univ. 38 Shadow: pseudocode pseudocode of shade function: feeler.start = hitPoint - epsilon * ray.dir; color = ambient part; for(each light source, L) { feeler.dir = L.pos - hitPoint; if(isInShadow(feeler)) continue; color.add(diffuse light); color.add(specular light); } 39 Recursive ray tracing For each pixel, Trace Primary Eye Ray and find intersection Trace secondary shadow rays to all lights Trace Reflected/Refracted Ray 40 Recursive ray tracing pseudocode color shade(object o, pos x, vector ur, int level) if(level > max_recursion_level)
return black; else{
um = reflection_vector(x, o, ur ); (om, t) = shoot(x, um);
if(t == ∞)
color = background_color; else{
m_color = shade(om, x +t ∗um, um, level+1);
color = directshade(o, x, ur, m_color, −um); }
for(each light i in the scene) if(light i is visible from x)
color += directshade(o, x, ur ,
light[i].color, light[i].direction); return color;
41

Refraction/Transparency
Qualitative refraction:
42

Refraction/Transparency
Light bends (refracts) when it passes from one material to another
Use Snell’s law to compute direction of refracted ray (based on the refractive index of the two mediums)
vacuum: 1
air: 1.000277 water: 1.33 glass: 1.5-1.75
43

Refraction: Snell’s law
Snell’s law: Tells us where the refracted ray goes (a.k.a. transmission vector)
Relative index of refraction, ηr is given by,
ηi sin θi = ηT sin θT
sinθT = ηi =ηr sin θi ηT
44

Refraction
How to compute the transmission vector T?
I=Ncosθi −Msinθi
=⇒ M=(Ncosθi −I)/sinθi
Similarly, transmission vector T can be written as, T=−NcosθT +MsinθT
Substituting M in T,
T=−NcosθT +(Ncosθi −I)sinθT/sinθi
45

Refraction
Applying Snell’s law,
T=−NcosθT +(Ncosθi −I)ηr
= [ηr cosθi −cosθT]N−ηrI 􏶢2
=[ηr cosθi − 1−sin θT]N−ηrI =[ηr cosθi −􏶢1−ηr2sin2θi]N−ηrI
Sometimes dealing with cosine is easier to handle than with sine:
􏶢
=[ηr cosθi − =⇒
1−ηr2(1−cos2θi)]N−ηrI
􏶢
T =[ηr(N.I)− 1−ηr2(1−N.I)2]N−ηrI
46

Total internal reflection
T =[ηr(N.I)−
􏶢
1−ηr2(1−N.I)2]N−ηrI
when the square root is imaginary, there is no refracted ray and all of the energy is reflected. This is called total internal reflection
47

Refraction: considerations
When a ray hits a translucent object, compute T, using r.i.=1 for air & given r.i. of the material, call the shader & add up with the colours accumulated so far
When the ray is inside the object, the normal to the hit point should reverse it’s sign
Inside an object, there is no ambient, diffuse or specular light
The inside wall of the translucent object may be reflective and therefore a reflection ray may be cast back into the object.
Upon exit of the refracted ray from the object, adjust the r.i. of the mediums, & check for total internal reflection
ITotal = IAmbient + ILambertian + IPhong + IReflection + IRefraction
48