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

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

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

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

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

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

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, но мне не нужен графический вывод процесса пересечения, мне просто нужен видимый многоугольник.

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

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

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


c++ sfml polygon intersection raytracing
person sro5h    schedule 03.07.2015    source источник
comment
en.wikipedia.org/wiki/Bounding_volume_hierarchy   -  person Raxvan    schedule 03.07.2015
comment
Итак, лучший способ - разделить ограничивающую рамку каждого многоугольника на четыре части, а затем, если необходимо, разделить ее на части? Но я думаю, мне нужно разделить всю область, потому что луч также может пересекать разные многоугольники.   -  person sro5h    schedule 03.07.2015
comment
РЕДАКТИРОВАТЬ: основная утечка производительности, похоже, является ближайшей функцией пересечения, где мне нужно перебирать многоугольники ...   -  person sro5h    schedule 04.07.2015

Ответы (1)


arrow_upward
1
arrow_downward

Я не могу говорить с алгоритмом (который, возможно, вам нужен), но некоторые немедленные мысли по ускорению того, что у вас есть.

Во-первых, вы можете определить все ваши геттеры и сеттеры inline (поместите их в класс в заголовке, а не в отдельный исходный файл), чтобы компилятор может оптимизировать вызовы функций.

Тогда эти изменения могут дать вам несколько фреймов:

// 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;
}

Я удалил один из операторов if, вычислив элемент 0 перед циклом и запустив цикл с 1, остальное просто кэширует часто используемое значение и избегает at(), который работает медленнее, потому что он выполняет проверку границ.

person Galik    schedule 03.07.2015
comment
Ваш код сделал это лучше (+50 кадров в секунду), но все еще не очень хорошо :( - person sro5h; 04.07.2015