[소프트 3D 엔진] Software Ren.. School, Part III: Triangle Rasterion

Software Rendering School, Part III: Triangle Rasterization		???????
Mihail Ivanchev, Hans Th?rnquist, and Anubis 26/03/2004

Legality Info The tutorials in this series as well as the source that comes with them are intellectual property of their producers (see the Authors section above to find out who they are). You may not claim that they are your property, nor copy, redistribute, sell, or anything of the nature, the tutorials without permission from the authors. All other articles, documents, materials, etc. are property of their respective owners. Please read the legality info shipping with them before attempting to do anything with them! Triangle Rasterization In this article we will discuss one of the most important basics of the computer 3D graphics ? triangle (polygon) rasterization. Perhaps there is no need to explain why this is important, but for those of you who aren't quite certain yet, we’ll explain. All 3D objects that we see on the computer screen are actually made of tiny little geometrical objects often called primitives. Quadrilaterals, triangles, n-gons etc. are example of primitives. We will concentrate on triangles mostly because of one main reason: every object can be split into triangles but a triangle cannot be split into anything else than triangles. Because of this, drawing triangles is a lot simpler than drawing polygons of higher order; less things to deal with. This is why those triangles are so commonly used in computer graphics. By knowing how to properly draw triangles, one has the ultimate power to deal with all kinds of cool 3D stuff. Of course, if everything you want to do is to draw a few dumb-lookin’ billboards or sprites you can skip reading about rasterization. But you should continue reading if you’re interested in doing solid 3D objects. Now, let’s see what we need to know in order to start drawing triangles in a 3D world. Every child after 1st grade will tell you that a triangle has 3 sides and therefore is composed of 3 points. In our case this will be vertices, which aside from other information like color or texture indices will also contain the coordinates of the triangle points. So, how do we convert a triangle defined in 3D space to 2D (screen) space? Well, very easy! A triangle in 3D is also a triangle in 2D space, so the only thing we have to do is to project the triangle’s points from 3D to 2D space and rasterize it. Right, that's all neat and simple, but how do we rasterize the beast on the computer screen?! Now that's a hard one! The triangle rasterization is fighting about being the slowest and most sophisticated process in a 3D engine. Imagine a 3D scene with hundreds or thousands of triangles and all these have to be rendered with all the maths to them. Also remember, the triangle rasterization described in this paper is only the top of the iceberg. Back on topic. After you’ve projected the points of your triangle, it is time to rasterize it. Rasterizing means that you draw it on the computer screen, which is a raster grid (discrete pixels). The best method known to the human kind for polygon rasterization so far is the method of the horizontal spans. A span is simply a synonym word for a horizontal line in our case. Let’s have a look at this image: As you can see a triangle can be viewed as a collection of a horizontal lines starting from the top of the triangle, going down to the bottom. When rasterizing a polygon, we find some information about the spans that build it (start/end points etc.) and then we simply draw the spans on the screen (we believe drawing horizontal lines won’t be much of a problem…). The process of converting a polygon to a set of horizontal lines is called "scan-conversion" and we'll describe this in detail with all the math involved. Most tutorials online just show some C source for the reader to wade through :) (We learnt from those resources though). As mentioned above, in order to define a horizontal line, we must define a start and end point for it. This is pretty simple business in theory, we just have to trace lines to the left and to the right and draw spans in between. To find them, we will have to linearly interpolate the triangle-edges (or sides). This isn't the best place to explain linear interpolation but you can think of it like this: Linear function: f(x) = ax + b a = const b = const You also know that: f(x+1) ? f(x) = const So, in the case of linear interpolation, we can see that f(x) is changing with a constant value each time we increment or decrement x. This will be quite useful for us. Let’s see how: It’s clear that the line above is defined by two points A and B. We also have a point C, for which we only know the y coordinate (we simply loop from the top point to the bottom point of the line). We will have to interpolate between B and A in order to find the x coordinate that we want. First we find with what amount the x coordinate will progress if we increment y on the line that we’ve defined by A and B: slope = (Bx ? Ax) / (By ? Ay) Now to find Cx for any y coordinate, do this: Cx = Ax + slope * (Cy ? Ay) One way to interpret "slope", is to think like "we go x per y", which is basically what the division-operator calculates. So, for every new scan-line we go to (for every new y), we add the value of "slope" to x. This means "add x per y to coordinate". Given the picture, we see that if we interpolate x coordinates from V1 to V3 for every y we will get the start points of our spans. In the same way, by interpolating x from V1 to V2 and from V2 to V3 for every y, we get the end points for our spans. If you have ever come across drawing lines on the computer, you have surely seen interpolation before. This time though, there is no need to account for slopes < -1 or slopes > 1, because gaps will be filled up by the spans we will draw later on. So what we got for the sides of the triangles is three very simple line routines. After you’ve scan-converted all of the triangle’s (polygon’s) edges all you have to do is to draw the spans with the color specified for the primitive. And that's it, neat and purdy. We know that it is pretty complicated and messy right now, but it will all become clear with time (at least it became for us ;) ). Anyway check out the sample source code to see how to implement the rasterizing process. It is well commented so we guess it will be easy to grasp. If not, send us an E-Mail and we promise reply. Now that we know how to render triangles, we can start with the fun stuff :). Next time you will learn how to gain speed using fixed-point math, how and why to do depth sorting and how to do some basic kinds of shading. Maybe something more, maybe something less ;).

Download source code for this article

원본 사이트 : http://www.devmaster.net/articles/software-rendering/part3.php