CPS615 - Fall 96 project -- Parallel Ray Tracing using HPF

Kayasidh Kasyapanun

Ray Tracing

In the real world, a point on a surface can be seen by an observer as a result of the interaction of the surface at that point with rays. There are many surface reflection model to simulate the illumination- reflection model in computer graphics. The Ray Tracing model is currently the most complete one. The difference of Ray Tracing from other model is the 'depth' to which interaction between light rays and objects in the scene is examined. There are also many disadvantages in Ray Tracing model. One of them is the processing overheads. Ray-traced images may take many minutes, hours or even days to cumpute. The significant advantage is that it combines several solutions for the global illumination problem.

Hidden surface removal.
Shading due to direct illumination.
Shading due to global illumination.
Shadow computation.

Algorithm

At a given point in the image, the color and intensity are obtained by tracing the ray backward form the eye (viewpoint) of an observer through the point into the scene. If the ray intersects an object, then local color calculations will determine the color that is the result of direct illumination at that point. This is light from a light source. If the object is partially reflective, the color of the point should include a contribution from reflected rays. (There is also a transmitted ray but I did not implemented it) Determining a color of each ray may require the tracing furthur at other intersections. The number of the tracings can be limited by a specified number of recursion depth in recursive Ray Tracing algorithm. There are 3 main parts of the model that must be specified for the processing.

Objects model, specified as quadratic coefficients and surface characteristics.
Image plane, the plane that each ray will trace through.
Eye, the observer view point.

Object model (data.image file)

The model must be specified in the file 'data.image' prior to the computation. There are some topics you must know to be able to specify the model correctly:

Quadric surface: Quadric surfaces can be specified by their coefficients in quadratic formula. There are several quadrics such as Ellipsoid, Paraboloid, Hyperbolic paraboloid, Hyperboloid, Hyperboloid of two sheets, Cone and Cylinder. Sphere and plane can also be specified. For ease of programming but less efficient code, the algorithms doesn't provide efficient way to compute each type of surface but it has an algorithm that works on all type of quadrics.
An example of a quadric formula
```
         2                         2                  2           2
        ax + 2bxy + 2cxz + 2dxw + ey + 2fyz + 2gyw + hz + 2izw + jw = 0

        a,b,c,d,e,f,g,h,i,j are the cofficients required in the file  
```
Ambient Color: This color component is defined for the object to reflect global illumination. For example, rgb(1.0,1.0,1.0) = white, an object with this ambient color component will be seen as an all white on every point on the object. Or, ambient color is the solor of an object.
Diffuse Color: This specified how much the light will leaves the object surface due to diffuse reflection of light from the light source. For example, a white ball will be looked like a sphere with shadow in the side that is away from the light and brighter toward the point that is closest to the ligth source.
Specular Color: This component will make the shiny object looks shiny by compute the angle of the light reflecting on the point. This is much like diffuse component but with a power to the cosine of the angle. The more power, the more shiny the object will be.
Recursive Ray Tracing: The algorithm used in this program is a recursive reyatracing. As mentioned above, for reflective objects, the color at the point can come from other objects that the ray reflects to. For example, without recursion, a scene with a red sphere and a white sphere will be seen as a red spehere wihtout any white color reflecting from the white sphere and the same for the white sphere. With recursive Ray Tracing, on a white sphere, you will be able to see a round-shaped red region which comes from reflecting ray from red sphere.

Using the program

This program takes a large amount of memory, the more number of objects and more recursion depth, the bigger the image size: these might take away all the memory from the machine. You will face the problem like 'core dump' or the program terminated when you run it because at that moment the system doesn't have enough memory to perform the computation. I recommend you to run and test on 32x32 or 64x64 subimage pixel size. If you run it from /scratch/kayasidh there will be the problem that you have to find where the output is put among 8 kestrels. I've tried to be specific on the directory where to put the output file but the system can not do it. Another problem for running on /scratch/kayasidh is you have to put the same copy of 'data.image' file on every nodes too.

The data (data.image)

32 32
256 256
300
0.0 0.0 300.0
1.0 1.0 1.0
0.0 0.0 2000.0
3
1.0 0.0 0.0 0.0 1.0 0.0 -50.0 1.0 0.0 0.0 1.0 1.0 1.0 1.0 1.0 1.0 0.99 
5   
1.0 0.0 0.0 0.0 1.0 0.0 50.0 1.0 0.0 0.0 1.0 0.05 0.05 1.0 0.05 0.05 1.0 2
1.0 0.0 0.0 0.0 0.0 0.0 0.0 1.0 0.0 -200.0 0.0 1.0 1.0 0.0 1.0 1.0 0.99 5
2 0.001 0.007

