Mesh Data Structure in OpenCascade
摘要Abstract： 本文對網格數據結構作簡要介紹，并結合使用OpenCascade中的數據結構，將網格數據在OpenSceneGraph中可視化。?
關鍵字KeyWords： OpenCascade、OpenSceneGraph、Triangulation、Mesh Data Structure?
一、引言 Introduction
三角網格就是全部由三角形組成的多邊形網格。多邊形和三角網格在圖形學和建模中廣泛使用，用來模擬復雜物體的表面，如建筑、車輛、人體，當然，還有茶壺等自由曲面。任意多邊形網格都能轉換成三角網格。三角網格以其簡單性而吸引人，相對于一般多邊形網格許多操作對三角網格列容易。?
常用的網格數據文件有：?
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?
有些文件以文本方式保存，有些可以以二進制方式保存。如下圖所示為OBJ文件的格式：?
Figure 1.1 Wavefront OBJ File Format?
l Vertices?
n 以‘V’開始；?
n 其后為坐標值（x,y,z）；?
l Faces?
n 以‘F’開始；?
n 其后為面的頂點索引值；?
l Other properties?
n Normal, texture coordinates, material, etc.?
二、三角網格的表示 Mesh Data Structure?
三角網格為一個三角形列表，所以最直接的表示方法是用三角形數組：
struct
Triangle
{
Vector3 p[
3
];
};
struct
TriangleMesh
{
int
triCount;
Triangle
*
triList;
};
對于某些應用程序，這種表示方法已經足夠。然而，術語“網格”隱含的相鄰三角形的連通性未在這種簡單表示中有任何體現。實際應用中出現的三角網格，每個三角形都和其他三角形共享邊。于是三角網格需要存儲三類信息：?
l 頂點。每個三角形有三個頂點，各頂點都有可能和其他三角形共享；?
l 邊。連接兩個頂點的邊，每個三角形有三條邊；?
l 面。每個三角形對應一個面。我們可以用頂點或邊列表表示面；?
根據應用程序的不同，有多種有效的網格表示方法。常用的一種標準的存儲格式為索引三角網格。?
在索引三角網格中，我們維護了兩個列表：頂點表與三角形表。每個頂點包含一個3D位置，也可能有表面法向量、紋理映射坐標、光照值附加數據。每個三角形由頂點列表的三個索引值組成。通常頂點列出的順序是非常重要的，因為我們必須考慮面的“正面”和“反面”。從前面看時，我們將用順時針方向列出頂點。?
在OpenCascade中，分別用類TColgp_Array1OfPnt和Poly_Array1OfTriangle表存儲頂點表和三角形表。注意到索引三角形列表中的鄰接信息是隱含的，即邊信息沒有存儲，但我們可以通過搜索三角形表找出公共邊。和前面“三角形數組”方式相比，這種方式確實能節省不少空間。原因是信息存于頂點級別，它的整數索引比之三角形數組里存儲的頂點重復率要小得多。實踐中，三角網里確實有大量的連接性問題。?
簡單索引三角網格對于基本應用已經足夠了。但為更加高效地實現某些操作還可以進一步改進。主要的問題是鄰接信息沒有顯式表達，所以必須從三角形列表中搜索。另一種表達方法可以常數時間內取得這種信息。方法是顯式維護一個邊列表，每邊由兩個端點定義，同時維護一個共享該邊的三角形列表。這樣三角形可視為三條邊而非三個點的列表，也就是說它是邊列表的索引。該思想的一個擴展稱作“Winged Edge”模型（翼邊模型），對每一頂點，存儲使用該點的邊的索引。這樣三角形和邊都可以通過定位點列表快速查找。?
大多數顯卡并不直接支持索引三角網。渲染三角形時，一般是將三個頂點同時提交。這樣，共享頂點會多次提交，三角形用到一次就提交一次。因為內存和圖形硬件間的數據傳輸是瓶頸，所以許多API和硬件支持特殊三角網格式以減少傳輸量。基本思想是排序點和面，使得顯存中已有的三角形不需要再次傳輸。?
從最高靈活性到最低靈活性，我們討論三種方案：?
n 頂點緩存；?
n 三角帶Triangle Strip；?
n 三角扇Triangle Fan；?
三、程序示例 Code Example
在安裝好的CGAL庫中發現其例子中有很多off文件，其格式同常見的網格文件格式基本相同，結合OpenCascade和OpenSceneGraph，讀取off文件，將其表示的網格模型顯示出來。程序代碼如下所示：?
/*
* Copyright (c) 2013 eryar All Rights Reserved.
*
* File : Main.cpp
* Author : eryar@163.com
* Date : 2013-08-10 18:02
* Version : V1.0
*
* Description : Mesh Viewer for the general mesh file format.
* Poly_Triangulation data structure can save vertices and triangle index.
*
*/
//
OpenSceneGraph library.
#include <osgDB/ReadFile>
#include
<osgViewer/Viewer>
#include
<osgGA/StateSetManipulator>
#include
<osgViewer/ViewerEventHandlers>
#pragma
comment(lib, "osgd.lib")
#pragma
comment(lib, "osgDBd.lib")
#pragma
comment(lib, "osgGAd.lib")
#pragma
comment(lib, "osgViewerd.lib")
//
OpenCascade library.
#include <TColgp_Array1OfPnt.hxx>
#include
<Poly_Array1OfTriangle.hxx>
#include
<Poly_Triangulation.hxx>
#pragma
comment(lib, "TKernel.lib")
#pragma
comment(lib, "TKMath.lib")
/*
*
* @breif Build the mesh from *.off file.
*/
osg::Node
* buildMesh(
const
std::
string
&
fileName)
{
std::ifstream offFile(fileName.c_str());
std::
string
strBuffer;
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();
Standard_Integer nbNodes
=
0
;
Standard_Integer nbTriangles
=
0
;
//
Ignore "OFF"
offFile>>
strBuffer;
offFile
>>nbNodes>>nbTriangles>>
strBuffer;
TColgp_Array1OfPnt nodes(
0
, nbNodes);
Poly_Array1OfTriangle triangles(
0
, nbTriangles);
//
Read node coordinate and store them.
Standard_Real dx =
0.0
;
Standard_Real dy
=
0.0
;
Standard_Real dz
=
0.0
;
for
(Standard_Integer i =
0
; i < nbNodes; i++
)
{
offFile
>>dx>>dy>>
dz;
nodes(i).SetCoord(dx, dy, dz);
}
//
Read the triangles
Standard_Integer ni =
0
;
Standard_Integer n1
=
0
;
Standard_Integer n2
=
0
;
Standard_Integer n3
=
0
;
for
(Standard_Integer i =
0
; i < nbTriangles; i++
)
{
offFile
>>ni>>n1>>n2>>
n3;
triangles(i).Set(n1, n2, n3);
}
//
Construct the mesh data by Poly_Triangulation.
gp_Pnt node1;
gp_Pnt node2;
gp_Pnt node3;
Poly_Triangle triangle;
Handle_Poly_Triangulation T
=
new
Poly_Triangulation(nodes, triangles);
for
(Standard_Integer i =
0
; i < nbTriangles; i++
)
{
triangle
=
triangles.Value(i);
triangle.Get(n1, n2, n3);
node1
=
nodes.Value(n1);
node2
=
nodes.Value(n2);
node3
=
nodes.Value(n3);
gp_XYZ vector12(node2.XYZ()
-
node1.XYZ());
gp_XYZ vector13(node3.XYZ()
-
node1.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(node1.X(), node1.Y(), node1.Z()));
vertices
->
push_back(osg::Vec3(node2.X(), node2.Y(), node2.Z()));
vertices
->
push_back(osg::Vec3(node3.X(), node3.Y(), node3.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);
return
geode.release();
}
int
main(
int
argc,
char
*
argv[])
{
osgViewer::Viewer myViewer;
std::
string
strFile;
(argc
>
1
) ? strFile = argv[
1
] : strFile =
"
ChineseDragon-10kv.off
"
;
myViewer.setSceneData(buildMesh(strFile));
myViewer.addEventHandler(
new
osgGA::StateSetManipulator(myViewer.getCamera()->
getOrCreateStateSet()));
myViewer.addEventHandler(
new
osgViewer::StatsHandler);
myViewer.addEventHandler(
new
osgViewer::WindowSizeHandler);
return
myViewer.run();
}
程序效果圖如下所示：?
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?
看到這些三維模型，很有感覺！在有關計算機圖形學的期刊上有可能也會看到上面的模型。?
四、結論 Conclusion
三角網格在計算中用來近似表示三維模型。存儲三角網格的標準方式是使用索引三角網格方式。結合OpenCascade中的數據結構，將CGAL示例中的off文件在OpenSceneGraph中顯示出來，感覺很棒！?
如果加上osgUtil::SmoothingVisitor，效果應該會更好。
?
PDF Version: Mesh Data Structure in OpenCascade
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
