Triangles to Pixels - Computerphile

Audible free book: www.audible.com/computerphile
How do we go from 3D representations within a computer to pixels on a screen? John Chapman has the details!
John Chapman is a graphics programmer who blogs here: www.john-chapman.net
Graphics series with John Chapman:
1/ Universe of Triangles : • A Universe of Triangle...
2/ Power of the Matrix : • The True Power of the ...
3/ Triangles to Pixels : • Triangles to Pixels - ...
4/ Visibility Problem : • The Visibility Problem...
5/ Light and Shade in Computer Graphics: Coming Soon
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computerphile is a sister project to Brady Haran's Numberphile. See the full list of Brady's video projects at: bit.ly/bradychannels

[@superjugy]

Hahaha, the inception moment when you realize that the animations trying to represent the animation process are basically going through the exact same process it is trying to explain. XD

[@somewony]

Does anyone else really like this guys voice?

[@zoranhacker]

***** everyone thinks their voice is horrible

[@tiny_rebel]

So, curiously, if when you "move" a camera, it is not actually the camera turning but everything in the world rotating around the camera, then how does this translate into scenarios where there are multiple cameras? Is there a separate world for each camera? And, if so, how do the items that represent these cameras interact with one another?

[@GuildOfCalamity]

I never knew Sean Connery's son was so good with graphics math.

[@Kram1032]

/me: *reload sub page* "oh look, a new computerphile!" My phone: BEEP! /me looks at phone: 'new computerphile video uploaded' /me: "Well thanks, I was about to click on it and you delayed me!"

[@antivanti]

I wish he'd explained how the 2D-projection transformation works and also how it is determined if a pixel is within a triangle or not. Great video series over all however. =)

[@jbrun009]

My assumption based on no knowledge on the subject at all is that the computer determines what percent of triangle would be filling that pixel. To keep things easy for myself, its a black triangle with a white background, with 100 shades or color as the total range. If the triangle is only 50% in the pixel, the pixel will be perfectly grey. If theres more triangle in the pixel, it'll be darker grey. This is why in Microsoft Paint, the greatest graphic creation program of all time, if you type a fancy font with nice soft edges, then try to paint it a different color, only the middle of the letter will be painted, as the outer edges are all slightly different shades of the former color

[@OmegaCraftable]

Huzzah, love these videos!

[@PabloBrubeck]

This series in particular has inspired me to code my own 3D graphics in java... I'll like to see more about perspective projections, controling rotation in 3 axes, and lighting...

I'll share some of the math and routines I wrote long ago. I would suggest exploring Java3D and OpenGL APIs. ;)

[@PabloBrubeck]

Thanks!

[@RsTheZigec]

This is by far my favourite series of videos on all your chanels. Thanks !

[@ScottLahteine]

Looking forward to the next bit, which no doubt will talk about Normals and Culling (two of my favorite things about 3D graphics) and how Normals make both both Shading and Culling almost simple! If you manage to get into Shaders and Shader Language I'll be quadruply-impressed!

[@squidcaps4308]

Personally, i'm looking for video of shaders too.. I'm precisely at that point of learning curve myself...

[@serkval7025]

i really wish an episode about shaders

[@druidshmooid]

He already kinda covered normals and culling in his last video (about triangle vertices). He doesn't go into explicit detail, but he talks about how triangular vertices are always co-planar, and how we can determine front/back facing through the way we list the order of those vertices. Those pieces of information (and you know, the vertices themselves) are all you really need to calculate normals, and by extension perform back face culling. (Actually, he does explicitly mention back face culling in that video).

[@Dayanto]

I really hope they mention the depth buffer. That was probably my biggest 'aha!' experience I've had with computer graphics.

[@tobortine]

It's rare to see genius but even more so on You Tube.

[@lebagelboy]

these videos are just getting better and better

[@HunMASK]

I love these video series about 3D and all videos from Computerphile in general. I just wanted to say thank you and please keep up the good work.

[@mothman.industries]

