三维裁剪算法

❶ 三维Cohen-Surtherland裁剪算法中直线端点编码需要多少位

三维Cohen-Surtherland裁剪算法中直线端点编码需要四位。直线的端点赋予一组4位二进制码，称为RC(区域编码），裁剪窗口的四条边所在的直线可以把平面分为9个区域，对各个区域的编码也是四位。

三维Cohen-Surtherland绪论

利用DDA和Wu算法测增量思路，以及Wu算法的思想利用距离进行颜色分配思想，根据计算机浮点数的内部格式，用整数补码表示平移后的斜率（增量）小数部分（32位定点小数），将画点位置的计算与颜色分配比例的计算合为一体。

将这两个参数的计算在绘制循环中减少到一个判断，和0～1个自增或自减计算。颜色分配的精度达到2的32次幂。并用32位整数以向量运算方式计算颜色分量与背景合成的颜色值，加快了颜色计算的速度。

圆求解坐标的时候利用级数展开，避免开放和实数运算，快并且误差小。

矩形裁剪算法可快速绘制。

❷ 计算机图形学中有几种直线裁剪算法

计算机图形学(Computer Graphics，简称CG)是一种使用数学算法将二维或三维图形转化为计算机显示器的栅格形式的科学。

简单地说，计算机图形学的主要研究内容就是研究如何在计算机中表示图形、以及利用计算机进行图形的计算、处理和显示的相关原理与算法。图形通常由点、线、面、体等几何元素和灰度、色彩、线型、线宽等非几何属性组成。从处理技术上来看，图形主要分为两类，一类是基于线条信息表示的，如工程图、等高线地图、曲面的线框图等，另一类是明暗图，也就是通常所说的真实感图形。

计算机图形学一个主要的目的就是要利用计算机产生令人赏心悦目的真实感图形。为此，必须建立图形所描述的场景的几何表示，再用某种光照模型，计算在假想的光源、纹理、材质属性下的光照明效果。所以计算机图形学与另一门学科计算机辅助几何设计有着密切的关系。事实上，图形学也把可以表示几何场景的曲线曲面造型技术和实体造型技术作为其主要的研究内容。同时，真实感图形计算的结果是以数字图像的方式提供的，计算机图形学也就和图像处理有着密切的关系。

图形与图像两个概念间的区别越来越模糊，但还是有区别的：图像纯指计算机内以位图形式存在的灰度信息，而图形含有几何属性，或者说更强调场景的几何表示，是由场景的几何模型和景物的物理属性共同组成的。

计算机图形学的研究内容非常广泛，如图形硬件、图形标准、图形交互技术、光栅图形生成算法、曲线曲面造型、实体造型、真实感图形计算与显示算法、非真实感绘制，以及科学计算可视化、计算机动画、自然景物仿真、虚拟现实等。

❸ 三维数据分析有哪些好的方法与软件

三维数据处理软件都包含哪些模块

三维数据处理软件，一般包含三个模块：数据管理和处理，三维渲染，UI。 这与图形学的三个经典问题是相对应的：建模，渲染和交互。与一般常见的数据处理软件，比如图像视频处理，不同的是，这里的数据展示模块需要三维渲染。与之对应的UI操作，也变成了一些三维空间的变换，比如模型的旋转缩放等。

如何搭建一个简单的三维数据处理软件

那么如何快速的搭建一个三维数据处理软件呢？采用搭积木的方式，每个模块都有很多现成的开发包可以选择。比如UI模块处，一般常见的有MFC，QT，MyGUI（Magic3D使用的UI）等。数据处理算法方面，常见的有Geometry++，CGAL，OpenMesh，PCL等。渲染模块，可以使用OpenGL或者Direct3D，也可以使用渲染引擎，如OGRE，OSG等。

如何选择几何算法开发包

几何算法模块，一般有三种选择：自主开发，使用开源库，使用商业库。如何选择呢？开发包API的生命周期，大概分为开发，维护和升级。对于一个算法，几乎不可能开发出放之四海皆准的API。它的绝大部分时间都在维护和升级。开发包的选择，其实就是一个成本问题。开发阶段主要是时间成本，如何快速的实现目标功能是最关键的问题。维护和升级阶段需要尽量低的成本开销。所谓开源库免费，其实只是在开发阶段免费，而开发阶段最看重的却是时间成本。有了源代码就需要人去维护，没有人维护的源代码是没有用处的。商业库的主要优势就是有专业的团队来维护和升级这些API，并且成本会比个人做得更低。如果想清楚API的生命周期以及每个阶段的成本开销后，根据自身具体情况，就能很容易的做出选择了。

数字几何处理是什么

数字几何处理，一般是指点云网格数据的处理。和传统的NURBS正向建模的模型相比，数字几何处理的对象一般是三维扫描仪采集的数据，是曲面的离散表达，也就是数字化的。它的研究内容包括数据的获取，存储，表示，编辑，可视化等等。

OpenGL是什么

OpenGL是一套跨平台的图形绘制API，它通过一系列API把三维模型渲染到2D屏幕上。OpenGL采用了流水线机制，其绘制过程也称为渲染流水线。此外还有OpenGLES，主要用于嵌入式系统，或者移动平台；WebGL主要用于Web浏览器里的图形绘制。

OpenGL流水线

OpenGL通过一系列API可以设置渲染流水线的状态，所以OpenGL也是一个状态机。三维模型通过一些处理，最终渲染到2D屏幕上：

• 模型离散为三角面片：所有模型都需要离散为三角面片，OpenGL只接受三角面片输入。注意，虽然OpenGL也可以接受四边形，NURBS等输入，其本质最后都是三角面片的绘制。

• Vertex Shader把三维三角片转化到屏幕坐标系下的2D三角片：这个过程包含了变换，裁剪等操作

• 2D三角片的光栅化：2D三角片被离散化，用屏幕坐标系的像素来表示，这也叫光栅化。

• Pixel Shader为光栅化后的模型像素着色。

  上面是渲染流水线的大致描述，其中还有很多细节，不同的API也有些细节上的差别。最早的OpenGL是固定的流水线，也就是只能通过API来设置一些流水线中的状态。现代的OpenGL开放出了一些Shader，用户可以自己为Shader写代码，利用Shader可以写出各式各样的渲染效果。

  渲染模块使用OpenGL还是渲染引擎

  如果渲染模块不是主要业务，建议使用渲染引擎。因为引擎内有很多现成的工具可以使用，减少开发的时间成本。

❹ 断面建模

（一）断面的生成

在断面建模之前，要先导入剖面图和钻孔以及断层线等信息。根据导入的剖面图、断层线和钻孔信息，来生成模型的断层。生成断层有两种方式，即根据剖面上的断层剖面线和根据离散点数据生成。

1.离散点断面建模算法

基于不同方法获取的离散点数据，可进行插值生成断面模型，下面是根据离散点来构建断面算法的思想。

（1）求解投影坐标系。断面采用的投影坐标系并非断面的最小二乘面投影坐标系，而是在求得最小二乘面后，将Z方向的偏差置为0，这是一个世界坐标与XOY平面垂直的平面。根据断面的特点，断面在一般情况下是竖直的，这样的投影平面不会出现插值点重叠的问题。该设计是为在查找地层离散点在断层上的投影点时提供一个更有意义的投影坐标系。

（2）求解矩形基础网格，并根据基础网格计算三角网格，根据三角网格包围盒计算一个包围边界。用这个包围边界作为第一次裁剪曲面的边界，得到初始显示曲面。

（3）用户根据需求对初始显示曲面进行编辑或者指定初始显示曲面的裁剪曲面就可以得到显示曲面。重复本步骤，直至满足要求，完成最终的断面模型。

2.基于剖面上的断层线生成断面模型

将剖面导入三维建模软件系统之后，对剖面上的断层线进行分析，选定属于相同断层的剖面断层线，然后进行剖分、插值生成断层。如图4-11所示。

图4-11 根据剖面上的断层线生成断层

3.基于离散点数据生成断面模型

通过导入的离散点也可以生成断层，或者在钻孔导入三维建模软件系统之后，通过在孔轨迹上指定断层上的钻点，然后通过剖分、插值生成断层。如图4-12所示。

图4-12 根据离散点生成断层

（二）断面的编辑

断层生成之后，根据需要可以编辑断层边界和使用控制点编辑断层，改变断层面的形状，还可以通过修改属性框中的内容来编辑断层的属性等。如图4-13所示。

图4-13 根据离散点生成断层

对地质体中的信息进行修改是重要的功能之一。课题组地质体模型的数据结构中，输入可以是点集合和折线集合，但是折线集合也被示为有序点的集合。所以，对于点的编辑和修改是所有编辑和修改的基础。由于一般图形平台中很难解决计算机图形学中的一个基本问题即“坐标变换”的深度问题，所以只能依赖于生成的三角网格面，实现沿着面和垂直面两个方向的空间点的“位置坐标”编辑，即标量编辑。采用标量编辑，解决了“坐标变换”的深度问题，实现了不依赖于三角网格面的空间点编辑。

此外，还采用了“三维空间矢量点”的编辑功能。“三维空间矢量点”是指工区种的三维点不仅含有“位置坐标”的概念，还赋予每个点一个“方向矢量”。这样，很容易对空间点进行方向上的编辑功能，我们称谓“三维空间矢量点编辑”。本系统中多处采用了这种编辑功能，例如断面上控制点的编辑（图4-13（a））、地层上控制点的编辑、光源矢量的编辑等。光源矢量的编辑效果如图4-14所示。

图4-14 光源矢量编辑功能

（三）定义断面关系

在建模时，对于工区中相交的两个断层，需要确认它们的相交关系，即哪一个是主切面，哪一个是被切面。通过定义它们的关系，实现主断层面剪切辅断层面的功能。在定义主断层面时，一般选择相对较高且长度大于被切断层面在其上的投影面的断层面，这样选择的要求可使系统较快地构建断面网格。

断层主辅关系定义之后，选择“更新断层”功能，生成切割后的断层。图4-15所示为定义断层关系之后重新生成的断层效果。

图4-15 定义断层关系

（四）三角网格边界裁剪算法

网格边界裁剪算法是构建连续曲面的基础算法。在复合结构表示的地质面构建算法中，没有采用根据边界进行三角剖分和插值的方法来构建地质面，而是设计了一种通用性更广、集网格裁剪、网格分割的快速网格边界计算方法。本系统中多处要应用此算法，如主辅断面的裁减、主辅地层的裁减、地层三角网与断面矩形网的裁减等等。

由三角剖分生成的三角网格均匀且易于保证求交精度，而直接切分的三角形势必出现三角形畸形的问题。由于本算法的计算基础是曲面的矩形网格，所以畸形的三角形对算法没有影响。

表4-1是分别由三角剖分和矩形网格映射生成三角网格的效果对比。

表4-1 三角网格效果对比

由表4-1可以看出，三角剖分和矩形网格映射各有优缺点，在本软件中，我们结合这两种方法的优点，设计出了一种全新的三角网格构建方法，具体将在下文中详细介绍。

1.裁剪器的设计

本系统中根据地质面边界计算的需求设计了裁剪器的结构。裁剪的核心计算部分是统一的，其他的输入和细节处理部分由虚函数分发到不同的子类处理，具有可维护性高，扩展性好的特点。

初始构建的三角网格由矩形网格映射而成，具有矩形的边界。同时在构建过程中采用了保留拓扑关系的映射方式，使得三角网格中相邻三角形之间有拓扑关系，并且在以后的计算中将保留并维护这种拓扑关系。

在构建地质面过程中，地质面边界可能由于以下情况而发生改变：

（1）用户直接对地质面边界进行编辑。

（2）地质面将地质面的边界改变；地质面被地质面切割包括两种：一种是有矩形背景网格的三角网格被三角网格切割；一种是无矩形背景网格的三角网格被有矩形背景网格的三角网格切割。对于三角网格被三角网格切割的情况，考虑到算法的效率以尽量避免为主，算法不对其进行研究。

（3）在地质面被切割时，还包括局部切割和全局切割的情况。

分析上述地质面切割的特点，发现上述切割有一个共同的特点，即三角网格被切割成两个部分后，网格的形态没有改变，只是网格的边界发生改变。根据上述需求三角网格裁剪的算法输入是：

（1）三角形网格：本算法为了提高运算的效率采用如下的三角网格结构：每个三角形中保存的是顶点的指针和临近三角形的指针。一套三角网格保存着一个顶点集合用来记录所有的顶点。该结构不仅能清晰记录三角形的形状信息和地理位置信息，还能保存同该三角形的相邻拓扑信息，便于查找和运算。本裁剪算法就是以此为基础进行设计和实现的。本算法认为三角网格边界相对于三角网格密度足够光滑，在三角形内部没有拐点。

（2）剪路径：裁剪路径是地质面新的边界，裁剪路径的限制条件是输入的裁剪路径不自交。

根据对输入条件的分析，裁剪三角形的流程是统一的，都是将三角形网格一分为二，只是裁剪路径的决定条件不同。裁剪路径可以是由多边形决定，也可以是由曲面决定，还可以是由其他几何元素决定，本算法根据C++派生类的关系设计了裁剪算法的机制——裁剪器。

构建裁剪器后，只需传入待裁剪的三角网格和裁剪路径，裁剪器就可以完成对三角网格的裁剪工作。不同的路径判断算法需要构建不同的裁剪器，每个具体裁剪器都从裁剪器基类派生而来，裁剪器基类负责三角网格的裁剪工作。这样有利于算法的维护和扩展。

2.裁剪器的基本裁剪算法

裁剪算法可以应用于所有三角网格被矩形网格或折线裁剪的情况，并且裁剪时对三角形拓扑关系的维护及重建过程是一致的，采用有拓扑的三角网格结构能起到很好的加速作用。

根据带拓扑关系的三角网格的特点，裁剪算法的流程如图4-16所示。

图4-16 三角网格裁剪流程

具体算法流程为：

（1）确定所有三角形的顶点与裁剪路径的关系，有以下两种可能的关系：①顶点在裁剪路径内；②顶点在裁剪路径外（即将被裁剪掉的部分）。该功能由每个具体的裁剪器来完成。

（2）根据顶点关系将三角形分类：顶点全部在裁剪路径外或全部在裁剪路径上的三角形为不需要裁剪的三角形，其他的为待裁剪三角形。

（3）建立一个待裁剪三角形堆栈，选出一个待裁剪三角形作为初始三角形入栈，开始裁剪：

①在初始三角形中，肯定有两个顶点同侧，如图4-17所示的三角形中顶点c和顶点b同侧；

图4-17 初始三角形

②求解三角形与裁剪路径的交点值，分别记为A和B，具体求交过程由每个具体的裁剪器完成，如图4-18所示：

图4-18 三角形交点

③建立四个新三角形顶点A，B，A'和B'，其中A=A'，B=B'。建立三个新三角形，分别为△aBA，△B'bc和△A'B'c，如图4-19所示：

图4-19 新三角形结构

④为上述三个新三角形建立拓扑关系，保持三角网格中拓扑的完整性，同时，将ac和ab边所对应的三角形入栈等待处理。记录维护拓扑所需的相应信息后，将初始三角形出栈并将其在三角网格中删除。将栈顶的三角形作为初始三角形重复步骤Ⅲ，直至栈空。

（4）查找待裁剪网格中没有裁剪的三角形，如果有则重复上述步骤（3）。

（5）根据三角网格顶点与裁剪路径的位置关系将三角形网格裁剪为两个三角网格。

（6）裁剪后的三角形网格存在法矢缺失的问题，在显示时，需要考虑到光照和反射才能有较好的三维效果。作为待显示的三角网格，需要补齐法矢。

3.裁剪器其他的功能

在基本算法的基础上，为了完成不同对象之间的裁剪，裁剪器还定义了一些其他的功能，包括：计算三角网格同裁剪器的交点、根据空间位置将三角网格顶点划分为裁剪路径正侧和负侧。裁剪器主要有以下几种：

（1）多边形裁剪器

主要用于裁剪多余的三角形，标定曲面的边界和有效范围。多边形裁剪器在裁剪三角网格时，将三角网格分为多边形内部和多边形外部两个部分进行裁剪。在三维地质建模过程中常常需要用多边形来标识断面边界，因此需要使用多边形裁剪器。该裁剪器的功能如下：

工作1：用多边形将三角网格顶点分为多边形内部和多边形外部。

工作2：用三角形边和多边形网格求交点。

（2）矩形网格完全裁剪器

该裁剪器是用矩形网格将待裁剪的三角网格分为两部分，当不能将三角网格完全划分为两个部分时，则矩形网格延长将三角网格完全划分为两个部分—矩形网格正侧部分和矩形网格负侧部分。利用矩形网格来判断待划分的三角网格顶点在矩形网格正侧还是负侧非常高效。可以采用该裁剪器计算断面被其他地质面裁剪后的形态。该裁剪器的功能如下：

工作1：用矩形网格将三角网格顶点分为矩形网格正侧顶点和矩形网格负侧顶点。

工作2：用三角形边和矩形网格求交点。

（3）矩形网格不完全裁剪器

该裁剪器是用矩形网格破坏待裁剪三角网格的拓扑关系，将矩形网格与待裁剪三角网格相交处三角形分为两步分，而三角网格本身并没有被完全割断。该裁剪器用于求解断层分割地层的裂口。该裁剪器的功能如下：

工作1：用矩形网格将三角网格顶点分为矩形网格正侧顶点和矩形网格负侧顶点。

工作2：用三角形边和矩形网格求交点。

经过多次不同裁剪器裁剪后的三角网格形态如图4-20所示：

图4-20 多次不同裁剪器裁剪后的三角网格

❺ 栅格化的基本实现方法

最基础的栅格化算法将多边形表示的三维场景渲染到二维表面。多边形由三角形的集合表示，三角形由三维空间中的三个顶点表示。在最简单的实现形式中，栅格化工具将顶点数据映射到观察者显示器上对应的二维坐标点，然后对变换出的二维三角形进行合适的填充。 一旦三角形顶点转换到正确的二维位置之后，这些位置可能位于观察窗口之外，也可能位于屏幕之内。裁剪就是对三角形进行处理以适合显示区域的过程。
最常用的技术是Sutherland-Hodgeman裁剪算法。在这种方法中，每次测试每个图像平面的四条边，对于每个边测试每个待渲染的点。如果该点位于边界之外，就剔除该点。对于与图像平的面边相交的三角形边，即边的一个顶点位于图像内部一个位于外部，那么就在交叉点插入一个点并且移除外部的点。 传统的栅格化过程的最后一步就是填充图像平面中的二维三角形，这个过程就是扫描变换。
第一个需要考虑的问题就是是否需要绘制给定的像素。一个需要渲染的像素必须位于三角形内部、必须未被裁掉，并且必须未被其它像素遮挡。有许多算法可以用于在三角形内进行填充，其中最流行的方法是扫描线算法。
由于很难确定栅格化引擎是否会从前到后绘制所有像素，因此必须要有一些方法来确保离观察者较近的像素不会被较远的像素所覆盖。最为常用的一种方法是深度缓存，深度缓存是一个与图像平面对应的保存每个像素深度的二维数组。每个像素进行绘制的时候都要更新深度缓存中的深度值，每个新像素在绘制之前都要检查深度缓存中的深度值，距离观察者较近的像素就会绘制，而距离较远的都被舍弃。
为了确定像素颜色，需要进行纹理或者浓淡效果计算。纹理图是用于定义三角形显示外观的位图。每个三角形顶点除了位置坐标之外都与纹理以及二维纹理坐标 (u,v) 发生关联。每次渲染三角形中的像素的时候，都必须在纹理中找到对应的纹素，这是根据在屏幕上像素与顶点的距离在与纹理坐标相关联的三角形顶点之间插值完成的。在透视投影中，插值是在根据顶点深度分开的纹理坐标上进行的，这样做就可以避免透视缩减（perspective foreshortening）问题。
在确定像素最终颜色之前，必须根据场景中的所有光源计算像素上的光照。在场景中通常有三种类型的光源。定向光是在场景中按照一个固定方向传输并且强度保持不变的光。在现实生活中，由于太阳距离遥远所以在地球上的观察者看来是平行光线并且其衰减微乎其微，所以太阳光可以看作是定向光。点光源是从空间中明确位置向所有方向发射光线的光源。在远距离的物体上的入射光线会有衰减。最后一种是聚光灯，如同现实生活中的聚光灯一样，它有一个明确的空间位置、方向以及光锥的角度。另外，经常在光照计算完成之后添加一个环境光值以补偿光栅化无法正确计算的全局照明效果。
有许多可以用于光栅化的浓淡算法。所有的浓淡处理算法都必须考虑与光源的距离以及遮蔽物体法向量与光照入射角。最快的算法让三角形中的所有像素使用同样的亮度，但是这种方法无法生成平滑效果的表面。另外也可以单独计算顶点的亮度，然后绘制内部像素的时候对顶点亮度进行插值。速度最慢也最为真实的实现方法是单独计算每点的亮度。常用的浓淡模型有 Gouraud shading 和 Phong shading。