0

I am trying to simulate an omnidirectional light source in a 2D room. I would like to set up a room and have "light" propagate from a point source, stopping only when it reaches a wall. The result is shadows will be cast where the light cannot reach. The below picture shows the problem with several point sources

enter image description here

I am implementing this in D3 JS as part of a game based around the art gallery problem.

I am struggling to come up with a data structure suitable for allowing this simulation and animation. I imagine a circle radiates out from the source, splitting into arcs whenever it encounters a wall? Is there a way to do this without simulating lots of individual light beams?

David Ferris
  • 2,215
  • 6
  • 28
  • 53
  • Do you really need SVG output? I seems like it would be a lot simpler to implement this on a Canvas. For each pixel work out which light sources it can see. Perhaps it may not be fast enough to run in real time. But you may not need that. Or if you need SVG, you could use polygons for the walls and generate an `` for the lit background. – Paul LeBeau Jul 20 '17 at 17:55
  • D3/SVG is not a requirement at all, it was just a first thought for polygon based animation/etc. The paradigm you have proposed (pixel by pixel line of sight) is actually better than anything I have come up with yet. Thanks! – David Ferris Jul 20 '17 at 18:08
  • I imagine it would still be possible to animate the circular light propagation by spiraling outwards from the point source, as opposed to traversing over the rows of pixels? – David Ferris Jul 20 '17 at 18:10
  • Assuming your "gallery" has walls like the example, then each pixel is just 36 calls to a [line/rectangle intersect function](https://stackoverflow.com/questions/1585525/how-to-find-the-intersection-point-between-a-line-and-a-rectangle/31254199#31254199) (4 lights x 9 rectangular walls). – Paul LeBeau Jul 20 '17 at 18:25

1 Answers1

1

I don't really think d3 will help here, besides drawing the SVG. On the theoretical side, <circle> elements have defined radii, which means that they will curve at the circumference. Arcs will do the same. The art gallery problem deals with polygonal spaces and circles are (arguably) not polygons.

On the practical side, if you are going to use d3, I would instead recommend making <polygon> elements. From your picture, it looks as though each 'light' covers at least one room, and the points of a polygon can match the coordinates of the walls. Where the lights extend out into other rooms, they look to be, from the dotted lines, triangles in most cases. Where the colors overlap, d3 can help because SVG elements are allowed fill properties with alpha components.

d3.select('svg').append('polygon')
    .attr('fill', 'rgba(255, 0, 0, 0.5)')
    .attr('d', foo);

That will draw a polygon with a semi-transparent red color.

However, d3 won't help you figure out the coordinates of these lights. IMHO you could do this with a search algorithm which starts at a 'light source' and emanates out in a linear fashion checking for walls. When it finds a wall, it takes the coordinates of that 'stop' point and adds it to the path of the polygon. When the polygon draws, the colors will overlap and appear to be light sources.

M. Davis
  • 669
  • 2
  • 10
  • 17
  • I should also add that this question is pretty theoretical and probably doesn't belong on SO – M. Davis Jul 20 '17 at 12:42
  • Thank you for your answer - I suspected that SO may not be the most appropriate place either. Are there better suited SE forums? – David Ferris Jul 20 '17 at 14:36
  • 1
    In a perfect world, some sort of Computational Geometry SE site would be best, but in lieu I would guess either [Theoretical CS](https://cstheory.stackexchange.com/) or maybe [Code Golf & Puzzles](https://codegolf.stackexchange.com/). You can always [start your own](http://area51.stackexchange.com/) too. IMO seems like a good question for CS/Math professors or a challenge for co-workers – M. Davis Jul 20 '17 at 15:06