Really enjoying this series. Thanks for putting it together, guys.

[@TheNoobilator]

This series of videos on triangles, matrices, and graphics etc was really awesome :)

[@squidcaps4308]

These videos are like gold to us, everything i've tried to say in thousands of posts compressed in to few minutes. Kudos and thank you from every teachers that has to explain the basics on 3D design, this is priceless. I'm sharing all videos from this series to our FB group (not gonna advertise so i'll leave the group name out). We try to learn, share and teach 3D design and level creation in the shortest time and simplest way possible (BTB or Bobs TrackBuilder combined with Google Sketchup has been so far the most intuitive tools to do that.).

[@cazino4]

Such an intuitive explanation of quite an involved topic. Thank you.

[@MindLessWiz]

Freaking awesome! Keep it up, I absolutely love this series!

[@apandaboy]

Thanks for this explanation. Always struggled to understand this. Nice to see it from a high level!

[@MohammadAdib]

I've always wanted to know this! Great video :)

[@piranha031091]

He looks a bit like a movie supervillain when he talks. Especially around 4:03 , I'd guess he'd make a convincing Joker!

[@ddoodm]

The perspective transform is quite simple in essence. 3D vertices can be transformed to 2D screen-space coordinates by simply dividing each component (X and Y) by the Z coordinate of a vertex. Transforming these newly calculated 2D coordinates to the centre of the screen, you'll see a perspective-projection effect. Easy, yet marvelous stuff!

[@clerisonn]

any example of calculation? or any site you know whith an example, thanks

[@ddoodm]

Clerison Campos Apologies for the late reply. Here's an excellent tutorial on perspective projection, and how to implement matrices to do the same thing more efficiently: www.scratchapixel.com/lessons/3d-advanced-lessons/perspective-and-orthographic-projection-matrix/perspective-projection-matrix/

[@GBFU2016]

Really like the videos from this guy can't wait for the next one. Would be cool to see a video of him talking about using a programming language to work these graphic representations and describing what a graphics engine is.

[@stalkerinis]

This is great! Hopefully the next video will be VERY in-depth about shaders. I would like him to talk about programmable shaders too :)

[@RyanJensenEE]

Wow. I'm really liking this video series!

[@zob314]

hey look, an actual use for all that math i learned in high school.

[@Ruxistico]

I'm blown away by that fact that I actually understand this. Chapman is doing an excellent job in explaining this - making the ideas seem simple and intuitive. I'm very grateful for this. If I were to program som very simple 3d objects in a language close to the hardware (since I want to understand the entire route from physical stuff in our world to pixels on the screen) - what language should I choose and where can I learn about it? Have a nice day.

[@ericsbuds]

awesome, cant wait for the next vid

[@Fuogger]

I must admit I'm curious about the projective transformation. And would love to see more about how it works

[@bruno_sjc_]

Bro, this channel is awesome

[@sergheiadrian]

Can you talk about Z-buffering and other hidden surface removal algorithms in a future episode? Also I would love to learn about antialiasing and anisotropic filtering. Great series of videos! Thank you.

[@reitube2]

Is there a video that talks about the last projection step in more detail D:?? I would really really really like to understand how people came up with the projection matrix.. I can understand the transformation matrices but the projection matrix is always soccery..

[@keistzenon9593]

i had to learn this from a book, this graphical explanation makes it so easy :p

[@Darieee]

you guys should add links between series of videos - it looks as if there's one before this one - is there ?

[@armouredhen30]

More videos with this guy please!

[@SyntekkTeam]

Awesome, I look forward to seeing it in more detail in future videos. In this example all the pixels are a color depending on which triangle. Will you be getting into anti-aliasing? Where if 2 triangles are on a pixel the color of the pixel is a mix of the colors of the 2 triangles?

[@cbbuntz]

Fourier Transform please!

[@Slutuppnu]

These videos are great. Please do one on how to interpolate pixels over the triangle (barycentric interpolation).

[@Pfaeff]

