PCL： Delaunay三角剖分（關于三維實體分塊思想總結）

引言：實體造型裡面講述的都是相對全局的方法介紹，主要應用于特定領域，在特定領域能達到相當好的結果；

一：關于模型細分化及其運算

（轉自于百科）

目前常用的實體表示方法主要有：邊界表示法(BRep)、構造實體幾何法(CSG)和掃描法。

(1) 三維形體在計算機内的常用表示法

對于三維幾何元素或簡稱三維形體，最常用的表示法有兩種：CSG和BRep。

① CSG表示法：先定義一些形狀比較簡單的常用體素，如方塊、圓柱、圓錐、球、棱柱等。然後用集合運算并、交、差把體素修改成複雜形狀的形體。早期的CSG模型僅使用代數方程及半空間的概念，體素隻支援多面體與二次曲面體，而不支援表面含有自由曲面的實體。整個模型是棵樹結構，最終形體的表面交線與有效區域沒有顯式給出，不能直接用于NC加工與有限元分析等後繼處理。

② BRep表示法：用點、邊、面、環以及它們之間互相的鄰接關系定義三維實體，形體表面、邊界線、交線等都顯式給出。但是生成個别形體的過程相當複雜、不直覺，不可能由使用者直接操作。它的優點是能支援所有類型的曲面作為形體表面。能直接支援NC加工與有限元分析等，故其優缺點恰與CSG模型相反。後來，人們轉向使用CSG與BRep的混合模型。

③ CSG與BRep的混合模型表示法：用CSG作為高層次抽象的資料模型，用BRep作為低層次的具體表示形式。CSG樹的葉子結點除了存放傳統的體素的參數定義，還存放該體素的BRep表示。CSG樹的中間結點表示它的各子樹的運算結果。用這樣的混合模型對使用者來說十分直覺明了，可以直接支援基于特征的參數化造型功能，而對于形體加工，分析所需要的邊界、交線、表面不僅可顯式表示，且能夠由低層的BRep直接提供。

(2) 三維形體的集合運算

通常一個形體是由兩個或兩個以上較簡單的形體(稱之為體素)經過集合運算得到的集合運算子包括并、交、差。設A和B是兩個用BRep表示描述的維數一緻的多面體，集合運算結果形體C=AB的步驟可簡介如下：

① 确定集合運算兩形體之間的關系：形體邊界表示BRep結構中的面、邊、點之間的基本分類關系分别是"點在面上"、"點在邊上"、"兩點重合"、"邊在面上"、"兩邊共線"、"兩個多邊形共面"等六種關系。先用數值計算确定"點在面上"的關系，其餘五種關系可以根據"點在面上"關系推導出來。當這些關系發生沖突時，就用推理的方法解決沖突。

② 進行邊、體分類：對A形體上的每一條邊，确定對B形體的分類關系(A在B形體内、外、上面、相交等)；同樣對B形體上的每一條邊，确定對A形體的分類關系。

③ 計算多邊形的交線：對于A形體上的多邊形PA和B形體上的每一個多邊形PB，計算它們的交線。

④ 構造新形體C表面上的邊：對于A形體上和B形體上的每一個多邊形PA、PB，根據集合運算的算子收集多邊形PA的邊與另一個多面體表面多邊形PB的交線以生成新形體C表面的邊，如果多邊形PA上有邊被收集到新形體C的表面，則PA所有的平面将成為新形體C表面上的一個平面，多邊形PA的一部分或全部則成為新形體C的一個或多個多邊型。如果定義了兩個形體A和B的完整邊界，那麼形體C的完整邊界就是A和B邊界各部分的總和。

⑤ 構造多邊形的面：對新形體C上的每一個面，将其邊排序構成多邊形面環。

⑥ 合法性檢查：檢查形體C的BRep表示的合法性。

二：模型的表面細分化：

1.1. 曲面的超像素表示方法：

利用模型表面即曲面的表層起伏特征，把三維曲面轉化為二維灰階圖像；再利用分割的方法，把圖像進行分割成小塊；再映射到三維曲面，完成三維曲面分割，形成體元顆粒模型；

1.2. 模型體元的連結表示：

三：點雲表面的Delaunay三角剖分

強烈推薦原文，我隻摘抄代碼

PCL： Delaunay三角剖分（關于三維實體分塊思想總結）

