Welcome, Guest. Please login or register. Did you miss your activation email?

Author Topic: Subtract Polygons From Polygons(Create Concave Shape)  (Read 3341 times)

0 Members and 1 Guest are viewing this topic.

MrSnappingTurtle

  • Newbie
  • *
  • Posts: 21
    • View Profile
    • Email
Subtract Polygons From Polygons(Create Concave Shape)
« on: February 18, 2015, 08:40:18 pm »
Hi,
I am trying to create a concave shape. As SFML does not support concave shapes, I can create a "hull" that encompasses the concave shape. I then look at the points that are not on the hull and create a triangle consisting of the point, a point on the hull to the left, and a point on the hull to the right. This will make a triangle that is the hole (the concave part of the polygon). Once I have all the holes, I want to subtract them from the "hull" and get my final polygon. How can I do the subtracting step? Is that even possible?

As a side note, I would then draw that shape to a sf::RenderTexture which  I would apply a light/glow fragment shader in order to create dynamic shadow light. Is that the proper way to do such a thing?

If anyone is wondering, this is what I am trying to create the polygon for: http://ncase.me/sight-and-light/

Thanks!

eXpl0it3r

  • SFML Team
  • Hero Member
  • *****
  • Posts: 11030
    • View Profile
    • development blog
    • Email
Re: Subtract Polygons From Polygons(Create Concave Shape)
« Reply #1 on: February 19, 2015, 03:08:14 pm »
Are you talking about triangulation?

If you just need a concave shape, you could look at Thor or it's implementation.
Official FAQ: https://www.sfml-dev.org/faq.php
Official Discord Server: https://discord.gg/nr4X7Fh
——————————————————————
Dev Blog: https://duerrenberger.dev/blog/

grok

  • Jr. Member
  • **
  • Posts: 67
    • View Profile
    • Email
Re: Subtract Polygons From Polygons(Create Concave Shape)
« Reply #2 on: March 10, 2015, 02:50:15 pm »
Hi there.

I think I have a solution for your problem, at least I hope so. Okay, here we go.

Suppose we have:
convex shapes/polygons which represent the light areas (which we have calculated using the rays intersection algorithm or alike).
Let's call them *the visible areas*.

Now, the problem we are facing is that we want to draw all the scene's objects to the screen so that they became fully/partly invisible if they do not fall into the visible areas (see above).

Of course, having visible areas related to the screen, we might calculate the remaining polygons (i.e. an invisible ones), so that invisible areas + visible areas = the whole screen's rectangle.
They, presumably, will be represented as the concave shape(s). Then, having these invisible area(s) we can utilize the some of the approaches described here: http://en.sfml-dev.org/forums/index.php?topic=7427.0 There are at least 3 solutions  (with the 1st one being kind of slow). But computing the invisible areas polygons is not an easy task, which involves a lot of math, though of course it is possible.

I have an alternative solution which involves SFML's blend modes and RenderTexture.
Here it is:
1) instantiate a RenderTexture object filled with the transparent color.
2) draw the visible areas (i.e. your lights convex shapes, for example) onto it.
3) perform RenderTexture display method
4) instantiate a blend mode with alphaSrcFactor equal to zero, and alphaDstFactor equal to one.
5) draw all your scene's objects (which, possibly, should be only partly visible or not visible at all) onto the RenderTexture using the blend mode from the 4th step.
6) clear your renderWindow (i.e. the target surface) with the desired color, whatever the scene's background color you want.
7) draw your RenderTexture on top of the renderWindow

Here is a code snippet which demonstrates the problem (there're the two shapes: the red and the green rectangles. the scene's background color is blue):
#include <SFML/Graphics.hpp>
#include <SFML/Graphics/RectangleShape.hpp>
#include <SFML/Graphics/BlendMode.hpp>

