BlenderCN论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 103|回复: 1

实体建模

[复制链接]
发表于 2020-1-14 11:48:42 | 显示全部楼层 |阅读模式
Blender中国社区或者说 Blender社区需要一本什么样的图形学书籍,这是我从接触Blender开始就在思考的问题,因为市面上有很多的专题和成果,但是很多书籍都是在某一方面进行了概括,并不是对整个人类社会将传统工作数字化上做出努力的概览,这样的叙述体系给我们的理解很多障碍,让我们只缘身在此山中,看不到一个整体的概况。

人类针对可观测世界的行为流程大致如下: 现实世界==>观测==>大脑==>思考运算==>执行  不管是画画还是做图形开发,我们的大脑都会对客观实在进行各种不变规律的分析和模拟,最终再输出到成品上,成为我们的程序和作品,因为我们是一个数字艺术社区,两方面同时思考,或许对我们理解如何使用计算机来制作艺术品会有更多的帮助。

简单以概括,计算机图形学就是物体表示,空间划分,场景物理,计算精度。

物体表示,就是现实物体在计算机中如何表达。 几何 拓扑 分形 如何放入计算机中,接下来这篇文章给了我们回答。

空间划分,这是计算机的要求,计算机中任何空间场景都是有限的,BVH,bsp,八叉树等等划分算法,将空间划分为有物体和没有物体的部分,计算机算法就可以很快识别其中的有和无。

场景物理,这是图形学的要求,将所有现实中的摄像机,灯光等放入计算机中,基本上与人眼感观有关系的参数,都是物理表示,最终,用户在GUI中可以调节这些数据,就跟我们在摄影棚里摆弄单反一样。

计算精度,这是计算机体系结构给的限制,也是离散化的要求,图形显卡和计算软件从2比特到8比特到16比特到32位到64位,带来的改变就是从黑白到256色到自然色彩,越少位数计算越快,位数越多计算越慢。要以适当的精度来构造图形学的表示。

数学上有个概念叫做**表示**,意思就是将抽象的描述用一种可以计算的方式展现出来,比如群和群的表示,几何描述和几何的代数表示等等。图形学中也借用了这个概念。下面的图解释了从现实世界,到数学模型,再到计算机表示上的一个思维过程。正是因为有了数学的发展,才有了如此多的工具,可以让我们把头脑中的构想,在计算机中得以实现。


下文以双语形式发布,为的是方便喜欢深入Blender开发的读者查询相关的技术术语,帮助很快的读懂Blender的源代码。也考虑到翻译工作难免有些纰漏,可以直接对照原文进行学习。



[TOC]



# Solid Modeling 实体建模

Rossignac & Requicha Solid Modeling 1

# Solid Modeling 实体建模 双语

**Jarek R. Rossignac**

GVU Center, College of Computing,

Georgia Institute of Technology, Atlanta

**Aristides A. G. Requicha**

Computer Science Department

University of Southern California at Los Angeles

# 1 Introduction 介绍

A solid model is a digital representation of the geometry of an existing or envisioned physical object. Solid models are used in many industries, from entertainment to health care. They play a major role in the discrete-part manufacturing industries, where precise models of parts and assemblies are created using solid modeling software or more general computer-aided design (CAD) systems. The design process is usually incremental. Designers may specify points, curves, and surfaces, and stitch them together to define electronic representations of the boundary of the object. Alternatively, they may select models of simple shapes, such as blocks or cylinders, specify their dimensions, position, and orientation, and combine them using union, intersection, or difference operators. The resulting representation is an unambiguous, complete, and detailed digital approximation of the geometry of an object or of an assembly of objects (such as a car engine or an entire airplane). Interactive three-dimensional (3D) graphic supports the design activities by providing designers with: (1) easy to understand images of their design, (2) efficient facilities for graphically selecting or editing features of the part being designed, and (3) immediate feedback, which helps them perform and check each design step.

实体建模是现有或设想的物理对象的几何形状的数字表示。从娱乐到医疗保健,实体建模已在许多行业中使用。它们在独立部件制造行业中扮演着重要角色,在独立制造业中,使用实体建模软件或更通用的计算机辅助设计(CAD)系统创建零件和组件的精确模型。设计过程通常是增量的。设计人员可以指定点,曲线和曲面,然后将它们缝合在一起以定义对象边界的电子表示形式。或者,他们可以选择简单形状的模型(例如块或圆柱体),指定其尺寸,位置和方向,然后使用并集,相交或差运算操作进行组合。结果表示是对象或对象组件(例如汽车引擎或整架飞机)的几何形状的明确,完整和详细的数字近似。交互式三维(3D)图形通过为设计师提供以下功能来支持设计活动:(1)易于理解其设计的图像;(2)用于以图形方式选择或编辑被设计零件的特征的高效工具;以及(3)即刻的反馈,这有助于他们执行和检查每个设计步骤。

Early applications of solid modeling focused on producing correct engineering drawings automatically and on cutter-path generation for numerically controlled machining [Requicha82, Requicha96]. Today, the engineering drawings still provide a link to traditional, non-electronic manufacturing or archival processes, but are being rapidly replaced with electronic file transfers. Solid modeling has evolved to provide the set of fundamental tools for representing a large class of products and processes, and for performing on them the geometric calculations required by applications. The ultimate goal is to relieve engineers from all of the low-level or non-creative tasks in designing products; in assessing their manufacturability, assemblability, and other life-cycle characteristics; and in generating all the information necessary to produce them. Engineers should be able to focus on conceptual, high-level design decisions, while domain-expert application programs should provide advice on the consequences of design decisions and generate plans for the manufacture and other activities associated with the product’s life cycle. The total automation of analysis and manufacturing activities (see for example [Spyridi93]), although in principle made possible by informationally complete solid models, remains a research challenge in spite of much progress on several fronts.

实体建模的早期应用集中于自动生成正确的工程图以及数控加工的刀具路径生成[Requicha82,Requicha96]。如今,工程图仍然提供了到传统的非电子制造或存档过程的链接,但已被电子文件传输迅速取代。实体建模已发展为提供一组基本工具,这些工具可用于表示一大类产品和过程,并在其上执行应用程序所需的几何计算。最终目标是使工程师摆脱设计产品时的所有低级或非创造性任务;评估其可制造性,可组装性和其他生命周期特征;并生成生产它们所需的所有信息。工程师应该能够专注于概念性的高层设计决策,而领域专家应用程序则应就设计决策的后果提供建议,并为制造和与产品生命周期相关的其他活动制定计划。尽管原则上可以通过信息完整的实体模型,实现分析和制造活动的完全自动化(例如,参见[Spyridi93]),但在实际上各个方面仍然是一项研究挑战。

Solid modeling has rapidly evolved into a large body of knowledge, created by an explosion of research and publications [Requicha88, Requicha92]. The solid modeling technology is implemented in dozens of commercial solid modeling software systems, which serve a multi-billion dollar market and have significantly increased design productivity, improved product quality, and reduced manufacturing and maintenance costs.

实体建模已迅速发展为大量的知识,这是由大量研究和出版物[Requicha88,Requicha92]创建的。 实体建模技术在数十种商业实体建模软件系统中实现,这些系统为数十亿美元的市场提供服务,并显着提高了设计生产率,改善了产品质量并降低了制造和维护成本。

Today, solid modeling is an interdisciplinary field that involves a growing number of areas. Its objectives evolved from a deep understanding of the practices and requirements of the targeted application domains. Its formulation and rigor are based on mathematical foundations derived from general and algebraic topology, and from Euclidean, differential, and algebraic geometry. The computational aspects of solid modeling deal with efficient data structures and algorithms, and benefit from recent developments in the field of computational geometry. Efficient processing is essential, because the complexity of industrial models is growing faster than the performance of commercial workstations. Techniques for modeling and analyzing surfaces and for computing their intersections are important in solid modeling. This area of research, sometimes called computer aided geometric design, has strong ties with numerical analysis and differential geometry. Graphic user-interface (GUI) techniques also play a crucial role in solid modeling, since they determine the overall usability of the modeler and impact the user’s productivity. There have always been strong symbiotic links and overlaps between the solid modeling community and the computer graphics community. Solid modeling interfaces are based on efficient three-dimensional (3D) graphics techniques, whereas research in 3D graphics focuses on fast or photo-realistic rendering of complex scenes, often composed of solid models, and on realistic or artistic animations of non-rigid objects. A similar symbiotic relation with computer vision is regaining popularity, as many research efforts in vision are model-based and attempt to extract 3D models from images or video sequences of existing parts or scenes. These efforts are particularly important for solid modeling, because the cost of manually designing solid models of existing objects or scenes far exceeds the other costs (hardware, software, maintenance, and training) associated with solid modeling. Finally, the growing complexity of solid models and the growing need for collaboration, reusability of design, and interoperability of software require expertise in distributed databases, constraint management systems, optimization techniques, object linking standards, and internet protocols.

如今,实体建模已成为一个涉及多个领域的跨学科领域。它的目标是从对目标应用程序领域的实践和要求的深刻理解中发展而来的。它的公式化和严格性是基于从普通拓扑和代数拓扑以及欧几里得几何,微分几何和代数几何派生而来的数学基础。实体建模的计算方面涉及有效的数据结构和算法,并受益于计算几何学领域的最新发展。高效的处理至关重要,因为工业模型的复杂性比商业工作站的性能增长更快。在实体建模中,用于建模和分析曲面以及计算其交点的技术很重要。该研究领域有时称为计算机辅助几何设计,与数值分析和微分几何有着紧密的联系。图形用户界面(GUI)技术在实体建模中也起着至关重要的作用,因为它们确定了建模者的整体可用性并影响了用户的生产率。实体建模社区和计算机图形学社区之间一直存在着强大的共生联系和重叠之处。实体建模界面基于高效的三维(3D)图形技术,而3D图形的研究则侧重于通常由实体模型组成的复杂场景的快速或逼真的渲染,以及非刚性对象的逼真的或艺术性的动画。 与计算机视觉类似的共生关系正在重新流行,因为视觉方面的许多研究工作都是基于模型的,并试图从现有零件或场景的图像或视频序列中提取3D模型。这些工作对于实体建模尤为重要,因为手动设计现有对象或场景的实体模型的成本远远超过了与实体建模相关的其他成本(硬件,软件,维护和培训)。最后,实体模型的复杂性和协作性,设计的可重用性以及软件的交互操作性的需求不断增长,这需要分布式数据库,约束管理系统,优化技术,对象链接标准和Internet协议方面的专业知识。

Rossignac & Requicha Solid Modeling 2

Research in solid modeling emerged in the 1970’s from early exploratory efforts that sought shape representations suitable for machine vision and for the automation of seemingly routine tasks performed by designers and engineers in Computer-Aided Design, Manufacturing, Construction and Architecture (currently encapsulated in the CAD/CAM/CAE abbreviation).

实体建模的研究始于1970年代的早期探索性工作,这些工作寻求适合于机器视觉的形状表示形式,并希望由计算机辅助设计人员和工程师执行的看似常规任务的自动化包括:设计,制造,构造和架构(当前封装在CAD / CAM / CAE中的缩写)。

Solid modeling impacts a great variety of design and manufacturing activities. Examples include early sketches, design decisions, space allocation negotiations, detailed design, drafting, interactive visualization of assemblies, maintenance-process simulation, usability studies, engineering changes, reusability of design components, analysis of tolerances [Requicha93], 3D mark-up and product data management, remote collaboration, internet-based catalogs of parts, electronic interaction with suppliers, analysis (e.g., mechanism analysis or finite elements), process planning and cutter-path generation for machining, assembly and inspection planning, product documentation, and marketing.

实体建模影响各种各样的设计和制造活动。 示例包括早期草图,设计决策,空间分配谈判,详细设计,起草,装配体的交互式可视化,维护过程模拟,可用性研究,工程变更,设计组件的可重用性,公差分析[Requicha93],3D标记和 产品数据管理,远程协作,基于Internet的零件目录,与供应商的电子交互,分析(例如,动力学分析或有限元),用于加工,装配和检验计划的工艺计划和刀具路径生成,产品文档和营销 。

# 2 Solid modeling systems 实体建模系统

A solid modeling system, often called a solid modeler, is a computer program that provides facilities for storing and manipulating data structures that represent the geometry of individual objects or assemblies. These representations can be created either by a human through a graphic user interface (GUI), or specified by software applications via an application programming interface (API). In a typical interactive application, a user selects and manipulates modeling primitives (parameterized instances of simple geometric shapes, such as a cylinder or a line) and invokes modeling operations that combine or transform these primitives into more elaborate representations.

实体建模系统(通常称为“实体建模器”)是一种计算机程序,它提供了用于存储和处理表示单个对象或组件的几何形状的数据结构的工具。 这些表示可以由人类通过图形用户界面(GUI)创建,也可以由软件应用程序通过应用程序编程接口(API)指定。 在典型的交互式应用程序中,用户选择并操纵建模图元(简单的几何形状的参数化实例,例如圆柱体或直线),并调用将这些图元组合或转换为更精细表示的建模操作。

A modeler’s GUI generates 3D graphic feedback to a user by immediately displaying selected portions of the objects being designed. In addition, it provides facilities for selecting and for graphically editing the displayed entities. Users of modern modelers can describe objects in terms of features, which are higher-level entities meaningful for their applications, can use dimensions and other constraints to help in sizing and positioning geometric entities, and can also parameterize the objects so as to create object families.

建模者的GUI通过立即显示要设计的对象的选定部分来向用户生成3D图形反馈。 另外,它提供了选择和图形编辑显示实体的功能。 现代建模工具的用户可以根据特征来描述对象,这些特征是对他们的应用有意义的高级实体,可以使用尺寸和其他约束条件来帮助确定几何实体的大小和位置,还可以参数化对象以创建对象族 。

The choice of representations used by the modeler determines its domain (i.e., which objects can be modeled), and has a strong impact on the complexity and performance of the algorithms that create or process the representations. A modeler may support several distinct representation schemes. Consistency between representations in different schemes is typically enforced by representation conversion algorithms.

建模工具使用的表示形式的选择决定了它的适用领域(即可以建模的对象),并且对创建或处理表示形式的算法的复杂性和性能有很大影响。 建模工具可以支持几种不同的表示方案。 不同方案中表示之间的一致性通常由表示转换算法来实现。

Application programs invoked by the users analyze the models and generate information on the object’s properties (e.g., its moments of inertia, or its deflection under load, calculated by finite element methods), or on processes needed by life-cycle activities such as manufacture, assembly or inspection. In a modern engineering environment, these applications should run concurrently with the design process, to help assess the consequences of design decisions, and provide guidance to the designers. The architecture of a typical solid modeler is illustrated Figure 1.

用户调用的应用程序会分析模型,并生成有关对象属性(例如,惯性矩或其在负载下的挠度,通过有限元方法计算)或生命周期活动(例如制造)所需的过程的信息, 组装或检查。 在现代工程环境中,这些应用程序应与设计过程同时运行,以帮助评估设计决策的结果,并为设计人员提供指导。 图1说明了一个典型的实体建模器的体系结构。

![1571901262329]( \AppData\Roaming\Typora\typora-user-images\1571901262329.png)

User 用户

Application 应用

Standard exchange formats 标准交换格式

Derived explicit representations 派生出的精确表示

High-level parameterized 高级参数化

Database 数据库

API commands 应用程序接口命令

Graphics 图形化

API answers 应用程序接口调用反馈

Conversion 转换

Algorithmic Evaluation 算法评估

GUI 用户界面

Archival 持久化/归档



Figure 1: A high-level parameterized representation of the design steps and of the model’s features and constraints may be created interactively by the user through a design interface (GUI) or by an application through a programming interface (API). This constructive representation may be archived for future editing and reuse and may be automatically converted into one or several derived representations, which explicitly list the faces of the solid’s boundary or the 3D cells covered by the solid. The derived representations are suitable for providing realtime graphic feedback to the designer and directly support application queries. They may also be exported to other applications or CAD systems by converting them to a standard file format.

