---

我们都知道“几何内核”在工业软件中的地位和重要性，目前市面上关于三维几何内核的深入介绍极少，有的话也都停留在基础知识，设计理念和发展历史层面。在实际工作中也经常听到诸如“开发仿真软件必须用PS/ACIS二选一”，“几何内核万能“，”找两个人半年做个几何内核“。看完这个系列后，会对几何内核有更深入的理解。

笔者有多年使用商业几何内核的经验，也做过几何内核的相关开发，研发中亲自使用过5种几何内核，而接触过的至少有8种；相对于一般的研发和科普文章，可能更有针对性。

“深入剖析三维几何内核”文章系列中，笔者将拿起“手术刀”剖开“几何内核”的外壳，看看“内核”里到底有什么东西。

在（点击链接查看）一文中，对几何内核做了入门介绍。

本文将对几何内核涉及的专业术语，设计理念，应用领域，以及现状做进一步的介绍。

计算机中表示三维形体的模型，按照几何特点进行分类，大体上可以分为三种：线框模型、表面模型和实体模型。如果按照表示物体的方法进行分类，实体模型基本上可以分为分解表示、构造表示CSG（Constructive Solid Geometry）和边界表示BREP（Boundary Representation）三大类。主流几何内核的做法是底层使用BREP结构，把CSG作为操作BREP结构的管理方法。

在内核里，按照使用目的我们一般把数据分为两类：

“几何”描述的是具体位置和形状，“拓扑”描述的是位置关系。

“几何”比较容易理解，就是我们通常所说的点，线，面，体。线又可以分为直线，线段，圆，圆弧，Nurbs曲线，贝赛尔曲线等各种线，面也类似可以分为平面，非参数曲面，参数方程定义的曲面等。而体则定义了各种实体，长方体，圆柱，球，圆环，组合体等

为什么要有“拓扑”的概念？

其实很好理解，举个例子：

一条线段有两个顶点，当我们只知道其中一点的坐标数据时，希望得到该点在哪条线段上。如果没有拓扑信息，简单的办法就是全局计算遍历一遍，缺点显而易见；如果有拓扑信息，记录了该点的拓扑信息，即该点的上层拓扑直线，我们直接拿点的拓扑信息就可以了。

“拓扑”这种记录位置关系或者对象关系的数据结构在三维几何计算中非常有用，是一种基础数据结构。

Boundary Representation（BRep），边界表示方法是目前主流的几何内核ACIS/OCC/PS使用的方法，主要原因是这种几何表示方法比较直观，简单，通用，适合大部分几何造型以及建模需求。

在该方法中，虽然拓扑上定义有“体”， 但实际上体也是由面来表示，比如一个长方体，由六个面构成，而体的内部是空的。如下图

有朋友可能会问：如果我想得到体里面的数据怎么办？

1.  切开实体，生成两个新的实体，如上图重新构建新的基于BRep的长方体；当然这个过程在软件中是“原子操作”，一步完成，也就是说用户感觉不到体内的空洞存在。

2. 在有限元方法中，我们有形函数，利用形函数可以得到体积内任意一点的信息，当然这只适用于比较规则的几何体。

3. 类似于体渲染的切片技术。在CT扫描中，CT会生成多幅图像，然后根据图像进行三维重建，重建后就可以得到任意位置的信息，这是目前比较成熟的技术。医疗，地质，探伤等领域会普遍用到三维重建的切片技术。

对于几何来说，BREP是万能的吗？

在很多领域，基于BRep的几何内核派不上用场。比如医疗行业，人的各种器官都是非常不规则的几何体，只能通过表面的三维细化面片重建。而基于BRep的拓扑几何结构过于重量化，海量的三角面片如果使用BRep，性能会非常差。

在CFD仿真中，大部分的模型都是基于面片数据，比如STL数据格式，而很少使用SAT，X_T，STEP等格式，即使使用了这些格式，最后也只是拿三角化后的数据。

在很多专业设计领域，比如需要很多流线型的曲面曲线非等值面设计，基本都会使用专业的设计方法和工具，而不会使用BREP结构。

对于一些复杂的数学方程和公式定义的异形几何，BREP也无能为力。

为什么几何内核是工业仿真软件的基础之一

(点击链接查看) 一文中，我们看到几乎所有的CAD/CAE/EDA/CFD建模仿真软件都会使用PS或ACIS两种内核。

其实原因也很简单，工业仿真软件最大的几个特点：稳定性，可靠性，性能，以及兼容性! ACIS/PS的底层应用非常成熟，基于ACIS/PS的不同程序之间可以直接无损交换数据。

虽然我们可以看到ACIS/PS每年都在更新，但实际上底层的结构还是几十年前的，不曾动过，现在的更新更多的是上层应用以及来自客户新需求。

有人会问：为什么不能超越ACIS/PS？

其实这种问题就类似于：为什么不能发明一种新的键盘？

不是不能超越ACIS/PS，而是超越的成本太高，而且这种成本并不是单指通过砸钱，很多有用的实际功能都来自于工程实践和用户迭代，这些都被封装了起来。

之前就说过：对于长期从事工业仿真软件研发的企业来说，几何内核的研发是必要的，但是不需要做类似ACIS/PS通用的几何内核，而是要做针对自己行业的，针对业务流程的轻量级的几何内核。使用商业内核的绝大部分企业都只使用了其中非常小的一部分功能（可能10%都不到），却要支付高昂的license费用。

发展到今天，几何内核和其它工业软件基础技术一样，技术上并没有太大的突破。主要是来自客户的需求以及应用层面的改进。

其实除了大家耳熟能详的ACIS/PS/OCC等几何内核，市场上还有许多做内核的小公司和企业，只不过名声不大。笔者接触过的至少就有7,8家。有些确实做的不错，有的有不少亮点。

相比于单纯的三维CAD设计建模，工业仿真软件对几何内核有更高的要求。以后几何内核的发展更多的源自于上层应用需求，比如CAD/Mesh无缝结合，性能持续改进，直接介入用户业务等等。

“草图”是一个专业术语。我们设计一个对象或者绘制一个对象时，开始很难用三维进行建模，通常的做法是先用二维表示，工程上的图纸一般也都是用二维表示，比如我们常见的俯视图，侧视图，截面图等等。AutoCAD之类的绘图设计软件最初都是二维的。

有人可能觉得二维比较简单，没什么难度，实则不然。单个的二维对象确实比较简单，点线面数据通过基本设计即可实现。

两个互相咬合的齿轮，已经分别设计出齿轮的半径，进行了咬合。现在需要修改其中一个齿轮的半径，如果只是简单的分别绘制出两个齿轮，其中一个改动后，另外一个也需要手动修改以保证齿轮咬合。一般的做法是将两个齿轮关联，一个改动后，另外一个自动修改以保证咬合。如果一个齿轮同时和多个齿轮相连，则涉及到多个同时关联。

再考虑一种情况，在平面墙上绘制门和窗户，当我们修改墙高度和宽度的时候，门和窗户要随动，比如我们加了约束（窗户不能靠房顶，门底和地面平齐等等），随动要满足这种约束关系。

这就引申出几何内核里的一项基本功能：约束设计求解器。

约束设计求解器在于给定各种约束情况下，求解类似刚体运动自由度方程，约束设计求解器常用于二维草图绘制，零件在装配体中定位，以及各种几何外轮廓的绘制。

2. 三维实体建模，属性计算

三维实体建模是几何内核的基本功能。基于几何特征，几何内核需要提供完整的实体表达。最常见的长方体，根据长宽高等参数建立起对应的数据结构。以BREP为例，一个长方体至少包含如下信息：

1个体，6个面，6个环，12条边，12条有向边，8个顶点，8个顶点的坐标

