Hacker News new | past | comments | ask | show | jobs | submit login
Computer Graphics from Scratch (2017) (gabrielgambetta.com)
296 points by fanf2 45 days ago | hide | past | favorite | 43 comments

Hi! Author here. Happy to answer any questions :)

A bit of shameless self-promotion, if I may: I've been working with No Starch Press to turn this into an actual book, and it's coming out within a couple of months! I'm going to update the website version soon, to reflect (heh) the much-improved quality of the text after months of editing. Stay tuned!

Thanks so much for making the book available on the site.

Have you ever written about your game development company and how you managed to get the contracts to produce the Ghost Whisperer and other games?

I haven't written much about Mystery Studio [0]. It's not that interesting :)

Ghost Whisperer, CSI:NY, and Murder She Wrote were done in partnership with Legacy [1], who are in Los Angeles and have the contacts. For CSI:NY it was really exciting that the actors of the show recorded the voiceovers, but we were nowhere near them :(

[0] https://en.wikipedia.org/wiki/Mystery_Studio

[1] http://https://legacygames.com

Thank you for taking the time to respond!

oh wow! thanks a lot for writing the book. definitely looking forward to it. this tutorial is definitely top 3 for me.

Share the other two with us!

Congrats on finishing the book. I hope it will turn out to be a good investment of your time :)

Thank you so much. It looks really great. If I ever manage to get a basic raytracer working , I will buy the book.

Thanks for your kind words! I think the book has a good chance to successfully guiding you the process of writing a fully-featured raytracer, not just a basic one :)

> "The sense of accomplishment you get when your SQL query runs just right is nothing compared to what you feel the first time you get ray traced reflections right."

This line is very motivating to someone who works with data frequently.

Everyone in my age group that started programming did so because they wanted to do computer graphics. Every single one. It's definitely a great hook to inspire learning.

Same here. And yet I spent...21 years programming before I finally got around to learning it.

I did a raytracer in BASIC on an 8-bit machine. Took two weeks and a nondescript lump of pixels was the result. But I knew it was a torus.

> the first time you get ray traced reflections right.

This guy graphics! I remember my highest pleasure in programming was attained when I first drew a rasterized triangle. Of uniform color.

It is one of the fun things about graphics programming. Bugs can also sometimes be funny enough to dispel the frustration.

But when you've been futzing around with quaternions all day, and your camera finally stops acting like a hyperactive husky who hasn't had a walk in days...well, I imagine that's close to what it felt like when they got the internal combustion engine to stop being an external combustion engine.

Many versions of SQL are Turing complete, so one can probably do both at the same time!

Here it goes - MySQL raytracer https://www.pouet.net/prod.php?which=83222

Totally agree. Especially if you write a ray-tracer from scratch. To go from fiddling with some lines of code to suddenly moving around in a room with some objects in 3D is insane.

Because I am a big jerk, I am going to take this opportunity to complain about a pet peeve, and ask for brainstorming help.

This (generally-pretty-great) book, like many educational materials about computer graphics, makes a terminological choice that I believe to be plainly a mistake. It uses the word "rasterizer" to mean "renderer that works by applying transforms to polygons", as contrastive with a "raytracer" (more generally, a physically-based light transport model). (e.g. "Raytracing and Rasterization, which focus on the two main ways to make pretty pictures out of data").

Properly (from a descriptivist standpoint), a "rasterizer" is any algorithm that transforms vector data into raster data, where rasters are arrays of horizontal lines, each horizontal line composed of pixels. RAYTRACERS ARE RASTERIZERS. (I mean, not if you're using the raytracer to detect collisions or for some other purpose; only if you're using it to generate 2d images of any kind.)

Surely there must be some better terminology for the non-physically-based option? I tend to say "polygon-pusher", but this is my own neologism. Does anyone have any suggestions for a more accurate name for this type of renderer?

Saying "rasterizer" in the sense the book does is as common as saying "literally" to mean "figuratively", as common as writing "there" to mean "they're". So I know that probably there's no fixing it. But I'm still hoping.

The names reflect pretty well what’s in the inner loop. A rasterizer’s outer loop is over the scene (objects/triangles/etc), and the inner loop is over pixels. It does what it says in the sense that it’s rasterizing each primitive one at a time.

