693 KB18 KB197320251998Čapelnik, SergejŽalik, Borutštevilka:3letnik:42str. 269-276ISSN:0351-0271COBISSID:19489541URN:URN:NBN:SI:doc-63L70KPJslZveza geodetov SlovenijeGeodetski vestnikdelitev prostorageodezijametodeprostorračunalniška grafikaHitro iskanje geometrijskih podatkov|This paper presents an efficient approach to, and the advantages of, traversing a uniformly subdivided space pierced by a line segment. A voxel, as the basis constituent element of a uniformly subdivided space, is restricted to the form of a cube. The algorithm works in two steps. In the first step, the so-called Bresenham voxels are identified and, by comparing their position codes, their type of connectivity is determinated. To achieve the required connectivity between neighbouring voxels, the second step of the algorithm is applied to find the missing voxels. In this way, the algorithm efficiently switches between face-, edge- and vertex-connectivity. Although the algorithm works with floating-point precision, in computational terms, it is extremely efficientV članku predstavljamo tehniko enakomerne delitve prostora ter prednosti, ki jih prinaša. Prostor delimo na več manjših enako velikih delov, ki jim pravimo celice. V 3D- prostoru imajo te celice obliko kocke, v 2D- prostoru pa obliko kvadrata. Namen delitve prostora je lokalizirati operacije nad geometrijskimi elementi, jih tako pospešiti ter vpeljati med geometrijske elemente neko strukturo. V postopku delitve prostora se vsi geometrijski elementi v tem prostoru porazdelijo po posameznih celicah. Ta porazdelitev poteka v dveh korakih. V prvem koraku se poiščejo Bresenhamove celice, v naslednjem koraku pa še manjkajoče Nebresenhamove celice. Algoritem deluje v aritmetiki s plavajočo vejico, kjub temu pa je zelo učinkovit. Predstavili smo tudi izboljšano metodo enakomerne delitve prostora, ki temelji na celicah z različno velikostjo in odpravlja problem prenatrpanosti posameznih celic z geometrijskimi elementiTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaZveza geodetov Slovenije