郑州企业网站seo,响应式网站的优缺点,网站备案上海,网站设计说明书功能流程图Bounding Volumes 包围盒#xff1a;用一个简单形状把物体包围起来#xff0c;如果物体连包围盒都无法碰撞#xff0c;一定无法碰撞包围盒内的物体 将长方体理解成三个不同对面形成的交集#xff0c;一定是在x#xff0c;y#xff0c;z轴上的范围。没有旋转
Ray Inters…Bounding Volumes 包围盒用一个简单形状把物体包围起来如果物体连包围盒都无法碰撞一定无法碰撞包围盒内的物体 将长方体理解成三个不同对面形成的交集一定是在xyz轴上的范围。没有旋转
Ray Intersection with Axis-Aligned Box 光线和包围盒求交 给定任何一根光线可以求出光线何时和无限大的两个面有交点 之后看水平的对面求两个面的交点 即对任何一个对面可以求出进入的时间和出去的时间。 求交即可求出光线何时进入盒子何时出去盒子 对于3维空间有3组对面各计算一次光线进入对面的最小最大时间·。求出最大的进入时间和最小的离开时间。如果进入时间小于离开时间说明这段时间光线在盒子里 光线是射线不是直线如果光线离开盒子时间小于0说明盒子是在光线背后 当离开的时间是正的进入盒子的时间是负的说明光线起点在盒子里 当且仅当进入时间小于离开时间且离开时间大于0则光线与包围盒有交点 之所以用横平竖直的包围盒因为光线与和xyz轴垂直的面求交比较方便 如上图当对面与x轴垂直时可以直接求光线在x轴方向上的传播
Uniform Spatial Partitions (Grids)
做光线追踪前的预处理 先找出一个场景把场景的包围盒找出 把盒子分成一堆格子 判定哪些格子里可能有物体将与物体表面相交的格子标记起来 做完预处理后可以开始进行光线追踪。 这里认为光线和格子求交是非常快的和实际物体求交是非常慢的。 可以找到光线走的过程中相交的格子如果格子中有物体则光线可能与物体相交
只需要做若干次光线与格子的求交来避免与场景所有物体进行求交
光线会打到哪个格子最简单的思路可以是类似光栅化一条线段 极端的情况将场景划分成1x1的格子则没有加速 另一个极端是格子太密则效率太低 启发式的算法格子的数量应该是一个常数(27)乘以物体的数量 对于场景里各个地方都有几何物体分布较均匀的情况下格子的效果比较好 当场景中物体分布很不均匀有很多空的情况下不适合格子的方式
Spatial Partitions/空间划分 八叉树2维空间下是四叉树把空间切成四块再把子块切成四块知道其中有三块不和任何物体相交则不在继续切。或者一块里有足够少数量的物体 kd树和八叉树几乎一样只不过每次会找一个轴沿轴划分保持了二叉树的性质KD-Tree BSP树对空间二分每次选一个方向把节点砍开与kd树的区别是不是横平竖直的砍开。在维度高时越来越不好计算 只需要在叶子节点实际存储和这些格子相交的几何形体 按xyz依次划分选取划分位置循环子节点 场景有一光线 判断和a是否有交点有交点说明需要考虑是否和子节点有交点 如果有交点的是叶子节点则和叶子节点里的所有物体求交 两个子节点都要判断可能都有交点所以B也判断求交 依次查询直到求交到所有相交的叶子节点。类似二分查找
很难判断这个物体和包围盒是否相交即格子和哪些物体相交。对于kd-tree有个明确的问题。很难判断一个三角形和立方体有交集如当一个三角形是插进这个盒子时这个三角形的三个顶点都不在盒子里但是和盒子相交。 近十年逐渐很少使用kd树来处理就因为很难判断一个三角形和AABB是否有交点。另外如上图345都存储了一个物体。但是人们希望一个物体只在一个叶子节点里所以kd-tree并不直观。
Object Partitions Bounding Volume Hierarchy (BVH)
不从空间划分通过物体来划分这张划分形成的结构称为BVH 把一个盒子的所有三角形组织成两部分再分别重新求包围盒 递归划分子节点 直到叶子节点有足够少的物体 kd-tree是直接把空间两份bvh是把物体分成两堆再重新求包围盒。 一个物体只可能在一个盒子里。 但bvh对空间的划分并没有严格划分开即不同的Bounding box有可能相交 选择维度可以xyz循环。也可以每次沿着最长的轴划分 排序取中间位置物体划分。保证树接近平衡。 把所有的三角形取重心通过重心进行排序。
如果只是找中位数的话其实不需要排序,排序复杂度是 n log n n{\log}n nlogn。 给n个无序的数找第i大的数可以在O(n)时间内解决称为快速选择算法只对划分两边的某一边进行操作 中间节点只存包围盒与子节点指针叶子节点存储实际物体 求交类似kd-tree 总结kd-tree划分的是空间空间与空间之间不会有交集但是物体可能在两个空间。bvh划分的是物体包围盒间可能有相交不需要处理物体和包围盒是否相交。