Will you also do a video about occlusion and depth-buffering? That is an important aspect when going from 3D to a 2D rasterized image.

[@DFX2KX]

great video as always, guys! Wow, takes me back a few years. (and next we'll talk about backface culling :P:)

[@LymonAdd]

It would be great to highlight search path algorithm and 2-D tree partition that, as I remember, are used to calculate which vertex is observable from current point of view and thus which one should be recalculated.

[@seigeengine]

The part that I've never seen an explanation for is WHY you move the world around the camera, rather than the camera moving around the world.

[@ashwith]

So that's who Sean is (never seen him on any videos before). Thanks for making these videos! :-)

[@ammobake]

This basically describes exactly how Autocad and other software models in 3-dimensions. Sometimes, you can extrude a 2-dimensional object into the Z coordinate and be finished but usually it is more complicated. However, You also have the option of creating 3D primitive in "model space" which you can then slice, cut, and manipulate that into the finished product (sometimes easier). There are also ways to create the 3d object as a wireframe and have the software automatically draw in the surface tabulations (as a mesh or skin).

[@combatshadowz]

Pardon my ignorance, but is this technique of dividing shapes into triangles applicable to everything we see on our screens i.e. images, movie clips (basically 2D content) or it is it only for 3D contents like games and simulation? Simply put, are all pixels on our screens made up of triangles, be it 2D or 3D content?

[@whtiequillBj]

I'd like to hear about boolians and 3D graphics. I've heard it is not really a true merge of verticies but simple a way to make faces invisable and connect the objects

[@Astfresser]

I got a question which i hoped would be covered in this episode: as the objects also lie behind each other, how is it decided which pixels of which objects are drawn on the screen? Does this also happen by the means of linear algebra or is it more like a brute force algorythm?

[@Melthornal]

Very nice. Are you going to be getting into things like antialiasing next?

[@theTOOLshed1]

Awesome video

[@the80386]

MAN I FRIGGIN LOVE THESE VIDEOS! TEXTURING, MAPPING, FILTERING VIDEOS COMING SOON EH? I'LL BE WAITING :D If you make those videos, PLEASE take some time to explain what a texel is. We all know what pixel is but texel is confusing for many. And keep up the great work you guys!

[@BrendonGreenNZL]

pixel = 2D picture element (screen) voxel = 3D volume element (3D equivalent of pixel) texel = 2D texture element (essentially, the "pixels" that make up a texture) Texels are mapped onto the surface of the triangles, and then projected onto the screen as pixels. Voxels are the solid equivalent of pixels, and must be mapped and projected onto the screen just as any other 3D object would be.

[@the80386]

hey thanks buddy. clean and simple :)

[@rangdor]

What books or websites would you recommend for this topic?

[@Ubeogesh]

A question remains after watching this video - how the projectile transformation works?

[@Qbe_Root]

My guess (but I don’t know much about this): get the spherical coordinates of every object relative to the camera, each of the two angles is a 2-D coordinate in a plane with the middle of the screen as its origin.

[@chsxtian]

Nicolas M. Mostly we're using matrix multiplication to make these transformations. www.songho.ca/opengl/gl_projectionmatrix.html here's the explanation of the matrix used to do this in OpenGL

[@skifree0]

Its called rasterisation, en.wikipedia.org/wiki/Rasterisation

[@boenrobot]

Wait, so how does the "projection" transformation work? That seems to be the most important bit in triangles-to-pixel conversion, and yet that part was never explained at all... just mentioned that it exists as part of the process. Maybe do something like the translation and rotation bits about the matrix?... That is, "manually" translate just one triangle to a set of 3 points on a screen. Please?

[@MadManMarkAu]

