基于线框模型的三维实体重构问题的分析与研究
|
摘要
多年来，由于三维实体的表示与重构在工业设计制造、建筑、航空航天及医学、生物学等领域的广泛应用，人们研究各种用于表示三维实体的方法以及基于不同方式和数据的三维实体的重构问题。
其中线框模型方法由来已久，但关于从线框模型描述重构三维实体的研究并不多见。主要原因是线框模型表示的不唯一性。通常描述的线框模型就可以定义多个不同的三维实体，取决于不同的观察者和不同观察的角度。虽然这一现象早已为人们所熟知，但由于线框模型形绘制比三维实体绘制快速、经济，因此线框模型仍作为图形表述的主要方法被广泛用于工业设计与制造领域。例如，工业制造商经常收到线框模型表示的三维实体文本数据，其中不附带任何的几何与拓扑描述信息。所以工业制造商需要将线框模型的文本数据自动转换成三维实体模型。因此重要的问题是转换处理必须是可行的或唯一的。
重构三维实体过程中，最重要是的线框模型的拆分。目前有两种方法：一种是把三维实体看成由多个多面体组成的，相应的方法是将线框模型拆分成多个多面体，然后进行多面体的拼接组合重构三维实体；另一种方法是把三维实体看作由多个面组成的，相应方法是搜索可行面并根据三维实体的特点来重构。
本文给出的基于线框模型重构三维实体求解算法，从三维实体的基本原则出发搜索由点、线组成的可行面，然后计算由可行面构成的三维实体。求解的三维实体满足欧拉公式点、线、面约束条件。由于三维重构是一个非常复杂的求解过程，一般算法很难在多项式时间内完成，本方法能够在多项式时间内完成，因此具有很高的理论和实际的价值。
There are tremendous papers evolving the problem of describing a 3D object and reconstructing a 3D object from different data and ways.
Although wire-frame has been applied to represent a 3D object for long time, extracting an object from a wire-frame has'not been studied fully. The main reason is a wire-frame usually cannot represent a unique 3D object. A wire-frame is possible to define several different 3D objects according to the vary observers and their observing direction. Although this phenomenon and assertion are well known, yet wire-frame as a graphics medium is still applied in some industry design and manufacture areas nowadays. It is because of that drawing a wire-frame is cheaper and easier rather than drawing a 3D object by solid modeling. For example manufacturing companies often receive order with files of wire-frame representing design of progressive stripe without any geometric and topologic description. From the point of view of manufacturing it is necessary to convert the wire-frame to the representation of 3D objects automatically. Actually the more important question that must be answered is feasibility and uniqueness o
f the conversion.
Extracting wire-frame is important when a 3D object is reconstructed. There are two methods are often used. A method is constructing some separate polyhedrons from vertex and edges of 3D wire-frame and combine the polyhedrons with each other one by one. Another is extracting wire-frame to some candidate faces and joining them up according to the nature of 3D object.
In this paper, an algorithm of reconstructing 3D object from wire-frame was put forward. The main idea is to search for feasible panels made of vertex and edges according to the elemental principles of 3D object, and reconstruct 3D object from feasible panels. The acquired 3D object satisfied the restrictive conditions of Euler formula. The common algorithms are difficult to solve the problem of reconstructing of 3D object because of the complexion of reconstructing of 3D object. In the paper, a method was first put forward to reconstruct 3D object from feasible panels, which is different from the idea of reconstructing 3D object from the polyhedrons, and it is easy to be applied in the industry areas.
其中线框模型方法由来已久，但关于从线框模型描述重构三维实体的研究并不多见。主要原因是线框模型表示的不唯一性。通常描述的线框模型就可以定义多个不同的三维实体，取决于不同的观察者和不同观察的角度。虽然这一现象早已为人们所熟知，但由于线框模型形绘制比三维实体绘制快速、经济，因此线框模型仍作为图形表述的主要方法被广泛用于工业设计与制造领域。例如，工业制造商经常收到线框模型表示的三维实体文本数据，其中不附带任何的几何与拓扑描述信息。所以工业制造商需要将线框模型的文本数据自动转换成三维实体模型。因此重要的问题是转换处理必须是可行的或唯一的。
重构三维实体过程中，最重要是的线框模型的拆分。目前有两种方法：一种是把三维实体看成由多个多面体组成的，相应的方法是将线框模型拆分成多个多面体，然后进行多面体的拼接组合重构三维实体；另一种方法是把三维实体看作由多个面组成的，相应方法是搜索可行面并根据三维实体的特点来重构。
本文给出的基于线框模型重构三维实体求解算法，从三维实体的基本原则出发搜索由点、线组成的可行面，然后计算由可行面构成的三维实体。求解的三维实体满足欧拉公式点、线、面约束条件。由于三维重构是一个非常复杂的求解过程，一般算法很难在多项式时间内完成，本方法能够在多项式时间内完成，因此具有很高的理论和实际的价值。
There are tremendous papers evolving the problem of describing a 3D object and reconstructing a 3D object from different data and ways.
Although wire-frame has been applied to represent a 3D object for long time, extracting an object from a wire-frame has'not been studied fully. The main reason is a wire-frame usually cannot represent a unique 3D object. A wire-frame is possible to define several different 3D objects according to the vary observers and their observing direction. Although this phenomenon and assertion are well known, yet wire-frame as a graphics medium is still applied in some industry design and manufacture areas nowadays. It is because of that drawing a wire-frame is cheaper and easier rather than drawing a 3D object by solid modeling. For example manufacturing companies often receive order with files of wire-frame representing design of progressive stripe without any geometric and topologic description. From the point of view of manufacturing it is necessary to convert the wire-frame to the representation of 3D objects automatically. Actually the more important question that must be answered is feasibility and uniqueness o
f the conversion.
Extracting wire-frame is important when a 3D object is reconstructed. There are two methods are often used. A method is constructing some separate polyhedrons from vertex and edges of 3D wire-frame and combine the polyhedrons with each other one by one. Another is extracting wire-frame to some candidate faces and joining them up according to the nature of 3D object.
In this paper, an algorithm of reconstructing 3D object from wire-frame was put forward. The main idea is to search for feasible panels made of vertex and edges according to the elemental principles of 3D object, and reconstruct 3D object from feasible panels. The acquired 3D object satisfied the restrictive conditions of Euler formula. The common algorithms are difficult to solve the problem of reconstructing of 3D object because of the complexion of reconstructing of 3D object. In the paper, a method was first put forward to reconstruct 3D object from feasible panels, which is different from the idea of reconstructing 3D object from the polyhedrons, and it is easy to be applied in the industry areas.
引文
[1] 陈志兰。CAD中的几何造型方法。民用飞机设计与研究，1997，(1) ：19-22。
[2] Michael E.Mortenson. Geometric modeling. John Wiley & Sons, Inc, July 1985
[3] David Salomon, D. Salomon. Computer Graphics and Geometric Modeling. Springer-Verlag New York, Inc, 1st, May 1999．
[4] Vera B. Anand. Computer Graphics and Geometric Modeling for Engineers. John Wiley & Sons, Inc 1st, February 1996．
[5] Michael E. Mortenson. Mathematics for Computer Graphics Applications: An Introduction to the Mathematics and Geometry of CAD/Cam, Geometric Modeling, Scientific Visualization. Edition:2nd May 1999．
[6] Hamid A, Kailath T. 'Subspace-based line detection'. IEEE Transactions on Pattern Analysis and machine Intelligence, 1994, 16(11) :1057-1073．
[7] Tamas Varady, Ralph R Martin and Jordan Cox, 'Reverse engineering of geometric models-an introduction', Computer-Aided Design, Vol.29, No.4, pp.255-268, 1997．
[8] Chivate , P N and Jablokow , A G, 'Solid-modelling generation from measured point data', Computer-Aided Design. Vol 25, NO 9,1993,587-600．
[9] Zhang Kuoliang, Computing horizontal/vertical convex shape's moments on reconfigurable meshes,Pattern Recognition. 1996,29(10) :1713-1717．
[10] Hoover, A, Goldgof. D and Bowyer, K W, 'Extracting a valid boundry representation from a segmented range images', IEEE PAMI, 17(9) ,1995,920-924．
[11] T Ranshi. Solid modeling in design and manufacture.. CAD/CAM Digest, volume 7, Issue 10-11． June 1986．
[12] 吴湘，赵万生，魏莉。三维几何表示法。航天制造技术，2002． 8，第4期。
[13] 万剑华，朱长贵．3D-GlS中空间对象的几何表示．矿山测量2001． 3：16-19．
[14] Srinivas Raghothama, Vadim Shapiro. Boundary representation deformation in parametric solid modeling. ACM Transactions on Graphics, volume 17,Issue 4, October 1998．
[15] Rappoport, A. The generic geometric complex (GGC): A modeling scheme for families of decomposed pointsets. In Proceeding of the Fourth ACM Symposium on Solid Modeling and Applications . 19-30 .Atlanta, GA, May 1997．
[16] Jeff Heisserman, Robert Woodbury. Generating languages of solid models. Proceedings on the second symplosium on solid modeling and applications, may 1993-may1993 Canada.
[17] 吴涛，刘金义。基于轮廓线的三维重建方法的研究。抚顺石油学院学报，Vol．19 No．3．
[18] Tamas, V, Ralph R M, Jordan C. Reverse engineering of geometric models-an introduction. Computer-Aided Design, 1997,4(29) :255-268．
[19] Idesawa Masanori. A system to generate a solid figure from three view. Bullletin of the Japan Society of Mechanical Engineering, 1973,16(92) :216-225．
[20] Gu Kaining, Tang Zesheng, Sun jiaguang. Reconstrucion of 3D solid objects from orthographic projection. Computer Graphics Forum, 1986,5(4) :317-324．
[21] Yan O, Chen C L P, Tang Z. Efficient algorithm for the recontruction of 3D object form orthographic projections. Computer Aided Design, 1994, 26(9) : 699-717．
[22] Shin Byeong-Seok, Shin Yeong Gil. Fast 3D solid modei reconstruction from orthographic views. Computer Aided Design, 1998,30(l):63-76．
[23] Kuo M H. Reconstruction of quadric surface solids from three orthographic view s[Ph D
thisis]. Department of Computer Science, University of Nottingham, UK, 1996.
[24] Gujar U G, Nagendra I V. Construction of 3D solid objects from orthographic views. Computer & Graphics,1989,13(4):505-521.
[25] 何昆，张德添，张学敏，杨怡，张飒，汪宝珍．生物组织细胞连续切片三维重建的研究进展。军事医学科学院院刊2000年第24卷第3期．
[26] 张义，李时光，杨恬．生物组织显微切片图像计算机三维重建的截面重建技术[J]．中国生物医学工程学报，1992，11(1)：17．
[27] 张显全，李自双，杨力，等．肝血窦连续切片的计算机三维重建[J]．生物医学工程学杂志，1997，14(2)：195．
[28] 陆惠民，颜坤，史美德，等．青蛙峡核的计算机三维重建[J]．解剖学报，1985，10(3)：303．
[29] 李叔梁，秦颂．三维逼真计算机图形的产生与显示[J]．清华大学学报(自然科学版)，1986，26(5)：10．
[30] 田村秀行．赫荣威译，计算机图像处理技术[M]．北京：北京师范大学出版社，1990．67～124．
[31] 陆惠民，王秀春，史美德，等．鸽峡核的计算机三维重建[J]．生物物理学报，1987，3(2)：162
[32] Nagendra I V, Gujar U G, 3-D objects from 2-D orthographic views-A survey[J]. Computers & Graphics,1998;12:111-114.
[33] Wang W D, Grinstein G. A surrevey of 3-D solid reconstruction from 2-D projection line drawings[J].Computer Graphics Forum,1993;12:137-158.
[34] Markow sky G, Wesley M A. Fleshing out wire frames.IBM Journal of Research and Development,1980, 24(5):582-597.
[35] 刘世霞，胡事民，陈玉健，孙家广。基于工程图的三维曲面体重建方法。第六界计算机辅助设计与计算机图形学会议论文集，上海，1999。1040-1044。
[36] J.Mukherjee, P. P. Das, B. N. Chatterji. An algorithm for the extraction of the wire frame structure of a three-dimensional object. Pattern Recognition, volume 23, Issue 9,September 1990.
[37] 公茂楷，高国安，石森。由三视图构造三维实体方法的综述。计算机研究与发展，1992．8。
[38] 霍瑜如。计算机辅助几何造型技术。机电设备，1997．6。
[39] 唐荣锡。《CAD/CAM技术》。北航出版社。
[40] 马利庄，王荣良。《计算机辅助几何造型技术及其应用》。科学出版社。
[41] Wang Jiaye, Chen Hui, Wang Wenping. A sufficient condition for a wire-frame representing a solid modeling uniquely. Journal of Computer Science and Technology, volume 16,Issue 6, November 2001. 595-598.
[42] Wang Jiaye, Wang Wenping .Reconstructing 3D Object from Wire-frame. To be published.
[43] Agarwal SC, Waggenspack Jr, WN. Decomposition method for extracting face topologies from wire-frame models. Computer-Aided Design 1992, 24(3):123-140.
[44] Hanrahan PM. Creating volume models from edge-vertex graphs.ACM Computer Graphics 1982, 16(3):77-84.
[45] Dutton RD, Brigham RC. Efficient identifying the faces of a solid. Computers and Graphics in Mechanical Engineering 1983,7(2):143-147.
[46] Hopcrdoft J, Tarjan, R. Efficient planarity testing. Journal of the Association of Computing Machinery 1974,21:549-568.
．
[47] Ganter MA, Uicjer JJ. From wire-frame to solid geometric:automated conversion of data representation. Computer in Mechanical Engineering 1983,2(2):40-45.
[48] Courter SM, Brewer JA. Automated conversion of curvilinear wire-frame models to surface boundary models, a topological approach. SIGGRAPH'86, ACM Computer Graphics 1986,20(4):171-178.
[49] Hojnichi JS, White PR. Converting CAD wire-frame data to surfaced representation.Computers in Mechanical Engineering 1988,March/April:19-25.
[50] Paton K. An algorithm from finding a fundamental set fo cycles of a graph. Communications of the ACM 1969, 12(9):514-518.
[51] M. H. Kuo. Automatic extraction of quadric surfaces from wire-frame models. Computer & Graphics 2001,25:109-119.
[52] Mantyla, M. An Introduction to Solid Modeling.Computer Science Press.Rockville, MD,1998.
[53] 朱仁芝，江涌，陶涛，刘磊。利用3维重建技术进行线框模型消隐的算法。计算机工程与应用。1998,5。
[54] Kate Gregory著，前导工作室译。Visual C++6开发使用手册。第1版。机械工业出版社，1999．6。
[55] 严蔚敏，吴伟民。《数据结构》。第2版。北京：清华大学出版社，1992。
[56] 马绍汉。《算法分析与设计》第1版。济南：山东大学出版社，1992。
[57] 彭晓明 王坚。《OpenGL深入编程与实例揭密》。第1版。北京：人民邮电出版社，1996．6。
[58] 左孝凌，李为 刘永才。《离散数学》。第1版。上海：上海科学技术文献出版社。1982．9。
[59] 孙家广，杨长贵。《计算机图形学》。第2版。北京：清华大学出版社，1995。
[2] Michael E.Mortenson. Geometric modeling. John Wiley & Sons, Inc, July 1985
[3] David Salomon, D. Salomon. Computer Graphics and Geometric Modeling. Springer-Verlag New York, Inc, 1st, May 1999．
[4] Vera B. Anand. Computer Graphics and Geometric Modeling for Engineers. John Wiley & Sons, Inc 1st, February 1996．
[5] Michael E. Mortenson. Mathematics for Computer Graphics Applications: An Introduction to the Mathematics and Geometry of CAD/Cam, Geometric Modeling, Scientific Visualization. Edition:2nd May 1999．
[6] Hamid A, Kailath T. 'Subspace-based line detection'. IEEE Transactions on Pattern Analysis and machine Intelligence, 1994, 16(11) :1057-1073．
[7] Tamas Varady, Ralph R Martin and Jordan Cox, 'Reverse engineering of geometric models-an introduction', Computer-Aided Design, Vol.29, No.4, pp.255-268, 1997．
[8] Chivate , P N and Jablokow , A G, 'Solid-modelling generation from measured point data', Computer-Aided Design. Vol 25, NO 9,1993,587-600．
[9] Zhang Kuoliang, Computing horizontal/vertical convex shape's moments on reconfigurable meshes,Pattern Recognition. 1996,29(10) :1713-1717．
[10] Hoover, A, Goldgof. D and Bowyer, K W, 'Extracting a valid boundry representation from a segmented range images', IEEE PAMI, 17(9) ,1995,920-924．
[11] T Ranshi. Solid modeling in design and manufacture.. CAD/CAM Digest, volume 7, Issue 10-11． June 1986．
[12] 吴湘，赵万生，魏莉。三维几何表示法。航天制造技术，2002． 8，第4期。
[13] 万剑华，朱长贵．3D-GlS中空间对象的几何表示．矿山测量2001． 3：16-19．
[14] Srinivas Raghothama, Vadim Shapiro. Boundary representation deformation in parametric solid modeling. ACM Transactions on Graphics, volume 17,Issue 4, October 1998．
[15] Rappoport, A. The generic geometric complex (GGC): A modeling scheme for families of decomposed pointsets. In Proceeding of the Fourth ACM Symposium on Solid Modeling and Applications . 19-30 .Atlanta, GA, May 1997．
[16] Jeff Heisserman, Robert Woodbury. Generating languages of solid models. Proceedings on the second symplosium on solid modeling and applications, may 1993-may1993 Canada.
[17] 吴涛，刘金义。基于轮廓线的三维重建方法的研究。抚顺石油学院学报，Vol．19 No．3．
[18] Tamas, V, Ralph R M, Jordan C. Reverse engineering of geometric models-an introduction. Computer-Aided Design, 1997,4(29) :255-268．
[19] Idesawa Masanori. A system to generate a solid figure from three view. Bullletin of the Japan Society of Mechanical Engineering, 1973,16(92) :216-225．
[20] Gu Kaining, Tang Zesheng, Sun jiaguang. Reconstrucion of 3D solid objects from orthographic projection. Computer Graphics Forum, 1986,5(4) :317-324．
[21] Yan O, Chen C L P, Tang Z. Efficient algorithm for the recontruction of 3D object form orthographic projections. Computer Aided Design, 1994, 26(9) : 699-717．
[22] Shin Byeong-Seok, Shin Yeong Gil. Fast 3D solid modei reconstruction from orthographic views. Computer Aided Design, 1998,30(l):63-76．
[23] Kuo M H. Reconstruction of quadric surface solids from three orthographic view s[Ph D
thisis]. Department of Computer Science, University of Nottingham, UK, 1996.
[24] Gujar U G, Nagendra I V. Construction of 3D solid objects from orthographic views. Computer & Graphics,1989,13(4):505-521.
[25] 何昆，张德添，张学敏，杨怡，张飒，汪宝珍．生物组织细胞连续切片三维重建的研究进展。军事医学科学院院刊2000年第24卷第3期．
[26] 张义，李时光，杨恬．生物组织显微切片图像计算机三维重建的截面重建技术[J]．中国生物医学工程学报，1992，11(1)：17．
[27] 张显全，李自双，杨力，等．肝血窦连续切片的计算机三维重建[J]．生物医学工程学杂志，1997，14(2)：195．
[28] 陆惠民，颜坤，史美德，等．青蛙峡核的计算机三维重建[J]．解剖学报，1985，10(3)：303．
[29] 李叔梁，秦颂．三维逼真计算机图形的产生与显示[J]．清华大学学报(自然科学版)，1986，26(5)：10．
[30] 田村秀行．赫荣威译，计算机图像处理技术[M]．北京：北京师范大学出版社，1990．67～124．
[31] 陆惠民，王秀春，史美德，等．鸽峡核的计算机三维重建[J]．生物物理学报，1987，3(2)：162
[32] Nagendra I V, Gujar U G, 3-D objects from 2-D orthographic views-A survey[J]. Computers & Graphics,1998;12:111-114.
[33] Wang W D, Grinstein G. A surrevey of 3-D solid reconstruction from 2-D projection line drawings[J].Computer Graphics Forum,1993;12:137-158.
[34] Markow sky G, Wesley M A. Fleshing out wire frames.IBM Journal of Research and Development,1980, 24(5):582-597.
[35] 刘世霞，胡事民，陈玉健，孙家广。基于工程图的三维曲面体重建方法。第六界计算机辅助设计与计算机图形学会议论文集，上海，1999。1040-1044。
[36] J.Mukherjee, P. P. Das, B. N. Chatterji. An algorithm for the extraction of the wire frame structure of a three-dimensional object. Pattern Recognition, volume 23, Issue 9,September 1990.
[37] 公茂楷，高国安，石森。由三视图构造三维实体方法的综述。计算机研究与发展，1992．8。
[38] 霍瑜如。计算机辅助几何造型技术。机电设备，1997．6。
[39] 唐荣锡。《CAD/CAM技术》。北航出版社。
[40] 马利庄，王荣良。《计算机辅助几何造型技术及其应用》。科学出版社。
[41] Wang Jiaye, Chen Hui, Wang Wenping. A sufficient condition for a wire-frame representing a solid modeling uniquely. Journal of Computer Science and Technology, volume 16,Issue 6, November 2001. 595-598.
[42] Wang Jiaye, Wang Wenping .Reconstructing 3D Object from Wire-frame. To be published.
[43] Agarwal SC, Waggenspack Jr, WN. Decomposition method for extracting face topologies from wire-frame models. Computer-Aided Design 1992, 24(3):123-140.
[44] Hanrahan PM. Creating volume models from edge-vertex graphs.ACM Computer Graphics 1982, 16(3):77-84.
[45] Dutton RD, Brigham RC. Efficient identifying the faces of a solid. Computers and Graphics in Mechanical Engineering 1983,7(2):143-147.
[46] Hopcrdoft J, Tarjan, R. Efficient planarity testing. Journal of the Association of Computing Machinery 1974,21:549-568.
．
[47] Ganter MA, Uicjer JJ. From wire-frame to solid geometric:automated conversion of data representation. Computer in Mechanical Engineering 1983,2(2):40-45.
[48] Courter SM, Brewer JA. Automated conversion of curvilinear wire-frame models to surface boundary models, a topological approach. SIGGRAPH'86, ACM Computer Graphics 1986,20(4):171-178.
[49] Hojnichi JS, White PR. Converting CAD wire-frame data to surfaced representation.Computers in Mechanical Engineering 1988,March/April:19-25.
[50] Paton K. An algorithm from finding a fundamental set fo cycles of a graph. Communications of the ACM 1969, 12(9):514-518.
[51] M. H. Kuo. Automatic extraction of quadric surfaces from wire-frame models. Computer & Graphics 2001,25:109-119.
[52] Mantyla, M. An Introduction to Solid Modeling.Computer Science Press.Rockville, MD,1998.
[53] 朱仁芝，江涌，陶涛，刘磊。利用3维重建技术进行线框模型消隐的算法。计算机工程与应用。1998,5。
[54] Kate Gregory著，前导工作室译。Visual C++6开发使用手册。第1版。机械工业出版社，1999．6。
[55] 严蔚敏，吴伟民。《数据结构》。第2版。北京：清华大学出版社，1992。
[56] 马绍汉。《算法分析与设计》第1版。济南：山东大学出版社，1992。
[57] 彭晓明 王坚。《OpenGL深入编程与实例揭密》。第1版。北京：人民邮电出版社，1996．6。
[58] 左孝凌，李为 刘永才。《离散数学》。第1版。上海：上海科学技术文献出版社。1982．9。
[59] 孙家广，杨长贵。《计算机图形学》。第2版。北京：清华大学出版社，1995。