新普金娱乐网址


顾人不相忘,思君如既往。

全然没有经验,一发手便起出「全世界最好好之食堂」!室内上菜、室外采收食材,这对英国手足打造出全新的进食更

Delaunay Triangulation in OpenCascade

  • 十月 13, 2018
  • 地理
  • 没有评论

二、 Voronoi图

Dirichlet于1850年研究了平面点的邻域问题,Voronoi于1908年拿其结果扩展及高维空间。半上空定义Voronoi图:给一定平面上n个点集S,S={p1,
p2, …, pn}。定义: 

图片 1

PiPj连线的垂直平分面将空间分为两半,V(Pi)表示比较其余点又类似Pi的触发之轨迹是n-1单半面的及,它是一个休多于n-1条边的阳多边形域,称为关联于Pi的Voronoi多边形或提到于Pi的Voronoi域。如下图所示为涉及于P1的Voronoi多边形,它是一个季止形,而n=6. 

图片 2

Figure 2.1 n=6时之一律种植V(p1) 

于点集S中的每个点还得以开一个Voronoi多边形,这样的n个Voronoi多边形组成的图称为Voronoi图,记否Vor(S)。如下图所示: 

图片 3

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)中有的多边形域是无界的。 

图片 4

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

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

图片 5

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三角剖分的同一长条边,反的也建立。 

Visualize Surface by Delaunay Triangulator

eryar@163.com

Abstract. Delaunay Triangulation is
the core algorithm for mesh generation. By Delaunay Triangulator you can
make a general method to visualize geometry surfaces, so does
OpenCascade. The paper focus on the geometry surfaces visualization,
include the surfaces with holes.

Key words. OpenCascade, Delaunay
Triangulator, OpenSceneGraph, Mesh, NURBS

1. Introduction

型数据最终使于显示器上输出,需要出统一的处理方式。对于曲线而言,只需要在曲线上取一定之接触总是成线,就足以据此来逼显示曲线了。对于曲面而言,可以就此三角网格来逼曲面。对于参数表示的曲线,求曲线之接触十分易,只要让起参数就足以赢得参数对应的曲线上之触发。对于参数表示的曲面,情况如果复杂些了,如何得到三角网格呢? 

通过boolean
operation后,会生出若干孔有,这些皮的孔如何用联合之不二法门可视化呢?对于曲面的可视化也势必是统一、简单的方法。程序开发最终追求的都是简简单单、统一,这样代码才亮淡雅。如果代码看上去十分复杂,到处是还代码,暴露出来的接口也异常自由,完全违背单一任务规范及Demeter法则,开发出来的软件用起来自然为十分辛苦,这对程序员和软件用户都是噩梦。这样的代码一定生重构和改良之空间,最终落得程序开发人员和软件的用户还痛快的状态。书山有路勤为径,学海无涯苦作舟,拒绝保守、懒惰,不思进取。 

言归正传,本文主要采用OpenSceneGraph中的Delaunay
Triangulator来针对OpenCascade中之自由参数曲面可视化,即曲面可视化的联合算法。在明曲面可视化的底子及,可针对NURBS曲面的可视化,有助于直观来修NURBS理论。 

言到NURBS理论,又是追统一、简单的结果。由于在数学与算法上的精粹性质,以及在工业领域的中标利用,使得NURBS得到了大幅度的推广。NURBS在CAD/CAM/CAE领域受到所从的意图类似于英语在是与小买卖中的企图。因此,想从CAD,必须理解NURBS。NURBS的重要性作用就是是统一了曲线曲面的数学模型,使软件对曲线曲面的处理方式相同,且下NURBS进行统筹好直观,几乎每个工具及算法都发生一个容易掌握的几乎哪解释。 

给CAD软件用户采取简单,得到便利,就假设出照应的技艺(NURBS)支持。至于NURBS是Non-Uniform
Rational B-Spline还是Nobody Understands Rational
B-Spline,普通用户是无关心的。网格化的算法也是接近,让三维模型可视化变得简单、统一,至于是运Delaunay
Triangulation还是别算法,对于图片显示接口如OpenGL也未体贴,他一味管画三角形就哼。然而高效之网格化算法也是一个技艺难关。如果不仅要懂得其然而且还要知其所以然,都使付出努力。 