There's a funky thing that happens with the projection matrix. Technically, he did explain it, but in a very round about fashion. In simple terms, to convert 3D coordinates to 2D space, you divide the X and Y coordinates by the Z coordinate. This gives you an orthographic representation of the vertices on a 2D plane (the screen). Very simple explanation, but that's the absolute basic idea behind it. In the real world, this is done with another matrix calculation. You remember how earlier in the series he explained how matrices worked, with all the rules of multiplying and adding various columns? Well, if memory serves me right, there is also a /divide/ operation that wasn't mentioned at that time. All the view information (viewport size, field of view, etc...) is compiled into a single matrix. This matrix, again from memory, applies perspective to each vertex, crunching them down into a 2D plane, and converts the vertices into screen coordinates (actual pixel coordinates). Then, the polygons are rasterized (drawn).

[@gumenski]

He did cover it but it might have been hard to catch because there wasn't much time wasted about it. He said that a simple projection transformation is literally to just discard all Z coordinates of your triangles entirely and you're done. If you went a sense of depth too then the X/Y coords also need to be scaled down by whatever factor you want based on the Z distance you threw away (x/z, y/z like DarkLord just showed)

[@iabervon]

The trick for getting that divide in a matrix is to go back to the same trick we used for translations, where we've got an extra 1 at the end of the vector, and come up with what it means for a point to have other numbers there. We say that (x, y, z, 1) is the same point as (2x, 2y, 2z, 2) or (10x, 10y, 10z, 10). That is, if you want to reduce a four-number vector to a three-number location, you don't just drop the last number, you divide by it. Then your perspective transform just copies z into the last spot, which turns a point (x, y, z, 1) into (x, y, z, z), which is (x/z, y/z, 1), which is what you want (as others have said). The point of doing this transform is that you can decide whether you want a perspective camera or an orthographic camera (objects don't shrink with distance) by choosing which matrix you use. This is important because your hardware will be set up to do two matrix multiplies and the special divide to every point you give it. So, for every point, you say its local coordinates are and what object it's part of. For each object, you say its world transform. You also say the camera transform. Then the hardware gives you screen coordinates for every point. You don't have to tell it what sequence of operations to do, because that's going to be the same for every scene that every program renders. (In general, computer stuff gets much much slower when you have to tell it what to do, rather than only telling it what numbers to use, which is why hardware 3D is so much faster than software 3D.)

[@Tossphate]

Hello people. Back in the day I used to play Sega Rally on the Saturn. The road would get all distorted where it was close to the "plane" of the screen. I aint a technical guy, but I do know that the Saturn did not have "z-buffering", whatever that is (the playstation did though). Is that polygon distortion something to do with the clipping thing that John is talking about here or something else?

[@OddStare]

The thing i never understood with this concept of "the world is moving not the camera" is if i have a scene with two camera looking at each other, i can see what they both render and i decide to move one of them i can see this camera object moving in the other one so how does it do translation ? You can't translate twice at the same time right ?

[@kwinvdv]

I wonder if 3D games/software will always keep using polygons (triangles). I know that a company in Australia called Euclideon is developing a fast method of doing similar like sparse voxel octree, which uses a 3D point cloud and searches for a point which would represents each pixel. I do wonder if their search algorithm would also perform well in dynamic worlds, since in the examples I have seen the world seemed static.

[@clearmenser]

Can we see similar videos on other Computer Rendering technology like Subsurface Scattering, Ambient Occlusion, Ray Tracing, Subdivision Surfaces... ?

[@hotrodmind]

I always thought that these objects were placed in a finite world space and that the supposed "camera" actually moved around and then displayed those things relative to how far the camera was away from it .. Would this be more computationally awkward than what was explained here ??

[@jasonpitt368]

YES, something I've always wondered about :)

[@AllTheJon]

What's the point of the clipping step? If it's just iterating over all the pixels and asking if each pixel is inside a triangle, what does it matter if part of that triangle is outside the view?

[@SamBrev]

can we have a bit of an explanation on the projection matrix (i assume you use a matrix) and how it works?

[@shell_jump]

I don't think it would be possible to understand without knowing some basic linear algebra. You might understand the formulas, but they wouldn't have any meaning. Then again, wikipedia is your friend - feel free to prove me wrong.

[@SamBrev]

ok well after a bit of searching i found a helpful link, so anyone _else_ who wants to know can try this, although you do need a knowledge of algebra and geometry, and basically maths in general: www.scratchapixel.com/lessons/3d-advanced-lessons/perspective-and-orthographic-projection-matrix/perspective-projection-matrix/

[@shell_jump]

Huh. Guess you proved me wrong :P

[@DrDeeDot]

I hope you cover an efficient method to determine object/face overlapping, i.e., a method to determine if a foreground object cover/hides a background object.

[@MadManMarkAu]

He didn't show how perspective is applied. It's pretty simple, but still a crucial step. It would have been interesting to show how the (as yet unmentioned) [w] component comes into play in a projection transform.

[@AlexN5142]

How does the projective matrix work? How does this differ from raytracing? How exactly do you decide where the origins of each of the coordinate systems are?

[@quietthomas]

0:19 - is he breaking into song there? Reminds me of that Radiolab episode: www.radiolab.org/story/91513-behaves-so-strangely/

[@TheOnlyGeggles]

Didn't understand everything, but still nice to know.

[@JustinKoenigSilica]

awesome!

[@sporkafife]

"We can have a world-view transformation" I'll tell you who needs a worldview transformation, the government! Think they are all that...

[@SoulboundDragon]

Great video! :D

[@DarkSamus918]

I really could have used this two weeks ago when I took a graphics programming final XD

[@Nattakorps]

Thanks for the tip on the free book, I recently lost neuromancer in a fire before I got to read it. this is the next best thing to buying a new copy.

[@maloney670]

Would be great if you explained the projection transformation in terms of the mathematics :) That would be interesting :D

