MCPov

Last updated :
    12 may 2008 : version 0.0.1 released.
    15 may 2008 : version 0.0.2 released.
    18 may 2008 : version 0.0.3 released.
    01 june 2008 : version 0.0.4 released.
    05 july  2008 : version 0.0.5 released.

General description
    The ray tracing algorithm
    MCPov modifications
Diffuse contribution
    Cosine weighted sampling
    Russian Roulette
Sky importance sampling
Portals
        Triangular portals
        Spherical portals
        Bounding sphere portals
        Portal overlap
        Portal speedup
Reflective contribution
Refractive contribution
Global settings
Multi core/CPU support
Sample scenes
Limitations - bugs
Release notes
Download
Links
Contact

General description
    MCPov is a patch to MegaPov 1.2.1. MegaPov use a ray tracing algorithm to produce photo realistic pictures.
    MCPov use a montecarlo approach to evaluate the different contribution of the ray tracing algorithm.
       
    The ray tracing algorithm
        Rays are shoots from the camera through the screen pixels.
        When a ray hits an object, different rays are shoot in order to compute the pixel color  :
            - shadow rays : those rays link the hit point to the light sources and allow the light sources to 'illuminate' the hit point.
            - a reflective ray : it gives the 'mirror' contribution.
            - a refractive ray : it gives the 'transparent' contribution.
        Moreover, a ambient contribution is added in order to take into account for the multiple inter object light interactions.
        This term is constant or precomputed with the radiosity algorithm.

    MCPov modifications
        There is no shadow rays.
        The diffuse (ambient), reflective and refractive contributions are computed by shooting some rays through the hemisphere surrounding the hit point.
        The distribution of the shooted rays change with the computed contribution.
        Only the objects with an ambient term not null contribute to the pixel color.
        The computation of each pixel color is no more done one time but is a integration process.
        MCPov trace the picture again and again and accumulate the pixel color results, resulting in a montecalo integration effect.
        At the start, the picture is very noisy and improve with time.
        The rendering of a scene is endless and may be very long before reaching a acceptable low enough noise level.
       
Diffuse contribution
        At the surface hit point, the hemisphere oriented by the surface normal is sampled.
        Three possible sampling distributions are possibles : uniform (stratified sampling), cosine weighted (stratified sampling) or sky importance sampling (hdr).
        If sky importance sampling is used, it is used for all the diffuse objects defined in the scene.
        The diffuse contribution computation make the radiosity computation unnecessary.

        The diffuse contribution computation is triggered by adding a montecarlo block in a finish block as follow :
            finish { montecarlo { mc_diffuse { on_off n1 n2 } [mc_use_cosine_distrib] } }
            with :
                on_off = [0|1] : turn on or off the computation.
                n1 : the number of raws and lines of the stratified sampling grid in case of a hitting primary ray (origin from the camera).
                n2 : the number of raws and lines of the stratified sampling grid for the other hitting rays.
                The number of shooted rays is then n1.n1 or n2.n2.
                mc_use_cosine_distrib : use a cosine distribution if present.
            examples :
                finish { montecarlo { mc_diffuse { 1 3 1 } } }
                finish { montecarlo { mc_diffuse { 1 2 2 } mc_use_cosine_distrib } }


    test scene : test_01.01a.pov, 30 seconds rendering.




              Cosine weighted hemisphere sampling
