4

我想在 2 个班级之间建立联系，但我不确定什么是最好的方法。我拥有的是一组点，我使用 delaunay 三角剖分在它们之间找到三角形（请注意，一个点可以属于多个三角形）。接下来，在视频的几帧中跟踪和更新这些点的位置。因此，三角形的位置也需要以某种方式更新。除此之外，我还希望能够删除丢失的点并自动删除与其关联的三角形。你们能给我一些建议如何结合这些课程吗？

class Point  
{ 
  float x,y;
}

class Triangle
{
  Point p1, pt2, pt3;
}
4

5 回答 5

1

您可能会使用以下数据结构：

struct Point
{
    double x, y;
};

struct Triangle
{
    unsigned int ids[3];
    bool isValid;
};

// Store points for each frame
std::vector<std::vector<Point>> points;
// Store triangles
std::vector<Triangle> triangles;

您还可以像这样为每个帧保留所有三角形：

// Store triangles for each frame
std::vector<std::vector<Triangle>> triangles;

这是一个“工作示例”。3 帧期间 4 个点，2 个三角形。它只输出顶点都是正的三角形。从一帧到另一帧，点云沿 Y 轴平移 -1。这显然是一个假测试，但它希望能帮助你开始。

#include <vector>
#include <iostream>

struct Point
{
    double x, y;
};

struct Triangle
{
    unsigned int ids[3];
    bool isValid;
};

void TrackFirstFrame(std::vector<Point> &firstFrame)
{
    Point p1, p2, p3, p4;
    p1.x = 1; p1.y = 0;
    p2.x = 2; p2.y = 1;
    p3.x = 1; p3.y = 2;
    p4.x = 0; p4.y = 1;
    firstFrame[0] = p1;
    firstFrame[1] = p2;
    firstFrame[2] = p3;
    firstFrame[3] = p4;
}

void Delaunay(const std::vector<Point> &points, std::vector<Triangle> &triangles)
{
    Triangle t1;
    t1.ids[0] = 0;
    t1.ids[1] = 1;
    t1.ids[2] = 3;
    triangles.push_back(t1);

    Triangle t2;
    t2.ids[0] = 1;
    t2.ids[1] = 2;
    t2.ids[2] = 3;
    triangles.push_back(t2);
}

// Assumption: all previous frame points give a new tracked point for current frame 
void TrackFrame(const std::vector<Point> &previousFramePoints, unsigned int currentFrame, std::vector<Point> &trackedPoints)
{
    for (unsigned int i = 0; i < previousFramePoints.size(); ++i)
    {
        Point previousPoint = previousFramePoints[i];
        Point trackedPoint;
        trackedPoint.x = previousPoint.x;
        trackedPoint.y = previousPoint.y - 1;
        trackedPoints[i] = trackedPoint;
    }
}

// Assumption: all vertices are positive. If not, triangle is invalid
void UpdateTriangles(const std::vector<Point> &points, std::vector<Triangle> &triangles)
{
    std::vector<Triangle>::iterator trianglesIT = triangles.begin();
    for (; trianglesIT != triangles.end(); ++trianglesIT)
    {
        (*trianglesIT).isValid = true; // By default
        for (unsigned int i = 0; i < 3; ++i)
        {
            Point vertex = points[(*trianglesIT).ids[i]];
            if (vertex.x < 0 || vertex.y < 0)
            {
                (*trianglesIT).isValid = false;
                break;
            }
        }
    }
}

void PrintPoints(const std::vector<Point> &points)
{
    std::cout<<"Points"<<std::endl;
    std::vector<Point>::const_iterator pointsIT = points.begin();
    for (; pointsIT != points.end(); ++pointsIT)
    {
        std::cout<<"("<<pointsIT->x<<", "<<pointsIT->y<<")"<<std::endl;
    }
}

void PrintTriangles(const std::vector<Triangle> &triangles)
{
    std::cout<<"Triangles"<<std::endl;
    std::vector<Triangle>::const_iterator trianglesIT = triangles.begin();
    for (; trianglesIT != triangles.end(); ++trianglesIT)
    {
        if (trianglesIT->isValid)
        {
            std::cout<<"["<<trianglesIT->ids[0]<<", "<<trianglesIT->ids[1]<<", "<<trianglesIT->ids[2]<<"])"<<std::endl;
        }
    }
}

int main()
{
    unsigned int nbFrames = 3;
    unsigned int nbPoints = 4;

    // Init 2D points
    std::vector<std::vector<Point>> points;
    points.resize(nbFrames);
    std::vector< std::vector<Point> >::iterator framesIT = points.begin();
    for (; framesIT != points.end(); ++framesIT)
    {
        framesIT->resize(nbPoints);
    }

    TrackFirstFrame(points[0]);
    std::cout<<"Frame 0"<<std::endl;
    PrintPoints(points[0]);

    // Init triangles with Delaunay. 4 points => 2 triangles;
    std::vector<Triangle> triangles;
    Delaunay(points[0], triangles);
    PrintTriangles(triangles);

    for (unsigned int i = 1; i < nbFrames; ++i)
    { 
        std::cout<<"Track frame #"<<i<<std::endl;
        TrackFrame(points[i-1], i, points[i]);
        PrintPoints(points[i]);
        UpdateTriangles(points[i], triangles);
        PrintTriangles(triangles);
    }

    char c;
    std::cin >> c;
}
于 2013-07-08T12:55:49.003 回答
1

计算机图形中的此类集合交互通常使用索引来实现。

class Point
{ 
  float x,y;
}

class Triangle
{
  unsigned int indices[3]; // indices in std::vector<Points>
}

std::vector<Points> points;
std::vector<Triangle> triangles;

与指针解决方案相比，主要优点是您可以在着色器程序中使用此类索引引用。

编辑： 通过已知索引删除顶点的代码示例（未测试）。请注意，现在我们将顶点存储在 std::map 中，以便在擦除索引时不会破坏索引。

class Mesh
{
public:
    struct Vertex
    {
        float x, y;
    };

    struct Triangle
    {
        bool Contains(unsigned int index) const 
        { 
            return ((indices[0] == index) || (indices[1] == index) || (indices[2] == index));
        }

        unsigned int indices[3];
    };

    // Removes vertex and corresponding triangles
    void RemoveByIndex(unsigned int index)
    {
        for (auto it = triangles.begin(); it != triangles.end(); ++it)
        {
            if (it->Contains(index))
                triangles.erase(it);
        }

        vertices.erase(index);
    }

private:
    std::map<unsigned int, Vertex> vertices;
    std::vector<Triangle> triangles;
};

当然，还有很大的优化空间：首先是容器的类型，但这取决于集合的大小，以及插入/擦除数据的频率。

于 2013-07-08T10:09:45.010 回答
1

@slava 指的是您说一个点可以属于多个三角形的事实。考虑到这一点，您的课程应如下所示：

class Point  
{ 
  float x,y;
}

class Triangle
{
  Point * p1;
  Point * pt2;
  Point * pt3;
}

按照您定义 Triangle 类的方式，您将随身携带点的副本。如果点已被修改，您的 Triangle 类将不得不单独更新。

请记住，这些不是文字类定义（一切都是私有的），并且您可能希望使用像 unique_ptr 这样的引用计数指针

于 2013-07-08T08:48:18.563 回答
0

我认为您需要一些东西来删除（或添加）三角形。我的代码有点像

std::vector<Triangle> update_triangles(const std::vector<Point> & points)
{
//...
}

此代码将重新找到新点集合的德劳内三角形。这可能会被证明很慢，并且您可能会使用一些聪明的算法来加速它。

于 2013-07-08T09:03:56.267 回答
0

三角形不应该包含点而是指向点的指针，因为点存在于三角形之外。此外，在每个点中保留相关三角形列表（当然是指针列表）可能会很方便，但这实际上取决于使用情况。

于 2013-07-08T08:39:36.533 回答