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

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0