图1:用户可以通过设计界面(GUI)或应用程序通过编程界面(API)交互地创建设计步骤以及模型的特征和约束的高级参数化表示。 这种结构性表示形式可以存档以备将来编辑和重复使用,并且可以自动转换为一个或几个派生表示形式,这些表示形式明确列出了实体边界的面或该实体所覆盖的3D单元。 派生的表示适用于向设计人员提供实时图形反馈,并直接支持应用程序查询。 通过将它们转换为标准文件格式,它们也可以导出到其他应用程序或CAD系统。

Rossignac & Requicha Solid Modeling 3

# 3 Mathematical foundations 数学基础

The modeling process is the result of a sequence of abstractions and approximations (idealization, surface approximation, and digitization) presented in this section.

建模过程是本节中介绍的一系列抽象和近似(理想化,表面近似和数字化)的结果。

## 3.1 Idealization 理想化

First the physical shape is abstracted into a perfect and homogeneous 3D point set, ignoring internal structures and boundary imperfections. (Modeling of non-homogeneous objects will be discussed briefly later in this article.)

首先,将物理形状抽象为一个完美且均匀的3D点集,而忽略内部结构和边界缺陷。 (非同质对象的建模将在本文稍后简要讨论。)

Mathematically, a solid is a subset of 3D Euclidean space. Precise definitions were developed in the mid 1970’s at the University of Rochester’s Production Automation Project (PAP) and have guided the development of data structures and algorithms that support high-level design operations and guarantee that valid representations of solids are produced. R-sets, which are bounded, regular, semi-algebraic sets, were proposed as mathematical models for physical solids [Requicha80]. A set is bounded if it has finite extent, i.e., if it can be enclosed by a ball of a finite radius. A regular set is homogeneously three-dimensional, and therefore has no dangling faces or edges. Mathematically, a set is regular if it equals the topological closure of its interior. A semi-algebraic set is the result of combining through set operations (union, difference, intersection and complement) a finite number of halfspaces, each defined by an algebraic inequality of the form {(x,y,z) | f(x,y,z)≤0}, where f is a polynomial. Note that this definition does not preclude sets that are bounded by free-form parametric patches, although implicitizing (i.e., converting them) into semialgebraic form is computationally hard and produces inequalities of very high degree. (Semi-algebraic sets also play an important role in robotics, constraint satisfaction, and theorem proving.) More precise definitions for these topological terms may be found in [Alexandroff61].

从数学上讲,实体是3D欧式空间的子集。精确定义是在1970年代中期由罗切斯特大学的生产自动化项目(PAP)开发的,并指导了数据结构和算法的开发,这些数据结构和算法支持高级设计操作并确保产生实体的有效表示形式。 R-集是有界的,规则的,半代数集,被提出作为物理实体的数学模型[Requicha80]。如果集合具有有限的范围,即它可以被有限半径的球包围,则该集合是有界的。规则集是均匀三维的,因此没有悬空的面或边。从数学上讲,如果集合等于其内部的拓扑闭合,则它是规则的。半代数集是通过集合操作(联合,差,相交和补码)组合有限数量的半空间而得到的结果,每个半空间都由形式为{(x,y,z)| f(x,y,z)≤0}的代数不等式定义,其中f是多项式。请注意,尽管将定义隐含(即将它们转换为)半代数形式在计算上很困难并且会产生非常高阶的不等式,但该定义并不排除以自由形式的参数补丁为边界的集合。 (半代数集在机器人技术,约束满足和定理证明中也起着重要作用。)这些拓扑术语的更精确定义可以在[Alexandroff61]中找到。

Some modelers cater only to r-sets that are manifolds. A manifold model has a boundary whose edges are shared by precisely two faces, and whose vertices are adjacent to a set of faces that forms a single cone with apex at the vertex. Unfortunately, the domain of manifold r-sets is not closed under some of the fundamental modeling operations. For example, the union of the two L-shaped manifold solids in Figure 2 is a non-manifold solid. Hence, users of such restricted systems must carefully avoid creating nonmanifold shapes.

一些建模工具仅适应于流形的R集。 流形模型具有一个边界,该边界的边缘恰好由两个面共享,并且其顶点与一组面相邻,这些面形成一个顶点为顶点的单个圆锥。 不幸的是,在某些基本建模操作下,流形r-集的域没有封闭。 例如,图2中两个L流形管实体的并集是非流形实体。 因此,使用这种受限系统的用户必须小心避免产生非流形形状。

![1571901316523](\AppData\Roaming\Typora\typora-user-images\1571901316523.png)

Figure 2: The two L-shaped solids A and B (left), are positioned so that an edge of A coincides with an edge of B. Their union, A+B, is a non-manifold solid (right).

图2:放置两个L形实体A和B(左),使A的边缘与B的边缘重合。它们的并集A + B是非流形实体(右)。

## 3.2 Surface Approximation 曲面近似

In a second idealization stage, the boundary of the shape is approximated by a relatively small number of faces, each face being a subset of a surface of a type supported by the modeling system. Much of the variation between solid modeling technologies stems from the different choices of the primitive surfaces they support. These surfaces essentially determine the geometric domain of a system, i.e., the objects that can be modeled exactly.

在第二理想化阶段,通过相对较少数量的面来近似形状的边界,每个面是建模系统所支持类型的表面的子集。 实体建模技术之间的许多差异都源于它们支持的原始曲面的不同选择。 这些表面本质上决定了系统的几何范围,即可以精确建模的对象。

On one hand, planar face primitives, i.e., triangles or more general polygons, provide a poor approximation of the real shape, unless used in large quantities to define fine tessellations of highly curved geometries. Although algorithms for dealing with individual triangles are simple and relatively robust, compact data structures for representing very large numbers of triangles and efficient algorithms for processing or rendering them are complex to develop and to maintain.

一方面,除非大量使用平面基本体,即三角形或更普通的多边形,否则不能很好地逼近真实形状,除非用于定义高度弯曲的几何形状的精细镶嵌。 尽管处理单个三角形的算法简单且相对健壮,但用于表示大量三角形的紧凑数据结构以及用于处理或渲染它们的高效算法开发和维护起来都很复杂。

On the other hand, a single parametric free-form surface patch [Farin90] which may be smoothly stitched with other patches in a Non-Uniform Rational B-spline Surface (NURBS), may provide a better fit to the desired geometry than a thousand triangles. However, detecting and computing intersections of such free-form surfaces involves elaborate mathematical techniques and algorithms that are significantly slower and less reliable than their counterparts for triangular geometries.

另一方面,可以与非均匀有理B样条曲面(NURBS)中的其他贴片平滑缝合的单个参数化自由形式表面贴片[Farin90],可以提供比一千个更好的拟合所需的几何形状 三角形。 但是,检测和计算此类自由曲面的交点涉及复杂的数学技术和算法,这些数学技术和算法比三角形几何图形的对应算法明显更慢且可靠性更低。

Natural quadric surfaces (plane, cylinder, cone, sphere) offer an attractive compromise, because they provide mathematically exact representations for the majority of faces found in manufactured objects, and lead to closed form expressions for theirintersection curves and to low degree polynomial solutions for the computation of the points where 3 surfaces intersect. However, these surfaces cannot model precisely the numerous fillets and blends found in most manufactured parts [Rossignac84]. They also cannot model sculptured or free-form surfaces that appear in many objects, especially those that must satisfy esthetic requirements, such as car bodies.

自然二次曲面(平面,圆柱,圆锥,球面)提供了一个有吸引力的折衷方案,因为它们在数学上提供了对制造对象中发现的大多数面的精确表示,并导致了相交曲线的闭合形式表达式以及对它们的低次多项式解来计算3个曲面相交的点。 但是,这些表面无法精确地模拟大多数制造零件中发现的大量圆角和混合[Rossignac84]。 他们也无法对出现在许多物体中的雕塑或自由曲面进行建模,尤其是那些必须满足美学要求的物体,例如车身。

Rossignac & Requicha Solid Modeling 4

The choice of the geometric domain of a modeler may affect the accuracy of the analysis results. For example, a cylindrical pin may freely rotate in a cylindrical hole of a slightly larger radius, if both surfaces are modeled using natural quadrics. Using faceted approximations for the pin and the hole may lead to the wrong conclusion that the pin cannot rotate or doesn’t even fit.

建模工具的几何域的选择可能会影响分析结果的准确性。 例如,如果两个表面都使用自然二次曲面建模,则圆柱销可以在半径稍大的圆柱孔中自由旋转。 对销和孔使用多面近似法可能会得出错误的结论,即销无法旋转或什至无法安装。

## 3.3 Digitization 数字化

In a third approximation stage, the numeric parameters that define the precise shape and position of the surfaces and their intersections are rounded to the nearest value representable in the digital format selected by the developer of the system. The most common formats are floating point and integer or rational [Ralston83]. Floating point representations cover a wider range of values, but their worst case round-off error grows with the distance to the origin. Integer numbers, when scaled and offset properly by a judicious choice of units and of the origin, provide a much denser and uniform coverage of a desired modeling range, and hence lead to lower and better-controlled round-off errors. In practice, floating point numbers are favored because they do not require prior knowledge of the range and can be used in a uniform way to represent the parameters of the model and the results of intermediate calculations. However, floating point calculations generate and propagate round-off errors. The developers of a modeling system must ensure that these round-off errors do not lead to logical errors, to software crashes, or to wrong design decisions. Exact arithmetic packages do not suffer from round-off problems, but are significantly slower and usually only effective for polyhedral geometries (see discussions in [Banerjee96, Agrawal94]).

在第三近似阶段中,将定义曲面及其相交的精确形状和位置的数值参数四舍五入为系统开发人员选择的数字格式可表示的最接近值。最常见的格式是浮点数和整数或有理数[Ralston83]。浮点表示法涵盖范围更广的值,但最差情况下的舍入误差随距原点的距离而增加。通过明智地选择单位和原点来适当地缩放和偏移整数,可以对所需的建模范围进行更密集,更均匀的覆盖,因此可以实现更低且更好控制的舍入误差。实际上,浮点数是受青睐的,因为它们不需要范围的先验知识,并且可以以统一的方式用于表示模型的参数和中间计算的结果。但是,浮点计算会生成并传播舍入误差。建模系统的开发人员必须确保这些舍入错误不会导致逻辑错误,软件崩溃或错误的设计决策。精确的算术程序包不会遇到四舍五入的问题,但速度明显较慢,通常仅对多面体几何有效(请参见[Banerjee96,Agrawal94]中的讨论)。

# 4 Representations 表示

This section reviews the most common schemes for representing 3D objects: boundary representations, constructive solid geometry, and spatial decompositions. Their extensions beyond the domain of solid models are also briefly discussed.

本节回顾了最常见的表示3D对象的方案:边界表示,构造实体几何和空间分解。 还简要讨论了它们在实体模型领域之外的扩展。

## 4.1 Boundary representations 边界表示



A physical object, modeled mathematically by an r-set, is unambiguously defined by its boundary. Therefore, a solid may be represented by a set of non-overlapping faces, whose union approximates the solid’s boundary. Such a scheme is called a boundary representation, or BRep for short. Unfortunately, an arbitrary set of faces does not necessarily correspond to the boundary of a solid. In fact, invalid BReps created by designers or by incorrect algorithms that implemented higher-level modeling operations plagued the early versions of many solid modelers.

用r-集数学建模的物理对象明确地由其边界定义。 因此,实体可以由一组不重叠的面表示,它们的并集近似于实体的边界。 这种方案称为边界表示或简称BRep。 不幸的是,任意一组面不一定对应于实体的边界。 实际上,设计人员或实施高级建模操作的错误算法所产生的无效BReps困扰着许多早期版本实体建模软件。

## 4.2 Data structures 数据结构

Although a simple enumeration of a solid’s faces suffices to unambiguously define the solid, most boundary representation schemes store additional information to accelerate the traversal and processing of the boundary and combine the description of adjacent faces in order to eliminate the redundant descriptions of their common vertices. These data structures often capture the incidence relations between a face and its bounding edges and vertices, and between an edge and its bounding vertices. Many data structures have been studied to achieve desired compromises between (1) the domain (or coverage) of the modeler, (2) the simplicity ,regularity, and compactness of the data structure, and (3) the complexity and efficiency of the algorithms that process the representation.

尽管简单地枚举实体的面就足以明确定义实体,但是大多数边界表示方案都存储了更多信息,以加速边界的遍历和处理,并结合了相邻面的描述,从而消除了它们共同顶点的多余描述。 这些数据结构通常捕获面及其边界、边界和顶点之间以及边界及其边界顶点之间的关联关系。 人们已经对许多数据结构进行了研究,以在(1)建模器的域(或覆盖范围),(2)数据结构的简单性,规则性和紧凑性以及(3)算法的复杂性和效率之间实现所需的折衷。 处理表示。

As an example, we describe with the help of Figure 3 a simple data structure for manifold polyhedral objects. It is a simplified version of the winged-edge representation introduced in [Baumgart72]. The vertices of the object are stored in a table with the associated coordinates. Edges are represented by references to vertices and to adjacent edges. Note that this data structure defines the geometry of the edges and of the loops which bound the faces, but does not explicitly capture the relations between the different loops of the same face. For example, the face on the right of Figure 3 has an outer loop that encloses a smaller, triangular, inner loop of edges. Some boundary representations have separate nodes for faces, and store explicitly the face and loop relationships. Alternatively, faces with holes may be converted into simply-connected faces by introducing artificial “bridge” edges that each merge two loops of a face.

例如,我们借助图3描述了用于流形多面体的简单数据结构。 它是[Baumgart72]中引入的有翼边缘表示的简化版本。 对象的顶点与关联的坐标一起存储在表格中。 边由对顶点和相邻边的引用表示。 请注意,此数据结构定义了边缘和限制面的环的几何形状,但未明确捕获同一面的不同环之间的关系。 例如,图3右侧的面具有一个外部环,该环包围了较小的三角形内部边缘环。 一些边界表示具有单独的面节点,并显式存储面和循环关系。 或者,可以通过引入人工“桥”边将带有孔的面转换为简单连接的面,每个边将面的两个环合并。

![1571901351648](\AppData\Roaming\Typora\typora-user-images\1571901351648.png)

Figure 3: Edge E points to its starting and ending vertices V1 and V2. The order of vertex-references defines an orientation for the edge (arrow). The node that corresponds to E also contains references to edges E1 and E2. E1 is the next edge around V1 for the face on the right of E, and E2 is the next edge around V2 for the face on the left of E. The terms “next edge”, “on the left”, and “on the right” are unambiguously defined by considering the outwardpointing normals to the faces and the orientation of E. The bridge edge which links the outer loop of the right face with its inner loop is indicated by the double line segment through the face.

图3:边E指向其起点和终点V1和V2。 顶点参考的顺序定义了边的方向(箭头)。 对应于E的节点还包含对边E1和E2的引用。 E1是E右边的脸的V1周围的下一条边,E2是E左边的脸的V2附近的下一条边。术语“下一条边”,“左侧”和“在……上” “右侧”是通过考虑面的朝外法线和E的方向明确定义的。将右面的外环与其内环相连的桥边由穿过该面的双线段表示。

Rossignac & Requicha Solid Modeling 5

The faces in a BRep of a curved object may be represented as parametric patches, which are the images of a unit square or of a triangle by a polynomial mapping from a 2D parameter space into the 3D modeling space. Alternatively, a face may be represented as a trimmed surface by a reference to the supporting surface on which it lies, and by its boundary in that surface. The supporting surface may itself be a larger parametric patch or an implicit surface. The boundary is usually represented by a set of edges, which may be arranged into loops.

曲线对象的BRep中的面可以表示为参数块,其是从2D参数空间到3D建模空间的多项式映射的单位正方形或三角形的图像。 可替代地,可以通过参考其所位于的支撑表面以及在该表面中的边界来将其表示为修剪的表面。 支撑表面本身可以是较大的参数面块或隐式表面。 边界通常由一组边缘表示,这些边缘可以排列成环。