这也是为什么专业软件的几何文件很小，而三维几何模型文件大的原因。

除了长方体，圆柱，圆台，圆环，球，锲形等各种基础实体模型外，各种常用的建模方法也是必须的，常见的拉伸，扫掠，放样，阵列，平移，缩放，矩阵变换，布尔运算，拆分。

创建的对象实体要提供边长，面积，体积，包围盒等基本信息。

历史系统主要用来跟踪记录几何对象的变化信息。这些信息在参数建模和约束建模中要经常使用，是undo/redo机制的基础，同时也是几何模型质量的保证。

一步步设计好模型后，保存工程文件，关闭程序退出。再次打开工程文件，需要undo进行编辑

一个复杂的模型，执行到某一步出现错误，整体模型坏掉，需要恢复到上一步模型完好的状态

一个模型，需要进行一些修改才能拿到某些信息，但是并不希望对模型本身进行修改

以上需求都可以通过历史系统来完成

几何对象一般不会单独存在，几何对象上会有很多属性，比如颜色，显示方式，材料，业务类型，参数。对于数值仿真，还会有各种边界，荷载等信息。附加在几何上的属性系统也会涉及到增加，删除，修改，以及随几何变动而变动，比如两个不同属性的几何进行并运算，并之后新几何上的属性系统要有明确的设定。

5. 参数建模和约束建模

参数建模和约束建模都很好理解。底层需要有参数系统，基本功能包含参数表达，驱动更新，参数表达式计算，几何对象参数管理，以及约束求解器等等。这些功能是CAD软件几何设计(Design)的基础，而非Drawing

几何拓扑，属性系统，历史系统，参数建模和约束建模构成了几何内核底层管理的基础。

几何内核要提供几何离散化功能，主要有两个目的：1. 生成基本的三角面片信息供渲染使用；2. 提供更多参数控制的面片的生成，以满足上层业务不同的需求。

位置运算提供各种几何之间的位置信息计算，常见的线线，点线，线面，点面，面面，面体，线体等各个维度几何的距离，相交，交点等信息。

通常位置运算需要大量使用计算几何或数值计算方法，这也是几何内核底层的基本功能之一

布尔运算涉及到两个对象之间的合并，减，公共基本操作。在基本操作上衍生出切分，投影，缝补等操作。布尔运算主要涉及到线线，面面，面线的求交和裁剪运算，后续详细介绍。

布尔运算的准确性，稳定性和性能是衡量一个几何内核质量的重要标准

识别模型中的倒角，突出，凹陷，以及常用基本几何实体，并对其进行编辑操作。

在实际工程中，通常使用的软件和数据文件格式有多种，为了保证整体数据格式的统一，几何内核需要提供与外部的数据的接口，即能导入和导出第三方的文件格式。这一块和几何内核没有直接关系，技术上也没有太多难度，主要问题是不同数据格式的接口兼容性问题，比如公差，数据表达转换。

这个在  已经做过介绍，不多讲。

除非建立封闭的生态系统，否则这是几何内核工程应用的一个基础模块。在建模工程中，因为种种原因导致模型出现问题，比如各种拓扑和几何不满足设定条件或者出现错误。这种错误会导致模型本身的分析，比如面积，体积计算出错，还会导致仿真的网格划分出现错误。

除了提供模型的拓扑几何检查外，还要提供基本的清理，修复以及必要的编辑功能。

很多时候CAD设计的模型即使没有错误，也无法用来直接仿真，比如CAD设计中的小边，小孔，倒角，印刻的字体，需要在划分网格前对其进行删除清理。

除了模型几何对象本身的错误外，实际应用中还要进行诸如几何对象之间的干涉检测，自由对象，重复对象的检测操作。这些功能可以在业务层实现，也可以在几何内核中完成。

几何内核本身是没有图形显示系统的。换言之，几何内核创建的数据无法直观的表现出来。为了将几何对象显示，需要和外部的图形显示引擎合作。

通常的做法是将几何对象离散化面片，然后送给图形显示引擎显示。离散化的面片和几何对象建立映射关系，以方便后续的操作。

14. 提供仿真所需的几何功能

比如提供抽中面，供有限元分析中的壳单元使用；三维实体简化成一维单元，供有限元分析中的杆，梁单元使用；处理非二维流体，以解决复合材料，流体，碰撞，接触分析中的共形网格；提供高次曲面以满足透平机械设计分析需求等等

提供脚本系统，便利上层应用的开发和调试

16.提供必要的调试工具

使用几何内核出错后，往往难以检查和调试，提供必要的工具帮助发现和解决错误

提供工具方便上层应用使用多线程，多进程以及分布式计算

为了涵盖B-Rep结构

(Boundary-Representation)的基础操作，需要定义一些基本的数据结构。参考OCC的BREP结构定义，几何上至少需要定义：

Point 包含基本的坐标X，Y，Z信息以及索引号。

Curve作为抽象几何定义，又可以衍生出各种形式的几何曲线，比如直线Line，圆弧Arc，椭圆弧Ellipse，样条曲线，NURBS，B样条等等。

考虑其中最简单的直线定义：

只需定义两个端点索引即可，其它信息都可以根据端点信息算出；

需要定义一个端点，再给出射线的方向（方向为三维向量Vector，需要单独给出定义，包括三维向量的加减乘除，归一化等等操作）

无限直线有多种定义方式，比如函数表达式，或者给定过直线一点以及方向等。

Surface的几何衍生类也类似。

拓扑自底向上至少需要定义：

在机械加工CAM，仿真CAE,CFD,EDA等领域，我们需要知道附加在某个三维实体的属性信息(Attribute/Property)，最常见的就是材料信息(Material)，这类信息在几何对象进行修改时，需要继续保持其属性，因此需要一定的Cell数据结构来进行操作。

其中Face的基本定义：

Face的数据结构中至少要包含如下信息：

1. 包含的所有Loop信息；

2. 引用的几何面所定义的几何信息；

3. 能直接取到Face以下所有的拓扑信息，包含Edge,Vertex；

4. Face所定义的边界信息；

5. 继承自拓扑基类的其它信息，比如ID，矩阵转换(Transform)，局部坐标系(Axis)等信息
   

定义拓扑信息的目的是将位置关系和几何关系进行关联，方便后续数据操作，比如查询，遍历，计算等。

下面在中以一个简单的三维实体四面体的创建，描述基本的B-Rep结构自底向上的构造过程。

1. 首先创建四个点坐标

2. 开启3D捕捉和顶点捕捉，将点两两之间用直线相连

从视图上，我们已经可以表现出一个三维四面体实体结构了；但是这对于B-Rep结构还远远不够，我们需要将完整的拓扑结构建立出来。

2. 在点的基础上构建边Edge

由点的坐标可以构建成一条直线Line，Edge可以由两点构成，Line和Edge建立映射关系，需要注意的是所有的Edge是有方向的，即一个面上的所有边的方向首尾相接而成。

所有的Edge可以构成一个环Loop，环最重要的特点是有方向性，可以作为内环和外环。比如一个面Face里有个孔Hole，Face的边界为外环(Outter Loop)，孔的Loop为内环(Internal Loop)，内环的方向通常和外环方向相反。

三条Line构成一个封闭的平面三角形Surface，Surface和Face可以建立映射关系。一条Loop就可以构建面的拓扑结构了，同样，面也有方向，右手左手准则都可以，所有面的准则保持一致即可，四根手指的方向指向Loop的方向，大拇指方向即为面的方向。Face的方向除了对显示光照有用外，对使用有限元单元方法的刚度矩阵计算和组装也非常关键。

有了面的信息后，就可以将所有的Face定义成一个Shell，然后将Shell封装成一个实体Solid。

这样我们就构建了一个完整的四面体B-Rep实体数据结构实例。

