Mesh Data Structure in OpenCascade
摘要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)。程序代碼如下所示：?
/*
* 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?
看到這些三維模型，很有感覺(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é)很棒！?
如果加上osgUtil::SmoothingVisitor，效果應(yīng)該會(huì)更好。
?
PDF Version: Mesh Data Structure in OpenCascade
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
