Triangle Polygon Algorithm

Be more precise. Do you want a triangulator ?

I''ll explain best if I can
I want to know details about the implementation of the algorithm that uses 3dcards(ogl/d3d) to draw a triangle polygon (flat,smooth or textures) in the screen.
A low level algorithm that can be used in a lineal framebuffer mode like mode13 or directdraw. I want the algorithm that uses ogl,d3d... because I think its the faster, maybe I am wrong.

I *believe* both ogl and d3d have scanline rendering using bresenham''s algorithm to reduce floating point math. I''m sure you''ll find plenty if you put "bresenham''s algorithm" into google. If you''re really interested, look up a sample implementation of OGL and see what it looks like. http://oss.sgi.com/projects/ogl-sample/

not that a know anything about this, but what has this to do with a graphics api? i very strongly assume this is done one the gpu, hardwarematic, or am i mad?
i think if it would be done softwarematic that would produce quite lame fillrates.

anyway you should indeed be able to find some poly filing algos and their implementations on google, i wouldnt know witch is best though..

You start in world space and pass three vertices to your renderer.


- Transformation - Transform each point by multiplying it with the transformation matrix. You are now in transformed world space.

- Projection - Project the transformed points by multiplying them with the projection matrix. You are now in clipping space (aka the canonical view volume).

- Lighting - You can do this several ways, just know that here is where lighting happens.

- Clipping - Clip the triangle by testing for intersections with the view volume and generating new points as necessary.

- Rasterization -
- - - Rasterize lines beween your points - If useing smooth/Gouraud shading, then interpolate fragment values (i.e. depth, color, alpha, texcoords, etc.). Test pixels if you need to (namely depth testing).
- - - Fill polygon - Running from left to right and top to bottom, take the first pixel you encounter and interpolate it with the next one you run into. Don''t forget to test your pixels. Continue until end of frame buffer.

- Fragment Processing -
Fill in your textures and whatever else you need to do.


Now do it bunch more times.

very helpfull your posts,
Eelco, yes, this is done by hardware, but I am making a software renderer and I am seeking a really fast method to dray polys, because mine is very slow, I believe that the ogl/d3d one was very fast, but maybe it don''t need to be a fast software method, because its implemented in hardware and don''t need so much optimization like you tell.

I posted a description of how to fill a polygon (via software) under the following topic:

Scan Line Polygon Fill Algorithm

To do flat shading, this algorithm works fine as is.

If you want to add Gourad shading you will need to know the normals of each vertex in the triangle/polygon. When you''re drawing your poly (via scanline) you interpolate the normal across the face and use this to adjust the pixels value you are writing.

This same technique (interpolating vertex normals) can be used for Phong lighting, and environment mapping.

Probably the best thing for you to do is to implement the scanline renderer I described, and then write a version that allows texture mapping. Once you have done this, you should be able to understand how to interpolate the normals across each scan line.

Good luck,
Will

i got a triangulator, it uses floating point outside the rendering loop and it is assembly optimized, i use this triangle rasterizer for my software hom buffer, so there is only information about depth , no texture coords , and shading interpolants, so if you think it might be still usefull for you, just email me

Take a look at swShader''s Renderer/Rasterizer.cpp code. It features sub-pixel/sub-texel accuracy, mipmap LOD calculation and much more.