（机械设计及理论专业论文）平面立体完整画隐线图解释及误差校正处理研究.pdf

太原理：工大学硕士研究生学位论文 平面立体完整画隐线图解释及误差校正处理研究 摘要 计算机自动解释线图是计算机视觉和模式识别的重要研究内容之一。 人们经常利用线图来描述三维物体，尽管线图只是由一些简单的直线段组 成的有序集合，实际上它却包含了三维物体的大量信息。长期以来人们一 直在画法几何中研究三维物体的二维表达方式，并已经形成了较为成熟的 理论和方法，但对其逆问题利用二维线图来重构三维实体模型的研究却起步 较晚。人类可以利用其高度发达的视觉系统比较容易的获取二维线图所表 达的三维信息，但对于计算机而言，计算机系统是一个完全具体的、无歧 义的、精确表达的系统，而线图具有的二义性特点将导致计算机系统产生 多种空间结构的理解。此外由于不可避免的外界因素导致的线图误差，也 可能使计算机得出线图对应的三维立体不存在结论。所以计算机自动解释 线图的首要任务就是要解决线图由抽象性、非独立性、歧义性和非精确性 向计算机系统所要求的具体性、无歧义性和精确性的跨越。 本论文的研究工作主要分为三个方面：( 1 ) 基于v c + + 6 0 平台利用 o b j e c t a r x 应用程序对a u t o c a d 软件所绘制二维投影线图( d w g ) 基元信 息进行提取；( 2 ) 基于线线约束关系进行线图计算机自动解释线图，即恢 复投影线图的三维结构；( 3 ) 针对含有节点位置误差的线图进行循环迭代 校正处理，是重构后所的三维实体的重投影线图与原线图结构上尽量的接 近 t 太原理工大学硕士研究生学位论文 此外，本文介绍了“流形”平面立体投影线图的标记理论并详细并阐 述了符合人类画图习惯的标记方法，对平面立体结构信息的表达方式做了 详细的介绍；讨论了线图中二维直线，空间直线的表示方法优缺点，为线 图解释工作选择了最佳的线段表达方式；论述了多边形凸凹性的判别方法， 提出了一种去除凹点来判别线段凸凹性的新方法。 论文的创新点：本文所提出的基于线线关系解释线图的方法充分利用 了直线元素提取方便、表达简单、相对误差较小的特点，相对于点线关系、 点面关系解释线图的方法具有误差小、运算过程简单、准确性高的优点。 此外本文针对含有节点位置误差的线图，建立了合理的误差评定函数，在 针对线图解释的误差进行了分析研究的基础上提出了一种基于迭代反馈技 术的误差修正：算法，并运用实验证明了其合理性。 关键词：线图解释，元素提取，多边形凸凹性，三维重构，误差校正 太原理工大学硕士研究生学位论文 c o m p u t e r 烈t e r p i t e 仉气t i o na n dn o i s e c o r r e c t i o no fl i n ed ra w i n g sf o r r e p r e s e n t i n gp l a n a r0 b j e c t s a bs t r a c t c o m p u t e ri n t e r p r e t a t i o no fl i n ed r a w i n g si s a ni m p o r t a n tr e s e a r c ht o p i ci n c o m p u t e rv i s i o na n dr e v e r s ee n g i n e e r i n g p e o p l eu s el i n ed r a w i n g st od e s c r i b e 3 一do b je c t si nm a n yc a s e s ，w h i l eal i n ed r a w i n gi sc o m p o s e db ys o m es t r a i g h t l i n es e g m e n t s ，i tc o n t a i n sal o to fi n f o r m a t i o no f3 一do b j e c t s i th a sl o n gb e e n c o m m i t t e dt o2 一de x p r e s s i o no ft h e3 一do b j e c t si nd e s c r i p t i v eg e o m e t r yw h i c h h a sf o r m e dam a t u r et h e o r ya n dm e t h o d s ，b u ti t si n v e r s ep r o b l e m3 一d r e c o n s t r u c t i o no ft w o d i m e n s i o n a ll i n ed r a w i n g si ss t u d i e dn m c hm o r el a t e h u m a n sc a nu s et h e i rh i g h l y d e v e l o p e d v i s u a l s y s t e m t oo b t a i nt h e t h r e e d i m e n s i o n a li n f o r m a t i o ne x p r e s s e db yl i n ed r a w i n g s ，b u tt h ec o m p u t e ri sa s p e c i f i c 、u n a m b i g u o u sa n da c c u r a t e l ys y s t e m ，t h e r em a yb e a v a r i e t y o f u n d e r s t a n d i n g i na d d i t i o n ，l i n ed r a w i n g sc o r r e s p o n d i n g3 一do b j e c t sm a yn o t e x i tb e c a u s eo ft h eu n a v o i d a b l ee x t e r n a lf a c t o r s t h e r e f o r e ，t h ep r i m a r yt a s ki s t om a k et h ei n f o r m a t i o no fl i n ed r a w i n g st ob es p e c i f i c 、u n a m b i g u o u sa n d a c c u r a c y i nt h i st h e s i s ，t h em a i nw o r kc a nb ed i v i d e di n t ot h r e ep a r t s ：t h ef i r s tp a r ti s t oe x t r a c ti n f o r m a t i o no fl i n ed r a w i n g sd r a w nb yc a ds o f t w a r eb yo b j e c t a r x a p p l i c a t i o n b a s e do n v c + + p l a t f o r m t h e s e c o n dp a r ti sl i n e d r a w i n g s i n t e r p r e t a t i o nb a s e do nl i n e l i n ec o n s t r a i n t s t h et h i r dp a r ti s t oc o r r e c tl i n e d r a w i n g sw i t hn o i s e ，t om a k et h eo r i g i n a l l i n ed r a w i n g sc l o s e s tt ot h er e a l p r o j e c t i o no f3 一de n t i t y i i i 太原理工大学硕士研究生学位论文 i n a d d i t i o n ，t h i st h e s i s d e s c r i b e dm a r k u pt h e o r ya n dm e t h o do ft h e d i m e n s i o n a lm a n i f o l dl i n ed r a w i n g s d i s c u s s e dt h ee x p r e s s i o na d v a n t a g e sa n d d i s a d v a n t a g e so ft h e2 一ds t r a i g h tl i n ei nl i n ed r a w i n g sa n d3 - ds p a c es t r a i g h t l i n e p r o p o s e dad i f f e r e n t i a lm e t h o d o f p o l y g o n c o n v e x = c o n c a v e p r o p e r t y i n n o v a t i o no ft h ep a p e r ：t h em e t h o do fi n t e r p r e t i n gl i n ed r a w i n gi nt h i s p a p e rm a k e f u 1u s eo fc h a r a c t e r i s t i c so ft h el i n e a re l e m e n t sw h i c hi sf a c i l i t a t et o e x t r a c t 、s i m p l et oe x p r e s s c o m p a r i n gw i t ht h ep o i n t l i n ea n dp o i n t f a c e c o n s t r a i n t st o i n t e r p r e tl i n ed r a w i n g s ，t h el i n e l i n em e t h o dn o to n l yh a ss m a l l e r r o rb u ta l s ol h a v es i m p l eo p e r m i o na n d h i g ha c c u r a c y i na d d i t i o n ，f o rt h el i n e d r a w i n gw i t hn o i s e ，w es e tar e a s o n a b l ea s s e s s m e n tf u n c t i o na n dp r o p o s e da n e r r o rc o r r e c t i o n a l g o r i t h m b a s e do ni t e r a t i v ef e e d b a c kt e c h n o l o g y t h e e x p e r i m e n tp r o v e di t sr a i o n a l i t y k e yw o r d s ：l i n e d r a w i n g si n t e r p r e t a t i o n ，e l e m e n t se x t r a c t i n g ，p o l y g o n c o n v e x c o n c a v ep r o p e r t y ，3 一dr e c o n s t r u c t i o n ，n o i s ec o r r e c t i n g i v 太原理工大学硕士研究生学位论文 1 1 前言 第一章绪论 线图是人与人信息交流的重要媒介之一，同时也是科技、文化交流的重要媒介，特 别是在工程技术领域线图已经成为设计者思维存储与交流的通用载体。尽管线图只是一 些简单的直线和曲线的组合，但它却能够承载大量的信息。经过人类大脑对其所承载信 息的分析与积累，它就不是简单的直线或曲线，而成为一种真实的三维形体。对于高度 发达的人类视觉系统而言，理解一幅线图它所表达的真实三维结构十分简单。如果存在 大量的复杂的线图，仅仅依靠人工去识别也必将存在很大的困难。随着社会的发展和科 学技术的进步，计算机在工程技术领域被广泛应用，人们便考虑使用计算机这种工具来 模仿人的视觉系统，来处理类似于线图解释等一些繁杂事务。 在许多重要的研究领域线图已成为种信息交流和传承的媒介，方便、快捷、准确 的解释图形与图像彰显出越来越重要的作用。图像处理研究的主要问题之一就是将草图 或者图像转换为普通线图，现已研究出许多将草图或图像形式转换为线图形式的理论方 法及软件系统。j e n k i n s 设计的草图输入和整理软件不仅可以自动检测草图是否对称，还 可以添加平行、垂直等一些特殊约束条件，但软件无法完成草图的解释。m i t a n i 在前人 工作的基础上设计出一款名叫j m s k e t c h 的程序可以轻松的将草图转化成线图。p a v l i d i s 所设计的程序通过添加线段长度相等、斜率一致及共线性等约束条件的方式来对草图进 行美化，此程序系统要求具备一些避免缺陷的负约束条件。计算机视觉的研究目的就是 利用计算机能够处理大量复杂信息的功能，实现机器代替人的眼睛和大脑对客观世界进 行视觉感知和解释。虽然人类可以通过高度发达的视觉系统很容易的理解一幅线图所要 表达的内容，但对于计算机而言，如果不采取一定的措施，计算机所理解的就只是一些 直线与曲线的集合。计算机主要依靠光学成像系统来观察外部世界，光学成像系统来获 得外界的信息主要经过以下几个阶段：第一步获取图像中的点、线、面( 区域) 以及 纹理等信息；第二步利用线图中已知的二维信息解释物体获取的三维结构信息；第三 步获得三维空间的直观形体结构。所以为了是计算机能够模仿人的视觉系统，就需要 1 太原理工大学硕士研究生学位论文 给计算机设定定的感知思路，但我们所设定的感知思路无法完全模拟人的视觉系统。 计算机辅助设计( c a d ) 系统给人类的科技发展和生产生活带来了巨大的帮助，人 们可以利用c a d 系统去描述自己的思维并可以将其以实体的形式保存下来。由于科技 水平的限制，当今的c a d 系统仍然存在着一定的不足，设计者的思路往往简单线图的 形式记录，如何将设计者的思路转换成直观的实体形式存储在计算机中是c a d 系统所 面临的重大问题，如果仅靠人工来完成这项工作，会耗费巨大的人力、物力和财力并且 往往会因为人的不同而产生一定的差异，如能够利用计算机来完成这项工作将大大降低 人类的劳动强度并且会避免同一幅线图因人不同而产生的理解差异。 1 2 线图研究的基本内容及其基本假设 常见的线图根据是否含有不可见棱线，分为自然线图和画隐线图两种。所谓线图解 释就是根据物体或场景的投影图像理解三维物体的真实形态，本文的所研究的线图如不 作特殊说明均指平面立体的投影线图。在日常生活中，线图往往具有二义性，这就要求 我们要利用日常生活常识对计算机识别系统加以“锻炼”。为排除自然线图的二义性， 即所研究的立体为真实的平面立体、解释的线图为真正的轴测投影图( n - i 含微小误差) ， 我们需要作如下假设： 假设l 对于投影线图中的任何一平面，它的一侧为有形物质另一侧为空，所以研究 对象不能为片状物体； 假设2 投影图中仅画出三维立体上的棱线和顶点的平面投影，在投影图中可见棱 线和轮廓线用粗实线表示，不可见棱线和轮廓线用虚线表示； 假设3 轴测投影时平面立体上的棱线不能平行于物体的投影方向，即直线的投影不 能为一点，面的投影不能为一条直线； 假设4 任意一条直线的投影不能与另一条直线的投影重合，即两条直线的投影不 能落在同一条直线上； 假设5 三维物体上任意一条棱线均属于两个面，即研究对象为三维“流形”物体。 2 太原理工大学硕士研究生学位论文 1 3 线图解释的研究概况 三维物体的二维线图一直是画法几何和射影几何所研究的对象，它们通常采用线性 投影的方法来研究给定对象的二维平面表达。 线图解释研究始于2 0 世纪6 0 年代，r 0 b e n s 【1 】设计的三维物体识别系统可从线图中 识别几种常见的平面立体。g u z m a n 算法采用区域分割的方法可以对一幅比较复杂的立 体线框图进行识别分析。h u f h a i l 【2 】和c l o w e s t 3 1 分别提出了线图中棱线的标记方法并给 出了线图的合理节点形式，称为h u f f m a n - c l o w e s 节点标记法，这种标记法主要从考虑 线图的几何结构与拓扑结构的一致性方面考虑，但其只适用于自然线图的标记。t u r n e d 4 】 将节点标记法的标记范围扩充到光滑平面立体的投影图。s u g i h a r a 嘲利用线图标记的机 理，提出了一种类似于h u f f m a n c l o w e s 的标记法来对线图进行解释，该标记方法可以 标记画隐线图，但其中隐藏线的画法有些不符合人们的画图习惯。d i n g 在基于s u g i h a r a 标记法的基础上对含有l 型节点的不完整线图进行了细致的分析，但他所给出的l 型节 点的补线方法所得到的完整线图不符合一般线图表示的习惯。鲁1 6 给出了符合人类画图 习惯的线图标记方法，但对曲面三维投影节点的类型标记形式过于复杂。c h a k r a v a r t y 提出了一种可以对许多的曲面立体节点进行标记的节点标记方法，l e e 在c h a k r a v a r t y 基础上提出了曲面立体上曲线元素的标记方法。c o o p e r 7 9 对曲面物体的投影线图标记研 究做了比较全面的分析并提出了降低线图标记算法复杂度的新方法。董从节点和线段的 标记方法入手，针对l 型节点和“一”字型节点进行了分析并提出了合理的线图完整方法。 利用“正交假设”b a m a r d 1 0 】提出了一种解释透视投影图的算法，并且推导出了非 线性约束关系式。利用梯度空间垂直原理m a c k w o r t h 1 】推导出了线图平面方向的定量约 束。利用投影图的标准变换k a n a t a n i 【1 2 】推导出了长度和角度的约束关系式，并且提出了 解释正交角点的算法。利用线图的h o u g h 空间的特征e n g e l b r e e h t 1 3 对面识别方法进行 了论述。m a r i l l 1 4 】针对含有噪声和不完整线图提出了一种从单幅线图重构三维实体的优 化方法。m a r i l l 的方法将解释线图的范围扩大到非平面物体及不完整物体，但他没有证 明出其方法的正确性，只是给出了一些比较优秀的线图解释实例。y v a n 和l e c l e r c 1 5 】在 m a r i l l 方法的基础上提出了更好的优化方法，特别是l e c l e r c 给出了m a r i l l 实例成立的理 论依据并指出了所存在的不足及修正方法。l i p s o n 1 6 】在目标函数中考虑了线的平行性、 3 太原理工大学硕士研究生学位论文 斜对称、垂直交点等特殊约束，但这种优化为非线性优化，并且对特殊约束的优先次序 的选取将会决定收敛性的快慢，若选取不当有可能导致收敛速度慢或甚至不收敛的情况 发生，最终可能陷入局部优化仅获得局部最优解。封【1 7 1 通过对节点误差设置阈值，提出 了一种针对含有节点误差线图的校正解释方法。 曲【1 8 】定义了一种新的空间直线表示方法，该种新定义含有6 个参数( 1 ，m ，n ，p ，q ，r ) ， 基于这种空间：直线表示方法，并提出了基于直线的平面立体解释理论和方法。 s h i m s h o n i 1 明在图像特征和模型特征假设匹配的算法识别处理概率的基础上，提出了随 机三维物体的识别方法。 p o n c e 2 0 提出了一种节点不确定性理论，即认为线图中节点的正确位置是在一定的 范围内变化的，并根据s u g i h a r a 提出的算法获得一系列的非线性的等式与不等式，尽管 利用一些技术手段可将非线性等式或不等式线性化，但不满足线图为空间物体真实投影 的充分必要条件的需求。r o s 2 1 1 提出了一种利用可分解序列技术解释线图中过约束问题 的算法。p o n c e ：翻提出了一种利用不连续曲面法矢的轮廓及遮挡轮廓来识别三维物体的 新算法。 1 4 线图解释中存在的问题 尽管计算机解释线图发展迅速并取得了不错的成绩，但还存在着许多的问题有待完 善，主要表现在以下几个方面： ( 1 ) 研究对象局限于三面顶点的投影线图。三面顶点物体仅是一种特殊情况，对 于一般物体来说往往还存在着非三面顶点( 四面顶点、五面顶点、k 型顶点等) ，现在 部分研究已经允许研究对象中存在少量的非三面顶点。 ( 2 ) 线图标记研究局限于完整画隐线图，由于噪声、光照、纹理等因素的差异， 从图像或图形中提取到的线图往往存在着缺线或者遗漏节点的情况，此外设计师在绘制 复杂物体的线图时，由于自身和外界因素的影响往往会出现一些遗漏或者多绘制线段的 情况。为满足实际工作对线图的完整性要求，便需要对不完整的线图进行解释分析使其 完整，但目前对于不完整线图的研究关注还比较少。 ( 3 ) 当线图遗漏节点时，经过补充完整的线图其节点位置往往是不正确的，节点 4 太原理工大学硕士研究生学位论文 的位置严重影响物体的三维重建结果，所以校正含节点位置误差的线图需要予以重视。 ( 4 ) 综合利用点线面约束关系能为三维重构研究工作提供更多的约束条件，但是 约束条件越多所得的线性系统就会越复杂，导致其解的误差就会越大，所以如何合理有 效的利用点线面的约束关系亟需深入研究。 ( 5 ) 画隐线图重构三维物体过程中，对于完整画隐线图因其无法判定线图中的线 和节点是否存在误差，若不对线图进行预处理直接进行重构处理很可能无法得到正确的 结果，所以对线图进行误差判别与预处理是十分必要的。 ( 6 ) 含误差线图重构物体的三维结构时，大多没考虑几何元素之间的位置关系和 度量关系，如棱线之间的平行或者垂直、棱线具有特定长度等。若考虑元素之间存在的 特殊关系，便得到一非线性系统的约束关系使问题变复杂化，如何合理的利用这些元素 之间的特殊关系需要进一步的研究。 1 5 本论文的主要研究内容 从图形图像中理解三维空间中的物体，对于人类视觉而言是非常容易的事情，计算 机系统是一个完全具体的、无歧义的、精确表达的系统，由于线画图具有二义性的特点， 一幅线图往往会有多种不同空间结构的理解，此外受视觉误差、噪声等不可避免的外部 因素的影响往往导致的线图中含有微小的误差，所以用计算机来模拟人类的视觉系统进 行三维物体的识别是一件十分困难的工作。 由于投影线图忽略了表面材质等细节，所以物体的线图只能描述工程物体的形态。 在设计阶段的初期，设计者所绘的草图( 线图) 往往不准确或有错误；由于噪声、光照、 纹理等因素的影响，从图像中的抽取物体的线图一般是杂乱无序且往往存在着少线、多 线的现象。为便于恢复三维物体的结构，需要对线图进行分析和处理，删去多余的线、 补上缺少的线。二维线图的三维重构要满足一定的几何关系，经过删补处理之后所得到 的完整线图往往存在着一定的位置误差，所以必须对其位置进行校正处理，以便于后续 恢复三维物体结构的顺利进行。 线图的解释主要分为定性分析和定量分析两个方面的内容。线图的定性分析是指对 线图元素( 节点、棱线) 的标记及完整处理；线图元素( 点、线、面) 之间的约束关系 及其对应的三维结构的重构处理称为线图的定量分析。 5 太原理工大学硕士研究生学位论文 计算机解释线图的基本流程： 图1 1 线图解释流程图 f i g u r e l 1p r o g r a mc h a r to f l i n ed r a w i n g si n t e r p r e t a t i o n 本文基于线图的线线关系对完整画隐线图进行解释，首先利用o b j e c t n r x 应用软件 提取d w g 格式的平面图形的点、直线等基元信息，利用平面线图基元与其所对应的三维 立体之间的约束关系建立约束方程，求解约束方程得到三维物体的基元信息，最后根据 三维信息重构三维立体，此外本文还针对含有微小误差的线图进行校正处理，使之能够 顺利恢复出其对应的三维结构。本论文的主要研究工作主要分为三个方面：( 1 ) 提取二 维线图的基元信息：( 2 ) 基于约束关系利用计算机自动解释线图( 恢复线图所对应的三 维结构) ；( 3 ) 针对有误差线图进行分析和研究，提出误差的修正方法。 1 6 本论文章节内容安排 第一章：绪论。介绍计算机视觉及计算机解释线图所研究的内容及其对人类生产和 生活带来的巨大帮助，然后从定性分析和定量分析两个大方面阐述计算机解释线图发展 现状、取得的成果以及存在的问题。文中给出线图解释研究的方法及基本步骤，并着重 从定性分析方面阐述含有误差完整画隐线图的研究方法及发展历程。 第二章：平面立体完整画隐线图的标记理论。首先给出线图解释研究过程需要的一 些条件约束，然后介绍“流形”平面立体投影线图的标记理论并详细阐述符合人类画图 习惯的标记方法，之后又对平面立体结构信息的表达进行详细的阐述。 第三章：直线表示及线图中直线段参数的提取。首先给出平面二维和空间三维直线 的表示原则，列举平面直线与三维直线的常见表示方法，并对每种方法的优劣做出评价， 最终确定投影线图的二维线图和三维线图最佳表示方法。其次，给出利用o b j e c t a r x 提 取a u t o c a d 软件所绘线图中直线段端点坐标的方法，并针对线段在坐标系中不同位置 6 太原理工大学硕士研究生学位论文 情况，对线图中节点、直线和由直线所围成的区域建立了不同的链表，进而获得线图的 拓扑结构。 第四章：从画隐线图识别面。首先介绍从画隐线图识别面的一些基本定理及推论， 其次阐述一种多边形凸凹性的判别方法，并提出一种去除凹点来判别线段凸凹性的新方 法。最后阐述从画隐线图搜索回路的递归算法，通过对所得回路集合的修枝和处理，最 终得到线图的真实面。 第五章：基于线线关系的完整画隐线图解释。首先给出正轴测投影线图中平面直线 与空间直线之间的约束关系及其证明过程，并通过线线之间的约束关系对完整画隐线图 的三维实体结构进行恢复，并用实例证明其有效性一。 第六章：含误差完整线图的校正处理。经过删补处理的不完整画隐线图，往往具有 边缘外部轮廓位置比较准确，内部轮廓位置误差相对较大的特点。针对这一特点，提出 一种基于线图内部元素之间约束关系来校正处理含误差完整画线图的方法。从隐含的平 面立体信息之间的约束关系及平行、垂直等特殊关系，建立相应的约束方程，然后平面 线图节点位置进行最优位置的迭代i 处理，直至满足设定的阈值，并通过实验证明此方法 是有效性。 第七章：工作总结及展望。 7 太原理工大学硕士研究生学位论文 8 太原理工大学硕士研究生学位论文 第二章平面立体完整画隐线图的标记理论 在工程设计中，二维线图是描述三维物体最简单、最直观、最普遍的方法，是人与 人以及人与计算机之间信息交流的一种重要媒介。人类高度进化的人视觉系统对二维线 图的理解比较容易，但对于计算机而言却存在非常大的难度。计算机视觉系统在自动分 析和理解物体三维物体场景图像时一般分为以下两个步骤：( 1 ) 三维物体的线图的提取， 常采用的技术手段有边缘分析、区域描述、图像分割等；( 2 ) 线图元素的标记处理及线 图所对应三维元素信息的获取。有些线图具有多义性，若想用计算机自动解释线图往往 要用到生活中的一些常识，必须对计算机进行必要的训练。为了排除线图的多义性及避 免病态情况的出现，需要对所研究线图做出一些必要的假设和人为的设定。 2 1 线图标记理论的基本假设 线图是指由一定数量有序节点和直线段的集合。本论文所提及的线图均为“流形” 平面立体的完整投影线图，线图中的直线段为三维立体的平面投影称为棱线；线图中直 线段之间的交点称为节点，本文所指的交点必须为线图所描述三维物体顶点的平面投影。 针对本文研究内容将提出如下假设： 假设1 对于投影线图中的任何一平面，它的一侧为有形物质另一侧为空，所以研究 对象不能为片状物体。 假设2 本文研究对象为“流形”物体的棱线及顶点在平面的投影所形成的线图。用粗 实线表示线图中可见棱线，虚线表示线图中的不可见棱线，不予考虑物体表面纹理特征 及物体材质。 假设3 三维物体上每个顶点属于且仅属于物体上的三个平面，也就是说平面立体上 每一个节点都是三个平面的交点的投影。 假设4 轴测投影时平面立体上的棱线不能平行于物体的投影方向，即直线的投影不 能为一点，面的投影不能为一条直线。在平面空间中不在直线上的点要求其投影不能位 与该直线的投影重合，也就是说平面立体某一顶点的平面投影不能与平面立体中不过该 顶点的棱线的平面投影重合。 9 太原理工大学硕士研究生学位论文 假设5 空间中任意两条直线的平面投影不能重合或部分重合，也就是说平面立体上 任何一条棱线的投影不能与其他棱线的投影重合或部分重合，并要求位于空间中不同顶 点的任意三条直线的投影不能共点。 2 2 线图的分类与标记 根据线图中是否画出不可见棱线可将线图分为自然线图和画隐线图两大类。根据线 图是否存在多余棱线或者缺少棱线线图分为完整线图和不完整线图两大类，其中完整线 图为不存在多线或者缺少棱线的线图：不完整线图为含有多余棱线或者缺少棱线或既存 在多余棱线又缺少棱线的线图。 图2 1 自然线图图2 - 2 画隐线图 f i g u r e 2 - 2l i n ed r a w i n gw i t hh i d d e nl i n e 图2 3 存在多余线的线图图2 _ 4 缺少棱线的线图 f i g u r e 2 3l i n ed r a w i n gw i t hr e d u n d a n tl i n ef i g u r e 2 - 4l i n ed r a w i n g sw i t hl e s sl i n e 平面立体的诸多结构信息大多都包含在棱线和节点所组成的投影线图中，但对于曲 面立体而言，一般情况下线图并不能表达足够的结构信息。本论文的研究对象为平面立 体，h u f f i n a n 和c l o w e s 针对平面立体的棱线不同结构，对棱线的类型进行了符合人类 认知习惯的化分。两个相交的平面将平面空间分为4 个区域，本文将这些区域称为象限， 这四个象限分别称为i ，如图2 5 所示； 1 0 太原理工大学硕士研究生学位论文 图2 - 5 空间象限图 f i g u r e 2 5f i g u r eo fs p a c eq u a d r a n t 在本论文中设定观察者总是位于第1 象限，也就是说观察者都是从第1 象限来观察 研究对象。根据属于相交于该棱线的两个平面与观察者相对位置，s u g i h a r a 将投影线图 中的棱线分为如下8 种类型： 圃句同 ，一 一一 一一 ( 1 )( 2 )( 3 )( 4 ) 国目国 ( 5 )( 6 )( 7 )( 8 ) 图2 - 68 种棱线标记 f i g u r e 2 6l a b e l i n gm e t h o do fe i g h tk i n d so fl i n e s 图( 1 ) 为两个面可见面的交线，本文称之为凸棱，用“+ ”表示。 图( 2 ) 和图( 3 ) 中为一个可见面与一个不可见面的交线，本文称之为遮挡棱，用 “_ 表示。沿箭头的方向表示两个面总是位于棱线的右边。 图( 4 ) 中为两个可见面的交线，本文称之为凹棱，用“一 表示。 如果线图为自然线图，那么用( 1 ) ( 4 ) 前四种类型就可以描述。 通过充满有形物质所在象限与空所在象限的互换可得到图( 5 ) ( 8 ) 四种棱线类 型，图中的不可见棱线采用虚线表示。 在将一幅线图中的所有棱线做出正确标记之后，相当于选定了线图所能表示三维物 1 1 太原理工大学硕士研究生学位论文 体集中的某一类型。若不需考虑线图所能表示三维物体的物理意义的真实性，那么含有 n 条棱线的线图在理论上应具有8 n 种不同类型的标记方案。但所得线图标记方案中所表 示的绝大多数三维实体是没有物理意义的，即线图所表示的三维实体为“非流形 三维 实体，也就是说只有极少数线图标记方案为具有物理意义的三维“流形弦实体。 一般平面立体的顶点为3 个平面的交点或3 个以上平面相交形成的交点，本文将由 3 个平面相交形成的顶点称为三面顶点。若平面立体上的顶点全部为三面顶点构则称该 平面立体为三面顶点平面立体。 在三顶点平面立体中相交于一个顶点的三个平面将立体空间分割为8 个区域，如图 2 7 所示： 图2 7 平面立体区域 f i g u r e 2 - 7d i v i s i o no fd i m e n s i o n a lr e g i o f l 如果忽略节点标记方案对三维物体物理意义的影响，w 型节点将有多达5 1 2 种不同 标记方案，y 型节点将有多达1 7 6 种不同标记方案。s u g i h a r a 根据棱线标记方案的分类 方法将线图中所有可能的节点结构进行了具体分类，最终得出了具有真实物理意义的2 4 种合法节点标记方案，具体方案如图2 - 8 。 图2 8 中所列举的2 4 种节点类型可分为两大类型，一类是y 型节点：另外一类是 w 型节点。所谓y 型节点是指交于一点的三条棱线中任意两相邻棱线之间的夹角均小 于7 c ；w 型节点是指交于一点的三条棱线中任意相邻两棱线间的三个夹角有且只有一个 大于兀。由图2 - 8 我们可知s u g i h a r a 的给出的2 4 种节点类型中有8 种合法的y 型节点 和1 6 种合法的w 型节点类型。 1 2 太原理工大学硕士研究生学位论文 _ - 一_ - _ - _ 一 、一一， 、 、 丫 i l 、 寸 、 - - i - 七， ， 、 、寸牟 、。 i 1 1 - i - 、 ， 一 y l i i l ： 杪此舻v 、 i 一 ， - 、i - 、：彳 l ， o 、 ：十，、 、 i 一、二，一 图2 - 8 2 4 种合法节点 f i r g u e 2 8l a b e l i n gm e t h o do f 2 4k i n d so f j u n c t i o n s 2 3 完整画隐线图的标记算法 2 3 1 棱线代码 本论文用代码1 8 来记录线图的8 种棱线，代码与棱线的对应关系如表2 一l ： 表2 1 棱线代码表 1 3 ， 一 ，：一 、 户 一 ， ：一 ， ， 、， l b ， 、 太原理工大学硕士研究生学位论文 r 出l e 2 1l i n ec o d e s 2 3 2 节点代码 本论文中按顺时针方向对属于节点的3 条棱线依次标记形成如表2 2 的节点代码： 表2 - 2 节点代码表 t a b l e 2 - 2j u n c t i o nc o d e s 弋彳 、弋一，f 、彳 。弋广，c。v 节点 i + l l + i i _ l i i 代码i l l2 忿3 3 3 4 4 45 6 2 5 6 4 节点 y 、，7 k k 也 t l + i 一i ： 卜l4妙 l 代码 7 8 37 8 45 1 61 2 l2 1 25 3 6 l k t 节点n ，l l ， 、 、苎 代碡1 5 87 6 l5 8 22 7 63 4 34 3 幸 l l i _ i 、土一上； 、也 、土一， 节点 、上一、三一- 7 代爵7 髓7 3 83 7 87 8 37 8 44 7 8 因不需要考虑棱线的顺序问题，所以y 型节点的代码4 2 3 和3 2 4 表示的是同一种代 码形式。而在w 型节点中需要考虑哪两条棱线之间的夹角大于7 1 ；，即需要考虑棱线之间 的顺序问题，历i 以上图中w 节点的6 7 8 ，7 8 6 和7 6 8 表示的是三种不同的形式。 2 3 3 完整画隐线图的标记步骤 线图标记时，首先将线图的外围轮廓线标以顺时针方向的箭头，按照线图标记唯一 性的原则，利用约束传播的原理将节点由外向里逐步标记相邻的节点，直至整个线图所 1 4 太原理工大学硕士研究生学位论文 有节点标记完成。 完整画隐线图的基本标记步骤为t ( 1 ) 线图外围轮廓及节点的标记。从中我们可以发现线图中的极限点( 最高点、 最低点、最左点和最右点) 一定在线图外围轮廓线上，并且都属于w 型节点。 本论文选取线图最左侧的最低点作为搜索线图外围轮廓的起始点，以最低点为原点 o ，向右水平线为x 轴正向建立右手直角坐标系o x y ，计算与此节点相连接的三条棱 线与x 轴正方向的夹角( 夹角定义为将x 轴绕原点o 逆时针旋转，x 轴与节点所连接 棱线重合时所转过的角度，角度范围为0 , - , 1 8 0 。) ，按顺时针方向寻找与x 轴夹角最大的 棱线即为所求的第一条外围轮廓线。然后以所得到的棱线的另一端作为原点建立新的坐 标轴，利用如上的方法进行下一条棱线的搜索，直至搜索回到线图的起点为止。这便完 成了线图的外围轮廓及节点的标记。 ( 2 ) 线图的内部棱线及节点的标记。根据节点的合法标记形式及约束传播原理由 外围轮廓线及节点逐层标记线图的内部棱线及节点。通过这一步便完成了“流形”平面 立体投影完整线图的部分棱线及节点的标记。 一幅“流形 平面立体的完整投影线图一定有符合合法节点和棱线形式的一致性标 记。本文提出的“流形”物体的线图必须是完整的，即线图中不存在缺线或者多线的情况， 对于不完整线图上述的标记方法不在适用。 2 4 线图的结构 线图中的节点是三维立体的顶点在平面上的投影，线图中的线段是三维立体上的棱 线在平面上的投影，线图中直线段首尾相连围成的闭合回路所包围的区域一般是三维物 体上某一表面的在平面上的投影。投影线图与三维实体之间是不可逆的，从单幅线图解 释三维实体往往会得到许多不同的结果，然而线图为三维物体的在平面上的投影，通常 包含了三维物体的某些三维特性，且往往隐含了三维物体的一些几何结构和拓扑信息。 2 4 1 线图的平面结构 一幅标记后的画隐线图可以用数据结 1 5 太原理工大学硕士研究生学位论文 d = ( v ，e ，f ，u 1 ，u 2 ，e v , e w ，f v ，f w ，f e ，f e e ，h ，i e ，c e ，c f ，c e f ，c v f ，r ) 来表示，该数据结 构描述了完整画i 隐线图的几何信息和拓扑结构，此数据结构称为线图的平面结构。平面 结构d 中各元素的具体含义： v 表示线图中所有节点组成的集合，线图中任一节点都是三维物体的顶点在平面上 的投影； e 表示线图中所有直线段组成的集合，线图中任一条直线段都是三维物体上的某一 棱线在平面上的投影： f 表示线图中直线段首尾连接形成的闭合区域所组成的集合，围成闭合回路的直线 段中可以包含实线、虚线，在经过识别面以后，满足条件的闭合回路就组成了线图中面 的集合，投影线图中的每一个面都是三维物体上表面在某一平面上的投影； u l 表示从节点v 到二维平面r 2 的映射，其中u l ( v ) 表示节点v 的坐标参数( x v y o ； u 2 表示从直线段e 到二维平面r 2 的映射，其中u 2 ( e ) 表示直线段e 的坐标参数 ( p e ，o e ) ： e v 表示线图中直线段元素e 与节点元素v 的附属关系，表示一组有序的直线段与 节点的元素集合，其中e v ( e lv ) 表示节点v 是直线段e 的一个端点； e w 表示一组有序顶点v 的元素所组成的集合，其中e w ( v l ，v 2 ) 表示棱线e 由节点v t 和v 2 连接而成； f v 表示线图中面与节点的附属关系，为一组有序的平面与节点所组成的集合，其 中f v ( f v ) 表示节点v 位于面f 的边界上； f w 表示一组有序节点v 的元素集合，其中f w ( v l ，v 2 ，v n ，v 1 ) 表示依序连接 节点( v 1 ，v 2 ，v n p v l ) 的所形成的直线段( e 1 ，e 2 一e n ) 是面f 的完整边界； f e 表示线图中直线段与面的附属关系，是一组有序的平面f 与直线段e 的元素集 合，其中f e ( f ：e ) 表示直线段e 是面f 的其中一条边界： f e e 表示一组有序直线段e 的元素集合，其中f e e ( e 1 ，e 2 ，e n ) 表示有序直线段 ( e 1 ，e z ，e n ) 是k 面f 的完整边界； h 表示线图中直线段e 的类型，即线图直线段标记所存在的8 种情况：线段的虚实 16 太原理工大学硕士研究生学位论文 及( + ，一，卜，_ ) ； i e 表示一组有序直线段e 的集合，其中i e ( e 1 ，e 2 ) 表示直线段e l ，e 2 在相交于节点； c e 表示一组有序的3 元集合，其中c e ( e 1 ，e 2 ，6 ) 表示直线段相交但不在线图节点 处相交，其中e 1 ，e 2 e ，6 ( b e h i n d ，f r o n t ) c f 表示一组有序的3 元集合，其中c f ( f l ，f 2 ，6 ) 表示两面f 1 ，f 2 部分重叠， f 1 ，f 2 f ，6 ( b e h i n d ，f r o n t ) c e f 表示一组有序的3 元集合，其中c e f ( e ，6 ) 表示直线段e 的部分或全部位于 面f 的内部，其中6 ( b e h i n d ，f r o n t ) ，e e ，f f ； c v f 表示一组有序的3 元集合，其中c v f “6 ) 表示节点v 位