2. Visualize Geometry Surface

网格生成技术是钻什么拿加以的空中离散为简便的几何单元的艺术。三角网格和四面体网格是迄今为止最常用的非组织形式,它可很好地逼近边界,描述结构复杂的空间。Delaunay三角、四面体剖分由于该有得天独厚的数学基础,对网格的一些控制能力强,网格单元自动往刚刚三角、四面体逼近等帅性状,近年来被了好多天地的钻人口之关注,在科学计算可视化、图形学三维表示、石油地质勘探、地理信息体系、逆向工程、医学图像处理等领域有所明确的以前景。 

在数字地形建模中,不规则三角网(TIN)通过由不规则离散分布之数据点生成的接连三角面来逼地形表面。就发表地形信息角度而言,TIN模型的助益是它能够因为不同层次之分辨率来描述地貌表面。TIN模型在一定特定分辨率下能用重新少之空间和时间重复精确地代表复杂的外表。特别是本土形包含有大量特色,如断裂线、构造线时,TIN模型能重新好地顾及这些特点,从而更精确地发挥地表形态。关于Delaunay算法,可以参照相关书籍或网络资源自己实现,或是使用开源库,如Triangle,
CGAL等。本文主要是采取OpenSceneGraph中成算法来用参数曲面可视化。 

OpenSceneGraph中Delaunay的下非常简单,只待将点集传给DelaunayTriangulator即可,下面代码示例将OpenCascade中任意参数曲面的参数空间距离散成三角网格,再映射到三维空间,将曲面可视化。 

osg::Node* BuildSurface(const Handle_Geom_Surface &theSurface)
{
    osg::ref_ptr<osg::Geode> aGeode = new osg::Geode();
    osg::ref_ptr<osg::Geometry> aGeometry = new osg::Geometry();

    osg::ref_ptr<osg::Vec3Array> aUVPoints = new osg::Vec3Array();
    osg::ref_ptr<osg::Vec3Array> aPoints = new osg::Vec3Array();

    osg::ref_ptr<osgUtil::DelaunayTriangulator> dt = new osgUtil::DelaunayTriangulator();

    // build triangulation for the parametric space.
    Standard_Real u1 = 0.0;
    Standard_Real u2 = 0.0;
    Standard_Real v1 = 0.0;
    Standard_Real v2 = 0.0;

    theSurface->Bounds(u1, u2, v1, v2);

    Precision::IsNegativeInfinite(u1) ? u1 = -1.0: u1;
    Precision::IsPositiveInfinite(u2) ? u2 =  1.0: u2;
    Precision::IsNegativeInfinite(v1) ? v1 = -1.0: v1;
    Precision::IsPositiveInfinite(v2) ? v2 =  1.0: v2;

    // tesselate the parametric space.
    Standard_Integer aStep = 30;
    Standard_Real uDelta = (u2 - u1) / aStep;
    Standard_Real vDelta = (v2 - v1) / aStep;

    for (Standard_Integer i = 0; i <= aStep; ++i)
    {
        for (Standard_Integer j = 0; j <= aStep; ++j)
        {
            Standard_Real u = u1 + i * uDelta;
            Standard_Real v = v1 + j * vDelta;

            aUVPoints->push_back(osg::Vec3(u, v, 0.0));
        }
    }

    // triangulate the parametric space.
    dt->setInputPointArray(aUVPoints);
    dt->triangulate();

    for (osg::Vec3Array::const_iterator j = aUVPoints->begin(); j != aUVPoints->end(); ++j)
    {
        // evaluate the point on the surface
        gp_Pnt aPoint = theSurface->Value((*j).x(), (*j).y());

        aPoints->push_back(osg::Vec3(aPoint.X(), aPoint.Y(), aPoint.Z()));
    }

    //aGeometry->setVertexArray(aUVPoints);
    aGeometry->setVertexArray(aPoints);
    aGeometry->addPrimitiveSet(dt->getTriangles());

    aGeode->addDrawable(aGeometry);

    // use smoothing visitor to set the average normals
    osgUtil::SmoothingVisitor sv;
    sv.apply(*aGeode);

    // set material for the surface
    osg::ref_ptr<osg::StateSet> aStateSet = aGeode->getOrCreateStateSet();
    osg::ref_ptr<osg::Material> aMaterial = new osg::Material();

    aMaterial->setDiffuse(osg::Material::FRONT, osg::Vec4(1.0f, 1.0f, 0.0f, 1.0f));
    aMaterial->setSpecular(osg::Material::FRONT, osg::Vec4(1.0f, 1.0f, 1.0f, 1.0f));
    aMaterial->setShininess(osg::Material::FRONT, 100.0f);

    aStateSet->setAttribute(aMaterial);

    return aGeode.release();
}

