3 ms·
I think the O(row * col * light_count * dist) algorithm could be optimized to run in O(row * col * light_count). The idea is, imagine the light is coming from
by abirler 8y ago
I think the O(row * col * light_count * dist) algorithm could be optimized to run in O(row * col * light_count).
The idea is, imagine the light is coming from the left, and our height map consists of a single row that looks like (0,5,2,7,1).
By using the angle of the light, we can compute from left to right whether the current point should be visible. We only need to store the last point that was also visible since that is the only point that can block us from this light source. For the given example, at point of height 2 we only need to care about the previously visible point of height 5. If 2 isn't visible, 5 remains the "highest" point, if 2 is visible, 2 becomes the "highest" point, there is no danger that 5 will block something beyond two since 2 wasn't blocked. So at each point we only have to check with one previous point, not all.
If the light isn't coming from exactly the left side, then we can tranform the image so in such a way that the light is now from the left. This transformation will take O(r * c) time per light.
Total complexity: O(transforms + visibilityChecks + mergingResults) = O(l * r * c)
- tylermw 8y agoOne thing I didn't mention in the article are a few optimizations I made that make it significantly less than O(row * col * light_count * dist). First, if the ray exits the map region (either by going higher than the highest point on the map, or outside the boundaries), it stops propagating that ray and calls it a non-intercept (cutting down on the "dist" complexity). Second, if you're drawing multiple rays for a finite sized light source, I first order them by angle and send the rays out from the lowest to the highest angle. If a ray at a lower angle doesn't intercept a surface, higher angles won't either. So you save a lot on the "light_count" complexity.