10 ms·

Scratchapixel: Computer Graphics Programming from Scratch

239 points by MrHamdulay 10y ago

dreamcompiler 10y ago
Maybe I missed it, but I didn't see any discussion of the Bresenham family of algorithms. I realize this is always done for you nowadays, but if you're really teaching pixels from scratch, it seems like drawing lines and circles from raw pixels needs to be covered.
- pavlov 10y ago
  The site focuses on raytracing, so it's all about 3D algorithms.
  - dreamcompiler 10y ago
    Fair enough.
    - padator 10y ago
      99% of the computer graphics you see on your screen everyday are made of simple lines, circles, curves, and text in 2D. 3D is useful mostly for games, movies, and CAD software. I don't understand this over focus on 3D. I think the latest edition of "Computer Graphics: principles and practice" does not even teach bresenham anymore. This seems wrong to me.
      - jacobolus 10y ago
        Our current CPU-based 2D vector graphics rendering pipelines are completely unmatched to modern hardware. They’re lumbering decades-old dinosaurs with poor render quality (full of nasty visual artifacts) and ridiculously slow speed compared to the possibilities on a GPU (or even compared to better-cache-optimized CPU algorithms, frankly). I really wish everyone would move toward something like this instead: http://w3.impa.br/~diego/projects/GanEtAl14/ http://w3.impa.br/~diego/projects/GanEtAl14/
      - dahart 10y ago
        I'm only arguing for fun, and because I love 3d graphics, don't take this personally. I'm upvoting your comment to offset my argumentative reply. :) You say 'games and movies' like those are niche markets. You can't watch any TV without seeing 3d graphics. And chances are you see a lot more 3d on your computer than you think while you work. Windows, Mac OSX, & Linux all have 3d hardware accelerated windowing features for task switching, virtual desktops, and lots of other fun tidbits. Plus, you might not be playing enough games, if you play games less than 1% of your time. I'm not sure who's over focused on 3d, but it'd be pretty weird to put together a site like scratchapixel.com without 3d. Finally, Bresenham's algorithm has historical significance, but is no longer generally useful, even for line drawing. Maybe if it's gone from CGP&P, that's a clue? Aliased, single pixel wide lines are almost never used. If you want soft edges or thick lines or curves or texture, you're a lot better off focusing on polygons from the start.
- tdicola 10y ago
  Sadly if you're actually implementing Bresenham's algorithm today you're doing something very wrong (or don't care about performance). Drawing lines and shapes is all a matter of pumping the desired geometry and shaders into your GPU today and letting it take care of the rasterization--running Bresenham's algorithm on your CPU will be many orders of magnitude slower.
  - Narishma 10y ago
    There are still uses for software 3d rendering. Some modern game engines for example use it for lighting or culling purposes.
    - deleted 10y ago
      [deleted]
  - dreamcompiler 10y ago
    No argument. That's why I said I realized this was always done for you today. But somebody had to build and program that GPU, and for those of us who care about such details, it would be nice to learn how rasterization works in a GPU. I had assumed that GPUs were still using Bresenham-like DDAs, but I learned from the above discussion that fixed-point non-branching algorithms may have become more common.
- pandaman 10y ago
  Bresenham algorithms replaced expensive (at the time) floating point computation with fast (at the time) flow control. Nowadays it's exactly opposite: float is cheap and control is expensive so they only have historical value.
  - clarry 10y ago
    We're still doing plenty of graphics on the CPU. For many applications, I'd prefer that it stay that way. And it doesn't seem like CPUs are becoming massively parallel anytime soon.
    - pandaman 10y ago
      The CPUs still had been doing floating point math much faster than flow control for the past 20 years or so.
      - clarry 10y ago
        Can you point me to relevant examples of line drawing or related things (e.g. triangle or polygon filling) that is faster to do in floating point (which may eventually need to convert to integer for addressing) than the old school way? Besides, it's not like the line drawing needs much in the control flow aside from a bit of setup and then a loop. Which you'll need with floating point too. And if you're e.g. filling a triangle? Going the barycentric way, you have a relatively speaking big amount of floating point operations per pixel, in addition to the loop, plus some initial setup. And you might have to compare signs... I don't believe it's faster. But I'm open to being shown wrong.
        pandaman 10y ago
        Sure, go find a Bresenham line drawing first, verify that it does flow control for every step (a pixel) then compare it to the naive implementation (y = kx + a). Loops are not as expensive as what Bresenham does since even the simple branch prediction works fine for them and there are even better ways the CPU can deal with a loop on newer CPUs. Bresenham's switch is inherently unpredictable since it's comparing accumulated errors.
