本赛项提供如下8个赛题，参赛者可任选一个或多个赛题进行参赛（请注意：晋级按赛题计分，参加多个赛题评分不做累积）。

1 赛题一

求解一元多项式方程a_nxⁿ+a_n-1x^n-1+…+a₁x+a₀=0，n=1,2,3,4,5,6

1.1 赛题简介
求解一元多项式方程是求解各类方程的基础，在科学计算与工程计算中有普遍而重要的应用。求解一元多项方程已有多种方法写进了教科书，例如，二分法，切线法。但是在某些情形下，例如重根，求解精度不能得到保证。因此，设计一个在不同情景下应用不同的求解算法，或多种方法组合的算法是非常必要的。

功能要求：求解一元多项式方程，阶n=1,...,6；

测试要求：设计10万例随机测试，要求根据根的单根/重根情况做合理的测试集分类；

性能要求：10万例测试最大误差不超过1e^-10，平均误差不超过1e-12；对时间开销没用确定要求，但时间效率高会有加分。

1.2 赛题评审标准

评分项

子评分项

评分标准

方案设计

（20分）

可行性

（10分）

方案是否具备用代码实现的可行性、是否能够实现要求的功能等

完整性

（5分）

是否完整覆盖赛题目标的功能和非功能性要求，包含算法流程、如何实现、如何测试等

原创性

（5分）

方案具有原创性和创新性

代码实现

（40分）

性能测试

（20分）

是否实现了方程求解功能等、方案性能是否达到求解精度要求。

代码提交量

（10分）

参赛者是否积极提交代码，

提交格式是否符合规范

代码注释质量

（10分）

对项目代码的注释是否详细和有价值

非功能性指标

（20分）

测试案例

（10分）

是否进行了测试、接口是否有对应测试，测试程序是否合理，测例是否完备，测试原始数据是否记录完成

稳定性

（10分）

方案是否会中断、报错等

实验报告

（10分）

完整性

（10分）

是否包含测试的设计,

测试的可行性

误差分析

（10分）

给出该算法的误差分析，提出算法的不足和优化空间

2 赛题二

NURBS曲面求交跟踪初始交点的快速求解

2.1 赛题简介

跟踪求交法是被广泛采用的求交方法，初始点的获取是保证拓扑完整的关键环节。面向B-Rep模型，兼容ACIS数据表示，设计实现高效、鲁棒的初始交点求解算法，要求每一个分支至少求出一个交点，同时保证计算精度的前提下获取尽可能搞的计算效率。

本赛题旨在设计高效、鲁棒的初始交点求解算法。该算法能够兼容ACIS数据表示，并根据给定的容差求解出每个分支上的至少一个交点。主要分成以下四种情况：

(1)孤立交点，有些分支退化为一个交点（下称孤立交点），能给定的容差内求解出相应的孤立交点；

(2)自交点，两条曲线分支相交的点；

(3)切点，两曲面在交点处同时相切（法向一致或平行）；

(4)一般交点，除(1)(2)(3)情形外的其它交点。

本赛项将提供上述四种情况及其符合情况的数据集。除前述(1)(2)(3)的特殊情况外，参赛选手可以提出其它特殊情况并设计测试集。功能要求：

(1)能够正确求解出每个分支上的至少一个交点（满足给定的容差）；

(2)能够识别孤立交点、自交点、切点，并正确求解出来（满足给定的容差）；

(3)所使用的时间消耗在相同容差设置下应当控制在ACIS相应接口所需时间的2倍以内；

(4)结果输出：按照交点在第一个曲面上的参数顺序(ui,vi)，从小到大依次输出相应的交点类型，交点坐标，交点对应在两个曲面上的参数值。

2.2 赛题评审标准

评分项	子评分项	评分标准
方案设计（40分）	可行性（15分）	方案是否具备用代码实现的可行性；是否能用于精确求解每个分支上的至少一个交点
	完整性（15分）	是否完整覆盖孤立交点、自交点、切点及一般交点，包含算法流程、如何实现、如何测试等
	原创性（10分）	方案具有原创性和创新性
代码实现（30分）	可扩展性与稳定性（10分）	算法是否可扩展至其余特殊情况的处理，及对各种特殊情况处理的稳定性
	解释性（5分）	代码是否有详细的注释与文档
	完整性 (5分)	是否包含了完整的算法设计及复杂度的分析等
	支持孤立交点、自交点、切点的检测和计算 (10分)	能够精确求解孤立交点、自交点、切点。
