Быстрое пересечение лучей и полигонов

Я работаю над программированием собственной маленькой игры, которая должна иметь эффект видимости, как описано Вот. Мой мир состоит из полигонов, каждый из которых имеет список краев (отсортированный CW). Теперь я хочу (как описано в статье) привести лучи к краям многоугольников, найти пересечения и получить многоугольник, который определяет видимую область.

Поэтому я написал классы для Векторов, Точек, Краев и Полигонов и настроил алгоритм пересечения, чтобы он работал с моим кодом.

Затем я проверил его, и все заработало нормально, но когда я запустил алгоритм пересечения в цикле for для имитации большого количества обработанных краев (начиная со 100 до 1000), fps резко упал, при 100 Edges «only» 300fps ( 3000 раньше), а с 300 он упал ниже 60 я думаю. Похоже, что для меня это намного проще, так как я хотел бы повторно использовать этот код для моих источников света, и тогда я думаю, что я бы быстро придумал способ обработки более чем 300 Edges, и он должен работать быстрее на менее мощных процессорах (я получил xeon e1230v3).

Я понял, что только вызывая EdgeIntersection, программа запускается во много раз быстрее, но мне определенно нужно перебрать края в моих полигонах, так что это не вариант.

Мой исходный код:

Vector.h / .cpp: базовый класс Vector с двумя числами с плавающей запятой (X, Y), геттерами&сеттеры, вращающиеся

Vertex.h / .cpp: класс базовой точки с вектором позиции, геттеры&сеттеры и логическое значение, указывающее, является ли это вершина пересечения

Edge.h / .cpp Базовый класс Edge с начальной / конечной вершинами, геттерами&сеттеры и вращающаяся функция (использует 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;
}

Для тестирования я создаю полигон LightModule и вызываю updateRays, а затем вызываю вспомогательную функцию callCI ().
Я знаю, что мой код становится довольно запутанным, когда мне приходится каскадировать мои геттеры и сеттеры, я должен это исправить, но для остальных я надеюсь, что все понятно и, если нет, не стесняйтесь спрашивать. И чтобы упомянуть об этом, я тестирую свои объекты с помощью Vertex-Arrays, но мне не нужен графический вывод процесса пересечения, мне просто нужен видимый многоугольник.

Еще раз хочу отметить: мне нужен более быстрый способ найти точку пересечения между лучом и многоугольником, и, поскольку я не знал, сделал ли я что-то не так в своем коде, я разместил все это здесь, чтобы кто-то мог помочь мне сделать мой код более эффективен или покажи мне другой метод для решения моей проблемы.

Хорошего дня и спасибо за ваши ответы 🙂
Павел

РЕДАКТИРОВАТЬ: Было бы значительно быстрее сначала триангулировать мои полигоны, а затем выполнить тест пересечения Луч-Треугольник?