So so close to getting my visibility polygon working. I'm using an SFML triangle fan with all the vertex points sorted by angle size with position 0 set to the mouse coords and the last element set to element 2, I needed to do this to fill in the gap for the last triangle.
However; a triangle appears to be missing at certain locations, see video.
I suspect that I'm having an out by one issue with my loop. I've tried rearranging a few numbers but this is the closest I can get.

https://streamable.com/d46yih​

sf::VertexArray visibilityPolygon(sf::TriangleFan, vectorAngleContainer.size() + 1);
visibilityPolygon[0] = ray[0].position;
visibilityPolygon[0].color = sf::Color::Red;

for (int i = 1; i <= vectorAngleContainer.size(); i++)
{
    visibilityPolygon[i] = sf::Vertex(sf::Vector2f(vectorAngleContainer[i-1].position.x, vectorAngleContainer[i-1].position.y), sf::Color::Red);
}
visibilityPolygon[vectorAngleContainer.size()] = visibilityPolygon[1].position;

vectorAngleContainer() is a vector of structs that holds a point and and angle.

nortski said:
all the vertex points sorted by angle

Watching the video, i guess it breaks if your at an edge, so a vertex from that edge and its projection outwards have the same angle.
Eventually this flips winding order and a triangle gets culled, or something like that.

JoeJ said:
Eventually this flips winding order and a triangle gets culled, or something like that.

Yeh I think that is what is probably happening. Not sure how to correct it though.

nortski said:
Not sure how to correct it though.

Well, you could tell us more about your algorithm.
The interesting parts surely happen before the final sort by anlge?

@JoeJ Sure. I create a ray from the mouse position to each vertex of each primitive shape and the boundary. I create to additional rays that are offset either side of the main ray by 0.0001 radians.

I then check each ray to see if it intersects with any line segments. If so then set the end point of the ray to where it intersects the line.

Then I calculate the angle of each ray and sort them in order from smallest to largest.

Finally; I create a visibility polygon using the sorted vector of rays.

My code below needs tidying up a lot, this is just for testing.

#include <iostream>
#include <SFML/Graphics.hpp>
#include <vector>
#include "Vec2.h"
#include <algorithm>

struct Intersect
{
    bool result = false;
    Vec2 pos;
};

struct LineSegment
{
    Vec2 a;
    Vec2 b;
};

struct VectorAngle
{
    Vec2 position;
    float angle = 0.0f;
};

float crossProduct(Vec2& a, Vec2& b)
{
    return a.x * b.y - b.x * a.y;
}

Intersect lineIntersect(Vec2& a, Vec2& b, Vec2& c, Vec2& d)
{
    Vec2 r = (b - a);
    Vec2 s = (d - c);
    float rxs = crossProduct(r, s);
    Vec2 cma = c - a;
    float t = crossProduct(cma, s) / rxs;
    float u = crossProduct(cma, r) / rxs;

    if (t >= 0 && t <= 1 && u >= 0 && u <= 1)
        return { true, Vec2(a.x + t * r.x, a.y + t * r.y) };
    else
        return { false, Vec2(0.0f, 0.0f) };
}

void updateMousePosition(Vec2& mousePos, sf::RenderWindow& window)
{
    mousePos.x = (float)sf::Mouse::getPosition(window).x;
    mousePos.y = (float)sf::Mouse::getPosition(window).y;
}

Vec2 getClosestIntersect(Vec2& origin, std::vector<Vec2>& lineIntersects)
{
    Vec2 intersect = lineIntersects[0];
    float dist = origin.dist(lineIntersects[0]);

    for (int i = 1; i < lineIntersects.size(); i++)
    {

        if (origin.dist(lineIntersects[i]) < dist)
        {
            dist = origin.dist(lineIntersects[i]);
            intersect = lineIntersects[i];
        }
    }

    return intersect;
}

float computeAngle(float ax, float ay, float bx, float by) {

    float radians = std::atan2f((by - ay), (bx - ax));

    if (radians < 0.0f)
        radians += 2.0f * 3.14160f;

    float degrees = radians * (180.0f / 3.14160f);
    return radians;
};

