一个雕塑实体的布尔操作算法

给出了一个雕塑实体布尔操作的现实算法,在保证效率和精确性的同时确保鲁棒性是算法的目标,实体模型通过裁剪曲面片和半边数据结构来表达几何和拓扑信息。采用了层次求交和交线跟踪的方法来保证曲面片分割和区域分类的一致性,从而克服实践中常见的退化情况。该算法也可以方便地扩展到非流形模型的布尔操作。作为一个实体造型系统的一部分,该算法已经在ＳＧＩ工作站上实现。     

支持异种材料体造型的特征布尔运算

针对传统CAD不能提供材料等非几何信息,且无法实现异种材料物体间的布尔运算,提出了一种可应用于构造异种材料物体的特征布尔运算,包含了由材料决定的布尔差和交运算及新的布尔复形并运算,由特征合并和特征抽取两步完成;并给出了该运算的几何实现、实现算法及实例．     

采用推理方法提高多面体Boolean运算的可靠性

提高实体Boolean运算的可靠性是几何造型中最基本也是最迫切的工作。通过对国内外几何造型系统在实体Boolean运算可靠性方面的测试,我们发现,实体Boolean运算不可靠是一个普遍现象,运算失败的根本原因在于数值计算存在误差。数值计算误差决定了我们不能精确地确定集合成员分类。集合成员分类的结果与选定的计算容差有关,具 有相对性。从而相关分类之间会发生冲突。一旦分类之间发生冲突,Boolean运算就不能得到正确的结果。我们提出了一个相当可靠的Boolean运算算法。该算法采用推理的方法在进行Boolean运算之前解决由数值计算误差所引起的相关分类之间冲突。这些算法已在Apollo和SUN工作站上实现,并取代了GEMS 2.0造型系统,构成了一个新的造型系统GEMS 2.1。经测试和比较,这个系统的可靠性比SDRC公司的Geomod 3.9和Intergraph公司的I/EMS高得多。     

基于压缩Voxel模型的五坐标数控加工仿真新方法

文章介绍了一种基于压缩Voxel模型的五坐标数控加工仿真新方法。该方法采用压缩Voxel模型表示数控加工工件模型和刀具空间扫描体模型,计算机内部存贮空间小,布尔操作简单、速度快。通过MarchingCubes方法提取数控加工仿真工件表面三角网格模型并进行图形显,提高了仿真工件显示质量。文章同时提出了一种基于压缩Voxel模型的刀具空间扫描体构造新方法,通过构造基本几何体球体、圆柱体、圆环体、锥形体和鼓形体的空间扫描体,完成各种加工刀具棒刀、球头刀、环形刀、锥形刀和鼓形刀空间扫描体压缩Voxel模型。该方法在《基于压缩Voxel模型的五坐标数控加工仿真系统》中得到了应用,仿真结果三维信息完备,操作人员可从任意方向观察、验证仿真结果,克服了现有五坐标数控加工仿真方法和商品化软件系统的不足,该方法是虚拟数控加工的关键技术。     

The Boolean closure of linear context-free languages

Closures of linear context-free languages under Boolean operations are investigated. The intersection closure and the complementation closure are incomparable. By closing these closures under further Boolean operations we obtain several new language families. The hierarchy obtained by such closures of closures is proper up to a certain level, where it collapses to the Boolean closure which, in turn, is incomparable with several closures of the family of context-free languages. The Boolean closure of the linear context-free languages is properly contained in the Boolean closure of the context-free languages. A characterization of a class of non-unary languages that cannot be expressed as a Boolean formula over the linear context-free languages is presented.     

基于“内点”识别的多边形布尔运算

在多边形内、外侧边界识别的基础上，充分利用多边形本身是一个整体的事实，我们提出了一种基于“内点”(多边形内的点)识别的布尔运算算法，简化了布尔运算的复杂性，从根本上解决了由于多边形问可能存在重合点、重合线而造成的布尔运算不稳定问题。     

一个基于异构型局域网的雕塑实体布尔操作并行算法

