,, e- mail : noori@mythos.yonsei.ac.kr 1999 9 : +82-2- 361-2717 F a x : +82-2- 365-2579 :,,,,.
(t errain height field dat a ) (greedy in sertion algorithm )[1,4,5].,. (trian gulation ),.,.,, 4 20,., 4.,. A Digit al T err ain Simplification Algorithm with a P artitioning Method In this paper w e intr odu ce a fast sim plification algorithm for t err ain h eight fields t o produce a triangulat ed irregular n et w ork, based on th e greedy in sertion alg orithm in [1,4,5]. Our alg orithm partition s a terr ain height dat a into r ect an gular block s w ith the sam e size an d sim plifies block s on e by on e w ith th e greedy in sertion alg orithm. Our alg orithm referen ces only to the point s an d the triangles w ithin each current block for addin g a point int o the triangulation. T h erefore, the algorithm run s fast er than th e greedy in sertion algorithm, w hich referen ces all input point s and trian gles in the t errain. Our ex perim ent show s th at partitioning m ethod run s fr om 4 to m or e than 20 tim es faster, and it approxim at es test h eight fields as accurat ely as the greedy in sertion alg orithm s. M ost greedy in sertion alg orithm s suffer from elon gat ed triangles th at u su ally appear n ear th e boundaries. H ow ev er, w e in sert the four corner point s int o each block t o produce the b ase triangulation of the block before the point addition st ep begin s so that elong ated trian gles could n ot appear in the sim plified t err ain. 1
1. 3, /, /, 3,. 3 3 [3,6,7,8,9]., 3, 3., 3,.. 3, 3, 3.,,. (refin em ent greedy in sertion ),,,,.,.,,.,,.,. [2,10,11,12, 13], (triangulat ed irregular n etw ork ), 3.. m n. p m n, H (p ) p, (p, H (p )). p H (p ),.,, 2
., 2, 3, 4. 5. 2.,. 2. 2.1 (V oron oi D ia g ram s ) (Eu clidean ) (sit es ). P = { p 1, p 2,..., p n } 2,. (region ) V ( p i ). V( p i ) = {x : p i - x p j - x, j i} 2 (edg e). 4, 4. 2.2 (D el au n ay T ri an g u lati on ) 1934 (R. Delaunay ), 2 [13]. 3,., 2.,.. 3
( 1). (a ) (b ) ( 1) (a) (b) 2.3 (Gre e dy In s e rti on A l g orith m ),.,. [1].,. /. (local error ). e (p ) p ={x, y, z } z p z, p p ' ={x, y, z '} z ' ( 2). (1), e (p ) = z - f (p ) (1) f (p ) z '. ( 2) 4
p t, t 3. 3. (a) (b) ( 3) (a) (b) [2, 4, 5] (circle crit erion ),. P T, P T, T. p 3 (edge) e f ( 3). 3.,.,.,. A F a s t D ig it al T errain S im plific ation w ith a P artitionin g M e th od : / * k l */ Partition a terrain into k l blocks ; / * */ 5
f or e ac h blocks b Make_BaseT riangles (b); en d for / * */ f or e ac h blocks b Init_T riangles (b); Init_Err or (b); Find the local maximum err or e and the point p by calling Get_Max_Err or&point (b); w hile error < = do / * = */ Insertion (p ); Recalculation (b); Find the local maximum error e and the point p by calling Get_Max_Err or&point (b); en d w hile en d for (pseudo),,,.. 3.1,.,., djej,.,.,, 6
( 4)..,. ( 4) ( ) ( 5) ( ), ( 5),.,., (edge ).,.,.. 3.2 ( 6). (k +1) (l+1).,..,,.,,, 7
. ( 6) 3.3.,, ( 7) (a ). ( 7) (c ), 3,, (edge sw apping ).. (a ) (b ) (c) (d ) ( 7). (a) (b). (c). (d) Delaunay triangulation. 8
4. 2 400Mhz CPU (512Kbyte L2 ) 128Mbyt e RAM P C,. ( ( m + n) log m ) (m :, n : ) Much ael Garland P aul Heckbert ' s algorithm III(F F A )[4],, 3. < 1>,. Crat er., k l m ax error,,, ( ( m + n k l ) log m ), k l k l ( ( m + n ) log m k l ). Ashby 346 452 (156,392 ) Ashby Gap. Virginia Crater 336 459 (154,224 ) West half of Crater Lake, Oregon Ozark 369 462 (170,478 ) Desert around Mt. T iefort, California NT C 1024 1024 (1,048,576 ) Ozark, Missouri West US 1024 1024 (1,048,576 ) Section of Idaho/ Whoming border < 1> 5 ( 8) 5 12 12. 9
( 9) Crater. ( 8) ( 9). ( 8), 12 12,. ( 9),. 6 6,,., ( 10) ( 11). P N, hm a x hm in /, R P i, S P i z, (2). 1 PN PN ( R P i - SP i ) (2) i = 0 h m ax - h m in ( 10), 6 6. ( 11) 10
,...,,. ( 12) ( 13) Crat er DEM im ag e. ( 13) (b ) 471 im age,,,. ( 10) Crater DEM FPA. ( 11) Crater DEM 11
(a ) (b ) ( 12) 154,224 Crater lake DEM (a) 52,800 48 48 (b) (a ) (b ) ( 13) 4,711 24 24 (a) 471 6 6 (b) 5...., 12
.,,..,.,.. [1] L. D. F loriani, B. F alcidieno, and C. Pienovi, "A Delaun ay - based m eth od for surface approxim ation," E urog rap hics '83, pp. 33-350, 1983. [2] [14] L. D. F loriani, B. F alcidien o, G. N agy, an d C. Pien ov i, "A hierarchical stru cture for surface approx im ation," Comp uters and Grap hics, V ol. 8, No. 2, pp. 183-193, 1984. [3] [5] L. D. F loriani. "Surface represent ation s based on triangular grids," T he V is ual Comp uter, Vol. 3, pp. 27-50, 1987. [4] [3] L. D. F loriani, "A pyram idal dat a structure for trian gle- based surface description," I E E E Comp uter Grap hics and A pp lication, V ol. 9, No, 2, pp. 67-78, M arch 1989. [5] [4] M. Garland and P. S. H eckb ert, "F a st poly g on al approx im ation of t err ain s and h eight fields," T echnical report, CS Dept., Carn egie M ellon U., S ept. 1995. CMUCS - 95-181, http :/ / w w w.cs.cm u.edu/ ~garlan d/ scape. [6] K. Anjy o, Y. U sam i, T. Kurih ara, "A Sim ple M ethod for Ex tracting the N atural Beauty of H air," SI GGR A P H '92, Vol. 26, N o. 2, pp. 111-120, July 1992. [7] P. S. H eckb ert, "Surv ey of t ex ture m appin g," I E E E T ransaction on Comp uter Grap hics and A pp lications, pp. 56-57, Nov. 1986 13
[8] M. Ch ow. "Optim ized g eom etry com pres sion for realtim e ren dering," I E E E V is ualiz ation '97, pp. 347-354, Oct. 1997. [9] N. Greene, "Environm ent m apping and oth er application s of w orld proj ection s," I E E E Comp uter Grap hics and A pp lications, Vol. 6, No. 11, pp. 21-29, 1986. [10] S. L. T anim oto an d T. P avlidis, "A hierarchical dat a structure for picture proces sing," Comp uter Grap hics and I m ag e P reocess ing, Vol. 4, No. 2, pp. 104-119, June 1975. [11] L. W illiam s, "P yramidal param etrics," Comp uter Grap hics (SI GGR A P H '83 P roc.), V ol. 17, N o. 3, pp. 1-11, July 1983. [12] D. Gom ez and A. Guzm an, "Digit al m odel for thr ee- dim en sion al surface representation," GeoP rocess ing, V ol. 1, pp. 53-70, 1979. [13] H. S am et, T he D es ig n and A naly s is of Sp atial D ata S tructures. A ddison - W esley, Readin g, MA, 1990. 14
< > 1993 ( ), 1999 ( ), 3D graphics algorithm. 1993 ( ). 1995 ( ). 1995 ~. 3-D, ASIC, Computer Arithmetic, High performance Computer Architecture 1981 ( ). 1984 (University of Oklahoma ( ). 1986 University of Oklahoma ( ). 1992 University of Oklahoma (qk ). 1992 8 ~ 1992 12 University of Oklahoma, Adjunct Assistant Professor. 1993 3 ~ 1994. 1994 9 ~., Computational geometry, Spatial data processing, 3D graphics algorithm. 15