int main()
{
    sf::RenderWindow                window(sf::VideoMode(900, 900), "My window");
    sf::RectangleShape              boundry(sf::Vector2f(780.0f, 780.0f));
    sf::RectangleShape              rect1(sf::Vector2f(200.0f, 75.0f));
    sf::CircleShape                 triangle(80, 3);
    std::vector<Vec2>               verticesVector;
    std::vector<LineSegment>        linesVector;
    std::vector<sf::VertexArray>    rays;
    std::vector<sf::VertexArray>    negOffsetRays;
    std::vector<sf::VertexArray>    posOffsetRays;
    Vec2                            origin;
    Vec2                            dest;
    Vec2                            direction;
    Vec2                            directionNorm;
    Vec2                            negOffsetRay;
    Vec2                            posOffsetRay;
    Vec2                            nearestIntersect;
    Intersect                       intersect;
    std::vector<Vec2>               lineIntersects;
    std::vector<VectorAngle>        vectorAngleContainer;
    sf::VertexArray                 ray(sf::Lines, 2);
    sf::VertexArray                 ray2(sf::Lines, 2);
    sf::VertexArray                 ray3(sf::Lines, 2);
    float                           angle = 0.00001f;

    window.setFramerateLimit(60);
 
    boundry.setOrigin(boundry.getSize().x / 2, boundry.getSize().y / 2);
    boundry.setPosition(sf::Vector2f(window.getSize().x / 2.0f, window.getSize().y / 2.0f));
    boundry.setOutlineThickness(1.0f);
    boundry.setOutlineColor(sf::Color::White);
    boundry.setFillColor(sf::Color::Transparent);
    rect1.setOrigin(rect1.getSize().x / 2, rect1.getSize().y / 2);
    rect1.setPosition(sf::Vector2f(200.0f, 300.0f));
    rect1.setOutlineThickness(1.0f);
    rect1.setOutlineColor(sf::Color::White);
    rect1.setFillColor(sf::Color::White);
    rect1.setRotation(150);
    triangle.setOrigin(triangle.getRadius() / 2, triangle.getRadius() / 2);
    triangle.setPosition(sf::Vector2f(600, 500));
    triangle.setOutlineThickness(1.0f);
    triangle.setOutlineColor(sf::Color::White);
    triangle.setFillColor(sf::Color::White);
    triangle.setRotation(60);
    

    // Calculate the line segments of each primitive and add to linesVector
    // Add all vertex points to verticeVector
    for (int i = 0; i < boundry.getPointCount(); i++)
    {
        LineSegment line;

        if (!(i == boundry.getPointCount() - 1))
        {
            line.a = { boundry.getTransform().transformPoint(boundry.getPoint(i)).x , boundry.getTransform().transformPoint(boundry.getPoint(i)).y };
            line.b = { boundry.getTransform().transformPoint(boundry.getPoint(i + 1)).x , boundry.getTransform().transformPoint(boundry.getPoint(i + 1)).y };
            linesVector.push_back(line);
            verticesVector.push_back(line.a);
        }
        else
        {
            line.a = { boundry.getTransform().transformPoint(boundry.getPoint(i)).x , boundry.getTransform().transformPoint(boundry.getPoint(i)).y };
            line.b = { boundry.getTransform().transformPoint(boundry.getPoint(0)).x , boundry.getTransform().transformPoint(boundry.getPoint(0)).y };
            linesVector.push_back(line);
            verticesVector.push_back(line.a);
        }
    }
    for (int i = 0; i < rect1.getPointCount(); i++)
    {
        LineSegment line;

        if (!(i == rect1.getPointCount() - 1))
        {
            line.a = { rect1.getTransform().transformPoint(rect1.getPoint(i)).x , rect1.getTransform().transformPoint(rect1.getPoint(i)).y };
            line.b = { rect1.getTransform().transformPoint(rect1.getPoint(i + 1)).x , rect1.getTransform().transformPoint(rect1.getPoint(i + 1)).y };
            linesVector.push_back(line);
            verticesVector.push_back(line.a);
        }
        else
        {
            line.a = { rect1.getTransform().transformPoint(rect1.getPoint(i)).x , rect1.getTransform().transformPoint(rect1.getPoint(i)).y };
            line.b = { rect1.getTransform().transformPoint(rect1.getPoint(0)).x , rect1.getTransform().transformPoint(rect1.getPoint(0)).y };
            linesVector.push_back(line);
            verticesVector.push_back(line.a);
        }
    }
    for (int i = 0; i < triangle.getPointCount(); i++)
    {
        LineSegment line;

        if (!(i == triangle.getPointCount() - 1))
        {
            line.a = { triangle.getTransform().transformPoint(triangle.getPoint(i)).x , triangle.getTransform().transformPoint(triangle.getPoint(i)).y };
            line.b = { triangle.getTransform().transformPoint(triangle.getPoint(i + 1)).x , triangle.getTransform().transformPoint(triangle.getPoint(i + 1)).y };
            linesVector.push_back(line);
            verticesVector.push_back(line.a);
        }
        else
        {
            line.a = { triangle.getTransform().transformPoint(triangle.getPoint(i)).x , triangle.getTransform().transformPoint(triangle.getPoint(i)).y };
            line.b = { triangle.getTransform().transformPoint(triangle.getPoint(0)).x , triangle.getTransform().transformPoint(triangle.getPoint(0)).y };
            linesVector.push_back(line);
            verticesVector.push_back(line.a);
        }
    }
       

    // Init main ray point 2 position to destination coords
    ray[1].position = { (float)window.getSize().x, (float)window.getSize().y };

    sf::VertexArray visibilityPolygon(sf::TriangleFan);

    while (window.isOpen()) {

        window.clear(sf::Color::Black);
        lineIntersects.clear();
        rays.clear();
        vectorAngleContainer.clear();

        sf::Event event;
        while (window.pollEvent(event)) {
            if (event.type == sf::Event::Closed) {
                window.close();
            }
        }

        // If mouse cursor is within window space then update point 1 coords of all rays to mouse position. Pass in window for window coords system
        if ((float)sf::Mouse::getPosition(window).x >= 0.0f && (float)sf::Mouse::getPosition(window).x <= (float)window.getSize().x && (float)sf::Mouse::getPosition(window).y >= 0.0f && (float)sf::Mouse::getPosition(window).y <= (float)window.getSize().y)
        {
            ray[0].position = sf::Vector2f((float)sf::Mouse::getPosition(window).x, (float)sf::Mouse::getPosition(window).y);
            ray2[0].position = sf::Vector2f((float)sf::Mouse::getPosition(window).x, (float)sf::Mouse::getPosition(window).y);
            ray3[0].position = sf::Vector2f((float)sf::Mouse::getPosition(window).x, (float)sf::Mouse::getPosition(window).y);
        }

        // Create a ray with two offset rays and add to rays vector
        for (int i = 0; i < verticesVector.size(); i++)
        {
            //if (i == 11)
            {
                ray[1].position = { verticesVector[i].x, verticesVector[i].y };
                direction = { verticesVector[i].x - ray[0].position.x, verticesVector[i].y - ray[0].position.y };
                directionNorm = direction.normalized();

                negOffsetRay = { (directionNorm.x * cosf(angle) + directionNorm.y * sinf(angle)), (directionNorm.x * -sinf(angle) + directionNorm.y * cosf(angle)) };
                posOffsetRay = { (directionNorm.x * cosf(-angle) + directionNorm.y * sinf(-angle)), (directionNorm.x * -sinf(-angle) + directionNorm.y * cosf(-angle)) };
                negOffsetRay * 1500.0f;
                posOffsetRay * 1500.0f;
                ray2[1].position = { ray2[0].position.x + negOffsetRay.x, ray2[0].position.y + negOffsetRay.y };
                ray3[1].position = { ray3[0].position.x + posOffsetRay.x, ray3[0].position.y + posOffsetRay.y };

                rays.push_back(ray);
                rays.push_back(ray2);
                rays.push_back(ray3);
            }
        }

        // Check if a ray intersects with a line segment
        for (auto& ray : rays)
        {
            origin = { ray[0].position.x, ray[0].position.y };
            dest = { ray[1].position.x, ray[1].position.y };

            for (auto& line : linesVector)
            {
                intersect = lineIntersect(origin, dest, line.a, line.b);

                if (intersect.result)
                {
                    lineIntersects.push_back(intersect.pos);
                    nearestIntersect = getClosestIntersect(origin, lineIntersects);
                    ray[1].position = sf::Vector2f(nearestIntersect.x, nearestIntersect.y);
                }
            }

            lineIntersects.clear();
        }

        // Calculate the angle of each ray and store angle with vertex position in a struct
        // Can probably combine this loop with a previous loop
        for (auto& ray : rays)
        {
            VectorAngle vc;
            float angle = computeAngle(ray[0].position.x, ray[0].position.y, ray[1].position.x, ray[1].position.y);

            vc.angle = angle;
            vc.position = { ray[1].position.x, ray[1].position.y };

            vectorAngleContainer.push_back(vc);
        }

        // Sort vectorAngleContainer by angle size
        std::sort(vectorAngleContainer.begin(), vectorAngleContainer.end(), [](VectorAngle a, VectorAngle b)
            {
                return a.angle < b.angle;
            });

        // Create visibility polygon
        sf::VertexArray visibilityPolygon(sf::TriangleFan, vectorAngleContainer.size() + 1);
        for (int i = 0; i <= vectorAngleContainer.size(); i++)
        {
            if (i == 0)
            {
                visibilityPolygon[i] = ray[0].position;
                visibilityPolygon[i].color = sf::Color::Red;
                continue;
            }

            visibilityPolygon[i] = sf::Vertex(sf::Vector2f(vectorAngleContainer[i - 1].position.x, vectorAngleContainer[i - 1].position.y), sf::Color::Red);
        }
        visibilityPolygon[vectorAngleContainer.size()] = visibilityPolygon[1].position;
        visibilityPolygon[vectorAngleContainer.size()].color = sf::Color::Red;


        // Clear, draw, display        
        window.draw(boundry);
        window.draw(rect1);
        window.draw(triangle);

        window.draw(visibilityPolygon);

        for (auto& r : rays)
        {
            window.draw(r);
        }

        window.display();
    }

    return 0;
}