int main()
{
    sf::RenderWindow window(sf::VideoMode(800, 600), "Visible vs Invisible areas render");
    window.setVerticalSyncEnabled(true);
   
    sf::RenderTexture targetVisible;
    if (!targetVisible.create(window.getSize().x, window.getSize().y))
        return -1;
    //targetVisible.clear(sf::Color::Transparent); //!
           
    //visible shape
    sf::RectangleShape rectangle1;
        rectangle1.setSize(sf::Vector2f(100, 200));
        rectangle1.setFillColor(sf::Color::Green);
        rectangle1.setPosition(100, 200);    
       
        targetVisible.draw(rectangle1);
    targetVisible.display();
   
    /*
     * uncomment, if you want to have a look at the intermediate image
     * (it is the transparent rectangle with the small green rectangle drawn on it)
     * */

        targetVisible.getTexture().copyToImage().saveToFile("intermediate_result.png");
       
    //partly visible shape
    //sf::BlendMode bm; //!
    //bm.alphaSrcFactor = sf::BlendMode::Zero; //!
    //bm.alphaDstFactor = sf::BlendMode::One;  //!
   
        sf::RectangleShape rectangle2;
        rectangle2.setSize(sf::Vector2f(200, 400));
        rectangle2.setFillColor(sf::Color::Red);
        rectangle2.setPosition(150, 300);
       
        targetVisible.draw(rectangle2/*, bm*/); //!
        targetVisible.display();
           
    while (window.isOpen())
    {
        sf::Event event;
        while (window.pollEvent(event))
        {
            if (event.type == sf::Event::Closed)
                window.close();
        }

        window.clear(sf::Color::Blue);
        window.draw(sf::Sprite(targetVisible.getTexture()));

        window.display();
    }

    return 0;
}
 


Here is my solution:
#include <SFML/Graphics.hpp>
#include <SFML/Graphics/RectangleShape.hpp>
#include <SFML/Graphics/BlendMode.hpp>

int main()
{
    sf::RenderWindow window(sf::VideoMode(800, 600), "Visible vs Invisible areas render");
    window.setVerticalSyncEnabled(true);
   
    sf::RenderTexture targetVisible;
    if (!targetVisible.create(window.getSize().x, window.getSize().y))
        return -1;
    targetVisible.clear(sf::Color::Transparent); //!
           
    //visible shape
    sf::RectangleShape rectangle1;
        rectangle1.setSize(sf::Vector2f(100, 200));
        rectangle1.setFillColor(sf::Color::Green);
        rectangle1.setPosition(100, 200);    
       
        targetVisible.draw(rectangle1);
    targetVisible.display();
   
    /*
     * uncomment, if you want to have a look at the intermediate image
     * (it is the transparent rectangle with the small green rectangle drawn on it)
     * */

        targetVisible.getTexture().copyToImage().saveToFile("intermediate_result.png");
       
    //partly visible shape
    sf::BlendMode bm; //!
    bm.alphaSrcFactor = sf::BlendMode::Zero; //!
    bm.alphaDstFactor = sf::BlendMode::One;  //!
   
        sf::RectangleShape rectangle2;
        rectangle2.setSize(sf::Vector2f(200, 400));
        rectangle2.setFillColor(sf::Color::Red);
        rectangle2.setPosition(150, 300);
       
        targetVisible.draw(rectangle2, bm); //!
        targetVisible.display();
           
    while (window.isOpen())
    {
        sf::Event event;
        while (window.pollEvent(event))
        {
            if (event.type == sf::Event::Closed)
                window.close();
        }

        window.clear(sf::Color::Blue);
        window.draw(sf::Sprite(targetVisible.getTexture()));

        window.display();
    }

    return 0;
}
 

Compile with:
Quote
g++ ./test.cpp -lsfml-window -lsfml-system -lsfml-graphics

The 1st code snippet generates the image 1, the 2nd one gives us the image 2 from the attachment.

Now imagine that the green rectangle is your visible area, calculated from the lights and the red one is some scene's object which visibility is in question, depending on its location on the scene related to the visible lights area ;-)

Hope that helps.
« Last Edit: March 10, 2015, 03:39:16 pm by grok »