
Field of view  primitives glitch 
Polybios
Member #12,293
October 2010

{"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).
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. 
Elias
Member #358
May 2000

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...  
Polybios
Member #12,293
October 2010

I'm atan2ing it from the coordinates to check. Yes, it's exactly the same. 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 260308. The vertices are generated by intersecting the current angles with the line segments. I'll post the "output" function here: 319 private function addTriangle(angle1:Float, angle2:Float, segment:Segment) {
320 var p1:Point = center;
321 var p2:Point = {x:center.x + Math.cos(angle1), y:center.y + Math.sin(angle1)};
322 var p3:Point = {x:0.0, y:0.0};
323 var p4:Point = {x:0.0, y:0.0};
324
325 if (segment != null) {
326 // Stop the triangle at the intersecting segment
327 p3.x = segment.p1.x;
328 p3.y = segment.p1.y;
329 p4.x = segment.p2.x;
330 p4.y = segment.p2.y;
331 } else {
332 // never happens
333 return;
334 }
335
336 var pBegin = lineIntersection(p3, p4, p1, p2);
337
338 p2.x = center.x + Math.cos(angle2);
339 p2.y = center.y + Math.sin(angle2);
340 var pEnd = lineIntersection(p3, p4, p1, p2);
341
342 output.push(pBegin);
343 output.push(pEnd);
344 }

Elias
Member #358
May 2000

cx: 499, cy: 238 vertex 30: 416.001801, 321.000000, angle: 134.999374 They don't are the same, which I suspect is the problem.  
Polybios
Member #12,293
October 2010

I think I don't understand what you mean. 
Elias
Member #358
May 2000

No, I mean, some rounding error may have caused it... so maybe you can use double instead of float or something like that.  
Polybios
Member #12,293
October 2010

I've tried to replace every "float" with "double". To no avail: The glitchline 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? 
SiegeLord
Member #7,827
October 2006

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 tjunction, 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_TJunctions_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. "For in much wisdom is much grief: and he that increases knowledge increases sorrow."Ecclesiastes 1:18 
Polybios
Member #12,293
October 2010

Thank you for your words of wisdom. Edit: Is triangulating it expensive performancewise? 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. 
ph03nix
Member #15,028
April 2013

If I understand correctly you're drawing it semitransparently 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 semitransparency. 
Polybios
Member #12,293
October 2010

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. 
SiegeLord
Member #7,827
October 2006

Polybios said: Is triangulating it expensive performancewise? I don't think it's too bad. Quote: 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. "For in much wisdom is much grief: and he that increases knowledge increases sorrow."Ecclesiastes 1:18 
Polybios
Member #12,293
October 2010

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