The use of the keyword mc_use_cosine_distrib activate the cosine weighted hemisphere sampling.
It should reduce the noise quickly than a uniform sampling.

                    test scene : test_01.01b.pov, 30 seconds rendering.
                   
                    With mc_use_cosine_distrib keyword, 30 seconds rendering :

 

                   
                    Without mc_use_cosine_distrib keyword, 30 seconds rendering :


                    The use of the cosine weighted sampling doesn't improve something : implementation problem ?.

              Russian roulette
                    The russian roulette optimisation allow to not follow path with low contribution to the final pixel color.
                    The choise to stop a path with a low contribution is done randomly.
                    The russian roulette feature is controlled with 2 parameters in the global setting block :

                        global_settings
{

                          ...
                          montecarlo
                          {
                              mc_russian_roulette_prob stop_probability
                              mc_russian_roulette_threshold 
contribution_threshold
                              ...
                          }
                         
contribution_threshold : define the threshold on the contribution to the pixel to trigger the russian roulette optimisation.
                          stop_probability : the probability of stopping the path (1.0 means 100% of chance).
                         
                         example : global_settings { montecarlo { mc_russian_roulette_prob 0.75 mc_russian_roulette_threshold  0.15 } }

                          By default, mc_russian_roulette_prob is set to 0.5 and mc_russian_roulette_threshold to 0.1.

                          Causion :
do not increase to much the rejection probability, it may results in bright pixels.

              Sky importance sampling
When a sky is define with a hdr bitmap, the sampling of the brighter parts of the picture reduce the noise.
The use of the keyword mc_sky activate the sky importance sampling :

    finish { montecarlo { mc_sky { sky_grid_dimension } } }
    sky_grid_dimension : define the grid dimension for the build of the importance sampling distribution. Should be lower or equal to 1000.

    example :
finish { montecarlo { mc_sky { 1000 } } }

If both the sky importance sampling and the cosine weighted sampling is used, sky importance sampling is used.

test scene : sky.pov (hdr file available here), 1 minute rendering without the use of the mc_sky keyword :


test scene : sky.pov (hdr file available here), 1 minute rendering with the use of the mc_sky keyword :

    Portals
As shown in the previous pictures, the contribution of an object with ambient term is difficult to catch if the emitting object is small or far from the hit point (most of the ray miss the object).
A portal define an area on the hemisphere that is sampled in priority with a latin hypercube sampling pattern.
A portal is an object. This object may be visible or not.
For instance, a portal may be (or surround) :
- a small object with ambient term.
- a refractive object.
In the first case, it reduces the noise and in the second case it helps the caustic resolution.



There are 3 types of portals :

    Spherical portals
        It is a sphere object define as follow :
            sphere { c, r
                montecarlo  {  mc_portal { n1_max n2_max n1_min n2_min }  }
                ...
            }
        The montecarlo block must be just after the sphere radius.
        With :
            n1_max : the maximum number of rays when the hitting ray is a primary ray (origin from the camera).
            n2_max : the maximum number of rays for the other hitting rays.
            n1_min : the minimum number of rays when the hitting ray is a primary ray (origin from the camera).
            n2_min : the minimum number of rays for the other hitting rays.

        test scene : test_01.02.pov, 30 seconds rendering :


   Triangular portals
        It is a triangle object define as follow :
            triangle { p1, p2, p3
                montecarlo  {  mc_portal { n1_max n2_max n1_min n2_min }  }
                ...
            }
        The montecarlo block must be just after the last triangle point.
        n1_max, n2_max, n1_min and n2_min have the same meaning than for a spherical portal.
      
        test scene : test_02.pov, 30 seconds rendering :


    Bounding sphere portals
        A bounding spherical portal is defined around an object as follow (with the example of a box) :
            box { p1, p2
                ...
                montecarlo  {  mc_portal { n1_max n2_max n1_min n2_min }  }
                ...
            }
        The montecarlo block may be place anywhere in the object block description.
        n1_max, n2_max, n1_min and n2_min have the same meaning than for a spherical portal.
                  Caution : If a bounding sphere portal is defined on a triangular or spherical portal, 2 portals are defined for the same object.

                  test scene : test_03.pov, 2 minutes rendering :


Portal overlap
In case of portal overlap, the standard algorithm introduce errors (some points received n times the same contribution).
The use of the keyword mc_check_portal_overlap solve this problem.

Test scene : test_04.pov, 30 seconds rendering. We see that the points outside the 2 portals are too bright when comparing to the inside ones :

                   
                    Test scene : test_04.pov, 30 seconds rendering. Same setting with the mc_check_portal_overlap keyword activated :


            Portal speedup
            Portals are heavy in computational.
            It is possible to not use the portals on path with small contribution to the pixel color.
            In this case, the diffuse contribution is computed by shooting random ray without special care for the portal.
            The feature is controlled with 2 keywords in the portal block, by default no optimisation is done :

                montecarlo  {  mc_portal { ... mc_max_light max_portal_ambient_light mc_light_cutoff min_pixel_contrib }  }
                With :
                    max_portal_ambient_light : maximum ambient light that may goes through the portal.
                    min_pixel_contrib : minimum pixel contribution that trigger the no more use of the portal.
               
                exemple : mc_portal { ... mc_max_light 20 mc_light_cutoff 0.01 }

Reflective contribution
        The computation of the reflection contribution is deactivated by default.
        When deactivated, the standard algorithm is used (one ray is shoot in the reflection direction).
        When activated, at the surface hit point, the hemisphere oriented by the surface normal is sampled with a stratified sampling pattern around the reflection direction.

        finish { ...  montecarlo { mc_reflect on_off n1 n2 exponent } } ... }
       With :
           on_off = [0|1] : turn on or off the computation.
           n1 : the number of rays for a primary hitting ray (origin from the camera).
           n2 : the number of rays for the other hitting rays.
           exponent : gives the sharpness of the reflectivity along the reflection direction (1 produce a reflection in all the direction).

       example :  finish { ...  montecarlo { mc_reflect { 1 3 1 100 } } ... }

