{"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.

I don't think it's too bad.

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...