需要注意的是，非封闭的Shell无法构建成实体。比如一个长方体(Cuboid)，在删除一个面后就不能构成实体了；从拓扑完整性上看，是不允许删除一个长方体的一个面；但有时候为了操作方便，有些前处理软件提供了Release功能，即允许删除长方体的一个面，在面删除后，实体自动退化成由五个面构成的Shell，在缺失的面补上后，又可以通过Shell生成实体Solid。

可见，如果使用B-Rep数据结构自底向上的方法创建三维实体是一件非常繁琐的事情。为了方便，一般会提供一些常用的基本实体的创建函数，比如长方体Cuboid，圆柱Cylinder，圆环Tours，圆台圆锥Cone，球Sphere等。

以上所定义的是基本的B-Rep数据结构，在这些数据结构的基础上，还可以根据实际需要或业务需求衍生或者减少数据结构定义。比如常见的实体Solid结构，如果存在大量Solid合并操作时，可以再派生出类似Assembly或者Compound实体结构。对于没有面组操作的实际业务，Shell可以拿掉。

综上所述，B-Rep数据结构是一种比较通用的三维数据结构，它能涵盖大部分三维设计工况；但也正是因为通用，数据结构尤其是拓扑设计比较庞大，在处理大模型时存在性能上的瓶颈。对于实际业务比较固定的情况，可以根据需要设计开发轻量级的三维几何数据结构。

在B-Rep拓扑结构中，我们知道实体Solid是由Face构成的，Face和Surface几何面关联（如图），因此在实体内部不存在数据，这个与体渲染形成了鲜明对比，体渲染在实体内部存在数据，也就是说用一个平面切开体渲染实体后，能够得到截面上任意一点的数据。

Parasolid几何面与拓扑面对应关系

所以从数据结构上来看，几何面的创建和处理是三维内核几何操作最核心的功能，几何面处理好了，其它几何操作都不是问题。从以下Parasolid的结构图中我们也可以看到曲面占据了几何主要地位。

在实际生活中我们绝少见到方方正正的设计，大部分都是需要用曲面处理。

各种奇特外观建筑是曲面设计的用武之地

发动机，螺旋桨对曲面设计和制造都有非常高的要求

通常我们将曲面分为两种：解析曲面和样条曲面，又叫插值曲面。

很好理解，解析曲面有函数表达式f(x,y,z)，即给出任意坐标值，可以准确的计算出该坐标的数据，有点类似偏微分方程的解析解，解析曲面通常可以高阶连续，在研究特定图形时很有用。解析曲面虽然是解析解，但很多时候能够构造出非常奇异的形状。如下图：

正如偏微分方程很难找到解析解一样，工程中设计很难找到预先定义好的用函数定义的曲面，设计中更多使用的离散点生成样条曲线，再利用样条曲线构成样条曲面。

回顾一下样条曲线的相关知识。

4.NURBS曲线（非有理样条曲线）

样条曲线1,2,3是NURBS曲线的特殊形式。设计曲线时，通常会给出一系列的离散点，再用曲线将该离散点拟合，形成不同的拟合表达式。拟合方式的不同构成不同的曲线。曲线通常使用控制点，控制点权重，基函数阶数，分段拟合表达式等来控制曲线生成。

下图显示了中利用多个控制点生成封闭B样条曲线

T样条曲线(T-Spline)是在2003年出现的一种新形式的样条曲线，最早放在Rhino作为插件使用。相比NURBS，生成相同的曲线，T样条曲线只需更少的控制点，和NURBS曲线也可以互转。

T样条控制点只需NURBS的大约1/3

关于样条曲线的理论计算和设计实现可以参考附录1.

任意曲面可以建立到规则平面的映射

NURBS 曲面是最通用的一种曲面形式

NURBS 曲面与 NURBS 曲线非常相似。可以将 NURBS 曲面视为位于两个方向上的 NURBS 曲线的栅格。NURBS 曲面的形状由多个控制点以及该曲面在 U 和 V 方向的阶数定义。相同的算法用于通过控制点、权重和阶数来计算形状、法线、切线、曲率和其他属性。

了解了曲面的基本参数，下面看看在设计中如何生成曲面

扫掠是规则曲面的常用方法，包括路径扫掠，自定义规则扫掠。绕轴360度旋转是一种特殊的扫掠。

一个简单鼠标全部由自由曲面构成

模板是事先定义好的曲线方程，或者控制点预先定义好的Pattern。最常见的模板就是圆角倒角。CAD软件中，用户并不需要实际设计圆倒角几何，修改简单的参数即可生成相应的倒角模型。

连续性是曲面的一个重要特征，反应了曲面的光滑程度和质量。

 Geometric continuity，通常记作G(N)，N表示曲线或曲面可连续可求导的阶数。G(N)的连续性是独立于表示（参数化）的。

G0两个对象相连或两个对象的位置是连续的。G0连续（也称为点连续）在每个表面上产生一次反射，这种连续仅仅保证曲面间没有缝隙而是完全接触。

G1两个对象光顺连续，一阶微分连续，或者是相切连续的。G1连续（也称为切线连续）将产生一次完整的表面反射，反射线连续但是扭曲，这种连续仅是方向的连续而没有半径连续。我们通常的倒圆角就是这种情况。

G2两个对象光顺连续，二阶微分连续，或者两个对象的曲率是连续的。G2连续（也称为曲率连续）将产生横过所以边界的完整的和光滑的反射纹。曲率连续意味着在任何曲面上的任一“点”中沿着边界有相同的曲率半径。外观质量要求高的产品需要曲率做到G2连续，其实曲面做到这一点难度很大。

G3两边对象光顺连续，三阶微分连续等

曲面布尔运算是比较容易出问题的地方，主要在于面被裁剪后，一方面需要重新计算端点，曲边需要重新插值计算，造成容差问题；另一方面如果曲面在相交面上，新生成的截面在仿真划分网格时会导致网格不匹配。在曲面布尔运算时，尽可能用曲面参数计算，对于存在非二维流形和截面的情况，需要保存双面的映射关系，而不能仅仅让B-Rep结构来处理。

曲面曲线的显示类似于圆弧和圆面的显示，圆弧需要将曲线离散成小段直线，圆面需要离散成三角形，圆周为连接的小线段。需要注意的是边界离散长度确定，通常利用弦高比，即计算曲线上点的切向和角度。参考OCC里网格生成方法：

对于设计类CAD软件，曲线的显示最好能采用矢量方法，以避免视图显示和实际几何产生误差。

商业软件方面，一般三维CAD软件都有曲面建模功能，但从工业软件和总体功能和效率上看，犀牛Rhino和CATIA在曲面建模上更有优势。

曲面处理的理论基础和计算是几何中最复杂的，也是衡量一个三维几何内核质量的重要指标。本文在之前文章的基础上进一步介绍了几何内核曲面的相关基础知识，其涉及到的理论公式都没有列出，有兴趣的读者可参考附录以及相关书籍。

1. 计算机辅助几何设计与非均匀有理B样条，作者：施法中

布尔运算是三维几何内核的一个基本功能，其功能，稳定性，性能直接反应了内核的质量。

1.布尔运算的基本原理和算法

2.布尔运算里的一些高级功能

3.OCC的布尔运算功能

---

1.布尔运算的基本原理和算法

常见的三种布尔运算：并集，交集，减集。其实这三种布尔运算的前面运算逻辑是一样的，最后一步不同。

1.并集就是把两个物体合并成一个物体

2.交集是求两个物体公共的部分

3.减集是从一个物体中减去两个物体公共的部分

为了简化描述，我们只讨论实体Solid和实体Solid的布尔运算，其它类型几何之间的计算类似(比如面Face和实体Solid，面Face和面Face)。

