 |
What is the Raytrix |
 |
The
Raytrix
With Monte Carlo
techniques, path tracing, and other time consuming techniques for
finding rays that origin from a light source, ray tracing begs the
question: how complex is it to find the destination of a ray given
its source, or vice versa.
Reif,
Tygar and Yoshida show that it is not only time consuming to
determine the destination of a ray from its input location, but that
it is undecidable. They accomplish this proof by using a ray fired
into a specific scene to simulate the universal Turing
machine.
The idea is as follows:
The entire computers memory
is saved as two stacks, each saved in the fraction of the ray's X
and Y position respectively. If a ray were at x=1011010111.11001
y=111.1011 (in decimal x=727.78125 y=7.6875) then the X stack would
have 1100100000.... and the Y stack would have 1011000000000.... on
it.
Given unlimited precision, this can easily hold the whole
Turing machine's tape, with the head pointing to the gap between the
X and the Y stacks. The stack may be manipulated as follows:
There are 3 basic commands:
- if(top) redirect beam:
- add k to stack:
- push (or pop) stack: (multiply or divide ray position by 2)
This functions by having 2 parabolas of different sizes which
share a focus.
Each operation may be chained by mirrors and each
operation may be performed on either the X or Y position
independently. Thus the machine is a Turing
machine.
|
Nondeterminism
However, the machine has another
powerful function that was not addressed in the paper: It has the
ability to act as a nondeterministic Turing machine by using
partially transmissive surfaces (like glass). assuming an input with
the top bit off (binary representation 101110101011.011101101 first
digit after . is zero) The fork device shown below can split the
beam and allow two beams to continue through the entire
machine.
The
Fork Instruction operates by using a partially reflective surface to
bounce the light perpendicular, then bounces it around and adds .5
on the way. That way the top most bit will end up with both zero and
one. After the fork instruction another push may be executed, and so
forth to fill up an arbitrary number of bits with both zero and one
values. Here is an example of a number of fork commands being
chained to result in 16 rays with the first four bits in both x and
y being set to all possibilities.
(Image Height
Stretched to 2x)
In this way it is possible to solve problems
in NP with only polynomial bounces per ray, resulting in a total
polynomial number of bounces to solve the problem. So it became my
goal to write a 3sat solver that used only polynomial number of
bounces |
Compiler Tool-chain
To write a program with the complexity
of 3-sat some assistance from a compiler is in order: manually
placing the mirrors one by one would be error prone and tedious.
Instead I designed a compiler to do this for me. The entire
tool-chain was written in the D programming language, a
language still in alpha testing and undergoing a lot of
flux--however also a clean high level language with careful typing
rules and templates (both a requisite for a large project).
I
began with writing the simulator: i.e. the ray-tracer itself. The
reason I could not use PBRT is that the entire memory was stored as
a single number; therefore a float would not be sufficient to hold
this memory--and I would have to refrain from doing approximations
like square roots and actually calculate the exact answers. I
started with an alpha-version D
BigInteger class and built upon it a templatized Big Rational,
that allowed division, mult, add, sub, and even sqrt if the fraction
was square. On top of this I built a template class for vector types
with the exact interface that Cg has (it turns out that D is a
superset of Cg's functionality!). So I ended up using rational3
vectors for all my computation. Then I wrote a ray-tracer that could
intersect rays with axis-aligned parabolas and arbitrary quads. The
interface was the same as PBRT with the DifferentialGeometry class
returning a normal to be reflected over and a material property
BSDF. I wrote part of a uniform grid implementation, but decided it
would be best to wait until things were actually going slowly than
to waste time now optimizing if necessary.
With the test system
in place, I could fork rays, multiply them, add them, and build
conditionals. I wrote little assembly statements by grouping
together mirrors into 3x4x2 blocks to perform such tasks. All
mirrors had closed edges, meaning that sometimes extra space was
necessary to avoid edge cases failing. I ended up with 8 commands
that could each produce part of a scene file:
noop
kill (black
surface destroys ray)
loop (reflect beam up and redirect to start
of program)
invert (flop top bit on either x or y)
mod5 (set
top bit to zero)
agetsb (set top bit of one stack to top bit of
the other)
if (if the top bit of one stack is one redirect to
another codepath)
fork (sets top bit to both zero and one and
doubles simulated # of rays)
plusgets (adds a bit pattern to the
stack)
mulgets (divide or multiply the stack by a
value)
|
I combined these very low level commands into more
useful commands that could be chained together by some C++
code:
< var> indicates to which stack the instruction will
apply
< index> indicates to which bit in the stack the
instruction will apply
If (< var>, < index> ); Checks
if the indexth bit of stack var is set. if so execute code until
EndIf
IfPop (< var>, < index> ); Checks if the
indexth bit of stack var is set and pops it. If so execute code
until EndIf
EndIf(); Loops to the beginning of the
program
Pop(< var > ); pops value from the < var>
stack
PopXX(< var > , num); pops num values from <
var> stack
void PushXX(< var >, value, nbits); pushes
nbits of bit pattern contained in value onto stack
Fork(< var
>, < index> ); Sets indexth bit to both zero and
one
Exit(); Terminate ray with
failure
|
With these eight commands that were made of the
previous nine, I was able to program 3-sat in assembly.
Each of
the instructions printed itself to a scene file with the appropriate
location determined by the layout algorithm below, and each
instruction also wrote itself out as a D array command, since D
arrays had all the functionality of stacks. So I could test the
output program as either a native x86 executable or as a raytraced
(interpreted) scene file. This helped me write 3-sat
I had to
write a layout algorithm that would lay out these carefully pieced
together commands into a larger map. I accomplished this by keeping
the invariant that each piece would be farther along in z, and
potentially father along in x, but never decreasing in x nor
increasing or decreasing in y. With this invariant, layout became
trivial: I would layout the next item in z that was greatest in x
and all of its children first, then I would layout the item lesser
in x at the farthest unused z value. This would ensure an O(n) time
layout of the building blocks of the programs. Since loops only
looped to the beginning it was trivial; however, I had a mechanism
for making looping constructs jump anywhere, I just did not
implement it. This would have involved pushing the address of the
desired instruction and then magnifying the ray until it hit the
exact destination instruction location.
My first
successful program was the loop x=y, where x's value would be copied
to y. The result of the run of the program is illustrated below: the
ray is dyed by time, the darker, the more intersections it had to
perform. The output is indicated with "END". 
It
literally loops around 10 times, and it really brings to light why a
loop is so named.
| |
