1820-02141001063S

1820-02141001063SUDC005.922.52:004.932,DOI:10.2298/CSIS1001063S3DMeshSkeletonExtractionUsingProminentSegmentationXiaopengSUN1,J.PAN2,andXiaopengWEI31SchoolofMechanical&Engineering,DalianUniversityofTechnology,Dalian116024,Chinaxpzhsun@@(DalianUniversity),MinistryofEducation,Dalian116622,Chinaxiaopengwei@(MDS)transformation.Thealgorithmfirststraightsthefoldedprominentbranchup,aswellastheprominentshapefeaturepointsofmesharecomputed,ameaningfulsegmentationisappliedunderthedirectionoffeaturepoints.TheNode-ringofallsegmentedcomponentsisdefinedbydiscretegeodesicpathonmeshsurface,andthentheskeletonofeverysegmentedcomponentisdefinedasthelinkoftheNode-ring’scenter.Astothecorecomponentwithoutprominentfeaturepoints,principalcurveisusedtofititsskeleton.Ouralgorithmissimple,andinvariantbothtotheposeofthemeshandtothedifferentproportionsofmodel’scomponents.Keywords:Skeleton,MDS,Discretegeodesicpath,Node-ring.1.IntroductionInrecentyears,howtodesignasimpleandrobustalgorithmtoextracttheskeletonofobjectwithlessmemorycostandshapeinformationlosshasbecomeafundamentalproblemofinformationvisualizationandpatternrecognition[1]etal.Mostexistingalgorithmsweredevelopedfor3Dmedicalimageanalysiswithvolumetricdataasinput,andlittleworkonthe3Dmeshmodels,whicharerepresentedasapolygonallist.Butbecauseofthepropertyofreducingthedimensionoftheproblem,skeletonhasshownitspromisingadvantageintheapplicationofgeometryandtopologydescriptionwithitssimplicityinregionof3DDigitalGeometryProcessing(DGP),suchasdeformation[2][3],XiaopengSUN,J.PAN,andXiaopengWEIshaperecognitionandretrieval[4][5],meshediting[6],simplification[7],motioncontrolandcollisiondetection[8],segmentation[9]etal.MeaningfulmeshsegmentationisanotherfundamentalprobleminDGP,whichdecompose3Dsurfacemeshesintofunctionalshapecomponents,notonlyprovidessemanticinformationabouttheunderlyingmesh,butalsocouldbeusedtoguideseveralmeshprocessingalgorithms,includingskeletonextraction,modeling,morphing,shape-based3Dshaperetrieval,andtexturemapping[9]etal.Alloftheseapplicationsbenefitfrommeshmeaningfulsegmentationsthatobeyhumanintuition.Good3Dmeshsegmentationwillresultinhighqualityskeleton.Inthispaper,weintroduceanovelskeletonextractionalgorithmbasedonmeaningfulshapedecomposition,whichsegmentthe3Dmeshunderthedirectionoftheprominentfeaturepointandcore.Thechallengeofthisalgorithmisthat,thetrianglepatchsizeshouldbeuniformingeneralleveltokeepahighprecision,becausetheNode-ringisdefinedbythelengthofdiscretegeodesicpath,orsubdivisionmustbeappliedfirstly.Andtothosemesheswith5,000verticesormore,efficientmemorymanagementshouldbeconsideredtoimprovecomputingspeedofshortestpathbetweenallpairverticesofmesh,orsimplificationmustbeappliedasapreprocessing.DuetothetransformationofMDSandthedirectionofprominentfeaturepoints,wedecomposethemeshintoseveralprominentmeaningfulbranchcomponentsandacorecomponent,andthencomputetheskeletonofmeaningfulcomponentsrespectively,soouralgorithmisrobust,simple,andpose-invariance.works2.RelatedCorneaetal.presentedacomprehensiveoverviewoncurve-skeletonproperties,applicationsandalgorithms[1].Inrecentdecades,hundredsresearchworkshavebeenpublishedinveryextensiveapplicationregions.Theskeletonmodelisinitiallydefinedasacollectionofthecentreofthelargestinscribedsphere[10],andisusedextensivelyinvirtualnavigation,traditionalcomputergraphics,medicalimagesegmentationandquantification,registration,matching,3Dmeshmorphing,segmentation,andanalysisofscientificdataetal.Andthevariousapplicationsrequiredtheirowndesiredpropertiesoftheskeleton;forexample,theskeletonshouldbetopologicallyequivalenttotheoriginalobjectinshaperecognition,andmustbeinvariantunderisometrictransformations[4][11].Intheapplicationofshapecompressionandvolumeanimation,theskeletonshouldprovideenoughinformationtoreconstructa3Dobjectcompletelyfromitsmedialskeletonrepresentationbycomputingtheunionofmaximalinscribedballs[12].Andtheskeletonshouldbeitscenterednesswithinthe3Dobject[13];thelogicalcomponentsoftheobjectshouldhaveaone-to-onecorrespondencewiththelogicalcomponentsoftheskeleton[14][15];benotverysensitivetolittlenoiseintheboundary;3DMeshSkeletonExtractionUsingProminentSegmentationapproximatetothecomplexcomponentsofanobject,andreflectthenaturalhierarchyofthesecomplexities,etal.Commonly,thecurve-skeletonalgorithmscanbedividedintothreeclasses:topologicalthinning(grassfirepropagation),distancetransformbased(ridgedetection)andVoronoidiagrambased[16][17].Morerecentlyin2021,Corneaetal.in