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

SCM Repository

[diderot] Annotation of /branches/pure-cfg/doc/field-norm/paper.tex
ViewVC logotype

Annotation of /branches/pure-cfg/doc/field-norm/paper.tex

Parent Directory Parent Directory | Revision Log Revision Log


Revision 471 - (view) (download) (as text)
Original Path: trunk/doc/field-norm/paper.tex

1 : jhr 468 \documentclass[11pt]{article}
2 :    
3 :     \setlength{\textwidth}{6in}
4 :     \setlength{\oddsidemargin}{0.25in}
5 :     \setlength{\evensidemargin}{0.25in}
6 :     \setlength{\parskip}{5pt}
7 :    
8 :     \input{defs}
9 :    
10 :     \title{Normalization of Field and Probe Expressions}
11 :     \author{
12 :     John Reppy \\
13 :     University of Chicago \\
14 :     {\small\tt{}jhr@cs.uchicago.edu} \\
15 :     }
16 :     \date{\today}
17 :    
18 :     \newcommand{\Fnorm}[1]{\mathcal{F}\LDB{}#1\RDB{}}
19 :     \newcommand{\Pnorm}[1]{\mathcal{P}\LDB{}#1\RDB{}}
20 :    
21 :     \begin{document}
22 :    
23 :     \maketitle
24 :     \thispagestyle{empty}
25 :    
26 :     \bibliographystyle{../common/alpha}
27 :     \bibliography{../common/strings-short,../common/manticore}
28 :    
29 :     \section{Introduction}
30 :    
31 :     This note describes the symbolic transformations that are applied to field and probe expressions in
32 :     the Diderot compiler.
33 :     The purpose of these transformations is to make the actual compilation of probe operations
34 :     more straightforward.
35 :     We describe these transformations using three simple expression languages.
36 :     The first corresponds to the Diderot surface-language syntax for field and probe expressions.
37 :     The second language has the property that derivative operations have been pushed down to the
38 :     convolution kernels, and the third language reduces probes to work on images.
39 :    
40 :     \section{The formal model}
41 :    
42 :     In the discussion below, we use a number of notational conventions that are
43 :     summarized in the following table:
44 :     \begin{center}
45 :     \begin{tabular}{cp{4in}}
46 :     $V$ & an image \\
47 :     $F$, $G$ & fields \\
48 :     $h$ & a piecewise polynomial convolution kernel \\
49 :     $s$ & a scalar \\
50 :     $\vecx$ & a position in world space
51 :     \end{tabular}%
52 :     \end{center}%
53 :    
54 :     The source language of field expressions is
55 :     \begin{displaymath}
56 :     \begin{array}{rcll}
57 :     F & ::= & V\circledast{}h & \text{convolution} \\
58 :     & \mid & F+G & \text{addition} \\
59 :     & \mid & s F & \text{scaling} \\
60 :     & \mid & \nabla{}F & \text{differentiation}
61 :     \end{array}%
62 :     \end{displaymath}%
63 :     We normalize these expressions by pushing the differentiation operators down to the
64 :     kernels, which results in the following language of field expressions:
65 :     \begin{displaymath}
66 :     \begin{array}{rcll}
67 :     \hat{F} & ::= & V\circledast{}h^k & \text{convolution with $k$th derivative of $h$} \\
68 : jhr 471 & \mid & \hat{F}+\hat{G} & \text{addition} \\
69 : jhr 468 & \mid & s \hat{F} & \text{scaling} \\
70 :     \end{array}%
71 :     \end{displaymath}%
72 :     The normalization rules are as follows:
73 :     \begin{eqnarray*}
74 :     \Fnorm{\nabla{}(V\circledast{}h^k)} & = & V\circledast{}h^{k+1} \\
75 :     \Fnorm{\nabla{}(F+G)} & = & \Fnorm{\nabla{}F} + \Fnorm{\nabla{}G} \\
76 : jhr 469 \Fnorm{\nabla{}(s F)} & = & s (\Fnorm{\nabla{}F})
77 : jhr 468 \end{eqnarray*}%
78 :    
79 :     The syntax of probe operations (after field normalization) is
80 :     \begin{displaymath}
81 :     \hat{F}\mkw{@}\vecx
82 :     \end{displaymath}%
83 :     We normalize these expressions by pushing the probes down to the leaves
84 :     and rewriting them as probes into images with the following syntax
85 :     \begin{displaymath}
86 :     V\mkw{@}_{h^k}\vecx
87 :     \end{displaymath}%
88 : jhr 469 The probe normalization rules are as follows:
89 : jhr 468 \begin{eqnarray*}
90 :     \Pnorm{(V\circledast{}h^k)\mkw{@}\vecx} & = & V\mkw{@}_{h^k}\vecx \\
91 : jhr 471 \Pnorm{(\hat{F}+\hat{G})\mkw{@}\vecx} & = & \Pnorm{\hat{F}\mkw{@}\vecx} + \Pnorm{\hat{G}\mkw{@}\vecx} \\
92 :     \Pnorm{(s \hat{F})\mkw{@}\vecx} & = & s (\Pnorm{\hat{F}\mkw{@}\vecx})
93 : jhr 468 \end{eqnarray*}%
94 :    
95 : jhr 469 \section{An example}
96 :     Consider the following Diderot fragment (taken from the \texttt{vr-lite.diderot} example).
97 :     \begin{lstlisting}[mathescape=true]
98 :     $\cdots$
99 :     field#1(3)[] F = img $\circledast$ bspln3;
100 :     $\cdots$
101 :     real val = F@pos;
102 :     vec3 grad = ($\nabla$ F)@pos;
103 :     \end{lstlisting}%
104 :     Applying the transformations will result in
105 :     \begin{lstlisting}[mathescape=true]
106 :     real val = img $\mkw{@}_{\mathtt{bspln3}}$ pos;
107 :     vec3 grad = img $\mkw{@}_{\mathtt{bspln3}^1}$ pos;
108 :     \end{lstlisting}%
109 :    
110 :    
111 : jhr 468 \section{Implementation in the compiler}
112 :     These transformations are mostly implemented on the SimpleAST representation.
113 : jhr 469 The final step of translating a probe of $(V\circledast{}h^k)\mkw{@}\vecx$
114 :     to $V\mkw{@}_{h^k}\vecx$ is done in the conversion to the HighIL representation.
115 : jhr 468
116 :     \end{document}

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