The edges of a solid typically lie on the intersection curves between two surfaces, and sometimes on singular curves of a single surface. A simple edge, such as a line segment or a circular arc, may be represented by its type, parameters, and position in space. More complex edges are often approximated by piecewise-polynomial parametric curves, either in 3D, or in the 2D parameter space of the host surface. The latter case leads to redundant representations because each edge typically belongs to two surfaces. Redundant representations may conflict due to numeric round-off errors, and cause “cracks” in the boundary. Exact, closed-form parametric representations for the intersection of natural quadric surfaces were first derived in the late 1970s at the University of Rochester for the PADL-2 modeler [Brown82]. The intersections of these edges with implicit polynomial surfaces can be computed efficiently by substituting the parametric expressions, (x(t),y(t),z(t)), of a point on the curve into the implicit polynomial equation for the surface, f(x,y,z)=0 and solving for t using an efficient numeric polynomial root finder.

实体的边缘通常位于两个曲面之间的相交曲线上,有时位于单个曲面的奇异曲线上。简单的边缘(例如线段或圆弧)可以通过其类型,参数和空间位置来表示。在3D或主体表面的2D参数空间中,通常通过分段多项式参数曲线来近似更复杂的边缘。后一种情况导致多余的表示,因为每个边缘通常属于两个表面。冗余表示法可能会由于数字舍入误差而发生冲突,并在边界中引起“裂纹”。天然二次曲面相交的精确,封闭形式的参数表示形式是在1970年代后期由罗切斯特大学(University of Rochester)使用PADL-2建模器得出的[Brown82]。通过将曲线上某点的参数表达式(x(t),y(t),z(t))替换为曲面的隐式多项式方程,可以有效地计算这些边与隐式多项式曲面的交点,f(x,y,z)= 0并使用有效的数值多项式根查找器求解t。

Edge loops may be insufficient to define a face unambiguously. For example, a circular edge on a spherical surface is the boundary of two complementary faces. These may be distinguished by storing information about which points in the neighborhood of the edge belong to the face. This neighborhood information can be encoded efficiently, as a single-bit “left” or “right” attribute, in terms of the orientation of the surface normal and the orientation of the curve.

边缘环可能不足以明确定义一个面。 例如,球形表面上的圆形边缘是两个互补面的边界。 这些可以通过存储有关边缘附近哪些点属于人脸的信息来区分。 就表面法线的方向和曲线的方向而言,该邻域信息可以有效地编码为一位“左”或“右”属性。



## 4.3 Domain extensions for BReps 边界表示的域扩张

Many contemporary applications of solid modeling require dealing with non-regular sets (such as lower-dimensional regions of contacts between solids), or with non-homogeneous point sets (such as composite-material aircraft parts and semi-conductor circuits consisting of adjacent regions with different material properties). Such objects cannot be represented in a traditional solid modeler. Several boundary representation schemes have been proposed for domains that extend beyond solids [Rossignac92b]. For example, Weiler’s radial-edge structure was centered around entities that represent face-edge and edge-vertex incidence relations to explicitly capture how faces are ordered around an edge [Weiler87]. Schemes that extend beyond solids are best analyzed in terms of a decomposition of space into cells of various dimensions (volumes, faces, edges, points) and in terms of their support for selecting arbitrary combinations of such cells. For example, the Selective Geometric Complex (SGC), developed by Rossignac and O’Connor [Rossignac89b], provides a general representation for non-regular point sets, which combine isolated points, edges, faces, and volumes with internal structures and cracks (isolated faces, edges, or vertices removed from the interior of the volume). An SGC model is based on a subdivision of Euclidean space into cells of various dimensions that are disjoint, open, connected sub-manifolds and are “compatible” with all the solids, faces, edges, and vertices of the primitive shapes and with all their intersections. (Two sets are compatible if they are disjoint or equal, or if one is included in the other.) Each cell is represented by its supporting manifold (curve, surface, or volume) and by the list of its bounding cells. Techniques independent of the dimension of the space have been proposed for computing such subdivisions, for selecting and marking sets of cells that correspond to a given description (such as a regularized Boolean operation between two previously selected sets), and for simplifying the representation through the removal or the merging of cells with identical markings. The SGC representation is capable of modeling sets with internal structures, or sets of sets. These combine mutually disjoint regions, where each region is the union of all the cells with identical markings. Each region may correspond to a mixed-dimensional (i.e. non regularized) set.

实体建模的许多当代应用都需要处理非规则集(例如实体之间接触的低维区域)或非均匀点集(例如复合材料飞机零件和由相邻区域组成的半导体电路具有不同的材料特性)。此类对象无法在传统的实体建模器中表示。对于超出实体[Rossignac92b]的域,已经提出了几种边界表示方案。例如,Weiler的放射状边缘结构围绕表示脸部边缘和边缘-顶点入射关系的实体为中心,以明确捕获围绕边缘的面部排序方式[Weiler87]。最好从空间分解成各种尺寸(体积,面,边缘,点)的单元的角度,以及它们对选择此类单元的任意组合的支持方面来分析超出固体的方案。例如,由Rossignac和O'Connor [Rossignac89b]开发的“选择性几何复合体(SGC)”提供了非规则点集的一般表示,该点集将孤立的点,边,面和体积与内部结构和裂缝结合在一起(从体积内部移除孤立的面,边或顶点)。 SGC模型基于欧几里德空间的细分,将其划分为各种大小的像元,这些像元是不相交的,开放的,相连的子流形,并且与原始形状的所有实体,面,边和顶点以及它们的所有“实体”“兼容”交叉路口。 (如果两个集合不相交或相等,或者其中一个包含在另一个集合中,则它们是兼容的。)每个像元均由其支持流形(曲线,曲面或体积)和其边界像元列表来表示。已经提出了独立于空间尺寸的技术,用于计算此类细分,选择和标记与给定描述相对应的单元格集合(例如两个先前选择的集合之间的正则布尔运算),以及通过移除或合并具有相同标记的单元格。 SGC表示能够使用内部结构或集合集对模型进行建模。这些结合了相互不相交的区域,其中每个区域是所有具有相同标记的单元的并集。每个区域可以对应于混合维(即,非正则化)集合。

Rossignac & Requicha Solid Modeling 6

## 4.4 Constructive solid geometry 构造实体几何

Constructive representations capture a construction process which defines the solid by a sequence of operations that instantiate or combine modeling primitives or the results of previous constructions. They often capture the user’s design intent in a highlevel representation that may be easily edited and parameterized.

构造表示捕获构造过程,该过程通过实例化或组合建模图元或先前构造结果的一系列操作来定义实体。 他们通常以高级表示形式捕获用户的设计意图,可以很容易地对其进行编辑和参数化。

### 4.4.1 CSG representations 构造实体几何表示

Constructive Solid Geometry (CSG) is the most popular constructive representation. Its primitives are parameterized solids, which may be simple shapes (such as cylinders, cones, blocks) or more complex features suitable for a particular application domain (such as slots or counter-bored holes). The primitives may be instantiated multiple times (possibly with different parameter values, positions, and orientations) and grouped hierarchically. Primitive instances and groups may be transformed through rigid body motions (which combine rotations and translations) or scaling.

构造实体几何(CSG)是最流行的构造表示。 它的基元是参数化的实体,可以是简单的形状(例如圆柱体,圆锥体,块体),也可以是更复杂的特征,适用于特定的应用领域(例如槽或沉头孔)。 图元可以被实例化多次(可能使用不同的参数值,位置和方向)并进行分层分组。 原始实例和组可以通过刚体运动(结合旋转和平移)或缩放来转换。

The transformed instances may be combined through regularized Boolean operations: union, intersection, and difference. These regularized operations perform the corresponding set theoretic Boolean operations, and then transform the result into an r-set by applying the topological interior operation followed by the topological closure. They always return valid (although possibly empty) solids. Although other Boolean operations may be offered, these three are convenient and sufficient, because amongst the 16 different Boolean combinations of two sets, A and B, 8 are unbounded, 3 are trivial, and only 5 are useful for solid modeling: the union A+B, the intersection AB, the differences A-B and B-A, and the symmetric difference, (A-B)+(B-A), as shown in Figure 4.

可以通过正则化布尔运算(并集,交集和差值)将转换后的实例进行组合。 这些正则化运算执行相应的集合理论布尔运算,然后通过应用拓扑内部运算和拓扑闭包将结果转换为r集。 它们始终返回有效(尽管可能为空)的实体。 尽管可以提供其他布尔运算,但是这三种方法方便且足够,因为在两组的16种不同布尔运算组合中,A和B,8是无界的,3是微不足道的,并且只有5个可用于实体建模:联合A + B,交点AB,差AB和BA以及对称差(AB)+(BA),如图4所示。

![1571901375856](\AppData\Roaming\Typora\typora-user-images\1571901375856.png)

Figure 4: The five non-trivial Boolean combinations of two sets (from left to right): A+B={a: a∈A or a∈B}, AB={a: a∈A and a∈B}, A-B={a: a∈A and a∉B}, B-A={a: a∉A and a∈B}, and the symmetric difference (A-B)+(B-A). The notation “ikS” refers to the interior of the closure of S and corresponds to the regularization of the results of the standard set theoretic Boolean operations.

图4:两组的五个非平凡布尔组合(从左到右):A + B = {a:a∈A或a∈B},AB = {a:a∈A和a∈B}, AB = {a:a∈A和a∉B},BA = {a:a∉A和a∈B},对称差(AB)+(BA)。 符号“ ikS”是指S闭包的内部,对应于标准集理论布尔运算的结果的正则化。

Figure 5 illustrates how a simple syntax may be used to specify a solid in CSG. Parsing such a syntax, yields a rooted graph, whose leaves represent primitive instances and whose internal nodes represent transformations or Boolean operations that produce solids. The root represents the solid corresponding to the CSG graph.

图5说明了如何使用简单语法在CSG中指定实体。 解析这种语法会生成一个有根图,其叶子代表原始实例,其内部节点代表产生实体的转换或布尔运算。 根表示与CSG图相对应的实体。

CSG representations are concise, always valid in the r-set modeling domain, and easily parameterized and edited. Many solid modeling algorithms work directly on CSG representations through a divide-and-conquer strategy, where results computed on the leaves are transformed and combined up the tree according to the operations associated with the intermediate nodes. However, CSG representations do not explicitly carry any information on the connectivity or even the existence of the corresponding solid. These topological questions are best addressed through some form of boundary evaluation, where a whole or partial BRep is derived algorithmically from the CSG model.

CSG表示简洁明了,在r-set建模域中始终有效,并且易于参数化和编辑。 许多实体建模算法通过分而治之的策略直接在CSG表示上工作,在叶子上计算的结果将根据与中间节点相关的操作进行转换并合并到树上。 但是,CSG表示没有明确携带有关连通性或相应实体是否存在的任何信息。 这些拓扑问题可以通过某种形式的边界评估得到最好的解决,其中从算法上从CSG模型中导出整个或部分BRep。



Rossignac & Requicha Solid Modeling 7

![1571901400772]\AppData\Roaming\Typora\typora-user-images\1571901400772.png)

Figure 5: The instances A, B, and E are shown (left) superimposed on the same reference grid. The solid S was specified by the following sequence of commands: A=Block(2,1,4); B=Rotated(A,Z-axis,-90) C=A+B D=Block(1,1,1); E=Translated(D,1,0,1); S=C-E; The corresponding CSG graph (right) has 2 leaf primitives, 2 transformation nodes, and 2 regularized Boolean operation nodes.

图5:实例A,实例B和实例E(重叠)显示在同一参考网格上。 固体S由以下命令序列指定:A = Block(2,1,4); B =旋转(A,Z轴,-90)C = A + B D =块(1,1,1); E =变换的(D,1,0,1); S = C-E; 相应的CSG图(右)具有2个叶基元,2个转换节点和2个正则化布尔运算节点。

### 4.4.2 Bending, twisting, blending, and Minkowski operations 弯曲,扭曲,混合和Minkowski操作

A Boolean operation always returns a solid whose boundary is a subset of the union of the boundaries of the arguments. Several transformations and operations that create new surfaces have been considered for extending the capabilities of CSG systems. However, many of these operations are difficult or impossible to integrate in the divide-and-conquer paradigm for CSG and in some CSG-to-boundary conversion algorithms, because simple calculations, such as point-containment, may not be easily obtained by combining the results of similar calculations on CSG primitives

布尔运算始终返回其边界是参数边界并集的子集的实体。 为了扩展CSG系统的功能,已经考虑了一些创建新表面的转换和操作。 但是,这些操作中有许多很难或不可能集成到CSG的“分而治之”范例中以及某些CSG到边界的转换算法中,因为简单的计算(例如点约束)可能难以通过合并获得 CSG原语类似计算的结果

Simple non-linear transformations may twist an object by applying to each point in space a 2D rotation around the z-axis with an angle that is a function of the z-coordinate [Barr84]. or may bend an object by interpreting the Cartesian x and y coordinates of a user-defined local coordinate system as the radius and angle in a cylindrical coordinate system. More complex free-form deformations have been proposed in [Sedeberg86].

简单的非线性变换可能会通过向空间中的每个点施加围绕z轴的2D旋转来扭曲对象,该旋转是z坐标的函数[Barr84]。 或者可以通过将用户定义的局部坐标系的笛卡尔x和y坐标解释为圆柱坐标系中的半径和角度来弯曲对象。 在[Sedeberg86]中已经提出了更复杂的自由形式变形。

The Minkowski sum A⊕B of two solids A and B is the result of sweeping one solid over the other. Mathematically, it is defined by {a+b, a∈A, b∈B}, where point a+b corresponds to the translation of point a by the vector from the origin to point b. Kaul and Rossignac used linear Minkowski combinations C(t)=(1-t)A⊕tB to construct parameterized shapes that smoothly interpolate any two polyhedra A and B. They further expanded this approach to the weighted Minkowski averages of a larger number of polyhedra [Rossignac94]. The user selects the shapes and orientations of the argument polyhedra. The modeling system computes the parameterized shape and animates its evolution in real time as the user explores the range of values of the interpolation parameters (weights). For example, one may animate a solid morph which corresponds to a Bezier curve in the space of polyhedra. Such tools are important for the interactive exploration of new shapes in design, for the simulation of some manufacturing processes, and for the creation of animations.

两个实体A和B的Minkowski和A⊕B是将一个实体扫掠到另一个上的结果。在数学上,它由{a + b,a∈A,b∈B}定义,其中点a + b对应于点a由向量从原点到点b的平移。 Kaul和Rossignac使用线性Minkowski组合C(t)=(1-t)A⊕tB来构造可平滑插值任意两个多面体A和B的参数化形状。他们进一步将此方法扩展为更多个多面体的加权Minkowski平均值[Rossignac94]。用户选择自变量多面体的形状和方向。当用户探索插值参数(权重)的值范围时,建模系统将计算参数化形状并对其动画进行实时动画处理。例如,可以在多面体空间中为对应于Bezier曲线的固体变形设置动画。此类工具对于交互式探索设计中的新形状,模拟某些制造过程以及创建动画非常重要。



Rossignac & Requicha Solid Modeling 8

Minkowski sums also play a crucial role in robotics for collision avoidance [Latombe91], and in accessibility and visibility analysis [Spyridi90, Spyridi94] Requicha used Minkowski operations to define the mathematical meaning of tolerance specifications [Requicha83] Minkowski sums or differences with a ball define growing and shrinking operations on solids. For instance, when B is a ball of radius r, A⊕B is a solid defined as the union of A with all points at a distance less or equal to r from A. The Minkowki difference, is the regularized difference between A and the set of points at a distance less than or equal to r from the complement of A. Combinations of growing and shrinking operations on solids were used by Rossignac and Requicha [Rossignac86] to produce constant radius fillets and blends (see Figure 6 for a 2D illustration). These operations always produce valid solids, and may be combined with Boolean operations to limit their “blending” or “filleting” effect to the desired sets of edges.