在一文中，我们知道基于B-Rep的三维结构都是由面Face构成，所以三维实体的布尔运算也是基于面Face的几何信息，相比单纯的面Face和面Face之间的布尔运算，三维实体Solid布尔运算多出的一步是需要维护Face拓扑之上的SHELL和BODY等拓扑信息，而几何信息则是完全相同的。

布尔运算基础算法涉及到的计算有：

1.几何面的相交计算，需要得出交点，交线等几何信息；

2.基于原始拓扑结构，对Face面进行裁剪；

3.裁剪区域Edge边和顶点Vertex的拓扑重建。

1.判断两个实体是否有重合。为了加快计算效率，可以首先使用包围盒进行过滤，即包围盒如果不相交，则两实体一定不会相交；还可以判断一个实体的点是否在另外一个实体里，如果在那两实体一定相交，这些加速算法可以在任一拓扑层级进行，后续再做详细介绍。

2.假设已经确定两个实体相交，遍历一个实体的面，计算每个面和另外一个实体的面的相交情况。面面相交通常是一条线Curve

3.将所有相交的线Curve分别加到原来的两个实体Solid上

4.根据实际操作需求(并，交，减)，对两个对象进行裁剪以及重新生成新的拓扑结构。

以两个长方体布尔并运算为例说明

布尔运算一般是两个物体，按照顺序习惯将第二个物体叫Tool，也就是加工工具的意思，第一个对象OCC里叫Object，PS里叫Target，ACIS里叫Blank。

初始两个相交的立方体A和B

计算出所有相交面的边，将拓扑边和几何信息加到物体A上

计算出所有相交面的边，将拓扑边和几何信息加到物体B上

交集：只需要把计算出的公共部分进行拓扑重建即可

并集：将公共部分的拓扑和几何去掉，保留A和B，拓扑重建

减集：将对应的原始部分去掉公共部分即可，拓扑重建

在这个过程中，反复提到了拓扑重建。我们在中建立了基本的拓扑结构，其目的之一就是在对物体进行编辑修改后，还能用基本的拓扑结构来表达三维物体。布尔运算之后同样也要遵守初始的拓扑规则定义，比如我们建立的面的方向，Loop的方向，Edge的方向等，仍然要保持一致。

这里只是介绍了基本的布尔运算，实际中会有更多需要处理的复杂情况：

1. 非二维流形的处理

2. 高阶曲面的求交精度问题

3. 不同维度几何求交，线面求交，线体求交

4. 复杂几何拓扑重建

---

2.布尔运算里的一些高级功能

在基本运算的基础上，根据实际需求，衍生出很多相关运算。

Chop，顾名思义就是削除。它是布尔交和布尔减得合集。

2.不同维度对象的布尔运算：

前面介绍的是实体Solid和Solid的运算，在实际中有大量的面Face和实体Solid，Edge边和面Face，Edge边和实体Solid的计算。底层计算本质上也是一样的，只是拓扑重建步骤不同。

压印，通常我们需要把线或者面放(印)到另外一个对象上。

Cell结构在B-Rep结构提出之后不久就被提出来。Cell结构对应于实体Solid，主要用来保留，编辑，追溯Solid实体的属性信息。

Split分割操作可以将一个实体Solid分成两个或多个实体。本质上也是一个实体Solid和面Face的布尔运算

在某些情况下，我们知道两个对象的一些特征，比如两个大的模型，都只在某个面上有重合，可以采用Glue粘贴操作，也就是指定Glue的拓扑，只在特定位置进行布尔计算，这样可以大大提高操作效率。Sew也是同样的道理。

也就是模糊布尔运算，在某些场合通过设置一定的容差和参数，可以稳定的处理模型接触地方近似一致，轻微干涉，不对齐的情况

布尔运算是一种非常耗时的运算，所以在针对大规模和特定场景时，需要用一定的加速算法来提升性能。

在机械加工中，要在某个复杂的对象A上钻100个孔，这是一个典型的布尔减运算。通常做法是创建孔的几何，然后再一个一个的执行布尔减运算。由布尔运算算法得知，每次运算都需要遍历几何的面进行面面相交计算。如果我们先将孔进行并运算得到B，然后再用A布尔减B，虽然面面相交计算次数没有减少，但是相应的各种过滤和无用算法调用次数会减少很多，能显著提升计算性能。

---

3.OCC的布尔运算功能

ACIS和PARASOLID里提供了大量的基础布尔运算和相关扩展功能，其中许多来自于实际应用需求，比如ACIS中有针对符复合材料，流体，多物理场的非二维流体的布尔运算，PARASOLID里的实体抽中面，Blend运算等。

笔者多年使用PARASOLID，ACIS和OCC，考虑到前两者都是商业内核，就不展开描述了。

需要说明的是PARASOLID，ACIS，OCC都是通用三维几何内核，在布尔运算方面也都是中规中矩的运算，针对很多实际业务时性能并不一定最优，还有很大的改进余地。之前见过一些做几何内核公司，拿特定的布尔运算和测试用例做性能比较，得出PARASOLID和ACIS布尔运算性能较差的结论，其实意义不大。不过这也说明如果能开发专业而非通用的几何内核，在业务上可以大幅提升性能。

稍微介绍下OCC里的布尔运算：

经过多年的发展，相对于早期的版本，OCC在布尔运算上可以说是有了质的飞跃。以7.3版本为例，实际应用中，包含两个对象的100M以下的STEP文件导入后，布尔运算可以稳定的实现，虽然相比ACIS和PARASOLID性能方面还有不少差距。

在OCC的文档中，有一篇文档

occt_boolean_operations.pdf是专门介绍布尔运算的，文档不仅介绍了相关API的用法，而且详细列举出了各种布尔运算的应用场景，覆盖了实际应用中的大部分情况。

对CAE工程师而言，几何修复清理是一个比较头疼的工作。因为这项工作不确定性因素很多，不仅要求工程师对几何数据和修复工具比较熟悉，对经验也有较高的要求。

相对于三维几何其它内容，几何修复清理是一门操作性和实践性较强的工作。

下面说明几种常见的几何修复清理场景：

1. 从外部导入的三维模型数据，在导入的过程中，因为转换问题比如精度，单位，数据不兼容等出现数据丢失，转换误差，模型损坏等。

2. 模型本身有问题，比如画线的时候没有使用捕捉，导致线线不连接；模型里几何应该对齐，但是因为容差导致出现细缝和小边；曲线处理不当导致模型几何之间出现干涉；模型数据不完整，导致出现实体面丢失，拓扑不完整和几何数据出错，出现自由边，自由面，重复对象等。

3. 仿真中不需要或者对网格划分影响较大几何特征，比如倒角圆角，logo等，细小边，面，体都需要在保证拓扑几何完整正确的前提下移除。

4. 无用几何数据。比如做飞机外流场仿真，只需要模型的外表面几何数据。而内部的诸如发动机零部件等都可以省去。可以直接删除内部几何，对于局部完整数据可以直接用其它模型替代。

5. 模型对象之间位置偏差，之前提到的模型之间的干涉，细缝等，对于复合材料，多物理场以及装配体，接触碰撞分析都是必须要修复的内容。

6. 一文中介绍了曲面相关知识，曲线的信息在转换，导入的时候更容易出问题，比如方程转换出错，连续性出错，阶次降低，在进行计算后出现容差精度问题。

一般的三维CAD软件中都会提供几何修复功能，专业的几何修复软件比如

CADDOCTOR，CADFIX 也都专门针对几何清理，还有一些专业的前处理软件比如HyperMesh，ANSA等几何修复清理也是必备功能，有些仿真软件也会提供基本的几何修复清理。但是这些软件的侧重点不太一样，CAD软件的主要目的是将几何拓扑修复干净，保证没有错误；而前处理器和仿真软件则是需要保证网格划分所需的输入几何正确。

