**Speeding up Computer Graphics** Making cool pictures fast!
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 *********************************************************************** * Mirror * * ---------------- * * / ^ * * v \ ^ ^ * * .-----. \ | / * * / \ / .-. * * +) <-------------\ / <--| |--> * * \ ' '-' * * Eye Prism / | \ * * v v v * * Light source * * * * * *********************************************************************** --- ## Raytracing - Backwards physics of images - For simplicity only one ray is traced from the eye *********************************************************************** * Mirror * * ---------------- * * ^ \ * * / \ * * .-----. v * * / \ / .-. * * +) ------------->\ / | | * * \ ' '-' * * Eye Prism Light source * * * * * * * *********************************************************************** --- ## Raytracing - Field of View *********************************************************************** * Mirror * * ---------------- * * ^ \ * * | / \ * * ^ | .-----. v * * / / | \ / .-. * * +) --> |-------->\ / | | * * \ \ | ' '-' * * Eye v | Prism Light source * * | * * Monitor * * * * * *********************************************************************** --- ## 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 *********************************************************************** * --> * * | * * v | * * ^ | * * / / | .-. * * +) --> | --------------------->| | * * \ \ | '-' * * Eye v | Light source * * | * * Monitor * * * * * *********************************************************************** --- ## Coordinates *********************************************************************** * --> * * | (1000,1000) * * v | * * ^ | * * / / | .-. * * +) --> | --------------------->| | * * \ \ | '-' * * Eye v | Light source * *(0,2000) | Center: (5000,2000) * * Monitor Radius: 500 * * (1000,3000) * * * * * *********************************************************************** --- ## 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 ```C #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 ``` [Listing [C-start]: First part of program - variable declaration.] --- ## C Program ```C 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; } ``` [Listing [C-kernel]: Second part of program - main loop.] --- ## Generated Image *********************************************************************** * --> * * | * * v | * * | * * / | .-. * * +) | | | * * \ | '-' * * | * * | * * * * * *********************************************************************** --- ## 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 ```C 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); } } ``` [Listing [C-Kernel2D]: Two dimensions - main loop.] --- ## SYCL Program Code Snippet ```C++ 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); ``` [Listing [SYCL-Start2D]: Two dimensions - parallelization setup.] --- ## SYCL Program Code Snippet ```C++ 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(); ``` [Listing [SYCL-Kernel2D]: Two dimensions - parallel main loop.] --- ### Resulting image ![Image of sphere that is created](images/sphere.jpg style="height: 12rem") --- ## Interactive Demonstration - The choice of programming language can be important - Compare [Javascript](https://www.ecma-international.org/publications-and-standards/standards/ecma-262/) and [WebAssembly](https://www.w3.org/wasm/) using [Matthew Harrison's Renderer](https://mtharrison.github.io/wasm-raytracer/) - How many frames per second do you get on your computer? --- ### Example Open Source Rendering Software - [Blender](https://www.blender.org/) - [Cycles Renderer](https://www.cycles-renderer.org) - [Lux Core Renderer](https://luxcorerender.org/) - [Appleseed](https://github.com/appleseedhq/appleseed) - [Ogre](https://github.com/OGRECave/ogre) --- ### References and Further Reading [#Gambetta21]: Gambetta, G. (2021). [Computer Graphics From Scratch](https://www.gabrielgambetta.com/computer-graphics-from-scratch/). [#MacWright20]: MacWright, T., Schaub, T., Diachok R. and Cutler D. (2020). [Literate RayTracer](https://tmcw.github.io/literate-raytracer/). [#Mirazchiyski20]: Mirazchiyiski, G. (2020). [Ray-tracing in a Weekend with SYCL: Basic sphere tracing](https://www.codeplay.com/portal/blogs/2020/05/19/ray-tracing-in-a-weekend-with-sycl-basic-sphere-tracing.html) [#PharrJakobHumphreys18]: Pharr, M., Jakob, W., Humphreys, G. (2018). [Physically Based Rendering: From Theory to Implementation](https://pbrt.org/) [#Shirley20]: Shirley, P. (2020). [Ray Tracing in One Weekend](https://raytracing.github.io/books/RayTracingInOneWeekend.html) --- ### Acknowledgements Slides made with [Markdeep-slides](https://github.com/doersino/markdeep-slides)