[@symbioticparasite6268]

Came from understanding z fighting to this, great explanation!

[@Azwoh]

John Chapman is easy listening

You have to watch Gilbert Strang's videos from MIT, those are the best on linear algebra!

[@Spiderboydk]

Imagine a modern computer game with hundreds of thousands of triangles in the scene and 2 million pixels on the screen going through all these calculations about 60 times per second. It's mindnumbingly fast.

[@Dayanto]

The beauty of matrices is that you actually don't have to do everything! Matrices allow you to clump together all the different transformations so that you end up with only a couple of multiplications and additions per vertex.

[@Spiderboydk]

***** Yes exactly, but despite of that the number of calculations is still mindnumbing. Take for example the number of times per second the pixel shaders are run on a 1920x1080 60 Hz display.

[@slpk]

Hey Sean! There you are!

[@coltonmoore6358]

Why do so many people not like this video (and the others computerphile videos as well)? Am I missing something that would change my perspective or is it just because I have different taste in videos?

[@LittlePeng9]

So that's how Sean looks like :O

[@Simaisan]

I love these videos !

[@TheGregcawthorne]

When going through all of the polygons and pixels to see if the pixel is in the polygon, that could take a hell of a lot of computation for complex worlds. You'd have to scan all the polygons in your world for every pixel! I guess that's why you have meaty GPUs.

[@justahker3988]

Talk about the Phong reflection model next? (And perhaps get yourself access to an actual 3D software program?)

[@fusobotic]

Awesome video! Btw, if anyone wants to experiment with 3D for free, check out Blender 3D or Google Sketchup.

[@HKragh]

Yeah, and then import the models into Unity to actually build a game. Also free...

[@Aliferopoulos]

I'd love to see an implementation in code :)

[@Andrewsarcus]

You could also create a circle from the three points on the plane.

[@Charlie2531games]

I would have appreciated some of the actual mathematics behind some of this. Perhaps in a future video?

[@MrGryph78]

There's an earlier video in this series on this channel that goes over some of the linear algebra techniques used to perform scale/rotation/translation transformations. Pretty much everything is achieved using some combination of those transformations.

[@capitangoldfish]

world space transformation or global transformation? and isnt the camera just another object in the space with its own coordinates aswell?

[@jdgrahamo]

So simple -- and so complicated.

[@matrinGD]