为了在某些限时操作下得到实时交互的速度 ,提出了一个分布式的雕塑实体模型布尔操作并行算法 .该算法在各个阶段抽取的并行性和原串行算法的拓扑相关性之间采取了折中的策略 ,并对于不同的并行任务 ,采用了不同的任务均衡手段 .该算法已经在一个由 10台 P /35 0微机和由 5台 SGI O2工作站组成的异构型局域网上得到实现 .实验结果显示 ,该算法获得了理想的加速比 ,对于复杂雕塑实体的造型 ,操作平均可在 3s～ 4 s完成 ,因此能满足实时交互的需要 .     

二维布尔运算中的奇异问题

图形布尔运算的关键是如何处理点、线重合等的奇异情况,详尽列举了布尔运算过程中的各种奇异情况,用一种重叠的思想来描述奇异状态的来源,分析了在各种情况下的交点取舍方法和特征值计算方法,同时提出一种奇异处理算法,使其能够对各种奇异情况进行正确处理,从而提高了二维布尔运算算法的鲁棒性.算法在实验室的自主CAD软件上进行了实现,并进行了大量实验,在重边、重点等多种复杂的情况下均能产生正确结果.     

一般点模型的交互式布尔运算

提出了一个适用于一般点模型的交互式布尔运算算法,此算法由4个步骤组成．首先将点模型表示为自适应的三色八叉树,然后利用自适应八叉树结构加速内外测试．对于局部采样密度不一致的相交区域或曲率太大容易导致较大求交误差的地方,实行了自适应细分加密采样;重采样相交的部分以获得更精确的求交结果．与已有的点模型布尔运算方法相比,该算法适用于一般的实测点云数据,包括少量噪声的点模型、非均匀采样以及不同分辨率点模型之间的交互式布尔运算。     

一种基于特征几何元素永久命名的快速相交特征检查与判别方法及其应用

相交特征的检查与判别是特征造型领域的一个重要问题,通常的方法是通过在特征体间作布尔运算进行相交特征的检查与判别,但这种方法存在复杂、耗时的缺点,为避免大量的求交运算,提高相交特征检查与判别的效率,文中提出了一种新的相交特征的检查与判别方法,该方法以一系列的面标号查找代替了特征之间的求交运算,从而有效地提高了相交特征的检查速度。     

基于二分图完善匹配的布尔匹配算法

提出了一种改进的基于二分图完善匹配的布尔匹配算法。该算法通过把布尔变量之间的匹配问题转换为二分图的完善匹配问题,避免了原算法中因乘积项过多而导致计算时间过长的缺点。对MCNC标准测试电路的实验结果表明;与原算法相比,改进后的算法可以减少21％左右的计算时间。同时,文中提出了布尔变量强匹配的概念,它是对传统布尔匹配概念的引申。     

Solid Modeling Based on a New Paradigm

The technique of solid modeling is essential in CAD/CAM applications, and is currently well established. However, problems remain, such as the lack of uniformity in geometric computations and the lack of stability of Boolean operations of two solids. In this paper, we introduce a theoretical solid modeling system that operates on boundary representations of polyhedral objects and is based on a new paradigm. The characteristics of the system are the following: (I) in Boolean Operations and modeling transformations, all geometric computations are performed by the 4 × 4 determinant method or the 4 × 4 matrix method in homogeneous space, which allows the system to avoid division operations, (2) all geometric computations are performed by the exact integer arithmetic, which makes the geometric algorithms stable and simple, and (3) primitive solids are constructed consistently in the integer domain, and the consistency is assured throughout Boolean operations and transformations.     

Boolean operations for solids with free-form surfaces through polyhedral approximation

This paper describes a new implementation method for Boolean operations between solids with free-form surfaces. Boolean operations consist of two processes-topological modification and geometric modification-which are performed separately in our method. This separation makes the Boolean operation process simple and robust. Surfaces contained in the final solid are interpolated by the repatching facility using Gregory patches.     

Robustness design of fuzzy control for nonlinear multiple time-delay large-scale systems via neural-network-based approach