The first line is the size in pixel of the subimage, 32 by 32, must be integers. The second line is the size of the whole image (image plane), here I use 256 by 256, they must be integers too. The third line, the location of the image plane in z-axis. The image plane is parallel to the X-Y plane only. It must be an integer. The forth line, the location of the light source (this program can work with single light source only). They must be of type real. The fifth line, the color of the light source, here is white. The color must be specified in r g b with the range 0.0 - 1.0 The sixth line, the view point (an observer's eye). Type real. The seventh line, the number of objects following this line. Integer. The eight line and so on, each line for each object only and must not be wrapped up to another line.

    1.0 0.0 0.0 0.0 1.0 0.0 -50.0 1.0 0.0 0.0 1.0 1.0 1.0 1.0 1.0 1.0 
0.99 5
    ^---------------------------------------^
      These 10 real numbers are coefficients of the quadratic formula
      representing the object.

    1.0 0.0 0.0 0.0 1.0 0.0 -50.0 1.0 0.0 0.0 1.0 1.0 1.0 1.0 1.0 1.0 
0.99 5
                                              ^---------^
      These 3 real numbers are r g b components of ambient color.

    1.0 0.0 0.0 0.0 1.0 0.0 -50.0 1.0 0.0 0.0 1.0 1.0 1.0 1.0 1.0 1.0 
0.99 5
                                                          ^---------^
      These 3 real numbers are r g b components of diffuse color.
    
    1.0 0.0 0.0 0.0 1.0 0.0 -50.0 1.0 0.0 0.0 1.0 1.0 1.0 1.0 1.0 1.0 
0.99 5
                                                                      ^----^
      These 2 real numbers are specularity and power-of-cosine value
      for specular color.

The last line must not be changed. The 2 values are for the computation. They are a minimum value of dot product and minimum value of threshhold for the intersection. MUST NOT BE CHANGED. for experiment.

Performance and efficiency

TESTING FROM ~kayasidh/HPF_RAYTRACE/hpf_raytrace.exe. On kestrel, with one node, the biggest subimage to be able to compute at a time is about 32 by 32 to avoid the memory problem. So, if you want a 640 by 640 pixels image, the program has to do at least 20x20 = 400 loops. I've tested on multiple nodes, the biggest subimage is 64 by 64 (the next power-of-two size is 128 by 128 which is too much to be computed). The more number of nodes will give better performance for big image because if the image is small, some internal communication will take down the speedup of multiple nodes. This is why for some subimage size the computation times are fluctuated. I've tested with a 256 by 256 pixels running at 64 by 64 pixels subimage with 6 objects and 1 recursion, the result is as follow.

        1 node  : can not run because of not enough memory
        2 nodes : 119.5024 secs.        3rd
        4 nodes : 76.13430 secs.        2nd
        8 nodes : 56.33170 secs.        1st

    For the same problem with 32 by 32 subimage.

        1 node  : 94.88480 secs.        4th
        2 nodes : 63.19810 secs.        1st
        4 nodes : 84.13950 secs.        3rd
        8 nodes : 68.67850 secs.        2nd
    
    For 200 x 200 image, 50 x 50 subimage, 2 objects, 1 recursion.

        1 node  : 28.81670 secs         2nd
        2 nodes : 43.87050 secs.        4th
        4 nodes : 30.70290 secs.        3rd
        8 nodes : 25.88000 secs.        1st
        
    For 50 x 50 image, 50 x 50 subimage, 2 objects, 1 recursion.
        
        1 node  : 2.654500 secs.        4th
        2 nodes : 1.813900 secs.        3rd
        4 nodes : 1.797400 secs.        2nd
        8 nodes : 1.676900 secs.        1st
        
    For 64 x 64 image, 64 x 64 subimage, 2 objects, 1 recursion.
        
        1 node  : can not run
        2 nodes : 5.725200 secs.        3rd
        4 nodes : 3.429400 secs.        2nd
        8 nodes : 2.557300 secs.        1st.

These time are computation time only. I didn't include the time to read the 'data.image' input file and the time to write the output file because the more number of nodes, the slower the writing output file. I/O operations are inefficient on the parallel environment.

Instructions for compiling and running the code

I put all the files in subdirectory /scratch/kayasidh on every kestrel nodes but the most completed one is on kestrel1. The code MUST NOT be compiled from VPL.

Compile the hpf_raytrace_type.f90 first (the module)

       f90 -wsf -c hpf_raytrace_type.f90
        this should take 15 seconds.

Compile the hpf_raytrace.f90

        f90 -wsf -c hpf_raytrace.f90
        this will take around 15 minutes.

Link both object files together

        f90 -o hpf_raytrace.exe hpf_raytrace.o hpf_raytrace_type.o

Make sure the file 'data.image' is in the same directory as the executable file 'hpf_raytrace.exe'.

Run:

        hpf_raytrace.exe -farm alphafarm -peers 8
                        or
        hpf_raytrace.exe -farm alphafarm -peers 4
                        or
        hpf_raytrace.exe -farm alphafarm -peers 2
                        or
        hpf_raytrace.exe -farm alphafarm -peers 1

        !!! beware of the size of the subimage !!!
        !!! The bigger subimage, the more memory is required.
        !!! WHEN you try to run it from /scratch/kayasidh/
        !!! directory, the 'data.image' file must be the same on 
        !!! every nodes.

More instructions on running the code:
The file 'data.image' contains the object models to be read by hpf_raytrace.exe program. It can be changed to make different ray traced image but make sure that you understand each value in that file. PLEASE READ THEM IN the file REPORT.raytrace.
- To run the program:
```
        hpf_ray_trace.exe -farm alphafarm -peers 
        where n is the number of nodes to be used.
```
- You CAN NOT use more than 64x64 subimage size on MULTIPLE NODES, FOR 1 NODE the subimage size must be around 32x32 EXCEPT you run the program when the system has enough memory. If you run from scratch direcory, the output file might be put in any kestrel node. You have to find it yourself in one of the eight nodes. The file 'hpf_raytrace.exe' must be placed on every node before you can run. The input file 'data.image' must be the same on every node too!!! becuase you don't know which node will run your program.
- I do RECOMMEND you to run from this directory for 32x32 subimage size, on 1 node or 64x64 subimage size for multiple nodes.
- Make sure that the memory will be enough. So, 32x32 subimage size is the safest size.
Output

The output file is 'pic.raw' which is in raw format. You can convert this file to ppm format by rawtoppm pic.raw > pic.ppm where x and y are sizes in x and y dimension of the image 'pic.raw' Ex. rawtoppm 256 256 pic.raw > pic.ppm
To view the ppm file (the quality of the image depends on the color depth of your system) xv pic.ppm If you run my program from /scratch/kayasidh the output file might be created on any kestrel machines depending on which nodes are selected to run.

Source code and data