而是一旦持有表面法向量都施用单位法向量可削减总计量澳门永利

Delaunay Triangulation in
OpenCascade

Surface Normal Vector in OpenCascade

eryar@163.com

摘要Abstract:表面上某一点的法向量(Normal
Vector)指的是在该点处与外表垂直的取向。对于平面,其上各点的法向是同一的,统一为那几个平面的法向。对于曲面,各点所有差其余法向量。几何对象的法向量定义了它在上空中的方向,法向量是在开展光照处理时的严重性参数。所以在展现造型算法离散曲面后的网格时,设置科学的法向量对现象的开封、光线追踪效果有一向影响。本文结合OpenCascade中代码,对其法向量的乘除办法开展解析,稍加修改即可用到实在的次序中。 

关键字Key Words:OpenCascade, Normal Vector, Mesh Normal,
OpenSceneGraph,  

eryar@163.com

一、引言 Introduction

表面上某一点的法向量(Normal
Vector)指的是在该点处与外部垂直的势头。对于平面,其上各点的法向是相同的,统一为那些平面的法向。对于曲面,因为它在微机图形中是由许多片小平面的三头形逼近期表示的,所以每一个终端的法向量都不等同。因而,曲面上每一个点的法向量总结就可以依照不一样的行使有两样的算法,则最后的浮现效果也是例外的。几何对象的法向量定义了它在空中中的方向,法向量是在举办光照处理时的重大参数。因为法向量决定了该如何总结光照,决定了该点可以吸收多少光照。 

OpenGL有很大的八面驶风,它只提须求予当前顶点法向量的函数,并不在内部具体测算其法向量,那些值由编程者自个儿依据须要安装。即便法向量并不要求指定为单位向量,不过只要持有表面法向量都使用单位法向量可收缩总结量。使用下列命令可机关将享有非单位法向量单位化:glEnable(GL_NORMALIZE),该命令也会对那些经过缩放或错切等几何变换的外表向量举办规范化。另一可用选项是点名一个法向量列表,与终极数组混合使用。 

在许多应用程序中网格上的各顶点都亟需一个表面法向量,它的用处很常见: 

l 总括光照; 

l 背面剔除; 

l 模拟粒子系统在外部的“弹跳”效果; 

l 对只须要正面而加速碰撞检测; 

一般我们在绘制几何体时都会指定法向量。当得到一个模子本人并未法向量时,则有必不可少通过现有的数据变化。经常表面法向量大概保留于三角形级或顶点级,其中的一个技术就是平均相邻三角形的表面法向量,并将结果规范化。一般可以如此只要三角形的终端按逆时针排列,通过叉乘就足以拿走外表面的法向量了。当然有些有气象下,顶点的次第是雾里看花且比较混乱的,那样就相比较劳顿了。这一个小编也尚无仔细长远钻研,推荐读者看一下《计算非固定结构系列的三头形的终点法线》那篇散文。通过平均三角形法向量求得顶点法向量是一种经验性的法门,不抱有通用性,即使很多情状下可以正确地劳作,但有些处境下依然不可以正常使用的。(以上内容摘自《OpenSceneGraph三维渲染引擎编程指南》) 

摘要:本文简要介绍了Delaunay三角剖分的基础理论,并采纳OpenCascade的三角剖分算法将边界BRep表示的几何体进行三角离散化后在OpenSceneGraph中显得。 

二、总结法向量 Finding Surface Normal Vectors

OpenGL并不只怕活动测算几何对象的法向量,而只可以由用户显式指定。法向量的持筹握算是一个彻头彻尾的几何和数学难题,那里只简不难单地区分了两种情况。 

关键字:Delaunay Triangulation、OpenCascade、OpenSceneGraph 

2.1 计算平面的法向量

率先,讲述平面法向量的总结格局。在平面内,有两条相交的线条,固然其中一条为矢量W,另一条为矢量V,且平面法向量为N。如图2.1所示,则平面法向量就卓殊七个矢量的叉积(遵守右手法则),即N=W
x V。 

