Perfect filled triangle rendering algorithm?

Question

Where can I get an algorithm to render filled triangles? Edit3: I cant use OpenGL for rendering it. I need the per-pixel algorithm for this.

My goal is to render a regular polygon from triangles, so if I use this triangle filling algorithm, the edges from each triangle wouldn't overlap (or make gaps between them), because then it would result into rendering errors if I use for example XOR to render the pixels.

Therefore, the render quality should match to OpenGL rendering, so I should be able to define - for example - a circle with N-vertices, and it would render like a circle with any size correctly; so it doesn't use only integer coordinates to render it like some triangle filling algorithms do.

I would need the ability to control the triangle filling myself: I could add my own logic on how each of the individual pixels would be rendered. So I need the bare code behind the rendering, to have full control on it. It should be efficient enough to draw tens of thousands of triangles without waiting more than a second perhaps. (I'm not sure how fast it can be at best, but I hope it wont take more than 10 seconds).

Preferred language would be C++, but I can convert other languages to my needs.

If there are no free algorithms for this, where can I learn to build one myself, and how hard would that actually be? (me=math noob).

I added OpenGL tag since this is somehow related to it.

Edit2: I tried the algo in here: http://joshbeam.com/articles/triangle_rasterization/ But it seems to be slightly broken, here is a circle with 64 triangles rendered with it:

But if you zoom in, you can see the errors:

Explanation: There is 2 pixels overlapping to the other triangle colors, which should not happen! (or transparency or XOR etc effects will produce bad rendering).

It seems like the errors are more visible on smaller circles. This is not acceptable if I want to have a XOR effect for the pixels.

What can I do to fix these, so it will fill it perfectly without overlapped pixels or gaps?

Edit4: I noticed that rendering very small circles isn't very good. I realised this was because the coordinates were indeed converted to integers. How can I treat the coordinates as floats and make it render the circle precisely and perfectly just like in OpenGL ? Here is example how bad the small circles look like:

Notice how perfect the OpenGL render is! THAT is what I want to achieve, without using OpenGL. NOTE: I dont just want to render perfect circle, but any polygon shape.

Answer 1

There's always the half-space method.

Answer 2

OpenGL uses the GPU to perform this job. This is accelerated in hardware and is called rasterization. As far as i know the hardware implementation is based on the scan-line algorithm.

Answer 3

This used to be done by creating the outline and then filling in the horizontal lines. See this link for more details - http://joshbeam.com/articles/triangle_rasterization/

Edit: I don't think this will produce the lone pixels you are after, there should be a pixel on every line.