2e:null 2f:["$","title",null,{"children":"Modelling: Axis-Aligned Bounding Boxes (AABBs) | Introduction to Computer Graphics MSState | Observable"}] 34:T482,{ const id = DOM.uid("plane"); const id2 = DOM.uid("arrow"); return html`

An axis-aligned box.

` }35:T6eb,${tex.block`\begin{aligned} t_l &= \frac{\left(\left(\textcolor{${ray_color}}{\textcolor{${object_color}}{\bullet \mathrm{q}_l}-\bullet\mathrm{r_0}}\right)\cdot\textcolor{${object_color}}{\hat{\mathbf{n}_l}}\right)}{\textcolor{${ray_color}}{\hat{\mathbf{d}}}\cdot\textcolor{${object_color}}{\hat{\mathbf{n}_l}}}\\ t_r &= \frac{\left(\left(\textcolor{${ray_color}}{\textcolor{${object_color}}{\bullet \mathrm{q}_r}-\bullet\mathrm{r_0}}\right)\cdot\textcolor{${object_color}}{\hat{\mathbf{n}_r}}\right)}{\textcolor{${ray_color}}{\hat{\mathbf{d}}}\cdot\textcolor{${object_color}}{\hat{\mathbf{n}_r}}}\\ t_b &= \frac{\left(\left(\textcolor{${ray_color}}{\textcolor{${object_color}}{\bullet \mathrm{q}_b}-\bullet\mathrm{r_0}}\right)\cdot\textcolor{${object_color}}{\hat{\mathbf{n}_b}}\right)}{\textcolor{${ray_color}}{\hat{\mathbf{d}}}\cdot\textcolor{${object_color}}{\hat{\mathbf{n}_b}}}\\ t_t &= \frac{\left(\left(\textcolor{${ray_color}}{\textcolor{${object_color}}{\bullet \mathrm{q}_t}-\bullet\mathrm{r_0}}\right)\cdot\textcolor{${object_color}}{\hat{\mathbf{n}_t}}\right)}{\textcolor{${ray_color}}{\hat{\mathbf{d}}}\cdot\textcolor{${object_color}}{\hat{\mathbf{n}_t}}}\\ t_n &= \frac{\left(\left(\textcolor{${ray_color}}{\textcolor{${object_color}}{\bullet \mathrm{q}_n}-\bullet\mathrm{r_0}}\right)\cdot\textcolor{${object_color}}{\hat{\mathbf{n}_n}}\right)}{\textcolor{${ray_color}}{\hat{\mathbf{d}}}\cdot\textcolor{${object_color}}{\hat{\mathbf{n}_n}}}\\ t_f &= \frac{\left(\left(\textcolor{${ray_color}}{\textcolor{${object_color}}{\bullet \mathrm{q}_f}-\bullet\mathrm{r_0}}\right)\cdot\textcolor{${object_color}}{\hat{\mathbf{n}_f}}\right)}{\textcolor{${ray_color}}{\hat{\mathbf{d}}}\cdot\textcolor{${object_color}}{\hat{\mathbf{n}_f}}}\\ \end{aligned}`}36:T16cd,{ const id = DOM.uid("ray"); const id2 = DOM.uid("box"); let origin = [0.125*ewidth, 128] let lb = [0.325*ewidth, 64]; let rt = [0.675*ewidth, 192]; let offset_len = Math.max(30,0.1*ewidth); const offset = ([x,y], d=offset_len) => add(origin, norm(sub([x,y],origin)).map(i=>i*d)) let target = offset([0.4*ewidth, 69]); let t_lb = intersect_ray_point(origin,norm(sub(target,origin)),lb); let t_rt = intersect_ray_point(origin,norm(sub(target,origin)),rt); let t_mins = [Math.min(t_lb[0], t_rt[0]), Math.min(t_lb[1], t_rt[1])]; let t_maxes = [Math.max(t_lb[0], t_rt[0]), Math.max(t_lb[1], t_rt[1])]; let t0 = Math.max(t_mins[0],t_mins[1]); let t1 = Math.min(t_maxes[0],t_maxes[1]); viewof t.value = `[${offset(target, t0).map(x => Math.round(x))}]` let fig= html`

Side view of the box. Drag point and ray to see possible intersections.

`; d3.select(fig).selectAll(".draggable").call(d3.drag() .on("drag", dragged)); function dragged(e) { if(e.x < 0 || e.x >= ewidth || e.y < 0 || e.y >= 256) return; let ele = d3.select(this); if(ele.classed("origin")) { // Dragging origin target = add(target, sub([e.x, e.y], origin)); origin = [e.x, e.y]; viewof origin.value = `[${origin.map((x,i) => Math.round((i%2?(256-x):x)))}]`; } else { // Dragging line target = [e.x, e.y]; viewof direction.value = `[${norm(sub(target,origin)).map((x,i) => x.toFixed(4) * (i%2==0?1:-1))}]`; } if(len(sub(origin, target)) < 0.001) return; // Too close target = offset(target); let far = offset(target,ewidth); d3.select(fig).selectAll("line.draggable") .attr('x1', origin[0]).attr('y1', origin[1]) .attr('x2', target[0]).attr('y2', target[1]); d3.select(fig).selectAll("line.ray") .attr('x1', target[0]).attr('y1', target[1]) .attr('x2', far[0]).attr('y2', far[1]); d3.select(fig).selectAll(".origin") .attr('cx', origin[0]).attr('cy', origin[1]); let t_lb = intersect_ray_point(origin,norm(sub(target,origin)),lb); let t_rt = intersect_ray_point(origin,norm(sub(target,origin)),rt); let t_mins = [Math.min(t_lb[0], t_rt[0]), Math.min(t_lb[1], t_rt[1])]; let t_maxes = [Math.max(t_lb[0], t_rt[0]), Math.max(t_lb[1], t_rt[1])]; var t0 = Math.max(t_mins[0],t_mins[1]); let t1 = Math.min(t_maxes[0],t_maxes[1]); if(t0 > t1 || t1 < 0) {t0 = NaN;} else if(t0 < 0) {t0 = t1;} viewof t.value =!Number.isNaN(t0) ? `[${offset(target, t0).map(x => Math.round(x))}]` : "undefined"; if((!Number.isFinite(t0) && !Number.isNaN(t0))|| offset(target, t0)[0] < 0 || offset(target, t0)[0] > ewidth || offset(target, t0)[1] < 0 || offset(target, t0)[1] > 256) { viewof t.value = "offscreen"; t0 = NaN; } d3.select(fig).select("#t0").attr("visibility", !Number.isNaN(t0) ? "visible" : "hidden") .attr("cx", !Number.isNaN(t0) ? offset(target, t0)[0]: -1) .attr("cy", !Number.isNaN(t0) ? offset(target, t0)[1]: -1) d3.select(fig).select("#t1").attr("visibility", t0 != t1 ? "visible" : "hidden") .attr("cx", !Number.isNaN(t0) ? offset(target, t1)[0]: -1) .attr("cy", !Number.isNaN(t0) ? offset(target, t1)[1]: -1) } return fig; }37:T15f6,{ const id = DOM.uid("plane"); const id2 = DOM.uid("arrow"); let origin = [0.125*ewidth, 112] let lb = [0.325*ewidth, 64]; let rt = [0.675*ewidth, 192]; let avg = add(lb,rt).map(x=>x/2); let offset_len = Math.max(30,0.1*ewidth); const offset = ([x,y], d=offset_len) => add(origin, norm(sub([x,y],origin)).map(i=>i*d)) let target = offset([0.2*ewidth, 112],0.2*ewidth); const fig = html`

The zones; zones which are symmetric are colored the same. Drag point ${tex`\color{#663399}\bullet`} to see its positive quadrant counterpart.

`; d3.select(fig).selectAll(".draggable").call(d3.drag() .on("drag", dragged)); function dragged(e) { if(e.x < 0 || e.x >= ewidth || e.y < 0 || e.y >= 256) return; let ele = d3.select(this); // Dragging origin origin = [e.x, e.y]; if(e.x <= lb[0] && e.y <= lb[1]) target = lb; else if(e.x <= lb[0] && e.y >= rt[1]) target = [lb[0], rt[1]]; else if(e.x >= rt[0] && e.y <= lb[1]) target = [rt[0], lb[1]]; else if(e.x >= rt[0] && e.y >= rt[1]) target = rt; else if(e.x < lb[0] && e.y > lb[1] && e.y <= rt[1]) target = [lb[0], e.y]; else if(e.x > rt[0] && e.y > lb[1] && e.y <= rt[1]) target = [rt[0], e.y]; else if(e.y < lb[1] && e.x > lb[0] && e.x <= rt[0]) target = [e.x, lb[1]]; else if(e.y > rt[1] && e.x > lb[0] && e.x <= rt[0]) target = [e.x, rt[1]]; else { let dlb = sub(lb,[e.x,e.y]).map(Math.abs); let drt = sub(rt,[e.x,e.y]).map(Math.abs); if(dlb[0] < dlb[1] && dlb[0] < drt[0] && dlb[0] < drt[1]) target = [lb[0], e.y]; else if(drt[0] < dlb[1] && drt[0] < dlb[0] && drt[0] < drt[1]) target = [rt[0], e.y]; else if(dlb[1] < dlb[0] && dlb[1] < drt[0] && dlb[1] < drt[1]) target = [e.x, lb[1]]; else if(drt[1] < dlb[0] && drt[1] < drt[0] && drt[1] < dlb[1]) target = [e.x, rt[1]]; } let t0 = sdf(origin,lb, rt); d3.select(fig).selectAll("line.draggable") .attr('x1', origin[0]).attr('y1', origin[1]) .attr('x2', target[0]).attr('y2', target[1]); d3.select(fig).selectAll(".origin") .attr('cx', origin[0]).attr('cy', origin[1]); d3.select(fig).selectAll("line.mirror") .attr('x1', Math.abs(origin[0]-avg[0])+avg[0]).attr('y1', avg[1]-Math.abs(origin[1]-avg[1])) .attr('x2', Math.abs(target[0]-avg[0])+avg[0]).attr('y2', avg[1]-Math.abs(target[1]-avg[1])); d3.select(fig).selectAll("circle.mirror") .attr('cx', Math.abs(origin[0]-avg[0])+avg[0]).attr('cy', avg[1]-Math.abs(origin[1]-avg[1])); } return fig; }38:T42c,Considering the 2D case, we have four cases to consider 1. ${tex`\bullet \mathrm{p}''_x > \textcolor{${object_color}}{\Delta \mathbf{q}_{\frac{1}{2}\color{black}x}}, \mathrm{p}''_y < \textcolor{${object_color}}{\Delta \mathbf{q}_{\frac{1}{2}\color{black}y}}`}: The point is outside the right plane, but inside the top plane. 2. ${tex`\bullet \mathrm{p}''_x < \textcolor{${object_color}}{\Delta \mathbf{q}_{\frac{1}{2}\color{black}x}}, \mathrm{p}''_y > \textcolor{${object_color}}{\Delta \mathbf{q}_{\frac{1}{2}\color{black}y}}`}: The point is inside the right plane, but outside the top plane. 3. ${tex`\bullet \mathrm{p}''_x > \textcolor{${object_color}}{\Delta \mathbf{q}_{\frac{1}{2}\color{black}x}}, \mathrm{p}''_y > \textcolor{${object_color}}{\Delta \mathbf{q}_{\frac{1}{2}\color{black}y}}`}: The point is outside both planes. 4. ${tex`\bullet \mathrm{p}''_x < \textcolor{${object_color}}{\Delta \mathbf{q}_{\frac{1}{2}\color{black}x}}, \mathrm{p}''_y < \textcolor{${object_color}}{\Delta \mathbf{q}_{\frac{1}{2}\color{black}y}}`}: The point is inside the box. 39:T4d1,where ${tex`\textcolor{${object_color}}{\Delta \mathbf{q}_\frac{1}{2}}=\frac{1}{2}\left(\textcolor{${object_color}}{\bullet \mathrm{q}_{rt}} - \textcolor{${object_color}}{\bullet \mathrm{q}_{lb}}\right)`} is the hemilength of the box—half its width and height (and depth in 3D). We have four corresponding signed distances 1. ${tex`\operatorname{sdf}\left(\bullet \mathrm{p}''\right) = \bullet \mathrm{p}''_x - \textcolor{${object_color}}{\Delta \mathbf{q}_{\frac{1}{2}\color{black}x}}`} 2. ${tex`\operatorname{sdf}\left(\bullet \mathrm{p}''\right) = \bullet \mathrm{p}''_y - \textcolor{${object_color}}{\Delta \mathbf{q}_{\frac{1}{2}\color{black}y}}`} 3. ${tex`\operatorname{sdf}\left(\bullet \mathrm{p}''\right) = \left\|\bullet \mathrm{p}'' - \textcolor{${object_color}}{\Delta \mathbf{q}_\frac{1}{2}}\right\|=\sqrt{\left(\bullet \mathrm{p}''_x - \textcolor{${object_color}}{\Delta \mathbf{q}_{\frac{1}{2}\color{black}x}}\right)^2+\left(\bullet \mathrm{p}''_y - \textcolor{${object_color}}{\Delta \mathbf{q}_{\frac{1}{2}\color{black}y}}\right)^2}`} 4. ${tex`\operatorname{sdf}\left(\bullet \mathrm{p}''\right) = -\left\|\bullet \mathrm{p}'' - \textcolor{${object_color}}{\Delta \mathbf{q}_\frac{1}{2}}\right\|`} 3a:T274c,{ const id = DOM.uid("ray"); const id2 = DOM.uid("box"); let origin = [0.125*ewidth, 128] let lb = [0.325*ewidth, 64]; let rt = [0.675*ewidth, 192]; let offset_len = Math.max(30,0.1*ewidth); const offset = ([x,y], d=offset_len) => add(origin, norm(sub([x,y],origin)).map(i=>i*d)) let target = offset([0.4*ewidth, 69]); var sdist = sdf(origin, lb, rt); let step = 0; let prev_step = 0; //viewof t.value = `[${offset(target, t0).map(x => Math.round(x))}]` let fig= html`

Side view of the box. Drag point and ray to see possible intersections.

`; d3.select(fig).select("#dist") .interrupt("march") .transition("march") .ease(d3.easeCubic) .on("start", function march(){ let loc = offset(target,step); if(loc[0] < 0 || loc[0] >= ewidth || loc[1] < 0 || loc[1] >= 256) { step = 0; loc = origin; } const distance = sdf(loc, lb, rt); prev_step = step; if(distance > 1 || distance < -1) { step += Math.abs(distance); viewof march_distance.value = `${distance}`; } else { viewof march_distance.value = `${distance}`; viewof march_intersection.value = `[${loc.map(x=>x.toFixed(4))}]`; step = 0; loc = origin; } var dir; let sloc = offset(target,prev_step); if(sloc[0] <= lb[0] && sloc[1] <= lb[1]) { dir = sub(lb,sloc); } else if(sloc[0] <= lb[0] && sloc[1] >= rt[1]) { dir = sub([lb[0], rt[1]],sloc); } else if(sloc[0] >= rt[0] && sloc[1] <= lb[1]) { dir = sub([rt[0], lb[1]],sloc); } else if(sloc[0] >= rt[0] && sloc[1] >= rt[1]) { dir = sub(rt,sloc); } else if(sloc[0] < lb[0] && sloc[1] > lb[1] && sloc[1] <= rt[1]) { dir = sub([lb[0], sloc[1]],sloc); } else if(sloc[0] > rt[0] && sloc[1] > lb[1] && sloc[1] <= rt[1]) { dir = sub([rt[0], sloc[1]],sloc); } else if(sloc[1] < lb[1] && sloc[0] > lb[0] && sloc[0] <= rt[0]) { dir = sub([sloc[0], lb[1]],sloc); } else if(sloc[1] > rt[1] && sloc[0] > lb[0] && sloc[0] <= rt[0]) { dir = sub([sloc[0], rt[1]],sloc); } else { let dlb = sub(lb,[sloc[0],sloc[1]]).map(Math.abs); let drt = sub(rt,[sloc[0],sloc[1]]).map(Math.abs); if(dlb[0] < dlb[1] && dlb[0] < drt[0] && dlb[0] < drt[1]) { dir = sub([lb[0],sloc[1]],sloc); } else if(drt[0] < dlb[1] && drt[0] < dlb[0] && drt[0] < drt[1]) { dir = sub([rt[0], sloc[1]],sloc); } else if(dlb[1] < dlb[0] && dlb[1] < drt[0] && dlb[1] < drt[1]) { dir = sub([sloc[0], lb[1]],sloc); } else if(drt[1] < dlb[0] && drt[1] < drt[0] && drt[1] < dlb[1]) { dir = sub([sloc[0], rt[1]],sloc); } } let start = ray(sloc,[-dir[1],dir[0]], ewidth); let end = ray(sloc,[dir[1],-dir[0]], ewidth); d3.active(this, "march") .attr("x1",start[0]) .attr("y1",start[1]) .attr("x2",end[0]) .attr("y2",end[1]) .attr("stroke", d3.interpolateGreys(1-distance/(0.5*ewidth-60))) .transition("march") .delay(1000) .on("start", march); }); d3.select(fig).select("#pos") .transition("march") .ease(d3.easeLinear) .on("start", function march(){ let loc = offset(target,prev_step); d3.active(this, "march") .attr("cx", loc[0]).attr("cy", loc[1]) .attr("fill", d3.interpolateGreys(1-sdf(origin, lb, rt)/(0.5*ewidth-60))) .transition("march") .delay(1000) .on("start", march); }); invalidation.then(() => d3.select(fig).selectAll("*").interrupt("march")); d3.select(fig).selectAll(".draggable").call(d3.drag() .on("start", start).on("drag", dragged).on("end", update)); function start() { d3.select(fig).selectAll(".anim") .attr("visibility", "hidden"); } function dragged(e) { if(e.x < 0 || e.x >= ewidth || e.y < 0 || e.y >= 256) return; let ele = d3.select(this); if(ele.classed("origin")) { // Dragging origin target = add(target, sub([e.x, e.y], origin)); origin = [e.x, e.y]; viewof march_origin.value = `[${origin.map((x,i) => Math.round((i%2?(256-x):x)))}]`; } else { // Dragging line target = [e.x, e.y]; viewof march_direction.value = `[${norm(sub(target,origin)).map((x,i) => x.toFixed(4) * (i%2==0?1:-1))}]`; } if(len(sub(origin, target)) < 0.001) return; // Too close target = offset(target); let far = offset(target,ewidth); d3.select(fig).selectAll("line.ray") .attr('x1', origin[0]).attr('y1', origin[1]) .attr('x2', target[0]).attr('y2', target[1]); d3.select(fig).selectAll("line.projection") .attr('x1', target[0]).attr('y1', target[1]) .attr('x2', far[0]).attr('y2', far[1]); d3.select(fig).selectAll(".origin") .attr('cx', origin[0]).attr('cy', origin[1]); } function update() { const distance = sdf(origin, lb, rt); var dir; if(origin[0] <= lb[0] && origin[1] <= lb[1]) { dir = sub(lb,origin); } else if(origin[0] <= lb[0] && origin[1] >= rt[1]) { dir = sub([lb[0], rt[1]],origin); } else if(origin[0] >= rt[0] && origin[1] <= lb[1]) { dir = sub([rt[0], lb[1]],origin); } else if(origin[0] >= rt[0] && origin[1] >= rt[1]) { dir = sub(rt,origin); } else if(origin[0] < lb[0] && origin[1] > lb[1] && origin[1] <= rt[1]) { dir = sub([lb[0], origin[1]],origin); } else if(origin[0] > rt[0] && origin[1] > lb[1] && origin[1] <= rt[1]) { dir = sub([rt[0], origin[1]],origin); } else if(origin[1] < lb[1] && origin[0] > lb[0] && origin[0] <= rt[0]) { dir = sub([origin[0], lb[1]],origin); } else if(origin[1] > rt[1] && origin[0] > lb[0] && origin[0] <= rt[0]) { dir = sub([origin[0], rt[1]],origin); } else { let dlb = sub(lb,[origin[0],origin[1]]).map(Math.abs); let drt = sub(rt,[origin[0],origin[1]]).map(Math.abs); if(dlb[0] < dlb[1] && dlb[0] < drt[0] && dlb[0] < drt[1]) { dir = sub([lb[0],origin[1]],origin); } else if(drt[0] < dlb[1] && drt[0] < dlb[0] && drt[0] < drt[1]) { dir = sub(target = [rt[0], origin[1]],origin); } else if(dlb[1] < dlb[0] && dlb[1] < drt[0] && dlb[1] < drt[1]) { dir = sub([origin[0], lb[1]],origin); } else if(drt[1] < dlb[0] && drt[1] < drt[0] && drt[1] < dlb[1]) { dir = sub([origin[0], rt[1]],origin); } } let start = ray(origin,[-dir[1],dir[0]], ewidth); let end = ray(origin,[dir[1],-dir[0]], ewidth); viewof march_distance.value = `${distance}`; viewof march_intersection.value = "undefined"; d3.select(fig).selectAll("#dist") .attr("x1", start[0]) .attr("y1", start[1]) .attr("x2", end[0]) .attr("y2", end[1]) .attr("stroke", d3.interpolatePurples(1-distance/(0.5*ewidth-60))) .attr("visibility", "visible"); d3.select(fig).selectAll("#pos") .attr("cx", origin[0]).attr("cy", origin[1]) .attr("fill", d3.interpolatePurples(1-distance/(0.5*ewidth-60))) .attr("visibility", "visible"); step = 0; } return fig; }3b:[] 32:{"id":"80f8c2f4adeb0fa5","slug":"modelling-axis-aligned-bounding-boxes-aabbs","title":"Modelling: Axis-Aligned Bounding Boxes (AABBs)","thumbnail":"c166c6b9e626f9925f6e96fdf06c2878ca9827605cecec49fba2fef93bec163c","access_level":"public","create_time":"$D2025-09-13T04:07:44.641Z","update_time":"$D2025-09-17T17:51:36.693Z","view_time":null,"first_public_time":"$D2025-09-17T17:39:42.289Z","has_unpublished_edits":null,"fork":{"id":"1dacf8b8806ceff6","slug":"modelling-planes","title":"Modelling: Planes","owner":{"id":"7c0dab8b587e2ed2","login":"cse4413msstate","name":"Introduction to Computer Graphics MSState"}},"stars":0,"starred":false,"owner":{"type":"team","id":"7c0dab8b587e2ed2","login":"cse4413msstate","name":"Introduction to Computer Graphics MSState","avatar_url":"https://avatars-next.observableusercontent.com/343b1e48cbb2480c08063f107b4631944c5bb97a5258576dd939a5be852f30bc","tier":"pro_2024"},"version":928,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"e83a97795d4ad3a2","login":"infowantstobeseen","name":"T.J. Jankun-Kelly","avatar_url":"https://avatars-next.observableusercontent.com/df9d7f817f9ad92a763b56ee2e891ca0716a6c2f6c398811547f89f0448fa181","tier":null}],"members":[{"type":"individual","id":"e83a97795d4ad3a2","login":"infowantstobeseen","name":"T.J. Jankun-Kelly","avatar_url":"https://avatars-next.observableusercontent.com/df9d7f817f9ad92a763b56ee2e891ca0716a6c2f6c398811547f89f0448fa181","tier":null,"role":"editor"},{"type":"team","id":"7c0dab8b587e2ed2","login":"cse4413msstate","name":"Introduction to Computer Graphics MSState","avatar_url":"https://avatars-next.observableusercontent.com/343b1e48cbb2480c08063f107b4631944c5bb97a5258576dd939a5be852f30bc","tier":"pro_2024","role":"viewer"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":{"id":"16798e6b406d73db","slug":"ray-tracing-notes","title":"Ray Tracing Notes","owner":{"id":"7c0dab8b587e2ed2","login":"cse4413msstate","name":"Introduction to Computer Graphics MSState"}},"type":"notebook","body":{"title":"Modelling: Axis-Aligned Bounding Boxes (AABBs)","cells":[{"id":0,"value":"# Modelling: Axis-Aligned Bounding Boxes (AABBs)","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":7,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":26,"value":"In addition to serving as a modelling primitive, axis-aligned boxes also serve as bounding boxes—proxy geometry for testing that is less expensive than the object the subtend. A single bounding box can contain a car model made up of a 100,000 triangles; if a ${spancolor(ray_color,\"ray\")} misses the bounding box, it misses all the triangles within, saving costly calculation.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":29,"value":"## Analytical (Ray Casting)\n\nA box is the closure of six planes in 3D space with unique pairs of parallel planes; thus, we can just use six [plane intersection tests](https://observablehq.com/@cse4413msstate/modelling-planes):","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":59,"value":"$35","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":70,"value":"for the left, right, bottom, top, near, and far planes respectively. The ${spancolor(ray_color,\"ray\")} then intersects the box if the maximum ${tex`t`} along one set of planes is less than the minimum along the other three planes parallel: we "enter" three bounding planes before leaving any one of their compliments. ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":368,"value":"Note, this solution works for any box, axis-aligned or not.\n\n### Optimization\n\nWe can optimize our solution if we account for the fact that our box is axis-aligned and utilize modern floating-point hardware. First, since each plane of the box is parallel to one of our coordinate planes, the other two coordinates are zero. Second, the normals are one in that coordinate, giving the normal unit length. This simplifies the equations somewhat:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":372,"value":"$${tex.block`\\begin{aligned}\nt_l &= \\frac{\\textcolor{${ray_color}}{\\textcolor{${object_color}}{x_l}-x_\\mathrm{r_0}}}{\\textcolor{${ray_color}}{x_{\\hat{\\mathbf{d}}}}}\\\\\nt_r &= \\frac{\\textcolor{${ray_color}}{\\textcolor{${object_color}}{x_r}-x_\\mathrm{r_0}}}{\\textcolor{${ray_color}}{x_{\\hat{\\mathbf{d}}}}}\\\\\nt_b &= \\frac{\\textcolor{${ray_color}}{\\textcolor{${object_color}}{y_b}-y_\\mathrm{r_0}}}{\\textcolor{${ray_color}}{y_{\\hat{\\mathbf{d}}}}}\\\\\nt_t &= \\frac{\\textcolor{${ray_color}}{\\textcolor{${object_color}}{y_t}-y_\\mathrm{r_0}}}{\\textcolor{${ray_color}}{y_{\\hat{\\mathbf{d}}}}}\\\\\nt_n &= \\frac{\\textcolor{${ray_color}}{\\textcolor{${object_color}}{z_n}-z_\\mathrm{r_0}}}{\\textcolor{${ray_color}}{z_{\\hat{\\mathbf{d}}}}}\\\\\nt_f &= \\frac{\\textcolor{${ray_color}}{\\textcolor{${object_color}}{z_f}-z_\\mathrm{r_0}}}{\\textcolor{${ray_color}}{z_{\\hat{\\mathbf{d}}}}}\\\\\n\\end{aligned}`}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":401,"value":"We can express this more succinctly if we use *component-wise* multiplication and division across the vectors: the first element of the first vector times the first element of the second vector becomes the first element of the result. This is supported in modern shading languages via the traditional multiplication/division operator:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":403,"value":"$${tex.block`\\begin{aligned}\\mathbf{a}\\mathbf{b} &= \\left[a_0b_0, \\cdots, a_nb_n\\right]\\\\\n\\mathbf{a}/\\mathbf{b} &= \\left[a_0/b_0, \\cdots, a_n/b_n\\right]\\end{aligned}`}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":407,"value":"Using this shorthand, we can rewrite the above as","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":409,"value":"$${tex.block`\\begin{aligned}\n\\mathbf{t}_{lbn} &= \\frac{\\textcolor{${ray_color}}{\\textcolor{${object_color}}{\\bullet \\mathrm{q}_{lbn} }-\\bullet\\mathrm{r_0}}}{\\textcolor{${ray_color}}{\\hat{\\mathbf{d}}}}\\\\\n\\mathbf{t}_{rtf} &= \\frac{\\textcolor{${ray_color}}{\\textcolor{${object_color}}{\\bullet \\mathrm{q}_{rtf}}-\\bullet\\mathrm{r_0}}}{\\textcolor{${ray_color}}{\\hat{\\mathbf{d}}}}\\\\\n\n\\end{aligned}`}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":425,"value":"We then check that the maximum of the dimension minimums is less than the minimum of the dimension maximums (again, functions are applied component-wise to vectors):","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":437,"value":"$${tex.block`\\begin{aligned}\n\\mathbf{t}_{\\text{min}} &= \\operatorname{min}\\left(\\mathbf{t}_{lbn}, \\mathbf{t}_{rtf}\\right)\\\\\n\\mathbf{t}_{\\text{max}} &= \\operatorname{max}\\left(\\mathbf{t}_{lbn}, \\mathbf{t}_{rtf}\\right)\\\\\nt_\\text{min} &= \\operatorname{max}\\left(\\mathbf{t}_{\\text{min}x},\\mathbf{t}_{\\text{min}y},\\mathbf{t}_{\\text{min}z}\\right)\\\\\nt_\\text{max} &= \\operatorname{min}\\left(\\mathbf{t}_{\\text{max}x},\\mathbf{t}_{\\text{max}y},\\mathbf{t}_{\\text{max}z}\\right)\\\\\nt_\\text{min} < t_\\text{max} &\\implies \\text{Intersection at }t_\\text{min}\n\\end{aligned}`}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":482,"value":"Remember, the bold ${tex`\\mathbf{t}`} are vectors, the non-bold ${tex`t`} are scalars.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":429,"value":"

The NaN is in the Details

For languages that support the IEEE 754 floating-point standard (which is many), our values will properly represent not-a-number (NaN) results if we divide by zero. So long as your ${tex`\\operatorname{max}`} implementation favors returning numbers over NaNs (such as WGSL), you do not need to explicitly check for this error case.

","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":138,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":207,"value":"viewof origin = Inputs.text({label: html`${spancolor(ray_color,\"Ray Origin\")}`, value:`[${0.125*ewidth}, ${256-128}]`, disabled:true})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":209,"value":"viewof direction = Inputs.text({label: html`${spancolor(ray_color,\"Ray Direction\")}`, value:`[${norm(sub(offset([0.4*ewidth, 69]),[0.25*ewidth,112])).map((x,i) => (i%2?-x:x).toFixed(4))}]`, disabled:true})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":211,"value":"viewof t = Inputs.text({label: \"Intersection\", value: \"\", disabled:true})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":110,"value":"## Implicit (Ray Casting)\n\nWe have six plane signed-distance functions simplified in that we only need to consider one dimension for each. Our distance from the plane is the one that is smallest in absolute value. While this approach works, it is not as efficient as one where we utilize symmetry. \n\nFirst, we transform the box to be centered at the origin; our query point ${tex`\\bullet \\mathrm{p}`} is similarly transformed:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":489,"value":"$${tex.block`\\begin{aligned}\n\\textcolor{${object_color}}{\\bullet \\mathrm{q_c}} &= \\textcolor{${object_color}}{\\bullet \\mathrm{q}_{lbn} } + \\frac{1}{2}\\left(\\textcolor{${object_color}}{\\bullet \\mathrm{q}_{rtf}}- \\textcolor{${object_color}}{\\bullet \\mathrm{q}_{lbn} }\\right)\\\\\n &= \\frac{\\textcolor{${object_color}}{\\bullet \\mathrm{q}_{rtf}} + \\textcolor{${object_color}}{\\bullet \\mathrm{q}_{lbn} }}{2}\\\\\n\\bullet \\mathrm{p}' &= \\bullet\\mathrm{p} -\\left(\\textcolor{${object_color}}{\\bullet \\mathrm{q_c}} - \\bullet\\mathrm{0}\\right)\\\\\n &= \\bullet\\mathrm{p} - \\textcolor{${object_color}}{ \\mathbf{q_c}} \n\\end{aligned}`}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":501,"value":"$${tex`\\textcolor{${object_color}}{\\bullet \\mathrm{q_c}}`} is the center of the box before translation to the origin; ${tex`\\bullet\\mathrm{p}'`} is our point ${tex`\\bullet \\mathrm{p}`} after translation. This point is in one of 27 zones: six regions outside of one plane but inside two others (above a box face), 12 regions outside of two planes but inside the other above the box edges, eight regions outside of all the planes above the corners, and one region inside. It is easier to consider a 2D box, where we have four regions above a face, four regions above a corner, and one inside: ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":507,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":478,"value":"Because of symmetry, we do not need to consider all of these cases; e.g. the signed distance to a point below the bottom plane is equivalent to the distance to a point above the top plane after flipping the sign of the ${tex`y`} coordinate. Thus, we only need to consider the octant where all coordinates are positive (again, apply the absolute value coordinate-wise); in 2D, this is the positive quadrant:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":514,"value":"$${tex.block`\\bullet \\mathrm{p}'' = \\left|\\bullet\\mathrm{p'}\\right|`}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":527,"value":"$38","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":546,"value":"$39","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":561,"value":"Note that for cases (1) and (2), the difference in the other dimension would be negative. We can detect this and set this to zero and use (3) to calculate the first three cases","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":563,"value":"$${tex.block`\\operatorname{sdf}\\left(\\bullet \\mathrm{p}''_\\text{outside} \\right) = \\left\\|\\operatorname{max}\\left(\\bullet \\mathrm{p}'' - \\textcolor{${object_color}}{\\Delta \\mathbf{q}_{\\frac{1}{2}}},0\\right)\\right\\|`}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":568,"value":"If we are inside the box, then the all the components of ${tex`\\bullet \\mathrm{p}''`} are negative and ${tex`\\operatorname{sdf}\\left(\\bullet\\mathrm{p}''_\\text{outside}\\right)=0`}. Those negative components, however, are the distances of the point from the boundary in each dimension while inside, so we just need to return the maximum of those (the smallest in absolute value)","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":571,"value":"$${tex.block`\\begin{aligned}\n \\Delta\\mathrm{p}'' &= \\bullet \\mathrm{p}'' - \\textcolor{${object_color}}{\\Delta \\mathbf{q}_{\\frac{1}{2}}}\\\\\n \\operatorname{sdf}\\left(\\bullet \\mathrm{p}''_\\text{inside} \\right) &= \\operatorname{max}\\left(\\Delta\\mathrm{p}''_x, \\Delta\\mathrm{p}''_y\\right)\n\\end{aligned}`}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":574,"value":"If we are outside the box, then ${tex`\\operatorname{sdf}\\left(\\bullet\\mathrm{p}''_\\text{inside}\\right)>0`}; we use this to form a single calculation","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":577,"value":"$${tex.block`\\begin{aligned}\n \\Delta\\mathrm{p}'' &= \\left|\\bullet \\mathrm{p}-\\textcolor{${object_color}}{\\mathbf{q_c}}\\right|- \\textcolor{${object_color}}{\\Delta \\mathbf{q}_{\\frac{1}{2}}}\\\\\n \\operatorname{sdf}\\left(\\bullet \\mathrm{p}\\right) &= \\left\\|\\operatorname{max}\\left(\\Delta\\mathrm{p}'',0\\right)\\right\\| + \\operatorname{min}\\left(0,\\operatorname{max}\\left(\\Delta\\mathrm{p}''_i\\right)\\right)\n\\end{aligned}`}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":584,"value":"for each dimension ${tex`i`}; this formulation extends to any dimension.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":142,"value":"$3a","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":314,"value":"viewof march_origin = Inputs.text({label: html`${spancolor(ray_color,\"Ray Origin\")}`, value:`[${0.25*ewidth}, 112]`, disabled:true})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":316,"value":"viewof march_direction = Inputs.text({label: html`${spancolor(ray_color,\"Ray Direction\")}`, value:`[${norm([1,1]).map(x => x.toFixed(4))}]`, disabled:true})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":318,"value":"viewof march_distance = Inputs.text({label: \"March Distance\", value:`${sdf([0.25*ewidth, 112], [0.5*ewidth,54],[0,-1])}`, disabled:true})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":322,"value":"viewof march_intersection = Inputs.text({label: \"Intersection\", value: \"undefined\", disabled:true})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":581,"value":"## References\n\nThe SDF derivation was modified from [an excellent video](https://www.youtube.com/watch?v=62-pRVZuS5c) by [Inigo Quilez](https://iquilezles.org/).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":95,"value":"## Implementation","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":14,"value":"ewidth = Math.min(width, 640)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":154,"value":"sub = ([x1,y1],[x0,y0]) => [x1-x0,y1-y0]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":156,"value":"add = ([x0,y0],[x1,y1])=>[x1+x0,y1+y0]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":648,"value":"div = (v1,v2) => [v1[0]/v2[0],v1[1]/v2[1]]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":158,"value":"dot = ([x,y], [i,j]) => x*i + y*j","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":160,"value":"lensq = (vec) => dot(vec, vec)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":162,"value":"len = (vec) => Math.sqrt(lensq(vec))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":164,"value":"norm = ([x,y]) => [x/len([x,y]), y/len([x,y])]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":180,"value":"sdf = (p, lb, rt) => {\n let avg = add(lb,rt).map(x=>x/2);\n let hemi = sub(rt,lb).map(x=>x/2);\n return len(sub(sub(p,avg).map(x=>Math.abs(x)),hemi).map(x=>Math.max(x,0)))+Math.min(0,Math.max(...sub(sub(p,avg).map(x=>Math.abs(x)),hemi)));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":836,"value":"len(sub(sub([1.9,-3],[1.5,1.5]).map(x=>Math.abs(x)),[0.5,0.5]).map(x=>Math.max(x,0)))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":834,"value":"Math.min(0,Math.max(...sub(sub([1.7,1.2],[1.5,1.5]).map(x=>Math.abs(x)),[0.5,0.5])))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":187,"value":"ray = (r,d,t) => add(r,d.map(x=>x*t))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":183,"value":"intersect_ray_point = (r,d,q) => div(sub(q,r),d)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":216,"value":"offset_len = Math.max(30,0.1*ewidth)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":219,"value":"offset = ([x,y], d=offset_len) => add([160,112], norm(sub([x,y],[0.125*ewidth,128])).map(i=>i*d))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"### Color Constants\n\nWe use a lot of colors; define constants to use for them. They are imported.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":11,"value":"import {x_color,y_color,z_color,u_color,v_color,n_color,camera_color,viewport_color,image_color,ray_color,object_color,scene_color,spancolor,texcolor} from \"@cse4413msstate/graphics-color-functions\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W3b","stdlib":"1","titling":"auto"}} 33:"$32:body"