一种实用的曲面求交算法

一、前言随着自由曲面在几何造型、CAD/CAM、RP（反向工程）等领域中的广泛应用,针对自由曲面的几何处理,如曲面求交、曲面裁剪等成为计算几何中的热门研究课题,并作为完成复杂产品造型及产生数控或RP加工数据的基本手段和衡量曲面造型系统设计能力的主要指标而倍受重视。其中,作为曲面裁剪、曲面过渡等基础的曲面求交是最基本和最重要的问题之一。曲面求交算法是曲面编辑操作中最基本的一种算法,是曲面造型、曲面加工的基础。通常要求算法效率高,计算稳定,且精度易于控制。由于曲面与曲面求交问题的非常复杂,至今还未得到圆满…     

参数曲面求交算法

参数曲面求交算法华中理工大学ＣＡＤ中心曾祥林，王启付，周济，余俊一、引言参数曲面／曲面求交问题在雕塑实体造型系统中经常出现，为了改进系统的稳定性和准确性，一个可靠的、准确的和拓扑一致的曲面／曲面求交方法是必要的。至今已有许多解决曲面／曲面交问题的方法...     

基于"结式法"的二次曲面求交算法

提出了一种新的基于“结式法”的二次曲面求交算法，该算法首先利用结式法计算出两二次曲面相交时交线的投影方程,再对投影方程进行分解等处理，通过循环计算从而得到投影交线的分支数及其上的一系列的点,然后回代入两二次曲面中的一个即可得到二次曲面的交线，该算法实现简单且符合求交算法的稳定、准确和快速等要求。     

曲面交线的B样条优化逼近

目前，在比较成熟的商业几何核心系统中，曲面的交线是一种基于位置算子的“精确”表示或称为“过程”表示．这样的交线如果用在几何建模操作中，必须输出为系统支持的曲线表示(如B样条表示)．现有的几何核心系统中曲面交线的B样条逼近算法存在控制点数目过多和连续性偏低(C^1)的缺点，导致下游操作结果太复杂且连续性低．基于此，提出了一种曲面交线的B样条逼近算法，使控制点数目减少为原来的三分之一，而连续阶上升为C^2．该算法已经在SolidWorks系统中得到应用，效果良好．     

任意曲面间跟踪求交的有效算法

提出了一种基于微分方程的跟踪算法，该算法采用基于交线微分形式的跟踪公式，解决了求交中难于处理的分支问题，和已有跟踪法相比，该算法稳定性更强，效率更高，而且适用于任意参数曲面及解析曲面。     

基于几何法表示的曲面实体的分割算法

分割是实体造型的重要步骤,而边界问题是影响分割算法效率和稳定性的主要因素。工程中常用的二次曲面有自封闭的特性,在相交时交线会出现退化和自交等情况,给拓扑表示和帝体重建带来困难,另外,边界重合也是实体分割时经常要遇到的问题,该文在二次曲面几何法表示的基础上,针对二次曲面相交时交线的特性,设计了合理的分割策略,提出了有效的分割算法,并对边界重合等问题做了很好的处理,同时用实例验证了本文算法的有效性。     

奇异情况下两个二次曲面间的求交

曲面求交是几何造型系统的核心之一,奇异情况下求交算法的稳定性直接关系到后续的布尔运算乃至整个系统的稳定性.提出2种二次曲面间对应特征多项式有重根情形下鲁棒的求交算法.首先给出精确求解特征多项式重根的方法,若交线中存在奇异交点,则给出奇异交点关于特征多项式重根的显式表达式,从而稳定地求解出对应的奇异交点;同时给出一种交曲线有理参数化的构造性方法,可以弥补Farouki相应有理参数化方法中的缺陷.最后通过实例进一步说明了文中算法的求解稳定性及有理参数化的构造性方法的实用性.     

一种基于矩形网格加速的曲面裁剪算法

在地质模型中.曲面一般用三角网格来表示.在三维地质建模过程中经常需要对曲面进行裁剪操作,本文描述了一种网格曲面裁剪算法.它是将传统裁剪算法中的曲面三角网格和三角网格求交简化为曲面三角网格和矩形网格求交,由于矩形网格的数据结构简单.查找和定位方便(可以直接根据坐标值定位到所位于的矩形网格单元),算法简练,较大的提高了计算速度.     

基于CAD几何模型的曲面流线可视分析方法

针对在大规模矢量场中复杂几何曲面流线生成难的问题，设计实现了一种高精度的复杂曲面流线可视分析方法。首先，基于拓扑二维曲面结构进行求交计算，并引入高精度插值算法实现几何曲面矢量场并行抽取操作；然后，采用改进型龙格-库塔矢量场流线积分扩展技术进行积分计算，并引入自适应积分步长策略和流线-曲面求交加速结构，生成连续一致的曲面流线；最后，引入小球特征到可视化管线流程中，并集成于通用可视分析平台。实验结果表明，该方法能够高精度地生成连续一致的几何曲面流线，有效刻画复杂装置表面流场物理特性。     

参数曲面求交算法

参数曲面求交是雕塑产体造型中的关键问题，为了提高曲面／曲面求交方法的稳定性，准确性以及拓扑一致性，本文提出了一种改进方法，它是［Ｈｏｕｇｈｔｏｎ ａｔ ａｌ．＇８５］和［Ｂａｒｎｈｉｌｌ ａｔ ａｌ．＇９０］的思想的延伸，在本算法中，提出了获取曲面临近点的新方法和确定分析支点的可靠方法，改进确定追踪步长的方法。此外，它可以方例地计算出等距曲顶交线而无需等距逼近，通过上述改进本算法可处理分支点，切环     

线框模型中二次曲面的识别