A ray tracer, on the other hand, is (sometimes) looping over pixels in the outer loop, and then iterating over objects (“traversing the scene”) in the inner loop.

The existing names are also good descriptors in the sense that they describe the core of what must be computed. A rasterizer always rasterizes. A ray tracer always traces rays but does not always result in pixels, the result can end up in a spatial data structure, it can trace resolution independent shadows & reflections, it can save results in a cache that gets rasterized later, it can end up in multiple pixels (splatting, pixel filtering), etc., etc.. Yes it’s very common to render pixels with a ray tracer, but it’s not required or inherently part of the algorithm, while rasterization doesn’t exist without pixels.

Thanks for pointing this out, I hadn't really thought about it this way.

You're technically correct (the best kind of correct!). Since raytracers draw pixels on the screen, and the screen is an array of horizontal lines, anything that draws pixels to the screen is a rasterizer.

On the other hand, "polygon-pushers" are rasterizers in a deeper sense: triangles are explicitly sliced into arrays of horizontal line segments, and this shapes how everything else works in them, e.g. the need to interpolate attribute values along the edges of each triangle so you can then interpolate them along each raster, etc. Raytracers do no such thing. So all renderers are rasterizers, but some are more rasterizer than others ;)

I also wonder what happens, for the sake of brainstorming, if you change the output to be something that is not a rectangular array of horizontal sets of pixels. In that case you probably wouldn't call a raytracer "a rasterizer" since there would be no raster data, but a polygon pusher would still fit the name, since it uses rasters internally?

BTW, I'll never accept "literally" used as "figuratively", "there" for "they're", or "could care less" unless you do care a little bit. So I don't think you're a jerk, and your comment prompted some interesting thinking!

Note that the interpolating of attribute values along the edges of the triangle is not exclusive to a polygon-pusher, right? If your raytracer has textures, it still interpolates the much same way the polygon-pusher does, right? Am I getting confused? (Of course the raytracer's geometry is less likely to be triangles than the polygon-pusher's geometry, but let's keep it apples-to-apples). And of course it applies to any kind of textures: baked in lightmaps, normal maps, whatever.

I mean, sure, the polygon-pusher presumably does it post-transforms, i.e. in screenspace, and the raytracer does it in some other space (exactly what space is gonna depend on implementation of the camera and stuff I think), but I think it's pretty similar?

But as far as I know the depth-checking in a polygon pusher is totally about the raster, so in that sense, yeah, the (non-wireframe) polygon-pusher has a deeper relationship to rasters.

If you want more technically accurate terms, you might call raytracers and polygon-pushers "image space" and "geometric space" renderers, respectively.

Worth noting that neither method is particularly physically based, and really just boils down to whether you approach the rasterization task "forwards" or "backwards". Which method ends up faster is essentially a function of how much geometry and how many pixels you have.

Follow-up: If you think that "rasterizer" is a good and accurate name for a polygon-transforming renderer, what would you call the rendering technology in the original Battlezone? It's not a ray-tracer. It works by taking line segments expressed as vectors in 3d space, and multiplying them through transformation matrices. But there are no rasters; it outputs to a vector display.

I admit, that's a rare example (though not unique; there's a reason wire-frames, as a display mode, came into existence). But I think it's absurd to say that the rasterizer is the heart of the polygon-transforming approach; the heart is the transformation matrix.

Drawing rasters or on a vector display comes later in the pipeline. Maybe there's a more complex taxonomy?

At the top level, you split polygon-transforming vs ray-tracing (or geometry-main-loop vs pixel-main-loop, or projecting vs searching-from-the-camera, or whatever). Then you split polygon-transforming by output style, raster display vs vector display?

I absolutely agree, drawing rasters or using a vector display (or doing neither, for example doing picking in UX or hitscan in a game) is later in the pipeline. I agree about the more complex taxonomy.

But I don't think it's a branching taxonomy? Both can raster-display, both can vector-display, and both can be used for things other than display. I feel like it's just a 2x3 matrix, or maybe I'm missing some rows columns.

I also agree with your other comment that, even though it's not strictly necessary to do any rasters at all (Battlezone), in 99.99% of cases polygon-pushers are more rasterizer-y than ray-tracers. Even if you're not texturing, you're doing depth occlusion checking (again, Battlezone and other wireframe renderers don't, but yeah, niche), and although there may be some way to do depth occlusion without rasters (z-buffer), I dunno what it is and I've never heard of anyone doing it any other way.

