Scratchapixel: Computer Graphics Programming from Scratch • Hacker News Board

Re: Scratchapixel: Computer Graphics Programming from Scratch

#41

Post by userbinator » Sat, May 21, 2016, 11:15 PM UTC

pandaman wrote: post #24

dreamcompiler wrote: post #2

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.

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.

Actually, what's really replaced Bresenham is fixed-point. Dead-simple and non-branchy code with less than a dozen instructions in the main loop. Floating-point is still not exactly as fast as integer arithmetic:

https://hbfs.wordpress.com/2009/07/28/faster-than-bresenhams...

Re: Scratchapixel: Computer Graphics Programming from Scratch

#42

Post by alejohausner » Sat, May 21, 2016, 11:25 PM UTC

pandaman wrote: post #35

clarry wrote: post #34

Earlier quoted context omitted.

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…

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 accum…

Back in the mid 80s I rediscovered a form of Bresenham on PDP-11 assembler that used integer overflow to avoid branches. I've forgotten the details, but I remember that it was integer only, and used an accumulator word which, on overflow, became a small number (somehow triggering a change in the dependent coordinate). Damn I wish I could remember the details. One of these days I'll dig up the assembler specs and re-derive it.

Or maybe I'll discover I was using a branch after all!

Re: Scratchapixel: Computer Graphics Programming from Scratch

#43

Post by pandaman » Sat, May 21, 2016, 11:29 PM UTC

userbinator wrote: post #41

pandaman wrote: post #24

Earlier quoted context omitted.

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.

Actually, what's really replaced Bresenham is fixed-point. Dead-simple and non-branchy code with less than a dozen instructions in the main loop. Floating-point is still not exactly as fast as integer arithmetic: https://hbfs.wordpress.com/2009/07/28/faster-than-bresenhams...

Fixed point is a good approach for line drawing but doing a sqrt for circles with integer arithmetics does not work really that well even if you don't know how to convert floats to ints fast (like author of the article you linked :)).

Re: Scratchapixel: Computer Graphics Programming from Scratch

#44

Post by alejohausner » Sat, May 21, 2016, 11:31 PM UTC

khedoros wrote: post #23

clarry wrote: post #6

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, an…

