Benson Muite
https://bkmgit.gitlab.io/cgintro
This work is licensed under a Creative Commons Attribution 4.0 International License.

Why is Computer Graphics Interesting?

• Generating images using a program
  • Video games
  • Cartoons
  • Engineering simulation visualization
  • Architecture visualization
  • Medical scan visualization
  • ...

Background Material

• Many different algorithms
• Consider Raytracing
• Presentation follows descriptions from
  • Gabriel Gambetta [Gambetta21]
  • Tom MacWright [MacWright20]
  • Peter Shirley [Shirley20]

Raytracing

Physics of Images

• Light is reflected and refracted by objects
• A small portion ends up in our eyes, for simplicity, only one ray is continued to the eye

Raytracing

• Backwards physics of images
• For simplicity only one ray is traced from the eye

Raytracing

• Field of View

Image Generation Problem

• The setup here is two dimensional
• Corresponding image is a line
• The line is represented by discrete points
• What is the intensity of the color on the monitor?

Image Generation Algorithm

• For each point on the monitor, determine vector to the eye
  • Continue the vector forward in space
  • Determine which objects get hit
  • Color the point on the monitor appropriately
• Assume the light source has only one color to get binary image
• Need to determine color on the monitor

Only a Light Source and a Monitor

Coordinates

When Does a Ray Intersect the Light Source?

• Geometry
  • Coordinates of a ray $$(t(ex-mx) + ex,t(ey-my) + ey)$$
    • t: parameter; ex,ey: eye x,y coordinates; mx,my: monitor x,y coordinates
  • Equation of light source boundary $$lr^2 = (lcx - lx)^2 + (lcy - ly)^2$$
    • lx,ly: point on light source boundary; lr: light source radius; lcx,lcy: center of light source

When Does a Ray Intersect the Light Source?

• Do line and disc intersect? $$(t(ex-mx) + ex,t(ey-my) + ey)$$ $$lr^2 = (lcx - lx)^2 + (lcy - ly)^2$$ $$lx = t(ex-mx) + ex, \quad ly = t(ey-my) + ey$$ $$lr^2 = (lcx - t(ex-mx) - ex)^2 + \\ (lcy - t(ey-my) - ey)^2$$

Find Real Solutions Part 1

$$t^2((ex-mx)^2+(ey-my)^2) - \\ 2t( (ex-mx)(lcx-ex) + (ey-my)(lcy-ey)) + \\ (lcx-ex)^2 + (lcy-ey)^2 - lr^2 =0$$ - Recall $$ ax^2 + bx +c =0$$ $$ x = \frac{-b\pm\sqrt{b^2-4ac}}{2a}$$

Find Real Solutions Part 2

• Real solutions if

$$b^2 -4ac >= 0$$ - Cancelling factor of 4 $$( (ex-mx)(lcx-ex) + (ey-my)(lcy-ey))^2 - \\ ((ex-mx)^2+(ey-my)^2) \times \\ ( (lcx-ex)^2 + (lcy-ey)^2 - lr^2 ) >= 0$$

C Program

#include "stdio.h"
#include "math.h"
// Compile with gcc OneDimensionalRender.c -lm
int main(){
  const int myt = 1000;   // monitor y location top
  const int myb = 3000;   // monitor y location bottom
  const int mx = 1000;    // monitor x location
  const int ex = 0;       // eye x location
  const int ey = 2000;    // eye y location
  const int lcx = 5000;   // light center x location
  const int lcy = 3000;   // light center y location
  const int lr = 500;     // light radius
  int my;                 // monitor y location
  int real_solution;      // 1 if real solution, 0 otherwise

C Program

  for(my = myt; my < myb; my++){
    int b = 2*((ex-mx)*(lcx-ex) + (ey-my)*(lcy-ey));
    int a = pow(ex-mx,2) + pow(ey-my,2);
    int c = pow(lcx-ex,2) - pow(lcy-ey,2) - pow(lr,2);
    real_solution = ( (pow(b/2,2) - a*c) >=0);
    printf("%d %d\n",my,real_solution);
  }
  return 0;
}

Generated Image

Parallelization

• Each of the rays can be computed independently
• In one dimension, fast runtime
• In two dimensions, significant improvement
• One reason for using graphics cards with many compute units

