Triangles to Pixels - Computerphile
Vložit
- čas přidán 17. 12. 2013
- 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
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
Does anyone else really like this guys voice?
***** everyone thinks their voice is horrible
/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!"
I never knew Sean Connery's son was so good with graphics math.
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?
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. =)
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
Huzzah, love these videos!
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!
Personally, i'm looking for video of shaders too.. I'm precisely at that point of learning curve myself...
i really wish an episode about shaders
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).
This is by far my favourite series of videos on all your chanels. Thanks !
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.
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.
;)
Thanks!
these videos are just getting better and better
It's rare to see genius but even more so on You Tube.
Really enjoying this series. Thanks for putting it together, guys.
I really hope they mention the depth buffer. That was probably my biggest 'aha!' experience I've had with computer graphics.
He looks a bit like a movie supervillain when he talks. Especially around 4:03 , I'd guess he'd make a convincing Joker!
I've always wanted to know this! Great video :)
Freaking awesome! Keep it up, I absolutely love this series!
hey look, an actual use for all that math i learned in high school.
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.).
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!
any example of calculation? or any site you know whith an example, thanks
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/
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.
This series of videos on triangles, matrices, and graphics etc was really awesome :)
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.
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.
***** 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.
Such an intuitive explanation of quite an involved topic. Thank you.
A question remains after watching this video - how the projectile transformation works?
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.
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
Its called rasterisation,
en.wikipedia.org/wiki/Rasterisation
Thanks for this explanation. Always struggled to understand this. Nice to see it from a high level!
This is great! Hopefully the next video will be VERY in-depth about shaders. I would like him to talk about programmable shaders too :)
Wow. I'm really liking this video series!
awesome, cant wait for the next vid
Bro, this channel is awesome
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.
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.
can we have a bit of an explanation on the projection matrix (i assume you use a matrix) and how it works?
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/
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.
Fourier Transform please!
great video as always, guys! Wow, takes me back a few years. (and next we'll talk about backface culling :P:)
So that's who Sean is (never seen him on any videos before). Thanks for making these videos! :-)
Awesome video
i had to learn this from a book, this graphical explanation makes it so easy :p
More videos with this guy please!
I must admit I'm curious about the projective transformation. And would love to see more about how it works
"We can have a world-view transformation"
I'll tell you who needs a worldview transformation, the government! Think they are all that...
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!
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.
hey thanks buddy. clean and simple :)
Great video! :D
These videos are great. Please do one on how to interpolate pixels over the triangle (barycentric interpolation).
you guys should add links between series of videos - it looks as if there's one before this one - is there ?
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?
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).
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)
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.)
Hey Sean! There you are!
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.
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).
Didn't understand everything, but still nice to know.
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.
Very nice. Are you going to be getting into things like antialiasing next?
So that's how Sean looks like :O
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..
awesome!
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.
I love these videos !
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.
YES, something I've always wondered about :)
I really could have used this two weeks ago when I took a graphics programming final XD
John Chapman is easy listening
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.
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?
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?
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.
Came from understanding z fighting to this, great explanation!
I would have appreciated some of the actual mathematics behind some of this. Perhaps in a future video?
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.
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?
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
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?
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.
If pixels on a screen were shaped like triangles instead of squares or dots would the process of projecting the 3D objects into pixels be easier?
Also at 2:50 I'm reminded of one time in Futurama where Professor Farnsworth explains that the ship never moves,but rather, the entire universe is moved by the engine and that the idea that the ship is moving through space is an illusion...
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 ?
Talk about the Phong reflection model next? (And perhaps get yourself access to an actual 3D software program?)
"Neo, the camera doesn't move around you. You move around the camera." Or was it with spoons :D
Would be great if you explained the projection transformation in terms of the mathematics :) That would be interesting :D
What books or websites would you recommend for this topic?
Tom Waits+Jeff Goldblum= this guy!
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?
I've been getting my feet wet in OpenGL recently, so this hits quite close to home.
Can we see similar videos on other Computer Rendering technology like Subsurface Scattering, Ambient Occlusion, Ray Tracing, Subdivision Surfaces... ?
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?
Don't collapse Z because depth test
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 ??
You could also create a circle from the three points on the plane.
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?
0:19 - is he breaking into song there?
Reminds me of that Radiolab episode: www.radiolab.org/story/91513-behaves-so-strangely/
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.
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 ;) )
You have to watch Gilbert Strang's videos from MIT, those are the best on linear algebra!
How does the computer decide whether or not a pixel is "within" the triangle? Would it actually do this for every single pixel?
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).
Awesome video! Btw, if anyone wants to experiment with 3D for free, check out Blender 3D or Google Sketchup.
Yeah, and then import the models into Unity to actually build a game. Also free...
Your next video should expand on this by talking about antialiasing!
I'd love to see an implementation in code :)
So simple -- and so complicated.
This guy is fucking with my mind.
this guy could play a diabolical villan in a movie
Wtf? He only colored in half of one of the pixels. XD.
Anti-aliasing.
So, I guess he'll get to that next video? Lol.
I knew that, it is quite impossible to phsically divide a pixel in half without discolouration. I guess it sort of acts as half a pixel allowing for clearer edges.
PoweredMinecart McUnite That's not how anti-aliasing works... you physically can't have half a pixel.
six2013 It's pretty close. Antialiasing, at least in concept, analyzes the portion of the pixel that is shaded and then chooses a color for said pixel that represents that portion. It portrays spacial information in the realm of color, since color is all a particular pixel has.