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: enter image description here

But if you zoom in, you can see the errors: enter image description here

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:

enter image description here

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.

You can do this by taking a scan line algorithm as a starting point. There's code an tutorial at: http://www.cs.utah.edu/~xchen/columbia/session2/lec13/html/index.html — Flexo, Jul 27 '12 at 13:35
@Flexo, will that result into same quality as OpenGL ? So i could use floats to define the points? — Rookie, Jul 27 '12 at 13:37
Sure, that's basically what your graphics card does at its most basic level. You can add stuff like shading (e.g. Phong shading) if you want. — Flexo, Jul 27 '12 at 13:39
If you want the most benefit from having fractional accuracy you should use it in some way during the scanline rasterization. E.g. by only rendering those pixels where the center of the pixel is covered by the polygon, or for doing some form of antialiasing on the edges. — Michael, Jul 27 '12 at 13:44
@Michael, So the code Flexo gave, doesn't work like OpenGL? I dont want to use antialiasing... that will be another problem, i just need plain pixel accuracy, but it should be like OpenGL. Check my edits, i added image how it should look. — Rookie, Jul 27 '12 at 13:48
It has been answered [here](http://stackoverflow.com/a/7870925/968261) and [here](http://stackoverflow.com/a/11145708/968261). — Alexey Frunze, Jul 27 '12 at 15:12
@AlexeyFrunze, It seems like your algorithm has the chance to draw same pixel twice? OR not? See my edits, i want to avoid the same pixel drawing because i use XOR for the pixels. Do you have any ideas how to fix that in my current algo? — Rookie, Jul 27 '12 at 15:35
How it is possible that the pixels have a color that you have not outputted in any way (and knowing that there is no blending or multisampling involved)? I mean, perhaps there is something wrong with your implementation. — Gigi, Jul 27 '12 at 16:55
@Gigi, ? the bugged pixel colors in that image is a result of two pixels overlapping, and when i use XOR, the colors will change in weird way like that. The overlapping isnt the only problem though; some pixels are not drawn at all inside that circle. I didnt change anything else (from that code i linked), than took away the gradient and replaced it with simple 1 color rendering with XOR. — Rookie, Jul 27 '12 at 17:00
You probably do not want to _XOR_ overlapping triangle colors, right? So you must detect overlapping regions and either: avoid the XOR there or you must calculate for each pixel the amount of coverage per-triangle and only rasterize the triangle that cover more space. Hope that this make sense! — Gigi, Jul 27 '12 at 17:15
Also, for your small circles aliasing problem... The fact is that your target _image_ has finite resolution. That is, it is quantized. To avoid the aliasing, you must rely on anti-aliasing solutions. — Gigi, Jul 27 '12 at 17:18
@Gigi, the purpose of XOR is that it will XOR anything previously drawn triangles (or any other pixel data in the image buffer), so i cant just check if they overlap (and actually the check would always return false because they DONT overlap in mathematical sense). About the bugged circles, check my edits and see how OpenGL does it with the same "finite resolution". I cant avoid XOR because thats the essential part of the whole program. — Rookie, Jul 27 '12 at 17:23
They do not overlap in the mathematical sense, but they can rasterize to the same pixel. How OpenGL does alias-free "small circles" rendering (without anti-aliasing)? It does not. — Gigi, Jul 27 '12 at 17:26
@Gigi, im not sure what you mean by anti-aliasing. but in opengl the "rasterized" pixels cannot overlap or else the blending would break completely. — Rookie, Jul 27 '12 at 19:05
@AlexeyFrunze, which pixel are you talking about? the circle with 64 triangles middle pixel, or that image which shows the 2 wrong pixels? — Rookie, Jul 28 '12 at 07:50
@AlexeyFrunze, http://img688.imageshack.us/img688/864/tritest22.png seems to belong to the orange triangle at right middle. why does this matter? — Rookie, Jul 28 '12 at 10:15
How do you think the "algorithm" should handle the central pixel, which mathematically belongs to multiple triangles, to satisfy your requirements (no unfilled pixels, no pixel painted multiple times)? — Alexey Frunze, Jul 28 '12 at 12:40
@AlexeyFrunze, even by the current (buggy) algorithm, it doesnt belong to multiple triangles. i managed to get it render the middle pixel twice only in few rare cases. i dont know how opengl does it (thats what im asking for in this question BTW), but im sure it doesnt render them twice, or, as i said: blending wouldnt work correctly since two triangles would overlap on each other and for example 50% transparent color would become a lot stronger and you would see really ugly rendering on complex polygons. Anyways, thats not the only problem, i want to use float coords too, not just ints. — Rookie, Jul 28 '12 at 13:08
I think you need to address the two main issues separately (in different questions, that is). Further, I think that you need to improve the question and requirements. As it is currently stated, it appears (at least to me) that there's no simple and good general-purpose algorithm to meet all of your requirements for all kinds of composite polygons. Of course, devising one for a special case described in the question (circle made up of equal triangles) shouldn't be hard, but you want all. I also think that the desired XOR behavior overly complicates rendering. Is it really needed? Really? — Alexey Frunze, Jul 28 '12 at 17:39
@AlexeyFrunze, feel free to answer to this question if you have a solution. — Rookie, Jul 28 '12 at 20:09
I know I'm late to the party but implement this: http://www.sunshine2k.de/coding/java/TriangleRasterization/TriangleRasterization.html with integers instead of floats and you'll be golden for pixel perfect triangles. — Emily L., Jan 08 '17 at 19:52

genpfault · Accepted Answer · 2021-10-20T15:41:08.543

4

There's always the half-space method.

edited Oct 20 '21 at 15:41

answered Jul 27 '12 at 19:02

genpfault

51,148
11
85
139

1

That looks like interesting approach. However, I cant get the code to work... It renders total gibberish. Also, I'm not sure what the `stride` variable should be set, currently I use it as "Bytes Per Pixel", any idea? – Rookie Jul 27 '12 at 19:57
`stride` is generally how many pixels wide your destination bitmap is. The `colorBuffer += stride` essentially moves down one row in the bitmap. – genpfault Jul 27 '12 at 20:37
I thought of that, but when i set `stride = width` it just crashes... maybe i can fix it if i access the buffer without pointer trickery like that, lets see... – Rookie Jul 27 '12 at 20:41

score 1 · Answer 2 · answered Jul 27 '12 at 13:36

1

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.

answered Jul 27 '12 at 13:36

brano

2,822
19
15

that's an old answer, but currently the most common way of rendering triangles on the GPU is the half-space method with all the pixels (or maybe equal square areas) concurrently. – somerandomdev49 Jul 19 '22 at 09:22

score 1 · Answer 3 · answered Jul 27 '12 at 13:59

1

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.

answered Jul 27 '12 at 13:59

SpacedMonkey

2,725
1
16
17

This looks promising, at my first test there werent pixel on every line; looks like correct algo! going to test with precise circle soon. – Rookie Jul 27 '12 at 14:35
See my edits, it didnt work perfectly, unfortunately! Do you have any idea how to fix it? – Rookie Jul 27 '12 at 15:20
It's been a long time since I've done this sort of thing but if I remember correctly, you can get different results depending on the direction you draw the lines. For the circles you should take advantage of symmetry, at least 8 fold, and only calculate the outline in the zeroth octant (from y=0 to y=x). – SpacedMonkey Jul 30 '12 at 09:28
Circle is just an example, i will need it to work for any polygon shape. – Rookie Jul 30 '12 at 09:42

score 1 · Answer 4 · answered Feb 11 '17 at 05:55

Your problem looks a lot like the problem one has when it comes to triangles sharing the very same edge. What is done by triangles sharing an edge is that one triangle is allowed to conquer the space while the other has to leave it blank.

When doing work with a graphic card usually one gets this behavior by applying a drawing order from left to right while also enabling a z-buffer test or testing if the pixel has ever been drawn. So if a pixel with the very same z-value is already set, changing the pixel is not allowed.

In your example with the circles the line of both neighboring circle segments are not exact. You have to check if the edges are calculated differently and why.

Whenever you draw two different shapes and you see something like that you can either fix your model (so they share all the edge vertexes), go for a z-buffer test or a color test.

You can also minimize the effect by drawing edges using a sub-buffer that has a higher resolution and down-sample it. Since this does not effect the whole area it is more cost effective in terms of space and time when compared to down-sampling the whole scene.

Perfect filled triangle rendering algorithm?

4 Answers4