澳门永利 1

Figure 2.1 Normal Vector of Plane 

比如计算一个三角形的法向就可以用它的多个终端来总计,如图2.2所示: 

澳门永利 2

Figure 2.2 Finding the normal vector of a triangle 

一、 概述

三角形剖分是平面剖分中的一个生死攸关课题,在数字图像处理、计算机三维曲面造型、有限元计算、逆向工程等世界有着广泛应用。由于三角形是平面域中的单纯形,与其他平面图形比较,其有描述方便、处理大致等特色,很适合于对复杂区域展开简化处理。因而,无论在盘算几何、统计机图形处理、格局识别、曲面逼近,还有个别元网格生成地点有大面积的行使。 

即便曲线、曲面等有准儿的方程来代表,可是在在总括机中,只好用离散的主意来逼近。如曲线可用直线段来逼近,而曲面可用多边形或三角形来表示。用多边形网格表示曲面是安顿中常常使用的格局,可以依照使用须求接纳网格的密度。利用三角形面片表示的曲面在微机图形学中也号称三角形网格。用三角网格表示曲面须要缓解多少个难题:三角形的暴发、描述、遍历、简化和减弱等,这么些标题都以计量几何研讨的规模,相关题材都足以从中找到答案。下图所示的圆柱和立方体是由OpenCascade生成,使用OpenCascade的算法离散成三角网格后在OpenSceneGraph中浮现的作用。 

澳门永利 3

Figure 1.1 Shaded Cylinder and Box 

澳门永利 4

Figure 1.2 Mesh generated by OpenCascade 

从图中能够见见,平面的三角网格成效还不易,曲面的三角形网格表示只好是相近表示,可以由此增强网格的密度来充实真实性,但相应渲染的数据量就大了。有人说OpenCascade的显得模块做得不是很好,上述办法则可以只使用OpenCascade的造型模块,再组成OpenSceneGraph来对图纸举行体现。 

三维数据交流STL格式文件中保存的都以三角面片的数量,STL文件格式是由美利哥3D
System公司支付,已被工业界认为是目前快速机动成型领域的准标准零件描述文件格式。它对三维实体描述的解释具有惟一性。几乎拥有的几何样子系统都提供STL文件数据互换接口。OpenCascade中的数据互换模块也提供对STL格式的扶助,不言而喻三角网格在几何样子系统中的主要性。 

Voronoi图和Delaunay三角剖分的应用领域极度常见:几何建模——用来寻觅三维曲面“好的”三角剖分;有限元分析——用来变化“好的”有限元网格;地理音讯系列——用来拓展空间领域分析;结晶学——用来规定合金的布局;人类学和考古学——用来规定氏族部落、首领权威、居住中央或堡垒等的震慑范围;天理学——用来规定恒星和星系的遍布;生物学生态学和林学——用来确定动植物的竞争;动物学——分析动物的领地;总结学和数码解析——用来分析总计聚合;机器人学——用来展开运动轨迹规划(在设有障碍物的气象下);形式识别——作为寻找物体骨架点的工具;生工学——用来分析毛细作用的天地;气象学——用来预计区域平均降水量;市场学——用来建立城市的商海辐射范围;以及在遥感图像处理、化学、地管理学、地质学、冶金学、数学等课程的应用等。 

正文只对OpenCascade中的三角剖分进行不难介绍,希望对三角剖分在三维几何样子方面有趣味的朋友可以对其长远钻研。水平很有限,文中不当之处欢迎批评指正、指导,联系邮箱:eryar@163.com。 

2.2 统计分析曲面的法向量

剖析曲面是由数学方程描述的平整的、可微曲面。在OpenCascade中曲面是由Geom_Surface来用参数u,
v来表示的,约等于曲面的数学方程,是曲面的可靠表示。通过统计曲面上一点u,v对应的两遍微分即可得到曲面在该点处的切线,如下图所示: 

澳门永利 5

Figure 2.3 Tangents on a surface 

关于参数u,v表示的Bezier曲面的微分统计办法如下所示: 

