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文件，将其表示的网格模型显示出来。程序代码如下所示：

  1 /*
  2 *    Copyright (c) 2013 eryar All Rights Reserved.
  3 *
  4 *        File    : Main.cpp
  5 *        Author  : [email protected]
  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 }

程序效果图如下所示：