在笔者看来，几何清理修复分为两种，分别是技术上和工程上的。

技术上是指把错误的对象修复正确，无用的对象清理干净，解决容差问题等，这个很好理解。

而工程上是指不一定要把错误的对象修复正确，而是采用一切手段将模型清理修复到一定目标即可。

从第三方导入的模型有问题，首先想到的是将模型导入到模型创建软件中，在软件中进行编辑，这样的好处是可以无损编辑，最大可能的保留原始模型信息，比如历史信息，参数信息。也可以解决因为软件版本不同，设置不同以及机器环境等造成的问题，有点类似于常说的第一性原理，把问题解决在最开始的地方。

如果做不到的话，在导入模型后，首先进行分析，分析出错的地方，能不能删？用简单模型替代？只做部分修复？用已有的网格替代？通过简单的平移，旋转，缩放等操作解决？通过修改容差解决？设置一些异常属性，比如结构分析中当做刚体使用，对称阵列结构能不能使复制正确的对象粘贴？等等。这些操作并不是一定要修复错误，而是保证整体模型可供后续仿真使用即可。

1. 拓扑相对容易修复，即按照原始定义的拓扑结构重新组织结构即可

2. 几何是比较难修复的，尤其是转换过程中出现的错误，通常没有太好的办法，即使修复了，也仍然会有很多警告信息

3. 需要提供模型检查工具，对于有错误或警告的内容，要尽可能给出详细的信息；即使不能修复，用户也可以根据检查报告信息给出相应的对策。

4. 特征识别和模式识别是三维几何里比较有挑战性的工作。目前少有全自动的识别功能，依赖于一定的输入参数和人工干预。

5. 容差系统是三维几何内核一个重要的底层系统，很多修复内容和容差系统相关。通常说的多尺度仿真在几何方面直接依赖容差系统。

总的来说，几何修复清理功能是三维几何内核一个可选模块，也是CAE/CFD前处理软件中的一个重要功能，前处理软件主要是导入几何，修复几何和生成网格，少有直接在前处理器中建模。由于该工作很大程度上依赖于业务，因此三维几何内核一般只提供比较基础的检查，修复功能，更多的是在内核的基础上建立适用业务的功能。

本文介绍一些几何内核经常使用的一些技术内容.

树是几何和图形学中一种常见的数据结构。比如最常见的二维平面四叉树，三维空间八叉树，它的基本思想来源于二分查找，是线性二分查找在高纬空间的扩展。

以平面为例，如图有大量的图元数据，在软件中执行选择操作的时候，需要对每个图元进行计算，判断鼠标位置和图元的关系。可以预先将图元结构放入四叉树结构中，首先判断鼠标和四叉树是否相交，加速过滤，避免进行全局计算，三维空间八叉树也是同样的道理。

四叉树，八叉树除了用来加速过滤，还可以用来查找，生成有限元中的网格。在标准四叉树八叉树的基础上，又衍生出了各种树的变种结构。常见的有KD树，BVH，R树，BSP树等，基本原理也都是利用分治来加速对象过滤。

一般来讲，数据越多，加速效果越明显。在以往测试中，千万级别的三维图元数据，通过合理的八叉树结构加速，查找次数可以降低几个数量级不到千次的查找。

容差控制是几何内核的一个重要内容。容差设置决定了能处理模型的最大和最小范围，邻近的两个点在计算（比如布尔运算）中是否会作为一个点，相邻的两个面是否作为一个面，点是否在面上，进而决定了几何拓扑的构建和整个模型是否有效。特别是针对样条曲线和曲面，容差出现问题，会导致一系列难以修复的问题。通常容差在整个模型初始时会设置好固定值，但有时候会有修改的需求；在几何内核端需要做好设计，做一定的保护机制，防止修改造成的各种问题。

C++的数值精度通常float型为6位有效，double型16位有效。在几何建模中一般使用double型数据，double型能满足大多数建模精度需求，但有少数情况不满足计算精度，比如多尺度建模，超大数据模型，细度网格划分等，要引入类似GMP，BigNum等数值库对数据进行更精准的控制。

需要注意：容差控制和数值精度是两个概念，避免混为一谈。

复杂建模是相对于简单的三维实体(Primitive)而言，比如放样，扫略，镂空，中面提取，Blending，offset。这一块看起来很复杂，其实在几何内核里相对来说还是比较简单的部分，主要涉及到拓扑和几何数据的重建，基础功能做的好的话，这块基本不会有什么问题。

对于仿真类软件，从技术上来讲，几何和网格其实是不分家的。如果几何内核能直接生成仿真所需的网格那是最好不过的。但实际上几何内核一般只会生成无参数控制的三角面片，也就是最基本的Delaunay离散方法。几何内核生成的三角面片数据和仿真所需的网格数据之间还有很大的鸿沟，这点在里有详细描述。

这里的数据库系统主要是用来管理数据，主要是在几何内核使用过程中对象创建，编辑，销毁等生命周期，历史消息维护管理，不是一般的关系型数据库。利用该数据库系统可以帮助上层实现类似undo/redo，历史信息查询，数据保护等。这个也是上层看不到，但是底层比较核心的功能之一。

微分几何现在是一门独立的学科，是运用微积分的理论研究空间的几何性质的数学分支学，最早和微积分发展紧密相关。前面讲过几何内核如果处理好了几何曲面，那其他的几何内容都没有问题。

拓扑学是研究几何图形或空间在连续改变形状后还能保持不变的一些性质的学科。它只考虑物体间的位置关系而不考虑它们的形状和大小。在拓扑学里，重要的拓扑性质包括连通性与紧致性。

几何内核常用的欧拉公式和非二维流型都来自拓扑学。

欧拉公式：凸多面体之间顶点数/面数/边数之间的关系

其中V代表G中点的个数, F代表G中面的个数, 而E是G的边数.

有朋友问，经常看见你提到几何内核和业务的关系，业务到底是什么东西？

做结构前处理的朋友一定非常熟悉壳单元，壳单元在有限元分析中是二维面单元，但几何数据通常为三维实体，所以需要把实体结构变成面结构，也就是类似把一个长方体变成一个长方形，有多种处理方法，一般是选取需要处理的面的中面，这样在结构上可以最大程度保持位置正确，也就是通常说的“抽中面”。

在几何内核处理上就需要根据实体信息，重新生成只有面几何的Shell拓扑结构，再将Shell通过合理布尔运算生成仿真需要的面结构。

“抽中面”就是一个典型的业务操作，最好在内核端提供支持。

常用的三维几何数据格式包括商业的sat，x_t，以及通用的igs，step以及各种三维CAD软件的数据格式。这一块其实没有太多技术难度，主要是工作量的问题，在数据转换过程中需要注意文件标准，一系列转换属性设置，比如单位，容差等。

好的几何内核是需要融入生态的，也就是要和第三方数据有接口进行互读互写。

几何约束求解器一般不作为三维几何内核的一个模块。商业几何约束求解器往往作为一个单独产品销售。几何约束求解器是CAD设计功能的一个基础模块。

本文简单介绍一下几何约束求解器GCS的基本知识。

---

曾经有一个朋友问到，二维CAD软件不就是画类似圆，直线图吗？现在还有技术瓶颈吗？

确实，现在二维CAD软件已经非常普及，而研发技术门槛也是一降再降，但是二维CAD还是有许多可以做的事或者优化空间，比如大规模场景管理优化，图形生成算法改进，渲染效率提升，行业CAD开发，上云，Saas，AI识图等，还有就是本文要介绍的几何约束求解器。另外类似标注排版，参数计算，容差设计，脚本系统，用户交互（拾取，捕捉，快捷操作等），硬件支持，跨平台等许多技术细节从头做要做好也非易事。