clarry 10y ago
What I don't get is why nearly all resources on 3D graphics assume the reader is familiar with matrices and linear algebra. For those who don't speak that language, what you're doing is plotting numbers into a magic box, doing a magic multiply, and hey presto, we got 3D! Magic. Meanwhile a teenager could easily get an intuitive grasp of 3D graphics if you just explained how translation is nothing besides addition, and that to rotate, you just use good old trig functions to generate rotated basis vectors along which to plot your vertices (really easy to show with images and animations too). And that magic perspective, to make things get smaller as they get further from the camera, is just one divide by the depth away... yes, all very basic arithmetic. And no need for magic such as homogeneous coordinates. They're just a convenience for when you do things a certain way. You don't need to go to college or even high school for 3D rasterization. But most if not all texts pretty much want to assume such a background? Actually, I'm quite tempted to try write such a tutorial for the 12-year-old me. Too bad I can't travel back in time to see if I'd actually understand it (but I have a strong feeling I could come up with something good enough). Yeah, the lack of approachable material was very frustrating for me back then. In the end I wrote a very primitive renderer (with plenty of trigonometry per vertex) which was way too slow and complicated to be useful. Because I didn't realize how simple the problem actually is.
- sillysaurus3 10y ago
  Yes. I was able to make a Quake-like clone when I was 17 with no knowledge of how matrices worked or linear algebra. This was before Unity et al, so I had to build it from scratch. You can get surprisingly far by stringing magical utility functions together. The reason I know those things now is because I wasn't forced to learn them then. Detail comes after engagement.
  - liamzebedee 10y ago
    Would love to see the source for that, if you still had it.
- dahart 10y ago
  > I'm quite tempted to try write such a tutorial You should do it! I agree and think that making 3D approachable is possible, and that most tutorials fail to make it easier than already available materials. I'm not sure it's easy to do, but if you succeed then people will benefit and if it turns out to be hard, you'll have developed a stronger appreciation for the problem and/or the motivation to solve it.
dahart 10y ago
Anyone know who's behind the site? I looked around, but all I found was a FAQ on the older version of the site that asks the question and doesn't answer, aside from "VFX professionals".
dahart 10y ago
This is a great resource! For those interested in a very quick and direct intro to writing code for ray tracing, something I think supplements Scratchapixel nicely, you might want to also check out "Ray Tracing in One Weekend". http://in1weekend.blogspot.com/2016/01/ray-tracing-in-one-weekend.html http://in1weekend.blogspot.com/2016/01/ray-tracing-in-one-we.... It's a $3 ebook on Amazon, but the blog post has lots of free resources including the complete code for the small ray tracer developed in the book. Written Peter Shirley, by a graphics prof. friend of mine, well known in graphics / ray tracing / global illumination circles.
- Keyframe 10y ago
  I didn't know Peter Shirley wrote more books! "Realistic Ray Tracing" was definitely a good introductory book back in the day.
ivan_ah 10y ago
Wow this is an awesome online book. Goes into a lot of details, and uses words to convey the important things + supports it with code. Another good tutorial, more specific to OpenGL, is this one: http://www.songho.ca/opengl/index.html http://www.songho.ca/opengl/index.html I liked this one because each lesson has a binary you can download and run on your computer (only tested on Mac).
- Narishma 10y ago
  I wouldn't recommend that one. It teaches the old deprecated fixed function OpenGL.
