1
\$\begingroup\$

I wanted to add a light source for a project I'm working on, and luckily I had some code based on this article: http://ncase.me/sight-and-light/, but when I ran the code after carefully transplanting it I realized my implementation of lighting was really slow. In the previous project I only ever had to worry about a few polygons at a time, but in my new project there are a metric ton of different polygons that the ray caster is checking against. I can avoid testing every ray against every polygon side.

\$\endgroup\$
  • \$\begingroup\$ "I can avoid testing every ray against every polygon side." That sounds like a good plan. Have you hit any particular snag putting this idea into practice? Any profiling information you can share about where the bottleneck in your lighting is? \$\endgroup\$ – DMGregory May 29 '18 at 19:16
1
\$\begingroup\$

Optimize using a quadtree so that you only need to check a few polygons instead of all of them.

https://gamedevelopment.tutsplus.com/tutorials/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space--gamedev-374

Edit: Okay, I'll admit I didn't read that well and made a mistake.

Light paths are pretty much the same as lines of sight of a viewer, so many of the same algorithms related to rendering should apply.

One way I can think of is to test only the polygons visible in the screen, and sort them all from closest to furthest each time the viewer moves, preferably using an insertion sort as it's fastest with almost sorted arrays. Test polygons from front to back, while keeping a record of how much of the 360 degree domain around the light has been tested. When all of the domain has been tested, then stop looping through the polygons.

Additionally, only test the lines where the face is visible in the light. This is exactly the same as determining whether a point is on the left or the right of a line, discussed on the link below. This also means the order of the points on the polygon must be consistent, such as going clockwise.

https://stackoverflow.com/questions/1560492/how-to-tell-whether-a-point-is-to-the-right-or-left-side-of-a-line

Another way, probably the most efficient way possible, is to use binary space partitioning. I'm not very familiar with it, and I haven't seen it used specifically in 2D lighting. In old games like DOOM, which is actually a top down 2D shooter on the inside, it is used to determine which faces should be drawn without looping through every face. I am probably not able to explain this properly, so here's a few links.

https://www.youtube.com/watch?v=yTRzfKh4Tg0 https://en.wikipedia.org/wiki/Binary_space_partitioning

\$\endgroup\$
  • \$\begingroup\$ could you please elaborate as to how you would use a quad tree to eliminate polygons checked against for lighting? \$\endgroup\$ – Julian May 28 '18 at 21:37
  • \$\begingroup\$ The post was heavily edited and is now a completely different answer. \$\endgroup\$ – Neal_Nicdao May 28 '18 at 22:43

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.