比如要建立一套可靠的参数系统，自己从头写商用耗时耗力。简单的参数系统就是可以自己定义变量并赋值，在实际使用的时候能用变量替代实际数据，而修改变量时，则整个程序中使用该变量都会修改。参数系统需要支持各种计算表达式和脚本系统，其开发涉及到词法语法解析，正则表达，软件框架设计等，从底层详细介绍的话写一本书是没问题的。

再比如标注排版系统，也就是一堆图元文字放在一起，按照一定规则排列，看起来是个非常简单的事情。但深究的话也涉及到了图论，约束优化算法等。

以上除了要实现基本功能外，还需要考虑到最重要的性能时效问题，对用户来说，设计阶段操作太耗时（点一个按钮等上1分钟），功能是没有实际用处的。

话说回来，如果二维CAD真的那么好做，也就不会有那么多基于IntelliCAD开发的商业软件了。

---

说个题外话，曾经有圈内朋友吐槽国内某公司使用IntelliCAD做开发，没有核心技术，还做上市了。其实大可不必，我们最终提供给用户的是产品，如果能集中有限的资源，开发出产品帮忙用户解决实际问题，比光喊“自主”口号强的多。一切照章办事，就没有什么可吐槽的。但是如果一开始明知有风险，后来出问题了又喊“卡脖子”就是另外一回事了。

还是那句话：工业软件也是商品，靠的是质量，最终服务的是客户！

这就是为什么笔者一直强调的：中国将来的仿真巨头一定是有自己核心技术，旗舰产品，讲究产品细节，服务于全球客户的公司，而不是其它。

而现在在工业软件领域经常讲的所谓“自主可控”，相当一部分是营销的幌子，或是“低质量”的挡箭牌，需要擦亮眼睛识别。

---

在CAE软件中，有一类仿真分析是针对刚体运动，比如ADAMS，

DADS(LMS Virtual Lab)，刚体运动也就是物体本身不发生变形（比如我们高中时学的动量守恒之类的运动都是简化的无约束的刚体运动，参考），基于对象之间的几何形态，相互连接关系，计算物体的运动情况，比如接触，碰撞；除此之外，还要时间，位移，速度，加速度等，以及受力状况，为其它类型分析准备输入数据。

刚体运动计算和CAD中的几何约束设计类似，只不过前者需要考虑各种外力（比如重力和物理因素影响），看重仿真模拟，偏向基于物理数学方程求解，而后者着重在几何计算和设计，算法实现上更偏向于数学方法。

狭义上，我们通常讲的GCS主要是为CAD设计服务；广义上，GCS就是用来求解多(刚)体动力学的。

在"十四五"软件和信息技术服务业发展规划，关键基础软件补短板的专项行动中，首次提到了约束求解引擎，并将其定义为"关键技术"。

二维GCS，又叫草图几何约束求解器，简称草图约束，它描述的是在二维平面设计时所用的几何约束功能。

二维里常见的三种约束类型：

尺寸约束：点点距离，点线距离，线线夹角，圆弧长度，圆和圆弧半径

结构约束：线水平或垂直，两线平行，线和圆相切

业务约束：用户自定义参数变量之间约束。

以下是开源参数化建模工具SolveSpace里列举的约束类型：

约束求解对用户最简单直观的表现就是在创建对象时候的捕捉设置。

比如：已生成一条直线，再画一条直线与其垂直。确定一点后，另一点的鼠标在移动过程中需要反复计算垂直约束是否满足。而垂直计算就涉及到最基本的对象位置关系计算。这一点在提及过。三维几何内核的曲线曲面有两种表达：方程式和离散式（）。所以约束在求解上需要支持线性方程组和非线性方程组。

考虑三维，约束内容除了从平面坐标扩展到三维坐标外，还有面面距离，面面垂直，点面距离，球形曲面于平面，直线相切以及共轴共点共面。

还是以CAD设计的GCS为例，通常用自由度，约束度，剩余自由度，和约束关系内容来记录每个对象的状态(这里的自由度和刚体运动的自由度相同，而非有限元中的单元节点自由度)，用来记录图元的任意时刻的状态，并将状态用图来表示，最后求解图：

这个过程中涉及到了参数表达驱动，大量的位置判定，计算迭代，以及图论相关和线性非线性方程组的求解。计算结果可以是确定的，也可以是方程。所以还会涉及到符号表达计算。

在实际设计中，会涉及到多重约束，即多个图元相互关联，当这种约束过多时，性能就会成为一个瓶颈。CAD的GCS，时效性是一个需要考虑的重要因素，毕竟用户可以等待CAE仿真，但在CAD设计阶段，一个命令等待时间太长是不太合理的。

GCS在技术上其实比较成熟，目前GCS的工作内容还是在已有求解方法的改进，性能提升和根据业务功能拓展上。在这个领域也有不少开源的工具，比如SolveSpace，chrono，ODE等，有兴趣的朋友可以参考。

本来打算在系列9中介绍属性关系等相关计算。

这一块其实也是三维几何内核的一个基础内容，它包括了线线， 线面，面面，线面实体的各种位置关系（重合，包含，干涉），相交（交点位置，个数），距离（最近点），这些内容是内核其它操作的基础(比如布尔加速运算中，要提前判断两物体是否相交，是否重合，重合的范围等等)；

也是其它上层应用的基础：比如常用的鼠标捕捉拾取操作，基本原理是从鼠标点位置垂直视图创建一条射线，然后判断射线和视图内几何图元的相交情况。如果某图元在容差范围内和射线相交，则可认为被鼠标拾取，然后后续进行高亮等操作。

物体的长度，面积，体积，质心，截面各种惯性矩也是上层应用的基础数据内容：建筑工程中的算量，三维容器倒入液体后的容积刻度，有限元一维梁杆单元截面各种属性，0阶质点单元，CAM中数据加工，容差分析，物料系统都需要几何相关的属性数据。

在整理这块内容时，发现并没有太多技术瓶颈，或者比较难理解的概念性内容，都是数学计算公式以及积分，插值，迭代算法等一般的数值计算，本着一直去公式化科普的原则，就不展开介绍了，附录推荐相关的几本书。

简单分析一下几何内核未来的一些发展趋势，注意是几何内核

几何内核发展到今天，其技术基础和市场环境都相对稳定。造成柯达，诺基亚等厂商没落的颠覆式技术出现的可能性非常小。翻阅ACIS/PS/OCC过去十年的release notes，从改进的数量，内容以及影响力看，就会发现，几乎都没有像样的功能大改进。其中PS提出的Convergent Modeling概念，从技术角度看只是BREP数据和面片数据的进一步融会贯通。而通常所说的Generative Design属于应用层面的内容，和几何内核没有直接关系。

1.提升性能。早期的内核数据结构设计并没有考虑到硬件的发展，默认按照当时的单CPU单核设计。而现在多CPU多核，分布式，GPU计算已经相当成熟。多线程已经在使用，但也只是基于一定接口使用，由于历史原因，这块商业和开源内核底层改进进度都比较缓慢。现在除了工业设计仿真软件外，很多业务场景对实时性都提出了很高要求，目前这一块几何内核还达不到要求。纵观近十年技术领域的发展，相比于人工智能，机器视觉，大数据，互联网的发展速度，几何内核的更新和发展速度可以算得上是龟速了。

2.进一步轻量化。PS提出的Convergent Modeling的初衷就在于高效的处理三维打印数据，因为三维打印数据为海量三角面片，用纯BREP结构表示性能低下。而CM正是通过简化BREP数据和操作，并融合面片数据，来处理这个矛盾。根据需求进一步简化或者轻量化数据结构，类似于“外科手术”式精准操作。