kowdermeister 10y ago
I give them a big kudos for adding lots of illustrations, it's vital to have good visual representation for math concepts. > Evaluating the curve's equation for values of tt going from 0 to 1, is sort of the same as walking along the curve. It is important to understand that tt is a scalar but that the result of the equation for any tt contained in the range [0:1] is a position in 3D space (for 3D curves, and obviously a 2D point for 2D curves). In other words, if we need to visualise a parametric curve, all we have to do is to evaluate the curve's equation for increasing values of tt at some regular positions (it doesn't have to be though), and connecting the resulting positions in space to create a polygonal path (as illustrated in figure 5). Unfortunately this is the language that you should avoid if you want to explain these concepts for beginners. Too technical, too rigid, too dry. I sort of understand what it says, but it could be done in much simpler way. I'd put it this way: "We have a function that describes the bezier curve. If you call that function with the P1-4 parameters you will receive X,Y (or Z if you do 3D) coordinates that you can easily plot and connect with straight lines. You also need to specify how many segments you want to receive, this will be resolution of the curve." Or something like this. Better explained ( betterexplained.com/calculus/ ) does a good job at this and I recently recently rediscovered Kirupa, I love his tutorials: https://www.kirupa.com/html5/animating_with_easing_functions_in_javascript.htm https://www.kirupa.com/html5/animating_with_easing_functions...
amelius 10y ago
I was surprised this starts at 3D graphics, and completely skips important 2D techniques, such as drawing/shading lines and polygons (which are also useful for doing 3D stuff).
TACIXAT 10y ago
These are the other graphics related tutorials I have found. Ray Tracing in a Weekend Series. Most the way through the first book and I plan on continuing it. [1][2][3] Tiny Renderer - How OpenGL Works. A software renderer in 500 lines of code. Wiki has a full tutorial. [4] The Book of Shaders. A step by step introduction into fragment shaders. [5] [1] https://www.amazon.com/_/dp/B01B5AODD8 https://www.amazon.com/_/dp/B01B5AODD8 [2] https://www.amazon.com/_/dp/B01CO7PQ8C https://www.amazon.com/_/dp/B01CO7PQ8C [3] https://www.amazon.com/_/dp/B01DN58P8C https://www.amazon.com/_/dp/B01DN58P8C [4] https://github.com/ssloy/tinyrenderer/wiki https://github.com/ssloy/tinyrenderer/wiki [5] https://thebookofshaders.com/ https://thebookofshaders.com/

239 points by MrHamdulay 10y ago

Maybe I missed it, but I didn't see any discussion of the Bresenham family of algorithms. I realize this is always done for you nowadays, but if you're really teaching pixels from scratch, it seems like drawing lines and circles from raw pixels needs to be covered.

pavlov 10y ago
The site focuses on raytracing, so it's all about 3D algorithms.
- dreamcompiler 10y ago
  Fair enough.
  - padator 10y ago
    99% of the computer graphics you see on your screen everyday are made of simple lines, circles, curves, and text in 2D. 3D is useful mostly for games, movies, and CAD software. I don't understand this over focus on 3D. I think the latest edition of "Computer Graphics: principles and practice" does not even teach bresenham anymore. This seems wrong to me.
    - jacobolus 10y ago
      Our current CPU-based 2D vector graphics rendering pipelines are completely unmatched to modern hardware. They’re lumbering decades-old dinosaurs with poor render quality (full of nasty visual artifacts) and ridiculously slow speed compared to the possibilities on a GPU (or even compared to better-cache-optimized CPU algorithms, frankly). I really wish everyone would move toward something like this instead: http://w3.impa.br/~diego/projects/GanEtAl14/ http://w3.impa.br/~diego/projects/GanEtAl14/
    - dahart 10y ago
      I'm only arguing for fun, and because I love 3d graphics, don't take this personally. I'm upvoting your comment to offset my argumentative reply. :) You say 'games and movies' like those are niche markets. You can't watch any TV without seeing 3d graphics. And chances are you see a lot more 3d on your computer than you think while you work. Windows, Mac OSX, & Linux all have 3d hardware accelerated windowing features for task switching, virtual desktops, and lots of other fun tidbits. Plus, you might not be playing enough games, if you play games less than 1% of your time. I'm not sure who's over focused on 3d, but it'd be pretty weird to put together a site like scratchapixel.com without 3d. Finally, Bresenham's algorithm has historical significance, but is no longer generally useful, even for line drawing. Maybe if it's gone from CGP&P, that's a clue? Aliased, single pixel wide lines are almost never used. If you want soft edges or thick lines or curves or texture, you're a lot better off focusing on polygons from the start.