nortski said:
I create to additional rays that are offset either side of the main ray by 0.0001 radians.

Oh, that's neat. Although i guess you could spare the ray at the center, so just two rays instead 3 per vertex.

Eventually the problem comes from the intersection of the angular range traced per vertex. Although the range is just 0.0002, it could still intersect with another range. But i guess it should work even then.

My first guess is this: When calculating the angle, you have some direction representing angle zero.
Maybe your algorithm currently only works if this direction is either inside or outside a triangle.
That's quite likely.
To test this, you could rotate the sorted array of rays by one. Then the cases which formerly did not work would work, and vice versa.
If so, we only need to think about a proper test to tell which option to choose, which i have no idea about in the moment.

JoeJ said:

To test this, you could rotate the sorted array of rays by one.

Could you explain what you mean by this please? As well as learning to make games, I'm learning programming at the same time lol

Rotation means to change array contents ABCD to BCDA.
There is a std::rotate() function which works for std::vector, iirc.

@JoeJ Ah gotcha.
So I just did this and it appears that the affected triangle moved one position.

I fail to imagine, but sounds promising.

I have thought about a strategy for debugging:

Ignore the ‘center’ ray to a vertex right now. Not for the speedup, but to make the problem simpler. So, adding only the rotated ‘left and right rays’ to the array for sorting. (ray2 and ray3 in your code)

For each ray also store a unique id from the edge it hits.

After the rays are sorted, iterate the array to classify the segments between two rays.
I talked about ‘inside or outside’, but this makes no sense here.
Instead we have ‘edge segments and vertex segments’. If two adjacent rays in the sorted list have the same edge id, it's a edge segment. Otherwise it's a vertex segment.

Depending on that, draw the triangles either red or green, and draw the triangle from the very first segment in the sorted list in a lighter red or green.
Then you should see if the problem only happens if the first segment is a vertex segment for example.
Eventually rotating the array only in this case would already solve the problem. (Try also to rotate in the other direction)

Maybe you have also forgotten to duplicate the first ray, so it forms both the first and the last triangle.
And maybe you did not see that because vertex segments are very narrow, so it only shows on edge segments.

Finally, i would temporarily increase the rotation angle for better visual feedback on debugging, and to make related special cases more likely to happen. It should help to figure out how robust the current algorithm is.
After it works, you can make it as small as possible, to compensate for the loss of accuracy from ignoring the center ray.