Minkowski求和在避免碰撞的机器人技术[Latombe91],可及性和可见性分析[Spyridi90,Spyridi94]中也起着至关重要的作用。Requicha使用Minkowski运算来定义公差规格的数学含义[Requicha83]对固体进行增长和收缩的操作。例如,当B是半径为r的球时,A⊕B是一个实体,定义为A与所有点之间的距离等于或小于r的A的并集。Minkowki差是A与A之间的正则差。距A的补数小于或等于r的一组点。Rossignac和Requicha [Rossignac86]使用对实体的生长和收缩操作的组合来生成恒定半径的圆角和混合(二维图请参见图6) )。这些操作始终会产生有效的实体,并且可以与布尔运算结合使用,以将其“混合”或“倒角”效果限制在所需的边集。

![1571901418916](\AppData\Roaming\Typora\typora-user-images\1571901418916.png)

Figure 6: The 2D shape (left) may be filleted (right) by first expanding it via a Minkowski sum with a disk of radius r (center) and then by shrinking the result via a Minkowski difference with the same disk. Subtracting the original shape from the filleted version yields solid fillets that may be easily trimmed before being added to the original solid.

图6:首先通过Minkowski和将2D形状(左)展开,然后将其倒角(右)
半径为r(中心)的圆盘,然后通过Minkowski差将结果缩小
磁盘。 从圆角版本中减去原始形状会产生易于填充的实心圆角
在添加到原始实体之前进行修剪。

### 4.4.3 CSG extensions to non-regularized sets CSG扩展到非正规集

Extensions of the Boolean operations to non-regularized solids, to r-sets with internal structures, and to sets of dimension larger than three are important for many applications. A constructive model for creating sets of sets from higher-level input, and for querying the existence and nature of intersections or adjacency relations between regions was developed by Rossignac and Requicha in their Constructive Non-Regularized Geometry (CNRG) model [Rossignac91]. Users or applications can instantiate primitives and specify how they should be combined to create a hyperset that is the union of mutually disjoint regions. CNRG regions correspond to expressions involving non-regularized Boolean and topological operations on primitive regions. Rossignac’s Structured Topological Complexes (STC) add to the CNRG representation the capability of creating and interrogating simultaneously several decompositions of the three-dimensional space [Rossignac97]. For example, the same space may be decomposed into volume and surface features important to manufacturing, into design features and their intersections, into functional components, or into finite elements for analysis. These decompositions are compatible, in that a cell belongs to a unique set in each decomposition. The user or the application program can manipulate primitive regions and their intersections in a uniform manner, independently of the representation or approximation of these entities in a particular modeler.

对于许多应用而言,将布尔运算扩展到非正则实体,具有内部结构的r集以及大于三维的维集非常重要。 Rossignac和Requicha在其构造性非正规几何(CNRG)模型[Rossignac91]中开发了一种构造模型,该模型用于从更高级别的输入创建集合集,并查询区域之间的相交或邻接关系的存在和性质。用户或应用程序可以实例化原语,并指定应如何组合它们以创建超集,该超集是相互不相交的区域的并集。 CNRG区域对应于涉及原始区域上非正规布尔和拓扑运算的表达式。 Rossignac的结构化拓扑复合体(STC)为CNRG表示增加了同时创建和询问三维空间分解的能力[Rossignac97]。例如,相同的空间可以分解为对制造重要的体积和表面特征,设计特征及其交叉点,功能组件或有限元素以进行分析。这些分解是兼容的,因为单元在每个分解中都属于唯一集合。用户或应用程序可以以统一的方式操作原始区域及其相交,而与特定建模器中这些实体的表示或近似无关。

## 4.5 Spatial decomposition approximations of solids 实体的空间近似分解

Solids may be represented either exactly or approximately by a variety of space decomposition schemes. The entire 3D space, or just the set that corresponds to the solid, is partitioned into non-overlapping 3D regions called cells.

实体可以通过各种空间分解方案精确地或近似地表示。 整个3D空间或仅与实体相对应的集合被划分为称为单元的非重叠3D区域。

Spatial decomposition schemes may differ in the restrictions they impose on cells. These may be polyhedral or bounded by curved surfaces. Cells are usually connected. Furthermore, many decomposition schemes do not support cells with holes or handles Cells may be further restricted to be convex, or even to be tetrahedra, or axis-aligned rectangular blocks, or regularlyspaced cubes.

空间分解方案可能会对它们施加的限制有所不同。 这些可以是多面体的,也可以由曲面限制。 单元通常是连接的。 此外,许多分解方案不支持带有孔或手柄的单元格。单元格可能进一步被限制为凸形,甚至四面体,轴对齐的矩形块或规则间隔的立方体。

### 4.5.1 Regular decompositions 常规分解

Regular decompositions approximate solids by stacks of constant-thickness slices, by prismatic columns of square cross-sections and parallel axes, or by regularly-spaced arrangements of cubes, which may also be organized into a hierarchical structure, called an octree [Samet90]. Conceptually, an octree may be constructed from a non-hierarchical decomposition by replacing 2x2x2 arrangements of neighboring cubes that are all in the solid or all in its complement by a single cell representing their union. This process is repeated recursively so as to reduce the total number of cells needed to represent the solid. Although the error allowed by these discretized representations may be significant, especially when their resolution is limited by storage concerns, they are popular, because their simplicity is well-suited to parallel algorithms and hardware support.

规则分解通过等厚切片堆栈,方形截面和平行轴的棱柱形圆柱体,或通过规则排列的立方体排列来逼近固体,立方体也可以组织成称为八叉树的分层结构[Samet90]。 从概念上讲,八叉树可以通过用表示其并集的单个单元格替换全部或全部互补的相邻立方体的2x2x2排列来从非层次分解中构造。 递归地重复此过程,以减少表示实体所需的像元总数。 尽管这些离散表示形式所允许的误差可能很大,尤其是当它们的分辨率受到存储问题的限制时,它们还是很受欢迎的,因为它们的简单性非常适合并行算法和硬件支持。

Rossignac & Requicha Solid Modeling 9

### 4.5.2 Boundary space partition trees 边界空间分区树

Among irregularly-spaced arrangements of cells, the Boundary Space Partition tree (BSP), introduced at the University of North Carolina at Chapel Hill [Naylor90] is one of the most interesting. A BSP recursively splits space into a binary tree, whose leaves correspond to convex polyhedra. A selection of these leaf-cells defines the desired solid. BSP trees were designed originally to speed up hidden-surface elimination in graphics. Although the z-buffer hardware available today on most graphics systems [Rossignac86b] makes BSP trees obsolete for conventional hardware-assisted rendering, BSP trees are still important for low-end software graphics systems (such as video-games), as an auxiliary data structure for computing shadows and other properties, and as an efficient modeling tool for supporting certain fundamental queries on solids. A BSP representation of a polyhedral solid may be obtained by selecting a face of the solid and using its supporting plane to split the solid into two parts. The face is encoded as the root of the BSP tree and the process is repeated to construct its two children nodes, as the BSP trees for the two parts of the solid.

在不规则间隔的单元格排列中,北卡罗来纳大学教堂山分校[Naylor90]引入的边界空间分区树(BSP)是最有趣的之一。 BSP递归地将空间拆分为二叉树,其叶子对应于凸多面体。这些叶细胞的选择定义了所需的固体。 BSP树最初旨在加快图形中隐藏表面的消除。尽管当今大多数图形系统[Rossignac86b]上都有可用的z缓冲区硬件,使得BSP树对于传统的硬件辅助渲染已过时,但是BSP树作为辅助数据对于低端软件图形系统(例如视频游戏)仍然很重要。用于计算阴影和其他属性的结构,以及作为支持实体上某些基本查询的有效建模工具。通过选择实体的面并使用其支撑平面将实体分为两部分,可以获得多面体实体的BSP表示。面被编码为BSP树的根,并重复此过程以构造其两个子节点,作为实体两个部分的BSP树。

# 5 Algorithms and Applications 算法和应用

Algorithms for constructing representations of solids, for converting between them, or for processing these representations in various applications build upon a few fundamental procedures that implement geometric queries and constructions. In the following sub-sections we describe some of these fundamental procedures, and then discuss briefly their use in application algorithms and efficiency issues. Our goal is to provide a high-level overview of typical computations involved in solid modeling. We neither attempt to present the most efficient algorithms nor the (many) details required for their successful implementation.

用于构造实体表示形式,在实体之间进行转换或在各种应用程序中处理这些表示形式的算法均基于一些实现几何查询和构造的基本过程。 在以下小节中,我们描述了一些基本过程,然后简要讨论了它们在应用算法和效率问题中的使用。 我们的目标是概述实体建模中涉及的典型计算。 我们既没有尝试提供最有效的算法,也没有尝试提供成功实施所需的(许多)细节。

## 5.1 Fundamental Queries and Operations 基本查询和操作

The most fundamental query is point membership, which tests whether a point is contained in a given set or not. Point membership classification may be generalized to sets of points such as curves or surface patches. This generalization, called set membership classification, is useful for many applications. Other important algorithms deal with Boolean operations, representation conversion, and intersections. Algorithms and representations are closely intertwined. We illustrate their interdependency by discussing a few algorithms that compute the same mathematical functions (or properties) but operate on different representations.

最基本的查询是点隶属关系,它测试一个点是否包含在给定集中。 点隶属度分类可以推广到点集,例如曲线或曲面补丁。 这种概括称为集合成员资格分类,对许多应用程序很有用。 其他重要算法处理布尔运算,表示转换和交集。 算法和表示紧密相关。 我们通过讨论一些算法来说明它们的相互依赖性,这些算法可以计算相同的数学函数(或属性),但可以在不同的表示形式上进行操作。

### 5.1.1 Point membership classification for BReps BReps的点成员资格分类

The most popular technique for point membership classification (PMC) with respect to solids represented by their boundaries is ray-casting. Construct a half-line L starting from the candidate point X to infinity and then count the parity of the number of times L crosses a face of S. Even parity of the number of line/face intersections implies that X lies outside of the solid. Odd parity implies that X lies inside. (A point on a face is by definition on S.) The treatment of special cases when L hits an edge or a vertex or when it is tangent to one of the supporting surfaces may be avoided by randomly choosing candidate lines L until one is found that does not run into any singular situation.

关于由其边界表示的实体进行点隶属度分类(PMC)的最流行技术是射线投射。 构造一个从候选点X到无穷大的半直线L,然后计算L穿过S面的次数的奇偶性。即使偶数的线/面相交也表示X不在实体之外。 奇校验表示X位于内部。 (根据定义,面上的点是S。)可以通过随机选择候选线L直到找到一条,来避免特殊情况下L碰到边缘或顶点或与支撑面之一相切的特殊情况,不会遇到任何异常情况。

For polyhedral models, each face F of S is checked against L as follows. First compute the intersection I of L with the plane P supporting F. (I is always an isolated point since L was chosen not to be tangent to any of the supporting planes.) Then perform the PMC of I against F in the two-dimensional space of plane P. If I lies in F, then the parity bit is toggled for the PMC of X against S, and the next face of S is considered. (The parity bit is initially set to 0 indicating that X is out of S if no intersection of L with a face is discovered.)

对于多面体模型,如下对L检查S的每个面F。 首先计算L与支撑F的平面P的交点I(由于选择L不与任何支撑平面相切,所以I始终是一个孤立点。)然后在二维方向上对F执行I的PMC。 如果我位于F,则将X的PMC相对于S的奇偶校验位切换,并考虑S的下一个面。 (奇偶校验位最初设置为0,表示如果未发现L与人脸的交集,则X超出S。)

To test whether I lies in F, cast a half-line R in P from I in a random direction that avoids the vertices of F and that is not parallel to any edges of F. Then count the parity of the number of intersections of R with the edges of F.

要测试我是否位于F中,请从I沿P随机地避开F的顶点,并且不平行于F的任何边,在P上投影R的半线。然后计算R的交点数的奇偶性 与F的边缘。

The complexity of this process grows with the number of faces in S. Consider for example the case of a simple sphere S crudely approximated with 288 flat faces with a 15 degree angle between two adjacent rectangular faces. Point membership classification against S requires 282 line-plane intersection calculations in 3D, and over a thousand line-line intersection calculations in 2D. Auxiliary data structures that accelerate PMC [Hoffmann89, Horn89] may help when the associated construction costs are amortized over a large number of candidate points.

该过程的复杂性随S中的面数而增加。例如,考虑一个简单球体S粗略地近似为288个平面的情况,两个相邻矩形面之间的夹角为15度。 针对S的点隶属度分类需要在3D中进行282条线-平面相交计算,在2D中需要进行一千多条线-线相交计算。 当在大量的候选点上分摊相关的建造成本时,可加速PMC的辅助数据结构[Hoffmann89,Horn89]可能会有所帮助。

PMC against BRep models involving a larger number of curved surfaces is typically performed using a variation of the raycasting approach outlined above, which requires intersecting half-lines with surfaces in 3D, and intersecting lines with facebounding curves in the 2D parametric spaces of the curved surfaces.

涉及大量曲面的PMC针对BRep模型通常是使用上述光线投射方法的一种变体来执行的,该方法要求在3D中将半线与曲面相交,在曲面的2D参数空间中与面边界曲线相交。

Although many subtleties were left out, this discussion shows that even the most basic computations in a solid modeler are not trivial.

尽管省略了许多微妙之处,但该讨论表明,即使是实体建模器中最基本的计算也不是简单的。

Rossignac & Requicha Solid Modeling 10

### 5.1.2 Point membership classification for CSG CSG的点成员资格分类

Divide and conquer is the natural design paradigm for CSG algorithms. The standard point membership classification algorithm for CSG representations traverses the CSG tree by recursive descent. When the recursion reaches the primitives, the point to be classified is tested against them.

分而治之是CSG算法的自然设计范例。 用于CSG表示的标准点成员资格分类算法通过递归下降遍历CSG树。 当递归到达基元时,将针对它们测试要分类的点。

Point/primitive classification is simple if the primitives are defined in a natural position (e.g. when the primitive’s axes are aligned with the principal axes) and then transformed through a rigid body motion. Classifying the point against the transformed primitive is done by applying the inverse of the transformation to the point, and classifying the result against the primitive in its original position. When the primitive is defined by an algebraic or analytical inequality (for example, a sphere is defined by a second degree inequality), it suffices to substitute the point’s coordinates into the inequality and evaluate its sign. More complex primitives may involve intersections of sets defined by inequalities, or more general point containment tests.

如果将原语定义在自然位置(例如,当原语的轴与主轴对齐时),然后通过刚体运动进行转换,则点/原语分类很简单。 通过将变换的逆应用于该点,并将结果相对于图元的原始位置进行分类,可以将点与转换后的图元进行分类。 当图元由代数或解析不等式定义(例如,球体由二次度不等式定义)时,只需将点的坐标替换为不等式并评估其符号即可。 更复杂的图元可能涉及由不等式定义的集合的交集,或更复杂的点包含测试。

Once point/primitive classification results are known, they are combined through the original Boolean expression that defines the CSG graph. Special processing based on neighborhood combinations may be necessary for points that lie on boundaries of several primitives [Requicha85]. A point’s neighborhood is the intersection of the solid with a small ball around the point. If the neighborhood is full, the point lies inside the solid, if it is empty, the point lies outside, otherwise, the point is on the boundary of the solid. The complexity involved in computing and testing the neighborhood depends on the nature, number, and orientation of the surfaces involved.

一旦知道了点/原始分类结果,它们就会通过定义CSG图的原始布尔表达式进行组合。 对于位于几个图元边界上的点,可能需要基于邻域组合的特殊处理[Requicha85]。 点的邻域是实体与围绕该点的小球的交点。 如果邻域已满,则该点位于实体内,如果为空,则该点位于实体外,否则,该点位于实体的边界上。 计算和测试邻域所涉及的复杂性取决于所涉及曲面的性质,数量和方向。

