Tài liệu MỘT THUẬT TOÁN RÚT GỌN BỀ MẶT BIỂU DIỄN MÔ HÌNH 3D

T P CHÍ KHOA H C VÀ CÔNG NGH T p 48, s 2, 2010 Tr. 123-133 M T THU T TOÁN RÚT G N B M T BI U DI N MÔ HÌNH 3D NĂNG TOÀN, NGUY N VĂN HUÂN 1. GI I THI U Xây d ng mô hình là m t khâu quan tr ng trong các h th ng th c t i o. Mô hình ư c xây d ng không nh ng ph i m b o v ch t lư ng mà còn ph i m b o v yêu c u gi m thi u không gian b nh , rút ng n th i gian tính toán, nh m ph c v cho các yêu c u i u khi n sau ó. i u này, c bi t quan tr ng khi s d ng các thi t b thu nh n như máy quét 3D, mô hình thu ư c thư ng có k t qu quá "n ng" [4, 15]. gi m thi u không gian b nh c a mô hình, m t trong nh ng cách ti p c n là gi m thi u s b m t bi u di n mô hình. Các thu t toán "gi m thi u b m t" bi u di n m t v t th trong không gian ba chi u hi n nay là không nhi u i v i a s các ng d ng th c t i o. Trong th c t , không ph i lúc nào chúng ta cũng c n bi u di n m t v t th trong không gian ba chi u v i ch t lư ng như th t. Hơn n a, m c ch t lư ng hình nh c a cùng m t v t th khi hi n th cũng có th thay i theo cách nhìn (view). Ví d , khi quan sát c n c nh m t v t th , chúng ta c n s lư ng m t nhi u hơn vi c mô hình hoá có th t n m t ch t lư ng như th t [8]. Tuy nhiên, khi kho ng cách tăng lên, v t th càng nh i i v i m t ngư i quan sát thì s lư ng m t bi u di n có th gi m i mà v n m b o cho ngư i quan sát v n có th hình dung ra ư c v t th . Kĩ thu t hi n th này ã ư c tích h p vào nhi u h th ng h a 3 chi u và th c t i o v i tên g i là LOD (Level Of Detail) [12, 14]. th c hi n ư c kĩ thu t hi n th LOD v cơ b n ngư i ta ph i sinh ra các mô hình m c chi ti t khác nhau và kĩ thu t s s d ng mô hình phù h p t i các tình hu ng hi khác nhau. Vi c sinh ra các mô hình này thư ng d a trên các kĩ thu t rút g n b m t trư ng h p mô hình ư c bi u di n b i các b m t có phương trình tham s , thì chúng s sinh ra b i các tham s phù h p [1, 2]. Hình 1 dư i ây minh h a cho i u này. các n th ho c ư c Hình 1. Minh h a v vi c gi m thi u b m t theo các m c khác nhau 123 Như v y, trong các ng d ng ho ba chi u n y sinh m t v n là nghiên c u m t l p các thu t toán nh m gi m b t s m t c a m t a di n bi u di n v t th sao cho v n gi l i ư c m t cách tương i hình d ng ban u c a v t th ó. Tùy theo cách phân lo i, các tiêu chí phân lo i có th k t i là: - D a trên ng d ng: M t s thu t toán gi i h n các i tư ng v t th c a mình, m t s d ng nh t nh tuỳ theo ng d ng c a nó. Ví d : có m t lo t thu t toán ch nh m gi m thi u m t c a a hình ư c dùng trong các ng d ng GIS hay các bài toán mô ph ng a hình. M t s khác ư c dành cho các ng d ng t ng quát nên các ràng bu c vào d li u u vào ít hơn. - D a trên các ràng bu c ban u: Có nh ng thu t toán chú tr ng t i vi c gi l i hình d ng v t th (TPA). Tuy nhiên, cũng có nh ng thu t toán ch p nh n m t mát b t i m t ph n thông tin có th t ư c t c x lý cao. - D a trên phương pháp ánh giá sai s : M t trong nh ng i u quan tr ng nh t c a các thu t toán “gi m thi u b m t” là cách th c ánh giá sai s c a v t th m i t o ra so v i v t th ban u, qua ó xác nh phương án gi m thi u nào là t t, phương án nào là kém. Bài báo này c p m t kĩ thu t rút g n s lư ng b m t bi u di n mô hình theo cách ti p c n d a trên ng d ng, thu t toán áp d ng cho các mô hình có các b m t g n nhau là tương i “b ng ph ng”, trên cơ s m r ng thu t toán rút g n s lư ng i m bi u di n Angles [13,19] trong không gian 2D. Ph n còn l i c a bài báo ư c th hi n như sau: Ph n 2 trình bày m t s thu t toán rút g n s lư ng b m t bi u di n mô hình 3D ã ư c phát tri n. Ph n 3 c pm t thu t toán rút g n s lư ng b m t bi u di n mô hình 3D d a trên cơ s thu t toán Angles. Ti p theo là th nghi m và cu i cùng là k t lu n v kĩ thu t xu t. 2. M T S NGHIÊN C U LIÊN QUAN Trong m t vài năm g n ây, bài toán rút g n s lư ng b m t bi u di n mô hình theo cách ti p c n d a trên ng d ng ã nh n ư c nhi u s quan tâm nghiên c u và luôn là v n ư c t ra khi mà trong th c t v n thư ng xuyên có nh ng yêu c u c th . Tùy thu c vào t ng ng d ng c th v i nh ng yêu c u c th mà hi n nay ngư i ta có th th c hi n vi c rút g n mô hình d a vào nh ng c trưng khác nhau c a t ng mô hình. V i nh ng ng d ng mà mô hình g m có nh ng b m t r i r c g n nhau ho c có t n t i nh ng c p (vi, vj) không ph i là c nh thì ngư i ta áp d ng gi i thu t bó nh ho c gi i thu t NEC (Non-Edge Contraction) [5, 9]. a) Mô hình g c Hình 2. Minh ho gi i thu t bó b) Mô hình rút g n nh ho c NEC V i gi i thu t bó nh cho phép th c hi n bó các nh g n nhau thành m t 2b), v i gi i thu t này cho k t qu t i và không h tr i u khi n mô hình x p x . 124 nh ơn (hình V i nh ng ng d ng mà mô hình g m có nh ng b m t cong, l i lõm, có nh không quan tr ng thì ngư i ta áp d ng gi i thu t ch n nh và xóa b nh này i, r i xóa b các b m t g n k . Nhưng gi i thu t này không phù h p cho các mô hình a t p [5, 9]. a) Mô hình g c Hình 3. Minh ho gi i thu t xoá b) Mô hình rút g n nh và l p l i lư i tam giác V i nh ng ng d ng mà mô hình g m có nh ng b m t mà có các c nh vi, vj v i ||vi-vj|| < t (t là ngư ng) thì ngư i ta áp d ng gi i thu t ch m c nh EC (Edge Contraction), r i xoá b nh ng b m t có c nh ch m [5, 6, 7, 9]. a) Mô hình g c b) Mô hình rút g n Hình 4. Minh ho gi i thu t ch m c nh (v1; v2) và hu b các m t có chung c nh a) Mô hình g c c) H y b tam giác láng gi ng b) Gán tr ng s trên b m t c c b d) L p lư i l i lư i tam giác Hình 5. Minh ho gi i thu t c t b hình h c 125 V i nh ng ng d ng mà mô hình g m có các vùng b m t có cong cao và cong th p thì ngư i ta áp d ng gi i thu t c t b hình h c b ng cách gán tr ng s cho nh ng b m t trong mô hình g c theo cong c c b [17]. V i nh ng ng d ng mà mô hình g m có nh ng b m t cong cao hơn so v i nh ng i tư ng ch a nh ng i m gián o n (không liên t c) có c nh nh n (có cong, ư ng cong t ng t) thì ngư i ta áp d ng gi i thu t Re-Tiling. Ví d : Rút g n b m t m t con th , lông th t t, nhưng không t t cho mô hình ngôi nhà (k t qu t i). V i kĩ thu t này yêu c u ngư i dùng ch ra s nh trong mô hình u ra [19]. a) Mô hình g c v i các i m ng u nhiên c) L p lư i tam giác t i các i m b) Phân b các i m d) H y b các u nhau nh trong mô hình g c Hình 6. Minh ho gi i thu t Re-Tiling V i nh ng ng d ng mà xây d ng mô hình t các hình kh i MC (Marching Cubes) thì ngư i ta áp d ng gi i thu t DTM (Decimation of Triangle Meshes). Gi i thu t th c hi n l a ch n các nh mà th a mãn m t i u ki n sai s kho ng cách, r i xóa b nh này, sau ó th c hi n l p l p lư i tam giác [18]. Ngoài nh ng ng d ng v i nh ng mô hình có các b m t v i nh hi n nay v n còn có nh ng ng d ng v i nh ng mô hình v i nh ng ư c rút g n s lư ng b m t xu ng m c t i thi u sao cho ch t lư ng v nh ng ng d ng mà mô hình g m có nh ng b m t g n nhau là tương ng c trưng như trên, thì c trưng khác mà c n ph i n m b o, ch ng h n như i b ng ph ng. M c 3 dư i ây trình bày kĩ thu t rút g n s lư ng b m t bi u di n mô hình 3D d a trên ng d ng, v i các mô hình có các b m t g n nhau là tương i b ng ph ng nh vi c tính toán góc gi a các véctơ pháp tuy n b m t k nhau, trên cơ s m r ng thu t toán Angles trong không gian 2D. 126 a) Ch n nh trong mô hình g c b) H y b tam giác t i nh ư c ch n c) L p lư i l i lư i tam giác Hình 7. Minh ho gi i thu t DTM 3. THU T TOÁN RÚT G N S LƯ NG B M T BI U DI N MÔ HÌNH 3D 3.1. Thu t toán g c Angles[13, 16] trong không gian 2D Thu t toán th c hi n vi c rút g n s lư ng i m bi u di n cho m t ư ng cong 2D. Thu t toán b t u b ng vi c xác nh i m u tiên trên ư ng cong và coi ó như là m t i m ch t (P1). i m th ba (P3) ư c coi là i m ng. i m gi a i m ch t và i m ng (P2) là i m trung gian. Ban u góc t i i m trung gian ư c t o b i các c nh n i i m trung gian gi a i m ch t và i m ng ư c tính toán và ki m tra. N u giá tr tính ư c này l n hơn m t ngư ng θ cho trư c thì i m trung gian có th b i, ti n trình ti p t c v i i m ch t là i m ch t cũ, i m trung gian là i m ng cũ và i m ng là i m k ti p sau i m ng cũ. Trong trư ng h p ngư c l i, góc tính ư c nh hơn ngư ng θ cho trư c thì i m trung gian s ư c gi l i, ti n trình ti p t c v i i m ch t là i m trung gian, i m trung gian là i m ng cũ và i m ng là i m k ti p sau i m ng cũ. Ti n trình ư c l p cho n h t ư ng cong (hình 8 minh h a thu t toán Angles). P3 P2 αk αi P4 P5 P1 Hình 8. ơn gi n hóa ư ng cong v i thu t toán Angles 3.2. Thu t toán lo i b các i m góc Angles 127 Bư c 1: Xác nh i m u tiên trên ư ng cong và coi ó như là m t i m ch t (P1). i m th ba (P3) ư c coi là i m ng. i m gi a i m ch t và i m ng (P2) là i m trung gian. i m Bư c 2: Tính góc t i i m trung gian t o b i các c nh n i i m trung gian v i i m ch t và ng. th b Bư c 3: Ki m tra góc tìm ư c n u l n hơn m t ngư ng θ cho trư c thì i m trung gian có i. Trong trư ng h p ngư c l i i m ch t chuy n n i m trung gian. Bư c 4: Chu trình ư c l p l i cho n h t ư ng cong v i i m trung gian ư c chuy n n i m ng và i m k ti p sau i m ng ư c ch nh làm i m ng m i. 3.3. Thu t toán rút g n s lư ng m t bi u di n m r ng HS Thu t toán ư c th c hi n như là vi c m r ng c a thu t toán Angles sang 3 chi u v i vi c thay tính góc t o b i các c nh t i m t nh b i tính góc t o b i véctơ pháp tuy n c a các m t có cùng m t nh. Xu t phát t vi c che ph i tư ng có th hình dung như sau: Coi nh che ph như m t mi ng cao su, sau ó óng inh các i m trên nh t i các v trí tương ng c a lư i. nh s b căng ra và che ph toàn b i tư ng. T i các i m ch t mà véctơ pháp tuy n t i các m t có ch a i m này l ch nhau m t góc nh hơn ngư ng θ cho trư c thì i m ó có th b i, a giác ư c t o b i các i m nh có c nh n i i m ư c b i s ư c chia lư i l i theo các thu t toán v chia lư i tam giác (hình 9). ni nj φ a) B m t thành ph n và véctơ pháp tuy n tương ng b) Lo i b nh v1 Hình 9. Véctơ pháp tuy n c a các b m t chung c) Chia l i lư i nh và s lo i b nh Do có th bi u di n b m t a giác thành các tam giác thành ph n, nên không làm m t tính t ng quát ta có th gi thi t r ng m t i tư ng b m t lư i trong không gian ba chi u M ch bao g m các m t tam giác và ư c bi u th b i c p danh sách (V, F) trong ó: V = (vl,v2,v3, .. ,vr): là danh sách g m m t dãy th t các c t vi = [xi, yi, zi]T; (i = 1, 2, 3) trong không gian R3. nh, m i m t nh là m t véctơ F = (f1, f2, f3, .. , fn): là danh sách dãy có th t các m t tam giác, m i m t tam giác fi là m t b ba nh (vi,vk,vl). Khi ó véctơ pháp tuy n c a b m t tam giác fi, ư c tính b i tích có hư ng c a hai véctơ a = (a1, a2, a3) và b = (b1, b2, b3) n m trong b m t: 128 a ni = aΛb =  2  b2 a3 a3 , b3 b3 a2   = (a2b3 − a3b2 , a3b1 − a1b3 , a1b2 − a2b1 ) . b2  a1 a1 , b1 b1 Góc ϕ gi a hai pháp tuy n ni và n j c a các b m t tam giác fi, fj ư c xác công th c: cos ϕ = ni n j = ni n j a1a2 + b1b2 + c1c2 2 1 2 2 a + b12 + c12 . a2 + b22 + c2 (*) nh b i . (**) Do ó, vi c rút g n s lư ng b m t bi u di n ư c th c hi n l p thông qua 4 bư c cơ b n. 3.4. Thu t toán rút g n b m t bi u di n HS Bư c 1: Kh i t o - L a ch n ngư ng θ; - Tính véctơ pháp tuy n ni c a các b m t tam giác fi ∈ F, i = 1,..,n. Bư c 2: V i m i nh vi ∈ V tính các góc ư c t o b i các c p véctơ pháp tuy n c a các b m t tam giác ch a nh vi Bư c 3: N u các góc tính ư c bư c 2 u nh hơn ngư ng θ cho trư c, t c là các b m t tương i ph ng t i nh vi, thì i m nh vi có th b i, thu t toán chuy n qua bư c 4. Trong trư ng h p ngư c l i nh ư c gi l i, thu t toán quay l i bư c 2. Bư c 4 : Chia a giác ư c t o b i các i m tam giác và c p nh t l i danh sách F 3.5. nh có c nh n i i m ư c b i thành lư i ph c t p c a thu t toán HS ánh giá hi u qu c a thu t toán HS, chúng tôi d a vào Gi s có mô hình tam giác M v i v b m t có chung nh v. T i bư c (1): Vì (*) có ph c t p c a thu t toán. nh và x b m t, n véctơ pháp tuy n ư c t o b i t x ph c t p tính toán là O(1), m i vòng l p tính tính m t n . Vì v y có i vòng l p thì chúng ta c n tính ni , do ó n u có n véctơ pháp tuy n (tương ng n b m t) thì có ph c t p là O(n). T i bư c (2)-(3), ta có 2 véctơ pháp tuy n t o thành m t góc c n tính. N u ph ng ch a nó ( x véctơ pháp tuy n ) thì ta có: C2x = nh v có x m t x! 1 = (n-1)(n-2) ⇒ O(n2). 2!( x − 2)! 2 T i bư c (4): chia ư c thành lư i các i m thì thu t toán chia c n ph i duy t các i m ã ư c b i. Gi s ph c t p c a thu t toán chia là O(log n). C p nh t l i danh sách c n th c hi n t i thi u n phép tính, do ó ph c t p là O(n) V y ph c t p c a thu t toán HS là: Max(O(n), O(n2), O(n), O(log n)) = O(n2) 129 3.6. Th nghi m Chúng tôi ã cài t thu t toán xu t trên và rút g n s lư ng b m t bi u di n trong xây d ng mô hình có b m t tương i b ng ph ng. Khi b m t i tư ng "b ng ph ng" thì s có nhi u b m t t o nên lư i i tư ng có cùng m t i m nh có véctơ pháp tuy n "song song" v i nhau do ó, góc t o gi a chúng s nh . Do v y, s i m nh có th b i nhi u hơn d n n s lư ng b m t lư i s ư c rút b nhi u hơn. Hình 10 dư i ây minh h a cho vi c rút g n s lư ng b m t bi u di n c a thu t toán HS. Hình 10.a, 10.b là mô hình t ng th và m t ph n c a khu ô th m i Nghĩa Tân. S lư ng b m t ban u c a h th ng là hơn 80.000.000 b m t. V i s lư ng b m t l n th này, vi c load và i u khi n mô hình là r t khó khăn. V i ngư ng góc gi a 2 véctơ pháp tuy n ≤ 5o, chúng tôi ã rút g n ư c xu ng còn dư i 54.000.000 b m t. Nh ó chương trình trình di n công trình ki n trúc VREpistypeRender [11] có th i u khi n khá linh ho t công trình ki n trúc này. a) Mô hình t ng th khu ô th m i Nghĩa Tân b) M t ph n khu ô th Hình 10. Mô hình khu ô th m i Nghĩa Tân, C u Gi y, Hà N i Hình 11 dư i ây minh h a cho vi c rút g n s lư ng b m t bi u di n c a thu t toán HS. Hình 11.a là mô hình t ng th c a m t h i trư ng v i s lư ng b m t là 73.400 b m t. Áp d ng thu t toán HS v i ngư ng góc gi a 2 véctơ pháp tuy n ≤ 5o, chúng tôi ã rút g n ư c xu ng s lư ng b m t khác nhau (k t qu hình 11.c, 11.e), còn thu t toán EC [10, 18] th c hi n rút g n b ng cách ch m c nh (k t qu hình 11.b, 11.d). So sánh k t qu rút g n c a HS v i k t qu rút g n c a EC thì th y HS cho k t qu mô hình có ch t lư ng t t hơn v i b m t m n hơn, còn EC cho k t qu mô hình t i hơn v i b m t thô hơn. 130 a) Mô hình g c v i 73.400 b m t b) Mô hình rút g n còn 45.000 b m t i v i EC c) Mô hình rút g n còn 45.000 b m t i v i HS d) Mô hình rút g n còn 10.000 b m t i v i EC e) Mô hình rút g n còn 10.000 b m t i v i HS Hình 11. Mô hình m t công trình ki n trúc v i các m c EC và thu t toán xu t HS rút g n khác nhau c a thu t toán 131 4. K T LU N Hai khâu quan tr ng trong vi c xây d ng m t h th ng th c t i o (virtual reality system) là xây d ng mô hình (modelling) và i u khi n mô hình (rendering). Trong xây d ng mô hình, ngoài v n ch t lư ng còn òi h i yêu c u v tính ơn gi n nh m gi m thi u không gian lưu tr , ph c v cho quá trình i u khi n sau này. Bài báo xu t m t kĩ thu t rút g n s thi u không gian lưu tr . Kĩ thu t xu t ư pháp tuy n b m t k nhau, trên cơ s m r th c nghi m kĩ thu t xu t t ra phù b ng ph ng. lư ng b m t bi u di n mô hình 3D nh m gi m c th c hi n nh vi c tính toán góc gi a các véctơ ng thu t toán Angles trong không gian 2D. Qua h p v i các b m t g n nhau là tương i L i c m ơn. Các tác gi i xin chân thành c m ơn s h tr c a tài KC.01.17/06-10 "Nghiên c u phát tri n và ng d ng các gi i pháp công ngh thông tin hi n i tái t o nh m t ngư i 3 chi u t d li u hình thái xương s ph c v i u tra hình s và an sinh xã h i" TÀI LI U THAM KH O 1. 2. Năng Toàn, Nguy n Văn Huân - A hair material simulation approach in Virtual reality and application, Proceedings of The 7th Asian Control Conference, Hong Kong, China, 2009, pp. 541-546. http://ieee.org Năng Toàn, Nguy n Văn Huân - Morphing and Repairing a 3D Scalp Geometry in Building Hair Models and Simulation, Proceedings of 2nd International Congress on Image and Signal Processing, Tianjin, China, 2009, pp.705-710. http://ieee.org 3. Eric Landreneau and Scott Schaefer - Simplification of Articulated Meshes, Journal compilation of The Eurographics Association and Blackwell Publishing Ltd. Eurographics 28 (2009). 4. Hoppe, S. Krömker - Adaptive Meshing And Detail-Reduction Of 3d-Point Clouds From Laser Scans, Proceedings of the ISPRS Workshop '3D-ARCH, 2009. 5. Mridulika - Surface Model Simplification Method Based On Quadric Error Metrics, Guru Gobind Singh Indraprastha University, Delhi 06, Proceedings of 2nd National Conference on Challenges & Opportunities in Information Technology (COIT-2008), RIMT-IET, Mandi Gobindgarh, March 29, 2008. 6. Frédéric Payan, Stefanie Hahmann and Georges-Pierre Bonneau - Deforming surface simplification based on dynamic geometry sampling, Proceedings of International Conference on Shape Modeling and Applications, SMI'07, Lyon – France, 2007. 7. Zhang S., Wu E. - Deforming surface simplification based on feature preservation, In ICEC, 2007, pp. 139-149. 8. Connie Phong - An Introduction to 3D Geometry Compression and Surface Simplification, CSC/Math 870, 2007. 9. Jia-xin CHEN, Hai-he HU - One Mesh Model Simplification Method Based on Shape Transform of Triangles, IEEE Computer Society, 2006. http://ieeexplore.ieee.org/iel5/4089190/4089191/04089302.pdf 10. S. Siltanen, T. Lokki, and L. Savioja - Geometry Reduction In Room Acoustics Modeling, Proceedings of the Institute of Acoustics, Vol. 28, Pt.2, 2006. 132 11. Năng Toàn - ng d ng công ngh th c t i o trong b o tàng các di s n, Khoa h c và Công ngh Vi t Nam, 2004-2006, 2006. tài c p Vi n 12. Röttger S. Terrain LOD Implementations-libMini, 2004. ttp://www.vterrain.org/LOD/ Implementations/.[capture on 26/03/04] 13. Năng Toàn, Ngô Qu c T o - ơn gi n hoá ư ng cong có hi u ch nh trong quá trình véctơ hoá, chuyên san Các công trình nghiên c u và tri n khai Công ngh thông tin và vi n thông, T p chí Bưu chính vi n thông (7) (2002) 75-81. 14. Zhao, Youbing, Ji Zhou, Jiaoying Shi, and Zhigeng Pan - A Fast Algorithm for Large Scale Terrain Walkthrough, CAD/Graphics, 2001. 15. Levoy M., Pulli K., Curless B., Rusinkiewicz S., Koller D., Pereira L. - The digital michelangelo project: 3d scanning of large statues. In SIGGRAPH ’00: Proceedings of the 27th annual conference on Computer graphics and interactive techniques, New York, NY, USA, 2000, pp. 131-144. 16. Mapscan, http://www.un.org/Depts/unsd/softproj/software/mapscan.htm http://www.ons.dz/unfpa/software/mapscan.htm; http://www.aig.asn.au/utilities.htm 17. Hamann Bernd - A Data Reduction Scheme for Triangulated Surfaces, Computer Aided Geometric Design 11 (2) (1994) 197-214. 18. Schroeder, William J., Jonathan A. Zarge, and William E. Lorensen - Decimation of Triangle Meshes, Computer Graphics, SIGGRAPH ‘92 Proceedings 26 (2) (1992) 65-70. 19. Turk Greg - Re-Tiling Polygonal Surfaces, Computer Graphics, SIGGRAPH ’92 Proceedings 26 (2) (1992) 55-64. SUMMARY AN ALGORITHM TO REDUCE FACES IN 3D MODELS This paper deals with a technique to reduce faces in 3D models based on Angles algorithm in 2D, by calculating angle between two normal faces, that have the same edge. The given technique seems be effective for approximately flat surfaces. a ch : Nh n bài ngày 12 tháng 8 năm 2008 Năng Toàn, Vi n Công ngh thông tin, VAST. Nguy n Văn Huân, Khoa Công ngh thông tin, Trư ng i h c Thái Nguyên. 133