简介:Visitingtrianglesthatconformadigitalterrainmodelisacoreoperationinanumberoffieldslikeanimationandvideogamesorgeneratingprofiles,cross-sections,andcontoursincivilengineering.Perfornfingthevisitinanefficientmannerisanissuespeciallywhentheoutputofthetraversaldependsinsomewayonadditionalparametersorinformationchangingovertime,forexample,amovingpointofview.Inthisworkwereportasetofrulesthat,givenadigitalterrainmodeldefinedoveraregulargridandanarbitrarypointofviewoutsidetheterrain,defineatotalback-to-frontorderinthesetofdigitalterrainmodeltriangleswithrespecttothepoint.Thesetofrulesisminimal,completeandcorrect.Toassesshowtherulesperform,wehaveimplementedaCPU-basedalgorithmforrealisticallyrenderingheightfieldsdefinedoverregulargrids.Thealgorithmdoesnotmakeuseofthez-bufferorshadersfeaturedbyourgraphicscard.Weshowhowouralgorithmisimplementedandshowvisualresultsobtainedfromsyntheticandrealdata.Wefurtherdiscussthealgorithmperformancewithrespecttotwoalgorithms:anaivealgorithmthatvisitstrianglesaccordingtogridindicesanddoesnotsolvethehiddenlineproblem,andthez-bufferprovidedbythegraphicscardfeaturedbyourcomputer.Ouralgorithmallowsreal-timeinteractionwhenthepointofviewarbitrarilymovesin3Dspaceandweshowthatitsperformanceisasgoodasthatofthez-buffergraphicscard.