三维网格表示

网格有哪些数据结构

网格的数据结构其实就是一个图结构:点,边,面。可以是有向图,比如半边结构,也可以是无向图。在不同的软件或者开发包里,网格数据结构的实现都是有差异的。这种差异主要体现在网格连接关系的记录结构上,比如顶点是否记录邻域点,边,面信息,边是否记录邻域面信息等。记录的信息越多,查询的时候越方便,但是冗余的信息也越多,如果网格连接关系有变动,维护的信息也越多。另外,这些关系的建立也是需要开销的。所以,没有最好的数据结构,只有最适合当前算法的数据结构。

在Geometry++里,ITriMesh用于表达网格数据结构。Geometry++的网格算法都是基于ITriMesh接口来调用的,具体如下:

    class GPP_EXPORT ITriMesh
    {
    public:
        ITriMesh(){}

        virtual Int GetVertexCount(void) const = 0;
        virtual Int GetTriangleCount(void) const = 0;

        virtual Vector3 GetVertexCoord(Int vid) const = 0;
        virtual void SetVertexCoord(Int vid, const Vector3& coord) = 0;
        virtual Vector3 GetVertexNormal(Int vid) const = 0;
        virtual void SetVertexNormal(Int vid, const Vector3& normal) = 0;

        virtual void GetTriangleVertexIds(Int fid, Int vertexIds[3]) const = 0;
        virtual void SetTriangleVertexIds(Int fid, Int vertexId0, Int vertexId1, Int vertexId2) = 0;
        virtual Vector3 GetTriangleNormal(Int fid) const = 0;
        virtual void SetTriangleNormal(Int fid, const Vector3& normal) = 0;
        virtual Int InsertTriangle(Int vertexId0, Int vertexId1, Int vertexId2) = 0;
        virtual Int InsertVertex(const Vector3& coord) = 0;
        
        virtual void SwapVertex(Int vertexId0, Int vertexId1) = 0; 
        virtual void PopbackVertices(Int popCount) = 0;
        virtual void SwapTriangles(Int fid0, Int fid1) =0;
        virtual void PopbackTriangles(Int popCount) = 0;

        virtual void UpdateNormal(void) = 0;
        virtual void Clear(void) = 0;

        virtual ~ITriMesh(){};
    };

ITriMesh是一个抽象类,不能直接使用。用户可以继承这个接口类,实现其成员函数。这样设计的一个好处是,用户无需改变自己已有的数据结构,只要实现了这个接口类,就可以调用Geometry++里所有关于网格的算法了。真正体现了即插即用的特点。比如用户已经有了一个三角网格类MyTriMeshData,则我们可以定义一个类MyTriMesh,并用它来调用Geometry++里的各种网格算法:

    class MyTriMesh : public ITriMesh
    {
        MyTriMeshData* mData;
        MyTriMesh(MyTriMeshData* data) : mData(data) 
        {}
        virtual Int GetVertecCount() const 
        { 
            return mData->GetVertecCount(); 
        }
        virtual Vector3 GetVertexCoord(Int vid) const 
        { 
            return mData->GetVertexCoord(); 
        }
        virtual void SetVertexCoord(Int vid, const Vector3& coord) 
        { 
            mData->SetVertexCoord(vid, coord[0], coord[1], coord[2]); 
        }
        virtual Int InsertVertex(const Vector3& coord) 
        { 
            mData->InsertVertex(coord); 
            return insertVertexId; 
        }
        // 其它成员函数类似
    };

    MyTriMesh triMesh(myTriMeshData); // 用自己的三角网格数据初始化MyTriMesh
    ErrorCode res = ConsolidateMesh::LaplaceSmooth(triMesh, 0.2, 5, true); // 调用网格算法API来修改自己的网格数据
    res = ConsolidateMesh::MakeTriMeshManifold(triMesh);

关于Geometry++三角网格更详细的介绍,可以参考开发文档里的 三角网格表示


半边结构好用吗

半边结构是网格数据结构的一种表达方式,它是一个有向图,把一条边表达为两个有向半边,如下图所示。它的优点在于网格信息的拾取非常方便,缺点是网格连接关系变动后,需要维护的信息也比较多。另外,半边结构表达的网格需要是流形结构,半边结构的构造也需要一定的时间开销。所以,一般场合我们都使用ITriMesh这类简单的网格表达方式。关于半边结构更详细的介绍,可以参考开发文档里的 半边结构

