空间栅格化(体素化)及射线选择原理
对于一个空间的多个primitive，栅格化是计算这些primitive的AABB包围盒bbox，定义或者估计x y z方向分割为多少栅格m n k
例如bbox的x方向长度xh=12.6 m=3
则分割的每个小栅格x方向长度xd=xh/m=4.2
对于图元i，假设它的包围盒i.bbox的最小角点i.bbox.minpt
对于一个double的值v确定它栅格索引这样计算
int celli=(v-v0)/d
d是栅格该维度的长度, v0是该维度的最小值
假设d=1.1 v0=0.7 v=3.5
则计算后celli= 2 即v在第2个cell里
组织为函数 int geiId(double v, double v0, double d)
对于一个三维点vec3d pt则落在空间cell 或者叫体素索引 计算函数为
vec3i getPointI(vec3d pt, vec3d minpt, vec3d d)
{
int xi=getId(pt.x, minpt.x, d.x);
int yi=getId(pt.y, minpt.y, d.y);
int zi=getId(pt.z, minpt.z, d.z);
return vec3i(xi,yi,zi);
}
这个第一阶段是栅格化：对于n个primitive 先确定每个cell包含哪些primitive；
这个阶段是比较耗时一般是场景才建立时候；
然后射线查询阶段，这个经常性要求快：通过ray和整个bbox求交计算，得到ray和bbox六个面的两个交点a, b；
基于getPointId或者由a b确定遍历的cell范围，或者是由a b算出的栅格索引坐标计算哪些cell被ray碰到了，可以参考直线线段的光栅化算法，这样其实得到小数量的可能cells；
设置tmin为DBL_MAX，primitive_i为-1
然后对于cells每个cell遍历cell包含的每个primitive
进行更精细的ray和primitive相交判断算法，计算和primitive的交点距离射点的距离t 记录最小tmin及primitive_i
if(t<tmin)
{
tmin=t; primitive_i=primitive
}
遍历完cells后就得到射到的primitive_i
有可能在分配图元到栅格阶段.，一个图元可能分到不同的cell里，这是存在的，例如一条线段就划到多个cell.