2b:null 2c:["$","title",null,{"children":"Accelerating Intersections | T.J. Jankun-Kelly | Observable"}] 31:T454,md`# Accelerating Intersections Once we have more than a few objects, it behoves us to accelerate our intersection testing for our ray methods. This acceleration is especially needed when attempting to ray trace triangle meshes: Many small triangles can significantly slow our rendering speed if we must test intersection every one every time. Thus, we turn to some data structures to accelerate our ray-object tests. ## Uniform Spatial Decomposition: Voxels The fundamental issue with testing everything is that we are testing everything, mainly because we have no *a priori* means of telling what objects are closest to our ray. If we divide space uniformly—turn continuous space into a discrete set of (an infinite number of) voxels—we need only test voxels near our ray origin. In addition, as we move along the ray, we only need to test voxels that intersect this ray—already, a significant savings in time. Specifically, we only need to consider voxels **on the boundary** of our objects as that is where intersetions occur. `32:T9c6,viewof uniform_cells = { const id2 = DOM.uid("spheres"); let grid = ''; for(let i = controls.dx; i < ewidth; i+=controls.dx) { grid += ``; } for(let i = controls.dy; i < 256; i+=controls.dy) { grid += ``; } const values = new Map(); let hit = ''; for(let i = 0; i < ewidth; i+=controls.dx) { for(let j = 0; j < 256; j+=controls.dy) { if(in_cell([i,j], [i+controls.dx,j+controls.dy], s1o, s1r) || in_cell([i,j], [i+controls.dx,j+controls.dy], s2o, s2r) || in_cell([i,j], [i+controls.dx,j+controls.dy], s3o, s3r)) { hit += ``; const allhit = []; if(in_cell([i,j], [i+controls.dx,j+controls.dy], s1o, s1r)) allhit.push("sphere_1"); if(in_cell([i,j], [i+controls.dx,j+controls.dy], s2o, s2r)) allhit.push("sphere_2"); if(in_cell([i,j], [i+controls.dx,j+controls.dy], s3o, s3r)) allhit.push("sphere_3"); values.set([i,j,controls.dx,controls.dy].join(),allhit); } else values.set([i,j,controls.dx,controls.dy].join(),[]); } } const fig = html`

Change grid spacing to see how it affects binning

` fig.value = values; return fig; }33:T1438,{ const id = DOM.uid("arrowhead"); const id2 = DOM.uid("spheres"); let origin = [0.3*ewidth, 130]; let offset_len = Math.max(30,0.05*ewidth); const offset = ([x,y], d=offset_len, src=origin) => add(src, norm(sub([x,y],src)).map(i=>i*d)) let target = offset([0.4*ewidth, 69]); let step = 0; let prev_step = 0; let [steps, hit_step] = ray_dda(origin, offset(target), uniform_cells); console.log(steps,hit_step); let grid = ''; for(let i = controls.dx; i < ewidth; i+=controls.dx) { grid += ``; } for(let i = controls.dy; i < 256; i+=controls.dy) { grid += ``; } const fig = html`

Drag point and ray to see traversal of grid.

` d3.select(fig).select("#step") .interrupt("step") .transition("step") .ease(d3.easeCubic) .on("start", function stepping(){ prev_step = step; step += 1; if(step >= steps.length) step = 0; const cell = steps[step]; d3.active(this, "step") .attr('x', cell.x) .attr('y', cell.y) .attr('fill-opacity', step == hit_step ? 0.25 : 0) .transition("step") .delay(1000) .on("start", stepping); }); invalidation.then(() => d3.select(fig).selectAll("*").transition("step").interrupt()); d3.select(fig).selectAll(".draggable").call(d3.drag() .on("start", start).on("drag", dragged).on("end", update)); function start() { d3.select(fig).selectAll("#step") .attr("stroke", "none"); } function dragged() { if(d3.event.x < 0 || d3.event.x >= ewidth || d3.event.y < 0 || d3.event.y >= 256) return; let ele = d3.select(this); if(ele.classed("origin")) { // Dragging origin target = add(target, sub([d3.event.x, d3.event.y], origin)); origin = [d3.event.x, d3.event.y]; } else { // Dragging line target = [d3.event.x, d3.event.y]; } 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() { step = 0; d3.select(fig).selectAll("#step") .attr('stroke', 'black') .attr('x', steps[0].x) .attr('y', steps[0].y); [steps, hit_step] = ray_dda(origin, offset(target), uniform_cells); } return fig; }34:T8b2,viewof quadtree_cells = { const id2 = DOM.uid("spheres"); let grid = ''; const queue = [[0,0,0]]; const max_subdivision = Math.min(Math.log2(ewidth),Math.log2(256)); const values = new Map(); while(queue.length > 0) { const [i,j,level] = queue.pop(); const dx = ewidth / Math.pow(2, level); const dy = 256 / Math.pow(2, level); const allhit = []; if(in_cell([i,j], [i+dx,j+dy], s1o, s1r, true)) allhit.push("sphere_1"); if(in_cell([i,j], [i+dx,j+dy], s2o, s2r, true)) allhit.push("sphere_2"); if(in_cell([i,j], [i+dx,j+dy], s3o, s3r, true)) allhit.push("sphere_3"); if(allhit.length > 1 && level < subdivision) { queue.push([i,j,level+1]); queue.push([i+dx/2,j,level+1]); queue.push([i,j+dy/2,level+1]); queue.push([i+dx/2,j+dy/2,level+1]); } else { grid += `0?0.25:0} />`; values.set([i,j,dx,dy].join(), allhit); } } const fig = html`

Select subdivision level. Splitting stops at one item per cell.

` fig.value = values; return fig; }35:T1438,{ const id = DOM.uid("arrowhead"); const id2 = DOM.uid("spheres"); let origin = [0.3*ewidth, 130]; let offset_len = Math.max(30,0.05*ewidth); const offset = ([x,y], d=offset_len, src=origin) => add(src, norm(sub([x,y],src)).map(i=>i*d)) let target = offset([0.4*ewidth, 69]); let step = 0; let [steps, hit_step] = ray_dda(origin, offset(target), quadtree_cells); let grid = ''; for(let [cell, hit] of quadtree_cells) { const [i,j,w,h] = cell.split(",").map(d=>parseInt(d)); grid += `0?0.25:0} />`; } const fig = html`

Drag point and ray to see traversal of grid.

` d3.select(fig).select("#step") .interrupt("step") .transition("step") .ease(d3.easeCubic) .on("start", function stepping(){ step += 1; if(step >= steps.length) step = 0; d3.active(this, "step") .attr('x', steps[step].x) .attr('y', steps[step].y) .attr('width', steps[step].w) .attr('height', steps[step].h) .attr('fill-opacity', step == hit_step ? 0.25 : 0) .transition("step") .delay(1000) .on("start", stepping); }); invalidation.then(() => d3.select(fig).selectAll("*").transition("step").interrupt()); d3.select(fig).selectAll(".draggable").call(d3.drag() .on("start", start).on("drag", dragged).on("end", update)); function start() { d3.select(fig).selectAll("#step") .attr("stroke", "none"); } function dragged() { if(d3.event.x < 0 || d3.event.x >= ewidth || d3.event.y < 0 || d3.event.y >= 256) return; let ele = d3.select(this); if(ele.classed("origin")) { // Dragging origin target = add(target, sub([d3.event.x, d3.event.y], origin)); origin = [d3.event.x, d3.event.y]; } else { // Dragging line target = [d3.event.x, d3.event.y]; } 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() { step = 0; d3.select(fig).selectAll("#step") .attr('stroke', 'black') .attr('x', steps[0].x) .attr('y', steps[0].y) .attr('width', steps[0].w) .attr('height', steps[0].h); [steps, hit_step] = ray_dda(origin, offset(target), quadtree_cells); } return fig; }36:T57e,md`## Spatial Partioning: k-d tree While octrees have less cells, their subdivision is based ultimately on space, and not on the objects themselves. Though the structure has good aspect ratios and can have efficient implementations, they are not the most efficient in terms of space and depth of the tree. For this, we can use a k-d tree which partitions space directly based upon where the objects are located. A k-d tree generalizes [binary search trees](https://observablehq.com/@infowantstobeseen/binary-search-trees-find) to 2 or more dimensions. It does so by alternating the dimension partitioned—we may first partition in ${tex`x`}, then ${tex`y`}, and then back to ${tex`x`} in two dimensions. In geometric applications, partioning is usually done on the points (the median is a good choice), but in computer graphics, [other heuristics](https://medium.com/@bromanz/how-to-create-awesome-accelerators-the-surface-area-heuristic-e14b5dec6160 "Medium: How to create awesome accelerators") that split to improve intersections are used. Consider our sphere-based scene above. We can treat each split as subdividing space into two bounding boxes that nest within each other. For ray tracing, we generally only store data at the leaves where we peform intersections. If we split at the radii we will get a different tree than that splitting based upon a surface-area-like heuristic:`37:T20a1,viewof kd_cells = { const id2 = DOM.uid("spheres"); let grid = ''; const values = new Map(); // recursive function // only store leaves in values const centers = [s1o, s2o, s3o]; const kdsplit = (dim, region, level = 0) => { grid += `l[dim]-r[dim]) .filter(d=>region.x < d[0] && d[0] < (region.x+region.w) && region.y < d[1] && d[1] < (region.y+region.h)); if(active_centers.length == 0 || (active_centers.length == 1 && use_bbox_kdtree)) { // Nothing to split const allhit = []; if(in_cell([region.x,region.y], [region.x+region.w,region.y+region.h], s1o, s1r, true)) allhit.push("sphere_1"); if(in_cell([region.x,region.y], [region.x+region.w,region.y+region.h], s2o, s2r, true)) allhit.push("sphere_2"); if(in_cell([region.x,region.y], [region.x+region.w,region.y+region.h], s3o, s3r, true)) allhit.push("sphere_3"); grid += ` fill-opacity=${allhit.length > 0 ? 0.25 : 0} />`; values.set([region.x,region.y,region.w,region.h].join(), allhit); return; } // Not leaf. Finish grid cell outline grid += ' fill-opacity=0 />'; if(!use_bbox_kdtree) { // We have three spheres. First split will always start w/ 3 active, go to 1 on each side // Next split will just have one active, so down the middle if(active_centers.length == 3) { // Two regions on either side of middle sphere kdsplit((dim + 1) % 2, {x:region.x, y:region.y, w:(dim? region.w : active_centers[1][0] - region.x), h:(dim? active_centers[1][1] - region.y : region.h)}, level + 1); kdsplit((dim + 1) % 2, {x:(dim? region.x : active_centers[1][0]), y:(dim? active_centers[1][1]: region.y), w:region.w - (dim? 0 : active_centers[1][0] - region.x), h:region.h - (dim? active_centers[1][1] - region.y : 0)}, level + 1); } else if(active_centers.length == 1) { // Two regions on either side of the sphere kdsplit((dim + 1) % 2, {x:region.x, y:region.y, w:(dim? region.w : active_centers[0][0] - region.x), h:(dim? active_centers[0][1] - region.y : region.h)}, level + 1); kdsplit((dim + 1) % 2, {x:(dim? region.x : active_centers[0][0]), y:(dim? active_centers[0][1]: region.y), w:region.w - (dim? 0 : active_centers[0][0] - region.x), h:region.h - (dim? active_centers[0][1] - region.y : 0)}, level + 1); } else { console.log("Error: Wrong number of centers", active_centers); } } else { // Split into two bins, grow them as big as we can w/o overlaps const bins = [{x:region.x, y: region.y, w: undefined, h: undefined}, {x:undefined, y: undefined, w: undefined, h: undefined}]; const middle = ["sphere_1", "sphere_2", "sphere_3"]; // Bin first and last if(active_centers[0][0] == s1o[0] && active_centers[0][1] == s1o[1]) { bins[0].w = dim? region.w : (s1o[0] - region.x + s1r); bins[0].h = dim? (s1o[1] - region.y + s1r) : region.h; middle.splice(middle.indexOf("sphere_1"), 1); } else if(active_centers[0][0] == s2o[0] && active_centers[0][1] == s2o[1]) { bins[0].w = dim? region.w : (s2o[0] - region.x + s2r); bins[0].h = dim? (s2o[1] - region.y + s2r) : region.h; middle.splice(middle.indexOf("sphere_2"), 1); } else { bins[0].w = dim? region.w : (s3o[0] - region.x + s3r); bins[0].h = dim? (s3o[1] - region.y + s3r) : region.h; middle.splice(middle.indexOf("sphere_3"), 1); } const last = active_centers.length-1; if(active_centers[last][0] == s1o[0] && active_centers[last][1] == s1o[1]) { bins[1].x = dim? region.x : (s1o[0] - s1r); bins[1].y = dim? (s1o[1] - s1r) : region.y; bins[1].w = dim? region.w : (region.w - bins[1].x + region.x); bins[1].h = dim? (region.h - bins[1].y + region.y) : region.h; middle.splice(middle.indexOf("sphere_1"), 1); } else if(active_centers[last][0] == s2o[0] && active_centers[last][1] == s2o[1]) { bins[1].x = dim? region.x : (s2o[0] - s2r); bins[1].y = dim? (s2o[1] - s2r) : region.y; bins[1].w = dim? region.w : (region.w - bins[1].x + region.x); bins[1].h = dim? (region.h - bins[1].y + region.y) : region.h; middle.splice(middle.indexOf("sphere_2"), 1); } else { bins[1].x = dim? region.x : (s3o[0] - s3r); bins[1].y = dim? (s3o[1] - s3r) : region.y; bins[1].w = dim? region.w : (region.w - bins[1].x + region.x); bins[1].h = dim? (region.h - bins[1].y + region.y) : region.h; middle.splice(middle.indexOf("sphere_3"), 1); } // Try to fit other sphere into one of the two bins; if overlaps both, do nothing if(active_centers.length == 3) { const o = middle[0] == "sphere_1" ? s1o : middle[0] == "sphere_2" ? s2o : s3o; const r = middle[0] == "sphere_1" ? s1r : middle[0] == "sphere_2" ? s2r : s3r; if(o[dim] + r < bins[1][(dim?"y":"x")]) { bins[0].w = dim? bins[0].w : Math.max(bins[0].w, o[0] - bins[0].x + r); bins[0].h = dim? Math.max(bins[0].h, o[1] - bins[0].y + r) : bins[0].h; } else if((dim?(bins[0].y + bins[0].h):(bins[0].x + bins[0].w)) < o[dim] - r) { bins[1].x = dim? bins[1].x : Math.min(bins[1].x, o[0] - r); bins[1].y = dim? Math.min(bins[1].y, o[1] - r) : bins[1].y; bins[1].w = dim? bins[1].w : region.w - (bins[1].x - region.x); bins[1].h = dim? region.h - (bins[1].y - region.y) : bins[1].h; } } // Fix the bins if((dim?(bins[0].y+bins[0].h):(bins[0].x+bins[0].w)) > (dim?(bins[1].y+bins[1].h):(bins[1].x+bins[1].w))) { // Overlap. Shrink to split the difference if(dim) { bins[1].y = Math.floor(0.5 * (bins[1].y + bins[0].y + bins[0].h)); bins[1].h = region.h - (bins[1].y - region.y); } else { bins[1].x = Math.floor(0.5 * (bins[1].x + bins[0].x + bins[0].w)); bins[1].w = region.w - (bins[1].x - region.x); } } // Make sure bins cover area if(dim) { bins[0].h = bins[1].y - bins[0].y; } else { bins[0].w = bins[1].x - bins[0].x; } //Split kdsplit((dim + 1) % 2, bins[0], level + 1); kdsplit((dim + 1) % 2, bins[1], level + 1); } } kdsplit(0, {x:0, y:0, w:ewidth, h:256}, 0); const fig = html`

Changing splitting option changes the structure of the k-d tree.

` fig.value = values; return fig; }38:T1454,{ const id = DOM.uid("arrowhead"); const id2 = DOM.uid("spheres"); let origin = [0.3*ewidth, 130]; let offset_len = Math.max(30,0.05*ewidth); const offset = ([x,y], d=offset_len, src=origin) => add(src, norm(sub([x,y],src)).map(i=>i*d)) let target = offset([0.4*ewidth, 69]); let step = 0; let [steps, hit_step] = ray_dda(origin, offset(target), kd_cells); console.log(steps); let grid = ''; for(let [cell, hit] of kd_cells) { const [i,j,w,h] = cell.split(",").map(d=>parseInt(d)); grid += `0?0.25:0} />`; } const fig = html`

Drag point and ray to see traversal of grid.

Changing the partioning axis changes the heirarchy.

` fig.value = regions; return fig; }3b:T170f,{ const id = DOM.uid("arrowhead"); const id2 = DOM.uid("spheres"); let origin = [0.3*ewidth, 130]; let offset_len = Math.max(30,0.05*ewidth); const offset = ([x,y], d=offset_len, src=origin) => add(src, norm(sub([x,y],src)).map(i=>i*d)) let target = offset([0.4*ewidth, 69]); let step = 0; let [steps, hit_step] = ray_bvh(origin, offset(target), bvh); if(steps.length == 0) steps = [{x:-1,y:-1,w:0,h:0}]; let grid = ''; for(let cell of bvh.children[0].children.concat(bvh.children[1].children)) grid += ``; for(let cell of bvh.children) grid += ``; grid += ``; const fig = html`

Drag point and ray to see traversal of the heirarchy. A bold border indicates a sphere test after a box test.

` const eq = (c1, c2) => c1.x == c2.x && c1.y == c2.y && c1.w == c2.w && c1.h == c2.h; d3.select(fig).select("#step") .interrupt("step") .transition("step") .ease(d3.easeCubic) .on("start", function stepping(){ step += 1; if(step >= steps.length) step = 0; d3.active(this, "step") .attr('x', steps[step].x) .attr('y', steps[step].y) .attr('width', steps[step].w) .attr('height', steps[step].h) .attr('stroke-width', (step > 0 && eq(steps[step], steps[step-1])) ? 4 : 2) .attr('fill-opacity', step == hit_step ? 0.25 : 0) .transition("step") .delay(1000) .on("start", stepping); }); invalidation.then(() => d3.select(fig).selectAll("*").transition("step").interrupt()); d3.select(fig).selectAll(".draggable").call(d3.drag() .on("start", start).on("drag", dragged).on("end", update)); function start() { d3.select(fig).selectAll("#step") .attr("stroke", "none"); } function dragged() { if(d3.event.x < 0 || d3.event.x >= ewidth || d3.event.y < 0 || d3.event.y >= 256) return; let ele = d3.select(this); if(ele.classed("origin")) { // Dragging origin target = add(target, sub([d3.event.x, d3.event.y], origin)); origin = [d3.event.x, d3.event.y]; } else { // Dragging line target = [d3.event.x, d3.event.y]; } 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() { step = 0; d3.select(fig).selectAll("#step") .attr('stroke', 'black') .attr('x', steps[0].x) .attr('y', steps[0].y) .attr('width', steps[0].w) .attr('height', steps[0].h); [steps, hit_step] = ray_bvh(origin, offset(target), bvh); if(steps.length == 0) steps = [{x:-1,y:-1,w:0,h:0}]; } return fig; }3c:T52d,md`## Additional Resources There are many, many optimizations for octrees/quadtrees; [Eppstein et al.'s *Skip Quadtree* paper](https://www.ics.uci.edu/~goodrich/pubs/skip-journal.pdf "The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data") has a good overview. As always, the PBR Book has some good reading on [k-d trees](http://www.pbr-book.org/3ed-2018/Primitives_and_Intersection_Acceleration/Kd-Tree_Accelerator.html) and [bounding volume heirarchies](http://www.pbr-book.org/3ed-2018/Primitives_and_Intersection_Acceleration/Bounding_Volume_Hierarchies.html). It is non-trivial to move these structures to the GPU due to the nature of the architecture. Stanford has a couple of early papers for k-d trees ([(1)](https://graphics.stanford.edu/papers/gpu_kdtree/kdtree.pdf) and [(2)](https://graphics.stanford.edu/papers/i3dkdtree/gpu-kd-i3d.pdf)) and the [GPU Ray Tracing](http://www.pbr-book.org/3ed-2018/Retrospective_and_The_Future/Alternative_Hardware_Architectures.html#GPURayTracing) section of *PBR* opens with links to more recent work. Hardware such as the [nVidia RTX architecture](https://en.wikipedia.org/wiki/Nvidia_RTX#Ray_tracing) help support ray tracing via hardware intersection acceleration and software support. `3d:T617,function ray_dda([x0, y0], [x1, y1], cells) { //return []; // Function to find cell const findcell = (x, y) => { for(let cellstr of cells.keys()) { const [left,bottom,w,h] = cellstr.split(',').map(d=>parseInt(d)); // console.log(left,bottom,w,h,x,y); if(left <= x && x < left + w && bottom <= y && y < bottom + h) { return {x:left, y:bottom, w:w, h:h}; } } //console.log("miss",x,y); return {x:0,y:0,w:0,h:0}; } // Direction of increment let cell = findcell(x0, y0); const dir = sub([x1,y1], [x0,y0]); let [dx, dy] = dir.map(Math.sign); // t steps const txprev = ((dx < 0 ? (cell.x + cell.w) : cell.x) - x0) / dir[0]; const typrev = ((dy < 0 ? (cell.y + cell.h) : cell.y) - y0) / dir[1]; let tx = ((dx < 0 ? cell.x : (cell.x + cell.w)) - x0) / dir[0]; let ty = ((dy < 0 ? cell.y : (cell.y + cell.h)) - y0) / dir[1]; // Generate let [x, y] = [x0, y0]; const hit_cells = []; let prev = txprev; do { hit_cells.push(cell); if(ray_hit(prev, Math.min(tx, ty), [x0,y0], dir, cell, cells)) { return [hit_cells, hit_cells.length - 1]; } prev = Math.min(tx,ty); //console.log("@", prev,x,y, add([x0,y0],dir.map(d=>(prev+0.001)*d))); [x,y] = add([x0,y0],dir.map(d=>(prev+0.001)*d)); cell = findcell(x, y); tx = ((dx < 0 ? cell.x : (cell.x + cell.w)) - x0) / dir[0]; ty = ((dy < 0 ? cell.y : (cell.y + cell.h)) - y0) / dir[1]; } while(x > 0 && x < ewidth && y >= 0 && y < 256); return [hit_cells, undefined]; }3e:T903,ray_bvh = function r_bvh([x0,y0], [x1,y1], cell) { let steps = [cell]; // Box intersection const dir = sub([x1,y1], [x0,y0]); let txprev = (cell.x - x0) / dir[0]; let typrev = (cell.y - y0) / dir[1]; let txnext = (cell.x + cell.w - x0) / dir[0]; let tynext = (cell.y + cell.h - y0) / dir[1]; if(dir[0] < 0) [txprev, txnext] = [txnext, txprev]; if(dir[1] < 0) [typrev, tynext] = [tynext, typrev]; if(txprev > tynext || typrev > txnext) return [steps, undefined, -1]; let [prev2, prev, next, next2] = [txprev, typrev, txnext, tynext].sort((l,r)=>l-r); if(next < 0) return [steps, undefined, -1]; prev = Math.max(0, prev); if(cell.children.length == 0) { steps.push(cell); // Sphere intersection let t1s = intersect_sphere([x0,y0], dir, s1o, s1r); t1s = t1s.length > 0 ? t1s[0] : 1/0; let t2s = intersect_sphere([x0,y0], dir, s2o, s2r); t2s = t2s.length > 0 ? t2s[0] : 1/0; let t3s = intersect_sphere([x0,y0], dir, s3o, s3r); t3s = t3s.length > 0 ? t3s[0] : 1/0; let t = Math.min(t1s, t2s, t3s); if(prev <= t && t <= next) { return [steps,steps.length - 1,t]; } } else { let [lchild_steps, lchild_hit, lchild_t] = r_bvh([x0,y0],[x1,y1],cell.children[0]); let [rchild_steps, rchild_hit, rchild_t] = r_bvh([x0,y0],[x1,y1],cell.children[1]); if(lchild_hit != undefined && rchild_hit != undefined) { if(lchild_t < rchild_t) { steps = steps.concat(rchild_steps); steps = steps.concat(lchild_steps); return [steps, steps.length - 1, lchild_t]; } else { steps = steps.concat(lchild_steps); steps = steps.concat(rchild_steps); return [steps, steps.length - 1, rchild_t]; } } else if(lchild_hit != undefined) { steps = steps.concat(rchild_steps); steps = steps.concat(lchild_steps); return [steps, steps.length - 1, lchild_t]; } else if(rchild_hit != undefined) { steps = steps.concat(lchild_steps); steps = steps.concat(rchild_steps); return [steps, steps.length - 1, rchild_t]; } else { steps = steps.concat(lchild_steps); steps = steps.concat(rchild_steps); } } return [steps,undefined,-1]; }3f:[] 2f:{"id":"34cfe8196b258175","slug":"accelerating-intersections","title":"Accelerating Intersections","thumbnail":"bd30df93f8c43f0986f8767c887d2c0e09f4e89b9111e0120df9862fd390feb2","access_level":"public","create_time":"$D2020-09-07T18:15:41.308Z","update_time":"$D2024-01-26T19:27:44.276Z","view_time":null,"first_public_time":"$D2020-09-16T04:50:18.642Z","fork":false,"stars":7,"starred":false,"owner":{"type":"team","id":"57cbc1498c70b426","login":"infowantstobeseen","name":"T.J. Jankun-Kelly","avatar_url":"https://avatars-next.observableusercontent.com/df9d7f817f9ad92a763b56ee2e891ca0716a6c2f6c398811547f89f0448fa181","tier":"starter_2024"},"version":868,"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"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":1,"collection":{"id":"47062c7e11777d35","slug":"advanced-graphics","title":"Advanced Graphics","owner":{"id":"57cbc1498c70b426","login":"infowantstobeseen","name":"T.J. Jankun-Kelly"}},"type":"notebook","body":{"title":"Accelerating Intersections","cells":[{"id":0,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":28,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":41,"value":"viewof controls = inputsGroup(\n[\n [\n slider({'title':'x spacing',min:10, max:ewidth/2, value: Math.max(ewidth/4, 10), step: 1 }),\n slider({'title':'y spacing',min:10, max:64, value: Math.max(32, 10), step: 1 })\n ]\n],\n \n[\n ['dx', 'dy']\n] \n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":309,"value":"uniform_cells","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":170,"value":"md`Once we have our grid, we use a voxel walking algorithm to step through each grid point. For the starting voxel, we look for intersections; if none, we use a 3D adaptation of [some line drawing algorithm](https://observablehq.com/@infowantstobeseen/drawing-lines \"Drawing Lines\") to traverse to the next voxel until a hit occurs or we exit the volume: the error terms we used are based upon the ray intersection values ${tex`t`} with the grid boxes—we always increment along the smallest ${tex`\\Delta t`}:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":18,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":11,"value":"md`## Non-unform Spatial Decomposition: Octree\n\nUniform decomposition is quick to set up, but there are numerous cells that will remain empty for most scenes, making traversal slower. We can address that by splitting space non-uniformly. A common approach is to split space into smaller and smaller octants only where we need it forming an octree (or quadtree in two dimensions).\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":396,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":398,"value":"viewof subdivision = slider({'title':'Max subdivision level',min:0, max:Math.min(Math.log2(ewidth),Math.log2(256)), value: 0, step: 1 })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":421,"value":"quadtree_cells","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":429,"value":"md`Ray traveral is similar to the uniform subdivision: We find the next ${tex`t`} intersection will a cell boundary; the space between the boundaries is just different. We need update all the ${tex`t,x,y,z`} values while walking due to the non-uniformity:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":434,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":393,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":576,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":580,"value":"viewof use_bbox_kdtree = checkbox({'title':'K-d method',options:[{value:true,label:'Use a surface-area approximation.'}], value: false })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":708,"value":"md`Regardless of the approach, the depth of the tree (and thus the number of traversals) is less than our octree for the same data:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":584,"value":"kd_cells","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":634,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":570,"value":"$39","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":720,"value":"$3a","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":715,"value":"viewof bbox_dir_y = checkbox({'title':'Direction of box partioning',options:[{value:true,label:'Use y to partition'}], value: false })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":736,"value":"bvh","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":753,"value":"md`Traversal starts at the top cell and tests against all children if the outer box matches, returning the closest.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":757,"value":"$3b","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":643,"value":"$3c","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":652,"value":"md`## Variables\n\n### Sphere centers and radii\n\nChanging these will change the scene for different octrees and k-d trees.\n\n#### Sphere 1 Origin (\\`s1o\\`) and Radius (\\`s1r\\`)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":91,"value":"s1o = [0.5*ewidth, 128]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":94,"value":"s1r = 60","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":663,"value":"md`#### Sphere 2 Origin (\\`s2o\\`) and Radius (\\`s2r\\`)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":97,"value":"s2o = [s1o[0]-90, s1o[1]+90]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":104,"value":"s2r = 60","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":666,"value":"md`#### Sphere 3 Origin (\\`s3o\\`) and Radus (\\`s3r\\`)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":107,"value":"s3o = [0.75*ewidth,45]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":111,"value":"s3r = 30","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":677,"value":"md`## Implementation\n\nLibaries and helper functions.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":15,"value":"ewidth=Math.min(640,width)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":21,"value":"import {add, sub, dot, len, norm, intersect_sphere} from \"@infowantstobeseen/basic-ray-casting\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":82,"value":"import {sphere_signed_distance} from \"@infowantstobeseen/basic-ray-marching\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":43,"value":"import {slider, checkbox, color} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":45,"value":"import {inputsGroup} from \"@bumbeishvili/input-groups\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":24,"value":"d3 = require(\"d3-selection@1.4\", \"d3-drag@1.2\", \"d3-ease\", \"d3-interpolate\", \"d3-scale-chromatic\",\"d3-array\", \"d3-transition@1.3\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":75,"value":"in_cell = (lb, tr, center, radius, contain=false) => {\n // Either center is in box, or sphere crosses box boundary\n const center_in = lb[0] <= center[0] && center[0] <= tr[0] && lb[1] <= center[1] && center[1] < tr[1];\n if(center_in && contain) return true;\n\n let ts = intersect_sphere(lb, sub([tr[0],lb[1]], lb), center, radius);\n if(ts.length > 0 && ts[0] <= 1.0)\n return true;\n ts = intersect_sphere(lb, sub([lb[0],tr[1]], lb), center, radius);\n if(ts.length > 0 && ts[0] <= 1.0)\n return true;\n ts = intersect_sphere([tr[0],lb[1]], sub(tr, [tr[0],lb[1]]), center, radius);\n if(ts.length > 0 && ts[0] <= 1.0)\n return true;\n ts = intersect_sphere([lb[0],tr[1]], sub(tr, [lb[0],tr[1]]), center, radius);\n if(ts.length > 0 && ts[0] <= 1.0)\n return true;\n \n return false;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":215,"value":"$3d","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":767,"value":"$3e","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":295,"value":"function ray_hit(prev, t, origin, dir, cell, cells)\n{\n let t1s = 1/0; let t2s = 1/0; let t3s = 1/0;\n const key = c => [c.x,c.y,c.w,c.h].join();\n if(cells.get(key(cell)) && cells.get(key(cell)).indexOf(\"sphere_1\") > -1)\n {\n t1s = intersect_sphere(origin, dir, s1o, s1r);\n t1s = t1s.length > 0 ? t1s[0] : 1/0;\n }\n if(cells.get(key(cell)) && cells.get(key(cell)).indexOf(\"sphere_2\") > -1)\n {\n t2s = intersect_sphere(origin, dir, s2o, s2r);\n t2s = t2s.length > 0 ? t2s[0] : 1/0;\n }\n if(cells.get(key(cell)) && cells.get(key(cell)).indexOf(\"sphere_3\") > -1)\n {\n t3s = intersect_sphere(origin, dir, s3o, s3r);\n t3s = t3s.length > 0 ? t3s[0] : 1/0;\n } \n \n return prev <= Math.min(t1s, t2s, t3s) && Math.min(t1s, t2s, t3s) <= t;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W3f","stdlib":"1","titling":"auto"}} 30:"$2f:body"