文章連結：OpenCascade中的Delaunay三角剖分

摘要：本文簡要介紹了Delaunay三角剖分的基礎理論，并使用OpenCascade的三角剖分算法将邊界BRep表示的幾何體進行三角離散化後在OpenSceneGraph中顯示。

關鍵字：Delaunay Triangulation、OpenCascade、OpenSceneGraph

....................................................................................................................................

Delaunay三角剖分在OpenCascade的應用

OpenCascade中網格剖分的包主要有BRepMesh、MeshAlgo、MeshVS，其中，類MeshAlgo_Delaunay使用算法Watson來進行Delaunay三角剖分。從類StlTransfer中的注釋The triangulation is computed with the Delaunay algorithm implemented in package BRepMesh.可以看出包BRepMesh就是Delaunay三角剖分的具體實作。使用方法如下：

BRepMesh::Mesh (aShape, Deflection);

這個函數主要是用來對拓撲形狀進行三角剖分。以下通過将一個圓柱三角剖分為例說明如何将一個拓撲形狀進行三角剖分并将結果進行可視化。

/** 
*    Copyright (c) 2013 eryar All Rights Reserved. 
* 
*        File    : Main.cpp 
*        Author  : [email protected] 
*        Date    : 2013-05-26 
*        Version : 0.1 
* 
*    Description : Use BRepMesh_Delaun class to learn  
*                  Delaunay's triangulation algorithm. 
* 
*/ 

// Open Cascade library. 

#include <gp_Pnt.hxx> 
#include <gp_Pln.hxx> 
#include <BRep_Tool.hxx> 
#include <TopoDS.hxx> 
#include <TopoDS_Edge.hxx> 
#include <TopoDS_Wire.hxx> 
#include <TopoDS_Face.hxx> 
#include <BRepBuilderAPI_MakeEdge.hxx> 
#include <BRepBuilderAPI_MakeWire.hxx> 
#include <BRepBuilderAPI_MakeFace.hxx> 
#include <BRepPrimAPI_MakeBox.hxx> 
#include <BRepPrimAPI_MakeCone.hxx> 
#include <BRepPrimAPI_MakeCylinder.hxx> 
#include <BRepPrimApI_MakeSphere.hxx> 
#include <BRepMesh.hxx> 
#include <TopExp_Explorer.hxx> 
#include <Poly_Triangulation.hxx> 
#include <TShort_Array1OfShortReal.hxx> 
#pragma comment(lib, "TKernel.lib") 
#pragma comment(lib, "TKMath.lib") 
#pragma comment(lib, "TKBRep.lib") 
#pragma comment(lib, "TKPrim.lib") 
#pragma comment(lib, "TKMesh.lib") 
#pragma comment(lib, "TKTopAlgo.lib") 

// OpenSceneGraph library. 

#include <osgDB/ReadFile> 
#include <osgViewer/Viewer> 
#include <osgViewer/ViewerEventHandlers> 
#include <osgGA/StateSetManipulator> 
#pragma comment(lib, "osgd.lib") 
#pragma comment(lib, "osgDbd.lib") 
#pragma comment(lib, "osgGAd.lib") 
#pragma comment(lib, "osgViewerd.lib") 

osg::Node* BuildShapeMesh(const TopoDS_Shape& aShape) 