I dunno, when I've taught the material that your book covers (on rare occasion, in less-formal settings), I have definitely felt this need for a raytracer-vs-polygon-projecting taxonomy, and definitely felt a need to talk about rasterizing, but not felt a need to talk about rasterizing in the context of the taxonomy.

Oh come on, don't be pedantic. There is a term for non-physically-based rendered, it's called "rasterization". Just because it's technically incorrect doesn't mean it's any less of a colloquial term. To ignore this is to ignore how language actually works. Even the wikipedia page for Rasterization compares it with ray tracing.

Another splendid resource which I've found to be in the same spirit is Jamis Buck's The Ray Tracer Challenge. It follows a language-agnostic test-driven approach to making a raytracer from scratch.

The Ray Tracer Challenge is an awesome book. It was really fun to code the ray tracer!

This looks really cool! Earlier this year I built a software rasterizer from scratch, and it was one of the most fun/challenging projects I've done. I learned a ton about efficient memory layout, and the linear-algebra concepts behind projection are very fun.

A long while ago I did a lot of 2d graphics work. I read a blog post on 2d rasterization of lines with anti-aliasing. The post was very long and detailed. I felt awe at how much complexity the most simple operation could take. Drawing many lines pixel by pixel in a performant way while also making it look good is a challenging task. Just another one of those things we take for granted once it is encapsulated in a library/module.

Could you tell what resources you found the most helpful for optimising memory in the context of raytracing/rasterisation?

That sounds amazing.

What did you read prior to undertaking the project? How did you know what you needed to build? Have you been working in graphics awhile?

I would totally read any blog post or postmortem writeup you have if you decide to publish your results.

I didn't know any computer graphics or linear algebra beforehand. I bought a copy of this book[0], which is a bit dated, but goes through the basics really well. I also got a lot out of this lecture series[1].

I ended up doing a lot more math than I expected to understand the fundamentals of projection, basically teaching myself linear algebra, but that was pretty fun in itself.

My goal was to build a minimum-viable software rasterizer for embedded situations (STM32-F7). I still haven't gotten around to getting lighting to work efficiently, or to leverage SIMD, but I intend to whenever I get back to the project.

The source is here if you're curious: https://git.sr.ht/~zjm/Moon3D. There's also some screenshots/progress updates on my Twitter: https://twitter.com/zackmichener

[0]: https://www.pearson.com/us/higher-education/product/Foley-Co...

[1]: https://www.youtube.com/watch?v=01YSK5gIEYQ&list=PL_w_qWAQZt...

When I wrote one it was part of an intro to computer graphics class at university (sample syllabus https://web.cs.ucdavis.edu/~ma/ECS175/). There's probably a lot out there at the university level.

I took it well over a decade ago, but the current material is largely similar. Going in you were required to know C and C++, and math pre-reqs (Calculus, linear algebra). Other university classes might skip the rasterizer building, but I think its a useful foundation.

We started with basic OpenGL to render models. Then we replaced the OpenGL with our own rasterizer, adding features as you went. It was a tough class (10 week schedule), but very rewarding. Probably the worst part was debugging rendering issues. You could see the problem, but it was hard to locate where your math went wrong.

You can write a basic (read: slow) rasterizer in 100 lines or so. It's mostly math.


Very nice. I like it that ray tracing comes first: all the problems of lighting, shadows are resolved in a more natural way. Rasterization is a bit less intuitive, so it's good to present it later.

An excellent contribution. Education at this "full stack" level is something we should see more of.

I particularly enjoyed the concise explanation and code example in the Perspective Projection section. Often web based explanations are lacking. Not the case here!

As an eternal student and enthusiast of computer graphics, this is golden;

Does anyone have suggestions of a similar tutorial or intro to 2D graphic implementation?

Yes another computer graphics tutorial, there are tons of these out there. Would have loved to see southing unique about it.

I think I’ve done about three of them. All were good, but this one is my favorite. It covers both ray tracing and rasterization, and it doesn’t require any sort of development setup to jump in. Most important, the explanations are the best that I have found.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact