Good times with weapons

It was hard time to upgrade for Vista and Visual Studio 2008, I had to recompile all the libraries (linker errors – there are some incompatibilities between VS2005 and VS2008 linker).
I fixed method, make it accurate, finished writing and submitted PhD, now I am waiting for reviews.
I am going to start my own project, based on the new method I have in my head already growing.
First step will be optimizing current raytracer core code (yeah it is high time for better SAH based KD-tree) .

Oh I forgot to say, finally paper is accepted for conference!

Picture below is accuracy test, on the left Monte Carlo path-tracing (50 samples per pixel), the middle one is photon
lightcuts, and the right one is the voxel lightcuts method.

Overall method preview:

Boost your raytracer

You can speed up a bit (6-10% maybe) your current raytracer by changing simple linear pixel rendering order into hilbert curve (in that case data are more coherent and there are less cache misses). I did not believe that until I try it.

Here is my Hilbert curve class (drop me a line if you find it usefull):

#ifndef HILBERT_H_
#define HILBERT_H_

class Hilbert
{
public:
    Hilbert(int dx,int dy)
    {
        nXDim  = dx;
        nYDim  = dy;
        int m  = dx>dy ? dx : dy;
        int nOrder = 1;
        while ((1<<nOrder)<m) nOrder++;        

        pPointsX = new int[dx*dy];
        pPointsY = new int[dx*dy];
        nX = 0;
        nY = 0;
        nPoints = 0;

        hilbert(nOrder, NORTH, EAST, SOUTH, WEST);
    }

    ~Hilbert()
    {
        if (pPointsX) delete []pPointsX;  pPointsX = NULL;
        if (pPointsY) delete []pPointsY;  pPointsY = NULL;
    }

    int *GetX() { return pPointsX; }
    int *GetY() { return pPointsY; }
    int Count() { return nPoints;  }

private:
    int nXDim,nYDim;

    int *pPointsX;
    int *pPointsY;
    int  nPoints;

    int curvesize(int ord) {    return (1<<ord) - 1;    }

    static const int NORTH=0, EAST=1, SOUTH=2, WEST=3;
    int nX,nY;

    void move(int d)
    {
        // Move one unit in direction d from point lastpoint.
        switch (d)
        {
          case NORTH: nY--;  break;
          case EAST:  nX++;  break;
          case SOUTH: nY++;  break;
          case WEST:  nX--;  break;
        }
    }

    void hilbert (int i,      // order of Hilbert curve to be drawn
                  int front,  // direction at front
                  int right,  // direction at right
                  int behind, // direction at back
                  int left)   // direction at left
    {
        if (i == 0)
        {
            if (nX<nXDim && nY<nYDim) // cut to image only
            {
                pPointsX[nPoints  ] = nX;
                pPointsY[nPoints++] = nY;
            }
        }
          else
        {
          hilbert(i-1, left , behind, right , front );    move(right );
          hilbert(i-1, front, right , behind, left  );    move(behind);
          hilbert(i-1, front, right , behind, left  );    move(left  );
          hilbert(i-1, right, front , left  , behind);
        }
    }
};

#endif

There are a lot of changes in the project I will write more about it soon, lightcuts works great,
some new images generated (including our new kitchen visualization designed by my wife):

So you wanna be a rockstar (Lightcuts implementation)

Finally, I implemented “Lightcuts: a scalable approach to illumination” paper . It took me two weeks and several nights (working during late night is not very healthy but extremely efficient). It would not be possible without great help of ANL and Thomas and his amazing blog. It would be also very hard without this paper (Implementing Lightcuts – Miksik M. (2007)).

First attempts was not very promising:

After four days it start to work (with o(n^3) cut tree creation complexity, and wrong distance bounding). Then I focused on writing optimal cut tree creation. When I get o(n log n) it start to be usable.

Implementing oriented lights bounds took me another week. Finally it start to work.

6207 lights (voxels) overall time: 323.89 sec, propagation time: 2.51 sec, avg cut size 288 (this number of lights per pixel was actually computed)

55334 lights (voxels) overall time: 977.87 sec, propagation time: 37.59 sec

155731 lights (voxels) overall time: 2748.81 sec, propagation time: 341.79 sec

Next steps:

• optimization of everything (shadow rays instead of full one and so)
• adaptive anti-aliasing
• testing environment/day light
• multi threaded rendering
• reconstruction cuts (maybe)

Bad day in L.A.

We’ve got notification from EG08 conference, paper was rejected. It was definitely worth to submit there, reviews are amazing, a lot of references/ideas and related comments from people that know the theme. At least nobody write “there are another methods to solve the problem” like in notification from the other conference. That makes a difference of submitting for good conferences (you have slight chances for paper being accepted but you can learn a lot).

The main disadvantage was that method is too slow comparing to the well known methods.

How it works:

1. First we discretize scene into set of voxels:

2. Then light is propagated over voxels, first pass for shooting, and then I linear propagation steps. Gathering overall complexity O(I*V*D) , where I is the number of iterations, V number of voxels, and D number of directions. This is optimal linear complexity for full propagation (every voxel at every direciton).

