A [[Binary Spatial Partitioning Tree]] is a [[Data Structure]] for [[Spatial Partitioning]] using a [[Binary Tree]]. This recursively divides space into two halves. This differs from a [[Bounding Volume Hierarchy]] as there is *no overlapping* between two partitions on the same level. This type of tree worlds directly on objects ([[Triangular Mesh|Mesh]] / [[Triangle|Triangles]]). The construction of a BSP [[Tree]] is expensive, making it best for static objects.i ### Ray Casting - Structure: Node-Storing Tree - Near/Far Side $[t_{\min}t_{\max}]$ Given $\vec s_{r},\vec d_{r}, t_{\min},t_{\max},t_{\op{plane}}$ Dealing with 3 Edge Cases: Edge Case 1: $\huge [t_{\min}, t_{\max}] \implies \begin{cases} [t_{\min}, t_{\op{mid}} ] \\ [t_{\op{mid}}, t_{\max} ] \\ \end{cases}$ Check near side with $[t_{\min},t_{\op{mid}}]$; - co-planar geometry - far-side with $[t_{\op{mid}},t_{\op{\max}}]$ Edge Case 2: Extend range to count for $\epsilon$. $\large [0, t_{\op{mid}}+\epsilon] $ $ \large \begin{align} t_{\epsilon} &= ? \\ \frac{\epsilon}{t_{\epsilon}} &= \cos \theta = \vec n \cdot \vec d_{r} \end{align} $ $ \huge t_{\epsilon} = \frac{\epsilon}{\left|{ \vec n \cdot \vec d_{r} }\right| } $ Edge Case 3: *Read .pdf* *Solution:* Use: $ \huge \begin{align} [t_{\min} - t_{\epsilon}, t_{\max} + t_{\epsilon}] \end{align} $ **Always**.