{"name":"608294","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/f\/1\/f19249459fdda3ab6ef0eb92cadd3376.png","w":288,"h":385,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/f\/1\/f19249459fdda3ab6ef0eb92cadd3376"}
Ok, I've tried to implement this 2d visibility / field of view algorithm here:
http://www.redblobgames.com/articles/visibility/
It basically involves "sweeping" through given endpoints / vertices of line segments in the order of the angle to the center point / the "viewer", producing triangles along the way if the encountered segments are closest to the "viewer".
It's a very nice algorithm, however, for me, it produces "glitches" between triangles in certain positions (see the visible line in the image). Of course they can only be seen because the triangles are drawn with alpha < 1.0. Unfortunately, this is a requirement.
I first thought the endpoints were not in the correct order or there was a problem with the angles, however, when I output the coordinates of the triangle fan, I can see that it seems to be alright.
The vertices are drawn with al_draw_prim as a triangle fan.
The line appears at the angle of almost 135°, vertex 30 and 31 are on that angle (bold in spoiler).
It's just a coincidence that it's 135° though, it also happens at other angles.
cx: 499, cy: 238 vertex 1: 453.000000, 240.999939, angle: 176.268677 vertex 2: 453.000000, 205.000076, angle: -144.344742 vertex 3: 433.484680, 191.000000, angle: -144.344742 vertex 4: 476.439484, 191.000000, angle: -115.641518 vertex 5: 486.999725, 213.000000, angle: -115.641518 vertex 6: 562.000061, 213.000000, angle: -21.644417 vertex 7: 576.000000, 207.444458, angle: -21.644426 vertex 8: 576.000000, 282.999451, angle: 30.302376 vertex 9: 576.000000, 282.999451, angle: 30.302376 vertex 10: 576.000000, 510.149841, angle: 74.202072 vertex 11: 557.001160, 443.000000, angle: 74.202072 vertex 12: 548.804688, 443.000000, angle: 76.344574 vertex 13: 542.002075, 415.000000, angle: 76.344582 vertex 14: 510.997437, 415.000000, angle: 86.122299 vertex 15: 511.000000, 415.037903, angle: 86.122307 vertex 16: 511.000000, 434.045959, angle: 86.497284 vertex 17: 511.548096, 443.000000, angle: 86.497284 vertex 18: 484.997650, 443.000000, angle: 93.907471 vertex 19: 476.732849, 564.000000, angle: 93.907471 vertex 20: 402.936768, 564.000000, angle: 106.418793 vertex 21: 438.000000, 445.009460, angle: 106.418800 vertex 22: 438.000000, 437.261169, angle: 107.020966 vertex 23: 469.000000, 335.997284, angle: 107.020973 vertex 24: 469.000000, 320.003021, angle: 110.094551 vertex 25: 469.001099, 320.000000, angle: 110.094551 vertex 26: 449.000427, 320.000000, angle: 121.372787 vertex 27: 442.000000, 331.480804, angle: 121.372787 vertex 28: 442.000000, 321.000305, angle: 124.479118 vertex 29: 442.000214, 321.000000, angle: 124.479118 vertex 30: 416.001801, 321.000000, angle: 134.999374 vertex 31: 299.000000, 438.004333, angle: 134.999374 vertex 32: 299.000000, 286.597717, angle: 166.342468 vertex 33: 392.000000, 263.999786, angle: 166.342468 vertex 34: 392.000000, 244.978119, angle: 176.268677
There is something wrong with primitives coordinates I guess.
What am I missing here?
How do you calculate the angle? It doesn't seem to me that 30 and 31 are the same gradient if you output a few more places behind the comma...
I'm atan2-ing it from the coordinates to check. Yes, it's exactly the same.
134.99937438964843750000...
But the angle is what the "input" is to generating the triangles anyway, so it should be the same.
My implementation is essentially a copy/port of the Haxe2 implementation the guy gave here: http://www.redblobgames.com/articles/visibility/Visibility.hx
The interesting stuff happens in the sweep function at lines 260-308.
The vertices are generated by intersecting the current angles with the line segments.
I'll post the "output" function here:
cx: 499, cy: 238
vertex 30: 416.001801, 321.000000, angle: 134.999374
vertex 31: 299.000000, 438.004333, angle: 134.999374
They don't are the same, which I suspect is the problem.
I think I don't understand what you mean.
The coordinates aren't the same, but they shouldn't be.
#30 is the little yellow cross where the glitch-line ends, #31 is farther along this line on the segment to the left.
Both are needed to draw this thing properly, no?
Or do you mean I am maybe too stupid to understand how the vertices for a proper triangle fan have to look like? 
No, I mean, some rounding error may have caused it... so maybe you can use double instead of float or something like that.
I've tried to replace every "float" with "double". To no avail: The glitch-line visible above disappears then, but there are others appearing instead. 
I've just realized my last post could come across as aggressive. Sorry, it wasn't meant like that at all. I'm merely totally clueless about what is causing this.
So how to solve this? I guess it's just not possible to draw this with a simple triangle fan then, because there will be glitches with vertices on the same gradient? What do you think?
Two triangles touching at an edge are guaranteed not to overdraw only if they share the two vertices of that edge. I think what's happening in your case is that you are violating that rule and creating something called a t-junction, where you have an overlapping edge, but one or two vertices that are not shared. There's a little discussion on this here (for an unrelated tool, but the idea is the same): http://wiki.ldraw.org/index.php?title=Avoiding_T-Junctions_in_LDraw_parts . The solution is to subdivide your triangles. I believe your field of view is a simple polygon, so you can use the al_triangulate_polygon to triangulate that field and then use al_draw_indexed_prim with ALLEGRO_PRIM_TRIANGLES_LIST to draw it.
Thank you for your words of wisdom.
Edit: Is triangulating it expensive performance-wise?
Edit2: I think more vertices aren't necessary. I just need a clever way to draw it with the given vertices. Somehow recursively deferring the triangles which result from the 2nd, 3rd, ... vertex on the same gradient.
If I understand correctly you're drawing it semi-transparently and it overlaps with itself creating lines? If that is the case you could draw it opaquely to another bitmap, then draw that bitmap to the screen with semi-transparency.
Yes, that's a possible solution. Which I'm trying to avoid nonetheless because I don't want a separate buffer to be involved when not strictly necessary.
Is triangulating it expensive performance-wise?
I don't think it's too bad.
I think more vertices aren't necessary. I just need a clever way to draw it with the given vertices. Somehow recursively deferring the triangles which result from the 2nd, 3rd, ... vertex on the same gradient.
That's right, no new vertices are necessary, but you need more edges.
... I managed to do it without calling an extra triangulation function. Instead of drawing a triangle fan with 34 vertices and center, I now draw an indexed triangle list with 30 vertices and 90 indices. No glitches so far...