Lighting Polygon Clipping

[Robustprogram]

Hello everyone,
I am currently trying to write a dynamic lighting system. Right now I am trying to perform a polygon clipping on a quad as shown in the attachment but I am not sure how to do it. If anyone can help, it will be appreciated 

[Nexus]

Have you searched already? There's a ton of information about it on the Internet... Maybe even on the site of that image.

[eXpl0it3r]

You might be interested in looking at two lighting systems that were presented here on the forum.

• Let There Be Light
• GLLight2D

It's a big topic, you should rather do some research on your own, than waiting for someone to explain it to you.

[Robustprogram]

I have spent hours searching on 2D dynamic lighting and I haven't being able to get the most out of it, so I'm wondering if someone can help point onto the right track. (I don't have good research skills).

[Nexus]

Then it might be a good idea to look at the libraries suggested by eXpl0it3r

[FRex]

This is not based on any 'research' or 'reading' I came up with it myself, so pardon me if it sucks. (But I think it's rather good and quick).
I wrote a note describing that and then I implemented it dirtily for myself. So far it's point lights and hard shadows(no penumbras) only.
Algorithm is:
For each light for each convex hull do:
1. find two points that will create lines with biggest angle when a
2. take curve enclosed between these points, including them
3. add 3 points: one taken from line made by light point and last edge point, one taken from line made by light point and avg of hull vertices and one taken from line made by light point and last edge point. Take them from far away the light point so that they lie at least 2* radius of light away from it, to be safe.
4. This polygon is the hard shadow for this hull made by this light. That's it.

Then you draw it using render textures and right blends and/or shaders, or clip the light circle with something like clipperlib and draw resulting concave poly after decomposing it (actually, I'd have to check but you might not even need to decompose it, since some concave shapes can be drawn using convex SFML polygon class, this result might fit the constraints required.. almost surely it will, since the way shadows are made fits the constraint SFML places but I'd still check if I went that route ).
The algorithm of course doesn't include the optimizations, limiting light angle and checking if light is inside hull and so on. It make shadows even if they are not needed because they don't lie in light circle, but all other things are 'noise' for the algorithm code, needed but not contributing to the algorithm itself.

Here's a screenshot with white lines drawn from light to each vertex and shadows being blue instead of black, you can see two outmost are selected and then a point is placed using them and then additional three points are added, two from that line and one from(not drawn) line that goes from light through middle of polygon.


I might post this code.. maybe.. if someone really wants, it's not optimized and messy now, and what I'm doing is not adding any public API and just commenting out //private: in every class and working that way. Definitely not the way to showcase work.
Also it's just hard shadows so far, no cones, etc. and I'd need to take some code from clipperlib and box2d for optimizations and so on.

[Lee R]

Algorithm is:
For each light for each convex hull do:
1. find two points that will create lines with biggest angle when a
2. take curve enclosed between these points, including them
3. add 3 points: one taken from line made by light point and last edge point, one taken from line made by light point and avg of hull vertices and one taken from line made by light point and last edge point. Take them from far away the light point so that they lie at least 2* radius of light away from it, to be safe.
4. This polygon is the hard shadow for this hull made by this light. That's it.

I won't pretend to understand exactly what you're describing there, but it sounds overly complicated. To form hard edged shadow geometry, you can project (away form the light source) the end points of each non-facing edge. The quad formed by the original end points and the projected end points is then the shadow geometry.

Here is the most drain-dead-simple form I could come up with to demonstrate. To make the shadow always reach the edge of the screen, you'd simply project the end points further out.

#include <SFML/Graphics.hpp>

sf::VertexArray shadow(const sf::Shape& caster, sf::Vector2f emitter, sf::Color ambient)
{
    sf::VertexArray geometry(sf::Quads);

    // for each edge of 'shape'.
    const unsigned size = caster.getPointCount();
    for (unsigned i = size - 1, j = 0; j < size; i = j++)
    {
        const auto& xf = caster.getTransform();
        // find world space end points of current edge.
        auto a = xf.transformPoint(caster.getPoint(i));
        auto b = xf.transformPoint(caster.getPoint(j));

        auto ab = b - a;
        auto ea = a - emitter;
        // if current egde faces away from emitter.
        if ((ab.x * ea.y - ab.y * ea.x) < 0.0f)
        {
            // make quad from edge end points and projected end points.
            geometry.append(sf::Vertex(a, ambient));
            geometry.append(sf::Vertex(a + ea, ambient));
            geometry.append(sf::Vertex(b + (b - emitter), ambient));
            geometry.append(sf::Vertex(b, ambient));
        }
    }

    return geometry;
}

int main()
{
    sf::RenderWindow window(sf::VideoMode(800, 600), "Shadows");
    window.setFramerateLimit(30);

    // Light blocker.
    sf::RectangleShape shape(sf::Vector2f(100.0f, 100.0f));
    shape.setFillColor(sf::Color::Blue);
    shape.setPosition(250.0f, 250.0f);
    shape.setRotation(60.0f);

    sf::Vector2f emitter;   // Position of light emitter.

    while (window.isOpen())
    {
        sf::Event event;
        while (window.pollEvent(event))
        {
            if (event.type == sf::Event::Closed)
            {
                window.close();
            }
            else if (event.type == sf::Event::MouseMoved)
            {
                // Emitter position tracks mouse pointer.
                emitter = sf::Vector2f(
                    static_cast<float>(event.mouseMove.x),
                    static_cast<float>(event.mouseMove.y)
                );
            }
        }

        window.clear(sf::Color::White);
        // Draw shadows cast by 'shape'.
        window.draw(shadow(shape, emitter, sf::Color::Black));
        // Dwaw actual 'shape'.
        window.draw(shape);
        window.display();
    }

    return 0;
}
 

The real tricky part is forming an image composed of multiple, coloured, shadow casting lights using only the blend modes provided by SFML.

[FRex]

How would one go about and draw the shadows with coloured light your way? Two render textures, one to draw shadows on top of light circle and then additively blend onto other texture which after all lights gets drawn onto scene with blend multiply? I'm asking about scene with multiple coloured lights, each casting multiple shadows(there are multiple hulls within reach of each light).

[Lee R]

I lost my lighting code in the great reformat of 2013. A sad time indeed. Your intuition looks right to me, though. This is from memory so please excuse any mistakes; in pseudo code, it goes something like:

Ambient:Color        - The colour of "no light".
Geometry:VertexArray - Shadow geometry.
LightTex:Texture     - Light falloff texture.
RT1:RenderTexture    - Holds entire light map.
RT2:RenderTexture    - Holds current light map pass.
Scene                - Anything affected by light.

RT1.clear(Ambient)
foreach light in lights_on_screen()
    Geometry.clear()
    foreach shape in shapes_in_range_of(light)
        Geometry.add(make_shadow(light, shape))
    RT2.clear(Black)
    RT2.draw(LightTex, BlendNone)
    RT2.draw(Geometry, BlendNone)
    RT1.draw(RT2, BlendAdd)
Screen.draw(Scene)
Screen.draw(RT1, BlendMultiply)
 

[FRex]

This is exactly what I mean, I did that, performance was completely abysmal. Render Target switches are expensive in SFML.
On my laptop with intel GPU(I know, I know, but still ) it starts being too slow with 20 lights, there is no textures or shaders even so the real life limit is even less when these eat small bits of time. It's as many render target switches as there are lights and as many draws as there are lights+shadows.

However I expected that(esp on my intel card) so I decided to go with another approach: for each light I subtract from light circle all the shadow polygons(which is why I wanted them as polygons rather) and then draw resulting polygon with custom triangle fan vertex array.
It takes just one clear, num_of_light draws and one display of render texture, there is single render texture and there are no switches of render target constantly, just one when you enter the shadow drawing code and then one when you draw first thing after it's done.

This algorithm starts giving out at around 30-40 lights now but it's debug build and there are no optimizations(either in c++ code by me or in generated code by gcc), no quad tree, no distance checking, no nothing - each light has shadow for each hull and most tests are not necessary + I allocate idiotic amounts of 64 bit int vertices and 32 bit float(SFML) vertices every frame, often it's an std::vector of std::vector of them.

It's half experiment with this approach I had an idea of (this thread title inspired me) and half attempt at good hard shadows code.
I'm not sure if your method with switching render target all the time is bad for good Nvidia and ATI cards as it is for my Intel.

[Lee R]

I'm running a GTX 660 (low end of the mid range) and don't remember having any issues with the performance of that technique. I didn't envision creating scenes with 20 shadow casting lights in them, though (not every light needs to cast a shadow e.g. emissive lights). Fill rate could also have been an issue, if you weren't using downscaled render textures. I wonder how that Intel card would fair with a raster based approach Overall, the 'lights as geometry' is probably the way to go; I just went with what seemed quickest to implement and found the performance acceptable.