P14

Spatial Partitioning

• 对空间做划分
• tree
  1. 八叉树Oct-Tree
     • 把一个3维的包围盒切成8份(2^3)
     • 高维空间就是2^n 叉树，
  2. KD-Tree
     • 每次划分只在1个维度上划分(二叉树)
     • n个维度依次循环被划分，保证空间上是均匀的
     • 问题：包围盒是否包围三角面需要对包围盒与三角面求交，不好写; 一个物体与多个叶子节点相交，所以每个叶子节点中都有存储这个物体（冗余？），最好是一个物体只存在于一个格子中（基于物体划分）。
  3. BSP-Tree
     • 每次划分方向并不与坐标轴平行
     • 计算量大

KD-Tree Preprocessing

• 对场景建立KD-Tree

Traversing a KD-Tree

• 从最大的包围盒开始，判断光线是否与之有交点，如果有交点，分别对它的两个子节点判断是否与光线有交点，如果没交点就不判断其子节点。走到叶子节点，就对包围盒中的所有物体求交。

Object Partitions & Bounding Volume Hierarchy (BVH)

• 把三角形分成两组，再分别重新求它们的包围盒，知道一个盒子中最多含有5个三角形就停止划分

• 一个物体只会存在于一个包围盒中,(各盒子会有重叠)

• How to subdivide a node?

  • Choose a dimension to split
  • Heurstic #1: Always choose the longest axis in node (沿最长轴划分)
  • Heurstic #2: Split node at location of median object (以中间物体的位置划分，两侧物体数量相等，平衡意味着最大深度小，搜索次数少)

• Data Structure for BVHs

  • Internal nodes store: Bounding box and Pointers to its child nodes
  • Leaf nodes store: Bounding box and Objects
  • Nodes represent subset of primitives(基础元素) in scene. All objects in subtree

• 遍历方式与KD-Tree 相同：

  1 2 3 4 5 6 7 8 9 10 11

  Intersect(Ray ray, BVH node) { if (ray misses node.bbox) return; if (node is a leaf node) test intersection with all objs; return closest intersection; hit1 = Intersect(ray, node.child1); hit2 = Intersect(ray, node.child2); return the closer of hit1, hit2;

Radiometry

• Termiology
  1. Radiant energy: 电磁辐射的能量 Q
  2. Radiant flux: 单位时间的能量 Φ=dQ/dt [Watt]（功率：单位时间射出多少光子）
  3. Radiant intensity: 从光源发出的光
  4. Irradiance: 表面接收的光
  5. Radiance: 沿光线传播的光

Radiant intensity

• The radiant (luminous) intensity I is the power Φ per unit solid angle ω emitted by a point light source. $I(w) ≡ \frac{dΦ}{dω}$ [candela]; $Φ = \int_S² I dw = 4πI$
• 某一方向上的能量