tdicola 10y ago
Sadly if you're actually implementing Bresenham's algorithm today you're doing something very wrong (or don't care about performance). Drawing lines and shapes is all a matter of pumping the desired geometry and shaders into your GPU today and letting it take care of the rasterization--running Bresenham's algorithm on your CPU will be many orders of magnitude slower.
- Narishma 10y ago
  There are still uses for software 3d rendering. Some modern game engines for example use it for lighting or culling purposes.
  - deleted 10y ago
    [deleted]
- dreamcompiler 10y ago
  No argument. That's why I said I realized this was always done for you today. But somebody had to build and program that GPU, and for those of us who care about such details, it would be nice to learn how rasterization works in a GPU. I had assumed that GPUs were still using Bresenham-like DDAs, but I learned from the above discussion that fixed-point non-branching algorithms may have become more common.
pandaman 10y ago
Bresenham algorithms replaced expensive (at the time) floating point computation with fast (at the time) flow control. Nowadays it's exactly opposite: float is cheap and control is expensive so they only have historical value.
- clarry 10y ago
  We're still doing plenty of graphics on the CPU. For many applications, I'd prefer that it stay that way. And it doesn't seem like CPUs are becoming massively parallel anytime soon.
  - pandaman 10y ago
    The CPUs still had been doing floating point math much faster than flow control for the past 20 years or so.
    - clarry 10y ago
      Can you point me to relevant examples of line drawing or related things (e.g. triangle or polygon filling) that is faster to do in floating point (which may eventually need to convert to integer for addressing) than the old school way? Besides, it's not like the line drawing needs much in the control flow aside from a bit of setup and then a loop. Which you'll need with floating point too. And if you're e.g. filling a triangle? Going the barycentric way, you have a relatively speaking big amount of floating point operations per pixel, in addition to the loop, plus some initial setup. And you might have to compare signs... I don't believe it's faster. But I'm open to being shown wrong.
      - pandaman 10y ago
        Sure, go find a Bresenham line drawing first, verify that it does flow control for every step (a pixel) then compare it to the naive implementation (y = kx + a). Loops are not as expensive as what Bresenham does since even the simple branch prediction works fine for them and there are even better ways the CPU can deal with a loop on newer CPUs. Bresenham's switch is inherently unpredictable since it's comparing accumulated errors.

clarry 10y ago

What I don't get is why nearly all resources on 3D graphics assume the reader is familiar with matrices and linear algebra. For those who don't speak that language, what you're doing is plotting numbers into a magic box, doing a magic multiply, and hey presto, we got 3D! Magic. Meanwhile a teenager could easily get an intuitive grasp of 3D graphics if you just explained how translation is nothing besides addition, and that to rotate, you just use good old trig functions to generate rotated basis vectors along which to plot your vertices (really easy to show with images and animations too). And that magic perspective, to make things get smaller as they get further from the camera, is just one divide by the depth away... yes, all very basic arithmetic. And no need for magic such as homogeneous coordinates. They're just a convenience for when you do things a certain way. You don't need to go to college or even high school for 3D rasterization. But most if not all texts pretty much want to assume such a background? Actually, I'm quite tempted to try write such a tutorial for the 12-year-old me. Too bad I can't travel back in time to see if I'd actually understand it (but I have a strong feeling I could come up with something good enough). Yeah, the lack of approachable material was very frustrating for me back then. In the end I wrote a very primitive renderer (with plenty of trigonometry per vertex) which was way too slow and complicated to be useful. Because I didn't realize how simple the problem actually is.

sillysaurus3 10y ago
Yes. I was able to make a Quake-like clone when I was 17 with no knowledge of how matrices worked or linear algebra. This was before Unity et al, so I had to build it from scratch. You can get surprisingly far by stringing magical utility functions together. The reason I know those things now is because I wasn't forced to learn them then. Detail comes after engagement.
- liamzebedee 10y ago
  Would love to see the source for that, if you still had it.
