Fast Ray and Polygon Intersection

Question

I'm working on programming my own little game which should have a visibility effect as described here. My world consists of Polygons which each have a list of Edges (sorted CW). I now want (as described in the article) to cast Rays towards the Edges of the polygons, find the intersections and retrieve a Polygon that defines the visible area.

So I wrote a classes for Vectors, Points, Edges and Polygons and adjusted the intersection-algorithm so it works with my code.

I then tested it and everything worked fine, but as I ran the Intersection algorithm in a for-loop to simulate a large amount of Edges processed(starting with 100, until 1000) the fps dropped drastically, with 100 Edges "only" 300fps (3000 before), and with 300 it dropped below 60 i think. This seems to be way to much drop for me as i wanted to reuse this code for my Lightsources and then i think i would quickly come up with processing way more than 300 Edges and it should run fast on way less powerful processors(i got an xeon e1230v3).

I figured out that only calling the EdgeIntersection the program runs many times faster, but I definitely need to loop through the Edges in my polygons so this is no option.

My Source-Code:

Vector.h/.cpp: Basic Vector class with two floats(X,Y), getters&setters, rotating

Vertex.h/.cpp: Basic Point class with a Position Vector, getters&setters and a boolean that indicates whether it is a Intersection Vertex

Edge.h/.cpp Basic Edge class with start/end-Verticies, getters&setters and rotating function(uses Vector.rotate())

Polygon.h:

#pragma once
#include <vector>
#include "Edge.h"

namespace geo
{
class Polygon
{
private:
    std::vector<Edge> edges;

public:
    Polygon();
    Polygon(std::vector<Edge> edges);
    ~Polygon();

    std::vector<Edge> getEdges();
    Edge getEdge(int index);
    int getEdgeCount();

    void setEdges(std::vector<Edge> edges);
    void setEdge(Edge e, int index);
    void addEdge(Edge e);
    void removeEdge(int index);
};
}

Ray.h:

#pragma once
#include "Vertex.h"

class Ray
{
private:
    geo::Vertex origin;
    geo::Vector dir;

public:
    Ray();
    Ray(geo::Vertex origin, geo::Vector dir);
    ~Ray();

    geo::Vertex getOrigin();
    geo::Vector getDirection();

    void setOrigin(geo::Vertex origin);
    void setDirection(geo::Vector dir);
};

LightModule.h:

#pragma once
#include "Polygon.h"
#include "Ray.h"

class LightModule
{
private:
//List of blocking Polygons
std::vector<geo::Polygon>* blockingPolygons;
std::vector<Ray> rays;

geo::Polygon bounds;
geo::Polygon visible;
/*geo::Polygon blocked;*/

//HitDetection Class later
geo::Vertex getIntersection(Ray r, geo::Edge* e);
geo::Vertex getClosestIntersection(Ray r, geo::Polygon *p);
public:
LightModule();
LightModule(std::vector<geo::Polygon>* blockingPolygons);
~LightModule();

//Set the Blocking Polygons
void setBlockingPolygons(std::vector<geo::Polygon>* blockingPolygons);

geo::Vertex callCI(Ray r, geo::Polygon* p);
geo::Vertex callI(Ray r, geo::Edge* e);

//Cast Rays towards Vertecies and store them in rays
void updateRays();
//Update Visibility Polygon
void updateVisible();
//Return Visibility Polygon
geo::Polygon* getVisible();
};

LightMModule.cpp:

#include "LightModule.h"


LightModule::LightModule()
{
rays.clear();
}

LightModule::LightModule(std::vector<geo::Polygon>* blockingPolygons)
{
this->blockingPolygons = blockingPolygons;
rays.clear();
}

LightModule::~LightModule()
{
}

void LightModule::setBlockingPolygons(std::vector<geo::Polygon>* blockingPolygons)
{
this->blockingPolygons = blockingPolygons;
}

//Test-cast a Ray (will follow mouse in the Test)
void LightModule::updateRays()
{
Ray r(geo::Vertex(geo::Vector(200, 100)), geo::Vector(-100, 0));
rays.push_back(r);

}

void LightModule::updateVisible()
{

}

//Both for Testing will later be part of a seperate class
geo::Vertex LightModule::callCI(Ray r, geo::Polygon *p)
{
return this->getClosestIntersection(r, p);
}

geo::Vertex LightModule::callI(Ray r, geo::Edge* e)
{
return this->getIntersection(r, e);
}



//TEST

