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
與曲線(xiàn)的可視化算法相比，曲面的可視化要稍微復(fù)雜點(diǎn)。總的思路還是很好理解的，那就是把參數(shù)空間三角剖分，再將剖分結(jié)果映射到三維空間，就得到曲面的網(wǎng)格數(shù)據(jù)了。
因?yàn)锽樣條曲面的強(qiáng)凸包性，所以可以對(duì)其參數(shù)空間進(jìn)行三角剖分，再映射到三維空間。這樣可以實(shí)現(xiàn)曲面的可視化，但是還有些問(wèn)題需要處理，如曲面上開(kāi)孔、曲面離散精度控制等。
因?yàn)镺penCascade使用了邊界表示法（BRep），所以通過(guò)Face，Wire，Edge可以得到曲面的參數(shù)范圍，若曲面上有開(kāi)孔，也可通過(guò)Edge的PCurve得到開(kāi)孔在曲面上的參數(shù)表示。將得到的參數(shù)空間進(jìn)行三角剖分，再映射到三維空間中，即可對(duì)邊界表示的形狀進(jìn)行可視化。
用三角網(wǎng)格來(lái)逼近實(shí)際的形狀的精度可以通過(guò)增加或減少參數(shù)空間中的點(diǎn)來(lái)實(shí)現(xiàn)。當(dāng)把參數(shù)空間剖分得密，映射到三維空間中的曲面更逼近真實(shí)的曲面；當(dāng)把參數(shù)空間剖分得疏，映射到三維空間中的曲面就比較粗糙了。
本文主要將OpenCascade中曲面的參數(shù)空間的三角剖分結(jié)果顯示出來(lái)，來(lái)分析和理解上述算法。
2. OpenCascade BRep Shape
在OpenCascade中實(shí)體的邊界表示法（BRep）為：
u COMPSOLID由面共享的SOLID組成；
u SOLID（Cylinder, Cone, Sphere, Torus, etc.）由SHELLS分隔出來(lái)的體（Volume）；
u SHELL由邊Edges相連的FACES組成；
u FACE是一個(gè)映射（MAP），從矩形的參數(shù)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也是一個(gè)映射，從一維參數(shù)空間U映射到3D空間。（Bezier’s Curve: [0,1] -> R3， NURBS Curve, etc.）
u VERTEX是用來(lái)限制EDGE的；
邊界表示法（BRep）形成了不同SHAPES（CompSolid, Solid, Shell, Face, Wire, Edge, Vertex）之間的一個(gè)圖結(jié)構(gòu)（a structure of GRAPH），如下圖所示：
Figure 2.1 Shape BRep in OpenCascade
表示上圖的的邊界表示法形成的樹(shù)形結(jié)構(gòu)如下圖所示。由圖可知，有些結(jié)構(gòu)被共享幾次。在OpenCascade中使用類(lèi)TopoDS_Shape來(lái)保存這個(gè)結(jié)構(gòu)。
Figure 2.2 Graph structure of the BRep Shape
3. How the Mesh is Generated
OpenCascade中可以遍歷COMPSOLID不同的子形狀。首先，將EDGE離散化，實(shí)現(xiàn)的偽代碼如下所示：
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
當(dāng)曲面上有開(kāi)孔時(shí)，開(kāi)孔的信息可以通過(guò)WIRE來(lái)獲得。對(duì)于組成開(kāi)孔的WIRE的每條EDGE，可以通過(guò)曲面上的曲線(xiàn)PCurve來(lái)將開(kāi)孔的參數(shù)統(tǒng)一到曲面的UV參數(shù)空間。實(shí)現(xiàn)的偽代碼如下所示：
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限制的曲面的參數(shù)空間UV進(jìn)行三角剖分，若其中有開(kāi)孔的信息，則將形成孔的WIRE內(nèi)部的三角形去掉。將參數(shù)空間的三角剖分映射到三維空間，即可得到曲面的三角剖分網(wǎng)格。如下圖所示：
Figure 3.3 Hole in Surface
對(duì)組成COMPSOLID的每個(gè)FACE進(jìn)行剖分，最后就得到COMPSOLID的網(wǎng)格。實(shí)現(xiàn)的偽代碼如下所示：
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
形狀通過(guò)三角網(wǎng)格來(lái)逼近顯示，所以當(dāng)離散精度越高時(shí)，顯示越逼真，但是產(chǎn)生的數(shù)據(jù)量大；離散精度越低時(shí)，顯示越失真，但是產(chǎn)生的數(shù)據(jù)量小。正如莎翁所說(shuō)：To be or not to be: that is the question。面對(duì)選擇時(shí)，不走極端，中庸之道也是個(gè)不錯(cuò)的解決方法。在顯示逼真程度與數(shù)據(jù)量的大小之間做個(gè)平衡，實(shí)體三角剖分的算法需要考慮的地方。
在OpenCascade中曲面的三角剖分的網(wǎng)格數(shù)據(jù)都保存在類(lèi)Poly_Triangulation中，也包括曲面的參數(shù)空間的剖分，參數(shù)結(jié)點(diǎn)數(shù)據(jù)是UVNodes。如下代碼所示為將曲面的參數(shù)空間三角剖分結(jié)果可視化：
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();
}
如下圖所示，將球面參數(shù)空間的三角剖分顯示出來(lái)。由球面的參數(shù)方程可知其參數(shù)空間的范圍，U從0到2PI，V從-PI/2到PI/2。
從圖中還可以看出，對(duì)球面的參數(shù)空間進(jìn)行剖分時(shí)，只在V方向加入了一些點(diǎn)，而在U方向沒(méi)有增加。
Figure 4.1 Triangulation of the Sphere parametric space
當(dāng)增加離散精度后，顯示得更逼真，但產(chǎn)生了更多的網(wǎng)格數(shù)據(jù)，如下圖所示：
Figure 4.2 Triangulation of the Sphere
從上圖可知，將參數(shù)空間剖分的越細(xì)密，顯示的效果越逼真。由上圖還可知，OpenCascade對(duì)球面的參數(shù)空間剖分也不是很均勻，有很密集的區(qū)域，也是相對(duì)稀疏的區(qū)域。如果將參數(shù)空間均勻剖分，映射到三維空間曲面上時(shí)，顯示效果也不是很均勻。如下圖所示為較理想的球面的剖分網(wǎng)格：
Figure 4.3 Triangulation of the Sphere Generated by Netgen
Figure 4.4 Triangulation of the Sphere
從圖中可以看出，將參數(shù)空間均勻剖分后，映射到三維空間后，在球面的兩個(gè)極點(diǎn)處，顯示出來(lái)有些密集，在軌道線(xiàn)附近，比較稀疏。
同一個(gè)曲面，當(dāng)剖分得密集時(shí)，顯示得細(xì)膩，如下圖所示：
Figure 4.5 Triangulation of a Shape by Netgen
在OpenCascade中得到的剖分結(jié)果如下圖所示：
Figure 4.6 Triangulation of a Shape by OpenCascade
在OpenCascade中只是把邊的離散點(diǎn)組成了三角形，沒(méi)有優(yōu)化，但是用于顯示也還不錯(cuò)，且數(shù)據(jù)量也很小。當(dāng)程序要處理的模型很多時(shí)，減少三角網(wǎng)格的數(shù)量，將會(huì)明顯提高顯示速度。所以在對(duì)實(shí)體進(jìn)行網(wǎng)格剖分時(shí)，需要根據(jù)實(shí)際需要，選擇折中的，和諧的算法。即若對(duì)網(wǎng)格剖分質(zhì)量要求較高（如用于有限元分析），模型量少，可以將實(shí)體剖分得精細(xì)；若模型量很大，又對(duì)顯示速度要求較高，在網(wǎng)格剖分算法中可以選擇產(chǎn)生數(shù)據(jù)量小的算法。
上述形狀的渲染模式如下圖所示。雖然剖分中也有很多細(xì)長(zhǎng)的三角形，但當(dāng)把網(wǎng)格的頂點(diǎn)法向設(shè)置正確后，用于顯示已經(jīng)足夠。三角形的數(shù)量明顯要少很多。
Figure 4.7 Shaded mode of the Shape
Figure 4.8 Shaded Mode in OpenCascade
5. Conclusions
將形狀中曲面的參數(shù)空間三角剖分后，再映射到三維空間即可得到形狀的剖分網(wǎng)格。當(dāng)形狀上有開(kāi)孔時(shí)，通過(guò)邊界表示法，可以得到孔的數(shù)據(jù)。通過(guò)曲面上的曲線(xiàn)PCurve，可將孔與面統(tǒng)一到參數(shù)空間進(jìn)行剖分。
網(wǎng)格的質(zhì)量與離散精度的控制是個(gè)問(wèn)題。根據(jù)需要來(lái)對(duì)形狀進(jìn)行網(wǎng)格化。當(dāng)把參數(shù)空間均勻剖分時(shí)，產(chǎn)生的曲面不一定均勻。所以，也應(yīng)該存在與曲線(xiàn)離散化類(lèi)似的算法，即在曲率較大的地方，剖分的密集；在很平的地方，剖分粗。這樣來(lái)對(duì)顯示與速度之間做個(gè)平衡。
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