dahart 10y ago
> I'm quite tempted to try write such a tutorial You should do it! I agree and think that making 3D approachable is possible, and that most tutorials fail to make it easier than already available materials. I'm not sure it's easy to do, but if you succeed then people will benefit and if it turns out to be hard, you'll have developed a stronger appreciation for the problem and/or the motivation to solve it.

dahart 10y ago

Anyone know who's behind the site? I looked around, but all I found was a FAQ on the older version of the site that asks the question and doesn't answer, aside from "VFX professionals".

dahart 10y ago

This is a great resource! For those interested in a very quick and direct intro to writing code for ray tracing, something I think supplements Scratchapixel nicely, you might want to also check out "Ray Tracing in One Weekend". http://in1weekend.blogspot.com/2016/01/ray-tracing-in-one-weekend.html http://in1weekend.blogspot.com/2016/01/ray-tracing-in-one-we.... It's a $3 ebook on Amazon, but the blog post has lots of free resources including the complete code for the small ray tracer developed in the book. Written Peter Shirley, by a graphics prof. friend of mine, well known in graphics / ray tracing / global illumination circles.

Keyframe 10y ago
I didn't know Peter Shirley wrote more books! "Realistic Ray Tracing" was definitely a good introductory book back in the day.

ivan_ah 10y ago

Wow this is an awesome online book. Goes into a lot of details, and uses words to convey the important things + supports it with code. Another good tutorial, more specific to OpenGL, is this one: http://www.songho.ca/opengl/index.html http://www.songho.ca/opengl/index.html I liked this one because each lesson has a binary you can download and run on your computer (only tested on Mac).

Narishma 10y ago
I wouldn't recommend that one. It teaches the old deprecated fixed function OpenGL.

kowdermeister 10y ago

I give them a big kudos for adding lots of illustrations, it's vital to have good visual representation for math concepts. > Evaluating the curve's equation for values of tt going from 0 to 1, is sort of the same as walking along the curve. It is important to understand that tt is a scalar but that the result of the equation for any tt contained in the range [0:1] is a position in 3D space (for 3D curves, and obviously a 2D point for 2D curves). In other words, if we need to visualise a parametric curve, all we have to do is to evaluate the curve's equation for increasing values of tt at some regular positions (it doesn't have to be though), and connecting the resulting positions in space to create a polygonal path (as illustrated in figure 5). Unfortunately this is the language that you should avoid if you want to explain these concepts for beginners. Too technical, too rigid, too dry. I sort of understand what it says, but it could be done in much simpler way. I'd put it this way: "We have a function that describes the bezier curve. If you call that function with the P1-4 parameters you will receive X,Y (or Z if you do 3D) coordinates that you can easily plot and connect with straight lines. You also need to specify how many segments you want to receive, this will be resolution of the curve." Or something like this. Better explained ( betterexplained.com/calculus/ ) does a good job at this and I recently recently rediscovered Kirupa, I love his tutorials: https://www.kirupa.com/html5/animating_with_easing_functions_in_javascript.htm https://www.kirupa.com/html5/animating_with_easing_functions...

amelius 10y ago

I was surprised this starts at 3D graphics, and completely skips important 2D techniques, such as drawing/shading lines and polygons (which are also useful for doing 3D stuff).

TACIXAT 10y ago

These are the other graphics related tutorials I have found. Ray Tracing in a Weekend Series. Most the way through the first book and I plan on continuing it. [1][2][3] Tiny Renderer - How OpenGL Works. A software renderer in 500 lines of code. Wiki has a full tutorial. [4] The Book of Shaders. A step by step introduction into fragment shaders. [5] [1] https://www.amazon.com/_/dp/B01B5AODD8 https://www.amazon.com/_/dp/B01B5AODD8 [2] https://www.amazon.com/_/dp/B01CO7PQ8C https://www.amazon.com/_/dp/B01CO7PQ8C [3] https://www.amazon.com/_/dp/B01DN58P8C https://www.amazon.com/_/dp/B01DN58P8C [4] https://github.com/ssloy/tinyrenderer/wiki https://github.com/ssloy/tinyrenderer/wiki [5] https://thebookofshaders.com/ https://thebookofshaders.com/