faintBlack = new Color(0,0,0,64);
abs(t) { return Math.abs(t); }
cos(t) { return Math.cos(t); }
sin(t) { return Math.sin(t); }
pi = Math.PI;
px(v) { return px(v[0],v[1],v[2]); }
py(v) { return py(v[0],v[1],v[2]); }
px(x,y,z) { return (7 * x - 3.4 * z) / (10 - .1*z); }
py(x,y,z) { return (7 * y - 3.4 * z - .3*x) / (10 - .1*z); }
set(v, x, y, z) { v[0] = x; v[1] = y; v[2] = z; }
dot(v, w) { return v[0] * w[0] + v[1] * w[1] + v[2] * w[2]; }
diff(a, b, c) {
for (j = 0 ; j < 3 ; j++)
c[j] = a[j] - b[j];
}
Color gridColor = new Color(0, 0, 0, 32);
normalize(vec) {
norm = Math.sqrt(dot(vec, vec));
vec[0] /= norm;
vec[1] /= norm;
vec[2] /= norm;
}
drawEye(x, y) {
draw.setColor(Color.red);
draw.drawDisk(x,y-.01,.13,.07);
draw.fillDisk(x,y-.01,.13,.07);
draw.setColor(Color.white);
draw.drawText("eye",x,y);
draw.setColor(Color.black);
}
drawSphere(cx,cy,r,color) {
draw.setColor(color);
draw.fillDisk(cx,cy,r);
draw.setColor(Color.black);
draw.drawDisk(cx,cy,r);
}
drawArrow(ax,ay,bx,by) {
drawArrow(ax,ay,bx,by,0.02);
}
drawArrow(ax,ay,bx,by,double r) {
drawArrow(ax,ay,bx,by,r,Color.black);
}
drawArrow(ax,ay,bx,by,Color color) {
drawArrow(ax,ay,bx,by,0.02,color);
}
drawArrow(ax,ay,bx,by,Color color,bgColor) {
drawArrow(ax,ay,bx,by,0.02,color,bgColor);
}
drawArrow(ax,ay,bx,by,r,color) {
drawArrow(ax,ay,bx,by,0.02,color,Color.black);
}
drawArrow(ax,ay,bx,by,r,color,outlineColor) {
draw.setColor(color);
draw.fillArrow(ax,ay,bx,by,r);
draw.setColor(outlineColor);
draw.drawArrow(ax,ay,bx,by,r);
}
Ray tracing, part two
Ray tracing different shapes
Ray tracing to a plane
Equation of a ray and equation of a plane:
Equation of a ray: P = v + tw, for t 0
Equation of a plane: L = (a,b,c,d)
Point P is on plane L when PL = 0.
L(x,y,z,1) = ax + by + cz + d = 0
ax = -1.0;
ay = -0.5;
bx = 1.0;
by = 0.5;
double[] X = {-0.4, 0.4, 0.4,-0.4};
double[] Y = { 0.6, 0.4,-0.7,-0.4};
draw() {
draw.setColor(Color.red);
draw.fillArrow(0,0,bx,by,.02);
draw.setColor(Color.red);
draw.drawText("P=v+tw", ax, ay - .1);
if (mode >= 1) {
draw.setColor(Color.blue);
draw.drawPolygon(X, Y, 4, .01);
draw.drawText("L=(a,b,c,d)", -1.3, .8, 1);
}
if (mode >= 2) {
draw.setColor(Color.black);
draw.drawText("P.L=ax+by+cx+d", -1.3,0.3, 1);
}
if (mode >= 3) {
draw.setColor(Color.black);
draw.fillDisk(0,0,.05);
draw.drawText("P.L=0", .6,-.2,1);
draw.fillArrow(.55,-.2,.1,-.03,.025);
}
draw.setColor(Color.red);
draw.draw(ax,ay,0,0,0.02);
}
Solving for t where the ray intersects the plane:
ax + by + cz + d = 0
a(vx+twx) + b(vy+twy) + c(vz+twz) + d = 0
(awx + bwy + cwz) t + (avx + bvy + cvz + d) = 0
(wL) t + (vL) = 0;
t = -(vL) / (wL)
Finding the intersection point P:
P = v + tw
There are a number of cases:
(1) The ray intersects the plane at t 0 (one root).
(2) The line containing the ray intersects the plane at t 0 (no root).
(3) The ray is parallel to the plane (zero roots).
(4) The ray is within the plane (infinitely many roots).
Transforming a plane equation.
Consider a plane L containing a point P. In other words, LP = 0.
When we transform P by matrix M to get MP, we need the transformed plane to also contain the transformed point.
As we learned in a previous lecture, L is transformed to LM-1, because:
(LM-1) (MP) =
L (M-1 M) P =
LP
Also, remember that LM-1 is the same as (M-1 )TL
Ray tracing to a cylinder
ax = -1.0;
ay = -0.1;
bx = 1.0;
by = 0.5;
cx = -.30;
cy = .12;
dx = .20;
dy = .27;
lightPink = new Color(255,200,200);
double[] X = new double[20];
double[] Y = new double[X.length];
draw() {
draw.setColor(Color.red);
draw.fillArrow(ax,ay,bx,by,.02);
draw.setColor(Color.red);
draw.drawText("v+tw", ax, ay - .1);
for (n = 0 ; n < X.length/2+1 ; n++) {
theta = 2 * pi * n / X.length + .3;
X[n] = 0.35 * cos(theta) - 0.1 - .02 * sin(theta);
Y[n] = 0.35 * sin(theta) + 0.2 + .03 * cos(theta);
}
draw.setColor(Color.blue);
for (n = 0 ; n < X.length/2 ; n++) {
draw.draw(X[n], Y[n], X[n+1], Y[n+1], .01);
}
draw.setColor(Color.blue);
for (n = 0 ; n < X.length ; n++) {
theta = 2 * pi * n / X.length;
X[n] = 0.38 * cos(theta) + 0.1;
Y[n] = 0.36 * sin(theta) - 0.2 + .03 * cos(theta);
}
draw.setColor(Color.white);
draw.fillPolygon(X, Y, X.length);
draw.setColor(Color.blue);
draw.drawPolygon(X, Y, X.length, .01);
draw.drawText("x +y - 1 = 0", 0,.7);
draw.drawText(" 2 2 ", -.15,.77);
draw.draw(-.44 ,.09,-.26 ,-.35,.01);
draw.draw( .194,.4 , .455,-.05,.01);
draw.setColor(lightPink);
draw.draw(cx,cy-.01,dx,dy-.01,.02);
draw.setColor(Color.black);
draw.fillDisk(cx,cy,.05);
draw.fillDisk(dx,dy,.05);
}
x2 + y2 - 1 = 0
(vx + t wx)2 + (vy + t wy)2 - 1 = 0
(wx2 + wy2) t2 + (2 vx wx + 2 vy wy) t + (vx2 + vy2 - 1) = 0
(ww) t2 + 2(vw) t + (vv - 1) = 0
So to solve the quadratic equation in t:
A = ww
B = 2 (vw)
C = vv - 1
Ray tracing to a general quadratic
(1) Describe quadratic in its untransformed form.
ax2 + by2 + cz2 + dyz + ezx + fxy + gx + hy + iz + j = 0
Unit sphere: x2 + y2 + z2 - 1 = 0
[ 1 1 1 0 0 0 0 0 0 -1 ]
Cylindrical tube along z axis: x2 + y2 - 1 = 0
[ 1 1 0 0 0 0 0 0 0 -1 ]
Cone along z axis: x2 + y2 - z2 = 0
[ 1 1 -1 0 0 0 0 0 0 0 ]
(2) Apply matrix transformation.
Plane equation ax + by + cz + d, which describes the plane L containing points x, can be defined by the following dot product:
(a b c d)(x y z 1)T = 0
In other words, LxT = 0.
So to find the plane that contains transformed points Mx, L L M-1.
Similarly, we can define quadratic equation
ax2 + by2 + cz2 + dyz + ezx + fxy + gx + hy + iz + j = 0
by the following double dot product:
blueScrim = new Color(0, 0, 255, 64);
redScrim = new Color(255, 0, 0, 64);
String Q = "afeg0bdh00ci000j";
String[] A = {
"a*x*x","f*x*y","e*z*x","g*x*1",
"0*y*x","b*y*y","d*y*z","h*y*1",
"0*z*x","0*z*y","c*z*z","i*z*1",
"0*1*x","0*1*y","0*1*z","j*1*1"};
if (mx == void) {
mx = -10;
my = 0;
}
mouseMove(x, y) { mx = draw.fx(x); my = draw.fy(y); }
draw() {
isOverQ = mx >= -.4 && my >= -.4 && mx <= .4 && my <= .4;
draw.drawText("x", -1.10, .0);
draw.drawText("y", -0.95, .0);
draw.drawText("z", -0.80, .0);
draw.drawText("1", -0.65, .0);
for (i = 0 ; i < 4 ; i++)
for (j = 0 ; j < 4 ; j++) {
x = -.3 + i * .2;
y = .3 - j * .2;
int n = i + 4 * j;
draw.drawText(Q.substring(n, n + 1), x, y);
}
draw.drawText("x", .7, .3);
draw.drawText("y", .7, .1);
draw.drawText("z", .7,-.1);
draw.drawText("1", .7,-.3);
draw.drawText(" = 0 ", 1.05,0);
if (isOverQ) {
draw.setColor(redScrim);
draw.fillBox(-0.875,0,.3,.1);
draw.setColor(blueScrim);
draw.fillBox(0.7,0,.1,.4);
}
draw.setColor(Color.black);
draw.drawBox(-0.875,0,.3,.1);
draw.drawBox(0,0,.4,.4);
draw.drawBox(0.7,0,.1,.4);
if (isOverQ) {
int i = (int)(4 * (mx + .4) / .8);
int j = (int)(4 * (.4 - my) / .8);
draw.setColor(Color.black);
draw.drawText(A[i + 4 * j], 0, -.6);
x = -.3 + i * .2;
y = .3 - j * .2;
draw.setColor(blueScrim);
draw.fillBox(0, y, .4, .1);
draw.setColor(redScrim);
draw.fillBox(x, 0, .1, .4);
}
}
In other words, x Q xT = 0, where Q denotes the 10 quadratic coefficients arranged into the above 44 matrix.
This means that if you want to find the three-variable quadratic equation that contains transformed points MxT, you need to replace Q by (M-1)T Q M-1, because that will give you:
(MxT)T (M-1)T Q M-1 (MxT) =
xT (MT(M-1)T) Q (M-1 M) xT =
x Q xT = 0
Note that when you create the product of:
(M-1)T Q M-1 you can end up with non-zero values in all sixteen slots of your 44 matrix. This is because in addition to x*y, x*z, x*1, y*z, y*1, z*1 terms, you also end up with y*x, z*y, 1*z, z*y, 1*z, 1*z terms, as follows:
Since multiplication of numbers is commutative, you can just add the six numbers in the lower left (shown in magenta above) into their mirror locations on the upper right, as follows:
String[] A = {"A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P"};
String[] B = {"A","B+E","C+I","D+M","0","F","G+J","H+N","0","0","K","L+O","0","0","0","P"};
draw() {
for (int n = 0 ; n < 16 ; n++) {
i = n % 4;
j = n / 4;
draw.drawText(A[n], (i-1.5) * .2 - 0.93, (1.5-j) * .2);
draw.drawText(B[n], (i-1.5) * .4 + (i==0?.58:.53), (1.5-j) * .2);
}
draw.drawBox(-.93,0,.4);
draw.drawBox(.61,0,.72,.4);
draw.fillArrow(-.45,0,-.2,0,.025);
}
This will leave you with just the ten unique coefficients of the quadratic in three variables, in the upper right of your transformed matrix.
(3) Substitute the ray equation into the surface equation.
Replace (x,y,z) by ( vx+twx , vy+twy , vz+twz ).
a(vx+twx)2 + b(vy+twy)2 + c(vz+twz)2 +
d(vy+twy)(vz+twz) + e(vz+twz)(vx+twx) + f(vx+twx)(vy+twy) +
g(vx+twx) + h(vy+twy) + i(vz+twz) + j = 0
Multiply everything out:
a(vx+twx)(vx+twx) + b(vy+twy)(vy+twy) + c(vz+twz)(vz+twz) +
d(vy+twy)(vz+twz) + e(vz+twz)(vx+twx) + f(vx+twx)(vy+twy) +
g(vx+twx) + h(vy+twy) + i(vz+twz) + j = 0
(awx2 + bwy2 + cwz2 + dwywz + ewzwx + fwxwy) t2 +
(2avxwx + 2bvywy + 2cvzwz + d(vywz+vzwy) + e(vzwx+vxwz) + f(vxwy+vywx) + gwx + hwy + iwz) t +
(avx2 + bvy2 + cvz2 + dvyvz + evzvx + fvxvy + gvx + hvy + ivz + j) = 0
To solve the quadratic equation:
A = awx2 + bwy2 + cwz2 + dwywz + ewzwx + fwxwy
B = 2(avxwx + bvywy + cvzwz) + d(vywz+vzwy) + e(vzwx+vxwz) + f(vxwy+vywx) + gwx + hwy + iwz
C = avx2 + bvy2 + cvz2 + dvyvz + evzvx + fvxvy + gvx + hvy + ivz + j
(4) Solve for t and find point.
P = v + tw
x = vx + t wx
y = vy + t wy
z = vz + t wz
(5) Compute surface normal.
The normal direction aligns with the derivative of:
ax2 + by2 + cz2 + dyz + ezx + fxy + gx + hy + iz + j = 0
N = ( 2ax+ez+fy+g, 2by+dz+fx+h, 2cz+dy+ex+i )
normalize N to unit length
Combining shapes
Boolean combinatorial geometry
Union
Difference
Intersection
double[] X = new double[40];
double[] Y = new double[X.length];
draw() {
r = 0.8;
d = 0.4;
i = 0;
for (int n = 0 ; n < X.length ; n++) {
theta = n * 2 * pi / (X.length-1);
double x = cos(theta);
if (abs(x) > d) {
X[i] = r * x + (x > 0 ? -d : d);
Y[i] = r * sin(theta);
i++;
}
}
draw.setColor(Color.cyan);
draw.fillPolygon(X, Y, i);
draw.setColor(Color.red);
for (int n = 0 ; n < X.length ; n++) {
theta = n * 2 * pi / (X.length-1);
X[n] = r * cos(theta) - d;
Y[n] = r * sin(theta);
}
draw.drawPolygon(X, Y, X.length);
draw.drawText("A", -.9, 0);
draw.setColor(Color.blue);
for (int n = 0 ; n < X.length ; n++) {
theta = n * 2 * pi / (X.length-1);
X[n] = r * cos(theta) + d;
Y[n] = r * sin(theta);
}
draw.drawPolygon(X, Y, X.length);
draw.drawText("B", .9, 0);
draw.setColor(Color.black);
draw.fillArrow(-1.3,-0.8,1.3,0.8,.02);
draw.fillDisk(-0.95,-.58,.05);
draw.fillDisk( 0.95, .58,.05);
draw.fillDisk(-0.37,-.23,.05);
draw.fillDisk( 0.37, .23,.05);
draw.drawText("A", -0.95, -.75);
draw.drawText("B", -0.42, -.43);
draw.drawText("A", 0.39, .47);
draw.drawText("B", 0.92, .79);
draw.drawText("0", -0.95 + .10, -.75 -.05);
draw.drawText("0", -0.42 + .10, -.43 -.05);
draw.drawText("1", 0.39 + .10, .47 -.05);
draw.drawText("1", 0.92 + .10, .79 -.05);
}
Making cool shapes using intersection
Intersection from the perspective of the ray
faintBlack = new Color(0,0,0,64);
draw() {
draw.setColor(faintBlack);
draw.fillBox(-.2, .2, .7, .05);
draw.fillBox( .6, 0, .7, .05);
draw.setColor(Color.black);
draw.fillBox( .2,-.2, .3, .05);
draw.drawText("A", -1.15, .2);
draw.drawText("B", -1.15, 0);
draw.drawText("A\u2229B", -1.15, -.2);
}
AB = [ max(A0,B0) ... min(A1,B1) ]
Union from the perspective of the ray
faintBlack = new Color(0,0,0,64);
draw() {
draw.setColor(faintBlack);
draw.fillBox(-.2, .2, .7, .05);
draw.fillBox( .6, 0, .7, .05);
draw.setColor(Color.black);
draw.fillBox( .2,-.2,1.1, .05);
draw.drawText("A", -1.15, .2);
draw.drawText("B", -1.15, 0);
draw.drawText("A\u222aB", -1.15, -.2);
}
AB = [ min(A0,B0) ... max(A1,B1) ]
Difference from the perspective of the ray
draw() {
draw.setColor(faintBlack);
draw.fillBox(-.2, .2, .7, .05);
draw.fillBox( .6, 0, .7, .05);
draw.setColor(Color.black);
draw.fillBox(-.5,-.2, .4, .05);
draw.fillBox( .9,-.2, .4, .05);
draw.drawText("A", -1.15, .2);
draw.drawText("B", -1.15, 0);
draw.drawText("A-B", -1.15, -.2);
}
Concave shapes
double[] X = {-.5,-.3,.1,.2,-.4,-.8};
double[] Y = { .1,-.3,.2,-.4,-.5,-.3};
double[] A = {-.64,-.40,-0.13,0.15};
draw() {
draw.setColor(faintBlack);
draw.fillPolygon(X, Y, X.length);
draw.setColor(Color.black);
draw.drawPolygon(X, Y, X.length);
draw.draw(-1.1,-.1,A[0],-.1,.02);
draw.draw(A[1],-.1,A[2],-.1,.02);
draw.fillArrow(A[3],-.1,0.9,-.1,.02);
draw.setColor(Color.blue);
draw.fillDisk(A[0],-.1,.03);
draw.fillDisk(A[1],-.1,.03);
draw.fillDisk(A[2],-.1,.03);
draw.fillDisk(A[3],-.1,.03);
}
Generalized boolean
faintBlack = new Color(0,0,0,64);
draw() {
draw.setColor(faintBlack);
draw.fillBox(-.5, .2, .4, .05);
draw.fillBox( .7, .2, .4, .05);
draw.fillBox(-.5, .0, .2, .05);
draw.fillBox(0.7, .0, .2, .05);
draw.setColor(Color.black);
draw.fillBox(-.8,-.2, 0.1, .05);
draw.fillBox(-.2,-.2, 0.1, .05);
draw.fillBox( .4,-.2, 0.1, .05);
draw.fillBox(1.0,-.2, 0.1, .05);
draw.drawText("A", -1.15, .2);
draw.drawText("B", -1.15, 0);
draw.drawText("A-B", -1.15, -.2);
}
Algorithm:
double[] A = {-1.2,-1.0,-0.9,-0.4,-0.2,0.1,0.2,0.5,0.7,1.2};
double[] B = {-1.1,-0.8,-0.5,-0.2,0.1,0.3,0.7,0.9,1.0,1.2};
double[] C = {-1.1,-0.9,-0.5,0.2,0.7,1.0};
double[] D = {-1.0,-0.8,-0.4,0.3,0.9,1.2};
double[] E = {-1.1,-1.0,-0.9,-0.8,-0.5,-0.4,0.2,0.3,0.7,0.9,1.0,1.2};
draw() {
draw.setColor(Color.black);
for (int i = 0 ; i < A.length ; i += 2)
draw.draw(A[i], .2, A[i+1], .2, .05);
for (int i = 0 ; i < B.length ; i += 2)
draw.draw(B[i], 0, B[i+1], 0, .05);
if (mode > 0) {
for (int i = 0 ; i < E.length ; i += 2) {
draw.setColor(Color.blue);
draw.fillBox(E[i], -.2, .015, .05);
draw.setColor(Color.red);
draw.fillBox(E[i+1], -.2, .015, .05);
if (mode >= 2) {
draw.setColor(Color.black);
draw.draw(E[i], -.4, E[i+1], -.4, 0.05);
}
if (mode >= 3) {
a = i==0 ? -1.3 : E[i-1];
b = i-1 >= E.length ? 1.4 : E[i];
draw.draw(a, -.6, b, -.6, 0.05);
}
}
}
if (mode == 3)
draw.draw(1.2, -.6, 1.4, -.6, 0.05);
}
Intersection: two input sequences output sequence
Difference: take negative of input sequence
Union: AB = - ((-A)(-B))
Shading, lighting, materials for ray tracing
Light sources not at infinity
A point source drops off in intensity with distance D from the surface:
Illuminance *= 1 / D2
An extended light source drops off more slowly
Illuminance *= 1 / Dpower, where power 2
Sky and fog
Rays that don't hit anything can return a "sky gradient":
Map the y component of ray direction w to different (r,g,b) values.
You can also add fog.
In fog visibility decreases exponentially with distance
Fog can greatly increase the drama of a scene
Measure distance D ray travels (before it hits something)
Compute visibility v = 2-kD Mix: result = v*rayColor + (1-v)*fogColor
Reflection
new ray
draw() {
draw.drawText("v", -1.05, .45);
draw.drawText("R", 1.05, .45);
draw.fillArrow(-1,.5,0,-.5,.02);
draw.draw(-1.3,-.5,1.3,-.5,.01);
draw.fillArrow(0,-.5,1,.5,.02);
if (highlighting) {
draw.setColor(Color.red);
draw.drawText("v'", 0.05, -.35);
draw.fillArrow(0.1,-.3,0.7,.3,.015);
draw.drawText("w'", 0.3, 0);
}
}
We need to create a secondary ray in R direction, and keep going, recursively.
v S + w
w R
where S is the surface point.
This ray will return a color.
Then we need to mix that color into the result.
Refraction
For glass materials, apply Snell's law, according to index of refraction.
Index of refraction = 1/velocity
sin 1 / sin 2 = n2 / n1
Create new ray:
v S + Q
w Q
Mix in resulting color
Texturing
Procedural texture
noise-based (more on this later)
Texture mapping
We will learn about this at the next lecture.
Applying texture
modifying reflectance values (ambient,diffuse,specular+power)
"bump mapping": changing surface normal
Rendering issues
Ray tracing can be slow.
To speed it up:
Start by looking at only every 44 pixels.
See where there are big changes in depth or color.
In those regions, shoot a ray at every pixel.
To create antialiased edges:
Look for pixels with color very different from neighbors
Shoot 44 rays within that pixel
Sub-pixel offsets: [x + (double)i/4, y + (double)j/4] Average all 16 results to get final color.
HOMEWORK
Your next homework is due on Wednesday May 8 (three weeks from this past lecture). Implement as many feature of ray tracing as you would like. Obviously those of you who are extremely motivated to learn, and consequently implement many features, will receive extra credit.
Among the features you can implement are: light sources not at infinity, transformation, quadratic surfaces (and matrix transformations of them), boolean shape modeling (intersection, union, difference), shadows, reflection, refraction, antialiasing, subsampling for efficiency, procedural texturing.
You can also feel free to surprise me by implementing other features as well.
Because the next assignment is not due until May 8, it would be a very bad idea to wait until very near to that deadline. You should get to work soon, so that you will be able to get a jump on things. If you have any questions, feel free to send me email.
Also, because of a problem with the grading of the "zbuffering with normals rendering" assignment, I am also giving you until May 8 to hand in the "zbuffering with Phong reflectance" assignment.
Notes about the noise function
Java implementation of noise