When the primitive faces that contain the point are subsets of a single surface, the neighborhood may be represented by two bits, each indicating whether there is material on the corresponding side of the surface. Combining neighborhoods according to the regularized Boolean operations amounts to combining these bits with the corresponding logical operations (OR for regularized union, AND for regularized intersection, NOT AND for regularized difference). The initial values of these neighborhood bits for surface points are obtained from the face orientation for each primitive whose boundary contains the point. If the two bits are set, the point is inside. If the two bits are off, the point is outside. If the bits differ, the points lies on a face of the solid. Figure 7 illustrates these cases in a 2D example.

当包含点的基本面是单个表面的子集时,可以用两个位表示邻域,每个位指示在表面的相应侧面上是否存在材质。 根据正则化布尔运算来组合邻域等于将这些位与相应的逻辑运算进行组合(对于正则并集,或对于正则交集,对于与正则差,则不是与)。 这些边界点的邻域位的初始值是从边界包含该点的每个图元的面方位获取的。 如果设置了两位,则该点在内部。 如果两个位都关闭,则该点在外面。 如果位不同,则点位于实体的面上。 图7以2D示例说明了这些情况。



![1571901456033](\AppData\Roaming\Typora\typora-user-images\1571901456033.png)

Figure 7: The solid S (bottom right) was defined in CSG by S=(A+B)-C. Points 1-4 may be evaluated using a 2-bit neighborhood. The neighborhoods of point 1 with respect to the primitives A, B and C are 01, 00, and 01, if we assign the first bit to the left side of the vertical line through the point and the second bit to the right side of that line. Combining each bit through the logical expression “(01 OR 00) AND NOT 01” yields 00 and thus point 1 lies out of S. The primitive neighborhoods for points 2 are 01, 00, and 00 and their combination yields 01. Indeed point 2 lies on S. The primitive neighborhoods for point 3 are 10, 01, and 00, and their combination is 11, making point 3 an interior point of S. The primitive neighborhoods for point 4 are 00, 01, and 10 (assigning the first bit to the side above the horizontal line and the second bit to the side below the line). Their logical combination yields 01, and hence the point lies on S. Evaluating the neighborhood of point 5 requires considering four sectors defined by the horizontal and vertical lines passing through the point. Assigning one bit to each of these sectors in clockwise order starting from the upper-right sector yields for 0011, 0100, 1001 for the three primitives and 0110 for S. Consequently, point 5 lies on S.

图7:在CSG中,固体S(右下)的定义为S =(A + B)-C。可以使用2位邻域评估点1-4。如果我们通过该点将第一位分配给垂直线的左侧,而将第二位分配给该点的右侧,则点1相对于图元A,B和C的邻域为01、00和01。线。通过逻辑表达式“(01 OR 00)AND NOT 01”组合每个位,得出00,因此点1位于S之外。点2的原始邻域为01、00和00,它们的组合得出01。的确,点2位于S上。点3的原始邻域为10、01和00,它们的组合为11,使点3成为S的内部点。点4的原始邻域为00、01和10(分配第一个位在水平线上方,第二位在水平线下方)。它们的逻辑组合得出01,因此该点位于S上。评估点5的邻域需要考虑由穿过该点的水平线和垂直线定义的四个扇区。从右上角扇区开始,按顺时针顺序为这些扇区中的每个扇区分配一个比特,对于三个图元,其结果为0011、0100、1001,对于S,结果为0110。因此,点5位于S上。

Rossignac & Requicha Solid Modeling 11

When the primitive faces containing point P lie on two or more supporting surfaces that intersect at a common curve passing through P, a curve neighborhood is used to classify P. A sufficiently small disk around P in the plane orthogonal to the curve is divided by the supporting surfaces into sectors, analogous to those in a pie chart. Each sector is classified against the primitives, and its classifications are simple logical values which may be combined according to the Boolean expression. If all sectors are full, the points lies in the solid. If all sectors are empty, the point is out. Otherwise the point lies on the solid. The most delicate computation in this process is the segmentation of the curve neighborhood, because it involves computing a circular order of surfaces around their common edge. The process may be numerically unreliable and mathematically challenging, if the surfaces are non-planar and are not simple quadrics.

当包含点的基本面是单个表面的子集时,可以用两个位表示邻域,每个位指示在表面的相应侧面上是否存在材质。 根据正则化布尔运算来组合邻域等于将这些位与相应的逻辑运算进行组合(对于正则并集,或对于正则交集,对于与正则差,则不是与)。 这些边界点的邻域位的初始值是从边界包含该点的每个图元的面方位获取的。 如果设置了两位,则该点在内部。 如果两个位都关闭,则该点在外面。 如果位不同,则点位于实体的面上。 图7以2D示例说明了这些情况。

### 5.1.3 Curve membership classification 曲线成员分类

The notion of membership classification can be generalized as follows. Given a solid S and a candidate set X, set membership classification partitions X into three subsets: Xi , the subset X in the interior of S, Xb, the subset of X on the boundary of S, and Xo, the subset of X in the interior of the complement of S [Tilove80]. Membership classification for curves and surfaces with respect to solids is used in many geometric algorithms.

成员资格分类的概念可以概括如下。 给定一个实心S和一个候选集X,集合成员资格分类将X划分为三个子集:Xi,S内部的子集X,Xb,S边界上的X的子集和Xo,X in的子集。 S的补码的内部[Tilove80]。 关于实体的曲线和曲面的隶属度分类在许多几何算法中使用。

A simple two-step strategy can be used to classify a line or curve X with respect to a solid S represented either by a BRep or CSG. (There are other, more efficient approaches to curve/solid classification.) In the first step, the curve is segmented into subsets that have uniform classification with respect to S. Then, the classification for each segment is determined, for example by classifying its mid point using the PMC algorithms discussed earlier. Which PMC algorithm to use depends on whether the solid is represented by a BRep or CSG. The first step also depends on the solid’s representation. If the solid is given by a BRep, we compute the isolated intersection points of X with all the faces, edges, and vertices of S and represent them in terms of the corresponding parameter values of some parameterization of X. (Cases where X is contained in a surface that supports a face of S or overlaps with a curve that supports an edge of S need not be processed.)

相对于由BRep或CSG表示的实体S,可以使用简单的两步策略对直线或曲线X进行分类。 (还有其他更有效的曲线/实体分类方法。)在第一步中,将曲线分割为相对于S具有统一分类的子集。然后,例如,通过将其分类来确定每个分类的分类。 使用前面讨论的PMC算法的中点。 使用哪种PMC算法取决于实体是由BRep还是CSG表示。 第一步还取决于实体的表示形式。 如果实体是由BRep给出的,则我们将计算X与S的所有面,边和顶点的孤立交点,并根据X的某些参数化的相应参数值来表示它们。 支撑S的表面或与支撑S的边缘的曲线重叠的表面中的曲面不需要进行处理。)

Sorting these parameter values defines segments of X that have uniform classification with respect to S. (The classification of X can only change at the computed intersection points.)

对这些参数值进行排序将定义X的分段,这些分段相对于S具有统一的分类。(X的分类只能在计算出的交点处改变)。

If the solid is represented in CSG, in the first step we intersect the curve with the faces, edges and vertices of all the primitives, and sort the parameter values of the intersection points to create the initial segmentation.

如果实体用CSG表示,则第一步,我们将曲线与所有图元的面,边和顶点相交,并对交点的参数值进行排序以创建初始分割。

### 5.1.4 Boolean Operations 布尔操作

Consider a solid S defined by a regularized Boolean operation on two argument solids A and B, both defined in CSG. The boundary of S may be computed by subdividing the boundaries of A and B at their intersection and by discarding the appropriate portions. For example, if S=A+B, we discard the portions of the boundary of A inside B and vice versa. This process is called boundary merging.. If the boundaries of A and B are not available, they may be derived recursively through an incremental boundary evaluation by merging boundaries up the tree, starting at the primitives. The BRep of S can also be obtained directly from its CSG by a non incremental boundary evaluation, process.

考虑通过对两个自变量实体A和B进行正则布尔运算定义的实体S,两者均在CSG中定义。 S的边界可以通过在A和B的交点处对其进行细分并丢弃适当的部分来计算。 例如,如果S = A + B,我们将丢弃B内A的边界部分,反之亦然。 此过程称为边界合并。如果A和B的边界不可用,则可以通过从树图元开始将边界合并到树上,通过增量边界评估递归地得出它们。 S的BRep也可以通过非增量边界评估过程直接从其CSG获得。

We describe briefly a non-incremental boundary evaluation algorithm, to illustrate the issues. Typically, faces of CSG solids are represented in terms of their supporting surface and their bounding edges. To compute the edges of a CSG solid S, we apply the generate and test paradigm. First, compute the intersection curves between all pairs of surfaces that support primitive faces. Then partition these curves into subsets that are in the interior of S, in its complement, or on its boundary by using curve/solid membership classification algorithms. Segments with a curve neighborhood that is neither empty nor full form the edges of the solid. The details of this process are illustrated in [Banerjee96] for CSG models composed of polyhedral primitives. First a tentative set of lines if generated as the intersection of each possible pair of non-parallel planes taken from the set P of planes that support the faces of the primitives of the CSG definition of S. Each line L is classified against S as follows. First, separate the planes of P into three sets: C, the planes containing L; I, the planes intersecting L at a single point, and O the planes disjoint from L. Then use the intersections with planes of I to split L into segments. Split the neighborhood of L into sectors defined by the planes of C. The classification of each sector for each segment may be represented by a single bit. Because S and its primitives are finite, the classification of any given sector of a semi-infinite segments of L with respect to the primitives and nodes of the CSG tree of S is readily known and may be stored by associating a bit with each node. Moving from one sector to an adjacent sector in the same segment or in an adjacent segment corresponds to the traversal of a single supporting plane, and therefore alters the classification bit of a single primitives or of several primitives that have faces supported by this plane. Changing this classification bit and updating the CSG tree may or may not alter the classification bit of S. By traversing all these sectors from neighbor to neighbor and by storing the associated classification bits with the sectors, we compute the neighborhood of each segment. Edges with full or empty neighborhood are discarded. Edges with identical neighborhoods are merged.

我们简要描述了一种非增量边界评估算法,以说明问题。通常,CSG实体的面以其支撑面和边界边缘表示。为了计算CSG实体S的边缘,我们应用了生成和测试范例。首先,计算支持基本面的所有成对曲面之间的相交曲线。然后使用曲线/实体隶属度分类算法将这些曲线划分为S内部,其补数或边界上的子集。既不为空也不为完整的曲线邻域的线段形成了实体的边缘。 [Banerjee96]对由多面体基元组成的CSG模型进行了详细说明。首先,如果从支持P的S组CSG定义的图元的平面的平面P中获取的每对可能的非平行平面对的交点生成,则生成一组临时线。每条线L如下针对S进行分类。首先,将P的平面分为三组:C,包含L的平面; I是与L在单个点处相交的平面,O是与L不相交的平面。然后使用与I平面相交的平面将L分割成段。将L的邻域划分为由C平面定义的扇区。每个段的每个扇区的分类可以用单个位表示。因为S及其基元是有限的,所以相对于S的CSG树的基元和节点,L的半无限段的任何给定扇区的分类都是众所周知的,并且可以通过将位与每个节点相关联来存储。在同一段或相邻段中从一个扇区移动到相邻扇区对应于单个支撑平面的遍历,因此更改了单个图元或具有该平面所支撑面的几个图元的分类位。更改此分类位并更新CSG树可能会或可能不会更改S的分类位。通过从邻居到邻居遍历所有这些扇区并通过将相关的分类位与扇区一起存储,我们可以计算每个段的邻域。邻域满或空的边将被丢弃。具有相同邻域的边被合并。

By keeping track of the association between curves and surfaces, and between vertices and segments, a full BRep may be inferred form the result of the curve classification process. Edges are chained into loops which are used to trim the solid’s faces. The representation of the loops may be simplified by merging adjacent curve segments, when no more than two segments share a vertex. Alternatively, the faces of CSG solids may be represented as the intersection between a supporting surface and a 3D trimming volume, whose CSG expression may be easily derived from the CSG of the entire solid [Rossignac96].

通过跟踪曲线和曲面之间以及顶点和线段之间的关联,可以从曲线分类过程的结果中推断出完整的BRep。 边链接成循环,用于修剪实体的面。 当不多于两个线段共享一个顶点时,可以通过合并相邻的曲线线段来简化循环的表示。 备选地,CSG实体的面可以表示为支撑表面和3D修剪体积之间的交点,其CSG表达式可以很容易地从整个实体的CSG导出[Rossignac96]。

Rossignac & Requicha Solid Modeling 12

Other algorithms for boundary evaluation and merging typically use also the generate and test paradigm, but may be articulated around vertices, edges or faces (see [Mantyla86] for an example and [Requicha85] for further references). Boolean operation algorithms are among the most complex in solid modeling. They also are among the most difficult to implement reliably, in the presence of round-off errors.

其他用于边界评估和合并的算法通常也使用生成和测试范式,但可以围绕顶点,边或面进行铰接(有关示例,请参见[Mantyla86],有关其他参考,请参见[Requicha85])。 布尔运算算法是实体建模中最复杂的算法。 在存在舍入错误的情况下,它们也是最难可靠实现的。

### 5.1.5 Representation Conversion 表示转换

Boundary evaluation is an important example of representation conversion, from CSG to BRep. The inverse process of computing semi-algebraic expressions for solids represented by their boundary is also very important, because it provides algorithms for maintaining consistency in multi-representation systems. When a BRep is edited, the modifications must be reflected on the associated CSG. The 2D case is fairly well understood [Shapiro91]. Algorithms for converting incomplete polyhedral boundary representations into a BSP tree have been proposed in [Murali97]. These algorithms are very useful for disambiguating models represented by incomplete boundaries where faces-face adjacency may have been perturbed by numeric approximation.

边界评估是从CSG到BRep的表示转换的重要示例。 计算由边界表示的实体的半代数表达式的逆过程也非常重要,因为它提供了在多表示系统中保持一致性的算法。 编辑BRep时,修改必须反映在关联的CSG上。 2D情况相当好理解[Shapiro91]。 在[Murali97]中提出了将不完整的多面体边界表示转换为BSP树的算法。 这些算法对于消除不完整边界所代表的模型非常有用,在不完整边界中,人脸-脸部邻接关系可能已受到数值逼近的干扰。

Other representation conversion algorithms are useful as well. For example, point membership classification for points on a regular grid can be used to construct a spatial enumeration approximation for a solid, which in turn facilitates the computation of the solid’s mass and moments of inertia [Lee82]. Conversion from CSG or BRep to octree format is even more useful for massproperty calculations, and can be done also through membership classification algorithms.

其他表示转换算法也很有用。 例如,规则网格上点的点隶属度分类可用于构造实体的空间枚举近似值,这反过来又便于计算实体的质量和惯性矩[Lee82]。 从CSG或BRep到octree格式的转换对于质量属性计算更为有用,并且也可以通过成员资格分类算法来完成。

As another example, conversion into a cell decomposition in which all the cells are “slices” perpendicular to a given direction is needed to drive rapid prototyping machines. It can be accomplished by classifying a set of parallel planes with respect to a solid. The portions of the planes inside the solid are the desired slices.

作为另一个示例,需要转换为细胞分解,其中所有细胞都是垂直于给定方向的“切片”,以驱动快速成型机。 可以通过对一组平行平面进行分类来实现。 实体内部的平面部分是所需的切片。

### 5.1.6 Curve and Surface Intersections 曲线曲面相交

The curve/solid classification algorithms discussed earlier are an example of computations that require intersecting a curve with surfaces of composite or primitive solids. Boolean operation algorithms also need to intersect surfaces with other surfaces. Curve and surface intersections arise in many other geometric algorithms.

前面讨论的曲线/实体分类算法是需要将曲线与复合或原始实体的曲面相交的计算示例。 布尔运算算法还需要使曲面与其他曲面相交。 曲线和曲面相交出现在许多其他几何算法中。

Suppose that we are given a curve with parametric equations x=x(u), y=y(u), z=z(u), plus an algebraic surface with implicit equation f(x,y,z)=0. Curve/surface intersection amounts to solving for the roots of the system of four equations: x=x(u), y=y(u), z=z(u), and f(x,y,z)=0.

