Mesh Algorithm in OpenCascade
eryar@163.com
Abstract. Rendering a generic surface is a two steps process: first, computing the points that will form the mesh of the surface and then, send this mesh to 3D API. Use the Triangle to triangulate the parametric space and then lifting map to the model 3D space. This is the main method to visualize the generic shaded surface. This paper show the OpenCascade triangulation of the parametric space and the map result: mesh in 3D model space. Use the method can visualize a generic surface.
Key words. Delaunay Triangulation, Tessellation, Mesh, OpenCascade, Shaded Surface
1. Introduction
與曲線的可視化算法相比，曲面的可視化要稍微復雜點。總的思路還是很好理解的，那就是把參數空間三角剖分，再將剖分結果映射到三維空間，就得到曲面的網格數據了。
因為B樣條曲面的強凸包性，所以可以對其參數空間進行三角剖分，再映射到三維空間。這樣可以實現曲面的可視化，但是還有些問題需要處理，如曲面上開孔、曲面離散精度控制等。
因為OpenCascade使用了邊界表示法（BRep），所以通過Face，Wire，Edge可以得到曲面的參數范圍，若曲面上有開孔，也可通過Edge的PCurve得到開孔在曲面上的參數表示。將得到的參數空間進行三角剖分，再映射到三維空間中，即可對邊界表示的形狀進行可視化。
用三角網格來逼近實際的形狀的精度可以通過增加或減少參數空間中的點來實現。當把參數空間剖分得密，映射到三維空間中的曲面更逼近真實的曲面；當把參數空間剖分得疏，映射到三維空間中的曲面就比較粗糙了。
本文主要將OpenCascade中曲面的參數空間的三角剖分結果顯示出來，來分析和理解上述算法。
2. OpenCascade BRep Shape
在OpenCascade中實體的邊界表示法（BRep）為：
u COMPSOLID由面共享的SOLID組成；
u SOLID（Cylinder, Cone, Sphere, Torus, etc.）由SHELLS分隔出來的體（Volume）；
u SHELL由邊Edges相連的FACES組成；
u FACE是一個映射（MAP），從矩形的參數UV空間映射到3D空間。（Cylinder: [0, 2*PI] x[0, H] -> R3，Cone, Sphere, Torus, Bezier Surface, NURBS Surface, etc.）
u FACE的邊界由WIRE組成；
u WIRE由相連的EDGES組成；
u EDGE也是一個映射，從一維參數空間U映射到3D空間。（Bezier’s Curve: [0,1] -> R3， NURBS Curve, etc.）
u VERTEX是用來限制EDGE的；
邊界表示法（BRep）形成了不同SHAPES（CompSolid, Solid, Shell, Face, Wire, Edge, Vertex）之間的一個圖結構（a structure of GRAPH），如下圖所示：
Figure 2.1 Shape BRep in OpenCascade
表示上圖的的邊界表示法形成的樹形結構如下圖所示。由圖可知，有些結構被共享幾次。在OpenCascade中使用類TopoDS_Shape來保存這個結構。
Figure 2.2 Graph structure of the BRep Shape
3. How the Mesh is Generated
OpenCascade中可以遍歷COMPSOLID不同的子形狀。首先，將EDGE離散化，實現的偽代碼如下所示：
for (TopExp_Explorer edgeExp(theCompSolid, TopAbs_EDGE);
edgeExp.More();
edgeExp.Next())
{
// The U-interval of the EDGE is subdivided into
// segments with respect to the edge length and
// deflection in 3D-space. By the map, the segments
// of the U-interval give the segments in 3D-Space.
const TopoDS_Edge& theEdge = TopoDS::Edge(edgeExp.Current());
BRepAdaptor_Curve BAC(theEdge);
GCPnts_TangentialDeflection thePointsOnCurve;
thePointsOnCurve.Initialize(BAC, aDeflection, cDeflection);
Standard_Real u = 0.0;
gp_Pnt aPoint;
for (Standard_Integer i = 1; i <= thePointsOnCurve.NbPoints(); ++i)
{
u = thePointsOnCurve.Parameter(i);
aPoint = thePointsOnCurve.Value(i);
}
}
使用上述算法將每條EDGE離散化，如下圖所示：
Figure 3.1 Creation of U-Mesh and 3D-Mesh for each EDGE
當曲面上有開孔時，開孔的信息可以通過WIRE來獲得。對于組成開孔的WIRE的每條EDGE，可以通過曲面上的曲線PCurve來將開孔的參數統一到曲面的UV參數空間。實現的偽代碼如下所示：
for (TopExp_Explorer faceExp(theCompSolid, TopAbs_FACE);
faceExp.More();
faceExp.Next())
{
for (TopExp_Explorer wireExp(faceExp.Current(), TopAbs_WIRE);
wireExp.More();
wireExp.Next())
{
for (TopExp_Explorer edgeExp(wireExp.Current(), TopAbs_EDGE);
edgeExp.More();
edgeExp.Next())
{
// The U-Mesh of the EDGE is assembled after scaling in the
// UV-domain to constitute the WIRE.
Standard_Real theFirst = 0.0;
Standard_Real theLast = 0.0;
gp_Pnt2d theUV;
Handle_Geom2d_Curve thePCurve =
BRep_Tool::CurveOnSurface(theEdge, theFace, theFirst, theLast);
theUV = thePCurve.Value(theFirst);
}
}
}
Figure 3.2 Hole in Parametric UV space
將WIRE限制的曲面的參數空間UV進行三角剖分，若其中有開孔的信息，則將形成孔的WIRE內部的三角形去掉。將參數空間的三角剖分映射到三維空間，即可得到曲面的三角剖分網格。如下圖所示：
Figure 3.3 Hole in Surface
對組成COMPSOLID的每個FACE進行剖分，最后就得到COMPSOLID的網格。實現的偽代碼如下所示：
for (TopExp_Explorer faceExp(theCompSolid, TopAbs_FACE);
faceExp.More();
faceExp.Next())
{
// The 3d-mesh of the FACE is assembled to form the
// boundary of the SOLID.
}
Figure 3.4 Mesh of the Shape
4. Deflection Control
形狀通過三角網格來逼近顯示，所以當離散精度越高時，顯示越逼真，但是產生的數據量大；離散精度越低時，顯示越失真，但是產生的數據量小。正如莎翁所說：To be or not to be: that is the question。面對選擇時，不走極端，中庸之道也是個不錯的解決方法。在顯示逼真程度與數據量的大小之間做個平衡，實體三角剖分的算法需要考慮的地方。
在OpenCascade中曲面的三角剖分的網格數據都保存在類Poly_Triangulation中，也包括曲面的參數空間的剖分，參數結點數據是UVNodes。如下代碼所示為將曲面的參數空間三角剖分結果可視化：
osg::Geode* BuildUVMesh(const Handle_Poly_Triangulation& theMesh)
{
osg::ref_ptr<osg::Geode> theGeode = new osg::Geode();
osg::ref_ptr<osg::Geometry> theTriangles = new osg::Geometry();
osg::ref_ptr<osg::Vec3Array> theVertices = new osg::Vec3Array();
for (Standard_Integer t = 1; t <= theMesh->NbTriangles(); ++t)
{
const Poly_Triangle& theTriangle = theMesh->Triangles().Value(t);
gp_Pnt2d theUV1 = theMesh->UVNodes().Value(theTriangle(1));
gp_Pnt2d theUV2 = theMesh->UVNodes().Value(theTriangle(2));
gp_Pnt2d theUV3 = theMesh->UVNodes().Value(theTriangle(3));
theVertices->push_back(osg::Vec3(theUV1.X(), 0.0, theUV1.Y()));
theVertices->push_back(osg::Vec3(theUV2.X(), 0.0, theUV2.Y()));
theVertices->push_back(osg::Vec3(theUV3.X(), 0.0, theUV3.Y()));
}
theTriangles->setVertexArray(theVertices.get());
theTriangles->addPrimitiveSet(
new osg::DrawArrays(osg::PrimitiveSet::TRIANGLES, 0, theVertices->size()));
osgUtil::SmoothingVisitor smv;
smv.smooth(*theTriangles);
theGeode->addDrawable(theTriangles);
return theGeode.release();
}
如下圖所示，將球面參數空間的三角剖分顯示出來。由球面的參數方程可知其參數空間的范圍，U從0到2PI，V從-PI/2到PI/2。
從圖中還可以看出，對球面的參數空間進行剖分時，只在V方向加入了一些點，而在U方向沒有增加。
Figure 4.1 Triangulation of the Sphere parametric space
當增加離散精度后，顯示得更逼真，但產生了更多的網格數據，如下圖所示：
Figure 4.2 Triangulation of the Sphere
從上圖可知，將參數空間剖分的越細密，顯示的效果越逼真。由上圖還可知，OpenCascade對球面的參數空間剖分也不是很均勻，有很密集的區域，也是相對稀疏的區域。如果將參數空間均勻剖分，映射到三維空間曲面上時，顯示效果也不是很均勻。如下圖所示為較理想的球面的剖分網格：
Figure 4.3 Triangulation of the Sphere Generated by Netgen
Figure 4.4 Triangulation of the Sphere
從圖中可以看出，將參數空間均勻剖分后，映射到三維空間后，在球面的兩個極點處，顯示出來有些密集，在軌道線附近，比較稀疏。
同一個曲面，當剖分得密集時，顯示得細膩，如下圖所示：
Figure 4.5 Triangulation of a Shape by Netgen
在OpenCascade中得到的剖分結果如下圖所示：
Figure 4.6 Triangulation of a Shape by OpenCascade
在OpenCascade中只是把邊的離散點組成了三角形，沒有優化，但是用于顯示也還不錯，且數據量也很小。當程序要處理的模型很多時，減少三角網格的數量，將會明顯提高顯示速度。所以在對實體進行網格剖分時，需要根據實際需要，選擇折中的，和諧的算法。即若對網格剖分質量要求較高（如用于有限元分析），模型量少，可以將實體剖分得精細；若模型量很大，又對顯示速度要求較高，在網格剖分算法中可以選擇產生數據量小的算法。
上述形狀的渲染模式如下圖所示。雖然剖分中也有很多細長的三角形，但當把網格的頂點法向設置正確后，用于顯示已經足夠。三角形的數量明顯要少很多。
Figure 4.7 Shaded mode of the Shape
Figure 4.8 Shaded Mode in OpenCascade
5. Conclusions
將形狀中曲面的參數空間三角剖分后，再映射到三維空間即可得到形狀的剖分網格。當形狀上有開孔時，通過邊界表示法，可以得到孔的數據。通過曲面上的曲線PCurve，可將孔與面統一到參數空間進行剖分。
網格的質量與離散精度的控制是個問題。根據需要來對形狀進行網格化。當把參數空間均勻剖分時，產生的曲面不一定均勻。所以，也應該存在與曲線離散化類似的算法，即在曲率較大的地方，剖分的密集；在很平的地方，剖分粗。這樣來對顯示與速度之間做個平衡。
6. References
1. Alain PERRONNET. NEF: A Mesher based on OpenCascade C.A.D software
https://www.ljll.math.upmc.fr/~perronnet/mit/mit.html
2. Kelly Dempski. Focus on Curves and Surfaces. Premier Press 2003