I remember doing something similar (ignoring matrix transforms and hand-calculating everything with trig because I wasn't comfortable with it). It works fine, and it's great for a theoretical understanding of how rasterization works. I like starting from the basics that way too, then building on it. I think that most tutorials and such have a more practical focus though, with the goal of getting you to practical use…

Ignoring matrix transformations is easy, as long as the eye point is at the origin. Then yes, the algebra is almost trivial: projection is just divide-by-z. But the moment you move the camera, or stretch and turn objects, or worry about clipping, you need the full machinery that matrices provide. They're not that mysterious. I wish they were taught in high school, because they would motivate kids to learn graphics and programming.

Re: Scratchapixel: Computer Graphics Programming from Scratch

#45

Post by alejohausner » Sat, May 21, 2016, 11:38 PM UTC

angersock wrote: post #28

clarry wrote: post #6

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, an…

We learned basic vector arithmetic back in highschool doing our own gamedev stuff, and it's pretty straightforward. The use of matrices as "mapping" one space to another likewise so. Any approach that ignores the relevant parts of linear algebra, though, is probably going to collapse under its own weight as things get more complicated--experiencing that collapse may be interesting from a learning perspective, but I s…

This. You went to the right high school. Matrices and vectors are just a subset of linear algebra, and can definitely be taught to teenagers.

When I teach graphics to 3rd-year college undergraduates, I tell them "this is what all that point-and-vector stuff you learnt in high school was really meant for". They've usually forgotten it all, but it comes back to them quickly, and the matrix stuff on top of that isn't very hard, so I can get them up to speed pretty quickly.

Most CS degrees require linear algebra, which talks about vector spaces, gaussian elimination, diagonalization, rank, which is all useless for graphics! Too bad that course is usually relegated to the math department, which doesn't know how fun and useful a small subset of linear algebra is!

Re: Scratchapixel: Computer Graphics Programming from Scratch

#46

Post by arthurcolle » Sat, May 21, 2016, 11:42 PM UTC

lastofus wrote: post #15

clarry wrote: post #6

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, an…

What you are wanting is this book: "Tricks of the 3D Game Programming Gurus" by Andre LaMothe. The book teaches you how to write a 3D software rasterizer from first principles. The first part of the book is nothing but a well written linear algebra primer. The book then assumes you have nothing but a C++ compiler and a pointer to the frame buffer like you might get using SDL. Unfortunately the book appears to be out…

http://portal.aauj.edu/portal_resources/downloads/programmin...

Re: Scratchapixel: Computer Graphics Programming from Scratch

#47

Post by pandaman » Sat, May 21, 2016, 11:44 PM UTC

alejohausner wrote: post #42

pandaman wrote: post #35

Earlier quoted context omitted.

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 accum…

Back in the mid 80s I rediscovered a form of Bresenham on PDP-11 assembler that used integer overflow to avoid branches. I've forgotten the details, but I remember that it was integer only, and used an accumulator word which, on overflow, became a small number (somehow triggering a change in the dependent coordinate). Damn I wish I could remember the details. One of these days I'll dig up the assembler specs and re-d…

The whole point of Bresenham is choosing between two integer values to minimize the accumulated error. You can totally implement any conditional computation without explicit conditional branch instructions e.g. using jump tables, conditional moves or predication etc. But the nature of your algorithm will remain conditional and a modern CPU still won't be able to process it as fast as a naive implementation.

Re: Scratchapixel: Computer Graphics Programming from Scratch

#48

Post by clarry » Sun, May 22, 2016, 12:05 AM UTC

alejohausner wrote: post #39

clarry wrote: post #6

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, an…

The reason that 4x4 matrices are used so much in graphics is their versatility: you can use them to implement modeling (placing an object into the world), viewing (changing a world point into camera coords), projection and clipping (putting a camera-coord point into clipping coords), color transformations (after all, both x,y,z,w and r,g,b,a are coordinates of a 4D point). That's why there's matrix multipliers built…

> I understand where you're coming from: translating a point is just 3 additions, so why do a full matrix x point multiply? Scaling is just 3 multiplies, and so on. But if you've got a hardware matrix-point multiplier, all those transformations cost the same, so you're not saving time by devoting special code to each kind of transformation.

Oh, I'm not arguing against the utility of matrices. I just find that they were too abstract a concept for the young me to learn at the same time while trying to understand 3d graphics. They're an useful abstraction for when you know them, but if you don't, focusing on them is a good way to frustrate a young mind who just wants to understand 3d transformation and perspective projection.

Even if you read about matrices and vectors, it takes quite a bit longer to get comfortable with them and build intuition. Instead, with weak knowledge and lack of intuition (can you expect more from a young teen who had to try learn about these things himself on the net in a foreign language?), dressing the simple core of 3d computations in that language only serves as a barrier to understanding, and you have to work hard backwards to really understand what's happening "under the hood", below these abstractions. It's a bit much to comprehend, and I don't think it helps. It didn't help me for sure. And that ended up being incredibly frustrating, crushing even. It could just be that I am dumber than the lot of you?

If anything, it would've been better if someone could've shown how simple and intuitive the underlying arithmetic is, and then from there on go on to show how one can wrap things up with useful abstractions to combine later. This would give the motivation to learn the more abstract material, and straight away show how it is useful, applying it to things you know already. To me, that would make as much sense as learning to do arithmetic before learning about functions and solving equations.

And really, I wasn't that interested in using graphics hardware or some library. For me the point was in doing it all from scratch.

Re: Scratchapixel: Computer Graphics Programming from Scratch

#49

Post by clarry » Sun, May 22, 2016, 12:11 AM UTC

alejohausner wrote: post #44

khedoros wrote: post #23

Earlier quoted context omitted.

I remember doing something similar (ignoring matrix transforms and hand-calculating everything with trig because I wasn't comfortable with it). It works fine, and it's great for a theoretical understanding of how rasterization works. I like starting from the basics that way too, then building on it. I think that most tutorials and such have a more practical focus though, with the goal of getting you to practical use…

Ignoring matrix transformations is easy, as long as the eye point is at the origin. Then yes, the algebra is almost trivial: projection is just divide-by-z. But the moment you move the camera, or stretch and turn objects, or worry about clipping, you need the full machinery that matrices provide. They're not that mysterious. I wish they were taught in high school, because they would motivate kids to learn graphics an…

Nope, you totally don't need matrices to rotate, scale, and translate stuff. It's all very simple addition, multiplication and a wee tiny bit of trigonometry. As trivial as the perspective divide. In a 3D renderer, this is among the simplest and most straightforward of things. You can take it step by step and each step should be pretty straightforward to explain and illustrate. That is what is needed to build intuition and dispel the magic. After that, matrices are just a convenient abstraction, and perhaps more importantly, a reasonable way to express your intent to the underlying graphics library or hardware. Which you don't necessarily want to use.

Re: Scratchapixel: Computer Graphics Programming from Scratch

#50

Post by alejohausner » Sun, May 22, 2016, 12:34 AM UTC

clarry wrote: post #49

alejohausner wrote: post #44

Earlier quoted context omitted.

Ignoring matrix transformations is easy, as long as the eye point is at the origin. Then yes, the algebra is almost trivial: projection is just divide-by-z. But the moment you move the camera, or stretch and turn objects, or worry about clipping, you need the full machinery that matrices provide. They're not that mysterious. I wish they were taught in high school, because they would motivate kids to learn graphics an…

Nope, you totally don't need matrices to rotate, scale, and translate stuff. It's all very simple addition, multiplication and a wee tiny bit of trigonometry. As trivial as the perspective divide. In a 3D renderer, this is among the simplest and most straightforward of things. You can take it step by step and each step should be pretty straightforward to explain and illustrate. That is what is needed to build intuiti…

Agreed: moving, turning and stretching don't need matrices, to be understood. But moving the camera away from (0 0 0) is going to require a change of coordinates. I'm not sure how to explain that process in a simple way that avoids matrices.