假设给定一条曲线,其参数方程为x = x(u),y = y(u),z = z(u),以及带隐式方程为f(x,y,z)= 0的代数曲面。 曲线/曲面相交等于求解四个方程组的根:x = x(u),y = y(u),z = z(u)和f(x,y,z)= 0。

This can be done by substituting the parametric equations in the implicit equation to obtain g(u)=f(x(u), y(u), z(u))=0 and solving this equation for u. Except in very simple cases the solution can only be found numerically.

可以通过将参数方程式替换为隐式方程式来获得g(u)= f(x(u),y(u),z(u))= 0并为u求解该方程式。 除非在非常简单的情况下,否则只能通过数值找到解决方案。

This simple example shows that intersection problems essentially consist of root finding. Much is known about this area, but the problem of designing algorithms that are both robust and efficient is still largely open. For surveys and representative research see [Patrikalakis93, Krishnan97].

这个简单的例子表明,相交问题实质上是由寻根组成的。 关于这一领域的知识很多,但是设计既健壮又高效的算法的问题仍然很大。 有关调查和代表性研究,请参见[Patrikalakis93,Krishnan97]。

## 5.2 Applications 应用

Applications that involve analysis of models are relatively well developed. Algorithms are available for generating displays of solids in many styles and degrees of realism, for kinematic simulation, for the evaluation of mass properties, for collision detection in static environments, and so on. For example, graphics applications are flourishing in the entertainment industry. On the other hand, problems such as design and planning, which involve synthesis, are much less understood. We speculate that the difficulties arise because synthesis algorithms must reason about space, which is notoriously hard to do computationally.

涉及模型分析的应用程序相对完善。 算法可用于生成多种样式和逼真的实体显示,运动学模拟,质量特性评估,静态环境中的碰撞检测等。 例如,图形应用在娱乐业中蓬勃发展。 另一方面,涉及综合的设计和计划等问题则鲜为人知。 我们推测出现困难的原因是合成算法必须对空间进行推理,而众所周知这在计算上很难做到。

Nevertheless, applications such as feature recognition for machining planning [Vandenbrande93, Han97] dimensional inspection planning [Spyridi90, Spyridi94] and robot path planning [Latombe91] are getting close to industrial usability.

尽管如此,诸如机加工计划[Vandenbrande93,Han97]尺寸检查计划[Spyridi90,Spyridi94]和机器人路径计划[Latombe91]的特征识别等应用已接近工业实用性。

Most of these application algorithms use extensively the fundamental queries and constructions described above. For example, mass property calculation for CSG solids typically involves either line/solid classification or CSG to octree conversion. And feature recognition and accessibility analysis for inspection planning require Boolean operation capabilities.

这些应用程序算法中的大多数都广泛使用上述基本查询和构造。 例如,CSG实体的质量属性计算通常涉及线/实体分类或CSG到八叉树的转换。 用于检查计划的特征识别和可访问性分析需要布尔运算功能。

