Home My Page Projects Code Snippets Project Openings diderot
Summary Activity Tracker Tasks SCM

SCM Repository

[diderot] Annotation of /trunk/doc/probe/paper.tex
ViewVC logotype

Annotation of /trunk/doc/probe/paper.tex

Parent Directory Parent Directory | Revision Log 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