3. Instant Radiosity gathering pass is used for final image rendering.

This step is slowest. In some cases we need to compute hundreds of thousands of rays for single pixel. Since rendering is progressive first results (after first 16 virtual point lights) are visible after seconds, but to converge we need to wait a lot more (specially for more complex scenes).

That make me think of Instant Radiosity as a method well suited for rough previews not for final quality rendering.

There is well suited method: Lightcuts, I start to implement it yesterday and seems to be very promising.

Other project news:

- AntTweakBar upgraded to the latest version

- MiniLight (Monte Carlo path-tracer) used as reference images calculator

- P3 great tone mapper (from the same author), in most cases produces better images then OpenEXR, and does not require as many parameters

How to hunt memory leaks using Visual Studio

Make sure you compile debug version of your project.

Press F5 (Start Debugging)

Do whatever you suspect to leak memory, and close program.

In output window you should see:

Detected memory leaks!
Dumping objects ->
{8677} normal block at 0x01AA4E08, 68 bytes long.
Data: < > CD CD CD CD CD CD CD CD CD CD CD CD CD CD CD CD
Object dump complete.

Add:

#ifdef _DEBUG
#define _CRTDBG_MAP_ALLOC
#define _INC_MALLOC
#endif


in your stdafx.h file, and recompile whole solution.

Now it should be something like:

Detected memory leaks!
Dumping objects ->
C:\Program Files\Microsoft Visual Studio 8\VC\include\crtdbg.h(1147) : {8677} normal block at 0x01AA4E08, 68 bytes long.
Data: < > CD CD CD CD CD CD CD CD CD CD CD CD CD CD CD CD
Object dump complete.

The problem is it shows allocator code, not your allocation itself. Still not very usefull. Now tricky part. Double click

C:\Program Files\Microsoft Visual Studio 8\VC\include\crtdbg.h

line. Set a trap (F9/Debug->Toggle Breakpoint) right click on the red dot and select condition and type _Size==<your leak size in this case 68>. Next time you will debug, program will stop if there will be 68 bytes allocated, then you can select Debug->Windows->Call Stack and if you are lucky you will see your memory leak.

Project news:

• fixed memory leaks

• wxWidgets upgraded to 2.8.3

• fixed hierarchy while 3ds loading

• about 40% memory saved (scene class)

• accurancy upgraded from float to double in most cases

• Material and Texture class refactored

Some test images:

Goodbye horses

I watched this (Revolution OS):

and Pirates of Silicon Valley, and decided to create Linux version of the Voxelizator3D.

Finally mfc is removed (rest in peace). I was looking for crossplatform GUI for a long time. The must have was:
- free (open source + ability to use in closed code)
- C++
- crossplatform
- OpenGL support
- fast, nice ,native , and active (it is good to learn something that will be alive in next 2 years)

Why crossplatform code is important, in spite of possibility to use it by more people?

The good crossplatform code should be:
- better planed/written,
- data and code logic separated,
- should not rely too much on anything except some base libraries (good – if mature and crossplatform).

In that case there is a great chance that you can port it to your fridge in next ten years or any new system/hardware that can show in the future. Another advantage is, you can test it on several platforms, each have own its memory management, so errors like memory leaks can be easy found (nice tool).

Preparation:
- wmWare player
- ubuntu 6.10 desktop virtual image
- updating ubuntu
- code::blocks
- wxWidgets

Two weeks later, first version run on Ubuntu, and it crashes in three places (yes,yes,yes…).

“I put my blood into this.”

This sentence is said by Michael Scofield in one part of the “Prison Break”. It is said at the moment it looks like he do not have any chances, and all he can do is to give up. Although the way he said that, sound like he never give up and it is absolutely impossible to waste all his work he made up to the time. So? The clue is, never give up folks.

Ashikhmin & Shirley “An Anisotropic Phong BRDF Model” implementation seems to be ready, and it is still noise free…

Divide and conquer

Maintenance almost finished.
Voxelizator has been divided into several libraries:
Import (import of .s3d,.3ds,.mgf,.3dd,.obj,.rtg,.ply), includes lib3ds, for now .obj and .mgf files seems to be most useful for me
OpenGL (OpenGL and its extensions manager)
Pics (most known bitmap files and .exr files manager), includes FreeImage and OpenEXR
Radio (main new voxel radiosity method/brdf material manager), will be used soon very extensively
SRay (kd-tree based raytracing speed/correctness benchmark)
Voxelizator (main program, includes Import.lib, Pics.lib, Tinyxml.lib, opengl32.lib, Radio.lib, glfwdll.lib, AntTweakBar.lib, glu32.lib)
Code compiles a way faster, get some of its previous logic, and is easiest to control.

Also texture filtering has been done, you can compare the results here:

Render preview window has been completely rebuilded, now it uses AntTweakBar library, that allow to adjust tone mapping settings in real time:

Refractions

Seems like I get hacked into refractions, still some work to do (look at glass.png).
Antyaliasing is turned off. What next, BRDF/bitmap lighting?

Reflections

Reflections seems to be ready, still to do some work with refractions, and anoying far intersection KD-Tree bug…