Why would you need to clip the triangle to the viewport? When colouring the pixels, aren't you going to traverse the viewport and consider those pixels only? Even if some part of the triangle lies outside the viewport, it shouldn't have an effect on how you colour pixels within the viewport.

[@ZipplyZane]

The way I understand it, it's so you don't actually have to analayze every single pixel. By clipping, you can get it down to just the vertices and then just auto fill everything in between them.

[@unidorsalicosahedron7416]

How does the computer decide whether or not a pixel is "within" the triangle? Would it actually do this for every single pixel?

[@d4v01d]

Dör Is there's a few ways of doing that but a common one is for each pixel the computers draw an imaginary line either to the left or right. if this line crosses 2 sides of the triangle the pixel is outside the triangle. if the line only crosses one side of the triangle then it's inside. I think this is called scanline rendering, but not sure about that. And yes, for every pixel and furthermore, every pixel against every triangle (not account for optimisations, culling etc).

[@BastetFurry]

If you want to experiment a bit with this in QBasic or whatever, here is a hint: dx = x/z:dy = y/z (Yep, thats all there is to it ;) )

[@bartekkko]

but what about deciding whether an object is behind another object

[@sicariusaevita2635]

Ha! Nice. We just did these in linear algebra! Cool stuff lol

[@KnightRiderDDR]

"Neo, the camera doesn't move around you. You move around the camera." Or was it with spoons :D

[@malc568]

I've just played Resogun on the ps4 and someone said it used something called voxels instead of pixels. Can you tell me what the difference is please?

[@seigeengine]

Voxels are 3D pixels.. Basically think minecraft. Voxels are like the blocks in minecraft, though many games have them smaller and work to smooth them out. The game still gets rendered into pixels for you to view though.

[@bjzaba]

When people talk about 'voxels', they are normally refer to a way of storing geometric data that can be used instead of storing lots of triangle information. They are basically 3d pixels. This is sometimes useful when you what destructable terrain like in Minecraft. Voxel rendering engines normally add in an additional translation step from voxel data to triangle data: voxel data -> triangle data -> transformation -> pixels There are various ways to do this translation from voxels to triangles - some smooth out the voxels, causing a lumpy appearance, but the simplest approach is to just render the voxels as lots of cubes, like in Minecraft. You still need to render that geometric data to a tv or computer monitor, so the rasterisation process is still used. Voxels *might* be used at the actual rasterisation step in the future, but that would require holographic displays or something :P

[@seigeengine]

The voxels may be rendered into triangles, but I'm pretty sure there are other methods.

[@KuraIthys]

Well, I'm sure you'd like them to explain it at some point, but until they do, here's a summary: (you can't actually replace pixels with voxels by the way, because if you create a 3d scene out of voxels it still gets turned into pixels on the screen at some point). - A voxel is basically an alternative to making things out of polygons. Where polygons are triangles, a voxel is basically the 3d version of a pixel. A pixel is a most often a square or rectangle, usually in a regular 2d grid. A voxel by comparison is usually a cube or box shape, in a regular 3d grid. (Although, in practice, because of how computer hardware has been designed, when something is made of voxels, to show it on a screen often involves turning it into polygons first, then using the stuff that's been explained here to draw the final image) - If you're having a hard time getting your head around the idea of voxels, go take a look at minecraft; - The terrain in that game, which consists almost entirely of cubes, are effectively very large voxels. (Although they have textures on them, which a proper voxel would not, the overall logic behind how they work, and how they are represented inside the computer is pretty much what voxels are about.)

[@abexuro]

I don't know the game, but if that's at all true, he meant voxels instead of polygons. Edit: explanation wrong :P

[@GeorgeStanmore]

Don't collapse Z because depth test

[@ValsGym]

This guy is fucking with my mind.

[@DeoMachina]

Seconding Neuromancer SO HARD. Reading it in the 21st century is kind of a trip, when you realise it was written in the 80's.

[@alexwang007]

so uh, anti-aliasing math? is it like image interpolation?