非功能性指标（30分）	测试案例（10分）	单元测试或集成测试用例，根据代码测试覆盖率、主要业务场景覆盖度进行评分；是否增加了更多特殊类型的测试用例

3 赛题三

二次曲线快速鲁棒参数化

3.1 赛题简介

在CAD建模中，二次曲线的曲线评估(curve evaluation)和点反求(point inversion)操作被频繁的使用在建筑设计、车船设计、PCB设计等领域。弧长参数化是最均匀的参数化方法，在理论上可精确实现弧长参数化的二次曲线只能是圆弧，而实现多项式或有理多项式弧长参数化的只能是直线。圆弧虽然可以被表示为弧长参数化的形式，但是在实际操作中效率较低，不满足实时性。一般的方法是用近似弧长的参数化方法去代替弧长参数化，但是近似弧长参数方法（例如弦长参数化）的均匀性较差。

为了解决上述实际问题，我们希望寻求一种新的参数化方法与常见的几何引擎（例如OCC、ACIS）相比具有以下优势包括但不限于：

(1)参数至少保证二次曲线C1连续；

(2)切向和曲率的计算效率有显著提高（一个数量级左右）；

(3)曲线评估的效率有显著提高（一个数量级左右）；

(4)点反求操作的效率有显著提高（一个数量级左右）；

(5)棒性较好，点与参数间相互转换的累加误差较小（一个数量级左右）；

(6)更接近弧长参数化；

(7)至少在应用方面验证参数化方法的有效性（模型离散化、实体布尔等）。

3.2 赛题评审标准

评分项

子评分项

评分标准

方案设计

（30分）

可行性

（5分）

方案充分考虑CAD几何引擎项目背景、特点，具备在VS中用代码实现的可行性；方案能够用于解决实际应用的问题，能够用于解决模型的离散化及布尔等

完整性

（5分）

方案完整的覆盖赛题目标的功能和性能需求，包含架构、工作流程、如何编码、测试验收等内容

原创性

（10分）

方案具有创新性，为业界当前所未公开发表过的方案，也可结合特有场景提出具有原创性的方案

先进性

（10分）

对比业界已有的方案，当前方案在连续性、鲁棒性、计算效率上有明显优势的，或者其他具备先进性的内容

代码实现

（60）

功能完整性

（15分）

（1）支持STEP、IGES等格式几何模型文件导入功能；

（2）支持模型离散化；

（3）支持简单实体的布尔运算（交、并、差）；

（4）在其他领域的应用（电路板等）；

（5）支持几何模型与参数之间映射信息输出；

性能效率

（25分）

（1）参数至少保证二次曲线C1连续；

（2）切向和曲率的计算效率有显著提高（一个数量级左右）；

（3）曲线评估的效率有显著提高（一个数量级左右）；

（4）点反求操作的效率有显著提高（一个数量级左右）；

（5）鲁棒性较好，点与参数间相互转换的累加误差较小；

（6）更接近弧长参数化

应用

（15分）

在应用方面验证参数化方法的有效性（模型离散化、实体布尔等）

代码注释质量

（5分）

对项目核心代码的注释详细、规范

实验报告

（10分）

作品文档质量

（10分）

参赛队提交的作品申报书等材料将由专家评委进行评审，并根据材料质量进行评分

4 赛题四

高效鲁棒的B-Rep模型布尔运算

4.1 赛题简介

在CAD软件中，布尔运算是最常用和最基础的建模功能之一，用于将简单的基本实体通过布尔交（相交）、布尔并（相加）和布尔差（相减）组合成新的复杂的模型。同时，布尔运算作为基础造型功能，同时也是支撑复杂造型功能的关键。布尔运算的性能和稳定性直接反映了CAD内核的性能、稳定性和准确性，该赛题我们期望参赛者能够实现面向B-Rep模型，兼容ACIS接口的高效、鲁棒的布尔运算算法，要求开发语言采用C++语言。

4.2 赛题评审标准

评分项	子评分项	评分标准
方案设计（30分）	可行性（10分）	方案是否具备用代码实现的可行性、是否能够实现要求的功能等
	完整性（15分）	是否完整覆盖赛题目标的功能和非功能性要求，包含算法流程、如何实现、如何测试等
	原创性（5分）	方案具有原创性和创新性
代码实现（50分）	性能测试（25分）	是否实现了布尔并、布尔交和布尔差功能、方案性能是否达到要求
	代码提交量（15分）	参赛者是否积极提交代码
	代码注释质量（10分）	对项目代码的注释是否详细和有价值