A growing number of solid modeling applications focus not on the design of the geometry of the individual components, but on their exploitation for the interactive design and inspection of manufacturing processes (assembly plans, NC cutter path generation) and of spatial arrangements (manufacturing cell layout, accessibility to control instruments in aircrafts, or urban planing.

越来越多的实体建模应用程序不将重点放在单个组件的几何设计上,而是将其用于交互式设计和检查制造过程(组装计划,NC刀具路径生成)和空间布置(制造单元布局) ,飞机控制工具的可及性或城市规划。

## 5.3 Efficiency Enhancements 效率提升

Set membership classification and CSG to BRep conversion algorithms perform a very large amount of computation when compared to their output sizes. Many of these algorithms are based on the generate-and-test paradigm, and spend much of their time generating, testing, and rejecting. Performance-enhancement methods play a crucial role in eliminating a large fraction of Rossignac & Requicha Solid Modeling 13 unnecessary tests. In essence, these methods ensure that entities are compared only when there is a good chance that they may interact.

与它们的输出大小相比,集成员资格分类和BSG的CSG转换算法执行大量计算。 这些算法中的许多算法都是基于“生成和测试”范例,并且花费了大量时间进行生成,测试和拒绝。 性能增强方法在消除大部分不必要的测试中起着至关重要的作用。 从本质上讲,这些方法确保仅在有很大可能的情况下才比较实体
相互作用。

Two of the widely used efficiency-enhancement techniques are plane sweep algorithms from computational geometry (which generalize the earlier scan line algorithms developed in computer graphics), and grid-based spatial directories. A plane sweep algorithm maintains a list of active entities that can potentially interact, and updates the list incrementally, as the plane advances in its sweep of the whole space. Only active entities need to be compared. A spatial directory decomposes the space into cells (either of constant size or arranged hierarchically) and associates with each cell the entities that intersect it. Only those entities associated with the same cell are compared and processed.

广泛使用的效率增强技术中的两种是计算几何学中的平面扫描算法(它概括了计算机图形学中开发的较早的扫描线算法)和基于网格的空间目录。 平面扫描算法会维护可能交互的活动实体的列表,并随着平面在整个空间中的扫描前进而递增地更新列表。 仅需要比较活动实体。 空间目录将空间分解为单元(大小不变或按层次排列),并将与之相交的实体与每个单元相关联。 仅比较和处理与同一单元格关联的那些实体。

# 6 Parameters, Constraints and Features 参数化,约束和特征

Regardless of the representation scheme used, building and editing a model for a complicated solid is non-trivial. Finding the size and position parameters that are needed to ensure that geometric entities are in desired relationships often is quite difficult. And so is ensuring that such relationships are preserved when an object is edited. In addition, the primitives provided by the representation methods discussed earlier tend to be relatively low level, and not directly connected with the application domain. The representational facilities discussed in the following subsections address these problems.

不管使用哪种表示方案,为复杂的实体建立和编辑模型都是很简单的。 通常很难找到确保几何实体处于所需关系所需的尺寸和位置参数。 因此,确保在编辑对象时保留此类关系。 另外,由前面讨论的表示方法提供的原语往往是相对较低的级别,并且不直接与应用程序域连接。 以下小节中讨论的代表性设施解决了这些问题。

## 6.1 Parametric models 参数模型

The size and position parameters used to instantiate the primitives needed to represent an object provide a natural parameterization for the object. However, there is no guarantee that a change of parameter values will produce an object that is valid and consistent with the designer’s intent. The first of these problems can be solved easily by using a CSG-based parameterization, which ensures that an instance of a parametric solid model is always valid. The second problem is more pernicious. Some of the design constraints may be expressed by substituting the parameters of the primitives or of the transformations by symbolic parameter expressions. This approach was first demonstrated in the 1970’s with the PADL-2 solid modeling system [Brown82], and is now in widespread use. In addition to symbolic expressions, Rossignac proposed to link CSG parameters to procedures specified by the user in terms of geometric constraints [Rossignac86b]. Each constraint corresponds to a transformation that brings the host surface of a primitive face into a specified relationship with the host surface of a primitive not affected by the transformation. These approaches rely on the user for producing and sorting a sequence of steps that evaluate symbolic expressions or that compute transformations to achieve the desired effects [Rossignac88b]. The user’s actions are akin to the writing of a macro that takes some input parameters and produces the desired solid. The macro defines a family of solids, also called a “parametric solid model”. The user is responsible for designing the correct macro, ensuring that executing such a sequence for reasonable values of the input parameters produces a solid that meets the designer’s intent. This is not always easy to achieve, because the required symbolic expressions may be hard to find, and a transformation may violate a previouslyachieved constraint.

用于实例化表示对象的原语的大小和位置参数为对象提供了自然的参数化。但是,不能保证更改参数值将产生一个有效且符合设计者意图的对象。通过使用基于CSG的参数化可以轻松解决第一个问题,这可以确保参数实体模型的实例始终有效。第二个问题更加有害。可以通过用符号参数表达式替换基元或变换的参数来表达某些设计约束。这种方法最早是在1970年代使用PADL-2实体建模系统[Brown82]进行演示的,现已广泛使用。除了符号表达式,Rossignac还建议将CSG参数链接到用户根据几何约束指定的过程[Rossignac86b]。每个约束对应于一个转换,该转换将基本面的主体表面与不受该转换影响的基本体的主体表面形成指定的关系。这些方法依赖于用户来生成和排序评估符号表达式或计算转换以实现所需效果的步骤序列[Rossignac88b]。用户的动作类似于编写带有一些输入参数并生成所需实体的宏。宏定义了一个实体族,也称为“参数实体模型”。用户负责设计正确的宏,以确保为输入参数的合理值执行这样的序列会产生符合设计者意图的实体。这并非总是容易实现的,因为所需的符号表达式可能很难找到,并且转换可能违反先前实现的约束。

## 6.2 Variational geometry 可变几何

In contrast, the variational geometry approach does not require the user to define an order for constraint-achieving operations, nor even to define all the constraints. A user can specify symbolic expressions that define relations between two or more parameters. In addition, the system infers automatically bi-directional constraints from all singular situations (such as parallelism, orthogonality or tangency) that are detected on a nominal model. A constraint solver adjusts the model to meet all the constraints simultaneously. This process may involve numeric iterations to solve the corresponding system of simultaneous, nonlinear equations. Because the constraints, such as edge dimensions or angles between faces, are typically expressed in terms of boundary entities, and because it is difficult to relate these to the input parameters of a CSG model, variational geometry is typically used in conjunction with a parameterized boundary representation. The variational geometry approach is popular for 2D drafting and for designing solids that are extruded from 2D contours, but its application to more general 3D shapes still suffers from several drawbacks. Performance problems are due to the large number of nonlinear equations in many variables that must be solved simultaneously. A small change in one parameter may lead the iterative techniques to converge to a local minimum that is significantly different from the previous configuration, and surprise or confuse the user. In an over-constrained situation, a user will have trouble deciding which constraints to relax for the system to converge to a solution. Finally, users may create invalid boundary representations, because no practical techniques exist for computing the bounds on parameter values for which the model remains valid.

相反,可变几何方法不需要用户定义约束实现操作的顺序,甚至不需要定义所有约束。用户可以指定定义两个或多个参数之间关系的符号表达式。此外,系统会从在名义模型上检测到的所有奇异情况(例如,并行性,正交性或相切性)自动推断出双向约束。约束求解器调整模型以同时满足所有约束。此过程可能涉及数值迭代,以求解相应的联立非线性方程组。由于约束(例如边尺寸或面之间的角度)通常用边界实体表示,并且由于很难将这些约束与CSG模型的输入参数相关联,因此通常将变分几何与参数化边界结合使用表示。变分几何方法在2D绘图和从2D轮廓拉伸的实体的设计中很流行,但是将其应用于更通用的3D形状仍然存在一些缺点。性能问题是由于许多变量中的大量非线性方程式必须同时求解。一个参数的微小变化可能导致迭代技术收敛到与先前配置明显不同的局部最小值,并使用户感到惊讶或困惑。在过度约束的情况下,用户将难以确定要放松哪些约束以使系统收敛到解决方案。最后,用户可能会创建无效的边界表示,因为不存在用于计算模型保持有效的参数值范围的实用技术。

## 6.3 Features 特征

Features provide a higher level and domain-targeted vocabulary for specifying shape-creating operations, and for identifying the model’s elements from which the parameters of symbolic expressions or manufacturing plans are to be derived.

功能提供了更高级别和针对特定领域的词汇,用于指定形状创建操作以及用于识别要从中导出符号表达或制造计划参数的模型元素。

Models may be constructed by a sequence of operations that create additive or subtractive volumetric features. The nature of these features may vary widely with the application domain. Volumetric features may be viewed as higher-level parameterized Rossignac & Requicha Solid Modeling 14 primitives that are relevant to a specific domain. For example, dove-tail slots, profiled pins, blends, or chamfered holes are useful features for machined parts. Their creation sequence and parameters can be captured in a CSG representation with union and difference operations, and feature leaves. However, the geometry of a feature created by one operation may be partially or totally obliterated by a subsequent operation [Rossignac90]. Consequently, these design features cannot be used directly for analysis or other computations without a verification step, or conversion into a standard (i.e., non feature-based) model.

可以通过一系列创建加法或减法体积特征的操作来构建模型。 这些功能的性质可能会随着应用程序领域的不同而变化。 体积特征可被视为与特定领域相关的高级参数化Rossignac和Requicha实体建模14个原语。 例如,燕尾槽,异型销,混纺或倒角孔是加工零件的有用功能。 它们的创建顺序和参数可以在具有联合和差异操作以及特征叶的CSG表示中捕获。 但是,由一个操作创建的特征的几何形状可能会被后续操作部分或全部消除[Rossignac90]。 因此,如果没有验证步骤或将其转换为标准(即基于非特征的)模型,这些设计特征将无法直接用于分析或其他计算。

A feature-based representation can be converted into a BRep via a general purpose CSG-to-Boundary conversion. However, many systems provide the user with immediate feedback based on direct modification of the boundary. This is fast, but not without danger. When tweaking the parameters of one feature, the faces that bound the feature may intersect faces of other features in unanticipated ways. Also, if the volume of an additive feature overlaps the volume of a subtractive feature, precedence information is needed to decide whether to keep or remove the intersection of the two features. This amount to using a CSG-like structure for evaluating the boundary of the resulting solid.

可以通过通用CSG到边界的转换将基于特征的表示转换为BRep。 但是,许多系统基于边界的直接修改为用户提供即时反馈。 这很快,但并非没有危险。 调整一个要素的参数时,绑定该要素的面可能会以意想不到的方式与其他要素的面相交。 同样,如果加法要素的体积与减法要素的体积重叠,则需要优先级信息来确定是保留还是删除这两个要素的交集。 这相当于使用类似于CSG的结构来评估所得固体的边界。

Because feature faces may be altered, split into several connected components, or even destroyed by the creation of other features, it is important to provide mechanisms for connecting the feature entities with the corresponding faces of the resulting solid. Furthermore, the user or an automatic feature-extraction process may identify collections of faces or volumes in the solid or in its complement as features that are important for further design activities or for downstream applications, but that do not correspond to a single feature creation operation. For example, adding two ribs to a solid may create a slot feature, which is a more appropriate abstraction for manufacturing process planning than the ribs. Techniques developed by Requicha and his students at the University of Southern California address issues of automatic feature conversion and dependencies between converted and original features [Vandenbrande93, Han97].

由于特征面可能会更改,拆分为几个相连的组件,甚至可能因创建其他特征而破坏,因此提供将特征实体与所得实体的相应面连接的机制非常重要。 此外,用户或自动特征提取过程可以将实体或其补充中的面或体积的集合标识为对进一步的设计活动或下游应用很重要但不与单个特征创建操作相对应的特征 。 例如,在实体上添加两个肋可以创建槽特征,这比肋更适合用于制造工艺规划。 Requicha和他在南加州大学的学生开发的技术解决了自动要素转换以及转换后的要素与原始要素之间的依存关系的问题[Vandenbrande93,Han97]。

In essence, the input (or design) features are converted either manually or automatically into other, application-dependent features. The challenge is to capture the results of these conversions in a form that persists when the parameters of the model are changed. Otherwise, all user interactions or annotations with the converted features are lost and must be re-entered manually after each parameter modification or engineering change to the geometry of the model.. The difficulty of this challenge may be illustrated by considering two versions, S and S’, of the same CSG model, although with different parameter values. Which face F’ of S’ corresponds to a given face F of S? Because the boundary of a CSG solid is a subset of the boundaries of its primitives, F may be associated with the faces of CSG primitives whose intersection with F is two dimensional and F’ may be recovered as the contributions to S’ of the corresponding primitive faces, given the CSG parameters for S’. This approach suffers from three difficulties: (1) there may be several primitive faces in S that overlap with F, (2) some of these faces may not be responsible for contributing F, and (3) F may only be one connected component of the contribution of a set of primitive faces in the CSG model of S. The first two difficulties have been addressed by Rossignac using an extension of the active zone [Rossignac89] invented by Rossignac and Voelcker, which provides a simple CSG expression for the region of space where the boundary of a CSG primitive contributes to the boundary of the solid. The third difficulty may be addressed by using Boolean or topological filters to distinguish one connected component of the boundary of a solid from another. Except for limited situations, no automatic technique is currently available for deriving such filters.

本质上,输入(或设计)功能可以手动或自动转换为其他与应用程序相关的功能。面临的挑战是以一种更改模型的参数时仍然存在的形式捕获这些转换的结果。否则,所有具有已转换功能的用户交互或注释都将丢失,必须在每次对模型的几何参数进行修改或工程更改后手动重新输入。通过考虑两个版本S和S可以说明这一挑战的难度。 S',具有相同的CSG模型,但参数值不同。 S’的哪个面F’对应于S的给定面F?因为CSG实体的边界是其图元边界的子集,所以F可以与CSG图元的面相关联,CSG图元与F的交点是二维的,并且F'可作为对应图元对S'的贡献而恢复。给定S'的CSG参数。这种方法遇到三个困难:(1)S中可能有几个与F重叠的原始面,(2)其中一些面可能不构成F,(3)F可能只是F的一个连接部分。 Rossignac通过使用Rossignac和Voelcker发明的活动区域[Rossignac89]的扩展解决了前两个困难,这为S的CSG模型提供了一个简单的CSG表达式。 CSG基本体边界有助于实体边界的空间。第三个困难可以通过使用布尔或拓扑过滤器来解决,以将实体边界中的一个连接部分与另一个部分区分开。除少数情况外,目前尚无自动技术可用于导出此类滤波器。

# 7 User interfaces 用户界面

A solid modeler’s user interface defines the skills required to use the modeler and has a major impact on the users’ effectiveness. Early solid modeling systems were reserved to CAD experts in the aerospace and automotive industries and were focused on providing designers with powerful and robust design operations and analysis. Although much progress is still needed on these fronts, considerable research and development efforts have been recently re-focused on improving the ease-of-use for non-experts and the productivity of expert designers. Indeed, labor is the dominant cost of solid modeling and many professionals involved in the design cycle are not CAD experts. Furthermore, new easy-to-use “light-weight” solid modelers are making inroads in nontraditional areas (such as electronic components or entertainment) where accessibility to non-specialists and rapid design cycles are more important than precision.

可靠的建模者的用户界面定义了使用建模者所需的技能,并且对用户的有效性产生重大影响。 早期的实体建模系统是为航空航天和汽车行业的CAD专家保留的,专注于为设计师提供强大而强大的设计操作和分析功能。 尽管在这些方面仍需要很多进步,但是最近大量的研究和开发工作重新集中在提高非专家的易用性和专家设计人员的生产率上。 确实,劳动力是实体建模的主要成本,并且许多参与设计周期的专业人员都不是CAD专家。 此外,新的易于使用的“轻量级”实体建模器正在非传统领域(例如电子组件或娱乐)中进军,在这些领域中,非专业人员的可及性和快速的设计周期比精度更为重要。

Very often a complex 3D database created by designers would be of considerable value to others employees, customers, or suppliers, who do not have the skills necessary to use a complex solid modeler. To fulfill this need, many vendors are now offering intuitive 3D browsers that support the review and annotation of 3D models of complex assemblies of solids. These browsers support communication in product data management activities, help illustrate maintenance manuals, or provide interactive virtual-reality experiences for marketing, styling, or ergonomic analysis. In fact, we expect that future solid modelers will be architected from interchangeable design and analysis components controlled from such a browser. The remainder of this section discusses performance and ease-of-use issues related to interactions with highly complex models.

通常,由设计师创建的复杂3D数据库对于其他员工,客户或供应商而言具有相当大的价值,这些员工,客户或供应商没有使用复杂的实体建模器所需的技能。 为了满足这一需求,许多供应商现在提供直观的3D浏览器,这些浏览器支持对复杂的实体装配体的3D模型进行查看和注释。 这些浏览器支持产品数据管理活动中的通信,帮助说明维护手册,或提供交互式虚拟现实体验,以进行市场营销,样式或人体工程学分析。 实际上,我们希望将来的实体建模器将由这种浏览器控制的可互换设计和分析组件构成。 本节的其余部分讨论与与高度复杂的模型进行交互有关的性能和易用性问题。

## 7.1 Graphics 图形

Solid modelers may be rendered in different styles. Photo-realistic images of complex scenes require extensive computation and are typically used at the final illustration stage of finished models. Simpler shaded images are generally used to support interactive manipulation during design and analysis.

实体建模器可以以不同的样式呈现。 复杂场景的逼真图像需要大量计算,并且通常在完成模型的最终图示阶段使用。 通常在设计和分析过程中使用更简单的阴影图像来支持交互式操作。

Rossignac & Requicha Solid Modeling 15

### 7.1.1 Triangulation 三角化

Solid models are typically approximated by triangles (or sometimes convex polyhedra) before rendering, because graphics libraries and hardware graphics accelerators have been tuned to render such simple shape-primitives very fast. Arbitrary polyhedral faces must be decomposed into triangles. Curved surfaces must be approximated by triangular tesselations, which may automatically adapt their resolution so as to guarantee the desired accuracy. Triangulating trimmed surfaces requires combining the 3D surface tessellation with the triangulation of the face representation in the 2D parameter space of the surface. The implementation of such triangulations must ensure that the triangulations of any two adjacent faces do not generate gaps, which would arise if the two triangulations were to produce different piecewise linear approximation of the common edge of the two faces.

实体模型通常在渲染之前用三角形(有时是凸多面体)近似,因为图形库和硬件图形加速器已经过调整,可以非常快速地渲染这种简单的形状基元。 任意多面体面必须分解为三角形。 曲面必须通过三角棋盘格近似,这样可以自动调整其分辨率,以确保所需的精度。 对修剪的曲面进行三角剖分需要将3D表面细分与在曲面的2D参数空间中的面部表示的三角剖分结合起来。 这种三角剖分的实现必须确保任何两个相邻面的三角剖分不会产生间隙,如果两个三角剖分要对两个面的公共边产生不同的分段线性近似,则会产生间隙。

### 7.1.2 Graphics acceleration and compression 图形加速和压缩

Simple scenes in 3D video-games may only need a few hundred textured polygons, but solid models used for mechanical CAD, scientific, geo-science, and medical applications involve scenes with millions of faces, sometimes grouped to form the boundaries of polyhedral solids of widely varying complexity. The successful exploitation of such large volumes of scientific and engineering 3D data hinges on users’ ability to access the data through phone lines or network connections and to manipulate significant portions of these 3D models interactively on the screen for scientific discovery, teaching, collaborative design, or engineering analysis. Currently available high-end graphics hardware is often insufficient to render the models at sufficient frame rates to support direct manipulation and interactive camera control.

3D视频游戏中的简单场景可能只需要几百个纹理多边形,但是用于机械CAD,科学,地质科学和医学应用的实体模型涉及具有数百万张面孔的场景,有时将它们组合在一起以形成多面体的边界。 复杂程度差异很大。 能否成功利用如此大量的科学和工程3D数据取决于用户能否通过电话线或网络连接访问数据,以及在屏幕上交互地操纵这些3D模型的重要部分以进行科学发现,教学,协作设计, 或工程分析。 当前可用的高端图形硬件通常不足以以足够的帧速率渲染模型以支持直接操纵和交互式相机控制。

The complexity (triangle count) of industrial and sometimes even entertainment models significantly exceeds what can be rendered on a mid-range or low-end workstation at interactive rates (15 frames per second or more). Software techniques, which eliminate unnecessary or unessential rendering steps, lead to dramatic performance improvements and hence reduce hardware costs for graphics. Many of these techniques require not only complex algorithmic pre-processing. Furthermore, it is often necessary to trade the accuracy of the images for performance during interactive view manipulation. The following are examples of such techniques.

工业模型,有时甚至是娱乐模型的复杂性(三角形计数)大大超过了以交互速率(每秒15帧或更多)在中端或低端工作站上可以呈现的模型。 消除不必要或不必要的渲染步骤的软件技术可显着提高性能,从而降低图形的硬件成本。 这些技术中的许多不仅需要复杂的算法预处理。 此外,通常需要在交互视图操纵过程中为了实现性能而牺牲图像的准确性。 以下是此类技术的示例。

Triangles are often ordered to form long triangle strips which reduce by 3 the number of times the same vertex is processed by the graphics library. Each new triangle is defined by combining the next vertex of the strip with the previous two vertices.

三角形通常被命令形成长三角形带,从而将图形库处理同一顶点的次数减少3倍。 通过将条带的下一个顶点与前两个顶点进行组合来定义每个新的三角形。

Triangles may be grouped by orientation and entire groups of back-facing triangles may be readily rejected without further considerations. Objects or triangles that do not intersect the viewing frustum or are hidden behind large occluding objects may also be quickly identified and need not be processed for rendering.

三角形可以按方向进行分组,而整组背面三角形可以不经进一步考虑而轻易拒绝。 不与视锥相交或隐藏在较大的遮挡对象后面的对象或三角形也可以快速识别,无需进行渲染处理。

The remaining (potentially visible) triangles may still be too numerous. Solids that are far from the viewer (i.e. whose projection on the screen is small) may be rendered using “impostors” which resemble the original solid but have significantly fewer triangles. Numerous simplification algorithms have been developed for producing series of approximating models with decreasing levels-of-detail (LOD). The simplest and most efficient approach clusters vertices by comparing their truncated coordinates and eliminates triangles with more than one vertex in the same cluster [Rossignac93]. Many slower and more complicated, although more effective simplification techniques have been proposed. For example, the edges of a triangulated boundary may be collapsed in an order which introduces the least amount of error [Ronfard96], until the desired triangle count or the maximum allowable error have been reached. Collapsing an edge also collapses the two triangles incident upon the edge.

其余的(可能可见的)三角形可能仍然太多。 距离观看者较远的实体(即,其在屏幕上的投影较小)可以使用类似于原始实体但三角形的数量明显较少的“标记”来渲染。 已经开发出许多简化算法来产生具有降低的细节水平(LOD)的一系列近似模型。 最简单,最有效的方法是通过比较顶点的截断坐标来对顶点进行聚类,并消除同一聚类中具有多个顶点的三角形[Rossignac93]。 尽管提出了更有效的简化技术,但许多慢速且更加复杂的技术。 例如,三角边界的边缘可以按照引入最小误差量的顺序折叠[Ronfard96],直到达到所需的三角形计数或最大允许误差为止。 塌陷边缘也会使入射在边缘上的两个三角形塌陷。

In many industrial applications, complex 3D models approximated by millions of triangles, must be archived, downloaded using limited bandwidth connections, and finally transmitted to the rendering subsystem at each frame (or stored on the graphics board’s limited local memory). Representing each triangle by the floating point coordinates of its three vertices requires 26 bytes, to which one must often add rendering attributes, such as texture coordinates or vertex normals for smooth shading. This count may be reduced by more than a factor of two if one were to use triangle strips. Separating the description of the vertex locations from the description of the triangle-vertex incidence eliminates the need to store or send the same vertex twice, but requires storing for each triangle, the references to its supporting vertices. In its non-compressed form, each one of these references may involve a number of bits equal to the log of the total number of vertices.

在许多工业应用中,必须将近似3百万个三角形的复杂3D模型进行存档,使用有限的带宽连接进行下载,最后在每一帧传输到渲染子系统(或存储在图形板的有限本地内存中)。 用三个顶点的浮点坐标表示每个三角形需要26个字节,通常必须向其添加渲染属性,例如纹理坐标或顶点法线以平滑阴影。 如果使用三角带,则此计数可能会减少两倍以上。 将顶点位置的描述与三角形-顶点入射的描述分开,消除了存储或发送相同顶点两次的需要,但是需要为每个三角形存储对其支撑顶点的引用。 在其非压缩形式中,这些参考中的每一个都可以涉及等于总顶点数的对数的位数。

A lossy compression to the vertex coordinates, which combines vertex quantization and entropy coding, reduces by three or more the number of bits that represent the location of the vertices [Deering95]. Triangle-vertex incidence relations may be encoded with less than 2 bits per triangle [Taubin96]. An alternative, which does not require random access to all the vertices, generalizes the notion of triangle strips to a stack-buffer of 16 vertices [Deering95]. Although this approach requires on average about 13 bits per triangle to store the triangle-vertex incidence and requires sending about 15% of the vertices more than once, it is particularly effective for interfacing to a graphics subsystem with limited on-board memory.

对顶点坐标的有损压缩(结合了顶点量化和熵编码)将代表顶点位置的位数减少了三倍或更多[Deering95]。 三角形-顶点入射关系可以用每个三角形少于2位的方式编码[Taubin96]。 一种不需要随机访问所有顶点的替代方法,将三角形带的概念推广为16个顶点的堆栈缓冲区[Deering95]。 尽管此方法平均每个三角形需要大约13位来存储三角形顶点入射,并且需要多次发送约15%的顶点,但对于与板载内存有限的图形子系统进行接口连接特别有效。

Rossignac & Requicha Solid Modeling 16

## 7.2 3D input 3D输入

The human-machine communication during the design activity involves mostly the selection and entry of commands and parameter values and increasingly the direct manipulation of the model on the screen to control the position of the camera or of a particular group of solids in an assembly. Although this manipulation of 3D positions was traditionally performed with a 2D mouse, new techniques are being explored for using two-hand interfaces [Zeleznik97] or immersive virtual reality environments. A natural alternative uses pen-and-tablet 2D input and generates solid 3D models from drawings [Grimstead95]. These approaches have to deal with a lack of information that implies ambiguity.

在设计活动期间,人机通信主要涉及命令和参数值的选择和输入,并且越来越多地直接在屏幕上对模型进行直接操作,以控制照相机或组件中特定的一组固体的位置。 尽管传统上是使用2D鼠标来执行3D位置的这种操纵,但是正在探索使用双手界面[Zeleznik97]或沉浸式虚拟现实环境的新技术。 自然的选择是使用笔和平板电脑的2D输入并从工程图生成实体3D模型[Grimstead95]。 这些方法必须处理缺乏信息的隐含性。

# 8 Conclusions 总结

Solid modeling technology has significantly outgrown its original scope of computer-aided mechanical design and manufacturing automation. It plays an important role in may domains including medical imaging and therapy planning, architecture and construction, animation and digital video-production for entertainment and advertising.

实体建模技术已远远超出了其最初的计算机辅助机械设计和制造自动化范围。 它在医学成像和治疗计划,建筑和构造,动画以及娱乐和广告的数字视频制作等可能领域中发挥着重要作用。

The recent maturity of the solid modeling theory and technology has fostered an explosion in the field’s scientific literature and in the deployment of commercial solid modelers. The dominant cost of embracing the solid modeling technology within an industrial sector has shifted over the years from hardware, to software, to labor. Today, industrial strength solid modeling tools are supported on inexpensive personal computers, software price ceased being an issue, and the progress of user-friendly graphics interfaces has considerably reduced training costs. As the theoretical understanding of solid modeling and efficient algorithms for the fundamental operations have begun to percolate towards commercial systems, research efforts are focused on making nonexpert users more productive.

实体建模理论和技术的日趋成熟,促进了该领域的科学文献和商业实体建模师的部署。 多年来,在工业部门中采用实体建模技术的主要成本已经从硬件,软件到劳动力转移了。 如今,廉价的个人计算机支持工业强度的实体建模工具,软件价格不再是一个问题,并且用户友好的图形界面的进步已大大降低了培训成本。 随着对基本建模的实体建模和有效算法的理论理解开始渗透到商业系统,研究工作集中在提高非专家用户的生产率上。

The modeling task is labor intensive. For instance, the design of a new aircraft engine requires 200 person years. Although the solid modeling activity is only a small part of this cost, much of the current research attempts to make designers more effective, by supporting higher-level design automation and reusability. Significant progress was recently achieved on data compatibility between different solid modelers and on the support of constraints and features encapsulated into “smart” objects that adapt their shape and dimensions to the context in which they are used.

建模任务是劳动密集型的。 例如,新飞机发动机的设计需要200人年。 尽管实体建模活动仅占此成本的一小部分,但当前的许多研究都试图通过支持更高级别的设计自动化和可重用性来提高设计人员的效率。 最近,在不同的实体建模器之间的数据兼容性以及对封装在“智能”对象中的约束和特征的支持方面取得了重大进展,这些约束和特征使它们的形状和尺寸适应使用它们的上下文。

The exploitation of the resulting models has been so far primarily restricted to designers. Spreading the access to a larger population will reduce the cost of downstream applications (such as manufacturing, documentation, and marketing) and will improve communication through out the enterprise, its suppliers, and its customers. Progress is still inhibited by the network bandwidth for accessing highly complex assembly models, by the limited graphics performance of personal computers, and by unnatural 3D manipulation interfaces. Recent progress on these fronts are reviewed in [Rossignac97b].

迄今为止,对结果模型的开发主要仅限于设计人员。 将访问权限扩展到更大的人群将减少下游应用程序的成本(例如制造,文档和营销),并将改善整个企业,其供应商和客户之间的通信。 用于访问高度复杂的装配体模型的网络带宽,个人计算机有限的图形性能以及不自然的3D操作界面仍然阻碍了进度。 [Rossignac97b]综述了这些方面的最新进展。

Total automation of a wide range of applications--an original motivation of solid modeling--has proven harder than originally expected, especially when automatic synthesis or planning is required.

事实证明,广泛应用的全自动化(实体建模的原始动机)比最初预期的要难,特别是在需要自动综合或计划时。

Current trends point away from closed end-user modelers and towards flexible object-oriented libraries supporting a broader range of geometric computations. Access to these libraries may be provided from easy-to-use 3D browsers.

当前的趋势从封闭的最终用户建模工具转向指向支持更广泛的几何计算的灵活的面向对象的库。 可以从易于使用的3D浏览器中访问这些库。

# 9 Bibliography  参考书目

[Agrawal94] A. Agrawal and A. A. G. Requicha, “A paradigm for the robust design of algorithms for geometric modeling”, Computer Graphics Forum, Vol. 13, No. 3, pp. 33-44, September 1994. (Proc. Eurographics ‘94.)
[Alexandroff61] P. Alexandroff, Elementary Concepts of Topology, Dover Publications, New York, NY, 1961.
[Banerjee96] R. Banerjee and J. Rossignac, Topologically exact evaluation of polyhedra defined in CSG with loose primitives, to appear in Computers Graphics Forum, Vol. 15, No. 4, pp. 205-217, 1996.
[Barr84] A. Barr, Local and global deformations of solid primitives, Proc. Siggraph’84, Computer Graphics, Vol. 18, No. 3, pp. 21-30, July 1984.
[Baumgart72] B. Baumgart, Winged Edge Polyhedron Representation, AIM-79, Stanford University Report STAN-CS-320, 1972.
[Bowyer95] A. Bowyer, S. Cameron, G. Jared, R. Martin, A. Middleditch, M. Sabin, J. Woodwark, Introducing Djinn: A Geometric Interface for Solid Modeling, Information Geometers Ltd, 1995.
[Brown82] C. Brown, PADL-2: A Technical Summary, IEEE Computer Graphics and Applications, 2(2):69-84, March 1982.
[Deering95] M. Deering,Geometry Compression, Computer Graphics, Proceedings Siggraph'95, 13-20, Augiust 1995.

[Farin90] G. Farin, Curves and Surfaces for Computer-Aided Geometric Design,  Second edition, Computer Science and Scientific Computing series, Academic Press, 1990.
[Grimstead95] I.J. Grimstead and R.R. Martin, Creating solid models from single 2D sketches, Proc. Third Symposium on Solid Modeling and Applications, ACM Press, pp. 323-337, May 17-19, 1995.
[Han97] J.-H. Han and A. A. G. Requicha, Integration of feature based design and feature recognition, Computer-Aided Design, Vol. 29, No. 5, pp. 393-403, May 1997.
[Hoffmann89] C. Hoffmann. Geometric and Solid Modeling. Morgan Kaufmann, San Mateo, CA, 1989.
[Horn89] W. Horn and D. Taylor, A theorem to determine the spatial containment of a point in a planar polyhedron, Computer Vision, Graphics, and Image Processing, 45:106-116, 1989.
[Krishnan97] S. Krishnan and D. Manocha, An efficient surface intersection algorithm based on lower-dimensional formulation, ACM Transactions on Graphics, Vol. 16, No. 1, pp. 74-106, January 1997.
[Latombe91] J. Latombe, Robot Motion Planning, Kluwer, Boston, 1991.
[Lee82] Y. T. Lee and A. A. G. Requicha, Algorithms for computing the volume and other integral properties of solids: I --Known methods and open issues and II --- A family of algorithms based on representation conversion and cellular approximation, Commun. of the ACM, Vol. 25, No. 9, pp. 635-650, September 1982.
[Mantyla86] M. Mantyla, Boolean Operations of 2-manifold Through Vertex Neighborhood Classification, ACM Trans. on Graphics, 5(1):1-29, 1986.
[Murali97] T.M. Murali and T.A. Funkhouser, Consistent solid and boundary representations from arbitrary polygonal data, Proc. 1997 Symposium on Interactive 3D Graphics, ACM Press, pp. 155-162, Providence, R.I.,  April 1997.
[Naylor90] B. Naylor, J. Amanatides and W. Thibault, Merging BSP Trees Yields Polyhedral Set Operations, ACM Computer Graphics SIGGRAPH '90, 24(4):115-124, August 1990.
[Patrikalakis93] N.M. Patrikalakis, Surface-to-surface intersections, IEEE Computer Graphics and Applications, Vol. 13, No. 1, pp. 89-95, 1993.
[Requicha80] Representation of Rigid Solids: Theory, Methods, and Systems, A.A.G. Requicha, ACM Computing Syrveys, 12(4), 437:464, Dec 1980.
[Ralston83] A. Ralston and E. Reilly, Editors, Encyclopedia od Computer Science and Engineering, second Edition, van Nostrand Reinhold Co., New York, pp .97-102, 1983.
[Requicha82] A. A. G. Requicha and H. B. Voelcker, Solid modelling: a historical summary and  contemporary assessment”, IEEE Computer Graphics and Applications, Vol. 2, No. 2, pp. 9-24, March 1982.
[Requicha83] A. A. G. Requicha, Toward a theory of geometric tolerancing, Int. J. of Robotics Research, Vol. 2, No. 2, pp. 4560, Winter 1983.
[Requicha83b] A. A. G. Requicha and H. B.  Voelcker, “Solid modelling: current status and research directions”,  IEEE Computer Graphics and Applications, Vol. 3, No. 7, pp. 25-37, October 1983.
[Requicha85] A. A. G. and H. B. Voelcker, “Boolean operations in solid modelling: boundary evaluation and merging algorithms”,  Proc. IEEE, Vol. 73, No. 1, pp. 30-44, January 1985.
[Requicha88] A. A. G. Requicha, “Solid modelling: a 1988 update”, in B. Ravani, Ed., CAD Based Programming for Sensory Robots. New York: Springer Verlag, 1988, pp. 3-22.
[Requicha92] A. A. G. Requicha and J. R. Rossignac, “Solid modeling and beyond”, IEEE Computer Graphics & Applications, (Special issue on CAGD ) Vol. 12, No. 5, pp. 31-44, September 1992.
[Requicha93] A. A. G. Requicha, “Mathematical definition of tolerance specifications”, ASME Manufacturing Review, Vol. 6, No. 4, pp. 269-274, December 1993.
[Requicha96] A. A. G. Requicha, “Geometric reasoning for intelligent manufacturing”, Commun. ACM, Special Issue on Computer Science in Manufacturing, Vol. 39, No. 2, pp. 71-76, February 1996.
[Ronfard96] R. Ronfard and J. Rossignac, Full-range approximations of triangulated polyhedra, Computer Graphics Forum, (Proc. Eurographics’96), pp. C-67, Vol. 15, No. 3, August 1996.
[Rossignac84] J. Rossignac and A. Requicha, Constant-Radius Blending in Solid Modeling, ASME Computers in Mechanical Engineering (CIME), Vol. 3, pp. 65-73, 1984.

[Rossignac86] J. Rossignac and A. Requicha, Offsetting Operations in Solid Modelling, Computer-Aided Geometric Design, Vol. 3, pp. 129-148, 1986.
[Rossignac86b] J. Rossignac and A. Requicha, Depth Buffering Display Techniques for Constructive Solid Geometry, IEEE Computer Graphics and Applications, 6(9):29-39, September 1986.
[Rossignac86b] J. Rossignac, Constraints in Constructive Solid Geometry, Proc. ACM Workshop on Interactive 3D Graphics, ACM Press, pp. 93-110, Chapel Hill, 1986.
[Rossignac88b] J. Rossignac, P. Borrel, and L. Nackman, Interactive Design with Sequences of Parameterized Transformations, Proc. 2nd Eurographics Workshop on Intelligent CAD Systems: Implementation Issues, April 11-15, Veldhoven, The Netherlands, pp. 95-127, 1988.
[Rossignac89] J. Rossignac and H. Voelcker, Active Zones in CSG for Accelerating Boundary Evaluation, Redundancy Elimination, Interference Detection and Shading Algorithms, ACM Transactions on Graphics, Vol. 8, pp. 51-87, 1989.
[Rossignac89b] J. Rossignac and M. O'Connor, SGC: A Dimension-independent Model for Pointsets with Internal Structures and Incomplete Boundaries, in Geometric Modeling for Product Engineering, Eds. M. Wosny, J. Turner, K. Preiss, North-Holland, pp. 145-180, 1989.
[Rossignac90] J. Rossignac, Issues on feature-based editing and interrogation of solid models, Computers&Graphics, Vol. 14, No. 2, pp. 149-172, 1990.
[Rossignac91] J. Rossignac, and A. Requicha,  Constructive Non-Regularized Geometry, Computer-Aided Design, Vol. 23, No. 1, pp. 21-32, Jan./Feb. 1991.
[Rossignac92b] J. Rossignac, Through the cracks of the solid modeling milestone, in From object modelling to advanced visualization, Eds. S. Coquillart, W. Strasser, P. Stucki, Springer Verlag, pp. 1-75, 1994.
[Rossignac93] J. Rossignac and P. Borrel, Multi-resolution 3D approximations for rendering complex scenes, pp. 455-465, in Geometric Modeling in Computer Graphics, Springer Verlag, Eds. B. Falcidieno and T.L. Kunii, Genova, Italy, June 28-July 2, 1993.
[Rossignac94] J. Rossignac and A. Kaul, AGRELs and BIPs: Metamorphosis as a Bezier curve in the space of polyhedra, Computer Graphics Forum, Vol 13, No 3, pp. C179-C184, Sept 1994.
[Rossignac96] J. Rossignac, CSG formulations for identifying and for trimming faces of CSG models,  CSG'96: Set-theoretic solid modeling techniques and applications, Information Geometers, Ed. John Woodwark, pp.1-14, 1996.
[Rossignac97] J. Rossignac, Structured Topological Complexes: A feature-based API for non-manifold topologies”, Proceedings of the ACM Symposium on Solid Modeing 97, C. Hoffmann and W. Bronsvort, Editors, ACM Press,  pp. 1-9, 1997.
[Rossignac97b] J. Rossignac, The 3D revolution: CAD access for all, International Conference on Shape Modeling and Applications, Aizu-Wakamatsu, Japan, IEEE Computer Society Press, pp. 64-70, 3-6 March 1997.
[Sedeberg86] T. Sedeberg and S. Parry, Free-form deformation of solid geometric models, ACM Computer Graphics (Proc. Siggraph), 20(4):151-160, Dallas, August 1986.
[Spyridi93] A. J. Spyridi and A. A. G. Requicha, “Automatic planning for dimensional inspection”, ASME Manufacturing Review,  Vol. 6, No. 4, pp. 314-319, December 1993.
[Taubin96] G. Taubin and J. Rossignac, Geometric Compression through Topological Surgery, IBM Research Report RC-20340. January 1996. (http://www.watson.ibm.com:8080/PS/7990.ps.gz).
[Samet90]  Hanan Samet, Applications of Spatial Data Structures, Reading, MA, Addison-Wesley, 1990
[Shapiro91] V. Shapiro and D. Vossler. Construction and Optimization of CSG Representations, Computer-Aided Design, 23(1):4-20, January/February 1991.
[Spyridi90] A. J. Spyridi and A. A. G. Requicha, “Accessibility analysis for the automatic inspection of mechanical parts by coordinate measuring machines”, Proc. IEEE Int’l Conf. on Robotics & Automation, Cincinnati, OH, pp. 1284-1289, May 13 18, 1990.
[Spyridi94] A. J. Spyridi and A. A. G. Requicha, “Automatic programming of coordinate measuring machines”, Proc. IEEE Int’l Conf. on Robotics & Automation, S. Diego, CA, pp. 1107-1112, May 8 - 13, 1994.
[Tilove80] R. Tilove, Set Membership Classification: A Unified Approach to Geometric Intersection Problems, IEEE Trans. on Computers,, C-29(10):874-883, October 1980.

[Vandenbrande93] J. H. Vandenbrande and A. A. G. Requicha, “Spatial reasoning for the automatic recognition of machinable features in solid models”, IEEE Trans. Pattern Analysis & Machine Intelligence, Vol. 15, No. 10, pp. 1269-1285, December 1993.
[Weiler87] Non-Manifold Geometric Boundary Modeling, K. Weiler, ACM Siggraph, Tutorial on Advanced Solid Modeling, Anaheim, California, July 1987.
[Zeleznik97] R.C. Zeleznik, A.S. Forsberg, and P. Strauss, Two pointer input for 3D interaction, Proc. 1997 Symposium on Interactive 3D Graphics, ACM Press, pp. 115-120, Providence, R.I.,  April 1997.



# 10 Further reading 延申阅读

M. Mantyla. An Introduction to Solid Modeling. Computer Science Press, Rockville, Maryland, 1988. (Detailed presentation of som solid representations and of algorithms for regularized Boolean operations.)

A. Bowyer, S. Cameron, G. Jared, R. Martin, A. Middleditch, M. Sabin, J. Woodwark, Introducing Djinn: A Geometric Interface for Solid Modeling, Information Geometers Ltd, 1995. (Definition of a set-theoretic API independent of the representation scheme used.)

J. Rossignac and J. E. Turner, Editors, Proc. ACM Symposium on Solid Modeling Foundations and CAD/CAM Applications, ACM Press, Austin, Texas, 1991. (About 40 papers devoted to solid modeling.)

J. Rossignac, J. Turner, and G. E. Allen, Editors, Second ACM Symposium on Solid Modeling and Applications, ACM Press, Montreal, Canada, 1993. (About 40 papers devoted to solid modeling.)

C. Hoffmann and J. Rossignac, Editors, Proc. Third Symposium on Solid Modeling and Applications, ACM Press, Salt Lake City, Utah, 1995. (About 40 papers devoted to solid modeling.)

J. Rossignac, Simplification and Compression of 3D Scenes, Tutorial, Eurographics’97, Budapest, Hungary, September 1997. (Overview of advances in polyhedral simplification and compression.)

Representing Solids and Geometric Structures, in Geometry and Optimization Techniques for Structural Design, pp. 1-44, Eds. S. Kodiyalam, M. Saxena, Computational Mechanics Publications, Southhampton, 1993.





 楼主| 发表于 2020-1-14 12:02:45 | 显示全部楼层
带图版已经发表在 blendercn中文杂志上。
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

站长推荐上一条 /1 下一条

Blender最新中文教学视频|Blender头条|小黑屋|手机版|Archiver|Blender中国 ( 蜀ICP备17002929号 )360网站安全检测平台

GMT+8, 2020-1-22 21:31 , Processed in 0.046072 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表