SCM Repository
Annotation of /trunk/doc/probe/paper.tex
Parent Directory
| 
Revision Log
Revision 159 - (view) (download) (as text)
| 1 : | jhr | 156 | \documentclass[11pt]{article} |
| 2 : | |||
| 3 : | \input{defs} | ||
| 4 : | \usepackage{graphicx} | ||
| 5 : | \usepackage{listings} | ||
| 6 : | \lstset{ | ||
| 7 : | basicstyle=\ttfamily, | ||
| 8 : | keywordstyle=\bfseries, | ||
| 9 : | showstringspaces=false, | ||
| 10 : | } | ||
| 11 : | |||
| 12 : | \lstset{ | ||
| 13 : | language=C, | ||
| 14 : | } | ||
| 15 : | |||
| 16 : | \setlength{\textwidth}{6in} | ||
| 17 : | \setlength{\oddsidemargin}{0.25in} | ||
| 18 : | \setlength{\evensidemargin}{0.25in} | ||
| 19 : | \setlength{\parskip}{5pt} | ||
| 20 : | |||
| 21 : | \newcommand{\matM}{\mathbf{M}} | ||
| 22 : | jhr | 157 | \newcommand{\vecx}{\mathbf{x}} |
| 23 : | jhr | 159 | \newcommand{\vecp}{\mathbf{p}} |
| 24 : | jhr | 156 | \newcommand{\vecn}{\mathbf{n}} |
| 25 : | \newcommand{\vecf}{\mathbf{f}} | ||
| 26 : | \newcommand{\VEC}[1]{\left\langle{#1}\right\rangle} | ||
| 27 : | \newcommand{\FLOOR}[1]{\left\lfloor{#1}\right\rfloor} | ||
| 28 : | |||
| 29 : | \title{Compiling probe operations for Diderot} | ||
| 30 : | \author{ | ||
| 31 : | John Reppy \\ | ||
| 32 : | University of Chicago \\ | ||
| 33 : | {\small\tt{}jhr@cs.uchicago.edu} \\ | ||
| 34 : | } | ||
| 35 : | \date{\today} | ||
| 36 : | |||
| 37 : | \begin{document} | ||
| 38 : | |||
| 39 : | \maketitle | ||
| 40 : | \thispagestyle{empty} | ||
| 41 : | |||
| 42 : | \bibliographystyle{../common/alpha} | ||
| 43 : | \bibliography{../common/strings-short,../common/manticore} | ||
| 44 : | |||
| 45 : | \section{Introduction} | ||
| 46 : | |||
| 47 : | This note describes the code needed to implement a probe of a field operation. | ||
| 48 : | |||
| 49 : | In the discussion below, we use $\matM^{-1}$ for the homogeneous matrix that maps from world | ||
| 50 : | jhr | 157 | coordinates to image coordinates and use $\vecx$ for the position vector. |
| 51 : | jhr | 156 | |
| 52 : | \section{Probing a 1D scalar field} | ||
| 53 : | The simplest case is probing a 1D scalar field $F = V\circledast{}h$, where $s$ is the support | ||
| 54 : | of $h$. | ||
| 55 : | The probe $F\mkw{@}x$ is computed as follows: | ||
| 56 : | \begin{eqnarray*} | ||
| 57 : | \left[\begin{array}{c} x' \\ 1 \end{array}\right] & = & \matM^{-1} \left[\begin{array}{c} x \\ 1 \end{array}\right] \qquad \text{\textit{transform to image space}} \\ | ||
| 58 : | n & = & \FLOOR{x'} \qquad \text{\textit{integer part of position}} \\ | ||
| 59 : | f & = & x' - f \qquad \text{\textit{fractional part of position}} \\ | ||
| 60 : | F\mkw{@}x & = & \sum_{i=1-s}^s {V(n+i) h(f - i)} | ||
| 61 : | \end{eqnarray*}% | ||
| 62 : | The convolution $h$ is represented as a symmetric piecewise polynomial formed | ||
| 63 : | from $s$ polynomials $h_1,\,\ldots,\,h_s$. | ||
| 64 : | \begin{displaymath} | ||
| 65 : | h(x) = \left\{\begin{array}{ll} | ||
| 66 : | jhr | 158 | 0 & \text{$x < -s$} \\ |
| 67 : | jhr | 157 | h_i(-x) & \text{$-s \leq -i \leq x < 1-i \leq 0$} \\ |
| 68 : | jhr | 156 | h_i(x) & \text{$0 < i-1 \leq x < i \leq s$} \\ |
| 69 : | 0 & \text{$x > s$} \\ | ||
| 70 : | \end{array}\right. | ||
| 71 : | \end{displaymath}% | ||
| 72 : | Thus, we can rewrite the probe computation as | ||
| 73 : | \begin{displaymath} | ||
| 74 : | jhr | 157 | F\mkw{@}x = \sum_{i=1-s}^{0} {V(n+i) h_{1-i}(i - f)} + \sum_{i=1}^s {V(n+i) h_i(f - i)} |
| 75 : | jhr | 156 | \end{displaymath}% |
| 76 : | \figref{fig:1d-probe} illustrates the situation for a kernel $h$ with support $s = 2$, | ||
| 77 : | and \figref{fig:1d-probe-code} gives the C code for the probe operation, assuming that | ||
| 78 : | $h$ is represented by third-degree polynomials. | ||
| 79 : | \begin{figure}[t] | ||
| 80 : | \begin{center} | ||
| 81 : | \includegraphics[scale=0.8]{pictures/convo} | ||
| 82 : | \end{center}% | ||
| 83 : | \caption{1D scalar probe} | ||
| 84 : | \label{fig:1d-probe} | ||
| 85 : | \end{figure}% | ||
| 86 : | |||
| 87 : | \begin{figure}[t] | ||
| 88 : | \begin{quote} | ||
| 89 : | \begin{lstlisting} | ||
| 90 : | double img[]; // image data | ||
| 91 : | double h1[4], h2[4]; // kernel | ||
| 92 : | |||
| 93 : | double probe (double x) | ||
| 94 : | { | ||
| 95 : | double imgX = transform(x); // image-space position | ||
| 96 : | double n, f; | ||
| 97 : | |||
| 98 : | f = modf (imgPos, &n); | ||
| 99 : | |||
| 100 : | double value = 0.0, x; | ||
| 101 : | |||
| 102 : | jhr | 157 | w = -1.0 - f; |
| 103 : | jhr | 156 | value += img[n-1] * (h2[0] + w*(h2[1] + w*(h2[2] + w*h2[3]))); |
| 104 : | jhr | 157 | w = -f; |
| 105 : | jhr | 156 | value += img[n] * (h1[0] + w*(h1[1] + w*(h1[2] + w*h1[3]))); |
| 106 : | w = f - 1.0; | ||
| 107 : | value += img[n+1] * (h1[0] + w*(h1[1] + w*(h1[2] + w*h1[3]))); | ||
| 108 : | w = f - 2.0; | ||
| 109 : | value += img[n+2] * (h2[0] + w*(h2[1] + w*(h2[2] + w*h2[3]))); | ||
| 110 : | |||
| 111 : | return value; | ||
| 112 : | } | ||
| 113 : | \end{lstlisting}% | ||
| 114 : | \end{quote}% | ||
| 115 : | jhr | 157 | \caption{Computing $F\mkw{@}x$ for a 1D scalar field in C} |
| 116 : | jhr | 156 | \label{fig:1d-probe-code} |
| 117 : | \end{figure} | ||
| 118 : | |||
| 119 : | \begin{figure}[t] | ||
| 120 : | \begin{quote} | ||
| 121 : | \begin{lstlisting} | ||
| 122 : | double4 d = (double4)(h2[0], h1[0], h1[0], h2[0]); // x^0 coeffs | ||
| 123 : | double4 c = (double4)(h2[1], h1[1], h1[1], h2[1]); // x^1 coeffs | ||
| 124 : | double4 b = (double4)(h2[2], h1[2], h1[2], h2[2]); // x^2 coeffs | ||
| 125 : | double4 a = (double4)(h2[3], h1[3], h1[3], h2[3]); // x^3 coeffs | ||
| 126 : | |||
| 127 : | double probe (double x) | ||
| 128 : | { | ||
| 129 : | double imgX = transform(x); // image-space position | ||
| 130 : | double n, f; | ||
| 131 : | |||
| 132 : | f = modf (imgPos, &n); | ||
| 133 : | |||
| 134 : | double4 v = (double4)(img[n-1], img[n], img[n+1], img[n+2]); | ||
| 135 : | jhr | 157 | double4 w = (double4)(-1.0 - f, -f, f - 1.0, f - 2.0); |
| 136 : | jhr | 156 | return dot(v, d + w*(c + w*(b + w*a))); |
| 137 : | } | ||
| 138 : | \end{lstlisting}% | ||
| 139 : | \end{quote}% | ||
| 140 : | jhr | 157 | \caption{Computing $F\mkw{@}x$ for a 1D scalar field in OpenCL} |
| 141 : | jhr | 156 | \label{fig:1d-probe-code-opencl} |
| 142 : | \end{figure} | ||
| 143 : | |||
| 144 : | \section{Probing a 3D scalar field} | ||
| 145 : | |||
| 146 : | The more common case is when the field is a convolution of a scalar 3-dimensional | ||
| 147 : | field ($F = V\circledast{}h$). | ||
| 148 : | Let $s$ be the support of $h$. | ||
| 149 : | jhr | 159 | Then the probe $F\mkw{@}\vecp$ is computed as follows: |
| 150 : | jhr | 156 | \begin{eqnarray*} |
| 151 : | jhr | 159 | \vecx & = & \matM^{-1} \vecp \qquad \text{\textit{transform to image space}} \\ |
| 152 : | \vecn & = & \FLOOR{\vecx} \qquad \text{\textit{integer part of position}} \\ | ||
| 153 : | \vecf & = & \vecx - \vecn \qquad \text{\textit{fractional part of position}} \\ | ||
| 154 : | F\mkw{@}\vecp & = & \sum_{i=1-s}^s {\sum_{j=1-s}^s {\sum_{k=1-s}^s {V(\vecn+\VEC{i,j,k}) h(\vecf_x - i) h(\vecf_y - j) h(\vecf_z - k)}}} | ||
| 155 : | jhr | 156 | \end{eqnarray*}% |
| 156 : | |||
| 157 : | \begin{figure}[t] | ||
| 158 : | \begin{quote} | ||
| 159 : | \begin{lstlisting} | ||
| 160 : | typedef double vec3[3]; | ||
| 161 : | |||
| 162 : | typedef struct { | ||
| 163 : | int degree; | ||
| 164 : | double coeff[]; | ||
| 165 : | } polynomial; | ||
| 166 : | |||
| 167 : | typedef struct { | ||
| 168 : | int support; | ||
| 169 : | polynomial *segments[]; | ||
| 170 : | } kernel; | ||
| 171 : | |||
| 172 : | double probe (vec3 ***img, kernel *h, vec3 pos) | ||
| 173 : | { | ||
| 174 : | } | ||
| 175 : | \end{lstlisting}% | ||
| 176 : | \end{quote}% | ||
| 177 : | jhr | 157 | \caption{Computing $F\mkw{@}\vecx$ for a 3D scalar field in C} |
| 178 : | jhr | 156 | \end{figure} |
| 179 : | |||
| 180 : | jhr | 159 | \section{Probing a 3D derivative field} |
| 181 : | We next consider the case of probing the derivative of a scalar field $F = V\circledast{}h$, where $s$ is the support | ||
| 182 : | of $h$. | ||
| 183 : | The probe $(\mkw{D}\;F)\mkw{@}\vecp$ produces a vector result as follows: | ||
| 184 : | \begin{eqnarray*} | ||
| 185 : | \vecx & = & \matM^{-1} \vecp \qquad \text{\textit{transform to image space}} \\ | ||
| 186 : | \vecn & = & \FLOOR{\vecx} \qquad \text{\textit{integer part of position}} \\ | ||
| 187 : | \vecf & = & \vecx - \vecn \qquad \text{\textit{fractional part of position}} \\ | ||
| 188 : | (\mkw{D}\;F)\mkw{@}\vecp & = & \left[\begin{array}{c} | ||
| 189 : | \sum_{i=1-s}^s {\sum_{j=1-s}^s {\sum_{k=1-s}^s {V(\vecn+\VEC{i,j,k}) h'(\vecf_x - i) h(\vecf_y - j) h(\vecf_z - k)}}} \\ | ||
| 190 : | \sum_{i=1-s}^s {\sum_{j=1-s}^s {\sum_{k=1-s}^s {V(\vecn+\VEC{i,j,k}) h(\vecf_x - i) h'(\vecf_y - j) h(\vecf_z - k)}}} \\ | ||
| 191 : | \sum_{i=1-s}^s {\sum_{j=1-s}^s {\sum_{k=1-s}^s {V(\vecn+\VEC{i,j,k}) h(\vecf_x - i) h(\vecf_y - j) h'(\vecf_z - k)}}} \\ | ||
| 192 : | \end{array}\right] | ||
| 193 : | \end{eqnarray*}% | ||
| 194 : | |||
| 195 : | jhr | 156 | \end{document} |
| root@smlnj-gforge.cs.uchicago.edu | ViewVC Help |
| Powered by ViewVC 1.0.0 |
