25:["$","title",null,{"children":"Ray tracing | Tom MacWright | Observable"}] 4c:Tb90,function render() { // This process // is a bit odd, because there's a disconnect between pixels and vectors: // given the left and right, top and bottom rays, the rays we shoot are just // interpolated between them in little increments. // // Starting with the height and width of the scene, the camera's place, // direction, and field of view, we calculate factors that create // `width*height` vectors for each ray // Start by creating a simple vector pointing in the direction the camera is // pointing - a unit vector var eyeVector = Vector.unitVector(Vector.subtract(camera.vector, camera.point)), // and then we'll rotate this by combining it with a version that's turned // 90° right and one that's turned 90° up. Since the [cross product](http://en.wikipedia.org/wiki/Cross_product) // takes two vectors and creates a third that's perpendicular to both, // we use a pure 'UP' vector to turn the camera right, and that 'right' // vector to turn the camera up. vpRight = Vector.unitVector(Vector.crossProduct(eyeVector, Vector.UP)), vpUp = Vector.unitVector(Vector.crossProduct(vpRight, eyeVector)), // The actual ending pixel dimensions of the image aren't important here - // note that `width` and `height` are in pixels, but the numbers we compute // here are just based on the ratio between them, `height/width`, and the // `fieldOfView` of the camera. fovRadians = Math.PI * (camera.fieldOfView / 2) / 180, heightWidthRatio = height / width, halfWidth = Math.tan(fovRadians), halfHeight = heightWidthRatio * halfWidth, camerawidth = halfWidth * 2, cameraheight = halfHeight * 2, pixelWidth = camerawidth / (width - 1), pixelHeight = cameraheight / (height - 1); var index, color; var ray = { point: camera.point }; for (var x = 0; x < width; x++) { for (var y = 0; y < height; y++) { // turn the raw pixel `x` and `y` values into values from -1 to 1 // and use these values to scale the facing-right and facing-up // vectors so that we generate versions of the `eyeVector` that are // skewed in each necessary direction. var xcomp = Vector.scale(vpRight, (x * pixelWidth) - halfWidth), ycomp = Vector.scale(vpUp, (y * pixelHeight) - halfHeight); ray.vector = Vector.unitVector(Vector.add3(eyeVector, xcomp, ycomp)); // use the vector generated to raytrace the scene, returning a color // as a `{x, y, z}` vector of RGB values color = trace(ray, 0); index = (x * 4) + (y * width * 4), data.data[index + 0] = color.x; data.data[index + 1] = color.y; data.data[index + 2] = color.z; data.data[index + 3] = 255; } } // Now that each ray has returned and populated the `data` array with // correctly lit colors, fill the canvas with the generated data. ctx.putImageData(data, 0, 0); }4d:Tf10,function trace(ray, depth) { // This is a recursive method: if we hit something that's reflective, // then the call to `surface()` at the bottom will return here and try // to find what the ray reflected into. Since this could easily go // on forever, first check that we haven't gone more than three bounces // into a reflection. if (depth > reflectionDepth) return; var distObject = intersectScene(ray); // If we don't hit anything, fill this pixel with the background color - // in this case, white. if (distObject[0] === Infinity) { return backgroundColorVector; } var dist = distObject[0], object = distObject[1]; // The `pointAtTime` is another way of saying the 'intersection point' // of this ray into this object. We compute this by simply taking // the direction of the ray and making it as long as the distance // returned by the intersection check. var pointAtTime = Vector.add(ray.point, Vector.scale(ray.vector, dist)); function surface(ray, object, pointAtTime, normal, depth) { var b = object.color, c = Vector.ZERO, lambertAmount = 0; // **[Lambert shading](http://en.wikipedia.org/wiki/Lambertian_reflectance)** // is our pretty shading, which shows gradations from the most lit point on // the object to the least. if (object.lambert) { for (var i = 0; i < lights.length; i++) { var lightPoint = lights[0]; // First: can we see the light? If not, this is a shadowy area // and it gets no light from the lambert shading process. if (!isLightVisible(pointAtTime, lightPoint)) continue; // Otherwise, calculate the lambertian reflectance, which // essentially is a 'diffuse' lighting system - direct light // is bright, and from there, less direct light is gradually, // beautifully, less light. var contribution = Vector.dotProduct(Vector.unitVector( Vector.subtract(lightPoint, pointAtTime)), normal); // sometimes this formula can return negatives, so we check: // we only want positive values for lighting. if (contribution > 0) lambertAmount += contribution; } } // **[Specular](https://en.wikipedia.org/wiki/Specular_reflection)** is a fancy word for 'reflective': rays that hit objects // with specular surfaces bounce off and acquire the colors of other objects // they bounce into. if (object.specular) { // This is basically the same thing as what we did in `render()`, just // instead of looking from the viewpoint of the camera, we're looking // from a point on the surface of a shiny object, seeing what it sees // and making that part of a reflection. var reflectedRay = { point: pointAtTime, vector: Vector.reflectThrough(ray.vector, normal) }; var reflectedColor = trace(reflectedRay, ++depth); if (reflectedColor) { c = Vector.add(c, Vector.scale(reflectedColor, object.specular)); } } // lambert should never 'blow out' the lighting of an object, // even if the ray bounces between a lot of things and hits lights lambertAmount = Math.min(1, lambertAmount); // **Ambient** colors shine bright regardless of whether there's a light visible - // a circle with a totally ambient blue color will always just be a flat blue // circle. return Vector.add3(c, Vector.scale(b, lambertAmount * object.lambert), Vector.scale(b, object.ambient)); } return surface(ray, object, pointAtTime, sphereNormal(object, pointAtTime), depth); }4e:T528,function sphereIntersection(sphere, ray) { var eye_to_center = Vector.subtract(sphere.point, ray.point), // picture a triangle with one side going straight from the camera point // to the center of the sphere, another side being the vector. // the final side is a right angle. // // This equation first figures out the length of the vector side v = Vector.dotProduct(eye_to_center, ray.vector), // then the length of the straight from the camera to the center // of the sphere eoDot = Vector.dotProduct(eye_to_center, eye_to_center), // and compute a segment from the right angle of the triangle to a point // on the `v` line that also intersects the circle discriminant = (sphere.radius * sphere.radius) - eoDot + (v * v); // If the discriminant is negative, that means that the sphere hasn't // been hit by the ray if (discriminant < 0) { return; } else { // otherwise, we return the distance from the camera point to the sphere // `Math.sqrt(dotProduct(a, a))` is the length of a vector, so // `v - Math.sqrt(discriminant)` means the length of the the vector // just from the camera to the intersection point. return v - Math.sqrt(discriminant); } }4f:Tb74,Vector = { let Vector = {}; // # Constants Vector.UP = { x: 0, y: 1, z: 0 }; Vector.ZERO = { x: 0, y: 0, z: 0 }; Vector.WHITE = { x: 255, y: 255, z: 255 }; Vector.ZEROcp = function() { return { x: 0, y: 0, z: 0 }; }; // # Operations // // ## [Dot Product](https://en.wikipedia.org/wiki/Dot_product) // is different than the rest of these since it takes two vectors but // returns a single number value. Vector.dotProduct = function(a, b) { return (a.x * b.x) + (a.y * b.y) + (a.z * b.z); }; // ## [Cross Product](https://en.wikipedia.org/wiki/Cross_product) // // generates a new vector that's perpendicular to both of the vectors // given. Vector.crossProduct = function(a, b) { return { x: (a.y * b.z) - (a.z * b.y), y: (a.z * b.x) - (a.x * b.z), z: (a.x * b.y) - (a.y * b.x) }; }; // Enlongate or shrink a vector by a factor of `t` Vector.scale = function(a, t) { return { x: a.x * t, y: a.y * t, z: a.z * t }; }; // ## [Unit Vector](http://en.wikipedia.org/wiki/Unit_vector) // // Turn any vector into a vector that has a magnitude of 1. // // If you consider that a [unit sphere](http://en.wikipedia.org/wiki/Unit_sphere) // is a sphere with a radius of 1, a unit vector is like a vector from the // center point (0, 0, 0) to any point on its surface. Vector.unitVector = function(a) { return Vector.scale(a, 1 / Vector.length(a)); }; // Add two vectors to each other, by simply combining each // of their components Vector.add = function(a, b) { return { x: a.x + b.x, y: a.y + b.y, z: a.z + b.z }; }; // A version of `add` that adds three vectors at the same time. While // it's possible to write a clever version of `Vector.add` that takes // any number of arguments, it's not fast, so we're keeping it simple and // just making two versions. Vector.add3 = function(a, b, c) { return { x: a.x + b.x + c.x, y: a.y + b.y + c.y, z: a.z + b.z + c.z }; }; // Subtract one vector from another, by subtracting each component Vector.subtract = function(a, b) { return { x: a.x - b.x, y: a.y - b.y, z: a.z - b.z }; }; // Length, or magnitude, measured by [Euclidean norm](https://en.wikipedia.org/wiki/Euclidean_vector#Length) Vector.length = function(a) { return Math.sqrt(Vector.dotProduct(a, a)); }; // Given a vector `a`, which is a point in space, and a `normal`, which is // the angle the point hits a surface, returna new vector that is reflect // off of that surface Vector.reflectThrough = function(a, normal) { var d = Vector.scale(normal, Vector.dotProduct(a, normal)); return Vector.subtract(Vector.scale(d, 2), a); }; return Vector; }50:[] 48:{"id":"498f1a2859a5a9f5","slug":"ray-tracing","title":"Ray tracing","thumbnail":"a8b0a9c56c842e1f00791ba43a1f717f9fafcad741070b1a03f0b61306853b85","access_level":"public","create_time":"$D2018-01-17T21:44:52.827Z","update_time":"$D2018-01-22T18:39:42.218Z","view_time":null,"first_public_time":"$D2018-01-22T18:37:35.941Z","has_unpublished_edits":null,"fork":false,"stars":4,"starred":false,"owner":{"type":"team","id":"b47c3705cfcd7c1b","login":"tmcw","name":"Tom MacWright","avatar_url":"https://avatars-next.observableusercontent.com/669bdd774da8a1b9c1b7706ecbc1ea5136b9932c3d5e86b753aa5a098005f674","tier":"starter_2024","bio":"hi!","followed_by_you":false,"follows_you":false},"version":183,"publish_version":183,"role":null,"authored":false,"authors":[{"type":"individual","id":"0bf14b8d9c6eb88a","login":"tmcw","name":"Tom MacWright","avatar_url":"https://avatars-next.observableusercontent.com/669bdd774da8a1b9c1b7706ecbc1ea5136b9932c3d5e86b753aa5a098005f674","tier":null,"bio":"hi!","followed_by_you":false,"follows_you":false}],"members":[{"type":"individual","id":"0bf14b8d9c6eb88a","login":"tmcw","name":"Tom MacWright","avatar_url":"https://avatars-next.observableusercontent.com/669bdd774da8a1b9c1b7706ecbc1ea5136b9932c3d5e86b753aa5a098005f674","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":2,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Ray tracing","cells":[{"id":0,"value":"md`# Ray tracing`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":99,"value":"c = {\n let c = DOM.canvas(width, width / 1.5);\n return c;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":147,"value":"viewof randomize = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":149,"value":"viewof numberOfObjects = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":170,"value":"viewof reflectionDepth = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":174,"value":"viewof fieldOfView = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":154,"value":"viewof backgroundColor = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":156,"value":"backgroundColor","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":158,"value":"backgroundColorVector = {\n let hex = backgroundColor.substring(1);\n return {\n x: parseInt(hex.substring(0, 2), 16),\n y: parseInt(hex.substring(2, 4), 16),\n z: parseInt(hex.substring(4, 6), 16)\n };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":107,"value":"ctx = c.getContext('2d')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":109,"value":"data = ctx.getImageData(0, 0, width, height)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":111,"value":"render()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"md`We need to define three different kinds of things in 3D space:\na **camera** from which we cast rays into the scene, **objects**\nthat can be hit by those rays and are drawn into the scene, and\n**lights** that change the color of rays, by extension coloring objects.\n\nIn this case, we define these objects as simple objects with vectors defined as \\`{x, y, z}\\` objects.\n\n## The Camera\n\nOur camera is pretty simple: it's a point in space, where you can imagine\nthat the camera 'sits', a \\`fieldOfView\\`, which is the angle from the right\nto the left side of its frame, and a \\`vector\\` which determines what\nangle it points in.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"camera = ({\n point: {\n x: 0,\n y: 1.8,\n z: 10\n },\n fieldOfView,\n vector: {\n x: 0,\n y: 3,\n z: 0\n }\n})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"md`## Lights\n\nLights are defined only as points in space - surfaces that have lambert\nshading will be affected by any visible lights.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":14,"value":"lights = [{\n x: -30,\n y: -10,\n z: 20\n}]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":20,"value":"md`## Objects\n\nThis raytracer handles sphere objects, with any color, position, radius,\nand surface properties.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":16,"value":"objects = {\n randomize;\n let objArray = [];\n for (let i = 0; i < numberOfObjects; i++) {\n objArray.push({\n type: 'sphere',\n point: {\n x: (Math.random() - 0.5) * 5,\n y: (Math.random() - 0.5) * 9,\n z: (Math.random() - 0.5) * 5\n },\n color: {\n x: Math.random() * 255,\n y: Math.random() * 255,\n z: Math.random() * 255\n },\n specular: Math.random(),\n lambert: Math.random(),\n ambient: Math.random(),\n radius: (0.5 + Math.random()) * 0.5\n });\n }\n return objArray;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":25,"value":"md`# Throwing Rays\n\nThis is one part where we can't follow nature exactly: technically photons\ncome out of lights, bounce off of objects, and then some hit the 'eye'\nand many don't. Simulating this - sending rays in all directions out of\neach light and most not having any real effect - would be too inefficient.\n\nLuckily, the reverse is more efficient and has practically the same result -\ninstead of rays going 'from' lights to the eye, we follow rays from the eye\nand see if they end up hitting any features and lights on their travels.\n\nFor each pixel in the canvas, there needs to be at least one ray of light\nthat determines its color by bouncing through the scene.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":27,"value":"$4c","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":33,"value":"md`# Trace\n\nGiven a ray, shoot it until it hits an object and return that object's color,\nor \\`Vector.WHITE\\` if no object is found. This is the main function that's\ncalled in order to draw the image, and it recurses into itself if rays\nreflect off of objects and acquire more color.\n\n## Surface\n\nIf \\`trace()\\` determines that a ray intersected with an object, \\`surface\\`\ndecides what color it acquires from the interaction.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"$4d","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":38,"value":"md`# Detecting collisions against all objects\n\nGiven a ray, let's figure out whether it hits anything, and if so,\nwhat's the closest thing it hits.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":40,"value":"function intersectScene(ray) {\n // The base case is that it hits nothing, and travels for `Infinity`\n var closest = [Infinity, null];\n // But for each object, we check whether it has any intersection,\n // and compare that intersection - is it closer than `Infinity` at first,\n // and then is it closer than other objects that have been hit?\n for (var i = 0; i < objects.length; i++) {\n var object = objects[i],\n dist = sphereIntersection(object, ray);\n if (dist !== undefined && dist < closest[0]) {\n closest = [dist, object];\n }\n }\n return closest;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":43,"value":"md`## Detecting collisions against a sphere\n\nSpheres are one of the simplest objects for rays to interact with, since\nthe geometrical math for finding intersections and reflections with them\nis pretty straightforward.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":45,"value":"$4e","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":48,"value":"md`A normal is, at each point on the surface of a sphere or some other object,\na vector that's perpendicular to the surface and radiates outward. We need\nto know this so that we can calculate the way that a ray reflects off of\na sphere.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":50,"value":"function sphereNormal(sphere, pos) {\n return Vector.unitVector(\n Vector.subtract(pos, sphere.point));\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":63,"value":"md`Check whether a light is visible from some point on the surface of something.\nNote that there might be an intersection here, which is tricky - but if it's\ntiny, it's actually an intersection with the object we're trying to decide\nthe surface of. That's why we check for \\`> -0.005\\` at the end.\n\nThis is the part that makes objects cast shadows on each other: from here\nwe'd check to see if the area in a shadowy spot can 'see' a light, and when\nthis returns \\`false\\`, we make the area shadowy.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":65,"value":"function isLightVisible(pt, light) {\n var distObject = intersectScene({\n point: pt,\n vector: Vector.unitVector(Vector.subtract(pt, light))\n });\n return distObject[0] > -0.005;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"md`# Vector Operations\n\nThese are general-purpose functions that deal with vectors - in this case,\nthree-dimensional vectors represented as objects in the form\n\n { x, y, z }\n\nSince we're not using traditional object oriented techniques, these\nfunctions take and return that sort of logic-less object, so you'll see\n\\`add(a, b)\\` rather than \\`a.add(b)\\`.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2,"value":"$4f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":31,"value":"height = width / 1.5","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W50","stdlib":"1"}} 24:null