Computação Gráfica 2D
2D Computer Graphics

Este é um curso introdutório de computação gráfica 2D. O tema central é a renderização de ilustrações vetoriais. Ao final do curso, os alunos compreenderão completamente, tanto na teoria como na prática, todas as etapas necessárias para produzir imagens de alta qualidade a partir de ilustrações vetoriais. Para melhor aproveitar o curso, os alunos devem estar previamente familiarizados com álgebra linear, cálculo, e ter conhecimentos de programação em Lua ou C++.

This is an introductory course in 2D Computer Graphics. The main topic of study is vector graphics rendering. By the end of the course, students will thoroughly understand, both in theory and in practice, all the steps required to produce high-quality renderings of vector graphics illustrations. Students are expected to be familiar with linear algebra, calculus, and have basic computer programming skills in Lua or C++.

Administrative

Class hours:
Mon, Wed & Fri, 3PM—5:00PM, Room 224

Lab:
Thu 1PM—3PM, Room 345

Discussion list:
impa-2019-0-2dcg

Instructor:
Prof. Diego Nehab
Office: 410
E-mail: diego@...

Teaching assistant:
Pedro Arthur dos Santos Souza
Office: Visgraf
E-mail: pasouza@...

Grading

Practical aspects will be tested by programming assignments distributed throughout the course. Assignemts will be based on software infrastructure we will provide. Students without a solid programming experience can use the Lua Programming Language. More advanced students can use C++ instead.

Theory will evaluated with a final exam at the end of the course.

The final grade will be formed by the assignments (60%), the exam (30%), and participation in class (10%).

Schedule

