Jump to content
  • Advertisement
Sign in to follow this  
stonerose2

Math behind rasterization?

This topic is 5114 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Rasterization seems to be a poorly documented concept, I realize that is better left to hardware, but this is a learning exercise :P. Does anyone have any good resources on the math behind rasterization? Ive got my program setup and read/writing directly from the framebuffer, and bresenhams algoritihm is ready to go, Im just how sure how exactly to translate a 3d object to its 2d representation so I can draw it in the pixmap using bresenham.

Share this post


Link to post
Share on other sites
Advertisement
You usually do this in two steps: first, you transform your objects into screen space. Screen space is basically y pointing up, x pointing right, with the middle being (0,0,0) and the entire screen being the rect (-1,-1) to (1,1).

This transform is up to the user of the renderer: he should select the transforms (view+projection).

Once you have the objects in screen space, you will need to apply an affine transform to move (0,0) to the top left-hand corner, with y pointing down and x pointing right, and the entire screen being the rect (0,0) to (your resolution).

Once this is done, you will have the pixel coordinates of your objects (such as, the corners of your triangles), which you can then rasterize.

Share this post


Link to post
Share on other sites
Quote:
Does anyone have any good resources on the math behind rasterization?

I recommend LaMothe's "Tricks of the 3D Game Programming Gurus" (2003). It goes through nearly everything you need to write a full 3D software rasterizer -- in fact, the book takes you step by step making one. The only thing I would say is left out is collision detection, but one may classify this more as physics instead of graphics. The engine it teaches you to write is completely free in D3D of OpenGL.

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
You usually do this in two steps: first, you transform your objects into screen space. Screen space is basically y pointing up, x pointing right, with the middle being (0,0,0) and the entire screen being the rect (-1,-1) to (1,1).

This transform is up to the user of the renderer: he should select the transforms (view+projection).

Once you have the objects in screen space, you will need to apply an affine transform to move (0,0) to the top left-hand corner, with y pointing down and x pointing right, and the entire screen being the rect (0,0) to (your resolution).

Once this is done, you will have the pixel coordinates of your objects (such as, the corners of your triangles), which you can then rasterize.



Hmm, this seems as thought it would only work for 2d objects? Lets say Ive got a wireframe cube that I wish to display on the 2d screen space, that has a line going from (1,0,-2) - (2,2,2). This wont translate directly to the 2d screen space as its simply not a (1,0) - (2,2) line, the z coordinates put a slant on it, accordingly so there must be a line in 2d space that can be drawn to represent this 3d line, Im lost on translating things like this from 2d -> 3d.

Share this post


Link to post
Share on other sites
You'd want to read up on linear algebra, specificly vectors and matrices. A point in 3d is usually represented as a 3 component vector, which at world->screen-space transformation is multiplicated by a projection matrix which projects the point on a 2d plane.

Share this post


Link to post
Share on other sites
Actually, rasterization is rather DAMNED WELL documented! But, there are multiple pieces to the puzzle and it can be hard to find all the details for the whole pipeline in one place. It can be a puzzle to put it all together.

ToohrVyk's post is a succinct summary of how to get triangles into a 2D screen/pixel coordinate projection. I'll point you to some resources on the final step, which is the actual rasterization---generation of pixels. For the purposes of web searches, use the phrase "scan conversion" in place of "rasterization." You'll find many, many web pages that document the procedure!

Polygon Scan Conversion Algorithm

Scan Conversion - This one is really good, though the images are a bit low resolution

Polygon Scan Conversion and Shading - Another really good presentation

Hope this helps!

Share this post


Link to post
Share on other sites
I didn't look as closely for docs on the 3D to 2D/screen projection steps. Again, there are many, many, many, MANY resources out there. Here is one of them:

World to Screen Projection Transformation

Here is another one, HIGHLY recommended since it shows a flow char that feeds into scan conversion, e.g., the other references I gave. In fact, this is a fantastic companion to the last link in my other email. They are both from the University of Virginia Computer Science Department. Use them together.

3D Polygon Rendering Pipeline

Again, hope it helps!

Share this post


Link to post
Share on other sites
Here is a trick you might understand once you know all what's needed about rasterization : "x(y) Bresenhams", subpixel accuracy issues, linear mapping, perspective correct mapping, etc... Something (quite simple) I found by myself, and of great interest for small triangles.

carry = xf>>31UL; // Get carry bit;
xf &= 0x7FFFFFFFUL;
pStart += dpStart[carry];
pEnd += dpEnd[carry];
s += ds[carry];
t += dt[carry];
xf+=dxf;
etc ...


This avoids many computations (multiplications) for linearilly interpolated values when you jump from one scan line to the next. Ten years ago the great advantage was to stay in fixed point as much as possible and integer mul was BS. This way perspective correctness, that is the high latency division could be very well scheduled with integer code.

EDIT : You should see how this carry trick is related to left and right "Bresenhams". Many coders used to write scan-line jumps very poorly, this resulted in atrocious mapping artefacts, specially in movement. I often had to explain why it was BS, but some never understood. You don't interpolate linearilly on the (infinitesimal) edges ! The exact way to do is step from pixel center to pixel center, that is discrete (integer) steps, and there are two such kind of steps on a Bresenham. Take a look at one. Then you see where this idea of exploiting a carry bit comes from.



[Edited by - Charles B on October 23, 2004 8:19:13 AM]

Share this post


Link to post
Share on other sites
It's all about linear interpolation. You first vertically interpolate values going from top to bottom of the triangle, then horizontally interpolate across them. What are you interpolating? It could be anything... rgb values, texture coords, z-values, bump-map coords, environment-map coords, normals, etc. Obviously, the more interpolants you have, the slower it will run.
So basically, learn linear interpolation first and then learn how to draw a triangle, then you will know rasterisation :)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!