geo::Vertex LightModule::getIntersection(Ray r, geo::Edge* e)
{
geo::Vertex v;
v.setIntersectVert(false);

float r_px = r.getOrigin().getPosition().getX();
float r_py = r.getOrigin().getPosition().getY();
float r_dx = r.getDirection().getX();
float r_dy = r.getDirection().getY();

float s_px = e->getOrigin().getPosition().getX();
float s_py = e->getOrigin().getPosition().getY();
float s_dx = e->getDirection().getX();
float s_dy = e->getDirection().getY();

float r_mag = sqrt(r_dx*r_dx + r_dy*r_dy);
float s_mag = sqrt(s_dx*s_dx + s_dy*s_dy);

if (r_dx / r_mag == s_dx / s_mag && r_dy / r_mag == s_dy / s_mag)
{
    return v;
}

float T2 = (r_dx*(s_py - r_py) + r_dy*(r_px - s_px)) / (s_dx*r_dy - s_dy*r_dx);
float T1 = (s_px + s_dx*T2 - r_px) / r_dx;

if (T1 < 0 /*|| T1 > 1 For Lines*/)
{
    return v;
}
if (T2 < 0 || T2 > 1)
{
    return v;
}

v.setIntersectVert(true);
v.setPosition(geo::Vector(r_px + r_dx*T1, r_py + r_dy*T1));
return v;
}

geo::Vertex LightModule::getClosestIntersection(Ray r, geo::Polygon *p)
{
geo::Vertex v;
v.setIntersectVert(false);
geo::Vertex v_nearest(geo::Vector(0, 0));
v_nearest.setIntersectVert(false);

geo::Vector h1;
geo::Vector h2;

for (int i = 0; i < p->getEdges().size(); i++)
{
    v = this->getIntersection(r, &p->getEdges().at(i));
    h1.setX(v.getPosition().getX() - r.getOrigin().getPosition().getX());
    h1.setY(v.getPosition().getY() - r.getOrigin().getPosition().getY());
    h2.setX(v_nearest.getPosition().getX() - r.getOrigin().getPosition().getX());
    h2.setY(v_nearest.getPosition().getY() -                     r.getOrigin().getPosition().getY());

    if (i < 1)
        v_nearest = v;
    else if (v.isIntersectVert() == true && h1.getLength() < h2.getLength())
    {
        v_nearest = v;
    }
}
return v_nearest;
}

For the Testing i create a Polygon a LightModule and call updateRays and then call the helper-Function callCI(). I know my code gets pretty messy when i have to cascade my getters and setters, ill have to fix that but for the Rest i hope everything is understandable and if not feel free to ask. And just to have mentioned it, I Test-draw my Objects with Vertex-Arrays but I don't need Graphical output of the intersection process, i just need the visible polygon.

Just to point out again: I need a faster way of finding the Intersection-Point between a Ray and a Polygon and as I didn't know if i did something wrong in my code I posted it all here so someone can maybe help me making my code more efficient or show me a different method to solve my problem.

Have a nice day and thank you for your answers :) Paul

EDIT: Would it be meaningfully faster to first triangulate my polygons and then do a Ray-Triangle intersection Test?

Answer 1

I can't speak to the algorithm (which is possibly what you need) but some immediate thoughts on speeding up what you have.

First off you can define all your getters and setters inline (put them in the class in the header, not the separate source file) so the compiler can optimize the function calls away.

Then these changes might buy you a few frames:

// make sure your getters and setters are inline so the compiler
// can optimize them away
geo::Vertex LightModule::getClosestIntersection(Ray r, geo::Polygon* p)
{
    geo::Vertex v;
    v.setIntersectVert(false);
    geo::Vector h1;
    geo::Vector h2;

    // cache these
    Vector ray_position = r.getOrigin().getPosition();

    geo::Vertex v_nearest(geo::Vector(0, 0));
    v_nearest.setIntersectVert(false);

    // cache size (don't dereference each time)
    size_t size = p->getEdges().size();

    // avoid acces violation
    if(!size)
        return v_nearest;

    // preset item 0
    v_nearest = this->getIntersection(r, &p->getEdges()[0]);

    // start from 1 not 0
    for(int i = 1; i < size; i++)
    {
        // don't use at() its slower
        // v = this->getIntersection(r, &p->getEdges().at(i));
        v = this->getIntersection(r, &p->getEdges()[i]);

        // used cached ray position rather than call functions
        h1.setX(v.getPosition().getX() - ray_position.getX());
        h1.setY(v.getPosition().getY() - ray_position.getY());

        h2.setX(v_nearest.getPosition().getX() - ray_position.getX());
        h2.setY(v_nearest.getPosition().getY() - ray_position.getY());

        // this if not needed because presetting item 0
        //if(i < 1)
        //  v_nearest = v;
        if(v.isIntersectVert() == true && h1.getLength() < h2.getLength())
        {
            v_nearest = v;
        }
    }
    return v_nearest;
}

I removed one of the if statements by calculating the 0 item before the loop and starting the loop from 1, the rest is just caching a much used value and avoiding at() which is slower because it does bound-checking.