定义关联两曲线间的夹角和由3条关联曲线确定二次曲面,提出适用于曲面的回路搜索最小转角法,且利用它并辅以矢量混合积验证搜索曲面上最小回路的方法．实现从线框模型中选择任意一条曲线就能够搜索到包含它的所有潜在表面回路,突破以往回路搜索方法中只能从某方向极值点开始的束缚,为线框模型表面识别中将含曲线表面与不含曲线表面分治识别奠定基础．算法可处理含有任意位置的二次曲表面的线框模型,并能较准确地判别二次曲面的类型．     

Solid reconstruction using recognition of quadric surfaces from orthographic views

The reconstruction of 3D objects from 2D orthographic views is crucial for maintaining and further developing existing product designs. A B-rep oriented method for reconstructing curved objects from three orthographic views is presented by employing a hybrid wire-frame in place of an intermediate wire-frame. The Link-Relation Graph (LRG) is introduced as a multi-graph representation of orthographic views, and quadric surface features (QSFs) are defined by special basic patterns of LRG as well as aggregation rules. By hint-based pattern matching in the LRGs of three orthographic views in an order of priority, the corresponding QSFs are recognized, and the geometry and topology of quadric surfaces are recovered simultaneously. This method can handle objects with interacting quadric surfaces and avoids the combinatorial search for tracing all the quadric surfaces in an intermediate wire-frame by the existing methods. Several examples are provided.     

虚拟维修中表面间碰撞检测问题研究

基于几何约束的虚拟样机中,表面间的碰撞检测是实现维修操作的必要条件.目前有一些公用的碰撞检测工具包,但这些碰撞检测工具包一般支持多面片模型,并没有利用CAD模型中的表面信息,无法确定发生碰撞的表面.该文针对虚拟维修操作的特点,提出了一种新的场景图数据结构.在该场景图下采用表面-三角面片映射和表面-对象映射,在通用的碰撞检测工具包的基础上实现表面间的碰撞检测.最后,描述了约束管理系统的结构,利用该系统可对碰撞检测系统中发生碰撞的表面进行约束识别和求解,从而有效地支持虚拟维修中的装配和拆卸操作.     

Fast interference detection between geometric models

We present efficient algorithms for interference detection between geometric models described by linear or curved boundaries and undergoing rigid motion. The set of models include surfaces described by rational spline patches or piecewise algebraic functions. In contrast to previous approaches, we first describe an efficient algorithm for interference detection between convex polytopes using coherence and local features. Then an extension using hierarchical representation to concave polytopes is presented. We apply these algorithms along with properties of input models, local and global algebraic methods for solving polynomial equations, and the geometric formulation of the problem to devise efficient algorithms for convex and nonconvex curved objects. Finally, a scheduling scheme to reduce the frequency of interference detection in large environments is described. These algorithms have been successfully implemented and we discuss their performance in various environments.     

Exact and approximate computation of B-spline curves on surfaces

Curves on surfaces are important elements in computer aided geometric design. After presenting a method to explicitly compute these curves in three-dimensions, practical algorithmic issues are discussed concerning the efficiency of the implementation. Good approximations are important because of the quite high degree of exact curves on surfaces. We present two approximate solutions to the problem. The first is derived from the exact representation, while the second extends conventional least-squares approximation by incorporating the geometry of the surface as well. The efficiency and behaviour of the algorithms are evaluated by means of examples.     

Advanced Geometric Modeler with Hybrid Representation

An advanced geometric modeler GEMS4.0 has been developed,in which feature representation is used at the highest level abstraction of a product model.Boundary representation is used at the bottom level,while CSG model is adopted at the median level.A BRep data structure capable of modeling non-manifold is adopted.UNRBS representation is used for all curved surfaces,Quadric surfaces have dual representations consisting of their geometric data such as radius,center point,and center axis.Boundary representation of free form surfaces is easily built by sweeping and skinning method with NURBS geometry.Set operations on curved solids with boundary representation are performed by an evaluation process consisting of four steps.A file exchange facility is provided for the conversion between product data described by STEP and product information generated by GEMS4.0.     

Reconstruction of curved solids from engineering drawings

This paper presents a new approach for reconstructing solids with planar, quadric and toroidal surfaces from three-view engineering drawings. By applying geometric theory to 3-D reconstruction, our method is able to remove restrictions placed on the axes of curved surfaces by existing methods. The main feature of our algorithm is that it combines the geometric properties of conics with affine properties to recover a wider range of 3-D edges. First, the algorithm determines the type of each 3-D candidate conic edge based on its projections in three orthographic views, and then generates that candidate edge using the conjugate diameter method. This step produces a wire-frame model that contains all candidate vertices and candidate edges. Next, a maximum turning angle method is developed to find all the candidate faces in the wire-frame model. Finally, a general and efficient searching technique is proposed for finding valid solids from the candidate faces; the technique greatly reduces the searching space and the backtracking incidents. Several examples are given to demonstrate the efficiency and capability of the proposed algorithm.     

Reconstruction of intersecting curved solids from 2D orthographic views

This paper presents a new approach to reconstruct curved solids composed of elementary volumes intersecting with one another from three-view engineering drawings. Intersection curves arising from two intersecting curved surfaces are mostly higher order spatial curves, which cannot be described exactly by 2D orthographic projections and normally represented as smooth curves passing through several key points or even simplified as arcs or lines. Approximated sketches of higher order intersection curves in 2D views result in the invalidation of existing methods that need the exact projection information as input. Based on some heuristic hints, our method is able to recover the complete and correct half-profiles of the intersecting elementary volumes using the least traces left by them, which ensure the correctness of solution solids constructed finally. Several examples are provided to show the validation of the described method.