非功能性指标（10分）	测试（5分）	是否进行了测试、接口是否有对应测试
非功能性指标（10分）	稳定性（5分）	方案是否会中断、报错等
实验报告（10分）	完整性（5分）	是否包含测试的设计
实验报告（10分）	可行性（5分）	测试的可行性

5 赛题五

特殊情况下的高效曲面离散化算法设计

5.1 赛题简介

随着现代制造业和工程设计的不断发展，对复杂曲面的精确表示和处理需求日益增加。边界表示（Boundary Representation，BRep）是几何建模中的一种重要表示方法，它能够准确地描述复杂的实体模型。ACIS作为一种广泛使用的几何建模内核，支持BRep模型的表示和处理。在实际应用中，曲面和实体表面的离散化是计算机辅助设计（CAD）和计算机辅助制造（CAM）过程中必不可少的一步。为了保证计算效率和精度，离散化过程需要根据预设的容差进行。

本赛题旨在设计一套能处理特殊情况的高效曲面离散化算法，该算法能够兼容ACIS数据表示，并根据容差对不同含有特殊情况的曲面及含有这些曲面的实体表面进行高速离散，生成对应的mesh（mesh在本赛题意境下仅表意表面网格）。特殊情况主要分成以下三种：

（1）周期曲面，诸如柱面、球面、环面、具备周期性的样条面等；表征此类曲面边界信息的Loop在三维空间中是连续的，但映射至二维空间即曲面的参数域时，由于周期性的原因，会被截断，导致不连续性的产生；由此，基于参数域的离散化方法需要处理周期性；而直接利用空间信息进行离散的方法则不需要处理此种不连续性。请设计算法离散周期曲面。

（2）奇点，诸如锥面、退化环面、退化样条面等；奇点的产生源自于边的退化，即此处表征边界信息的本应当是一条边，而此处边上所有的点位置均相同；奇点映射至二维空间中参数域时仅仅由一个点表示，但其实则表征了二维空间中一条边的信息；此类信息的缺失也会提高离散化的难度。请设计算法离散含有奇点的曲面。

（3）非流形，流形是一个数学术语，表示局部类似于直线、平面或空间的对象。 n 流形一词是指局部类似于 n 维空间的流形，而不是位于 n 维空间中的流形。在几何建模上下文中，通常指固体对象的2流形边界。具有2流形边界意味着边界上的每个点都类似于平面内部的点。二维边界上的每个点都完全被二维边界上的其他点包围。球体、环面或块的表面都是二维流形的示例。（在此上下文中，对象的“表面”是指其外部边界，而不是特定的几何元素。）流形实体边界上的每个点将建模空间分为两个区域：实体内部区域和实体内部区域。如果在边界上的任何点建模空间没有分为两个区域，则该对象在该点是非流形的，例如两个高度不一的圆柱相切时，其切线在任一柱面看来均是非流形的，在切线上任意点均没有明确的将建模空间分成内外两个区域，而是有两个方向进入内部空间。非流形会给曲面离散带来额外的限制，即采样过后的点在连接时必须连接非流形上的点以保证模型的水密性。请设计算法离散含有非流形信息的曲面。

本赛项将提供上述三种特殊情况的数据集。另外提供一个复合情况的数据集，即同时包含多种特殊情况的曲面的测试集。除前述三种特殊情况外，参赛选手可以提出其它特殊情况并设计测试集。

功能要求：

（1）算法能离散上述含有特殊情况的曲面，生成对应的水密的mesh；

（2）离散化算法所使用的时间消耗在相同容差设置下应当控制在ACIS离散化模块时间的2倍以内；

（3）离散化后的网格质量应满足用户设定的容差要求，如设置为0.1，则生成的mesh与原B-Rep表示的模型误差不超过0.1，绝对误差支持精度至少在1e-2之上；

（4）结果输出：支持常见文件格式（如STL、OBJ等）的导出，提供离散化结果的可视化展示功能。

5.2 赛题评审标准

评分项

子评分项

评分标准

功能实现（基于通过测试集的数量）

（55分）

周期曲面

（15分）

算法是否能处理周期曲面的特殊情况

奇点

（10分）

算法是否能处理奇点的特殊情况

非流形

（15分）

算法是否能处理非流形的情况

复合情况

（10分）

算法是否能处理复合的特殊情况

结果输出

（5分）

是否支持常见文件格式的输出

性能表现

（15分）

时间消耗

（10分）

