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
 [diderot] / branches / pure-cfg / doc / field-norm / paper.tex

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

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