计算机科学

计算机科学 ›› 2025, Vol. 52 ›› Issue (4): 222-230.doi: 10.11896/jsjkx.240700042

• 计算机图形学&多媒体 • 上一篇    下一篇

基于轮廓线的网格体物体空间快速消隐算法

宋海川1, 邱荪泓1,2, 汪鑫星1, 李一锦3, 陈振华1, 陈小雕4   

  1. 1 华东师范大学计算机科学与技术学院 上海 200062
    2 先进计算与关键软件(信创)海河实验室 天津 300450
    3 南京大学计算机学院 南京 210023
    4 杭州电子科技大学计算机学院 杭州 310018
  • 收稿日期:2024-07-08 修回日期:2024-09-13 出版日期:2025-04-15 发布日期:2025-04-14
  • 通讯作者: 宋海川(hcsong@cs.ecnu.edu.cn)

Fast Contour-based Object-space Hidden Line Removal Algorithm for Mesh

SONG Haichuan1, QIU Sunhong1,2, WANG Xinxing1, LI Yijin3, CHEN Zhenhua1, CHEN Xiaodiao4   

  1. 1 School of Computer Science and Technology,East China Normal University,Shanghai 200062,China
    2 Haihe Laboratory of Information Technology Application Innovation,Tianjin 300450,China
    3 School of Computer Science,Nanjing University,Nanjing 210023,China
    4 School of Computer Science,Hangzhou Dianzi University,Hangzhou 310018,China
  • Received:2024-07-08 Revised:2024-09-13 Online:2025-04-15 Published:2025-04-14
  • About author:SONG Haichuan,born in 1986,Ph.D,associate professor.His main research interests include computer vision,3D printing,and point projection.

PDF (PC)

99

摘要： 隐藏线消除,即消除在一定视角下被遮挡的线段,是解决三维场景中视觉混淆问题的关键技术。其中,物体空间的隐藏线消除技术可以计算可见性变化点的精确坐标,因此在实际工程中被广泛用于三维可视化建模、高精度图纸的绘制等。然而,先前的物体空间消隐算法在处理实际工程中常用的网格体模型时,往往会因为模型面内部含有大量三角面片而计算效率低下。因此,提出了基于轮廓线的网格体物体空间快速消隐算法。该算法通过网格体轮廓线投影的交集进行三角面片的筛选及其求交计算,从而避免了大部分的无效求交计算。同时,在求交后根据待定可见性变化点所在线段与轮廓线和模型的射入、射出情况进行快速可见性判断,进一步提高了算法效率。实验结果显示,在两种常见的消隐模式下处理普通和复杂网格体模型的消隐,所提算法相较于对比算法效率分别提高了20倍和80倍以上,与主流几何内核ACIS的消隐处理效率差距在2.5倍以内。

关键词: 消隐算法, 物体空间消隐, 网格体, 轮廓线, CAD

Abstract: Hidden line removal,which eliminates lines occluded under certain viewing angles,is a key technique for addressing visual clutter issues in 3D scenes.Object-space hidden line removal techniques can calculate the precise locations of visibility transformation points,making them widely used in practical engineering for 3D visualization modeling,high-precision drawing,and other purposes.While there are many mature object-space hidden line removal algorithms available for planar polyhedra,these algorithms often suffer from low computational efficiency when handling commonly used mesh models in practical engineering due to the large number of triangles within model surfaces.To address this issue,this paper proposes a fast contour-based object-space hidden line removal algorithm for mesh.This algorithm filters triangular facets based on the intersection of mesh object contour line projections and performs intersection calculations,thereby avoiding most redundant intersection computations.Additionally,after intersection calculations,the algorithm rapidly determines visibility based on the line segments where potential visibilitytransformation points lie in relation to the contour lines and model,further enhancing efficiency.Experimental results show that when processing the hidden line removal of ordinary and complex mesh models in two common hidden line removal modes,the efficiency of the algorithm presented in this paper is over 20 times and 80 times higher,respectively,than compared algorithm,and the efficiency difference between our algorithm and the mainstream geometric kernel ACIS is within 2.5 times.