The stabilization problem is considered in this correspondence for a nonlinear multiple time-delay large-scale system. First, the neural-network (NN) model is employed to approximate each subsystem. Then, a linear differential inclusion (LDI) state-space representation is established for the dynamics of each NN model. According to the LDI state-space representation, a robustness design of fuzzy control is proposed to overcome the effect of modeling errors between subsystems and NN models. Next, in terms of Lyapunov's direct method, a delay-dependent stability criterion is derived to guarantee the asymptotic stability of nonlinear multiple time-delay large-scale systems. Finally, based on this criterion and the decentralized control scheme, a set of fuzzy controllers is synthesized to stabilize the nonlinear multiple time-delay large-scale system.     

Simultaneous and incremental feature-based multiresolution modeling with feature operations in part design

This paper proposes a new feature-based multiresolution modeling approach that can provide multiresolution representation of dynamically changing CAD models of intermediate design stage. Feature-based multiresolution modeling provides simplified shapes of parts of various levels of detail (LOD) by suppressing the detailed features according to a certain LOD criterion. Unlike previous research having mainly focused on the multiresolution representation of the final design model, our approach can carry out simultaneous and incremental multiresolution representation on the intermediate design models. To implement the system supporting this capability, we developed history-based selective Boolean operations, in which if the order of the Boolean operations for a part is altered, the regions affected by the operations are redefined according to the history of the Boolean operations so that the resultant shape may be the same as the original shape of the part. The system implemented using these operations guarantees a unique and valid shape for each intermediate LOD in the simultaneous multiresolution modeling environment. Since the system provides the designer immediately with various detail levels of the CAD model in any design stage, the design process is expected to be accelerated.     

海量数据多边形布尔运算的区域分割算法

研究了一种大数据量的2维多边形,称为海量数据多边形,其边界由直线段和圆弧段组成,顶点很多,形状复杂。本文设计并实现了海量数据多边形之间的布尔运算算法。首先用区域划分的方法快速求解出两多边形的交点,然后判断各交点的出点、入点性质,最后沿着多边形的边界跟踪,并根据并、交、差的不同要求切换跟踪路线,直到形成封闭的回路。运算结果仍为2维多边形。该算法从实用的角度出发,避开繁琐的数学推理,易于程序实现,在实际应用中显著提高了布尔运算的效率。     

基于DNA Tiles自组装的布尔逻辑运算

大量研究工作表明,DNA tiles自组装现象是分子生物计算过程中一个很重要的计算方式.分子自组装的基本特点在于由许多小分子在一定机理的作用下,自动形成更大规模的超级分子结构的过程.自组装用于计算,在于这种组装模式可以抽象成一个自动化的系统,只需根据问题的需要设计好输入,再将其输入到运算系统,经过分子自组装过程,最后能生成问题的解.文中基于这样的运算机理,在DNA tiles自组装这个计算平台上,尝试做布尔逻辑运算,针对4变量4句子的布尔逻辑问题,提出一个DNA tiles自组装自动化运算系统.     

Boolean set operations on non-manifold boundary representation objects

For Boolean operations on geometric models, we have developed an intersection algorithm for non-manifold boundary models with vertices, linear edges, planar faces, and volumetric regions. The algorithm operates by intersecting entities in an ordered manner, from vertex to edge, then to face elements. Singular intersections are systematically handled by determining if an entity in one object is within a tolerance region of the entity in the other object. The algorithm performs Boolean operations between objects of different dimensionality as well as solids. An implementation of the proposed algorithm and the experimental results are briefly discussed.     

Octree creation via C.S.G. definition

The common method for generating the octrees of complex objects, is based upon generating the octrees of several pre-defined primitives and applying Boolean operations on them. Regardless how the octrees representing the primitives are generated (top-down or bottom-up) the octree of a desired object is obtained by performing Boolean operations among the primitives comprising the object according to the object's CSG (constructive solid Geometry) representation. When carrying out this procedure, most of the computing and memory resources are used for generating and storing the octants comprising the primitives. However, the majority of those octants are not required for the representation of the final object. In this paper the extention of the top-down approach to the CSG level (i.e., generating the octree of an object directly from its CSG representation) is proposed. With this method there is no need to generate the octrees of the primitives comprising the object nor to perform Boolean operations on them. Moreover, only these octants which belong to the final object are generated.