3.BREP增强。BREP是目前主流三维几何内核的基础数据结构，但这并不意味着BREP等于三维几何内核数据结构。就如同CAD不等于AutoCAD，CAE不等同于ANSYS。BREP的优缺点之前做过描述，参见。BREP无法表达出三维几何内部的结构，如果要用BREP对内部数据进一步细化，需要将原有结构拆分，或者建立虚拟拓扑。而基于几何特征的一些算法(比如MAR中轴变换)或者类似体渲染的技术可以有效弥补这种不足。未来有可能将这些技术和方法融合到BREP结构中，在更小的维度实现对三维实体的控制。

业务融合。利用商用内核开发通用CAD软件其实性价比已经非常低，风险也很大，除非能在应用层整出点花样出来。通用三维几何内核提供了丰富的功能，但一般的仿真软件实际上能用得上的只有一小部分，性价比很低。所以未来如果开发几何内核可以和业务融合，根据业务情况建立更符合实际的内核结构和功能。早期的CFD前处理软件就是一个很好的例子。因为CFD通常需要处理的是表面数据，所以不需要基于BREP的结构，一般的CFD前处理器会自己构建一套几何数据系统。

5.人工智能。几何内核在拓扑跟踪，特征模式识别，对象计算，参数建模，约束求解方面是有一定的固定模式的，AI是可以发挥作用的。

---

需要说明一个观点或认识：在欧美工业软件研发行业，有很多细分领域由某些小公司主导，这些小公司常年在某个领域耕耘，能提供更专业的组件和技术。被ANSYS以7.5亿美金收购的LSTC（核心产品LSDYNA）最多人数不过百人；而流固耦合做的好的ADINA公司人员在二三十人；被techsoft3d收购的VKI公司人员常年保持在个位数。而大厂一般因为性价比或者壁垒，不太愿意在这些细分领域投入研发，往往选择购买或者成熟后收购。但这并不意味着大厂没有能力做这些事，不必过分拔高这些细分领域的技术难度。

---

针对三维几何内核，在产品开发，技术选型以及公司战略规划上，如果对几何内核技术细节不了解，就很容易陷入诸如：

2.OCC是否能替换一下

3.自己开发是否风险太高

“在选择使用三维几何内核上，国内工业软件公司采取什么样的策略”

如果业务本来不太需要内核，而购买了商业产品，浪费钱；而真正需要商业内核时候，选择了开源或自己开发，产品失败风险高；总的讲，还是要非常了解自己的业务，并对几何内核技术细节有一定的认识，在此基础上才能选择合适的策略。

几何计算 何援军

计算几何算法设计与分析 周培德

之前每次理发进美容店，穿的跟空姐一样的服务员第一句话就是：“请问您有选择好的老师吗？”，听着非常别扭，在我看来，站在讲台上传道受业解惑，教书育人的才是老师！后来理发就选择了一个较远的街边摊，理发的是个老师傅，不仅手艺好还便宜，刮胡子还是一绝。

我们说开发三维几何内核，一定是通用型的工业级的应用。如果开发的功能连ACIS/PS的1/5都达不到，那不叫几何内核，只能叫软件的一个模块。

---

1. 开发自主的三维几何内核需要多少投入？

仍然以目前主流的商业三维几何内核为例，按照60分的标准对标，也就是主要功能性能指标要能达到60%-70%。

研发成本主要是人力成本，为了保证高质量的开发，假设开发全是熟手，有过相关内容的研发经验，省去学习探索开销；按照功能需求，至少需要10人左右的团队，可以部分在国内招募，另一部分在国外：1名架构，2-3名核心开发，5-6名一般开发，1-2名测试。参照美国湾区和国内一线城市的研发待遇，企业一年总共开销至少在八百万(作为在这个行业工作多年，这个计算不会有问题，无需质疑)

其实这一块最难的还是找人，一般的程序员即使有多年工作经验，这块也排不上用场。最好的办法是直接从PSACIS挖核心开发(来源于网络)。

根据以往经验，一年起步，两年原型，三年初步能用的时间节点，最起码的投资两千万往上走，如果少于这个很多，后续要做到及格线就很困难。两千万是根红线，而且前提是已经有一个优秀的研发团队。

笔者一直以来的观点就是：凡事要么不做，做就尽全力做好；明知做不好的情况下还要去碰一碰，不仅砸自己招牌，还影响整个行业的信用，让后来者更加困难。

2. 在选择使用三维几何内核上，国内工业软件公司采取什么样的策略

关于三维几何内核的作用，地位，历史发展等公众号之前讲了很多，现在国内研发设计仿真类工业软件的公司如雨后春笋，很多产品都需要用到几何内核。这里分情况对待：

1. 大的公司，有长远发展计划，不缺资金，可以先使用商业内核，但是在理解，应用，消化商业内核的基础上，一定要同时试用国内的一些内核产品，帮助其迭代产品，或者试着开发跟自己业务相关的几何内核。如果想在技术领域深耕，做这块一定是有价值的，当然也要考虑成本问题。

2. 中小企业尤其是创业公司，根据业务，可以选择商用的，也可以选择开源的。商用的好处是可以快速帮助产品上市，但是贵；开源虽在功能上弱一点，但是如果业务应用场景不是特别复杂，开源产品也完全可以胜任。

3. 科研院所背景的，建议用开源或者自己开发相关底层模块，有一定的技术和业务经验积累，以后商用化更容易。

经常有朋友问，内核这个东西会不会也断供？这个也聊过，参见

其实现在报道的很多断供封锁消息，已经不是单纯的技术问题，而是商业博弈问题，简单讲就是需要考虑投资成本，收益，以及长期影响。

---

A：需要买盾构机，多少钱

A：太贵了，能便宜点么

B：不能，外加人工费一人一天5万美金，刀头一个3千万，机器维护时，你们不能在场...

B：还需要买盾构机吗？打对折

A：需要，我们一台卖6千万

4.判断两线段是否相交

我们分两步确定两条线段是否相交：

(1)． 快速排斥试验
设以线段 P1P2 为对角线的矩形为R， 设以线段 Q1Q2 为对角线的矩形为T，如果R和T不相
交，显然两线段不会相交；

5.判断线段和直线是否相交

6.判断矩形是否包含点

只要判断该点的横坐标和纵坐标是否夹在矩形的左右边和上下边之间。
判断线段、折线、多边形是否在矩形中
因为矩形是个凸集，所以只要判断所有端点是否都在矩形中就可以了。

6.判断矩形是否在矩形中

只要比较左右边界和上下边界就可以了。

7.判断圆是否在矩形中

圆在矩形中的充要条件是：圆心在矩形中且圆的半径小于等于圆心到矩形四边的距离的最

8.判断点是否在多边形中

以点P为端点，向左方作射线L，由于多边形是有界的，所以射线L的左端一定在多边形外，
考虑沿着L从无穷远处开始自左向右移动，遇到和多边形的第一个交点的时候，进入到了多
边形的内部，遇到第二个交点的时候，离开了多边形，……所以很容易看出当L和多边形的
交点数目C是奇数的时候，P在多边形内，是偶数的话P在多边形外。
但是有些特殊情况要加以考虑。如果L和多边形的顶点相交，有些情况下交点只能计算一个
，有些情况下交点不应被计算（你自己画个图就明白了）；如果L和多边形的一条边重合，
这条边应该被忽略不计。为了统一起见，我们在计算射线L和多边形的交点的时候，1。对
于多边形的水平边不作考虑；2。对于多边形的顶点和L相交的情况，如果该顶点是其所属
的边上纵坐标较大的顶点，则计数，否则忽略；3。对于P在多边形边上的情形，直接可判
断P属于多边行。由此得出算法的伪代码如下：

其中做射线L的方法是：设P'的纵坐标和P相同，横坐标为正无穷大（很大的一个正数），
则P和P'就确定了射线L。这个算法的复杂度为O(n)。

