Computer Science

Computer Science ›› 2025, Vol. 52 ›› Issue (4): 222-230.doi: 10.11896/jsjkx.240700042

• Computer Graphics & Multimedia • Previous Articles     Next Articles

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)

101

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

CLC Number: 

  • 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.
[1] CHEN Zhangyuan, CHEN Ling, LIU Wei, LI Bin. Method for Selecting Observers Based on Doubly Resolving Set in Independent Cascade Model [J]. Computer Science, 2025, 52(4): 280-290.
[2] WANG Hao, CAI Yuhang, CHEN Guojie, WANG Lu. Study on MAC Protocol of LoRa Network Hidden Terminal Based on BTMA [J]. Computer Science, 2025, 52(3): 318-325.
[3] WANG Qian, HE Lang, WANG Zhanqing, HUANG Kun. Road Extraction Algorithm for Remote Sensing Images Based on Improved DeepLabv3+ [J]. Computer Science, 2024, 51(8): 168-175.
[4] SHAO Wenxin, YANG Zhibin, LI Wei, ZHOU Yong. Natural Language Requirements Based Approach for Automatic Test Cases Generation of SCADE Models [J]. Computer Science, 2024, 51(7): 29-39.
[5] DENG Ziwei, CHEN Ling, LIU Wei. Continuous Influence Maximization Under Independent Cascade Propagation Model [J]. Computer Science, 2024, 51(6): 161-171.
[6] BAI Xuefei, SHEN Wucheng, WANG Wenjian. Salient Object Detection Based on Feature Attention Purification [J]. Computer Science, 2024, 51(5): 125-133.
[7] LI Yu, YANG Xiangli, ZHANG Le, LIANG Yalin, GAO Xian, YANG Jianxi. Combined Road Segmentation and Contour Extraction for Remote Sensing Images Based on Cascaded U-Net [J]. Computer Science, 2024, 51(3): 174-182.
[8] CHEN Pan, CHEN Hongmei, LUO Chuan. Academic Influence Ranking Algorithm Based on Topic Reputation and Dynamic HeterogeneousNetwork [J]. Computer Science, 2024, 51(3): 81-89.
[9] WANG Yuchen, GAO Chao, WANG Zhen. Survey of Inferring Information Diffusion Networks [J]. Computer Science, 2024, 51(1): 99-112.
[10] ZHANG Wenxiang, GUO Jiapeng, FU Xiaoming. Error-bounded Compatible High-order Remeshing [J]. Computer Science, 2024, 51(1): 207-214.
[11] BAI Mingli, WANG Mingwen. Fabric Defect Detection Algorithm Based on Improved Cascade R-CNN [J]. Computer Science, 2023, 50(6A): 220300224-6.
[12] YANG Heng, ZHU Yan. Analysis of Academic Network Based on Graph OLAP [J]. Computer Science, 2023, 50(6A): 220100237-5.
[13] WANG Tao, GUO Wushi, DENG Jian, CHEN Liang. Building Natural Language Interfaces for Distributed SCADA Systems Using Semantic Parsing [J]. Computer Science, 2023, 50(6A): 220300141-9.
[14] ZHANG Zelun, YANG Zhibin, LI Xiaojie, ZHOU Yong, LI Wei. Machine Learning Based Environment Assumption Automatic Generation for Compositional Verification of SCADE Models [J]. Computer Science, 2023, 50(6): 297-306.
[15] CHEN Bonian, HAN Yutong, HE Tao, LIU Bin, ZHANG Jianxin. Cascade Dynamic Attention U-Net Based Brain Tumor Segmentation [J]. Computer Science, 2023, 50(11A): 221100180-7.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.