算法时间消耗情况，基于测试集平均时间消耗表现

空间消耗

（5分）

算法内存占用情况，基于测试集平均空间消耗表现

设计报告

（30分）

创新性

（5分）

算法是否具备一定的理论基础与创新点

可扩展性与稳定性

（10分）

算法是否可扩展至其余特殊情况的处理，及对各种特殊情况处理的稳定性

解释性

（10分）

代码是否有详细的注释与文档

完整性

（5分）

是否包含了完整的算法设计及复杂度的分析等

额外加分

（10分）

测试集

（5分）

添加所给测试集中所不包含的情况的测例

特殊情况曲面

（5分）

提出新的特殊情况的曲面，并设计算法解决

6 赛题六

四边线框的曲面覆盖

6.1 赛题简介

覆盖（covering）是ACIS中三种高级建模技术之一，不但直接服务于终端用户，还为其他建模方法提供接口。覆盖功能通过拟合一个或多个边回路（一组首尾相连并形成封闭“环”的边构成的几何）来生成覆盖曲面，并满足用户在拓扑上的要求。覆盖功能可用于从线框创建片状实体（称为片体），或开发实体，以及为现有片体或开放实体添加面。覆盖功能主要分为七个子功能，包括线框的基本平面覆盖、线框的增强平面覆盖、边的增强平面覆盖、单个线框的非平面覆盖、多个线框的非平面覆盖、自由边的非平面覆盖、边回路的非平面。这些子功能可以分为两类，平面覆盖和非平面覆盖。其中，非平面覆盖对于边界曲线的插值性、覆盖曲面的品质有较高的要求，是一个较难实现的功能。

本赛题旨在设计高效、高质量的四边线框覆盖曲面生成算法。给定四条首尾相连，无自相交的曲线作为边界线框，要求生成一张高品质覆盖曲面，覆盖曲面兼容ACIS数据表示，插值于线框四条边界曲线，保证曲面光顺性，通过考虑覆盖曲面光顺能量，并比较覆盖曲面和ACIS覆盖曲面差异性，评估生成结果。

本赛项将提供若干四边线框数据集，参赛选手也可以根据功能要求自行设计测试集。

功能要求：

（1）兼容ACIS数据表示；

（2）插值给定的四条线框曲线；

（3）评估生成的覆盖曲面与ACIS覆盖功能生成曲面的差异性；

（4）本功能生成的覆盖曲面光顺性与ACIS生成的覆盖曲面的光顺品质相当；

（5）本功能时间消耗与ACIS覆盖功能所需时间相当；

（6）结果输出：输出覆盖曲面的控制顶点、阶数、节点向量。

6.2 赛题评审标准

评分项	子评分项	评分标准
方案设计（15分）	设计说明（10分）	算法设计说明是否清晰、详细，内容是否完整，包括算法设计思路、算法流程、如何实现等
方案设计（15分）	原创性（5分）	方案具有原创性和创新性
代码实现（15分）	代码规范（5分）	是否有统一的代码风格规范
代码实现（15分）	代码注释质量（10分）	对项目代码的注释是否详细、逻辑清晰
测试表现（70分）	测例通过率（30分）	在容差范围内通过的测例数目占比
测试表现（70分）	性能表现（40分）	计算时间和内存消耗的优化情况

7 赛题七

沿路径扫掠曲面生成

7.1 赛题简介

在CAD（计算机辅助设计）软件中，扫掠（Sweeping）是一种常见的建模技术，用于创建复杂的三维形状。扫掠是一个强大且灵活的建模工具，可以帮助设计师和工程师高效地创建复杂的三维几何形状。通过合理使用扫掠，可以大大提高CAD设计的效率和质量。

扫掠操作方式其一即通过沿着一条路径（开放边，闭合边，多段开放/闭合线框）移动一个二维轮廓（开放边，闭合边，多段开放/闭合线框，平面等）来生成三维对象。

要求：兼容ACIS数据表示，实现单段/多段曲线沿单段/多段曲线在ACIS默认参数下的扫掠(轮廓与路径共起点)，当扫掠生成的不止一个面时，参赛者需要采用合理的方法组织这些曲面，以完成多段曲线沿多段曲线扫掠算法，最终算法应支持三种合并可选项（new miter, crimp miter, bend miter）。

7.2 赛题评审标准

