■
l 9 9 0年
西 北 纺 鲺 土 学 院 学 报
of Northw est Institute 0f Textile Science and Technology
第3 4期 (总第15、16期) No．3 4 1990 (Sum No．15、16)
，2
图 形 数 据 结 构 的 研 究 。 0{ ?
√
应柏安 马 柯 王承武 程苏民
(机械系)
埔 要
， 拳文针对现有CAD系统的不足，提 出了动态图 数据 姑杓的概念及其构 成 原
理，井从集合论的角度对动态图开j数据姑杓进行 T较精确的定叉。在此图形数据结
构基础上设计的交五式CAD系统可有数地解击图开j识别和参数作囤的问 题，这 寿
从根本上解决CAD与CAPP~9集成以覆使CAD具有理想的、高效的工作方式提供
T理论 上的依据 。J
f I
关键词r
．垄垒旦 双射 关系， 塑 堕，基本体素 c
J＼
0 前 言
。 在通用图形数据结构基础上设计的交互式CAD系统 (后简称传统的 CAD，这 里 aCA
D”的概念指对机械零部件的计算机辅助结构设计和精度设计，且设计结果体现在计算机辅
助下绘制出的标准工程图之中)巳发展到了较成熟的程度，但是随着计算机应用的进一步深
化厦系统化，人们便可发现，由此所产生的图形信息难于进行图形识别。对于机械制造业而
言，就使得CAD的设计结果不能直接用于CAPP中，这便给CAD与CAPP的集成造成了很
大的障碍·因此，能否设计一种新的图形数据 结构，使得用此图形数据结构来描述图形对象
的结果能直接成为机内可知图形或经简单的识剐分析就能成为机内可知图形，这是问题提 出
的一个方面。
另一方面 ，实用中理想的CAD作图方式是参数作图，而传统睁CAD系统所 作出的图形
不具备 参数响应 的特征，因而CAD系统在实用中很难实现 参数作图，逸对CAD的推广
和应用是一个很大的障碍。那么，怎样的图形数据结构描述的图形才能具有 “参数响应”的
特征，这是问题提出的第二个方面。 。
针对这两个问题，本文帆应用的角度提出了动态图形数据结构的概念及其构成原理，力
图使以此图形数据结构为基础的CAD系统能较好地解决这两个闷题。
丰文收蓟目期l 1990年3月31日
维普资讯
茵 北 纺 织 工 学 皖 学 报
i 基本概念和构成原理
通用图形数据结构的重点放在了图形的最底层，即列基本图元的组织稻表达上面，这是
传统的CAD系统产生上述两个问题的根本原因。但就图形学来讲，基本图元是实现图 形 的
基础。由此我们设想有这样一种图形数据结构，它通过图形的特征和参数来描述图形对象，
而图形实现 的工作仍由通用的图形数据结构来完成，这部分是处在随参数的变化而被刷新的
动态状态之 中。若将记录持征和参数的结构称为图形描述结构，将实现图形的这部分称为对
应图形变换算法，则可 说动态图形数据结构是建立在通用图形数据结构 ( 点、线来描述图
形)基础之上的一种 高层次信息来描述图形对象的图形数据结构，它由图形描述结构和对
应图形 变换算法这两大部分组成。下面从集合论的角度，对动态图形数据结构作 如 下 的 定
义 。
由于动态图形数据结构的重点放在了图形对象的特征和参数上，因此，我们必须按能反
映出图形对象的整体特征的基本特征来分解图形对象 (对不同类别的图形对象其分解的方法
不同)，被分解 出的基本图形和其描述结构以及它的图形变换算法应满足定义一的要求。
定义一：设s为某类物体的图形表示的集合， 为从s中分解出的基本图形的有限集 合，
D为对基本图形描述的有限集合， 为实现基本图形的图形变换算法的有 限集合。则有 函 数
r—D， ：D一 ，g和f均为双射 (印一一对应的)，且有复合函数fog： 一 ，fog亦
为双射。 ：
图形识别的最终目的是在于对图形作描述和解释，以便最终能理解它是什么图形，如果
在图形描述结构中记录的就是对图形的识别结果，那无疑便解决了图形识别这一闻题 而能
否有效地达到这一目的，与图形的输入方式有密切关系。因此，要求图形输入方式及图形描
述结构D应满足定义二的要求。
定义二：对于D，要求其中的每一元素d辛 对对应基本图形t的识剐结果，且对于描 述
s中某一物体的图形，有限集合D 辛 对该物 体图形的识别结果，其中 D 为 D的子 集，即
D D 。
为达到参数作图的要求，对图形描述结构应按定义三 的要求来设计。
定义三t对基本图形描述信息D的组织和记录 ，构成了形式上的动态图形数据结 构。它
由基本图形描述信息结构 TD、图形数据顺序表 0D和图形动态信息顺序表 DD这三部分 姐
成。若记形式上的动态图形数据结构为DB ，则有DB 串(TD，一OD，DD}，其 中有 如 下
关系z ’
关系m l
R1={(n)，OD)由OD向TD提供其所需的图形几何数据值，TD中通过指向OD的 指
针KP (m)来获取几何数据)
关 系R2；
R2={(TD，DD)DD是在2D的构造过程中动态生成昀，JIDD~]TD提供其所需的有
关图点的坐标值，TD中通过指向DD的指针五 ( )来获取圈点信息}
DB 的构成如图 l所示。
其中由KM ( )记录基本图形固有的特征信息，出 ( )实现i0录闻的关系。
●
维普资讯
■
第3 4期 图形数括站桩的研究
图 1 DB 的构成
在I 中如第 条记录产生Pn=< l，p2，⋯⋯ )中所台的 个圈点信息，则在该记录 椅
造完之后，DD中圈点信息的集合为P。
= UPi
= 1
从DB 的构成上可见，对于同一rD只要改变对应OD申的参数值，便实现了同一结 构 下
不同尺寸的另一个图形，这就是参数作图的原理 在系统申TD．01)存在外 存 储 器 申，而
DD处在被不断刷新的状态冲I。
定义四；在D口中，定义实现基本图形的变换算法的存在形式为功能子程序，即有；
A={ l d为功能子程序)。
基本图形变换算法 是DB中的有机组成部分，在程序中图形信息是通过通用图形数据 结
构来组织的，从这个意义上可说； 、
A=通用图形数据结构 (I'B) +通用算法
基本图形变按算法 应具有以下基本功能； !
①按要求计算出基本体素在壑问的点、线、面几何参数值，并使用通用的图形数据结 构
来组织基本体素的几何信息和拓扑信息。
◎具有提取动态生成的圈点信息和其它图形识别所需的特缸值的功能。
@提供对该图进行各种变换操作的信息接 口。
④完成图形输出对的图形实现任务。
在现有的CAD系统中，其对图形的变换操作及图形实现的功靛以选到了成熟的 程 度 ．
因此，只需在现有的CAD系统之上加上高层次的输入方式和管理结构印可使其解决图 形 识
别和参数作图这两个问题。 。
至此，从广义上对动态图形数据结构作如下定义： · -
定义五；对于集合D和 ，定义二元关系R；
R={(d，口) f口是d唯一对应的图形变换算法，d是0唯一对应的作用对象)
则关系R为描述该类图形s的动态图形数据结约，记为D最， 印DB车 。
以上定义构成了动态图形数据结构DB的基本概念和原理，从中i觇 ，图形变换算法讨符
以子程序的形式溶于系统中，且对它的设计体现在子程序所具备的功能之上。因 此，对 DB
的设计相操作将集中在DB 上。同时，由于对D 的特殊要求，D 中对z'D §设计，不仅涉
及反映其记录问关系的指针场，而且更重要的是要对反映描述对象信息的数据场进行设计。
另外，由予芷DB的设计中与具体的描述对象类有关，r1)e~的内容会因描述对象的种类
维普资讯
e 西 北 纺 织 工 学 院 学 报 1990年
不同而有所不同，因此以下备部分的内容均以机械 几何形体类对象为例。但是，需要说明的
是，对于不 同类的描述对象，以上所述的基本概念和构成原理是完全相同的。
2 对象描述 ●
根据定义一 的要求，选择基本体素为构成机械几何形体的基本元素，此基本体素可分为
轴类和孔类。按照定义二的要求对基本体素的描述需用以下信息。 ●
2．1 特征信息
特征信息由表l所示结构表示。
表 l 特征信息
巨至Ⅱ亘工二]互 !
特征信息通常用一命令字 (或特征字)来表示，它与基本体素一一对应，且与图形变换
算法一一对应，其中隐台着基本体素中的面信息
2．2 基本体素定位信息
基本体素定位信息由表2所示结构表示
袭 2 基本体素定位信息
定位基点 向位移 X向系数 y向位移 y向系数 z向位移 j z向系数
【 占 DX FX Dy Fy DZ l FZ 、
其中，定位基点B是在构造对象的过程中动态生成的，其生成的一般规律是t对于 一 空
_ l
间六面体，有六个定位点 (均以各面的中心点为定位点)，若其中某一点被用于确定该基 本
体素的位置，则 其它五点为在该体素构造完成后所新生成的基点。原始基点B0可在三维空间
中任意给定，也可根据其它要求来确定。DX，DY、DZ为指向OD的指针。 -
按此结构所给的定位法，可确定空间任一点的位置 ，称此法为基点～一位移定位法
2．3 几何数据厦其关系信息
几何数据及其关系信息由表3所示结构表示。
表 s 几何数据聂其关系信息
X方向尺寸链 y方向尺寸链 Z方向尺寸 链
数目 量1 ⋯ I。量 数目l量1 ⋯ 置 数目 量1{⋯ 量N
{ I m ⅣZ VZ‘ Zn Ⅳ 1 l VXt NY l Y1
维普资讯
t
捧3 4期 图形数据结构的研究
由于机械几何形体的特殊要求，我们设计其基本体素各方向的几何尺寸均由对应尺寸链
的计算结果给出，即为各量的代数和。其中 xl～yXl、 yl～VYm， _Zl～ 为指向0D
的带符号的指针，当其值为正时表示为增环，当其值为负时表示为减环。
具体计算为 (以 向尺寸为例)t
当NX=l时， Xl所指的数据为墨方向晦尺寸t
当Nx>l时，该尺寸链的封闭环为基本体素x方向的尺寸。
对于不同的使用对象，各方向上尺寸链中的环数可根据具体情况来确定，即确定f、m、
n的具体值，且有关系l≤Nx≤r，l≤Ny≤m，l≤Nz≤ 。
2．I 加工信息
’
对于机械几何形体其加工信息是指对零件加工所应达到的精度信息，其中包括面精度信
息和尺寸精度两部分，见表4，表5所示。
裹 4 面精度信息
面精度 信息
序号l特征 粗糙度 形位公差类型 形位公差公差值 形位公差基准l基准面
裹 5 尺寸精度值童
尺寸精度信息
尺寸名称1尺寸数值l上偏差l下偏差
2．5 修饰信息
为使输出的图形便于人工识别，即符合工程图的要求，还需对基本体素的圈形作一定的
修饰，这就是附属在基本体素上的修饰信息，如剖面线等。由于这些信息不影响在机内对对
象的识别，因此在识别到为修饰信息时，则该信息不记入对对象的识g 结果市
以上各信息中，表l至表4内容记录在 D中，表5的内容记在O 中，修饰信息使用 D的
结构。
3 链接关系分析
这里的链接关系是指TD中的链接关 系，对于OD、DD，由于其仅存在记录间的 关 系，
所以根据其构成方式确定这二者的链接关系为顺序单链关系。
在IrD中，由于它的链接关系不仅有记录链接关系，而且还有结构链接关系，周此，TD
中的链接关系是通过以下三个方面实现的。
3·1 自然链接关系
自然链接关系反映的是记录问的关系，它与n)的构成方式有关，由于 )的构成也是顺
维普资讯
3 西 北 纺 织 工 学 院 学 报 l090单
序完成的，因此TD的自然链接关系亦为顺序单链关系。所不同韵是，在TD记录间的关系还
反映 了一定的结构关系，所以还需要表6的辅助信息来对此顺序单链关系作一补充，以 便 能
正确地完成对TD的操作。
表 6 辅助信息
图点增量 l包含对象 I尺寸链关系 ；
图点增量指本记录新增加的图点数量，包含对象指轴型基本体素所包誊自 十或者几个
孔犁基本体素的记录号'尺寸链关系即为表3所示的苯系。 。 、
3．2 体链接关系
J
_
在rD中，定位信息 (见表2)也反应了基本体素间的体链接关系，这种链接 关 系 不 是
平面上的，而是空间六个方向上的链接关系。具体的链接关系是由D 、DY、D饭 应 出 的
(见表7)。
衰 T 基本体素问的麓接关系
D 置 一 · D y t DZ
位移量符号 + + +
反应链接关系的方向 +置 一置 + —y +Z —Z
r
反应出的这种体链接关系能全面地描述对象的结构关系。
3．3 面麓接关系
‘ 如 中尺寸链信息 (见表3)反应了描述对象平行平面之间的链接关系}在加工信息 (见
表4)中，通过位置公差反应了另一种面之间的链接关系。
4 结 束 语
我们从实际应用的角度出发，研究了CAD系统中的信息的组织形式及其作用，力 图 使
CAD能识射自身所产生的图形，并使其能将成组技术的设计思想运用在CAD过程中以实现
设计的高效性。为此提出了动态图形数据结构的概念和其构成原理 同时，我们运用这一原
理设计了GT--CAD／CAPP集成系统 (3]，系统的工作结果表明，它较理想地解决了机内
识别和参数作图的问题。但是，作为一个新的理论，对动态图形数据结构的研究违需作进一
步的细致工作．使其更加完善。 ．
●
维普资讯
t
第3、4期 图形数据结构的研究 31
参 考 文 献
l 金廷赞，计算机图形学，浙江大学出版社，1886年版
2 刘光奇 张霭珠、胡黄琛，离{我数学。复旦大掌出版社，1988年版
3 马柯 应柏安、王承武。CA￡l／CAPP寨威系统的研究及实现。成组技术与生产现代化 isgo(z)
Research On Graphic Data Structure
Ying B口i 4 K 昭 Ch Ch ng Sumin
(Mechanic Engineering Department)
l
Abitract
In this paper we put forword the conception and the forming fundamental
theory Of the dynamic graph data structure， which point at the insuffieient of
existing CAD system 。And the conception is accurately defineted from set theory
The CAD system which dased 0n the dynamic graph data strueture can efficiently
solve the problem of graph di8七iagu hing且nd parameter draming．This provided
theoretical basis for solving the problem of intergrating eAD／CAPP and making
the CAD system have the!~eal end efferent wor
KeyWo rdI Dgnamic 口曲 data str cf杯r翻
stingui shng~ Paramcte r drarai Primary s
king way． -．
丑{ieetion~Retadom Graph
offd
维普资讯