Date Topic Details
M 07/01 Introduction Reading list:
class slides,
Lua [PIL],
line rasterization [Bresenham1965],
polygon rasterization (edge flag) [AcklandWeste1981],
polygon rasterization (active-edge list) [WylieEtAl1967],
error diffusion dithering [FloydSteinberg1976],
general books covering computer graphics [FoleyVanDam1990] [GomesVelho2008]
W 09/01 Geometry and transformations Warmup assignment posted: run examples from class
Reading list:
class slides,
Conics, affine geometry, and projective geometry [BrannanEtAl2012, chapters 0—3],
transformations [Mathematica: xforms]
F 11/01 Vector graphics Warmup due
Assignment 1 posted: triangles, circles, and polygons
Reading list:
class slides,
PostScript tutorial [PSBlueBook],
PostScript reference [PSRedBook],
PDF reference [PDF],
OpenXPS reference [OpenXPS],
SVG reference [SVG],
OpenVG API [OpenVG],
NV Path Rendering API [NVPR],
inside-outside test for triangles and polygons [Mathematica: polygons],
inside-outside test, center, and bounding-box for ellipses [Mathematica: ellipses]
M 14/01 Bézier curves Reading list:
class slides,
integral Bézier curves [Mathematica: Bézier],
general books covering these topics [Sederberg2014, chapters 1—3] [Farin2002, chapters 1—6]
W 16/01 More on Bézier curves Reading list:
class slides,
blossoms (multiaffine maps) [Mathematica: Multiaffine maps],
rational quadratic Bézier curves [Mathematica: Rational Bézier],
general books covering these topics [Sederberg2014, chapters 1—3] [Farin2002, chapters 13]
F 18/01 Floating-point and root-finding Assignment 1 due
Assignment 2 posted: paths
Reading list:
class slides
floating-point [MullerEtAl2010],
finding roots [Mathematica: roots],
solving quadratics [Blinn2005],
solving cubics [Blinn2007],
root finding [Press2007, chapter 9],
root finding in Bernstein form [Sederberg2014, chapter 9],
integration [Press2007, chapter 4]
M 21/01 Color and compositing Reading list:
class slides,
great webpage covering color [Hardprint],
sRGB color model [sRGB],
seminal works on compositing [Wallace1981] [PorterDuff1984],
FAQs on color and gamma [ColorFAQ] [GammaFAQ],
general book covering these topics [GomesVelho2008, chapters 5 and 17]
W 23/01 Gradient paints Reading list:
class slides,
EPS/PDF gradient samples,
[PSRedBook, section 4.9.3],
PDF reference [PDF, section 4.6],
SVG reference [SVG, chapter 13]
F 25/01 Differential geometry Assignment 2 due
Assignment 3 posted: transparency and gradients
List 1 posted
Reading list:
class slides,
integral Bézier curves [Mathematica: Bézier],
rational quadratic Bézier curves [Mathematica: Rational Bézier],
general books covering these topics [Kreyszig1991, chapters 1–2], [ONeil2006, chapters 1–3],
offset curves [Sederberg2014, chapter 8], [Hoschek1988],
arc-length approximation [Juttler1997]
M 28/01 Resultants and implicitization Reading list:
class slides,
resultants for CAGD [MontaudouinTiller1984] [GoldmanEtAl1984],
resultants [Mathematica: resultants],
implicitization by affine functionals [LoopBlinn2005] [LoopBlinn2007],
implicitizing integral quadratics [Mathematica: implicit quadratics],
implicitizing rational quadratics [Mathematica: implicit rational quadratics],
implicitizing integral cubics [Mathematica: implicit cubics]
W 30/01 Inflection points and double points Reading list:
class slides,
computing inflection points and double-points [Mathematica: inflection-double],
tensor notation [Blinn1992a] [Blinn1992b],
cubic inflection points [Blinn1999]
F 01/02 Abstract segments Assignment 3 due
Assignment 4 posted: implicit intersection tests
Reading list:
class slides,
abstract segments [LoopBlinn2005] [LoopBlinn2007] [GanacimEtAl2014]
M 04/02 Digital images and anti-aliasing Assignment 4 addition: add supersampling
Reading list:
class slides,
analytic anti-aliasing [Duff1989] [MansonSchaefer2013],
anti-aliasing and gamma, analytic anti-aliasing approximation [NehabHoppe2008],
Fourier transforms [Teixeira2001],
perceptual image metric [ZhangWandell1996]
W 06/02 Texture mapping Assignment 4 addition: add texture mapping
Reading list:
class slides
Monte Carlo methods [Anderson1999],
sampling and reconstruction [NehabHoppe2014]
F 08/02 Acceleration datastructures List 2 posted
Reading list:
polygon clipping [SutherlandHodgman1974],
Quad trees [Warnock1969],
k-d trees [Bentley1975] [FriedmanEtAl1977],
BSP trees [FuchsEtAl1980],
R-trees (BVH) [Guttman1984]
M 11/02 The shortcut tree and regular grid Reading list:
lattice clipping [NehabHoppe2008],
“tripod” line rasterization [Cohen1994],
shortcut tree [GanacimEtAl2014]
W 13/02 Typesetting Assignment 4 due
Group assignment 5 posted: accelerated rendering
Readling list:
caligraphy video,
Making manuscripts video,
Jaquet Droz's writer automaton video,
KUKA scribe video,
METAFONT tutorial [Grandsire2004],
Gutenberg's printing press video,
Linotype machine video,
OpenType specification [OpenType],
FreeType library [FreeType],
HarfBuzz library [HarfBuzz],
Unicode standard [Unicode],
hyphenation and justification used in TeX [KnuthPlass1981],
microtypography in TeX [Thanh2000],
general book covering these topics [Felici2012]
F 15/02 Computational geometry Reading list:
reentrant polygon clipping [SutherlandHodgman1974],
general polygon clipping [Vatti1992],
triangulation by ear-clipping [Meisters1975],
plane-sweep convex hull [Andrew1979],
plane-sweep all segment intersections [BentleyOttmann1979],
plane-sweep closest pair of points [HinrichsEtAl1988],
plane-sweep Voronoi diagram [Fortune1986],
general books covering these topics [deFigueiredoCarvalho1991] [deBergEtAl2008]
M 18/02 Stroked primitives Reading list:
SVG stroke properties [SVG, chapter 11.4],
OpenXPS stroke rendering [OpenXPS, chapter 18.6],
arc-length approximation [Juttler1997],
offset (and evolute) approximation [Hoschek1988],
GPU-accelerated path rendering [KilgardBolz2012],
differential geometry of stroking [Mathematica: stroke],
joining flattened offsets [Mathematica: join],
W 20/02 Screen space effects (blur, clipping)
F 22/02 Other rendering algorithms
M 25/02 Group presentations Group assignment 5 due
W 27/02 Test

