c++ - 快速射线和多边形相交

Question

我正在编写我自己的小游戏，它应该具有所描述的可见性效果 here .我的世界由多边形组成，每个多边形都有一个边列表(按 CW 排序)。我现在想要(如文章中所述)将光线转换到多边形的边缘，找到交点并检索定义可见区域的多边形。

所以我为 vector 、点、边和多边形编写了一个类，并调整了交集算法，使其适用于我的代码。

然后我对其进行了测试，一切正常，但是当我在 for 循环中运行交集算法以模拟大量已处理的边(从 100 开始，直到 1000)时，fps 急剧下降，“只有 100 个边” “300fps(之前是 3000)，我认为 300 时它下降到 60 以下。这对我来说似乎是一个很大的下降，因为我想为我的光源重用这个代码然后我想我会很快想出超过 300 个边的处理方式并且它应该在功能较弱的处理器上运行得很快(我有一个至强 e1230v3)。

我发现仅调用 EdgeIntersection 程序运行速度快很多倍，但我确实需要遍历多边形中的边，所以这不是选择。

我的源代码:

Vector.h/.cpp:具有两个 float (X，Y)、getters&setters、旋转的基本 Vector 类

Vertex.h/.cpp:具有位置 vector 、getters 和 setters 以及指示它是否为交点顶点的 bool 值的基本点类

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

多边形.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);
};
}

雷.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()。我知道当我必须级联我的 getter 和 setter 时，我的代码会变得非常困惑，我必须解决这个问题，但对于其余部分，我希望一切都是可以理解的，如果不能随意询问。顺便提一下，我用顶点数组测试绘制我的对象，但我不需要相交过程的图形输出，我只需要可见的多边形。

只是再次指出:我需要一种更快的方法来找到射线和多边形之间的交点，因为我不知道我的代码是否做错了，所以我把它全部贴在这里，这样也许有人可以帮助我提高代码效率或向我展示解决问题的不同方法。

祝你有美好的一天，谢谢你的回答:)保罗

编辑:首先对我的多边形进行三角剖分然后进行射线-三角形相交测试会有意义地更快吗？

Answer 1

我无法谈论算法(这可能是您所需要的)，但有一些关于加速您所拥有的东西的直接想法。

首先，您可以定义所有您的getter 和setter 内联(将它们放在 header ，而不是单独的源文件)，以便编译器可以优化函数调用。

然后这些更改可能会为您购买一些框架:

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

我通过计算循环前的 0 项并从 1 开始循环，删除了一个 if 语句，剩下的只是缓存一个经常使用的值并避免 at() 速度较慢，因为它进行边界检查。