为跟外一样首blog中之分,在OpenSceneGraph中绘制OpenCascade的曲面:
http://www.cppblog.com/eryar/archive/2013/08/11/202466.html

专门加上了材料与光照效果。离散的曲面效果使下图所示: 

图片 6

Figure 2.1 Shaded Surfaces in OpenSceneGraph 

图片 7

Figure 2.2 Mesh of the Surfaces in OpenSceneGraph 

为了显示出光照效果,使用了osgUtil::SmoothingVisitor来机关测算三角网格的平分法向。从上图可知,这种办法是以曲面的参数空间都匀剖分得到的曲面,当剖分得密时,数据量大,但显示得传神。剖分疏时,数据量小,显示失真。 

动特色敏感网格重剖技术,可以动用比较少之三角面片来比确切地意味着几哪里模型,如下图所示:(图片源于:http://cg.cs.tsinghua.edu.cn/papers/TVCG2007featuresensitive.pdf) 

图片 8

Figure 2.3 Feature sensitive remeshing
(http://cg.cs.tsinghua.edu.cn/) 

3. Holes in the Surface

当曲面上发开孔时,开孔的信息可以经WIRE来获得。对于构成开孔的WIRE的各级条EDGE,可以透过曲面上的曲线PCurve来拿开孔的参数统一到曲面的UV参数空间。 

图片 9

Figure 3.1 Hole in Parametric UV space 

当OpenSceneGraph中实现代码如下所示: 

osg::Node* BuildSurface(const Handle_Geom_Surface &theSurface, const Handle_Geom2d_Curve &thePCurve)
{
    osg::ref_ptr<osg::Geode> aGeode = new osg::Geode();
    osg::ref_ptr<osg::Geometry> aGeometry = new osg::Geometry();

    osg::ref_ptr<osg::Vec3Array> aUVPoints = new osg::Vec3Array();
    osg::ref_ptr<osg::Vec3Array> aPoints = new osg::Vec3Array();
    osg::ref_ptr<osg::Vec3Array> aBounds = new osg::Vec3Array();

    osg::ref_ptr<osgUtil::DelaunayTriangulator> dt = new osgUtil::DelaunayTriangulator();
    osg::ref_ptr<osgUtil::DelaunayConstraint> dc = new osgUtil::DelaunayConstraint();

    // build triangulation for the parametric space.
    Standard_Real u1 = 0.0;
    Standard_Real u2 = 0.0;
    Standard_Real v1 = 0.0;
    Standard_Real v2 = 0.0;

    theSurface->Bounds(u1, u2, v1, v2);

    Precision::IsNegativeInfinite(u1) ? u1 = -1.0: u1;
    Precision::IsPositiveInfinite(u2) ? u2 =  1.0: u2;
    Precision::IsNegativeInfinite(v1) ? v1 = -1.0: v1;
    Precision::IsPositiveInfinite(v2) ? v2 =  1.0: v2;

    // tesselate the parametric space.
    Standard_Integer aStep = 30;
    Standard_Real uDelta = (u2 - u1) / aStep;
    Standard_Real vDelta = (v2 - v1) / aStep;

    for (Standard_Integer i = 0; i <= aStep; ++i)
    {
        for (Standard_Integer j = 0; j <= aStep; ++j)
        {
            Standard_Real u = u1 + i * uDelta;
            Standard_Real v = v1 + j * vDelta;

            aUVPoints->push_back(osg::Vec3(u, v, 0.0));
        }
    }

    Standard_Real pDelta = (thePCurve->LastParameter() - thePCurve->FirstParameter()) / aStep;
    for (Standard_Integer c = 0; c <= aStep; ++c)
    {
        gp_Pnt2d p = thePCurve->Value(thePCurve->FirstParameter () + c * pDelta);

        aBounds->push_back(osg::Vec3(p.X(), p.Y(), 0.0));
    }

    dc->setVertexArray(aBounds);
    dc->addPrimitiveSet(new osg::DrawArrays(osg::PrimitiveSet::LINE_LOOP, 0, aBounds->size()));

    // triangulate the parametric space.
    dt->addInputConstraint(dc);
    dt->setInputPointArray(aUVPoints);
    dt->triangulate();
    dt->removeInternalTriangles(dc);

    for (osg::Vec3Array::const_iterator j = aUVPoints->begin(); j != aUVPoints->end(); ++j)
    {
        // evaluate the point on the surface
        gp_Pnt aPoint = theSurface->Value((*j).x(), (*j).y());

        aPoints->push_back(osg::Vec3(aPoint.X(), aPoint.Y(), aPoint.Z()));
    }

    //aGeometry->setVertexArray(aUVPoints);
    aGeometry->setVertexArray(aPoints);
    aGeometry->addPrimitiveSet(dt->getTriangles());

    aGeode->addDrawable(aGeometry);

    // use smoothing visitor to set the average normals
    osgUtil::SmoothingVisitor sv;
    sv.apply(*aGeode);

    // set material for the surface
    osg::ref_ptr<osg::StateSet> aStateSet = aGeode->getOrCreateStateSet();
    osg::ref_ptr<osg::Material> aMaterial = new osg::Material();

    aMaterial->setDiffuse(osg::Material::FRONT, osg::Vec4(1.0f, 1.0f, 0.0f, 1.0f));
    aMaterial->setSpecular(osg::Material::FRONT, osg::Vec4(1.0f, 1.0f, 1.0f, 1.0f));
    aMaterial->setShininess(osg::Material::FRONT, 100.0f);

    aStateSet->setAttribute(aMaterial);

    return aGeode.release();
}

开孔的落实重点为是因此osgUtil::DelaunayConstraint,将孔中的三角去除。如下图所示为于球面和锥面开孔: 

图片 10

Figure 3.2 Holes on Sphere and Cone Surface 

图片 11

Figure 3.3 Mesh for Sphere and Cone with holes 

由于上图克,对于发出拓朴结构的老三维模型数据,可以由WIRE得到组成孔的各条边Edge,根据Edge中PCurve可以搜索到相应之曲面。通过PCurve将开孔数据统一到参数空间被。剖分完带孔的参数空间,再映射回三维空间就取得开孔的曲面了。

4. Conclusion

原一直百相思不得其解的题材现在都豁然开朗,对三维模型的可视化有了肯定之知道。借助于这些开源库,对有关知识之修而轻松多,可以以多国产教材及断续的理论知识与执行衔接起来。

5. Acknowledgement

谢OpenCascade和OpenSceneGraph的绽开和享受,让学习变得轻松诙谐。

6. Reference

  1. 孙家广, 胡事民等. 计算机图形学. 清华大学出版社. 2000 

  2. 赵罡, 穆国旺, 王拉柱译. 非净匀有理B类条. 清华大学出版社. 2010 

  3. Jonathan R. Shewchuk. Triangle:
    http://www.cs.cmu.edu/~quake/triangle.html

  4. 汪嘉业 王文平 屠长河 杨承磊. 计算几何及应用.  科学出版社. 2011 

  5. 王成恩. 面向科学计算的网格划分以及可视化技术. 科学出版社. 2011 

  6. 周培德. 计算几哪-算法设计和分析. 清华大学出版社. 2008 

  7. http://cg.cs.tsinghua.edu.cn/

  8. Mesh Algorithm in
    OpenCascade: 

http://www.cppblog.com/eryar/archive/2014/04/06/206484.html

 

Source code and PDF Version: Visualize Surface by Delaunay
Triangulator

六、 参考资料

  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

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

借用设V是二维实数域上的有限点集,边e是出于点集中之点作端点构成的查封线段,E为e的汇,那么该点集V的一个三角剖分T=(V,E)是一个面图: 

l 除了端点,平面图中的界限不包含点集中之任何点; 

l 没有互相交边; 

l 平面图备受持有的面都是三角面,且独具三角面的合集是点集V的凸包。 

关键字:Delaunay Triangulation、OpenCascade、OpenSceneGraph 

五、 结论

Delaunay三角剖分理论以三维几哪样子饱受尚是较关键的,通过对造型的三角剖分,不仅可针对该进行可视化,还利于对造型做进一步的处理,如消隐、光照处理等。通过对OpenCascade中三角剖分算法的动,以越来越询问三角剖分理论以及其算法实现。 

eryar@163.com

Delaunay Triangulation in
OpenCascade

一、 概述

三角形剖分是平面剖分中之一个关键课题,在数字图像处理、计算机三维曲面造型、有限元计算、逆向工程等领域有所广泛应用。由于三角形是同等面域中之只是形,与其它平面图形相比,其产生描述方便、处理大概等特点,很适合给对复杂区域开展简化处理。因此,无论在算几哪、计算机图形处理、模式识别、曲面逼近,还闹星星点点元网格生成上面发生科普的应用。 

虽曲线、曲面等发出纯正的方程来代表,但是于当微机被,只能用离散的办法来逼。如曲线可用直线段来逼,而曲面可用多边形或三角形来代表。用多边形网格表示曲面是规划着时常应用的花样,可以依据使用要求选择网格的密度。利用三角形面片表示的曲面在微机图形学着也叫三角形网格。用三角网格表示曲面需要解决几只问题:三角形的产生、描述、遍历、简化和削减等,这些问题还是计算几何研究的面,相关问题都得以从中找到答案。下图所出示之圆柱和立方体是由OpenCascade生成,使用OpenCascade的算法离散成三角网格后当OpenSceneGraph中显得的功力。 

图片 12

Figure 1.1 Shaded Cylinder and Box 

图片 13

Figure 1.2 Mesh generated by OpenCascade 

起图中可以看,平面的三角网格作用还对,曲面的三角形网格表示只能是近乎表示,可以由此提高网格的密度来增加真实性,但对应渲染的数据量就十分了。有人说OpenCascade的亮模块做得无是雅好,上述措施虽然可只是利用OpenCascade的样模块,再结合OpenSceneGraph来针对图片进行亮。 

三维数据交换STL格式文件中保留之且是三角面片的多寡,STL文件格式是由于美国3D
System公司开支,已于工业界认为是目前快机动成型领域的准标准零件描述文件格式。它对三维实体描述的诠释有惟一性。几乎拥有的几乎何样子系统还提供STL文件数据交换接口。OpenCascade中之数据交换模块也提供对STL格式的支持,由此可见三角网格在几何样子系统受到的要害。 

Voronoi图和Delaunay三角剖分的应用领域十分大规模:几哪里建模——用来找三维曲面“好之”三角剖分;有限元分析——用来变化“好之”有限元网格;地理信息体系——用来开展空中领域分析;结晶学——用来确定合金的组织;人类学和考古学——用来确定氏族部落、首经受权威、居住中心要堡垒等之影响范围;天文学——用来规定恒星和星系的遍布;生物学生态学和林学——用来规定动植物的竞争;动物学——分析动物之领地;统计学和数码解析——用来分析统计聚合;机器人学——用来展开移动轨迹规划(在设有障碍物的景象下);模式识别——作为找物体骨架点的工具;生理学——用来分析毛细作用的天地;气象学——用来估算区域平均降雨量;市场学——用来建市的市场辐射范围;以及以遥感图像处理、化学、地理学、地质学、冶金学、数学等学科的采取等。 

正文只针对OpenCascade中的三角形剖分进行简短介绍,希望对三角剖分在三维几哪里样子点出趣味之爱侣可对那个深刻钻研。水平非常简单,文中不当之处欢迎批评指正、指导,联系邮箱:eryar@163.com。 

3. Delaunay三角剖分

假定接触集V的一个三角形剖分T中单独包含Delaunay边,那么该三角剖分称为Delaunay剖分。 

近年触及意思下之Voronoi图的夹图实际上是点集的同一种三角剖分,该三角剖分就是Delaunay剖分(表示为DT(S)),其中每个三角形的外接圆不包含点集中的别样任何点。因此,在布局点集的Voronoi图之后,再发作其对偶图,即对每条Voronoi边发通过接触集中某片接触的垂直平分线,即获Delaunay三角剖分。 

图片 14

Figure 3.1 Delaunay Triangulation (Generated by MATLAB) 

还拘留几乎只图片,加深对Delaunay三角剖分的明亮: 

图片 15

Figure 3.2 Delaunay Edge  

图片 16

Figure 3.3 Illustrate Delaunay Edge 

图片 17

Figure 3.4 Delaunay Edge 

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/Watson算法和组成部分变换法。 

l
Bowyer/Watson算法又称为Delaunay空洞算法或加点法,以Bowyer和Watson算法为表示。从一个三角形开始,每次加一个碰,保证各一样步得到的脚下三角形是片优化的。以英国Bath大学数学分校Bowyer,Green,Sibson为表示的测算Dirichlet图的主意属于加点法,是比早成名的算法有;以澳大利亚悉尼大学地模拟系Watson为代表的空外接球法也属于加点法。加点法算法简明,是眼下采取最多之算法,该方式应用了Delaunay空洞性质。Bowyer/Watson算法的长处是和上空的维数无关,并且算法在落实上于有变换算法简单。该算法在新点参加到Delaunay网格时,部分外接球包含新点的三角单元不再符合Delaunay属性,则这些三角形单元被剔除,形成Delaunay空洞,然后算法将新点与做空洞的诸一个极端相连生成一个新边,根据空球属性可以作证这些新边都是一对Delaunay的,因此新生成的三角网格仍是Delaunay的。 

图片 18

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

l
局部变换法又称为换边、换面法。当用有变换法实现增量式点集的Delaunay三角剖分时,首先定位新加入点所在的三角,然后在网格中入三独新的连续该三角形顶点与新顶点的界限,若该新点位于某条边上,则该边被删去,四漫漫连接该新点的无尽给加入。最后,在通过换边方法对该新点的片段区域外之限进行检测及转换,重新维护网格的Delaunay性质。局部变换法的别样一个亮点是那个可对曾经是的三角形网格进行优化,使该易成为Delaunay三角网格,该措施的毛病则是当算法扩展及高维空间时移得比较复杂。 

季、 Delaunay三角剖分在OpenCascade的使

OpenCascade中网格剖分的包要发生BRepMesh、MeshAlgo、MeshVS,其中,类MeshAlgo_Delaunay使用算法Watson来进展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();
}

结果如果下图所示: 

图片 19

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_FastDiscretFace。这个看似证了哪以一个冲进行网格划分。 

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

其三、 Delaunay三角剖分 

2. Delaunay边

借设E中的如出一辙条边(两端点a,b),e满足下列原则,则叫Delaunay边:存在一个圆经过a,b两触及,圆内不分包点集V中的其他的触及。这等同特色又曰空圆特性。 

相关文章

No Comments, Be The First!
近期评论
    分类目录
    功能
    网站地图xml地图