Today has been a pretty good day, both for me and for my work. For the last couple of weeks I’ve been working from home because all I am doing lately is background reading and coding my new renderer. At first it was nice to know that my workspace was only a commando roll (or a fall) out of bed away from me; but after 3 weeks it just got to be a bit much. Don’t take this to mean I didn’t leave the house for three weeks, I did, but working long hours from the comfort of my room did dramatically take its toll on me.
But enough about me going mad in the house! Today I came into the office (which I think I’ll start doing a lot more often) and have made great progress on my new C++ render!
So I’m still playing with graphs in Matlab… I shouldn’t complain, I know. I should be cherishing how laid back and relaxed the PhD experience is right now compared the where I’ll be a couple of years from now.
The function f(x) is shown in green, the sample distribution in blue with histogram bins marked as circles, and the error curve in orange. Since creating these images I’ve begun drawing the error on the log x log scale which displays as a linear decay as you’d expect.
It’s still not perfect, far from it in fact, but it’s progress none the less. I’ve been reading a lot lately about Metropolis Light Transport, Manifold Exploration, Multiple Importance Sampling (they do love their M names) and it’s high time I started implementing some of them myself.
So it’s with great sadness that I am retiring my PRT project which began over a year ago, all the way back at the start of my dissertation. PRT is written in Java, for simplicity, and was designed in such a way that as I read new papers about more and more complex rendering techniques I could easily drop in a new class, add a call to the render loop, or even replace the main renderer all together with an alternative algorithm which still called upon the original framework.
I added many features over time from Ray Tracing, Photon Mapping, Phong and Blinn-Phong shading, DOF, Refraction, Glossy Surfaces, Texture Mapping, Spacial Trees, Meshes, Ambient-Occlusion, Area Lighting, Anti-Aliasing, Jitter Sampling, Adaptive Super-Sampling, Parallelization via both multi-threading and using the gpu with OpenCL, Path Tracing, all the way up top Bi-Directional Path Tracing.
But the time has taken it’s toll and too much has been added on top of what began as a very simple ray tracer. It’s time to start anew.
My plans for the new renderer is to build it entirely in C++ with the ability to easily add plugins over time like the original. Working in C++ gives a nice benefit that as time goes by I can choose to dedicate some parts of the code to the GPU via CUDA or OpenCL without too much overhead or hassle. For now though the plan is to rebuild the optimized maths library and get a generic framework for a render in place. Functioning renderers will then be built on top of the framework each implementing different feature sets and algorithms.
Continuing on from experiments last week with Metropolis Hastings sampling for probability distributions I decided to implement Accept-Reject sampling. Accept-Reject seems to deliver well distributed results faster than Metropolis Hastings does but in the long run can easily introduce biased samples if the proposal distribution q(x) is not well tuned to the specific probability distribution function. MH on the other hand, is far more resilient to an improperly chosen proposal distribution as it will still converge to an unbiased result in most cases, albeit by taking a longer time to converge than it normally would. Accept-Reject also seems to have issues towards the truncations of it’s function causing under-sampling of values close to the lower and upper bounds.
A little update on what I’ve been learning about lately.
Metropolis-Hastings is an algorithm for sampling random values out of a probability distribution. Effectively, for a function f(x) you wish to simulate where the curve is higher it is more probable that a random number will be chosen from there. Uniform sampling of the range would mean that all x values on the graph have an even probability of being chosen, this could be simulated by saying f(x) = 1.
However, if the function f(x) represents a curve then the number of samples in high energy (probability) regions needs to be more dense. This can be seen in the simulations of f(x) = sqrt(x-1) and f(x) = sin(1/x) below.
Metropolis-Hastings is best suited to problems where Direct Sampling and other more efficient solutions are not available. Because it only relies on the availability of a computable function f(x) and a proposal density Q(x|x*) M-H can correctly sample unusual probability distributions that would else-wise be difficult or impossible to compute. This can be seen below in the simulations of the sine function f(x) = sin(x) + 1.5.
Matlab code for Metropolis-Hastings Monte Carlo Integration (for generating samples)
Below is the Matlab code used to generate the above graph. By modifying the function f(x), the sample count N, the proposal distribution and it’s variance qV, and the upper and lower truncation bounds LB & HB any PDF can be simulated.
Work continues and it’s going well! Over the last week I have been teaching myself Bayesian Statistics which allows you to think about probability in terms of degrees of belief. It is also predicated on the concept of parameters, or prior known data, allowing you to update the probability of something happening in the future. This allows for convergent solutions on unknown probabilities which useful in graphics in terms of being able to fully sample arbitrary probability distributions.
I joke. So far it’s just been a lot of reading papers on graphics, most of which I do not understand. :(
Anyway, as a fun little side project I’ve been working on a 3D Ray Caster using my old favourites, OpenCL, OpenGL, and C++. It’s quite similar in concept to the renderer for my dissertation project last year but with a simplified rendering method and faster performance.
The goal for this project is to revisit Voxel Rendering which I played around with over the summer, and possibly to revisit game development with a new version of my Aliens First-Person Pacman game.
Currently the program has seven hardcoded Axis Aligned Bounding Boxes (AABB’s) which it renders as the camera orbits around them. I’m working on a method to organise AABB’s into a flat packed Oct-Tree which can be passed to the GPU. Once this is working it should be trivial to construct an AABB Oct-Tree of the CT Scanned skull I used before, or to construct a simple game.
Another thing I may look into is modifying the Aliens game to have textured floors and ceilings using floor-casting and possibly to have maps with multiple vertical levels.
Still very much a work in progress but it’s at least 99% there. And what better way to celebrate than with a round of 99 bottles of beer on the wall!
1.1 Do part 2 for a = 99(-1)2.
1.2 Do part 3.
1.3 Line.
2.1 Type a in form 1.
2.2 Type a in form 2.
2.3 Do step 4.1.
2.4 Set b = a - 1.
2.5 Do step 3.1 if b = 1.
2.6 Do step 3.5 if b != 1.
2.7 Line.
3.1 Type "1 bottle of beer on the wall".
3.2 Type "1 bottle of beer".
3.3 Do step 4.1.
3.4 Set b = 0.
3.5 Type b in form 1.
4.1 Type "You take one down, you pass it around".
Form 1:
_._ bottles of beer on the wall
Form 2:
_._ bottles of beer
The PEG.js parser is now complete!!! Now all that is left to do is write the functions for the evaluator and control flow. For now I have locked the parser to only testing commands against MathExp as the root node. The function eval_math(tree) accepts a syntax tree with a root node marked as num for a plain numerical value, var for a reference to a variable, math for a simple add/sub/mult/div between two other math trees, or function which represents a call to a math function (built into the language). Below is an overview of the parse tree for a math expression (MathExp).
Math::Number
{ tag: "num", val: 0 }
Math::Variable
{
tag: "var",
val: {
id: "a",
index: {
// Another Math Expression
}
}
}
Math::Math
{
tag: "math",
val: {
op: "+",
left: {
// Another Math Expression
},
right: {
// Another Math Expression
}
}
}
Math::Function
{
tag: "function",
val: {
func: "sqrt",
param: {
// Another Math Expression
}
}
}
Math::Function (multiple params)
{
tag: "function",
val: {
func: "min",
param: [
{}, // Another Math Expression
{}, // Another Math Expression
{} // Another Math Expression
]
}
}
Program