Extension to Two Dimensional Projection

• Geometry
  • Coordinates of a ray $$(t(ex-mx) + ex,t(ey-my) + ey, t(ez-mz) + ez)$$
    • t: parameter; ex,ey,ez: eye coordinates; mx,my,mz: monitor coordinates
  • Equation of light source boundary $$lr^2 = (lcx - lx)^2 + (lcy - ly)^2 + (lcz - lz)^2$$
    • lx,ly,lz: point on light source boundary; lr: light source radius; lcx,lcy,lcz: center of light source

When Does a Ray Intersect the Light Source?

• Do line and sphere intersect? $$(t(ex-mx) + ex,t(ey-my) + ey),t(ez-mz) + ez)$$ $$lr^2 = (lcx - lx)^2 + (lcy - ly)^2 + (lcz - lz)^2$$ $$lx = t(ex-mx) + ex, \quad ly = t(ey-my) + ey, \quad lz = t(ez-mz) + ez$$ $$lr^2 = (lcx - t(ex-mx) - ex)^2 + \\ (lcy - t(ey-my) - ey)^2 + \\ (lcz - t(ez-mz) - ez)^2$$

Condition for Real Solutions

$$( (ex-mx)(lcx-ex) + (ey-my)(lcy-ey) + (ez-mz)(lcz-ez))^2 - \\ ((ex-mx)^2 + (ey-my)^2 + (ez-mz)^2) \times \\ ( (lcx-ex)^2 + (lcy-ey)^2 + (lcz-ez)^2 - lr^2 ) >= 0$$

C Program Code Snippet

  for(my = myt; my < myb; my++){
    for(mz = mzt; mz < mzb; mz++){
      int b = 2*((mx-ex)*(lcx-ex) + (my-ey)*(lcy-ey) + (mz-ez)*(lcz-ez));
      int a = pow(ex-mx,2) + pow(ey-my,2) + pow(ez-mz,2);
      int c = pow(lcx-ex,2) + pow(lcy-ey,2) + pow(lcz-ez,2) - pow(lr,2);
      real_solution[ (mz-mzt) + (my-myt)*(mzb-mzt) ] = (pow(b/2,2) - a*c >= 0);
    }
  }

SYCL Program Code Snippet

sycl::default_selector deviceSelector;
sycl::queue queue(deviceSelector);
sycl::buffer<int, 1> d_real_solution(real_solution, (myb-myt)*(mzb-mzt));
queue.submit([&d_real_solution,ex,ey,ez,mx,myb,myt,mzb,lcx,lcy,lcz,lr](
  sycl::handler& cgh) {
  auto real_solution = d_real_solution.get_access
  <sycl::access::mode::write>(cgh);

SYCL Program Code Snippet

 cgh.parallel_for<class render>(
    sycl::nd_range<1>{(myb-myt)*(mzb-mzt),1},
    [real_solution,ex,ey,ez,mx,myb,myt,mzb,lcx,lcy,lcz,lr](sycl::nd_item<1> item){
    int global_id = item.get_global_linear_id();
    int kk = global_id % (mzb-mzt);
    int jj = (global_id - kk) / (myb-myt);
    int my = jj + myt;
    int mz = kk + mzt;
    int b = 2*((mx-ex)*(lcx-ex) + (my-ey)*(lcy-ey) + (mz-ez)*(lcz-ez));
    int a = pow(ex-mx,2)+pow(ey-my,2)+pow(ez-mz,2) );
    int c = pow(lcx-ex,2)+pow(lcy-ey,2)+pow(lcz-ez,2) - pow(lr,2);
    real_solution[kk + jj*(mzb-mzt)] = pow( b/2, 2) - a * c >= 0;
  });
});
queue.wait();

Resulting image

Image of sphere that is created

Interactive Demonstration

• The choice of programming language can be important
• Compare Javascript and WebAssembly using Matthew Harrison's Renderer
• How many frames per second do you get on your computer?

Example Open Source Rendering Software

• Blender
• Cycles Renderer
• Lux Core Renderer
• Appleseed
• Ogre

References and Further Reading

Acknowledgements

Slides made with Markdeep-slides