评分项	子评分项	评分标准
方案设计（20分）	可行性（5分）	充分考虑扫掠功能的工作场景、操作特点，具备能在CAD软件中用代码实现的可能性；方案能够用于解决实际场景的问题，能够通过扫掠构造三维实体
	完整性（5分）	是否完整覆盖赛题目标的功能和非功能性要求，包含算法流程、如何实现、如何测试等
	原创性（5分）	方案具有原创性，所实现代码为自创或在已发表论文的基础上改进
	先进性（5分）	对比业界已有的方案，当前方案在内存消耗、时间消耗等方面有着明显优势，或者其他具备先进性的内容
代码实现（50分）	正确生成扫掠面（25分）	沿路径扫掠可以正确地生成扫掠面，要求与ACIS所生成的扫掠面外观相似，甚至可以通过布尔减测试
	不同实体与路径的支持情况（10分）	路径应支持开放边，闭合边，多段开放/闭合线框等；二维轮廓应支持开放边，闭合边，多段开放/闭合线框，平面等。二者的不同组合也应有良好的支持性
	多个扫掠面的合并（10分）	在沿多段路径的折角处，应设计不同的倒角方式，最终算法应支持三种合并可选项(new miter, crimp miter, bend miter)
	代码注释质量（5分）	对项目代码的注释是否详细和有价值
非功能性指标（20分）	测试案例（10分）	是否进行了测试、接口是否有对应测试
非功能性指标（20分）	稳定性（10分）	方案是否会中断、报错，在边际条件下是否能正常使用等
实验报告（10分）	完整性（5分）	是否包含测试的设计
实验报告（10分）	可行性（5分）	测试的可行性

8 赛题八

三维CAD模型干涉检查算法

8.1 赛题简介

干涉检查用于在三维CAD模型设计阶段检查模型之间是否存在碰撞或穿透的问题。如在船舶设计中，通过船舶CAD模型的干涉检查可以排查管路模型之间，以及船体结构板材、型材等模型之间的位置、尺寸冲突，以确保建立的模型能符合设计要求。目前干涉检查功能除了通过包围盒和求交等算法来判断实体之间是否有干涉情况，还支持用户通过输入实体之间的距离来控制干涉检查的容差，但是要求容差值不可小于0，即不可以用来判断两个实体互相嵌入的深度，但是实际业务中两个零件是有容许部分相互嵌入场景的。

因此，本赛题要求开发一种三维CAD模型干涉检查算法，不仅要能实现对大部分模型干涉情况的判断，还要能支持用户输入正负距离容差来控制干涉检查的条件。要求开发语言采用C++，项目开源许可协议应采用BSD、MIT、Apache 2.0协议之一。

8.2 赛题评审标准

评分项	子评分项	评分标准
方案设计（30分）	可行性（10分）	方案是否具备用代码实现的可行性；是否能用于解决目前CAD软件干涉检查功能的瓶颈
	完整性（10分）	是否完整覆盖赛题目标的功能和非功能性要求，包含算法流程、如何实现、如何测试等
	原创性（10分）	方案具有原创性和创新性
代码实现（40分）	实现对实体模型之间的干涉检查算法（5分）	算法实现对实体模型之间的干涉检查判断。
	支持用户输入正负距离容差值（20分）	支持用户数据正负距离容差来控制干涉检查的判断条件
	支持对模型碰撞、穿透等大部分干涉场景的检查（5分）	算法支持对模型碰撞、穿透等大部分干涉场景的检查，并通过测试
	干涉检查成功率90%以上（10分）	基于给定测试案例集，干涉检查成功率在90%以上
非功能性指标（30分）	测试案例（10分）	单元测试或集成测试用例，根据代码测试覆盖率、主要业务场景覆盖度进行评分
	性能（15分）	算法内存开销；计算耗时
	稳定性（5分）	方案是否会中断、报错等

9 参赛作品

9.1 初赛作品

（1）初赛作品须针对赛题给出完整的解决方案设计报告，需要包含接口说明等。

（2）初赛作品须给出满足赛题要求的完整代码程序，以PR方式提交至仓库。

（3）部分赛题在初赛时要求提交实验报告，具体要求参见各赛题要求。

9.2 决赛作品

在初赛作品的基础上新增：

（1）结赛PPT，采用线下的方式，参赛团队通过PPT简述参赛作品的方案设计、优势以及相较初赛时的优化。

（2）实验报告，包括方案测试流程与测试结果。

最终，需要将相关文件（包括方案设计报告、源代码、结赛PPT与实验报告）提交在AtomGit上对应队伍仓库，同时以邮件的方式发送给导师邮箱yiransong@mail.tsinghua.edu.cn。