Published
Edited
Mar 17, 2022
md`### Grid Construction`
md` Grid construction is a two step process: find the grid resolution, and partition the objects into grid cells
(duplicate as necessary). A simple way to choose the resolution will be to decide on
the average number of objects per grid cell. This number tells us the average number of
ray-intersection tests that must be carried out when the ray intersects a grid cell.
So we would like to have this number as small as possible, say <i>n</i>.
If we try to make the grid cell to be as close as possible to a cube, then we have
a simple algorithm to compute the number of subdivision along each cube dimentions.
<pre>
let <i>boxVolume</i> = (xSize × ySize × zSize).
let <i>cellVolume</i> = a<sup>3</sup> where <i>a</i> the size of the cubic cell is unknown.
<i>numVoxels = boxVolume/cellVolume = N/n</i> where <i>N</i> is the total objects and <i>n</i> average # of objects for cell
So <i>a</i> = <i>(n×boxVolume/N)</i><sup>1/3</sup> = n</i><sup>1/3</sup>×(boxVolume/N)</i><sup>1/3</sup>
xResolution = clamp(round(xSize/a),1,MaxResolution)
yResolution = clamp(round(ySize/a),1,MaxResolution)
zResolution = clamp(round(ySize/a),1,MaxResolution)
</pre>
The algorithm clamps the number of subdivisions along each axis to a user-specified maximum, and this
limits the grid resolution. Choice of resolution affects the overhead associated with the acceleration structure.
The higher the grid resolution, the smaller the size of the object partition, hence
faster is the ray-object-partition intersection, but the higher is the
memory overhead (to hold the cell grid) and larger the number of cells to traverse along the ray.
The latter can counterbalance the speed-up derived from the acceleration structure.
[PBRT](https://www.pbrt.org/) textbook suggests using 64 as the maximum resolution along each axis.
Instead of the box volume, it uses a cube of the maximum box dimension and uses n=3<sup>3</sup>. Under these assumptions
the equation for <i>a</i> simplifies to:<pre><i>a</i> =3×max(xSize, ySize, zSize)/N</i><sup>1/3</sup>.</pre>
<p>
Once the resolution is decided, partitioning the bounding box to grid cells is straight forward.
<br/>Next, we partition the objects into grid cells.
As we mentioned earlier, an object may overlap multiple cells. So instead of trying to find out the exact
overlap of the object with the grid cell, we find the
grid cell indices of the min and max bounds and add the object to the partition of all those cells in between.
This process may lead to unnecessary duplication of the objects, but gives us a simple and robust algorithm.
<pre>
(i<sub>min</sub>,j<sub>min</sub>,k<sub>min</sub>) = gridIndex(minBound)
(i<sub>max</sub>,j<sub>max</sub>,k<sub>max</sub>) = gridIndex(maxBound)
Iteratively add object to the partitions of all the grid cells (i,j,k)
where i ∈[i<sub>min</sub>..i<sub>max</sub>], j ∈[j<sub>min</sub>..j<sub>max</sub>] and k ∈[k<sub>min</sub>..k<sub>max</sub>].
</pre>
Grid index for a point is computed as
<pre>
gridIndex(P)=((x<sub>p</sub>-xMin<sub>AABB</sub>)/xSize<sub>AABB</sub>,(y<sub>p</sub>-yMin<sub>AABB</sub>)/ySize<sub>AABB</sub>,(z<sub>P</sub>-zMin<sub>AABB</sub>)/zSize<sub>AABB</sub>)
</pre>
As we know, valid index range in each dimension are ([0..xResolution-1], [0..yResolution-1],[0..zResolution-1]).
For the rays entering the bounding box from the maximum end, the above equation
will produce an index xResolution/yResolution/zResolution. Even if the ray is entering
the volume from the minimum end, because of floating-point precision issue, we may get an index as -1.
So we must clamp the indices less than 0 to 0 and indices above the max index to max index.
i.e.
<pre>
gridIndex(P)=(clamp((x-xMin<sub>AABB</sub>/xSize<sub>AABB</sub>), 0, xResolution-1),
clamp((y-yMin<sub>AABB</sub>)/ySize<sub>AABB</sub>, 0, yResolution-1),
clamp((z-zMin<sub>AABB</sub>)/zSize<sub>AABB</sub>, 0, zResolution-1))
</pre>
</pre>
Because of the possibility of duplication,
instead of storing object itself, it may be preferable to store object indices in the partitions.
`
d3.range(xScale(box.min[0]), xScale(box.max[0]), cellWidth)
xScale(box.min[0])
xScale(box.max[0])
d3.range(yScale(box.max[1]), yScale(box.min[1]), cellHeight)
yScale(box.min[1])
yScale(box.max[1])
cellHeight
renderEndPoints = (svg, endPoints) => {
svg
.selectAll('.symbol')
.data(endPoints)
.join('path')
.attr("class", "symbol")
.attr('transform', function(d) {
return `translate(${xScale(d.x)} ,${yScale(d.y)})`;
})
.attr('d', crossGenerator);
}
import {columns} from "@bcardiff/observable-columns"
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.