歯강윤식.PDF

Size: px

Start display at page:

Download "歯강윤식.PDF"

지은 부
6 years ago
Views:

1 ,, e- mail : noori@mythos.yonsei.ac.kr : F a x : :,,,,.

2 (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

3 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

4 ., 2, 3, , (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, (D el au n ay T ri an g u lati on ) 1934 (R. Delaunay ), 2 [13]. 3,., 2.,.. 3

5 ( 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

6 p t, t (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

7 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

8 ( 4)..,. ( 4) ( ) ( 5) ( ), ( 5),.,., (edge ).,., ( 6). (k +1) (l+1).,..,,.,,, 7

9 . ( 6) 3.3.,, ( 7) (a ). ( 7) (c ), 3,, (edge sw apping ).. (a ) (b ) (c) (d ) ( 7). (a) (b). (c). (d) Delaunay triangulation. 8

10 Mhz 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 (156,392 ) Ashby Gap. Virginia Crater (154,224 ) West half of Crater Lake, Oregon Ozark (170,478 ) Desert around Mt. T iefort, California NT C (1,048,576 ) Ozark, Missouri West US (1,048,576 ) Section of Idaho/ Whoming border < 1> 5 ( 8)

11 ( 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 ,...,,. ( 12) ( 13) Crat er DEM im ag e. ( 13) (b ) 471 im age,,,. ( 10) Crater DEM FPA. ( 11) Crater DEM 11

13 (a ) (b ) ( 12) 154,224 Crater lake DEM (a) 52, (b) (a ) (b ) ( 13) 4, (a) (b) 5...., 12

14 .,,..,.,.. [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 , [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 , [3] [5] L. D. F loriani. "Surface represent ation s based on triangular grids," T he V is ual Comp uter, Vol. 3, pp , [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 , M arch [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 CMUCS , 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 , July [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 , Nov

15 [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 , Oct [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 , [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 , June [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 [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 , [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,

< > 1993 ( ), 1999 ( ), 3D graphics algorithm. 1993 ( ). 1995 ( ).

1986 University of Oklahoma ( ). 1992 University of Oklahoma (qk ).

16 < > 1993 ( ), 1999 ( ), 3D graphics algorithm ( ) ( ) ~. 3-D, ASIC, Computer Arithmetic, High performance Computer Architecture 1981 ( ) (University of Oklahoma ( ) University of Oklahoma ( ) University of Oklahoma (qk ) ~ University of Oklahoma, Adjunct Assistant Professor ~ ~., Computational geometry, Spatial data processing, 3D graphics algorithm. 15

정봉수.PDF

정봉수.PDF A pplic ation of Continu ou s P re fle x Com po s it e Girder to Rig id F ram e by V ertic al Lo adin g 2001 2 A pplic ation of Continu ou s P re fle x Com po s it e Girder to Rig id F ram e by V ertic

歯강윤식.PDF

歯강윤식.PDF