.. title: CG Class 23, Mon 2019-11-18
.. slug: class23
.. date: 2019-11-18
.. tags: class
.. category:
.. link:
.. description:
.. type: text
.. has_math: true

.. sectnum::
.. contents:: Table of contents


Homeworks 9 and 10
------------------

are online.

ACM SIGSPATIAL GIS Cup 
-----------------------

I mentioned that 2 weeks ago I was at `27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2019) <https://sigspatial2019.sigspatial.org/>`_.

They have an annual programming contest, the GISCup.   My students and I
`won first place <http://sigspatial2018.sigspatial.org/giscup2018/results>`_
in 2018.    

In 2016, we `won 2nd place <http://sigspatial2016.sigspatial.org/giscup2016/results>`_.  We also won 2nd place in 2015, and 4th in 2014.


How I made a fast forward video in linux
----------------------------------------

For the `2019 International Geometry Summit Vancouver <https://geometrysummit2019.org/>`_.

This is my `FF video <https://wrf.ecse.rpi.edu/p/231-parover2-vancouver-2019-ff.mp4>`_.  It plays on some browsers, like chromium, but not on others, like firefox.

How I made it, approximately.

#. This gives the same time to each slide.
#. I made a pdf file of the slides, using LaTeX Beamer.
#. Convert that to separate png files using Imagemagick:
   
     mogrify -verbose -density 500 -resize 1600x900\\! -format png ./\*.pdf

#. Make a timed video of slides:
   
     ffmpeg -framerate 1:42 -pattern_type glob -i '\*.png' -c:v libx264 video.mp4

#. Note: Don't use Imagemagick convert, whose output runs slow.

#. Write the transcript for my voiceover.

#. Record my audio with my best headset.

#. Combine audio and video:
   
     ffmpeg -i narration.wav -i video.mp4  combo.mp4

Week 13 slides
--------------

#. `13_2 Polygon rendering <https://wrf.ecse.rpi.edu/Teaching/graphics/SEVENTH_EDITION/PPT/WEEK13/Angel_UNM_14_13_2.ppt>`_. Includes clipping polygons, hidden surface algorithms.

   Start at slide 23.
   
#. `13_3 Rasterization <https://wrf.ecse.rpi.edu/Teaching/graphics/SEVENTH_EDITION/PPT/WEEK13/Angel_UNM_14_13_3.ppt>`_.

   
My commentaries
---------------
   
Clipping
========
#. Many of these algorithms were developed for HW w/o floating point, where
   even integer multiplication was expensive.

#. Efficiency is now less important in most cases (unless you're implementing in HW).

#. The idea of clipping with a 6-stage pipeline is important.

#. `Jim Clark <http://en.wikipedia.org/wiki/James_H._Clark>`_, a prof at
   Stanford, made a 12-stage pipeline using 12 copies of the same chip, and
   then left Stanford to found SGI.

   a. Later he bankrolled Netscape and 2 other companies.

   #. More recently he had the world's `4th largest yacht <http://www.forbes.com/sites/ryanmac/2012/05/15/billionaire-jim-clark-seeks-more-than-100-million-for-two-superyachts/>`_.
   

Polygon rendering
=================

#. My note on `Bresenham Line and Circle Drawing
   <http://www.ecse.rpi.edu/~wrf/Research/Short_Notes/bresenham.html>`_.  Jack
   Bresenham, then at IBM invented these very fast ways to draw lines and
   circles with only integer addition and subtraction.  My note gives
   step-by-step derivations by transforming slow and clear programs to fast and
   obscure programs.

#. My note on `Two polygon filling algorithms <http://www.ecse.rpi.edu/~wrf/Research/Short_Notes/polyfill.html>`_.


Visibility methods
==================

Here's my summary of problems with the main methods:

#. *Painters:*

   a. The painter's algorithm is tricky when faces are close in Z.
   #. Sorting the faces is hard and maybe impossible.  Then you must split
      some faces.
   #. However sometimes some objects are always in front of some other
      objects.  Then you can render the background before the foreground.

#. *Z-buffer:*

   a. Subpixel objects randomly appear and disappear (aliasing).
   #. Artifacts occur when objects are closer than their Z-extent across one
      pixel.
   #. This happens on the edge where two faces meet.

#. *BSP tree:*

   a. In 3D, many faces must be split to build the tree.

#. The scanline algorithm can feed data straight to the video D/A.  That was
   popular decades ago before frame buffers existed.  It became popular again
   when frame buffers are the slowest part of the pipeline.

#. A real implementation, with a moving foreground and fixed background,
   might combine techniques.

#. References: wikipedia.


.. used up to 2018 class 25