9.判断线段是否在多边形内

线段在多边形内的一个必要条件是线段的两个端点都在多边形内；
如果线段和多边形的某条边内交（两线段内交是指两线段相交且交点不在两线段的端点）
，因为多边形的边的左右两侧分属多边形内外不同部分，所以线段一定会有一部分在多边
形外。于是我们得到线段在多边形内的第二个必要条件：线段和多边形的所有边都不内交
线段和多边形交于线段的两端点并不会影响线段是否在多边形内；但是如果多边形的某个
顶点和线段相交，还必须判断两相邻交点之间的线段是否包含与多边形内部。因此我们可
以先求出所有和线段相交的多边形的顶点，然后按照X-Y坐标排序，这样相邻的两个点就是
在线段上相邻的两交点，如果任意相邻两点的中点也在多边形内，则该线段一定在多边形
如果线段和多边形的两相邻交点P1 ，P2的中点P' 也在多边形内，则P1, P2之间的所有点
假设P1,P2之间含有不在多边形内的点，不妨设该点为Q，在P1, P'之间，因为多边形是闭
合曲线，所以其内外部之间有界，而P1属于多边行内部，Q属于多边性外部，P'属于多边性
内部，P1-Q-P'完全连续，所以P1Q和QP'一定跨越多边形的边界，因此在P1,P'之间至少还
有两个该线段和多边形的交点，这和P1P2是相邻两交点矛盾，故命题成立。证毕
由命题1直接可得出推论：
设多边形和线段PQ的交点依次为P1,P2,……Pn，其中Pi和Pi+1是相邻两交点，线段PQ在多
边形内的充要条件是：P，Q在多边形内且对于i =1, 2,……, n-1，Pi ,Pi+1的中点也在多

在实际编程中，没有必要计算所有的交点，首先应判断线段和多边形的边是否内交，倘若
线段和多边形的某条边内交则线段一定在多边形外；如果线段和多边形的每一条边都不内
交，则线段和多边形的交点一定是线段的端点或者多边形的顶点，只要判断点是否在线段
至此我们得出算法如下：

这个算法的复杂度也是O(n)。其中的排序因为交点数目肯定远小于多边形的顶点数目n，所
以最多是常数级的复杂度，几乎可以忽略不计。

10.判断折线在多边形内

只要判断折线的每条线段是否都在多边形内即可。设折线有m条线段，多边形有n个顶点，

11.判断多边形是否在多边形内
只要判断多边形的每条边是否都在多边形内即可。判断一个有m个顶点的多边形是否在一个
有n个顶点的多边形内复杂度为O(m*n)。

12.判断矩形是否在多边形内

将矩形转化为多边形，然后再判断是否在多边形内。

13.判断圆是否在多边形内

只要计算圆心到多边形的每条边的最短距离，如果该距离大于等于圆半径则该圆在多边形
内。计算圆心到多边形每条边最短距离的算法在后文阐述。

14.判断点是否在圆内

计算圆心到该点的距离，如果小于等于半径则该点在圆内。

15.判断线段、折线、矩形、多边形是否在圆内

因为圆是凸集，所以只要判断是否每个顶点都在圆内即可。

16.判断圆是否在圆内

设两圆为O1,O2，半径分别为r1, r2，要判断O2是否在O1内。先比较r1，r2的大小，如果r

17.计算点到线段的最近点

18.计算点到折线、矩形、多边形的最近点

只要分别计算点到每条线段的最近点，记录最近距离，取其中最近距离最小的点即可。

20.计算两条共线的线段的交点

对于两条共线的线段，它们之间的位置关系有图5所示的几种情况。
图5(a)中两条线段没有交点；图5 (b) 和 (d) 中两条线段有无穷交点；图5 (c) 中两条线
段有一个交点。设line1是两条线段中较长的一条，line2是较短的一条，如果line1包含了
line2的两个端点，则是图5(d)的情况，两线段有无穷交点；如果line1只包含line2的一个
端点，那么如果line1的某个端点等于被line1包含的line2的那个端点，则是图5(c)的情况
，这时两线段只有一个交点，否则就是图5(c)的情况，两线段也是有无穷的交点；如果li
ne1不包含line2的任何端点，则是图5(a)的情况，这时两线段没有交点。

21.计算线段或直线与线段的交点
设一条线段为L0 = P1P2，另一条线段或直线为L1 = Q1Q2 ，要计算的就是L0和L1的交点。

1． 首先判断L0和L1是否相交（方法已在前文讨论过），如果不相交则没有交点，否则说
明L0和L1一定有交点，下面就将L0和L1都看作直线来考虑。
2． 如果P1和P2横坐标相同，即L0平行于Y轴
a) 若L1也平行于Y轴，
i. 若P1的纵坐标和Q1的纵坐标相同，说明L0和L1共线，假如L1是直线的话他们有无穷的交
点，假如L1是线段的话可用'计算两条共线线段的交点'的算法求他们的交点（该方法在前
ii. 否则说明L0和L1平行，他们没有交点；
b) 若L1不平行于Y轴，则交点横坐标为P1的横坐标，代入到L1的直线方程中可以计算出交
3． 如果P1和P2横坐标不同，但是Q1和Q2横坐标相同，即L1平行于Y轴，则交点横坐标为Q
1的横坐标，代入到L0的直线方程中可以计算出交点纵坐标；
4． 如果P1和P2纵坐标相同，即L0平行于X轴
a) 若L1也平行于X轴，
i. 若P1的横坐标和Q1的横坐标相同，说明L0和L1共线，假如L1是直线的话他们有无穷的交
点，假如L1是线段的话可用'计算两条共线线段的交点'的算法求他们的交点（该方法在前
ii. 否则说明L0和L1平行，他们没有交点；
b) 若L1不平行于X轴，则交点纵坐标为P1的纵坐标，代入到L1的直线方程中可以计算出交
5． 如果P1和P2纵坐标不同，但是Q1和Q2纵坐标相同，即L1平行于X轴，则交点纵坐标为Q
1的纵坐标，代入到L0的直线方程中可以计算出交点横坐标；
6． 剩下的情况就是L1和L0的斜率均存在且不为0的情况
i. 如果Q1在L0上，则说明L0和L1共线，假如L1是直线的话有无穷交点，假如L1是线段的话
可用'计算两条共线线段的交点'的算法求他们的交点（该方法在前文已讨论过）；
ii. 如果Q1不在L0上，则说明L0和L1平行，他们没有交点。
c) 联立两直线的方程组可以解出交点来

说明：这个算法并不复杂，但是要分情况讨论清楚，尤其是当两条线段共线的情况需要单
独考虑，所以在前文将求两条共线线段的算法单独写出来。另外，一开始就先利用矢量叉
乘判断线段与线段（或直线）是否相交，如果结果是相交，那么在后面就可以将线段全部

22.求线段或直线与折线、矩形、多边形的交点

分别求与每条边的交点即可。

23.求线段或直线与圆的交点

设圆心为O，圆半径为r，直线（或线段）L上的两点为P1,P2。
1. 如果L是线段且P1，P2都包含在圆O内，则没有交点；否则进行下一步
2. 如果L平行于Y轴，
a) 计算圆心到L的距离dis
c) 利用勾股定理，可以求出两交点坐标，如图6(a)所示；但要注意考虑L和圆的相切情况

3. 如果L平行于X轴，做法与L平行于Y轴的情况类似；
4. 如果L既不平行X轴也不平行Y轴，可以求出L的斜率K，然后列出L的点斜式方程，和圆方
程联立即可求解出L和圆的两个交点；
5. 如果L是线段，对于2，3，4中求出的交点还要分别判断是否属于该线段的范围内。

特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。