Refractive contribution
        The computation of the refraction contribution is deactivated by default.
        When deactivated, the standard algorithm is used (one ray is shoot in the refraction direction).
        When activated, at the surface hit point, the hemisphere oriented by the surface normal is sampled with a stratified sampling pattern around the refraction direction.

        finish { ...  montecarlo { mc_refract on_off n1 n2 exponent } } ... }
       With :
           on_off = [0|1] : turn on or off the computation.
           n1 : the number of rays for a primary hitting ray (origin from the camera).
           n2 : the number of rays for the other hitting rays.
           exponent : gives the sharpness of the refractivity along the refracted direction (1 produce a refraction in all the direction).

        example :  finish { ...  montecarlo { mc_refract { 1 3 1 500 } } ... }

Global settings
global_settings {
...
  montecarlo
  {
    mc_rand_seed                                                                  // the C random sequence is seed with the current time
    mc_max_diffuse_bounce 3                                              // max number of diffuse bounce
    mc_pixel_refresh_ratio 0.5                                              // ratio of pixels computed at each iteration (try to reduce noise first)
    mc_dof { mc_focal_distance 20.0 mc_lens_radius 0.5 } // depth of  field
    mc_max_diff_stop_value 0.05                                        // stop criteria
    mc_max_pass 1000                                                         // max iteration
    mc_colour_clip 1.0                                                          // max rgb color  for clipping
    mc_check_portal_overlap                                               // handle portal overlap
    mc_sort_portals                                                               // sort portal before use
   
mc_russian_roulette_prob 0.5                                         // probability of path stopping
    mc_russian_roulette_threshold 0.1                                 // threshold on pixel contribution to start russian roulette
  }
...
}

keywords default values Explanation
mc_rand_seed deactivated Initiate the random sequence used by the montecarlo algorithm with the current date.
mc_max_diffuse_bounce 3 Max number of diffuse rays in  the path.
The path may also include reflected and refracted rays.
The total max path depth is limited by the max_trace_level keyword.
Maximum value : 125.
mc_pixel_refresh_ratio 1.0 Define the ratio of the pixels to refresh at each iteration (1.0 -> 100%, 0.5 -> 50%).
Every 5 iterations, all the pixels are refreshed.
mc_dof
      mc_focal_distance
      mc_lens_radius

0.0
0.0
To activate depth of field effect computation.
      Gives the distance from the camera to the point in focus. Should be greater than 0.0.
      Gives the radius of the lens (to increase in order to increase the effect). Should be greater than 0.0.
mc_max_diff_stop_value -1.0 Define a rendering stop criteria based on the noise level. Dependant of mc_pixel_refresh_ratio.
mc_max_pass 0 Define the maximum number of pass before the rendering stops.
The rendering never stops if null or negative.
mc_colour_clip 0.0 Define the max value for RGB components. 0.0 deactivate the clipping.
Introduce a bias in the rendering.
Useful with scenes producing bright spots.
mc_check_portal_overlap deactivated See more explanation here.
mc_sort_portals deactivated Experimental...
mc_russian_roulette_prob 0.5 See more explanation here.
mc_russian_roulette_threshold 0.1 See more explanation here.

Multi core/CPU support
MegaPov 1.2.1 doesn't support natively a multi core/CPU rendering.
Nevertheless, the montecarlo integration make easy the use of multi cores/CPUs.
Follow two possible solutions :
- SMPOV : the picture is split and rendered on the different cores. The disaventage is that if some parts are longer to render, the noise doesn't reduce at the same rate. It may be visible when the picture is reassembled.
- Run an instance of  MCPov on each available core/CPU and render different times the same scene. Include in your scene the keyword mc_rand_seed in order to initiate the random number generator differently. Reassemble the different computed pictures in one picture by merging them in any picture manipulation tool (for instance Paint.NET). The disaventage of the method is that the final noise level is not visible without a merging of the pictures (but it is possible to make picture copies and a merging without stopping the rendering).