Materials

May require Inkscape or Wolfram CDF Player.

Lua and C++ materials

src-1.01.zip C++ source-code for Lua modules and the C++ framework.
rvgs-1.00.zip Sample vector graphics inputs in the RVG format.
pngs-1.00.zip Ground-truth renderings of RVG inputs.
svgs-1.00.zip Corresponding SVG files.
fonts-1.00.zip A collection of freely avaialable fonts.
docker image A Docker image configured for the course.
win64-1.00.zip Win64 libraries and Lua executable (Requires the Visual Studio Runtime.)

Mathematica

xforms-1.0.cdf Linear, affine, and projective transformations.
polygons-1.0.cdf Inside-outside tests for triangles and polygons, winding rules.
ellipses-1.0.cdf Inside-outside test, transformation, center, and bounding-box for implicit ellipses.
bezier-1.0.cdf Bézier curves, polynomial basis (Bernstein and Power), De Casteljau, tangents,
affine reparametrization, subdivision, monotonization, flattening,
silly bisection, curvature, oscullating circle.
rational-bezier-1.1.cdf Same and more for rational quadratic Bézier curves.
multiaffine-1.0.cdf Blossoms (Multiaffine maps).
roots-1.0.cdf Bisection search, Newton-Raphson, Safe Newton-Raphson, polynomial root-finding.
resultants-1.0.cdf Resultants via the Sylvester and Cayley-Bézout matrices.
implicit-quadratics-1.0.cdf Implicitization of integral quadratic Bézier curves.
implicit-rational-quadratics-1.0.cdf Implicitization of rational quadratic Bézier curves.
implicit-cubics-1.0.cdf Implicitization of integral cubic Bézier curves.
inflection-double-2.0.cdf Computing inflection points and double points of rational parametric cubics.

Exercices and programming assignments

warmup-1.00.zip Due 11/01/2019 (before class).
assign-1-1.00.zip Due 18/01/2019 (before class).
assign-2-1.00.zip Due 25/01/2019 (before class).
list-1.pdf Try to solve the exercices. No need to hand in your solutions.
assign-3-1.00.zip Due 01/02/2019 (before class).
assign-4-1.00.zip Due 13/02/2019 (before class).
list-2.pdf Try to solve the exercices. No need to hand in your solutions.
assign-5-1.00.zip Due 25/02/2019 (before class).