澳门永利 6

若须要总结参数对应点处的法向量,还亟需对那两个切向量进行叉乘即可,计算方法如下所示: 

澳门永利 7

澳门永利 8

Figure 2.4 Normal on a surface 

二、 Voronoi图

Dirichlet于1850年探究了平面点的邻域难点,Voronoi于1908年将其结果扩大到高维空间。半空间定义Voronoi图:给定平面上n个点集S,S={p1,
p2, …, pn}。定义: 

澳门永利 9

PiPj连线的垂直平分面将空间分为两半,V(Pi)表示比其余点更接近Pi的点的轨道是n-1个半平面的交,它是一个不多于n-1条边的凸多边形域,称为关联于Pi的Voronoi多边形或涉及于Pi的Voronoi域。如下图所示为关联于P1的Voronoi多边形,它是一个四边形,而n=6. 

澳门永利 10

Figure 2.1 n=6时的一种V(p1) 

对此点集S中的每一个点都足以做一个Voronoi多边形,那样的n个Voronoi多边形组成的图称为Voronoi图,记为Vor(S)。如下图所示: 

澳门永利 11

Figure 2.2 Voronoi diagram for 10 randomly points (Generated by MATLAB) 

图中的顶点和边分别名为Voronoi顶点和Voronoi边。分明,|S|=n时,Vor(S)划分平面成n个多边形域,每一个多边形域V(Pi)包蕴S中的一个点同时只蕴含S中的一个点,Vor(S)的边是S中某点对的垂直平分线上的一条线条或半直线,从而为该点对所在的三个多边形域所共有。Vor(S)中有的多边形域是无界的。 

澳门永利 12

Figure 2.3 Ten shops in a flat city and their Voronoi cells 

