docs/ray_intersect.tex

   1 % build me with xelatex + bibtex
   2 \documentclass[a4paper,10pt]{article}
   3
   4 \usepackage{hyperref}
   5 \usepackage{mathpazo}
   6 \usepackage{amsmath}
   7 \usepackage[small,bf,hang]{caption}
   8 \usepackage{xunicode}
   9 \usepackage[numbers,square,sort]{natbib}
  10
  11 \usepackage{tikz}
  12 \usetikzlibrary{calc,3d}
  13
  14 \setlength{\oddsidemargin}{-0.4mm}    % 25 mm left margin - 1 in
  15 \setlength{\evensidemargin}{\oddsidemargin}
  16 \setlength{\topmargin}{-5.4mm}        % 20 mm top margin - 1 in
  17 \setlength{\textwidth}{160mm}         % 20/25 mm right margin
  18 \setlength{\textheight}{247mm}        % 20 mm bottom margin
  19 \setlength{\headheight}{5.1mm}
  20 \setlength{\headsep}{5mm}
  21 \setlength{\parindent}{0mm}
  22 \setlength{\parskip}{\medskipamount}
  23
  24 \title{Details of Ray/OBB Intersection}
  25 \author{Wildfire Games -- \url{http://wildfiregames.com/}}
  26
  27 \hypersetup {
  28         pdfauthor = {Wildfire Games},
  29         pdftitle = {Details of Ray/OBB Intersection},
  30         pdfsubject = {Some details of how the slabs method for determining ray/OBB intersection works.}
  31         pdfkeywords = {Ray, Box, OBB, Intersect},
  32 }
  33
  34 \newcommand{\vectornorm}[1]{\left|\left|#1\right|\right|}
  35 \newcommand{\mathdef}{\ensuremath{\overset{\Delta}{=}}}
  36
  37 \begin{document}
  38
  39 \maketitle
  40
  41 \section{Definitions}
  42 A ray is defined as a collection of points $\mathbf{r}(t)$ such that:
  43 \begin{equation*}
  44 \mathbf{r}(t) = \mathbf{o} + t \mathbf{d}
  45 \end{equation*}
  46 where $\mathbf{o}$ denotes the origin of the ray, $\mathbf{d}$ is a unit vector indicating the direction of the ray, and $t$ is an independent scalar parameter that specifies the distance of $\mathbf{r}(t)$ from the origin of the ray. Points that are generated by negative values of $t$ are said to lie behind the ray origin, and are not considered part of the ray.
  47
  48 An OBB, or Oriented Bounding Box, is an arbitarily-rotated three-dimensional rectangular cuboid defined by a center point $\mathbf{a}_c$, a set of mutually orthonormal basis vectors $(\mathbf{a}_u, \mathbf{a}_v, \mathbf{a}_w)$, and the half-distances $(h_u, h_v, h_w)$ of each face from the origin along their respective axes.
  49
  50 \section{Method}
  51 In 0 A.D., rays are tested for intersection with OBBs using the slab method as outlined in \cite{real_time_rendering_3}. In brief, the goal of the algorithm is to compute the distances from the ray's origin to its intersection points with each of three slabs (one for each dimension). By then performing a clever comparison of these intersection point distances, it is able to determine whether the ray hits or misses the shape.
  52
  53 This document is concerned with providing some details of how these distances are computed, in order to allow the reader to more thoroughly comprehend the algorithm. Before continuing, the reader should have the algorithm as it appears in \cite{real_time_rendering_3} at hand. For the most part, the same variable names will be used here.
  54
  55 Figure \ref{fig:visual_2d} presents a visual illustration of a sample 2D case, for one particular slab. The points $\mathbf{t}_1$ and $\mathbf{t}_2$ are the intersection points of the ray with the slab. The goal is to determine the distances between $\mathbf{o}$ and these points in the general case. Observe that each basis vector $\mathbf{a}_i$ corresponds to a slab of which it is the normal vector.
  56
  57 As in the algorithm, in what follows, let:
  58 \begin{eqnarray*}
  59 f & \mathdef & \mathbf{a}_i \cdot \mathbf{d} = \cos \theta \\
  60 e & \mathdef & \mathbf{a}_i \cdot \mathbf{p} \\
  61 \end{eqnarray*}
  62 \vspace{-1cm}
  63
  64 Both $\mathbf{a}_i$ and $\mathbf{d}$ are unit vectors; therefore by definition of the dot product, $f = \cos \theta$ where $\theta$ is the angle between the two; i.e., the ray direction and the slab normal. The scalar $e$ is the distance between $\mathbf{o}$ and the center of the box $\mathbf{a_c}$, projected onto the slab normal $\mathbf{a}_i$.
  65
  66 \begin{figure}[ht]
  67 \centering
  68 \begin{tikzpicture}[>=stealth,scale=1]
  69 \tikzstyle{empty}=[inner sep=0pt]
  70 \tikzstyle{dot}=[shape=circle,draw,fill=black,inner sep=0pt,minimum size=1mm]
  71
  72 \begin{scope}[rotate=-15]
  73 %\draw[help lines] (-5,-6) grid (7,4);
  74
  75 % box points (top right, bottom right, etc.)
  76 \node[empty] (box tr) at (4,2)   {};
  77 \node[empty] (box br) at (4,-2)  {};
  78 \node[empty] (box bl) at (-4,-2) {};
  79 \node[empty] (box tl) at (-4,2)  {};
  80 % slab points (same as box, but a bit wider)
  81 \node[empty] (slab tl) at (-5.5,2)  {};
  82 \node[empty] (slab bl) at (-5.5,-2) {};
  83 \node[empty] (slab tr) at (7.5,2)   {};
  84 \node[empty] (slab br) at (7.5,-2)  {};
  85
  86 \node[empty] (center)     at (0,0)      {};
  87 \node[empty] (ray origin) at (-2.5,-5)    {};
  88 \node[empty] (ray direction) at (0.78221, 0.640184) {};
  89 \node[empty] (ray end)    at ($(ray origin) + 12*(ray direction)$)   {};
  90
  91 \node[empty] (p) at +($(center) - (ray origin)$) {};
  92
  93 % intersection points between ray and slab lines
  94 \node[empty] (t1) at (intersection cs:
  95         first line={(ray origin) -- (ray end)},
  96         second line={(slab bl) -- (slab br)}) {};
  97 \node[empty] (t2) at (intersection cs:
  98         first line={(ray origin) -- (ray end)},
  99         second line={(slab tl) -- (slab tr)}) {};
 100
 101 % normal vector and axis through center, t1 and t2
 102 \node[empty] (normal) at (0,1) {};
 103 \node[empty] (normal through center start) at ($(center) - 6*(normal)$) {};
 104 \node[empty] (normal through center end)   at ($(center) + 4*(normal)$) {};
 105 \node[empty] (normal through t1 start)     at ($(t1)     - 4*(normal)$) {};
 106 \node[empty] (normal through t1 end)       at ($(t1)     + 6*(normal)$) {};
 107 \node[empty] (normal through t2 start)     at ($(t2)     - 8*(normal)$) {};
 108 \node[empty] (normal through t2 end)       at ($(t2)     + 2*(normal)$) {};
 109
 110 \node[empty] (q1) at ($(normal through t1 start)!(ray origin)!(normal through t1 end)$) {};
 111 \node[empty] (q2) at ($(normal through t2 start)!(ray origin)!(normal through t2 end)$) {};
 112
 113 % draw the slab background and the box
 114 \draw[fill=gray!10,fill opacity=80,draw=green!0] (slab bl) rectangle (box tl);
 115 \draw[fill=gray!10,fill opacity=80,draw=green!0] (box br) rectangle (slab tr);
 116 \draw[dashed] (slab tl) -- (box tl);
 117 \draw[dashed] (box tr) -- (slab tr);
 118 \draw[dashed] (box br) -- (slab br);
 119 \draw[dashed] (slab bl) -- (box bl);
 120 \draw (box bl) rectangle (box tr);
 121
 122 % draw node points
 123 \filldraw[fill=black] (center) circle (1.5pt) node[below right,xshift=-1mm] {$\mathbf{a}_c$};
 124 \filldraw[fill=black] (ray origin) circle (1.5pt) node[below] {$\mathbf{o}$};
 125 \filldraw[fill=black] (t1) circle (1.5pt) node[above left,xshift=1mm] {$t_1$};
 126 \filldraw[fill=black] (t2) circle (1.5pt) node[above left,xshift=1mm] {$t_2$};
 127 \filldraw[fill=black] (q1) circle (1.5pt) node[below,xshift=2mm,yshift=-.5mm] {$q_1$};
 128 \filldraw[fill=black] (q2) circle (1.5pt) node[below,xshift=2mm,yshift=-.5mm] {$q_2$};
 129
 130 % draw normal vector, ray, p
 131 \draw[->] (center) -- (0,1) node[left] {$\mathbf{a}_i$};
 132 \draw[->] (ray origin) -- (ray end);
 133 \draw[->|] (ray origin) -- +($(ray direction)$) node[midway,right,yshift=-1mm] {$\mathbf{d}$};
 134 \draw[->,shorten >=1mm] (ray origin) -- +($(p)$) node[midway,left] {$\mathbf{p}$};
 135
 136 % line parallel to ray through origin, and normal axes through t1 and t2
 137 \draw[dashed] ($(center) - 6*(ray direction)$) -- ($(center) + 6*(ray direction)$);
 138 \draw[dashed] (normal through t1 start) -- (normal through t1 end);
 139 \draw[dashed] (normal through t2 start) -- (normal through t2 end);
 140
 141 % draw angle arcs
 142 % TODO: let TikZ figure out that the angle is about 50 degrees
 143 \draw (center) ++ (40:0.5cm) arc (40:90:0.5cm) node[right,yshift=1mm,xshift=1mm] {$\theta$};
 144 \draw (t1)     ++ (-90:0.5cm) arc (-90:-140:0.5cm) node[below,yshift=-1mm] {$\theta$};
 145 \draw (t2)     ++ (-90:0.5cm) arc (-90:-140:0.5cm) node[below,yshift=-1mm] {$\theta$};
 146
 147 % draw line between (ray origin) and (ray origin) projected onto (normaxis start) -- (normaxis end)
 148 \draw[dashed] (ray origin) -- ($(normal through t1 start)!(ray origin)!(normal through t1 end)$);
 149 \draw[dashed] (ray origin) -- ($(normal through t2 start)!(ray origin)!(normal through t2 end)$);
 150
 151 % draw e, e+h and e-h distance indicators, and perpendicularity markers
 152 \begin{scope}[color=blue]
 153 %\draw[<->,shorten <=.7mm] (center) -- ($(normal through center start)!(t1)!(normal through center end)$) node[midway,left] {$h$};
 154 \draw[<->,shorten <=.7mm] (center) -- ($(normal through center start)!(ray origin)!(normal through center end)$) node[midway,left] {$e$};
 155 \draw[|<->|] ($(t1) + (1.5mm,0)$) -- ($(q1) + (1.5mm,0)$) node[midway,right] {$e-h_i$};
 156 \draw[|<->|] ($(t2) + (1.5mm,0)$) -- ($(q2) + (1.5mm,0)$) node[midway,right] {$e+h_i$};
 157 \end{scope}
 158 \draw ($(q1) + (-1.2mm,1.2mm) - (2.5mm,0)$) -- ($(q1) + (-1.2mm,1.2mm)$) -- ($(q1) + (-1.2mm,1.2mm) + (0,2.5mm)$);
 159 \draw ($(q2) + (-1.2mm,1.2mm) - (2.5mm,0)$) -- ($(q2) + (-1.2mm,1.2mm)$) -- ($(q2) + (-1.2mm,1.2mm) + (0,2.5mm)$);
 160
 161 \end{scope}
 162 \end{tikzpicture}
 163
 164 \caption{A visual representation of how the distances between $\mathbf{o}$ and $\mathbf{t}_1$ and $\mathbf{t}_2$ are computed in the two-dimensional case, for a generic slab $i \in \{u,v\}$ with normal vector $\mathbf{a}_i$ and half-size $h_i$.}
 165 \label{fig:visual_2d}
 166 \end{figure}
 167
 168 In a right-angled triangle, per definition of the cosine, the hypotenuse's length is $\cos \theta$ times the length of the adjacent side:
 169
 170 \begin{center}
 171 \begin{tikzpicture}[scale=1]
 172 \draw (0,0) -- (3,0) node[midway,below] {$x$} -- (3,2) -- (0,0) node[midway,sloped,above] {$x \cos \theta$};
 173 \draw (0,0) -- (5mm,0) arc (0:33:5mm) node[right,xshift=1mm,yshift=-.5mm] {$\theta$};
 174 \begin{scope}[xshift=-1.2mm,yshift=1.2mm]
 175 \draw ($(3,0) - (2.5mm,0)$) -- (3,0) -- ($(3,0) + (0,2.5mm)$);
 176 \end{scope}
 177 \end{tikzpicture}
 178 \end{center}
 179
 180 Thus, looking at the right-angled triangles $\Delta \mathbf{o} q_1 t_1$ and $\Delta \mathbf{o} q_2 t_2$ in Figure \ref{fig:visual_2d}, we find that:
 181 \begin{eqnarray*}
 182 \vectornorm{\mathbf{o} - \mathbf{t_1}} & = & \frac{e - h_i}{\cos \theta}\\
 183 \vectornorm{\mathbf{o} - \mathbf{t_2}} & = & \frac{e + h_i}{\cos \theta}\\
 184 \end{eqnarray*}
 185
 186 \section{Degenerate cases}
 187
 188 It's prudent to consider what happens for the degenerate case of testing a ray for intersections against an OBB that has no size in one or more dimensions. Figure \ref{fig:degenerate_2d_1dim} depicts the degenerate variant of the 2D case seen earlier, where the box now has a null size in the $u$ dimension.
 189
 190 \begin{figure}[ht]
 191 \centering
 192 \begin{tikzpicture}
 193 \tikzstyle{empty}=[inner sep=0pt]
 194 \tikzstyle{dot}=[shape=circle,draw,fill=black,inner sep=0pt,minimum size=1mm]
 195
 196 % two rays
 197 \node[dot]   (ray 1 origin) at (-5,-2)  [label=below:{$\mathbf{o}_1$}] {};
 198 \node[empty] (ray 1 direction) at (0.861934, 0.50702) {};
 199 \node[empty] (ray 1 end)    at ($(ray 1 origin) + 12*(ray 1 direction)$) {};
 200 %\node[dot]   (ray 2 origin) at (-5,-6)  [label=below:{$\mathbf{o}_2$}] {};
 201 %\node[empty] (ray 2 direction) at (0.861934, 0.50702) {};
 202 %\node[empty] (ray 2 end)    at ($(ray 2 origin) + 12*(ray 2 direction)$) {};
 203
 204 \begin{scope}[rotate=-15]
 205 %\draw[help lines] (-6,-4) grid (5,4);
 206
 207 % box points (top right, bottom right, etc.)
 208 \node[empty] (box tr) at (0,2)   {};
 209 \node[empty] (box br) at (0,-2)  {};
 210 \node[empty] (box bl) at (0,-2) {};
 211 \node[empty] (box tl) at (0,2)  {};
 212 % slab points (same as box, but a bit wider)
 213 \node[empty] (slab tl) at (-5.5,2)  {};
 214 \node[empty] (slab bl) at (-5.5,-2) {};
 215 \node[empty] (slab tr) at (5.5,2)   {};
 216 \node[empty] (slab br) at (5.5,-2)  {};
 217
 218 \node[empty] (center)     at (0,0)      {};
 219
 220 % draw the slab background and the box
 221 \draw[fill=gray!10,fill opacity=80,draw=green!0] (slab bl) rectangle (box tl);
 222 \draw[fill=gray!10,fill opacity=80,draw=green!0] (box br) rectangle (slab tr);
 223 \draw[dashed] (slab tl) -- (box tl);
 224 \draw[dashed] (box tr) -- (slab tr);
 225 \draw[dashed] (box br) -- (slab br);
 226 \draw[dashed] (slab bl) -- (box bl);
 227 \draw (box bl) rectangle (box tr);
 228
 229 % draw rays
 230 \draw[->]  (ray 1 origin) -- (ray 1 end);
 231 %\draw[->]  (ray 2 origin) -- (ray 2 end);
 232 \draw[->] (ray 1 origin) -- +($(ray 1 direction)$) node[midway,below,xshift=2mm,yshift=1mm] {$\mathbf{d}_1$};
 233 %\draw[->] (ray 2 origin) -- +($(ray 2 direction)$) node[midway,below,xshift=2mm,yshift=1mm] {$\mathbf{d}_2$};
 234
 235 % draw basis vectors
 236 \begin{scope}[xshift=-7cm]
 237 \draw[->] (0,0) -- (1,0) node[midway,below] {$\mathbf{a}_u$};
 238 \draw[->] (0,0) -- (0,1) node[midway,left]  {$\mathbf{a}_v$};
 239 \end{scope}
 240
 241 % draw node points
 242 \filldraw[fill=black] (center) circle (1.5pt) node[below right,xshift=-1mm] {$\mathbf{a}_c$};
 243 \end{scope}
 244 \end{tikzpicture}
 245
 246 \caption{Degenerate 2D case with null size in the $u$ dimension.}
 247 \label{fig:degenerate_2d_1dim}
 248 \end{figure}
 249
 250 In the method seen above, the only prerequisites to computing the distances between the ray origin and its intersection points with the slab are $\cos \theta$ and $e \pm h_i$. In the degenerate case, $h_u$ is 0, and so both intersection points will be correctly found at $e / \cos \theta$. None of the other terms depend upon the size of the box along the dimension at hand, and hence remain unaffected. However, they do depend on the degenerate dimension's normal vector remaining well-defined and non-null.
 251
 252 %\bibliographystyle{plainnat-keepcase}
 253 \bibliographystyle{plainnat}
 254 \bibliography{ray_intersect}
 255
 256 \end{document}