Bibliography

  1. [Bresenham1965] Bresenham, J. E. “Algorithm for computer control of a digital plotter.”, IBM Systems Journal, 4(1):25–30, 1965.
  2. [WylieEtAl1967] Wylie, C.; Romney, G.; Evans, D.; Erdahl, A. “Half-tone perspective drawings by computer”, Proceedings Fall Joint Computer Conference, pages 49–58, 1967.
  3. [Warnock1969] Warnock, J. E. “A hidden surface algorithm for computer generated halftone pictures”, PhD Thesis, University of Utah, 1969.
  4. [SutherlandHodgman1974] Sutherland, I.; Hodgman, W. G. “Reentrant polygon clipping.”, Communications of the ACM, 17(1):32–42, 1974.
  5. [Meisters1975] Meisters, G. H. “Polygons have ears”, American Mathematical Monthly, 82(6):648–651, 1975.
  6. [Bentley1975] Bentley, J. L. “Multidimensional binary search trees used for associative searching”, Communications of the ACM, 18(9):509–517, 1975.
  7. [FloydSteinberg1976] Floyd, R.; Steinberg, L. “An adaptive algorithm for spatial greyscale.”, Proceedings of the Society for Information Display, 17(2):75–77, 1976.
  8. [FriedmanEtAl1977] Friedman, H. J; Bentley, J. L.; Finkel, R. A. “An algorithm for find best matches in Logarithmic expected time.”, ACM Transactions on Mathematical Software, 3(3):209–226, 1977.
  9. [Catmull1978] Catmull, E. “A hidden-surface algorithm with anti-aliasing”, Computer Graphics (Proceedings of ACM SIGGRAPH 1978), 12(3):6–11, 1978.
  10. [Andrew1979] Andrew, A. M. “Another efficient algorithm for convex hulls in two dimensions”, Information Processing Letters, 9(5):216–219, 1979.
  11. [BentleyOttmann1979] Bentley, J. O.; Ottmann, T. A. “Algorithms for Reporting and Counting Geometric Intersections”, IEEE Transactions on Computers, C-28(9):643–647, 1979.
  12. [FuchsEtAl1980] Fuchs, H. and Kedem, Z. M. and Naylor, B. F. “ On visible surface generation by a priori tree structures”, Computer Graphics (Proceedings of ACM SIGGRAPH 1980), 14(3):124–133, 1980.
  13. [AcklandWeste1981] Ackland, B. D.; Weste, N. H. “The Edge Flag Algorithm - A Fill Method for Raster Scan Displays”, IEEE Transactions on Computers, pages 41–48, 1981.
  14. [KnuthPlass1981] Knuth, D. E.; Plass, M. F. “Breaking paragraphs into lines”, Software: Practice and Expeerience, 11(11):1119–1184, 1981.
  15. [Wallace1981] Wallace, B. A. “Merging and transformation of raster images for cartoon animation”, Computer Graphics (Proceedings of ACM SIGGRAPH 1981), 15(3):253–262, 1981.
  16. [WarnockWyatt1982] Warnock, J. E.; Wyatt, D. K. “A device independent graphics imaging model for use with raster devices”, Computer Graphics (Proceedings of ACM SIGGRAPH 1982), 16(3):313–319, 1982.
  17. [Guttman1984] Guttman, A. “ R-trees: a dynamic index structure for spatial searching”, Proceedings of ACM SIGMOD 1984, 14(2):47–57, 1984.
  18. [PorterDuff1984] Porter, T.; Duff, T. “Compositing digital images”, Computer Graphics (Proceedings of ACM SIGGRAPH 1984), 18(3):253–259, 1984.
  19. [Carpenter1984] Carpenter, L. “The A-buffer, an antialiased hidden surface method”, Computer Graphics (Proceedings of ACM SIGGRAPH 1984), 18(3):103–108, 1984.
  20. [CookPorterCarpenter1984] Cook, R. L.; Porter, T.; Carpenter, L. “Distributed Ray Tracing”, Computer Graphics (Proceedings of ACM SIGGRAPH 1984), 18(3):137–145, 1984.
  21. [Catmull1984] Catmull, E. “An analytic visible surface algorithm for independent pixel processing”, Computer Graphics (Proceedings of ACM SIGGRAPH 1984), 18(3):109–115, 1984.
  22. [MontaudouinTiller1984] de Montaudouin, Y.; Tiller, W. “The Cayley method for computer aided geometric design”, Computer Aided Geometric Design, 1(4):309–326, 1984.
  23. [GoldmanEtAl1984] Goldman, R. N.; Sederberg, T. W.; Anderson, D. C. “Vector elimination: A technique for the implicitization, inversion, and intersection of planar parametric rational polynomial curves”, Computer Aided Geometric Design, 1(4):327–356, 1984.
  24. [PSBlueBook] Adobe Systems Incorporated. “The PostScript Language tutorial and cookbook”, 1985.
  25. [Fortune1986] Lee, E. T. Y. “A sweepline algorithm for Voronoi diagrams”, In proceedings of the Symposium on Computational Geometry, pages 313–322, 1986.
  26. [Lee1987] Lee, E. T. Y. “The rational Bézier representation for conics”, Geometric Modeling: Algorithms and New Trends, pages 1–19, SIAM, 1987.
  27. [Hoschek1988] Hoschek, J. “Spline approximation of offset curves”, Computer Aided Geometric Design, 5(1):33–40, 1988.
  28. [HinrichsEtAl1988] Hinrichs, K.; Nievergelt, J.; Schorn, P. “Plane-sweep solves the closest pair problem elegantly”, Information Processing Letters, 26(5):255–261, 1988
  29. [Ramshaw1988] Ramshaw, L. “Béziers and B-splines as multiaffine maps”, Theoretical Foundations of Computer Graphics and CAD, NATO ASI Series, Springer, 40:757–776
  30. [Duff1989] Duff, T. “Polygon scan conversion by exact convolution”, Cambridge University Press, pages 154–168, 1989.
  31. [Vatti1992] Vatti, R. E. “A generic solution to polygon clipping”, Communications of the ACM, 35(7):56–63, 1984.
  32. [FoleyVanDam1990] Foley, D. J.; van DAm, A; Feiner, K. S.; Hugues, J. F. “Computer Graphics: Principles and Practice in C”, 2nd edition, Addison-Wesley Professional, 1990.
  33. [deFigueiredoCarvalho1991] de Figueiredo, L. H.; Carvalho, P. C. “Introdução à geometria computacional”, 18o Colóquio Brasileiro de Matemática, IMPA, 1991.
  34. [Kreyszig1991] Kreyszig, E. “Differential Geometry”, Dover, 1991.
  35. [Blinn1992a] Blinn, J. F. “Uppers and downers”, IEEE Computer Graphics and Applications, 12(2):85–91, 1992.
  36. [Blinn1992b] Blinn, J. F. “Uppers and downers: Part 2”, IEEE Computer Graphics and Applications, 12(3):80–85, 1992.
  37. [Cohen1994] Cohen, D. “Voxel Traversal along a 3D line”, Graphics Gems 4, chapter V.3, pages 366–369, 1994.
  38. [Smith1995] Smith, A. R. “A pixel is not a little square (and a voxel is not a little cube)”, Technical Memo 6, 1995.
  39. [sRGB] Stokes, M.; Anderson, M.; Chandrasekar, S.; Motta, R. “A standard default color space for the internet — sRGB”, 1996. (see also IEC 61966-2-1 1999-10 standard)
  40. [ZhangWandell1996] Zhang, X.; Wandell, B. A. “A spatial extension to CIELAB for digital color image reproduction”, Proceedings of the SID Symposiums, 27:731–734, 1996.
  41. [FontFAQ] Walsh, N. “Frequently-Asked Questions about Fonts”, 1996.
  42. [Zuttler1997] Juttler, B. “A vegetarian approach to optimal parameterizations”, Computer Aided Geometric Design, 14(9):887–890, 1997.
  43. [GammaFAQ] Poynton, C. “Frequently-Asked Questions about gamma”, 1998. (see also C. A. Poynton. Rehabilitation of gamma. In Proc. SPIE, volume 3299, pages 232–249, 1998)
  44. [PSRedBook] Adobe Systems Incorporated. “PostScript Language reference”, 3rd edition, 1999.
  45. [Blinn1999] Blinn, J. F. “How many different rational parametric cubic curves are there? Part 1: Inflection points”, IEEE Computer Graphics and Applications, 19(4):84–87, 1999.
  46. [Anderson1999] Anderson, E. C. “Monte Carlo Methods and Importance Sampling”, Lecture Notes for Stat 578C, 1999.
  47. [Thanh2000] Thanh, H. T. “Micro-typographic extensions to the TeX typesetting systemrdquo;, PhD Thesis, Masaryk University Brno, 2000.
  48. [Teixeira2001] Teixeira, R. “Introdução aos espaços de escala (EDPs em processamento de imagens)”, 23o Colóquio Brasileiro de Matemática, IMPA, 2001.
  49. [Blinn2002] Blinn, J. F. “How many different rational parametric cubic curves are there? Part 3. The catalog ”, IEEE Computer Graphics and Applications, 20(2):85–88, 2002.
  50. [Farin2002] Farin, G. “Curves and surfaces for CAGG: A practical guide”, Morgan Kaufmann Series on Computer Graphics and Geometric Modeling, 5th edition, 2002.
  51. [Grandsire2004] Grandsire, C. “The METAFONTutorial”, 2004.
  52. [Blinn2005] Blinn, J. F. “How to solve a quadratic equation”, IEEE Computer Graphics and Applications, 25(6):76–79, 2005.
  53. [LoopBlinn2005] Loop, C.; Blinn, J. F. “ Resolution independent curve rendering using programmable graphics hardware ”, ACM Transactions on Graphics (Proceedings of the ACM SIGGRAPH 2005), 24(3):1000–1009, 2005.
  54. [PDF] Adobe Systems Incorporated. “Adobe Portable Document Format,”, v. 1.7, 6th edition, 2006.
  55. [ColorFAQ] Poynton, C. “Frequently Asked Questions about colour (color)”, 2006.
  56. [ONeil2006] O'Neill, B. “Elementary Differential Geometry”, University Press, revised 2nd edition, 2006.
  57. [Press2007] Press, W. H. and Teukolsky, S. A. and Vetterling, W. T. and Flannery, B. P. “Numerical Recipes: The Art of Scientific Computing”, Cambridge University Press, 3rd edition, 2007.
  58. [LoopBlinn2007] Loop, C.; Blinn, J. F. “Rendering vector art on the GPU”, GPU Gems 3, chapter 25, 2007.
  59. [Blinn2007] Blinn, J. F. “How to solve a cubic equation, part 5: Back to numerics ”, IEEE Computer Graphics and Applications, 27(3):78–89, 2007.
  60. [PressEtAl2007] Press, W. ; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. F. “Numerical recipes in C: The art of scientific computing”, 3rd edition, Cambridge University Press, 2007.
  61. [deBergEtAl2008] de Berg, M.; Cheong, O.; van Kreveld, M.; Overmars, M. “Computational Geometry: Algorithms and Applications”, 3rd edition, Springer, 2008.
  62. [GomesVelho2008] Gomes, J.; Velho, L. “Fundamentos da computação gráfica”, Série de Computação e Matemática, IMPA, 2008.
  63. [OpenVG] Khronos Group. “OpenVG specification”, v. 1.1, 2008.
  64. [NehabHoppe2008] Nehab, D.; Hoppe, H. “Random-access rendering of general vector graphics”, ACM Transactions on Graphics (Proceedings of the ACM SIGGRAPH Asia 2008), 27(5):135, 2008.
  65. [OpenXPS] ECMA International. “Open XML Paper Specification”, Standard ECMA-388, 2009.
  66. [MullerEtAl2010] Muller, J.-M.; Brisebarre, N.; de Dineshin, F.; Jeannerod, C.-P.; Lefèvre, V.; Melquiond, G.; Revol, N.; Stehlé, D.; Torres, S.; “Handbook of floating-point arithmetic”, Birkhauser, 2010.
  67. [SVG] W3C recommendation. “Scalable Vector Graphics (SVG)”, v. 1.1, 2nd edition, 2011.
  68. [BrannanEtAl2012] Brannan, D. A.; Esplen, M. F.; Gray, J. G. “Geometry”, Cambridge University Press, 2012.
  69. [Felici2012] Felici, J. “The Complete Manual of Typography: A Guide to Setting Perfect Type”, Peachpit Press, 1st edition, 2012.
  70. [KilgardBolz2012] Kilgard, M. J.; Bolz, J. “GPU-accelerated path rendering”, ACM Transactions on Graphics (Proceedings of the ACM SIGGRAPH Asia 2012), 31(6):172, 2012
  71. [Sederberg2014] Sederberg, T. W. “Computer aided geometric design”, Course notes, 2014.
  72. [PIL] Ierusalimschy, R., “Programming in Lua”, 3rd edition, 2013.
  73. [MansonSchaefer2013] Manson, J.; Schaefer, S. “Analytic Rasterization of Curves with Polynomial Filters”, Computer Graphics Forum (Proceedings of Eurographics), 32(2):499–507, 2013.
  74. [NVPR] Kilgard, M. et al. “NV Path Rendering”, version 35, 2014.
  75. [NehabHoppe2014] Nehab, D.; Hoppe, H. “A fresh look at generalized sampling”, Foundations and Trends in Computer Graphics and Vision, 8(1):1–84, 2014.
  76. [GanacimEtAl2014] Ganacim, F.; Lima, R. S.; de Figueiredo, L. H.; Nehab, D. “Massively-parallel vector graphics”, ACM Transactions on Graphics (Proceedings of the ACM SIGGRAPH Asia 2014), 36(6):229, 2014.
  77. [FreeType] The Freetype Project, “FreeType glyph conventions”, 2014.
  78. [Hardprint] B. MacEvoy. “Color vision”, 2015.
  79. [OpenType] Mircrosoft Corporation, “OpenType specification”, 2015.
  80. [Unicode] Unicode consortium, “Unicode standard”, version 8.0, 2015.
  81. [HarfBuzz] HarfBuzz, “OpenType text shaping engine”, 2016.
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

a/html>