Sample scenes
All scenes rendered on 1 core of a Intel Q6600 2.4 GHz, 4 GB of RAM.

sample_01.pov 2 spherical portals
portal overlap
1 hour 30 min rendering (version 0.0.4)
sample_02.pov 1 spherical portal
30 min rendering (version 0.0.4)
Depth of field
sample_03.pov 1 spherical portal
2 hours rendering (version 0.0.4)
sample_04.pov 1 spherical portal
2 hours and 30 min rendering (version 0.0.4)
sample_05.pov 1 spherical portal
distributed reflection
30 min rendering (version 0.0.4)
sample_06.pov 1 spherical portal
distributed refraction
2 hours rendering (version 0.0.4)
sample_07.pov hdr lighting
distributed reflection
1 hour and 30 min rendering (version 0.0.4)
hdr file available here
sample_08.pov 1 bounding sphere portal
30 min rendering (version 0.0.4)
sample_09.pov hdr lighting
distributed reflection/refraction.
color clipping
2 hours rendering (version 0.0.4)
hdr file available here
sample_10.pov 4 triangular portals
russian roullette (set to default values)
portal optimisation
use of the maximum diffuse bounce (125)
30 min rendering (version 0.0.5)


Limitations - bugs
This patch is experimental and has some limitations, bugs and some features of MegaPov 1.2.1 may have been changed or are no more working correctly :
    - Maximum number of portals per scene : 10.
    - Maximum number of samples per portal : 256.
    - Radiosity : should not be used (unnecessary).
    - Antialiasing : should not be used (unnecessary). MCPov do it for all rendered scenes.
    - Photon : incompatible in its current implementation.
    - Media : seems no more working correctly.
    - Object with ambient term : if the patch is not activated in a scene, the ambient term is not taken into account.
    - The PovRay light models (point light, etc.) are not supported.
    - Continuing a trace ( +c ) doesn't work.

Release notes
    12 may 2008 : version 0.0.1
        initial release.
    15 may 2008 : version 0.0.2
        - compile now correctly under Linux.
        - use of  a fast high-quality RNG as provided by Warp (the original RNG algorithm and implementation is by Bob Jenkins).
    18 may 2008 : version 0.0.3
        - bugfix : sometimes wrong results when depth of field is activated.
        - bugfix : wrong results if a CSG object is defined as portal.
        - bugfix : segmentation fault if the mc_sky keyword is used in a CSG object.
        - bugfix : wrong results with mc_sky.
        - Max grid dimension for sky is now 1000 (instead of 100).
              01 june 2008 : version 0.0.4
                  - bugfix : crash in some resolution (for instance 240x320).
              05 july 2008 : version 0.0.5
                  - bugfix : crash with high mc_max_diffuse_bounce. Now max value is 125.
                  - compilation : problem with gcc 4.3.1.
                  - speedup : russian roulette optimisation added.
                  - speedup : new keywords mc_max_light and mc_light_cutoff for stop using portal when comtribution negligeable.
                  - speedup : new keywords mc_russian_roulette_prob and mc_russian_roulette_threshold  for control of the russian roulette feature.

Download
Source file modification (the complete source are available here) :
        sources version 0.0.1
        sources version 0.0.2
       
sources version 0.0.3
        sources version 0.0.4
        sources version 0.0.5

Windows binary, only tested on Intel CPU (Pentium M and Q6600) and Windows XP/Vista :
        binary version 0.0.1
        binary version 0.0.2
       
binary version 0.0.3
                binary version 0.0.4
                binary version 0.0.5

Links
PovRay raytracer
MegaPov raytracer : introduce valuable extension to PovRay (hdr support, etc.).
PovRay Newsgroup : Newsgroup of the PovRay community. Good entry point for help with PovRay use.
Luxrenderer : Open-source free unbiased renderer.
Indigo : Free unbiased renderer.
Monte Carlo Siggraph course : gives math background for implementation.

Contact
          For bug reports, advices, comments, result infos, etc.
          Please include the string "MCPov" in your email header for easy SPAM filtering

mcpov@orange.fr