Allegro.cc - Online Community

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

This thread is locked; no one can reply to it. rss feed Print
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"}608294

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

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

--
"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
avatar

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
avatar

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
avatar

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: