Basic Geometry Library

BGL (Basic Geometry Library) 是一个关于三维数据(点云,网格)处理的基础几何库。它包含了三维数据处理最基础的数据结构。用户可以很方便的使用它来开发各种几何相关的算法。

它可以免费的,无限制的使用,包括科研,商业产品等。


使用简介

1. 头文件: 所有的头文件都在include文件夹里, 设置好头文件包含路径, 在使用api的源文件里包含BGL.h

2. 库: 设置好对应版本动态链接库的路径. 如果是Windows平台,需要在预处理里定义宏BGL_DLL_EXPORT,WIN32


IPointCloud

通用的点云数据表示接口类. 它包含了最基础,最常用的点云操作接口。

    // IPointCloud.h
    class BGL_EXPORT IPointCloud
    {
    public:
        IPointCloud(){}

        virtual Int GetPointCount() const = 0;

        virtual Vector3 GetPointCoord(Int pid) const = 0;
        virtual void SetPointCoord(Int pid, const Vector3& coord) = 0;
        
        virtual bool HasNormal() const = 0;
        virtual void SetHasNormal(bool has) = 0;
        virtual Vector3 GetPointNormal(Int pid) const = 0;
        virtual void SetPointNormal(Int pid, const Vector3& normal) = 0;
        
        virtual bool HasColor(void) const = 0;
        virtual void SetHasColor(bool has) = 0;
        virtual Vector3 GetPointColor(Int pid) const = 0;
        virtual void SetPointColor(Int pid, const Vector3& color) = 0;
        
        // Return inserted point id
        virtual Int InsertPoint(const Vector3& coord) = 0;
        // Return inserted point id
        virtual Int InsertPoint(const Vector3& coord, const Vector3& normal) = 0;
        
        virtual void SwapPoint(Int pointId0, Int pointId1) = 0; 
        virtual void PopbackPoints(Int popCount) = 0;
        virtual void Clear(void) = 0;

        virtual ~IPointCloud(){}
    };

用法:继承这个接口类,实现其成员函数。BGL的PointCloud是IPointCloud的一个实现,可以直接拿来用。

接口类的优点:使用接口类实现算法,用户只需要实现这个接口类,就可以调用所有相关的算法。在实际工程中,点云往往有各种不同的数据结构表示,用户不需要为每一个数据结构都去实现一遍算法。就好比用户面向OpenGL编程,显卡的硬件实现,可以是N卡,也可以是A卡。

用法说明:

  • 假设用户表示点云数据的类为MyPointCloudData, 则可以定义一个类MyPointCloud
  •     class MyPointCloud : public IPointCloud
        {
            MyPointCloudData* mData;
            MyPointCloud(MyPointCloudData* data) : mData(data) 
            {}
            virtual Int GetPointCount() const
            { 
                mData->GetPointCloud(); 
            }
            virtual Vector3 GetPointCoord() const 
            { 
                mData->GetPointCoord(); 
            }
            virtual void SetPointCoord(Int pid, const Vector& coord) 
            { 
                mData->SetPointCoord(pid, coord[0], coord[1], coord[2]); 
            }
            // 其它成员函数类似
        };
    
        MyPointCloud pointCloud(myPointCloudData); // 用自己的点云数据初始化MyPointCloud
        ErrorCode res = LaplaceSmooth(pointCloud); // 调用点云算法API来修改自己的点云数据
        res = CalculatePointCloudNormal(pointCloud);
        // 其它点云算法API的具体用法可以参考相应模块的介绍
    
  • 构造点云:通过InsertPoint不断的往点云里加点.
  •     IPointCloud* pointCloud = new PointCloud;
        for (int pid = 0; pid < pointSize; pid++)
        {
            pointCloud->InsertPoint(pointCoords.at(pid));
            /* If pointCloud has Normal information
            pointCloud->InsertPoint(pointCoords.at(pid), pointNormals.at(pid));
            */
        }
    
  • 点云顶点的存储格式是线性的,获取方便,但是删除会存在一些效率问题. IPointCloud提供了SwapPoint函数把需要删除的元素交换到尾部,然后再通过PopbackPoints删除尾部元素。下面是一个删除点云点的示例:
  •     // BglToolPointCloud.h
        // deleteIndex could have duplicate index
        // originPointIds->at(pid_AfterDelete) = pid_OriginId
        ErrorCode DeletePointCloudElements(IPointCloud* pointCloud, const std::vector< Int >& deleteIndex, std::vector< Int >* originPointIds)
        {
            if (pointCloud == NULL )
            {
                return GPP_INVALID_INPUT;
            }
            Int pointCount = pointCloud->GetPointCount();
            if (originPointIds)
            {
                originPointIds->resize(pointCount);
                for (Int pid = 0; pid < pointCount; pid++)
                {
                    originPointIds->at(pid) = pid;
                }
            }
            if (deleteIndex.empty())
            {
                return GPP_NO_ERROR;
            }
            std::vector< bool > validFlag(pointCount, 1);
            for (std::vector< Int >::const_iterator itr = deleteIndex.begin(); itr != deleteIndex.end(); ++itr)
            {
                validFlag.at(*itr) = 0;
            }
            Int validDeleteCount = 0;
            for (Int pid = 0; pid < pointCount; pid++)
            {
                if (!validFlag.at(pid))
                {
                    validDeleteCount++;
                }
            }
            Int nonNullId = -1;
            for (Int pid = pointCount - 1; pid >= 0; pid--)
            {
                if (validFlag.at(pid))
                {
                    nonNullId = pid;
                    break;
                }
            }
            if (nonNullId == -1)
            {
                pointCloud->PopbackPoints(pointCount);
                if (originPointIds)
                {
                    originPointIds->clear();
                }
                return GPP_NO_ERROR;
            }
            for (Int pid = 0; pid <= nonNullId; pid++)
            {
                if (!validFlag.at(pid))
                {
                    pointCloud->SwapPoint(pid, nonNullId);
                    if (originPointIds)
                    {
                        Int tempId = originPointIds->at(pid);
                        originPointIds->at(pid) = originPointIds->at(nonNullId);
                        originPointIds->at(nonNullId) = tempId;
                    }
                    validFlag.at(nonNullId) = 0;
                    validFlag.at(pid) = 1;
                    nonNullId--;
                    while (!validFlag.at(nonNullId))
                    {
                        nonNullId--;
                    }
                }
                if (!validFlag.at(pid))
                {
                    break;
                }
            }
            pointCloud->PopbackPoints(validDeleteCount);
            if (originPointIds)
            {
                originPointIds->erase(originPointIds->begin() + pointCount - validDeleteCount, originPointIds->end());
            }
            return GPP_NO_ERROR;
        }
    
  • Clear函数负责清除Point Coordinate, Point Normal, Point Color. 回到构造类初始化时的状态.
  • HasNormal, HasColor函数主要用意: 有时候点云创建后没有法线或者颜色信息,IPointCloud提供这些函数查询点云是否有可靠的法线或者颜色信息. SetHasNormal, SetHasColor函数可以设置点云是否有法线或者颜色信息

  • IGridPointCloud

    有序点云的数据结构接口,它继承于IPointCloud。

        // IGridPointCloud.h
        class BGL_EXPORT IGridPointCloud : public IPointCloud
        {
        public:
            IGridPointCloud() {}
    
            // Initialise all variables
            virtual void InitGrid(Int width, Int height) = 0;
            // Making valid grid bounding box as small as possible
            virtual void RemoveOuterBlankGrids(void) = 0;
            virtual bool HasGridTopology(void) const = 0;
    
            virtual Int GetWidth(void) const = 0;
            virtual Int GetHeight(void) const = 0;
            
            virtual bool IsGridValid(Int wid, Int hid) const = 0;
            virtual void InvalidateGrid(Int wid, Int hid) = 0;
    
            virtual Int GetGridPointId(Int wid, Int hid) const = 0;;
            virtual void GetPointGridId(Int pointId, Int& wid, Int& hid) const = 0;
            
            // If grid is valid: it will set grid coord 
            // If grid is invalid: it will make grid valid, and set its coord.
            virtual void SetGridCoord(Int wid, Int hid, const Vector3& coord) = 0;
            virtual Vector3 GetGridCoord(Int wid, Int hid) const = 0;
            
            // Grid should be valid and GridPointCloud should has normal
            virtual void SetGridNormal(Int wid, Int hid, const Vector3& normal) = 0;
            virtual Vector3 GetGridNormal(Int wid, Int hid) const = 0;
    
            virtual void SetGridColor(Int wid, Int hid, const Vector3& color) = 0;
            virtual Vector3 GetGridColor(Int wid, Int hid) const = 0;
            
            virtual ~IGridPointCloud() {}
        };
    

    有序点云是一个方阵,如图所示。点云按照方阵一行一行的,从左上角到右下角排列。相比IPointCloud,IGridPointCloud多了点云的位置连接关系信息。相关的计算可以更加快速。

    Grid Point Cloud

    用法说明:

  • 构造有序点云:首先通过InitGrid初始化有序点云,设置长宽。初始化的点云格点默认为invalid。然后通过SetGridCoord往点云里加点。与IPointCloud不同的是,它不能通过InsertPoint函数来加点,因为这个函数没有格点坐标信息。
  •     IGridPointCloud* pointCloud = new PointCloud;
        pointCloud->InitGrid(width, height);
        for (Int pid = 0; pid < pointCount; pid++)
        {
            pointCloud->SetGridCoord(xidList.at(pid), yidList.at(pid), coordList.at(pid));
        }
    
  • RemoveOuterBlankGrids:移出掉四周无效的点,并重新设置点云的长宽。如下图所示,原始点云变为了红色框内缩小长宽的有序点云。
  • RemoveOuterBlankGrids
  • SetGridCoord:为格点设置坐标。也可以通过此函数来向点云里加点,因为格点默认是invalid,设置坐标以后就valid
  • SetGridNormal:为格点设置法线信息。注意,此格点必须是valid
  • GetGridPointId:获取格点对应的有效格点的索引。若格点无效,则返回-1
  • GetPointGridId:获取有效格点对应的格点坐标
  • 导入导出:可以使用gbg和gtg格式的文件存储有序点云。

  • PointCloud

    PointCloud是IPointCloud接口类和IGridPointCloud接口类的一个实现,用户可以直接使用它来表示点云数据

    这是PointCloud的一个实现示例:

        // PointCloud.h
        Int PointCloud::GetPointCount() const
        {
            return mCoordList.size();
        }
    
        Vector3 PointCloud::GetPointCoord(Int pid) const
        {
            return mCoordList.at(pid);
        }
    
        void PointCloud::SetPointCoord(Int pid, const Vector3& coord)
        {
            mCoordList.at(pid) = coord;
        }
    
        bool PointCloud::HasNormal() const
        {
            return mHasNormal;
        }
        
        void PointCloud::SetHasNormal(bool hasNormal)
        {
            mHasNormal = hasNormal;
            if (mHasNormal && mNormalList.size() < mCoordList.size())
            {
                mNormalList.resize(mCoordList.size());
            }
        }
    
        Vector3 PointCloud::GetPointNormal(Int pid) const
        {
            if (mHasNormal)
            {
                return mNormalList.at(pid);
            }
            else
            {
                return Vector3(0, 0, 0);
            }
        }
    
        void PointCloud::SetPointNormal(Int pid, const Vector3& normal)
        {
            mNormalList.at(pid) = normal;
        }
    
        bool PointCloud::HasColor(void) const
        {
            return mHasColor;
        }
    
        void PointCloud::SetHasColor(bool has)
        {
            mHasColor = has;
            if (mHasColor && mColorList.size() < mCoordList.size())
            {
                mColorList.resize(mCoordList.size());
            }
        }
    
        Vector3 PointCloud::GetPointColor(Int pid) const
        {
            if (mHasColor)
            {
                return mColorList.at(pid);
            }
            else
            {
                return mDefaultColor;
            }
        }
    
        void PointCloud::SetPointColor(Int pid, const Vector3& color)
        {
            mColorList.at(pid) = color;
        }
    
        void PointCloud::ReservePoint(Int pointCount)
        {
            mCoordList.reserve(pointCount);
            if (mHasNormal)
            {
                mNormalList.reserve(pointCount);
            }
            if (mHasColor)
            {
                mColorList.reserve(pointCount);
            }
        }
    
        Int PointCloud::InsertPoint(const Vector3& coord)
        {
            mCoordList.push_back(coord);
            if (mHasNormal)
            {
                mNormalList.resize(mCoordList.size());
            }
            if (mHasColor)
            {
                mColorList.resize(mCoordList.size());
            }
            if (mIsGrid)
            {
                ClearGridTopologyInfo();
            }
            return mCoordList.size() - 1;
        }
    
        Int PointCloud::InsertPoint(const Vector3& coord, const Vector3& normal)
        {
            mCoordList.push_back(coord);
            mNormalList.push_back(normal);
            if (mHasColor)
            {
                mColorList.resize(mCoordList.size());
            }
            if (mIsGrid)
            {
                ClearGridTopologyInfo();
            }
            return mCoordList.size() - 1;
        }
    
        void PointCloud::SwapPoint(Int pointId0, Int pointId1)
        {
            Vector3 tempCoord = mCoordList.at(pointId0);
            mCoordList.at(pointId0) = mCoordList.at(pointId1);
            mCoordList.at(pointId1) = tempCoord;
            if (mHasNormal)
            {
                Vector3 tempNormal = mNormalList.at(pointId0);
                mNormalList.at(pointId0) = mNormalList.at(pointId1);
                mNormalList.at(pointId1) = tempNormal;
            }
            if (mHasColor)
            {
                Vector3 tempColor = mColorList.at(pointId0);
                mColorList.at(pointId0) = mColorList.at(pointId1);
                mColorList.at(pointId1) = tempColor;
            }
            if (mIsGrid)
            {
                Int gridIndex0 = mPoint2GridMap.at(pointId0);
                Int gridIndex1 = mPoint2GridMap.at(pointId1);
                mGrid2PointMap.at(gridIndex0) = pointId1;
                mGrid2PointMap.at(gridIndex1) = pointId0;
                mPoint2GridMap.at(pointId0) = gridIndex1;
                mPoint2GridMap.at(pointId1) = gridIndex0;
            }
        }
    
        void PointCloud::PopbackPoints(Int popCount)
        {
            Int pointCount = mCoordList.size();
            mCoordList.erase(mCoordList.begin() + pointCount - popCount, mCoordList.end());
            if (mHasNormal)
            {
                mNormalList.erase(mNormalList.begin() + pointCount - popCount, mNormalList.end());
            }
            if (mHasColor)
            {
                mColorList.erase(mColorList.begin() + pointCount - popCount, mColorList.end());
            }
            if (mIsGrid)
            {
                for (Int pid = 1; pid <= popCount; pid++)
                {
                    mGrid2PointMap.at(mPoint2GridMap.at(pointCount - pid)) = -1;
                }
                mPoint2GridMap.erase(mPoint2GridMap.begin() + pointCount - popCount, mPoint2GridMap.end());
            }
        }
    
        void PointCloud::InitGrid(Int width, Int height)
        {
            mGridWidth = width;
            mGridHeight = height;
            std::vector< Int >().swap(mPoint2GridMap);
            std::vector< Int >().swap(mGrid2PointMap);
            mGrid2PointMap.resize(width * height, -1);
            mIsGrid = true;
            std::vector< Vector3 >().swap(mCoordList);
            std::vector< Vector3 >().swap(mNormalList);
            std::vector< Vector3 >().swap(mColorList);
        }
    
        bool PointCloud::IsGridValid(Int wid, Int hid) const
        {
            return (mGrid2PointMap.at(hid * mGridWidth + wid) != -1);
        }
    
        void PointCloud::InvalidateGrid(Int wid, Int hid)
        {
            Int gridIndex = hid * mGridWidth + wid;
            if (mGrid2PointMap.at(gridIndex) != -1)
            {
                SwapPoint(mGrid2PointMap.at(gridIndex), mPoint2GridMap.size() - 1);
                PopbackPoints(1);
            }
        }
    
        Int PointCloud::GetGridPointId(Int wid, Int hid) const
        {
            return mGrid2PointMap.at(hid * mGridWidth + wid);
        }
    
        void PointCloud::GetPointGridId(Int pointId, Int& wid, Int& hid) const
        {
            wid = mPoint2GridMap.at(pointId) % mGridWidth;
            hid = mPoint2GridMap.at(pointId) / mGridWidth;
        }
    
        Vector3 PointCloud::GetGridCoord(Int wid, Int hid) const
        {
            return mCoordList.at(mGrid2PointMap.at(hid * mGridWidth + wid));
        }
    
        void PointCloud::SetGridCoord(Int wid, Int hid, const Vector3& coord)
        {
            Int gridIndex = hid * mGridWidth + wid;
            if (mGrid2PointMap.at(gridIndex) == -1)
            {
                mGrid2PointMap.at(gridIndex) = mPoint2GridMap.size();
                mPoint2GridMap.push_back(gridIndex);
                mCoordList.push_back(coord);
                if (mHasNormal)
                {
                    mNormalList.resize(mCoordList.size());
                }
                if (mHasColor)
                {
                    mColorList.resize(mCoordList.size());
                }
            }
            else
            {
                mCoordList.at(mGrid2PointMap.at(gridIndex)) = coord;
            }
        }
        
        Vector3 PointCloud::GetGridNormal(Int wid, Int hid) const
        {
            if (mHasNormal)
            {
                return mNormalList.at(mGrid2PointMap.at(hid * mGridWidth + wid));
            }
            else
            {
                return Vector3(0, 0, 0);
            }
        }
    
        void PointCloud::SetGridNormal(Int wid, Int hid, const Vector3& normal)
        {
            mNormalList.at(mGrid2PointMap.at(hid * mGridWidth + wid)) = normal;
        }
    
        Vector3 PointCloud::GetGridColor(Int wid, Int hid) const
        {
            if (mHasColor)
            {
                return mColorList.at(mGrid2PointMap.at(hid * mGridWidth + wid));
            }
            else
            {
                return mDefaultColor;
            }
        }
    
        void PointCloud::SetGridColor(Int wid, Int hid, const Vector3& color)
        {
            mColorList.at(mGrid2PointMap.at(hid * mGridWidth + wid)) = color;
        }
    
        bool PointCloud::HasGridTopology(void) const
        {
            return mIsGrid;
        }
    

    注意事项:

  • UnifyCoords的典型使用场景:在多帧点云使用过程中,如果对第一帧点云应用了前一个UnifyCoords,为了保持之后帧的点云做同样的平移缩放变换,可以用前一个UnifyCoords的返回值来设置这个UnifyCoords,使得每一帧的点云做同样的变换
  • 有序点云在调用了InsertPoint之后,会变成无序点云

  • 点云导入导出
    PointCloud* Parser::ImportPointCloud(std::string fileName);
    

    目前支持的文件格式:obj, asc,gbg,gtg. 用户也可以导入其它格式的点云数据, 只需要自己写一个Parser, 然后用导入的数据创建点云类(例如PointCloud)即可使用了

    fileName: 格式为path/xxx.obj, path/xxx.asc, path可以是绝对路径,也可以相对路径

    返回值: 如果导入失败则返回NULL


    void Parser::ExportPointCloud(std::string fileName, const IPointCloud* pointCloud);
    

    目前支持的文件格式:obj, asc, ply.

    fileName: 格式为path/xxx.obj, path/xxx.asc, path可以是绝对路径,也可以相对路径


    void Parser::ExportGridPointCloud(std::string fileName, const IGridPointCloud* pointCloud);
    

    目前支持的文件格式:gbg(二进制), gtg(文本).

    fileName: 格式为path/xxx.gbg, path/xxx.gtg, path可以是绝对路径,也可以相对路径


    点云工具箱

    BglToolPointCloud.h

    ErrorCode CalculatePointListDensity(const IPointList* pointList, Int neighborCount, Real& density);
    

    计算点云密度:计算每个点的neighborCount邻域点的平均距离。

    neighborCount > 0,值越大,density也越大

    返回值: 如果成功则返回GPP_NO_ERROR


    ErrorCode UniformSamplePointList(const IPointList* pointList, Int sampleCount, std::vector< Int >& sampleIndex, Int seedId = 0, Int quality = 0);
    

    均匀采样:采样结果分布均匀。

    pointList: 点列数据

    sampleCount: 采样的目标点数,点数应小于点云点的个数

    sampleIndex: 返回采样点的索引结果

    seedId: 采样种子点,不同的种子点得到的采样结果不一样

    quality: 采样质量,0-低质量,速度快;1-高质量,速度慢

    返回值: 如果成功则返回GPP_NO_ERROR


    ErrorCode GeometrySamplePointList(const IPointList* pointList, Int sampleCount, std::vector< Int >& sampleIndex, Real uniformWeight = 0.1, Int neighborCount = 9, Int seedId = 0, Int quality = 1, Real* planeRatio = NULL);
    

    几何采样:采样结果在几何特征明显的地方数量会多一些。

    pointList: 点列数据

    sampleCount: 采样的目标点数,点数应小于点云点的个数

    sampleIndex: 返回采样点的索引结果

    uniformWeight: 采样结果的均匀性,范围[0, 1]. 参数越大,均匀性越好.

    neighborCount: 点云邻域个数,主要用于计算几何特征. 默认参数为9,如果点云均匀性不好,可以提高此参数以获得更好的稳定性

    seedId: 采样种子点,不同的种子点得到的采样结果不一样

    quality: 采样质量,0-低质量,速度快;1-高质量,速度慢

    planeRatio:点云平面点个数与总点数的比值

    返回值: 如果成功则返回GPP_NO_ERROR


    ErrorCode GridSamplePointList(const IPointList* pointList, Real interval, std::vector< Int >& sampleIndex);
    

    格栅采样:根据点间距把空间分为一个一个的格子,每个格子采样一个点,并且使得采样的点云尽量均匀。

    pointList: 点列数据

    interval: 点间距

    sampleIndex: 返回采样点的索引结果

    返回值: 如果成功则返回GPP_NO_ERROR


    ErrorCode EstimateCameraDirection(const IPointCloud* depthData, const std::vector< Int >* sampleList, Vector3& cameraDir);
    

    估计深度相机方向。

    depthData: 深度点云数据,需要带法线

    sampleList: 采样的点云索引,如果输入值是NULL,则对所有点进行整体估计

    cameraDir: 深度相机方向,与点云法线相反

    返回值: 如果成功则返回GPP_NO_ERROR


    ITriMesh

    通用的三角网格数据表示接口类. 它包含了最基础,最常用的三角网格操作接口。

        // ITriMesh.h
        class BGL_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;
            // Sometimes, Mesh doesn't need vertex normal information
            virtual bool HasVertexNormal(void) const = 0;
    
            // vertexIds are in a consistent order in all connected triangles
            virtual void GetTriangleVertexIds(Int fid, Int vertexIds[3]) const = 0;
            // make sure vertexIdx are in a consistent order in its connected triangles
            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;
            // Sometimes, Mesh doesn't need triangular normal information
            virtual bool HasTriangleNormal(void) const = 0;
            
            // Return inserted triangle id
            virtual Int InsertTriangle(Int vertexId0, Int vertexId1, Int vertexId2) = 0;
            // Return inserted vertex id
            virtual Int InsertVertex(const Vector3& coord) = 0;
            
            // Be careful: if you swap vertex and popback them, then vertex index after the deleted vertices will be changed.
            // If you want to delete some vertices, please use api DeleteTriMeshVertex in BglToolMesh.h which is still developping.
            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;
            // Clear all geometry information to initial state
            virtual void Clear(void) = 0;
    
            virtual ~ITriMesh(){};
        };
    

    用法:继承这个接口类,实现其成员函数。BGL的TriMesh是ITriMesh的一个实现,可以直接拿来用。

    接口类的优点:与IPointCloud类似,使用接口类实现算法,用户只需要实现这个接口类,就可以调用所有相关的算法。在实际工程中,网格往往有各种不同的数据结构表示,用户不需要为每一个数据结构都去实现一遍算法。

    用法说明:

  • 假设用户表示三角网格数据的类为MyTriMeshData, 则可以定义一个类MyTriMesh:
  •     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);
        // 其它网格算法API的具体用法可以参考相应模块的介绍
    
  • 构建网格示例:
  •     for (GPP::Int vid = 0; vid < vertexCount; vid++)
        {
            triMesh->InsertVertex(vertexCoord[vid]);
        }
        for (GPP::Int fid = 0; fid < faceCount; fid++)
        {
            triMesh->InsertTriangle(triangleIndex[fid][0], triangleIndex[fid][1], triangleIndex[fid][2]);
        }
        triMesh->UpdateNormal();
    
  • 三角网格顶点和面的存储格式是线性的,获取方便,但是删除会存在一些效率问题. ITriMesh提供了SwapVertex(SwapTriangles) 函数把需要删除的元素交换到尾部,然后再通过PopbackVertices(PopbackTriangles)删除尾部元素。用户也可以直接调用BglToolMesh.h里的DeleteTriMeshVertices / DeleteTriMeshTriangles来删除顶点或者三角片。
  • 网格拓扑改变后,顶点和三角片所对应的属性如何相应的改变:这里的拓扑改变是指Swap**, Popback**函数。TriMesh在调用这类函数之后,顶点或三角片的顺序发生了变化。如果我们能知道变化后和变化前,顶点和三角片的对应,则可以其对应的属性就可以做相应的更新了。一般有两种思路:1. 属性属于网格的成员变量,则可以在Swap**, Popback**里做相应的属性更新,具体可以参考TriMesh的实现;2. 属性独立于网格存在,则用户可以在网格类里添加顶点和三角片的Id信息,并在Swap**, Popback**里做相应的Id更新,这样就可以得到改变后顶点或三角片与之前的对应信息了,下面是一个示例:
  •     void MyTriMesh::SwapVertex(Int vertexId0, Int vertexId1)
        {
            Int tempId = mVertexIds.at(vertexId0);
            mVertexIds.at(vertexId0) = mVertexIds.at(vertexId1);
            mVertexIds.at(vertexId1) = tempId;
        }
    
        void MyTriMesh::PopbackVertices(Int popCount)
        {
            mVertexIds.erase(mVertexIds.begin() + mVertexIds.size() - popCount, mVertexIds.end());
        }
    
        void MyTriMesh::SwapTriangles(Int fid0, Int fid1)
        {
            Int tempId = mTriangleIds.at(fid0);
            mTriangleIds.at(fid0) = mTriangleIds.at(fid1);
            mTriangleIds.at(fid1) = tempId;
        }
    
        void MyTriMesh::PopbackTriangles(Int popCount)
        {
            mTriangleIds.erase(mTriangleIds.begin() + mTriangleIds.size() - popCount, mTriangleIds.end());
        }
    
  • Clear函数负责清除Vertex Coordinate, Vertex Normal, Triangle Index, Triangle Normal. 回到构造类初始化时的状态.
  • UpdateNormal负责重新计算网格的顶点和三角面的法线信息.

  • TriMesh

    ITriMesh接口类的一个实现,用户可以直接使用它来表示网格数据

    这是TriMesh的一个实现示例:

        Int TriMesh::GetVertexCount() const
        {
            return mVertexCoordList.size();
        }
    
        Vector3 TriMesh::GetVertexCoord(Int vid) const
        {
            return mVertexCoordList.at(vid);
        }
    
        void TriMesh::SetVertexCoord(Int vid, const Vector3& coord)
        {
            mVertexCoordList.at(vid) = coord;
        }
    
        Vector3 TriMesh::GetVertexNormal(Int vid) const
        {
            return mVertexNormalList.at(vid);
        }
    
        void TriMesh::SetVertexNormal(Int vid, const Vector3& normal)
        {
            if (mVertexNormalList.empty())
            {
                mVertexNormalList.resize(mVertexCoordList.size());
            }
            mVertexNormalList.at(vid) = normal;
        }
    
        bool TriMesh::HasVertexNormal(void) const
        {
            return mHasVertexNormal;
        }
    
        Int TriMesh::GetTriangleCount() const
        {
            return mTriangleList.size();
        }
    
        void TriMesh::GetTriangleVertexIds(Int fid, Int vertexIds[3]) const
        {
            vertexIds[0] = mTriangleList.at(fid)->mIndex[0];
            vertexIds[1] = mTriangleList.at(fid)->mIndex[1]; 
            vertexIds[2] = mTriangleList.at(fid)->mIndex[2]; 
        }
    
        void TriMesh::SetTriangleVertexIds(Int fid, Int vertexId0, Int vertexId1, Int vertexId2)
        {
            mTriangleList.at(fid)->mIndex[0] = vertexId0;
            mTriangleList.at(fid)->mIndex[1] = vertexId1;
            mTriangleList.at(fid)->mIndex[2] = vertexId2;
        }
    
        Vector3 TriMesh::GetTriangleNormal(Int fid) const
        {
            return mTriangleNormalList.at(fid);
        }
    
        void TriMesh::SetTriangleNormal(Int fid, const Vector3& normal)
        {
            if (mTriangleNormalList.empty())
            {
                mTriangleNormalList.resize(mTriangleList.size());
            }
            mTriangleNormalList.at(fid) = normal;
        }
    
        bool TriMesh::HasTriangleNormal(void) const
        {
            return mHasTriangleNormal;
        }
    
        Vector3 TriMesh::GetVertexColor(Int vid) const
        {
            if (mHasVertexColor)
            {
                return mVertexColorList.at(vid);
            }
            else
            {
                return mDefaultColor;
            }
        }
    
        void TriMesh::SetVertexColor(Int vid, const Vector3& color)
        {
            mVertexColorList.at(vid) = color;
        }
    
        Vector3 TriMesh::GetVertexTexcoord(Int vid) const
        {
            return mVertexTexCoordList.at(vid);
        }
    
        void TriMesh::SetVertexTexcoord(Int vid, const Vector3& texcoord)
        {
            mVertexTexCoordList.at(vid) = texcoord;
        }
    
        Vector3 TriMesh::GetTriangleColor(Int fid, Int localVid) const
        {
            if (mHasTriangleColor)
            {
                return mTriangleColorList.at(fid * 3 + localVid);
            }
            else
            {
                return mDefaultColor;
            }
        }
        
        void TriMesh::SetTriangleColor(Int fid, Int localVid, const Vector3& color)
        {
            mTriangleColorList.at(fid * 3 + localVid) = color;
        }
    
        Vector3 TriMesh::GetTriangleTexcoord(Int fid, Int localVid) const
        {
            return mTriangleTexCoordList.at(fid * 3 + localVid);
        }
    
        void TriMesh::SetTriangleTexcoord(Int fid, Int localVid, const Vector3& texcoord)
        {
            mTriangleTexCoordList.at(fid * 3 + localVid) = texcoord;
        }
    
        Int TriMesh::InsertVertex(const Vector3& coord)
        {
            mVertexCoordList.push_back(coord);
            if (mHasVertexNormal)
            {
                mVertexNormalList.push_back(Vector3(0, 0, 0));
            }
            if (mHasVertexColor)
            {
                mVertexColorList.push_back(Vector3(0, 0, 0));
            }
            if (mHasVertexTexCoord)
            {
                mVertexTexCoordList.push_back(Vector3(0, 0, 0));
            }
            return (mVertexCoordList.size() - 1);
        }
        
        Int TriMesh::InsertVertex(const Vector3& coord, const Vector3& normal)
        {
            mVertexCoordList.push_back(coord);
            mVertexNormalList.push_back(normal);
            if (mHasVertexColor)
            {
                mVertexColorList.push_back(Vector3(0, 0, 0));
            }
            if (mHasVertexTexCoord)
            {
                mVertexTexCoordList.push_back(Vector3(0, 0, 0));
            }
            return (mVertexCoordList.size() - 1);
        }
    
        void TriMesh::SetHasVertexColor(bool has)
        {
            mHasVertexColor = has;
            if (mHasVertexColor && mVertexColorList.size() < mVertexCoordList.size())
            {
                mVertexColorList.resize(mVertexCoordList.size());
            }
        }
    
        bool TriMesh::HasVertexColor() const
        {
            return mHasVertexColor;
        }
    
        void TriMesh::SetHasVertexTexCoord(bool has)
        {
            mHasVertexTexCoord = has;
            if (mHasVertexTexCoord && mVertexTexCoordList.size() < mVertexCoordList.size())
            {
                mVertexTexCoordList.resize(mVertexCoordList.size());
            }
        }
    
        bool TriMesh::HasVertexTexCoord(void) const
        {
            return mHasVertexTexCoord;
        }
    
        void TriMesh::SetHasTriangleColor(bool has)
        {
            mHasTriangleColor = has;
            if (mHasTriangleColor && mTriangleColorList.size() < mTriangleList.size() * 3)
            {
                mTriangleColorList.resize(mTriangleList.size() * 3);
            }
        }
        
        bool TriMesh::HasTriangleColor(void) const
        {
            return (mHasTriangleColor && (mTriangleColorList.size() == mTriangleList.size() * 3));
        }
    
        void TriMesh::SetHasTriangleTexCoord(bool has)
        {
            mHasTriangleTexCoord = has;
            if (mHasTriangleTexCoord && mTriangleTexCoordList.size() < mTriangleList.size() * 3)
            {
                mTriangleTexCoordList.resize(mTriangleList.size() * 3);
            }
        }
    
        bool TriMesh::HasTriangleTexCoord(void) const
        {
            return mHasTriangleTexCoord;
        }
    
        Int TriMesh::InsertTriangle(Int vertexId0, Int vertexId1, Int vertexId2)
        {
            TriangleInfo* triangleInfo = new TriangleInfo(vertexId0, vertexId1, vertexId2);
            mTriangleList.push_back(triangleInfo);
            if (mHasTriangleNormal)
            {
                mTriangleNormalList.push_back(Vector3(0, 0, 0));
            }
            if (mHasTriangleTexCoord)
            {
                mTriangleTexCoordList.resize(mTriangleTexCoordList.size() + 3);
            }
            if (mHasTriangleColor)
            {
                mTriangleColorList.resize(mTriangleColorList.size() + 3);
            }
            return (mTriangleList.size() - 1);
        }
    
        void TriMesh::SwapVertex(Int vertexId0, Int vertexId1)
        {
            Vector3 temp = mVertexCoordList.at(vertexId0);
            mVertexCoordList.at(vertexId0) = mVertexCoordList.at(vertexId1);
            mVertexCoordList.at(vertexId1) = temp;
            if (mHasVertexNormal)
            {
                Vector3 normalTemp = mVertexNormalList.at(vertexId0);
                mVertexNormalList.at(vertexId0) = mVertexNormalList.at(vertexId1);
                mVertexNormalList.at(vertexId1) = normalTemp;
            }
            if (mHasVertexColor)
            {
                Vector3 tempColor = mVertexColorList.at(vertexId0);
                mVertexColorList.at(vertexId0) = mVertexColorList.at(vertexId1);
                mVertexColorList.at(vertexId1) = tempColor;
            }
            if (mHasVertexTexCoord)
            {
                Vector3 tempCoord = mVertexTexCoordList.at(vertexId0);
                mVertexTexCoordList.at(vertexId0) = mVertexTexCoordList.at(vertexId1);
                mVertexTexCoordList.at(vertexId1) = tempCoord;
            }
        }
    
        void TriMesh::PopbackVertices(Int popCount)
        {
            Int vertexCount = mVertexCoordList.size();
            mVertexCoordList.erase(mVertexCoordList.begin() + vertexCount - popCount, mVertexCoordList.end());
            if (mHasVertexNormal)
            {
                mVertexNormalList.erase(mVertexNormalList.begin() + vertexCount - popCount, mVertexNormalList.end());
            }
            if (mHasVertexColor)
            {
                mVertexColorList.erase(mVertexColorList.begin() + vertexCount - popCount, mVertexColorList.end());
            }
            if (mHasVertexTexCoord)
            {
                mVertexTexCoordList.erase(mVertexTexCoordList.begin() + vertexCount - popCount, mVertexTexCoordList.end());
            }
        }
    
        void TriMesh::SwapTriangles(Int fid0, Int fid1)
        {
            TriangleInfo* temp = mTriangleList.at(fid0);
            mTriangleList.at(fid0) = mTriangleList.at(fid1);
            mTriangleList.at(fid1) = temp;
            if (mHasTriangleNormal)
            {
                Vector3 normalTemp = mTriangleNormalList.at(fid0);
                mTriangleNormalList.at(fid0) = mTriangleNormalList.at(fid1);
                mTriangleNormalList.at(fid1) = normalTemp;
            }
            if (mHasTriangleTexCoord)
            {
                Int baseIndex0 = fid0 * 3;
                Int baseIndex1 = fid1 * 3;
                for (Int localId = 0; localId < 3; localId++)
                {
                    Vector3 tempCoord = mTriangleTexCoordList.at(baseIndex0 + localId);
                    mTriangleTexCoordList.at(baseIndex0 + localId) = mTriangleTexCoordList.at(baseIndex1 + localId);
                    mTriangleTexCoordList.at(baseIndex1 + localId) = tempCoord;
                }
            }
            if (mHasTriangleColor)
            {
                Int baseIndex0 = fid0 * 3;
                Int baseIndex1 = fid1 * 3;
                for (Int localId = 0; localId < 3; localId++)
                {
                    Vector3 tempCoord = mTriangleColorList.at(baseIndex0 + localId);
                    mTriangleColorList.at(baseIndex0 + localId) = mTriangleColorList.at(baseIndex1 + localId);
                    mTriangleColorList.at(baseIndex1 + localId) = tempCoord;
                }
            }
        }
    
        void TriMesh::PopbackTriangles(Int popCount)
        {
            Int faceCount = mTriangleList.size();
            for (Int fid = 0; fid < popCount; fid++)
            {
                GPPFREEPOINTER(mTriangleList.at(faceCount - 1 - fid));
            }
            mTriangleList.erase(mTriangleList.begin() + mTriangleList.size() - popCount, mTriangleList.end());
            if (mHasTriangleNormal)
            {
                mTriangleNormalList.erase(mTriangleNormalList.begin() + mTriangleNormalList.size() - popCount, mTriangleNormalList.end());
            }
            if (mHasTriangleTexCoord)
            {
                mTriangleTexCoordList.erase(mTriangleTexCoordList.begin() + mTriangleTexCoordList.size() - popCount * 3, mTriangleTexCoordList.end());
            }
            if (mHasTriangleColor)
            {
                mTriangleColorList.erase(mTriangleColorList.begin() + mTriangleColorList.size() - popCount * 3, mTriangleColorList.end());
            }
        }
    

    注意事项:

  • 如果导入的网格是STL格式,请使用FuseVertex建立网格的连接关系. 顶点位置相同的点会被处理为一个顶点. STL格式不能表示带缝的网格,因为它没有拓扑信息, 属于Triangle Soup. 建议使用OBJ格式的网格
  • UnifyCoords使得TriMesh的顶点坐标会被平移和均匀缩放到范围(-bboxSize, bboxSize)以内

  • 半边结构
    class HalfMesh

    HalfMesh类是网格半边结构的一个实现,用户可以直接使用它来表示网格数据. 半边结构的介绍可以参考这个网页

    Half Edge Structure
    图示:半边数据结构示例. 左边红点为内点,右边红点为边界点

    用法说明:

    1. 构建网格示例:

        for (GPP::Int vid = 0; vid < vertexCount; vid++)
        {
            halfMesh->InsertVertex(vertexCoord[vid]);
        }
        std::vector< Vertex3D* > vertexList;
        for (GPP::Int fid = 0; fid < faceCount; fid++)
        {
            vertexList.clear();
            vertexList.push_back(halfMesh->GetVertex(triangleIndex[fid][0]));
            vertexList.push_back(halfMesh->GetVertex(triangleIndex[fid][1]));
            vertexList.push_back(halfMesh->GetVertex(triangleIndex[fid][2]));
            halfMesh->InsertFace(vertexList);
        }
        halfMesh->SetBoundaryVertexEdge();
        halfMesh->UpdateNormal();
    

    2. 如果知道Vertex, Edge, Face的数量,在做Insert前,可以调用ReverseVertex, ReserveEdge, ReserveFace来提升Insert的效率,原理类似std::vector::reserve

    3. 访问顶点邻域示例:

        Edge3D* startEdge = vertex->GetEdge();
        Edge3D* curEdge = startEdge;
        do {
            if (curEdge->GetPair()->GetFace() == NULL)
                break;
            curEdge = curEdge->GetPair()->GetNext();
        } while (curEdge != startEdge);
    

    4. 对于边界点,函数SetBoundaryVertexEdge使得其出边(GetEdge)位于边界边(如上图右红边所示)

    5. ValidateTopology做了3件事情: a. 移出没有Face的Edge; b. SetBoundaryVertexEdge; c. 移出孤立Vertex. 一般对HalfMesh做了拓扑改变后用

    6. 边界点判断:vertex->GetEdge()->GetFace() == NULL; 边界边判断: edge->GetFace() == NULL || edge->GetPair()->GetFace() == NULL

    7. Edge3D的Pair Edge(GetPair)一定不是NULL. 如果Edge3D的Face(GetFace)不是NULL, 则Pre Edge(GetPre)和Next Edge(GetNext)一定不是NULL


    网格导入导出
    TriMesh* Parser::ImportTriMesh(std::string fileName);
    

    目前支持的文件格式: obj, stl, off, ply. 用户也可以导入其它格式的网格数据, 只需要自己写一个Parser, 然后用导入的数据创建网格类(例如TriMesh)即可使用了

    fileName: 格式为path/xxx.obj, path/xxx.stl, path可以是绝对路径,也可以相对路径

    返回值: 如果导入失败则返回NULL


    void Parser::ExportTriMesh(std::string fileName, const ITriMesh* triMesh);
    

    目前支持的文件格式: obj, stl, ply

    fileName: 格式为path/xxx.obj, path/xxx.stl, path可以是绝对路径,也可以相对路径


    最近邻点查询

    NNQuery(ToolNNQuery.h): Nearest Neighbor Query。最近邻域查询工具。

    NNQuery::Init: NNQuery初始化。它给空间的点集建立一个KD Tree,提供最近邻域点的查询效率。

    NNQuery::FindKNN: 查找最近的K个点,按照距离的升序排列。

    NNQuery::FindRadiusNN: 查找半径内的点集,无序。注意squareRadius是半径平方。

        // Compute point cloud density
        ErrorCode CalculatePointCloudDensity(const IPointCloud* pointCloud, Int neighborCount, Real& density)
        {
            if (pointCloud == NULL)
            {
                return GPP_INVALID_INPUT;
            }
            Int pointCount = pointList->GetPointCount();
            if (pointCount < 1 || neighborCount < 1)
            {
                return GPP_INVALID_INPUT;
            }
            neighborCount++;
            PointCloudPointList pointList(pointCloud);
            NNQuery nnQuery;
            ErrorCode res = nnQuery.Init(&pointList);
            if (res != GPP_NO_ERROR)
            {
                return res;
            }
            if (pointCount < neighborCount)
            {
                neighborCount = pointCount;
            }
            Real* distanceRes = new Real[pointCount * neighborCount];
            res = nnQuery.FindKNN(pointList, NULL, neighborCount, NULL, distanceRes);
            if (res != GPP_NO_ERROR)
            {
                GPPFREEARRAY(distanceRes);
                return res;
            }
            std::vector< Real > densityList(pointCount, 0);
            Real avgWeight = 1.0 / Real(neighborCount - 1);
            for (Int pid = 0; pid < pointCount; pid++)
            {
                Int nBase = pid * neighborCount;
                Real curDensity = 0.0;
                for (Int nid = 1; nid < neighborCount; nid++)
                {
                    curDensity += sqrt(distanceRes[nBase + nid]);
                }
                densityList.at(pid) = curDensity * avgWeight;
            }
            Int halfPointId = ceil(Real(pointCount) / 2.0) - 1;
            std::nth_element(densityList.begin(), densityList.begin() + halfPointId, densityList.end());
            density = densityList.at(halfPointId);
            GPPFREEARRAY(distanceRes);
            return GPP_NO_ERROR;
        }
    

    线性方程组(稠密)

    求解稠密矩阵的线性方程组:AX = b

    GeneralMatrix(GeneralMatrix.h):稠密矩阵

    GeneralMatrix3(GeneralMatrix.h):3X3的稠密矩阵。与GeneralMatrix的区别在于,GeneralMatrix3的特征值求解速度更快一些。

    LinearGeneralLUSolver(GeneralMatrix.h):线性方程组求解,LU分解法。

        GeneralMatrix A(matrixSize, matrixSize);
        std::vector< Real > b(matrixSize, 0);
        for (Int rid = 0; rid < matrixSize; rid++)
        {
            A.SetValue(rid, rid, 1.0);
            b.at(rid) = Real(rid);
        }
        LinearGeneralLUSolver solver;
        if (solver.Factorize(A) != GPP_NO_ERROR)
        {
            return false;
        }
        std::vector< Real > result;
        if (solver.Solve(A, b, &result) != GPP_NO_ERROR)
        {
            return false;
        }
    

    LeastSquareGeneralLDLSolver(GeneralMatrix.h):最小二乘求解,LDL分解法。

        // fit a sphere by points
        Int pointSize = points.size(); // pointSize >= 4
        GeneralMatrix matA(pointSize, 4);
        std::vector< Real > vecB(pointSize, 1);
        for (Int rid = 0; rid < supportNum; rid++)
        {
            Vector3 pos = points.at(rid);
            Vector3 nor = pointNormals.at(rid);
            matA.SetValue(rid, 0, nor[0]);
            matA.SetValue(rid, 1, nor[1]);
            matA.SetValue(rid, 2, nor[2]);
            matA.SetValue(rid, 3, 1.0);
            vecB.at(rid) = pos * nor;
        }
        LeastSquareGeneralLDLSolver solver;
        if (solver.Factorize(matA) != GPP_NO_ERROR)
        {
            GPPDebug << "FitSphere solver Factorize failed " << std::endl;
            return false;
        }
        std::vector< Real > result;
        if (solver.Solve(matA, vecB, &result) != GPP_NO_ERROR)
        {
            GPPDebug << "FitSphere solver Solve failed " << std::endl;
            return false;
        }
        sphereCenter = Vector3(result.at(0), result.at(1), result.at(2));
        sphereRadius = fabs(result.at(3));
    

    OrthgonalApproximation(GeneralMatrix.h):仿射变换的旋转矩阵近似求解。


    特征值求解(稠密)

    SelfAdjointEigenSolver(GeneralMatrix.h):特征值求解。

        // compute point cloud normal
        std::vector< Vector3 > deltaCoord(neighborCount)
        for (Int nid = 0; nid < neighborCount; nid++)
        {
            deltaCoord.at(nid) = neighorCoords.at(nid) - pointCoord;
        }
        GeneralMatrix3 matrix;
        for (Int rid = 0; rid < 3; rid++)
        {
            for (Int cid = rid; cid < 3; cid++)
            {
                Real v = 0;
                for (Int kk = 0; kk < neighborCount; kk++)
                {
                    v += deltaCoord.at(kk)[rid] * deltaCoord.at(kk)[cid];
                }
                matrix.SetValue(rid, cid, v);
                matrix.SetValue(cid, rid, v);
            }
        }
        SelfAdjointEigenSolver eigenSolver;
        res = eigenSolver.Compute(matrix);
        if (res != GPP_NO_ERROR)
        {
            GPPInfo << "EigenSolver Compute failed " << res << std::endl;
            return res;
        }
        eigenSolver.GetEigenVector(0, eigenVector);
        pointCloud->SetPointNormal(pid, Vector3(eigenVector.at(0), eigenVector.at(1), eigenVector.at(2)));
    

    线性方程组(稀疏)

    求解稀疏矩阵的线性方程组。

    SparseMatrix(SparseMatrix.h):稀疏矩阵

    LinearSparseLUSolver(SparseMatrix.h):线性方程组求解,LU分解法。

    LinearSparseLLTSolver(SparseMatrix.h):线性方程组求解,LLT分解法。其中矩阵必须为对称正定矩阵。

        SparseMatrix matA(matrixSize, matrixSize);
        std::vector< Real > vecB(matrixSize);
        for (int eid = 0; eid < entitySize; eid++)
        {
            matA.AddTriplet(rows.at(eid), cols.at(eid), values.at(eid));
        }
        if (!matA.BuildFromTriplets())
        {
            return false;
        }
        LinearSparseLUSolver solver;
        // if matA is symmetric positive definite, user can use LinearSparseLLTSolver here.
        ErrorCode res = solver.Factorize(sparseMatrix);
        if (res != GPP_NO_ERROR)
        {
            return false;
        }
        std::vector< Real > result;
        res = solver.Solve(vecB, &result);
        if (res != GPP_NO_ERROR)
        {
            return false;
        }
        solver.Free();
    

    LinearSparseCGSolver(SparseMatrix.h):线性方程组求解,共轭梯度法。适合有初始值的大型稀疏矩阵求解。

        SparseMatrix matA(matrixSize, matrixSize);
        std::vector< Real > vecB(matrixSize);
        for (int eid = 0; eid < entitySize; eid++)
        {
            matA.AddTriplet(rows.at(eid), cols.at(eid), values.at(eid));
        }
        if (!matA.BuildFromTriplets())
        {
            return false;
        }
        LinearSparseCGSolver solver;
        ErrorCode res = solver.Factorize(sparseMatrix);
        if (res != GPP_NO_ERROR)
        {
            return false;
        }
        solver.SetMaxIteration(maxIterationSize);
        std::vector< Real > result;
        res = solver.Solve(vecB, &result, &initValue);
        if (res != GPP_NO_ERROR)
        {
            return false;
        }
        solver.Free();
    

    LeastSquareSparseLLTSolver(SparseMatrix.h):最小二乘求解,LLT分解法。

        SparseMatrix matA(rowSize, colSize);  // rowSize >= colSize
        std::vector< Real > vecB(matrixSize);
        for (int eid = 0; eid < rowSize; eid++)
        {
            matA.AddTriplet(rows.at(eid), cols.at(eid), values.at(eid));
        }
        if (!matA.BuildFromTriplets())
        {
            return false;
        }
        LeastSquareSparseLLTSolver solver;
        ErrorCode res = solver.Factorize(sparseMatrix);
        if (res != GPP_NO_ERROR)
        {
            return false;
        }
        std::vector< Real > result;
        res = solver.Solve(vecB, &result);
        if (res != GPP_NO_ERROR)
        {
            return false;
        }
        solver.Free();
    

    LeastSquareSparseCGSolver(SparseMatrix.h):最小二乘求解,共轭梯度法。适合有初始值的大型稀疏矩阵求解。

        SparseMatrix matA(rowSize, colSize);  // rowSize >= colSize
        std::vector< Real > vecB(matrixSize);
        for (int eid = 0; eid < rowSize; eid++)
        {
            matA.AddTriplet(rows.at(eid), cols.at(eid), values.at(eid));
        }
        if (!matA.BuildFromTriplets())
        {
            return false;
        }
        LeastSquareSparseCGSolver solver;
        ErrorCode res = solver.Factorize(sparseMatrix);
        if (res != GPP_NO_ERROR)
        {
            return false;
        }
        solver.SetMaxIteration(maxIterationSize);
        std::vector< Real > result;
        res = solver.Solve(vecB, &result, &initValue);
        if (res != GPP_NO_ERROR)
        {
            return false;
        }
        solver.Free();
    

    齐次变换

    Matrix4X4: 齐次变换矩阵。主要用于表示三维的透视变换,仿射变换和刚体变换。其中刚体变换最为常用。

    齐次坐标,就是在传统坐标后面加入一维变量:C -> (C, W)。在三维空间中,它把三维坐标(X, Y, Z)提升到了四维的射影空间中(X, Y, Z, W),对应的线性变换就是射影变换。齐次坐标转回三维空间坐标分两种情况,如果W为0,则(X, Y, Z)表示三维空间中的一个方向,如果W不为0,则对应的三维点坐标为(X/W, Y/W, Z/W)。齐次坐标表示有两个好处:一个是可以区分向量和点,另一个是齐次坐标下的矩阵可以表示平移变换。

  • 透视变换:一般的射影变换是一个4X4的矩阵变换,如下图1所示,它可以表示射影空间中任意的线性变换,如透视变换。
  • 仿射变换:如果把矩阵元素做一些限制到下图2,则为一个仿射变换。它可以表示三维空间中任意的线性变换。
  • 刚体变换:如果把图2的a元素的矩阵块限制为正交矩阵块r,如下图3所示,它就变成了一个刚体变换。它可以表示旋转变换和平移变换。
  • transform matrix

    Matrix4X4的一些工具函数:

  • GenerateScale: 缩放变换矩阵
  • GenerateTranslation:平移变换矩阵
  • GenerateVectorToVectorRotation:一个方向旋转到另一个方向的旋转矩阵
  • GenerateLShapeRotation:一个L形状旋转到另一个L形状的旋转矩阵
  • GenerateUnitQuaternionRotation:单位四元数对应的旋转矩阵
  • AffineInverse:仿射逆矩阵

  • 时间统计

    Profiler(Profiler.h): 获取当前时间。可通过时间差来计算某段程序执行的时间。

        Real startTime = Profiler::GetTime();
        ...........
        Real deltaTime = Profiler::GetTime() - startTime;
    
    下载

    VS2013_64bit | VS2015_64bit | VS2017_64bit


    常见问题
    请不要在release的环境下debug程序,因为release环境下面的调试信息是不准确的。
    编译有错误
  • 请仔细检查头文件,lib库,宏定义是否都配置好了,详细请参考使用简介。如果工程中链接了很多第三方库,可以新建一个简单的工程来链接BGL库,来确认BGL库是否有问题。
  • API调用出现问题
  • 检查API的返回码(BglDefines.h):-6属于没有激活开发包;-8属于函数没有定义,如果你有这个函数的授权,可以前来联系。
  • 查看log文件,看能不能得到提示
  • 一般性问题还是特例问题
  • 某个api调用出现问题时,可以多试试几个例子,看看是对所有例子都有问题,还是个例有问题。如果对所有例子都有问题,一般都是用法有问题。
  • 程序崩溃了(Crash)怎么办
  • 请仔细确认程序的崩溃点!如果有异常发生,请在软件程序里Catch住异常。异常的捕获处理属于软件部分的内容。
  • 反馈问题时模型的导出
  • 导出模型坐标时,确保导出的坐标精度是没有截断的,如std::ofstream导出时可以调用precision来设置精度。
  • 网格导出时,一般使用OBJ格式,不要使用STL,因为STL没有网格拓扑信息。不同软件系统重构STL拓扑的实现可能不一样。具体可以参考为什么不建议使用STL格式。
  • 总之,最重要的环节是问题重现。只有问题能够重现出来,才能得到有效的解决。反馈问题前,请先想想反馈的信息是否能够得到问题重现。问题反馈请发送到邮箱geometryhub@qq.com,文件请压缩后发送.