Allegro.cc Forums » Programming Questions » Field of view - primitives glitch

 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).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?
 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... --"Either help out or stop whining" - Evert
 Polybios Member #12,293 October 2010 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.hxThe 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:#SelectExpand 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: 238vertex 30: 416.001801, 321.000000, angle: 134.999374vertex 31: 299.000000, 438.004333, angle: 134.999374They don't are the same, which I suspect is the problem. --"Either help out or stop whining" - Evert
 Polybios Member #12,293 October 2010 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?
 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. --"Either help out or stop whining" - Evert
 Polybios Member #12,293 October 2010 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?
 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 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. "For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]
 Polybios Member #12,293 October 2010 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.
 ph03nix Member #15,028 April 2013 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.
 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 performance-wise? 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[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]
 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...
 Go to: Allegro Development Installation, Setup & Configuration Allegro.cc Comments Off-Topic Ordeals The Depot Game Design & Concepts Programming Questions Recent Threads