Key words: Hidden-line removal algorithm, Object-space hidden-line removal, Mesh, Contour lines, CAD

中图分类号: 

  • TP391.72
[1]SUN J G,HU S M.Fundamental Course in Computer Graphics [M].Beijing:Tsinghua University Press,2009.
[2]SUTHERLAND I E,SPROULL R F,SCHUMACKER R A.A characterization of ten hidden-surface algorithms[J].ACM Computing Surveys(CSUR),1974,6(1):1-55.
[3]JIN H L,GAO J X.A Summary of Algorithms for Removing the Hidden Lines and Surfaces [J].Computer and Digital Enginee-ring,2006,34(9):27-31.
[4]GUO H,FU H G,LUO D H.Realization of hidden line removal in 3D dynamic geometry [J].Journal of Computer Applications,2007,27(3):663-665.
[5]LUO G L,WANG R,WU H,et al.Fast hidden line removalmethod for large-scale 3D substation scene model based on Z-buffer algorithm optimization [J].Journal of Graphics,2021,42(5):775.
[6]RUOBERTS L G.Machine perception of three-dimensional so-lids[D].Massachusetts:Massachusetts Institute of Technology,1963.
[7]WEISS R A.BE VISION,a package of IBM 7090 FORTRANprograms to draw orthographic views of combinations of plane and quadric surfaces[M]//Seminal graphics:pioneering efforts that shaped the field.1998:7-17.
[8]WEILER K,ATHERTON P.Hidden surface removal using poly-gon area sorting[J].ACM SIGGRAPH computer graphics,1977,11(2):214-222.
[9]APPEL A.The notion of quantitative invisibility and the ma-chine rendering of solids[C]//Proceedings of the 1967 22nd National Conference.1967:387-393.
[10]GALIMBERTI R.An algorithm for hidden line elimination[J].Communications of the ACM,1969,12(4):206-211.
[11]LOUTREL P P.A solution to the hidden-line problem for computer-drawn polyhedra[J].IEEE Transactions on Computers,1970,100(3):205-213.
[12]DEVAI F.Quadratic bounds for hidden line elimination[C]//Proceedings of the Second Annual Symposium on Computational Geometry.1986:269-275.
[13]GHALI S.A survey of practical object space visibility algo-rithms[J/OL].https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=3a735dce573effddf635dd03310ef50fafc2c3e9.
[14]OTTMANN T,WIDMAYER P.Solving visibility problems by using skeleton structures[C]//International Symposium on Mathematical Foundations of Computer Science.Berlin,Heidelberg:Springer,1984:459-470.
[15]OTTMANN T,WIDMAYER P,WOOD D.A worst-case efficient algorithm for hidden-line elimination[J].International Journal of Computer Mathematics,1985,18(2):93-119.
[16]NURMI O.A fast line-sweep algorithm for hidden line elimination[J].BIT Numerical Mathematics,1985,25(3):466-472.
[17]GOODRICH M T.A polygonal approach to hidden-line and hidden-surface elimination[J].CVGIP:Graphical Models and Image Processing,1992,54(1):1-12.
[18]HSU W I,HOCK J L.An algorithm for the general solution of hidden line removal for intersecting solids[J].Computers & graphics,1991,15(1):67-86.
[19]SONG R J,ZHANG J L,LI X D.Study and improvementation of hidden-line removal algorithm for convex polyhedrons [J].Computer Engineering and Design,2012,33(6):2358-2362.
[20]XU X,SHI K L,YONG J H.Hidden-Line Elimination with To-lerance [J].Journal of System Simulation,2013,25(9):2079-2084.
[21]ELBER G,COHEN E.Hidden curve removal for free form surfaces[J].ACM SIGGRAPH Computer Graphics,1990,24(4):95-104.
[22]JANSSEN T L.A simple efficient hidden line algorithm[J].Computers & Structures,1983,17(4):563-571.
[23]SPILLERS W R,LAW K H.On the hidden line removal problem[J].Computers & structures,1987,26(4):709-717.
[24]3D ACIS Modeler[EB/OL].(2024-06-15) [2024-06-16].https://www.spatial.com/products/3d-acis-modeling.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发