OpenCascade中網(wǎng)格的數(shù)據(jù)結(jié)構(gòu)
Mesh Data Structure in OpenCascade
eryar@163.com
摘要Abstract：本文對(duì)網(wǎng)格數(shù)據(jù)結(jié)構(gòu)作簡(jiǎn)要介紹，并結(jié)合使用OpenCascade中的數(shù)據(jù)結(jié)構(gòu)，將網(wǎng)格數(shù)據(jù)在OpenSceneGraph中可視化。
關(guān)鍵字KeyWords：OpenCascade、OpenSceneGraph、Triangulation、Mesh Data Structure
一、引言 Introduction
三角網(wǎng)格就是全部由三角形組成的多邊形網(wǎng)格。多邊形和三角網(wǎng)格在圖形學(xué)和建模中廣泛使用，用來(lái)模擬復(fù)雜物體的表面，如建筑、車輛、人體，當(dāng)然，還有茶壺等自由曲面。任意多邊形網(wǎng)格都能轉(zhuǎn)換成三角網(wǎng)格。三角網(wǎng)格以其簡(jiǎn)單性而吸引人，相對(duì)于一般多邊形網(wǎng)格許多操作對(duì)三角網(wǎng)格列容易。
常用的網(wǎng)格數(shù)據(jù)文件有：
1．Wavefront OBJ(*.obj)
2．3D Max(*.max, *.3ds)
3．VRML(*.vrl)
4．Inventor(*.iv)
5．PLY(*.ply, *.ply2)
6．STL(*.stl)
7．Off(*.off) in CGAL library
有些文件以文本方式保存，有些可以以二進(jìn)制方式保存。如下圖所示為OBJ文件的格式：
Figure 1.1 Wavefront OBJ File Format
l Vertices
n 以‘V’開(kāi)始；
n 其后為坐標(biāo)值（x,y,z）；
l Faces
n 以‘F’開(kāi)始；
n 其后為面的頂點(diǎn)索引值；
l Other properties
n Normal, texture coordinates, material, etc.
二、三角網(wǎng)格的表示 Mesh Data Structure
三角網(wǎng)格為一個(gè)三角形列表，所以最直接的表示方法是用三角形數(shù)組：
struct Triangle
{
Vector3 p[3];
};
struct TriangleMesh
{
int triCount;
Triangle* triList;
};
對(duì)于某些應(yīng)用程序，這種表示方法已經(jīng)足夠。然而，術(shù)語(yǔ)“網(wǎng)格”隱含的相鄰三角形的連通性未在這種簡(jiǎn)單表示中有任何體現(xiàn)。實(shí)際應(yīng)用中出現(xiàn)的三角網(wǎng)格，每個(gè)三角形都和其他三角形共享邊。于是三角網(wǎng)格需要存儲(chǔ)三類信息：
l 頂點(diǎn)。每個(gè)三角形有三個(gè)頂點(diǎn)，各頂點(diǎn)都有可能和其他三角形共享；
l 邊。連接兩個(gè)頂點(diǎn)的邊，每個(gè)三角形有三條邊；
l 面。每個(gè)三角形對(duì)應(yīng)一個(gè)面。我們可以用頂點(diǎn)或邊列表表示面；
根據(jù)應(yīng)用程序的不同，有多種有效的網(wǎng)格表示方法。常用的一種標(biāo)準(zhǔn)的存儲(chǔ)格式為索引三角網(wǎng)格。
在索引三角網(wǎng)格中，我們維護(hù)了兩個(gè)列表：頂點(diǎn)表與三角形表。每個(gè)頂點(diǎn)包含一個(gè)3D位置，也可能有表面法向量、紋理映射坐標(biāo)、光照值附加數(shù)據(jù)。每個(gè)三角形由頂點(diǎn)列表的三個(gè)索引值組成。通常頂點(diǎn)列出的順序是非常重要的，因?yàn)槲覀儽仨毧紤]面的“正面”和“反面”。從前面看時(shí)，我們將用順時(shí)針?lè)较蛄谐鲰旤c(diǎn)。
在OpenCascade中，分別用類TColgp_Array1OfPnt和Poly_Array1OfTriangle表存儲(chǔ)頂點(diǎn)表和三角形表。注意到索引三角形列表中的鄰接信息是隱含的，即邊信息沒(méi)有存儲(chǔ)，但我們可以通過(guò)搜索三角形表找出公共邊。和前面“三角形數(shù)組”方式相比，這種方式確實(shí)能節(jié)省不少空間。原因是信息存于頂點(diǎn)級(jí)別，它的整數(shù)索引比之三角形數(shù)組里存儲(chǔ)的頂點(diǎn)重復(fù)率要小得多。實(shí)踐中，三角網(wǎng)里確實(shí)有大量的連接性問(wèn)題。
簡(jiǎn)單索引三角網(wǎng)格對(duì)于基本應(yīng)用已經(jīng)足夠了。但為更加高效地實(shí)現(xiàn)某些操作還可以進(jìn)一步改進(jìn)。主要的問(wèn)題是鄰接信息沒(méi)有顯式表達(dá)，所以必須從三角形列表中搜索。另一種表達(dá)方法可以常數(shù)時(shí)間內(nèi)取得這種信息。方法是顯式維護(hù)一個(gè)邊列表，每邊由兩個(gè)端點(diǎn)定義，同時(shí)維護(hù)一個(gè)共享該邊的三角形列表。這樣三角形可視為三條邊而非三個(gè)點(diǎn)的列表，也就是說(shuō)它是邊列表的索引。該思想的一個(gè)擴(kuò)展稱作“Winged Edge”模型（翼邊模型），對(duì)每一頂點(diǎn)，存儲(chǔ)使用該點(diǎn)的邊的索引。這樣三角形和邊都可以通過(guò)定位點(diǎn)列表快速查找。
大多數(shù)顯卡并不直接支持索引三角網(wǎng)。渲染三角形時(shí)，一般是將三個(gè)頂點(diǎn)同時(shí)提交。這樣，共享頂點(diǎn)會(huì)多次提交，三角形用到一次就提交一次。因?yàn)閮?nèi)存和圖形硬件間的數(shù)據(jù)傳輸是瓶頸，所以許多API和硬件支持特殊三角網(wǎng)格式以減少傳輸量。基本思想是排序點(diǎn)和面，使得顯存中已有的三角形不需要再次傳輸。
從最高靈活性到最低靈活性，我們討論三種方案：
n 頂點(diǎn)緩存；
n 三角帶Triangle Strip；
n 三角扇Triangle Fan；
三、程序示例 Code Example
在安裝好的CGAL庫(kù)中發(fā)現(xiàn)其例子中有很多off文件，其格式同常見(jiàn)的網(wǎng)格文件格式基本相同，結(jié)合OpenCascade和OpenSceneGraph，讀取off文件，將其表示的網(wǎng)格模型顯示出來(lái)。程序代碼如下所示：
1 /*
2 * Copyright (c) 2013 eryar All Rights Reserved.
3 *
4 * File : Main.cpp
5 * Author : eryar@163.com
6 * Date : 2013-08-10 18:02
7 * Version : V1.0
8 *
9 * Description : Mesh Viewer for the general mesh file format.
10 * Poly_Triangulation data structure can save vertices and triangle index.
11 *
12 */
13
14 // OpenSceneGraph library.
15 #include <osgDB/ReadFile>
16 #include <osgViewer/Viewer>
17 #include <osgGA/StateSetManipulator>
18 #include <osgViewer/ViewerEventHandlers>
19
20 #pragma comment(lib, "osgd.lib")
21 #pragma comment(lib, "osgDBd.lib")
22 #pragma comment(lib, "osgGAd.lib")
23 #pragma comment(lib, "osgViewerd.lib")
24
25 // OpenCascade library.
26 #include <TColgp_Array1OfPnt.hxx>
27 #include <Poly_Array1OfTriangle.hxx>
28 #include <Poly_Triangulation.hxx>
29
30 #pragma comment(lib, "TKernel.lib")
31 #pragma comment(lib, "TKMath.lib")
32
33 /**
34 * @breif Build the mesh from *.off file.
35 */
36 osg::Node* buildMesh(const std::string& fileName)
37 {
38 std::ifstream offFile(fileName.c_str());
39 std::string strBuffer;
40
41 osg::ref_ptr<osg::Geode> geode = new osg::Geode();
42 osg::ref_ptr<osg::Geometry> triGeom = new osg::Geometry();
43 osg::ref_ptr<osg::Vec3Array> vertices = new osg::Vec3Array();
44 osg::ref_ptr<osg::Vec3Array> normals = new osg::Vec3Array();
45
46 Standard_Integer nbNodes = 0;
47 Standard_Integer nbTriangles = 0;
48
49 // Ignore "OFF"
50 offFile>>strBuffer;
51 offFile>>nbNodes>>nbTriangles>>strBuffer;
52
53 TColgp_Array1OfPnt nodes(0, nbNodes);
54 Poly_Array1OfTriangle triangles(0, nbTriangles);
55
56 // Read node coordinate and store them.
57 Standard_Real dx = 0.0;
58 Standard_Real dy = 0.0;
59 Standard_Real dz = 0.0;
60
61 for (Standard_Integer i = 0; i < nbNodes; i++)
62 {
63 offFile>>dx>>dy>>dz;
64
65 nodes(i).SetCoord(dx, dy, dz);
66 }
67
68 // Read the triangles
69 Standard_Integer ni = 0;
70 Standard_Integer n1 = 0;
71 Standard_Integer n2 = 0;
72 Standard_Integer n3 = 0;
73
74 for (Standard_Integer i = 0; i < nbTriangles; i++)
75 {
76 offFile>>ni>>n1>>n2>>n3;
77
78 triangles(i).Set(n1, n2, n3);
79 }
80
81 // Construct the mesh data by Poly_Triangulation.
82 gp_Pnt node1;
83 gp_Pnt node2;
84 gp_Pnt node3;
85 Poly_Triangle triangle;
86 Handle_Poly_Triangulation T = new Poly_Triangulation(nodes, triangles);
87
88 for (Standard_Integer i = 0; i < nbTriangles; i++)
89 {
90 triangle = triangles.Value(i);
91
92 triangle.Get(n1, n2, n3);
93
94 node1 = nodes.Value(n1);
95 node2 = nodes.Value(n2);
96 node3 = nodes.Value(n3);
97
98 gp_XYZ vector12(node2.XYZ() - node1.XYZ());
99 gp_XYZ vector13(node3.XYZ() - node1.XYZ());
100 gp_XYZ normal = vector12.Crossed(vector13);
101 Standard_Real rModulus = normal.Modulus();
102
103 if (rModulus > gp::Resolution())
104 {
105 normal.Normalize();
106 }
107 else
108 {
109 normal.SetCoord(0., 0., 0.);
110 }
111
112 vertices->push_back(osg::Vec3(node1.X(), node1.Y(), node1.Z()));
113 vertices->push_back(osg::Vec3(node2.X(), node2.Y(), node2.Z()));
114 vertices->push_back(osg::Vec3(node3.X(), node3.Y(), node3.Z()));
115
116 normals->push_back(osg::Vec3(normal.X(), normal.Y(),normal.Z()));
117 }
118
119 triGeom->setVertexArray(vertices.get());
120 triGeom->addPrimitiveSet(new osg::DrawArrays(osg::PrimitiveSet::TRIANGLES, 0, vertices->size()));
121 triGeom->setNormalArray(normals);
122 triGeom->setNormalBinding(osg::Geometry::BIND_PER_PRIMITIVE);
123
124 geode->addDrawable(triGeom);
125
126 return geode.release();
127 }
128
129 int main(int argc, char* argv[])
130 {
131 osgViewer::Viewer myViewer;
132
133 std::string strFile;
134
135 (argc > 1) ? strFile = argv[1] : strFile = "ChineseDragon-10kv.off";
136
137 myViewer.setSceneData(buildMesh(strFile));
138
139 myViewer.addEventHandler(new osgGA::StateSetManipulator(myViewer.getCamera()->getOrCreateStateSet()));
140 myViewer.addEventHandler(new osgViewer::StatsHandler);
141 myViewer.addEventHandler(new osgViewer::WindowSizeHandler);
142
143 return myViewer.run();
144 }
程序效果圖如下所示：
Figure 3.1 ChineseDragon-10kv.off
Figure 3.2 Camel.off
Figure 3.3 cow.off
Figure 3.4 elephant.off
Figure 3.5 man.off
Figure 3.6 pinion.off
Figure 3.7 spool.off
Figure 3.8 bones.off
Figure 3.9 couplingdown.off
Figure 3.10 rotor.off
Figure 3.11 joint.off
Figure 3.12 knot1.off
Figure 3.13 anchor.off
Figure 3.14 mushroom.off
Figure 3.15 sphere.off
Figure 3.16 star.off
看到這些三維模型，很有感覺(jué)！在有關(guān)計(jì)算機(jī)圖形學(xué)的期刊上有可能也會(huì)看到上面的模型。
四、結(jié)論 Conclusion
三角網(wǎng)格在計(jì)算中用來(lái)近似表示三維模型。存儲(chǔ)三角網(wǎng)格的標(biāo)準(zhǔn)方式是使用索引三角網(wǎng)格方式。結(jié)合OpenCascade中的數(shù)據(jù)結(jié)構(gòu)，將CGAL示例中的off文件在OpenSceneGraph中顯示出來(lái)，感覺(jué)很棒！