hafl edge structure

网格有哪些属性

三角网格可以看作是一个图结构,由顶点,边和面(三角片)三个元素组成。网格的常见属性也由这三个元素的属性来表达。


网格顶点属性

顶点的几何属性通常可以表示为:

    struct VertexInfo
    {
        Vector3 mCoord;
        Vector3 mNormal;
    };

除此之外,它还有一些其它的属性:

  • 邻域:邻顶点,邻边,邻面
  • 流形:如果顶点的邻域是一个单连同区域,则这点为流形结构
  • colorId:对于一个彩色顶点网格,每个顶点有一个颜色值。如果这个网格是多个角度的数据拼接而成,则每个角度的网格片往往存在色差。colorId用于记录这个色差信息:同一个colorId的顶点,可以认为是颜色相容的,没有色差。colorId属性用于去除顶点色差的功能里。

  • 网格边属性

    边的几何属性一般由对应端点的几何属性来表达,所以它通常由拓扑属性来表达:

        struct EdgeInfo
        {
            int mVertexId[2];
            std::vector< int > mFaceIds;
        };
    

    除此之外,它还有一些其它的属性:

  • 边界边:如果它的邻接面为1,则为边界上的边
  • 非流形边:如果它的邻接面个数 > 2,则为非流形边

  • 网格面属性

    面的常见表达方式为:

        struct TriangleInfo
        {
            Int mIndex[3];
            Vector3 mNormal;
        };
    

    其中mIndex为三角片的顶点索引,mNormal为三角片的法线。三角片的属性其实用的并不多,它常见的属性是面点属性。所谓面点,即三角片的三个顶点。需要注意的是,面点和顶点的概念是不同的。下面是一些常见的面点属性:

  • 面点法线:它和顶点法线是不一样的概念。比如特征尖锐的区域,可以设置面点法线为面法线;在光滑区域,设置面点法线为顶点法线。
  • 纹理坐标:纹理坐标是一个典型的面点属性。严格来讲,顶点并没有纹理坐标的概念,只有三角形有纹理坐标的概念。网格UV展开到平面的时候,如果没有割缝产生,那么每个顶点在其相邻三角形内的纹理坐标都是一样的,故可简称为顶点的纹理坐标。如果有割缝产生,割缝处的顶点在不同三角形内的纹理坐标是不一样的。这时,顶点和纹理坐标是一对多的关系。其实,UV展开在UV域生成了一个二维网格,UV域的网格的顶点和原始网格的面点是一一对应的。所以,从这个角度来看SimplifyWithTextureCoords,它其实是对UV域的网格做了保持边界的QuadricSimplify操作。
  • 点像对应:点像对应信息用于纹理贴图,它的含义是三角片的面点在图像中的对应。它的概念和纹理坐标是类似的,都是网格到二维区域的一个映射。点像对应信息在图像域也映射出了一个二维网格。和UV展开的区别在于,UV展开的二维域是唯一的,而点像对应的二维域(图像),有可能有多个(多张图片)。这导致某些三角片的面点可能对应于不同的图像域。对于这类三角片的纹理贴图,一般采用面点颜色插值。
  • 注意:虽然点像对应是一个面点属性,Magic3D里的点像对应采用的却是顶点属性的表达方式,其主要原因是,网格的点像对应信息是从点云的点像对应映射过来的,所以可以认为每个顶点对应于一个像素。

  • 网格法线计算

    网格的法线可以分为三类:面法线,顶点法线,面点法线。

  • 面法线:可以通过面的两条边做外积叉乘得到面法线
  • 顶点法线:可以加权平均顶点的面邻域法线
  • 面点法线:它代表了面里的顶点,而不是网格顶点,它与网格顶点是多对一的关系。比如正方体的一个角点,它有三个垂直的相邻面,面点法线可以取对应的面法线,而顶点法线则明显区别于这类面点法线。面点法线不是很常用。
  • 看似简单的法线计算,要得到稳定的计算结果,需要考虑一些退化的情况。比如网格内有面退化的时候,该如何处理呢?