(http://en.wikipedia.org/wiki/Voronoi\_diagram

澳门永利 13

Figure 2.4 Voronoi tessellation in a cylinder (Voro++ library:
http://math.lbl.gov/voro++/

Voronoi图有如下性质: 

l n个点的点集S的Voronoi图至多有2n-5个顶峰和3n-6条边; 

l 逐个Voronoi点恰好是三条Voronoi边的交点; 

l 设v是Vor(S)的顶峰,则圆C(v)内不含S的别的点; 

l 点集S中点Pi的逐个近年来靠拢点确定V(Pi)的一条边; 

l Voronoi图的直线对偶图是S的一个三角形剖分; 

l
假使Pi,Pj属于S,并且经过Pi,Pj有一个不包蕴S中任何点的圆,那么线段PiPj是点集S三角剖分的一条边,反之亦建立。 

2.3 总计多边形的法向量

在OpenGL中,那种情景占了绝大多数。求平均多边形的法向量,利用不在同平昔线上的多方面形多个极端v1,
v2, v3,则多个矢量的叉积((v2 – v1)x(v3 –
v1))垂直于多边形,即为该多边形的法向量,计算后要求经过规范化处理。 

对于求多边形网格上各顶点上的法向量,由于各个终端同时放在多少个不等的绝一大半形边界上,则需须要出周围多少个多边形的法向量,然后做加权平均。一般的话,能够利用种种多边形的面积做为加权的权值。 

一般来说图所示,曲面顶点P的法向就也等于其隔壁的多少个平面的法向平均值: 

澳门永利 14

Figure 2. 曲面顶点的平均法向总括 

注:当总括多边形网格表示的曲面时,最好是接纳平均法向的法子来计算。当曲面是用参数方程来代表时,就足以用求微分和叉乘的点子来直接总括法向量,不再需求运用平均法向了。 

三、 Delaunay三角剖分 

三、程序完毕 Demo Code

1. 二维实数域上的三角剖分

假使V是二维实数域上的有限点集,边e是由点集中的点作端点构成的封闭线段,E为e的会聚,那么该点集V的一个三角形剖分T=(V,E)是一个平面图: 

l 除了端点,平面图中的边不包蕴点集中的任何点; 

l 没有相交边; 

l 平面图中负有的面都以三角面,且持有三角面的合集是点集V的凸包。 

3.1 OpenCascade中曲面法向量的估算 Compute normal in OpenCascade

在OpenCascade准将形状数据保存为STL格式时就涉及到了将造型三角剖分及其法向量的测算完结。其计算方式如上所述,也是分成二种方式: 

l 参数方程表示的曲面; 

l 平面; 

l 网格; 

将其代码列出如下: 

//function computes normals for surface
static void Normal(const TopoDS_Face&  aFace,
           Poly_Connect&       pc,
           TColgp_Array1OfDir& Nor)
{
  const Handle(Poly_Triangulation)& T = pc.Triangulation();
  BRepAdaptor_Surface S;
  Standard_Boolean hasUV = T->HasUVNodes();
  Standard_Integer i;
  TopLoc_Location l;
  Handle(Geom_Surface) GS = BRep_Tool::Surface(aFace, l);

  if (hasUV && !GS.IsNull()) {
    Standard_Boolean OK = Standard_True;
    gp_Vec D1U,D1V;
    gp_Vec D2U,D2V,D2UV;
    gp_Pnt P;
    Standard_Real U, V;
    CSLib_DerivativeStatus Status;
    CSLib_NormalStatus NStat;
    S.Initialize(aFace, Standard_False);
    const TColgp_Array1OfPnt2d& UVNodes = T->UVNodes();
    if (!S.GetType() == GeomAbs_Plane) {
      for (i = UVNodes.Lower(); i <= UVNodes.Upper(); i++) {
    U = UVNodes(i).X();
    V = UVNodes(i).Y();
    S.D1(U,V,P,D1U,D1V);
    CSLib::Normal(D1U,D1V,Precision::Angular(),Status,Nor(i));
    if (Status != CSLib_Done) {
      S.D2(U,V,P,D1U,D1V,D2U,D2V,D2UV);
      CSLib::Normal(D1U,D1V,D2U,D2V,D2UV,Precision::Angular(),OK,NStat,Nor(i));
    }
    if (aFace.Orientation() == TopAbs_REVERSED) (Nor(i)).Reverse();
      }
    }
    else {
      gp_Dir NPlane;
      U = UVNodes(UVNodes.Lower()).X();
      V = UVNodes(UVNodes.Lower()).Y();
      S.D1(U,V,P,D1U,D1V);
      CSLib::Normal(D1U,D1V,Precision::Angular(),Status,NPlane);
      if (Status != CSLib_Done) {
    S.D2(U,V,P,D1U,D1V,D2U,D2V,D2UV);
    CSLib::Normal(D1U,D1V,D2U,D2V,D2UV,Precision::Angular(),OK,NStat,NPlane);
      }
      if (aFace.Orientation() == TopAbs_REVERSED) NPlane.Reverse();
      Nor.Init(NPlane);

    }
  }
  else {
    const TColgp_Array1OfPnt& Nodes = T->Nodes();
    Standard_Integer n[3];
    const Poly_Array1OfTriangle& triangles = T->Triangles();

    for (i = Nodes.Lower(); i <= Nodes.Upper(); i++) {
      gp_XYZ eqPlan(0, 0, 0);
      for (pc.Initialize(i);  pc.More(); pc.Next()) {
    triangles(pc.Value()).Get(n[0], n[1], n[2]);
    gp_XYZ v1(Nodes(n[1]).Coord()-Nodes(n[0]).Coord());
    gp_XYZ v2(Nodes(n[2]).Coord()-Nodes(n[1]).Coord());
    eqPlan += (v1^v2).Normalized();
      }
      Nor(i) = gp_Dir(eqPlan);
      if (aFace.Orientation() == TopAbs_REVERSED) (Nor(i)).Reverse();
    }
  }

}

假定是参数方程表示的曲面,若不是平面,则依照切线的叉乘来计量各顶点处的法向量;如果平面,则只总计一个终极处理的法向量,减少总计量。
即便离散后的网格面,则基于三角形的法向量的总括办法来计量各个顶点处的法向量。 

2. Delaunay边

如果E中的一条边(两端点a,b),e满意下列标准,则称之为Delaunay边:存在一个圆经过a,b两点,圆内不分包点集V中的任何的点。这一特征又叫做空圆特性。 

3.2 OpenSceneGraph中网格曲面的法向量统计 Compute normal in OpenSceneGraph

浮动顶点法向量(osgUtil::SmoothingVisitor)类继承自osg::NodeVisitor类,选用Visitor情势,遍历场景中的几何体,生成顶点法向量。osgUtil::SmoothingVisitor的使用很有利。对算法已毕感兴趣的读者可以组合源程序来精通商量。 

3. Delaunay三角剖分

假定点集V的一个三角剖分T中只包括Delaunay边,那么该三角剖分称为Delaunay剖分。 

近来点意思下的Voronoi图的双双图实际上是点集的一种三角剖分,该三角剖分就是Delaunay剖分(表示为DT(S)),其中各个三角形的外接圆不包罗点集中的其他任何点。因而,在布局点集的Voronoi图之后,再作其对偶图,即对每条Voronoi边作通过点集中某两点的垂直平分线,即拿到Delaunay三角剖分。 

澳门永利 15

Figure 3.1 Delaunay Triangulation (Generated by MATLAB) 

再看多少个图片,加深对Delaunay三角剖分的了解: 

澳门永利 16

Figure 3.2 Delaunay Edge  

澳门永利 17

Figure 3.3 Illustrate Delaunay Edge 

澳门永利 18

Figure 3.4 Delaunay Edge 

四、结论 Conclusion

OpenCascascade中有曲面的参数表示,所以对那类曲面可以得用参数方程总括出曲面上的巅峰的可相信法向量。对于从未参数表示的网格曲面,能够用平均法向量的方法来总结出一个法向量。 

OpenSceneGraph中也有火速计算网格曲面法向量的类osgUtil::SmoothingVisitor。 

4. Delaunay三角剖分的特色

l
1978年Sibson评释了在二维的情形下,在点集的有所三角剖分中,Delaunay三角剖分使得生成的三角的最小角达到最大(max-min
angle)。因为这一风味,对于给定点集的Delaunay三角剖分总是尽或者防止“瘦长”三角形,自动向等边三角形逼近; 

l 局部优化与共同体优化(locally optimal and globally optimal); 

l Delaunay空洞(cavity)与部分重连(local reconnection); 

  1. 经文的Delaunay三角剖分算法 

此时此刻常用的算法分为三种,有扫描线法(Sweepline)、随机增量法(Incremental)、分治法(Divide
and Conquer)等。 

经文的Delaunay三角剖分算法主要有两类:Bowyer/沃特son算法和局地变换法。 

l
Bowyer/沃特son算法又称为Delaunay空洞算法或加点法,以Bowyer和沃特son算法为表示。从一个三角形起先,每一遍加一个点,保险每一步得到的脚下三角形是一对优化的。以英帝国Bath大学数学分校Bowyer,格林,Sibson为代表的测算Dirichlet图的办法属于加点法,是较早成名的算法之一;以澳大路易斯维尔米兰高校地学系沃特son为代表的空外接球法也属于加点法。加点法算法简明,是当前接纳最多的算法,该办法运用了Delaunay空洞性质。Bowyer/Watson算法的长处是与空间的维数毫不相关,并且算法在促成上比部分变换算法不难。该算法在新点参预到Delaunay网格时,部分外接球包括新点的三角单元不再适合Delaunay属性,则这几个三角形单元被去除,形成Delaunay空洞,然后算法将新点与重组空洞的各个极端相连生成一个新边,依照空球属性可以印证这几个新边都是一些Delaunay的,因而新生成的三角网格仍是Delaunay的。 

澳门永利 19

Figure 3.5 Illustration of 2D Bowyer/Watson algorithm for Delaunay
Triangulation 

l
局地变换法又叫做换边、换面法。当使用一些变换法完结增量式点集的Delaunay三角剖分时,首先定位新参与点所在的三角形,然后在网格中进入多个新的连日该三角形顶点与新顶点的边,若该新点位于某条边上,则该边被删除,四条连接该新点的边被投入。最终,在通过换边方法对该新点的有的区域内的边举行检测和转移,重新维护网格的Delaunay性质。局地变换法的另一个优点是其得以对已存在的三角网格开展优化,使其更换成为Delaunay三角网格,该措施的毛病则是当算法增添到高维空间时变得相比复杂。 

五、参考资料 References

  1. Kelly Dempski, Focus on Curves and Surfaces, Premier Press, 2003 

  2. 王锐,钱学雷,OpenSceneGraph三维渲染引擎布置与实践,武大大学出版社 

3.
肖鹏,刘更代,徐明亮,OpenSceneGraph三维渲染引擎编程指南,交大高校出版社 

 

PDF Version: Surface Normal
Vector

四、 Delaunay三角剖分在OpenCascade的运用

OpenCascade中网格剖分的包紧要有BRepMesh、MeshAlgo、MeshVS,其中,类MeshAlgo_Delaunay使用算法沃特son来进展Delaunay三角剖分。从类StlTransfer中的注释The
triangulation is computed with the Delaunay algorithm implemented in
package
BRepMesh.可以见见包BRepMesh就是Delaunay三角剖分的现实贯彻。使用方式如下: 

BRepMesh::Mesh (aShape, Deflection); 

其一函数主即使用来对拓扑形状进行三角剖分。以下通过将一个圆柱三角剖分为例表明什么将一个拓扑形状进行三角剖分并将结果开展可视化。 

/**
*    Copyright (c) 2013 eryar All Rights Reserved.
*
*        File    : Main.cpp
*        Author  : eryar@163.com
*        Date    : 2013-05-26
*        Version : 0.1
*
*    Description : Use BRepMesh_Delaun class to learn 
*                  Delaunay's triangulation algorithm.
*
*/
// Open Cascade library.
#include <gp_Pnt.hxx>
#include <gp_Pln.hxx>
#include <BRep_Tool.hxx>
#include <TopoDS.hxx>
#include <TopoDS_Edge.hxx>
#include <TopoDS_Wire.hxx>
#include <TopoDS_Face.hxx>
#include <BRepBuilderAPI_MakeEdge.hxx>
#include <BRepBuilderAPI_MakeWire.hxx>
#include <BRepBuilderAPI_MakeFace.hxx>

#include <BRepPrimAPI_MakeBox.hxx>
#include <BRepPrimAPI_MakeCone.hxx>
#include <BRepPrimAPI_MakeCylinder.hxx>
#include <BRepPrimApI_MakeSphere.hxx>

#include <BRepMesh.hxx>
#include <TopExp_Explorer.hxx>
#include <Poly_Triangulation.hxx>
#include <TShort_Array1OfShortReal.hxx>

#pragma comment(lib, "TKernel.lib")
#pragma comment(lib, "TKMath.lib")
#pragma comment(lib, "TKBRep.lib")
#pragma comment(lib, "TKPrim.lib")
#pragma comment(lib, "TKMesh.lib")
#pragma comment(lib, "TKTopAlgo.lib")

// OpenSceneGraph library.
#include <osgDB/ReadFile>
#include <osgViewer/Viewer>
#include <osgViewer/ViewerEventHandlers>
#include <osgGA/StateSetManipulator>

#pragma comment(lib, "osgd.lib")
#pragma comment(lib, "osgDbd.lib")
#pragma comment(lib, "osgGAd.lib")
#pragma comment(lib, "osgViewerd.lib")

osg::Node* BuildShapeMesh(const TopoDS_Shape& aShape)
{
    osg::ref_ptr<osg::Group> root = new osg::Group();
    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();

    BRepMesh::Mesh(aShape, 1);

    TopExp_Explorer faceExplorer;

    for (faceExplorer.Init(aShape, TopAbs_FACE); faceExplorer.More(); faceExplorer.Next())
    {
        TopLoc_Location loc;
        TopoDS_Face aFace = TopoDS::Face(faceExplorer.Current());

        Handle_Poly_Triangulation triFace = BRep_Tool::Triangulation(aFace, loc);
        Standard_Integer nTriangles = triFace->NbTriangles();

        gp_Pnt vertex1;
        gp_Pnt vertex2;
        gp_Pnt vertex3;

        Standard_Integer nVertexIndex1 = 0;
        Standard_Integer nVertexIndex2 = 0;
        Standard_Integer nVertexIndex3 = 0;

        TColgp_Array1OfPnt nodes(1, triFace->NbNodes());
        Poly_Array1OfTriangle triangles(1, triFace->NbTriangles());

        nodes = triFace->Nodes();
        triangles = triFace->Triangles();       

        for (Standard_Integer i = 1; i <= nTriangles; i++)
        {
            Poly_Triangle aTriangle = triangles.Value(i);

            aTriangle.Get(nVertexIndex1, nVertexIndex2, nVertexIndex3);

            vertex1 = nodes.Value(nVertexIndex1);
            vertex2 = nodes.Value(nVertexIndex2);
            vertex3 = nodes.Value(nVertexIndex3);

            gp_XYZ vector12(vertex2.XYZ() - vertex1.XYZ());
            gp_XYZ vector13(vertex3.XYZ() - vertex1.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(vertex1.X(), vertex1.Y(), vertex1.Z()));
            vertices->push_back(osg::Vec3(vertex2.X(), vertex2.Y(), vertex2.Z()));
            vertices->push_back(osg::Vec3(vertex3.X(), vertex3.Y(), vertex3.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);

    root->addChild(geode);

    return root.release();
}

int main(int argc, char* argv[])
{
    osgViewer::Viewer myViewer;
    osg::ref_ptr<osg::Group> root = new osg::Group();

    root->addChild(BuildShapeMesh(BRepPrimAPI_MakeCylinder(.6, 1)));

    myViewer.setSceneData(root);

    myViewer.addEventHandler(new osgGA::StateSetManipulator(myViewer.getCamera()->getOrCreateStateSet()));
    myViewer.addEventHandler(new osgViewer::StatsHandler);
    myViewer.addEventHandler(new osgViewer::WindowSizeHandler);

    return myViewer.run();
}

结果如下图所示: 

澳门永利 20

Figure 4.1 Cylinder mesh generated by BRepMesh::Mesh 

BRepMesh::Mesh是透过包装的,便于对拓扑形状进行三角剖分。以下通过一个简约的例子来声明直接行使BRepMesh_Delaun的方法: 

/**
*    Copyright (c) 2013 eryar All Rights Reserved.
*
*        File    : Main.cpp
*        Author  : eryar@163.com
*        Date    : 2013-05-26
*        Version : 0.1
*
*    Description : Use BRepMesh_Delaun class to learn 
*                  Delaunay's triangulation algorithm.
*
*/

#include <BRepMesh_Edge.hxx>
#include <BRepMesh_Delaun.hxx>
#include <BRepMesh_Array1OfVertexOfDelaun.hxx>
#include <TColStd_MapIteratorOfMapOfInteger.hxx>

#pragma comment(lib, "TKernel.lib")
#pragma comment(lib, "TKMesh.lib")

int main(int argc, char* argv[])
{
    BRepMesh_Array1OfVertexOfDelaun vertices(1, 4);

    vertices.SetValue(1, BRepMesh_Vertex(0, 0, MeshDS_Free));
    vertices.SetValue(2, BRepMesh_Vertex(1, 0, MeshDS_Free));
    vertices.SetValue(3, BRepMesh_Vertex(1, 1, MeshDS_Free));
    vertices.SetValue(4, BRepMesh_Vertex(0, 1, MeshDS_Free));

    BRepMesh_Delaun triangulation(vertices);
    //triangulation.AddVertex(BRepMesh_Vertex(0.5, 0.5, MeshDS_OnSurface));
    Handle_BRepMesh_DataStructureOfDelaun meshData = triangulation.Result();

    std::cout<<"Iterate Mesh Triangles:"<<std::endl;

    MeshDS_MapOfInteger::Iterator triDom;
    for (triDom.Initialize(meshData->ElemOfDomain()); triDom.More(); triDom.Next())
    {
        Standard_Integer triId = triDom.Key();
        const BRepMesh_Triangle& curTri = meshData->GetElement(triId);

        Standard_Integer vertexIndex1 = 0;
        Standard_Integer vertexIndex2 = 0;
        Standard_Integer vertexIndex3 = 0;

        Standard_Integer edgeIndex1 = 0;
        Standard_Integer edgeIndex2 = 0;
        Standard_Integer edgeIndex3 = 0;

        Standard_Boolean o1 = Standard_False;
        Standard_Boolean o2 = Standard_False;
        Standard_Boolean o3 = Standard_False;

        curTri.Edges(edgeIndex1, edgeIndex2, edgeIndex3, o1, o2, o3);

        const BRepMesh_Edge& edge1 = meshData->GetLink(edgeIndex1);
        const BRepMesh_Edge& edge2 = meshData->GetLink(edgeIndex2);
        const BRepMesh_Edge& edge3 = meshData->GetLink(edgeIndex3);

        vertexIndex1 = (o1? edge1.FirstNode(): edge1.LastNode());
        vertexIndex2 = (o1? edge1.LastNode() : edge1.FirstNode());
        vertexIndex3 = (o2? edge2.LastNode() : edge2.FirstNode());

        const BRepMesh_Vertex& vertex1 = meshData->GetNode(vertexIndex1);
        const BRepMesh_Vertex& vertex2 = meshData->GetNode(vertexIndex2);
        const BRepMesh_Vertex& vertex3 = meshData->GetNode(vertexIndex3);

        const gp_XY& p1 = vertex1.Coord();
        const gp_XY& p2 = vertex2.Coord();
        const gp_XY& p3 = vertex3.Coord();

        std::cout<<"--------"<<std::endl;
        std::cout<<p1.X()<<" , "<<p1.Y()<<std::endl;
        std::cout<<p2.X()<<" , "<<p2.Y()<<std::endl;
        std::cout<<p3.X()<<" , "<<p3.Y()<<std::endl;
        std::cout<<"========"<<std::endl;
    }

    return 0;
}

上述顺序是以一个正方形为例,使用BRepMesh_Delaun三角剖分的结果为五个三角形,如下所示: 

Iterate Mesh Triangles: 
——– 
1 , 1 
0 , 0 
1 , 0 
======== 
——– 
1 , 1 
0 , 1 
0 , 0 
======== 

 以上结果都以二维空间上的,三维空间中的使用格局可以参考类:BRepMesh_法斯特DiscretFace。这些类表明了什么样将一个面拓展网格划分。 

五、 结论

Delaunay三角剖分理论在三维几何样子中如故比较紧要的,通过对造型的三角形剖分,不仅能够对其进展可视化,还便宜对造型做越来越的处理,如消隐、光照处理等。通过对OpenCascade中三角剖分算法的选拔,以更为精通三角剖分理论应用及其算法完毕。 

六、 参考资料

  1. 周培德. 计算几何—算法设计与分析. 清华大学出版社, 2011 

  2. 李海生. Delaunay三角剖分理论及可视化应用研讨. 金沙萨农林学院出版社,
    2010 

  3. 何援军. 总结机图形学. 机械工业出版社, 2010 

  4. 周元峰, 孙峰, 王文平, 汪嘉业, 张彩明.
    基于局地修复的运动数据点Delaunay三角化连忙更新方法.
    总计机帮衬设计与图片学学报, 2011, 12: 2006-1012 

  5. http://en.wikipedia.org/wiki/Voronoi_diagram

 

PDF Version: Delaunay Triangulation in
OpenCascade

相关文章