{ 

    osg::ref_ptr<osg::Group> root = new osg::Group(); 
    osg::ref_ptr<osg::Geode> geode = new osg::Geode(); 
    osg::ref_ptr<osg::Geometry> triGeom = new osg::Geometry(); 
    osg::ref_ptr<osg::Vec3Array> vertices = new osg::Vec3Array(); 
    osg::ref_ptr<osg::Vec3Array> normals = new osg::Vec3Array(); 

    BRepMesh::Mesh(aShape, 1); 
    TopExp_Explorer faceExplorer; 

for (faceExplorer.Init(aShape, TopAbs_FACE); faceExplorer.More(); faceExplorer.Next()) 
{ 

        TopLoc_Location loc; 
        TopoDS_Face aFace = TopoDS::Face(faceExplorer.Current()); 
        Handle_Poly_Triangulation triFace = BRep_Tool::Triangulation(aFace, loc); 
        Standard_Integer nTriangles = triFace->NbTriangles(); 

        gp_Pnt vertex1; 
        gp_Pnt vertex2; 
        gp_Pnt vertex3; 

        Standard_Integer nVertexIndex1 = 0; 
        Standard_Integer nVertexIndex2 = 0; 
        Standard_Integer nVertexIndex3 = 0; 

        TColgp_Array1OfPnt nodes(1, triFace->NbNodes()); 
        Poly_Array1OfTriangle triangles(1, triFace->NbTriangles()); 
        nodes = triFace->Nodes(); 

        triangles = triFace->Triangles(); 

for (Standard_Integer i = 1; i <= nTriangles; i++) 
{ 

            Poly_Triangle aTriangle = triangles.Value(i); 
            aTriangle.Get(nVertexIndex1, nVertexIndex2, nVertexIndex3); 

            vertex1 = nodes.Value(nVertexIndex1); 
            vertex2 = nodes.Value(nVertexIndex2); 
            vertex3 = nodes.Value(nVertexIndex3); 

            gp_XYZ vector12(vertex2.XYZ() - vertex1.XYZ()); 
            gp_XYZ vector13(vertex3.XYZ() - vertex1.XYZ()); 
            gp_XYZ normal = vector12.Crossed(vector13); 

            Standard_Real rModulus = normal.Modulus(); 

if (rModulus > gp::Resolution()) 
{ 
                normal.Normalize(); 
} 
else 
{ 
                normal.SetCoord(0., 0., 0.); 
} 

            vertices->push_back(osg::Vec3(vertex1.X(), vertex1.Y(), vertex1.Z())); 
            vertices->push_back(osg::Vec3(vertex2.X(), vertex2.Y(), vertex2.Z())); 
            vertices->push_back(osg::Vec3(vertex3.X(), vertex3.Y(), vertex3.Z())); 
            normals->push_back(osg::Vec3(normal.X(), normal.Y(), normal.Z())); 
} 
} 

    triGeom->setVertexArray(vertices.get()); 
    triGeom->addPrimitiveSet(new osg::DrawArrays(osg::PrimitiveSet::TRIANGLES, 0, vertices->size())); 
    triGeom->setNormalArray(normals); 
    triGeom->setNormalBinding(osg::Geometry::BIND_PER_PRIMITIVE); 

    geode->addDrawable(triGeom); 
    root->addChild(geode); 
return root.release(); 

} 

int main(int argc, char* argv[]) 
{ 
    osgViewer::Viewer myViewer; 
    osg::ref_ptr<osg::Group> root = new osg::Group(); 

    root->addChild(BuildShapeMesh(BRepPrimAPI_MakeCylinder(.6, 1))); 

    myViewer.setSceneData(root); 
    myViewer.addEventHandler(new osgGA::StateSetManipulator(myViewer.getCamera()->getOrCreateStateSet())); 
    myViewer.addEventHandler(new osgViewer::StatsHandler); 
    myViewer.addEventHandler(new osgViewer::WindowSizeHandler); 
return myViewer.run(); 
}

運作結果如下：

PCL： Delaunay三角剖分（關于三維實體分塊思想總結）

Figure 4.1 Cylinder mesh generated by BRepMesh::Mesh

PCL： Delaunay三角剖分（關于三維實體分塊思想總結）

Delaunay三角剖分在OpenCascade的應用

繼續閱讀

個人技術部落格的選擇：CSDN、部落格園、簡書、知乎專欄還是Github Page？

PCL：python pcl解碼RGB- point_cloud2.read_points rgb

三維重建15：最近遇到的-标定-EKF-優化方法等

三維重建：重定位問題

三維重建：SLAM的尺度和方法論問題

三維重建：SLAM算法的考題總結

三維重建3：旋轉矩陣-病态矩陣、歐拉角-萬向鎖、四元數

關于編譯PCL1.71

CNN結構：場景分割與Relation Network

SLAM: 單目視覺SLAM的方案分類《機器人手冊》

SLAM：使用G2O-ORB-SLAM（編譯）

PCL：描述三維離散點的ROPS特征（Code）

PCL：Ubuntu下安裝配置PCL

OpenCV：OpenCV4.0更新

人工機器：jetbot小車密碼

SLAM:(編譯ORB)fatal error LNK1181: 無法打開輸入檔案“libboost_mpi-vc110-mt-1_57.lib”