Luận văn thạc sĩ: Xây dựng bề mặt lưới từ tập hợp điểm 3D và phương pháp chia nhỏ bề mặt lưới

Chia sẻ: Sdfas Vfdtg | Ngày: | Loại File: PDF | Số trang:13

Thêm vào BST

Báo xấu

82
lượt xem 10
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Xây dựng bề mặt lưới từ tập hợp điểm 3D và phương pháp chia nhỏ bề mặt lưới nhằm tìm hiểu cách biểu diễn mô hình 3 D. Xây dựng cấu trúc dữ liệu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn thạc sĩ: Xây dựng bề mặt lưới từ tập hợp điểm 3D và phương pháp chia nhỏ bề mặt lưới

B GIÁO D C VÀ ĐÀO T O Công trình ñư c hoàn thành t i Đ I H C ĐÀ N NG Đ I H C ĐÀ N NG Ngư i hư ng d n khoa h c: TS. NGUY N T N KHÔI Đ PHÚ DUY Ph n bi n 1: XÂY D NG B M T LƯ I T T P H P ĐI M 3D VÀ Ph n bi n 2: PHƯƠNG PHÁP CHIA NH B M T LƯ I Chuyên ngành: Khoa h c máy tính Lu n văn ñư c b o v trư c H i ñ ng ch m Lu n Mã s : 60.48.01 văn t t nghi p th c sĩ k thu t h p t i Đ i h c Đà N ng vào ngày tháng năm 2012 TÓM T T LU N VĂN TH C SĨ K THU T Có th tìm hi u lu n văn t i: - Trung tâm thông tin – H c li u, Đ i h c Đà N ng - Trung tâm H c li u, Đ i h c Đà N ng Đà N ng – Năm 2012
1 2 “XÂY D NG B M T LƯ I T T P H P ĐI M 3D VÀ M Đ U PHƯƠNG PHÁP CHIA NH B M T LƯ I” 1. Lý do ch n ñ tài 2. Đ i tư ng, ph m vi, và phương pháp nghiên c u Trong nh ng năm g n ñây s phát tri n c a ñ h a máy tính Đ tài t p trung vào nghiên c u xây d ng b m t lư i 3D t làm thay ñ i hoàn toàn tương tác gi a ngư i và máy, khi các k thu t t p h p ñi m r i r c và k thu t chia nh b m t nh m c i thi n ch t ng d ng ñ h a ngày càng cao hơn nên có nhi u ngư i quan tâm lư ng b m t lư i ñư c xây d ng và làm m n m t lư i. Đ ñ t ñư c nghiên c u ñ n lĩnh v c này. Nh ñó mà các ng d ng ñ h a trên m c tiêu nghiên c u ñã ñ ra, trong ñ tài ñã th c hi n cách ti p c n máy tính ra ñ i như: phim ho t hình, game và ñ nh hư ng tương lai nghiên c u sau: v i các h th ng th c t i o... ñã ñóng góp cho s phát tri n chung Trên cơ s lý thuy t v ñ h a, tìm hi u các v n ñ v mô c a ngành Công ngh Thông tin. Do v y, ñ h a máy tính tr thành hình hóa các ñ i tư ng 3D, v các phương pháp bi u di n b m t lư i m t lĩnh v c h p d n và có nhi u ng d ng trong th c t . 3D trên máy tính. Nghiên c u các thu t toán xây d ng b m t lư i t Bi u di n b m t các ñ i tư ng 3 chi u (3D) ñư c coi là các t p h p ñi m r i r c trong không gian. Tìm hi u các phương pháp bư c kh i ñ u trong m t h th ng mô ph ng th c t i o, góp ph n chia nh b m t lư i tam giác. t o nên m t h th ng mô ph ng hoàn ch nh. M t trong nh ng cách T vi c nghiên c u và ti p thu các phương pháp, các thu t ti p c n bi u di n b m t các ñ i tư ng 3 chi u ph bi n hi n nay là toán và các ph n m m chuyên d ng tiên ti n c a th gi i trong lĩnh d a trên k thu t bi u di n b m t lư i. v c ñ h a trên máy tính. Tìm hi u rõ các ưu, như c ñi m c a t ng Trong bi u di n b m t o 3 chi u ngoài các v n ñ bi u di n phương pháp ñ ñ xu t cách ti p c n phù h p cho ñ tài. S d ng b m t ñ m b o ch t lư ng còn ph i ñáp ng yêu c u v tính ñơn các công ngh , các công c l p trình như: Ngôn ng l p trình Visual gi n nh m gi m thi u không gian lưu tr , rút ng n th i gian bi u di n C++ 6.0, thư vi n h tr x lý ñ h a OpenGL. b m t ph c v cho các bư c mô ph ng sau này. Vi c xây d ng m t 3. M c ñích c a ñ tài h th ng mô hình hóa là bao g m xây d ng và bi u di n b m t lư i Tìm hi u cách bi u di n mô hình 3D. các ñ i tư ng 3 chi u nh m tái t o l i các mô hình th c t trong Xây d ng c u trúc d li u ñ lưu tr các ph n t và bi u di n không gian t t p ñi m ño ñư c c a ñ i tư ng th c. các b m t lư i 3D. V i nhu c u mô hình hóa b m t lư i tam giác t t p h p ng d ng gi i thu t Delaunay xây d ng lư i tam giác t t p ñi m ño ñư c trong không gian 3 chi u, t i ưu b m t lư i ñ lưu tr , h p ñi m 3D ñ u vào ñ t o b m t lư i tam giác nh m tái t o mô tinh ch nh m t lư i r i r c h i t v m t b m t nh n. hình. Xu t phát t nhu c u th c ti n như trên, tôi ñ xu t ñ tài ng d ng phương pháp Loop chia nh b m t lư i nh m c i lu n văn cao h c như sau: ti n, xây d ng b m t m n, trơn.
3 4 4. Ý nghĩa khoa h c th c ti n năng phân lo i b t kỳ ñi m nào trong không gian ba chi u: phía Mô hình hóa ñ i tư ng 3D, x lý trên ñ i tư ng 3D và hi n trong, phía ngoài, ho c là trên b m t c a ñ i tư ng. th các thông s hình h c thu c tính c a ñ i tư ng. 1.1 H t a ñ trong không gian Kh năng tái t o v t th t t p h p ñi m r i r c 3D thành mô H t a ñ trong không gian là d a vào 3 tr c vuông góc nhau hình ñ i tư ng lư i 3D. t ng ñôi m t x'Ox, y'Oy, z'Oz mà trên ñó ñã ch n 3 véc-tơ ñơn v i, j, Thi t k và hi u ch nh mô hình lư i 3D, k t xu t d li u sang k sao cho ñ dài c a 3 véc-tơ này b ng nhau [1], [2]. ñ nh d ng c a ph n m m CAD/CAM chuyên d ng. 1.2 Phép bi n ñ i trong mô hình 3D Ph c v cho công tác nghiên c u thi t k mô hình ñ i tư ng Các ñi m trong không gian ba chi u ñư c bi u di n b ng h tham s 3D trong các phòng thí nghi m, công ty. tr c t a ñ ba chi u, có th xem là m r ng c a h tr c t a ñ hai 5. B c c lu n văn chi u. Trong th gi i hai chi u, m t ph ng XY ch a toàn b ñ i N i dung lu n văn bao g m các chương sau: tư ng. Trong th gi i ba chi u, m t tr c Z vuông góc ñư c ñưa ra ñ Chương 1: T ng quan v cơ s ñ h a 3D t o thêm hai m t ph ng chính khác là YZ và ZX [1], [2]. Chương 2: Xây d ng lư i t t p h p ñi m 3D và phương 1.3 Bi u di n ñ i tư ng 3D pháp chia nh b m t lư i Loop Các ñ i tư ng trong th gi i th c ph n l n là các ñ i tư ng Chương 3: Phân tích xây d ng chương trình xây d ng b m t ba chi u còn các thi t b hi n th ch bi u di n hai chi u. Do v y lư i 3D mu n có hình nh ba chi u ta c n ph i ti n hành gi l p. Ngoài ra khi Chương 1 T NG QUAN V CƠ S Đ H A chúng ta mô hình hoá và hi n th m t ñ i tư ng ba chi u, ta c n ph i Trong k thu t bi u di n mô hình, ta phân thành hai nhóm xem xét r t nhi u khía c nh khác nhau như m t ph ng, m t cong và bi u di n mô hình sau: mô hình hóa hình h c và mô hình hóa v t th . m t s thông tin v bên trong các ñ i tư ng. K thu t mô hình hóa hình h c ñư c phát tri n trong các 1.3.1 Bi u di n mô hình khung dây ngành công nghi p t ñ ng hóa và ch y u ñư c s d ng ñ thi t k Bi u di n mô hình ta có th bi u di n dư i d ng mô hình các hình d ng xe hơi. Hi n nay, mô hình này còn ñư c ng d ng khung dây, mô hình lư i ña giác, … trong các ngành như công nghi p hàng không, h i quân… và m t s Bi u di n mô hình d ng khung dây cho ta th y ñư c các chi lĩnh v c khác. Mô hình này cũng h tr chính cho vi c ñi u khi n v ti t bên trong c a mô hình, s d ng các phương pháp di chuy n, m t hình d ng. xoay, xoá ñi các ñư ng khu t (ñ th hi n mô hình d ng m t). K thu t mô hình hóa v t th ñư c xây d ng d a trên các 1.3.2 Bi u di n ñư ng, m t cong thông tin bi u di n ñ y ñ , chính xác, rõ ràng m t ñ i tư ng trong Các ñư ng cong và m t cong có th ñư c t o ra t m t t p không gian chúng có th t o ra các mô hình trên máy tính v i kh các hàm toán h c ñ nh nghĩa các ñ i tư ng ho c t p các ñi m trên ñ i
5 6 tư ng. Đ i v i các ñ i tư ng hình h c như hình tròn hay elip thì thư Trong công ngh CNC các ñ i tư ng th c ñư c t o ra t các vi n ñ h a ñã cung c p s n hàm v ñ i tư ng lên m t ph ng hi n hình kh i 3 chi u m u có trong máy tính. Đ t o ra các mô hình ba th . Hình bi u di n ñư ng cong là t p các ñi m d c theo hình chi u chi u m u trên máy tính, nhi u k thu t khác nhau ñư c áp d ng và c a ñư ng mô t b i hàm s . Nhưng v i các ñư ng cong hay m t ñư c g i là công ngh ñ o ngư c. Trên th gi i công ngh ñ o ngư c cong không có quy lu t, thì t p ñi m hay lư i ña giác x p x v i ñư c ng d ng r ng rãi vào các lĩnh v c m i như CAD/CAM, th c ñư ng m t cong s t o ra. H ñ h a hay t o các lư i tam giác ñ t i o, ki n trúc, b o t n các di s n văn hoá, v.v... Công ngh ñ o ñ m b o tính ñ ng ph ng c a các c nh [2]. ngư c thu th p d li u c a ñ i tư ng th c dư i d ng các ñi m, t các 1.4 Thư vi n x lý ñ h a OpenGL d li u ñi m thu ñư c m t lư i ña giác ñư c xây d ng ñ liên k t các OpenGL là m t tiêu chu n k thu t ñ h a nh m m c ñích ñi m ba chi u trong không gian. Mô hình ñ i tư ng th c ñư c s hoá t o ra m t giao di n l p trình ng d ng ñ h a 3D ñư c phát tri n hoàn toàn sau khi th c hi n m t s bư c tinh ch nh như làm m n ñ u tiên b i Silicon Graphic, Inc. OpenGL ñã tr thành m t chu n (bóng), vá l th ng, ho c chia nh lư i ña giác ñ tăng cư ng chi ti t công nghi p và các ñ c tính k thu t c a OpenGL do U ban k thu t hoá mô hình s . Xu t phát t các v n ñ trên, trong lu n văn này tôi ARB. OpenGL cho phép phát tri n các ng d ng ñ h a s d ng tri n khai nghiên c u các phương pháp bi u di n b m t lư i t các nhi u ngôn ng l p trình khác nhau như C/C++, Java, Delphi, v.v…, t p h p ñi m ño ñư c nh m tìm ki m m t gi i pháp t t nh t ñ tri n tuy nhiên OpenGL cũng có th ñư c dùng trong ng d ng ñ h a 2D. khai mô hình hoá các ñ i tư ng 3D t t p h p ñi m ñã cho. Giao di n l p trình này ch a kho ng 250 hàm ñ v các c nh ph c 2.1 Bi u di n b m t lư i 3D t p t nh ng hàm ñơn gi n và ñư c ng d ng r ng rãi trong các trò Đ lưu tr cơ s d li u s trong không gian nh m tham chơi ñi n t . Ngoài ra còn ñư c dùng trong các ng d ng CAD, th c chi u chính ñ t o mô hình. H th ng thông tin ñ a lý GIS là m t cơ t i o, mô ph ng khoa h c, mô ph ng thông tin, phát tri n trò chơi. s d li u s chuyên d ng trong h tr c t a ñ không gian. Như v y OpenGL s d ng h t a ñ theo quy t c bàn tay ph i. GIS có quan h v i các ng d ng cơ s d li u. Toàn b thông tin trong GIS ñ u liên k t v i tham chi u không gian. Cách th c nh p, Chương 2 PHƯƠNG PHÁP T O LƯ I 3D VÀ CHIA NH B lưu tr , phân tích d li u trong GIS ph i ph n ánh ñúng cách th c M T LƯ I LOOP thông tin s ñư c s d ng trong vi c l p quy t ñ nh hay nghiên c u Mô hình hoá các ñ i tư ng 3D trên máy tính b ng cách s c th . hoá các ñ i tư ng th c ñã và ñang ñư c ñ u tư r ng rãi trên th gi i. 2.2 Xây d ng b m t lư i T i Vi t Nam, công ngh CNC ñã ñư c bi t ñ n và ng d ng r ng Phương pháp xây d ng lư i tam giác t m t t p h p ñi m là rãi vào nhi u ngành công nghi p khác nhau. phương pháp d ng hình trong không gian 2-chi u và 3-chi u. Các quá trình tam giác hoá s ñư c th c hi n v i d li u ñ u vào là t p
7 8 h p h n ñ n các ñi m ñã thu th p ñư c. Thu t toán tam giác hoá có tròn nào ñi qua hai ñi m pj,pj mà không ch a b t kỳ ñi m nào thì th trình bày trong [4], [10], [11]: (pj,pj) là c nh tam giác Delaunay [7], [8], [9]. 2.3 Các lư c ñ xây d ng b m t lư i 3D 2.3.2 Sơ ñ Delaunay Cho V là t p h u h n các ñ nh trên m t ph ng R2 [3]. Cho E V i D(P) là các ñư ng th ng ñ i ng u c a V(P). M i tam là t p các c nh mà các ñi m ñ u cu i là các ñ nh thu c t p V. Ta có giác c a D(P) tương ng ñ n ñ nh c a V(P). M i c nh c a D(P) các ñ nh nghĩa sau: tương ng ñ n c nh c a V(P). M i nút c a D(P) tương ng ñ n vùng Đ nh nghĩa 1. Lư i tam giác T = (V,E) là m t ñ th ph ng c a V(P). Đư ng bao c a D(P) là bao l i c a P. Bên trong tam giác mà m i c nh không ch a ñ nh nào khác ngoài hai ñ nh ñ u cu i c a c a D(P) là bao l i c a P. nó, không có hai c nh nào c t nhau và t t c các m t là nh ng tam Phép chia nh t o ra s tam giác l n nh t không t n t i m t giác v i h i c a chúng là bao l i c a t p ñ nh V. c nh nào n i hai ñi m có th thêm vào mà không phá v phép chia Đ nh nghĩa 2. Bài toán n i các ñi m cho trư c trên m t nh S. Tam giác c a t p P (n>=2 ñi m) là Delaunay n u và ch n u ph ng b ng các ño n th ng không c t nhau ñ t o thành lư i tam giác ñư ng tròn qua nó không ch a ñi m th tư. g i là bài toán xây d ng lư i tam giác. V m t b n ch t, bài toán xây 2.4 Thu t toán Delaunay d ng lư i tam giác t t p ñi m cho trư c là không duy nh t. M t Thu t toán t o lư i tam giác Delaunay là m t bài toán cơ b n trong các ñi u ki n xây d ng lư i tam giác hay ñư c s d ng trong trong hình h c tính toán và nó ñư c s d ng trong r t nhi u lĩnh v c các ng d ng là ñi u ki n Delaunay. như h th ng thông tin ñ a GIS, ph n t h u h n, ñ h a máy tính và Đ nh nghĩa 3. Ta nói r ng lư i tam giác th a ñi u ki n ña phương ti n… Delaunay n u bên trong ñư ng tròn ngo i ti p c a m i tam giác Đ xây d ng lư i tam giác Delaunay t t p h p ñi m ñ u không ch a b t kỳ ñi m nào thu c lư i tam giác ñó. vào ta có th chia thành các hư ng ti p c n sau: 2.3.1 Sơ ñ Voronoi a) Hư ng ti p c n chia ñ tr Sơ ñ Voronoi bi u di n như sau: m i vùng Voronoi V(pi) là Đ u tiên, t p ñi m ñ u vào ñư c chia thành các t p con, th c ña giác l i, v i V(pi) là không ñóng kín n u pi thu c bao l i c a t p hi n xây d ng lư i tam giác cho m i t p con r i h p nh t l i ñ t o ñi m. N u v là ñ nh c a Voronoi ñi m giao nhau c a V(p1), V(p2) ra lư i tam giác k t qu cu i cùng. Tuy nhiên, ph n h p nh t các k t và V(p3) thì v là tâm c a ñư ng tròn C(v) xác ñ nh b i p1, p2, p3. qu con thư ng cài ñ t khá ph c t p. Gi i pháp này ñư c ñ c p b i Trong ñó C(v) là ñư ng tròn ngo i ti p tam giác Delaunay tương Dwyer trong công trình [6]. ng v i v. Bên trong C(v) không ch a ñi m pj. N u pj là ñi m g n b) Hư ng ti p c n s d ng dòng quét nh t ñ n pj thì (pj,pj) là c nh tam giác Delaunay. B t kì m t ñư ng
9 10 Gi i thu t theo hư ng ti p c n này ñã ñư c ñưa ra b i Fortune [7], sau ñó ñư c t ng h p l i b i de Berg trong công trình [5]. Fortune ñã phát tri n gi i thu t xây d ng ñ th ñ i ng u gi a lư i tam giác Delaunay và sơ ñ Voronoi. Vi c cài ñ t gi i thu t là khá ph c t p. Hình 2.16 Bi u di n gi i thu t chia nh Loop c) Hư ng ti p c n thêm t ng ñi m tu n t Mô hình chia nh theo phương pháp Loop ti n hành chia nh Các gi i thu t thu c hư ng ti p c n này khá ñơn gi n ñ cài m t lư i tam giác b ng cách th c hi n m t s bư c l p. Chú ý r ng ñ t. Gi s chúng ta có lư i tam giác Delaunay ñư c xây d ng t i-1 các ña giác t o nên các b m t ph i là các tam giác, các b m t không ñi m. Đi m th i s ñư c thêm vào lư i tam giác theo cách sau: Xác th là nh ng ña giác ph ng b t kỳ. ñ nh tam giác ch a ñi m i m i thêm vào lư i. Phân rã tam giác ñó Gi i thu t này do Charles Teorell Loop ñ c p trong [12], thành các tam giác con thu c lư i và hi u ch nh tho ñi u ki n ông ñã c i ti n gi i thu t chia nh m i tam giác thành 4 tam giác con. Delaunay [4]. Gi i thu t này cũng ñư c bi t ñ n v i tên là gi i thu t chia nh Loop 2.5 Phương pháp chia nh b m t lư i tam giác Loop nh phân. Các mô hình 3D ñư c t o ra t các t p h p ñi m b ng gi i Gi i thu t Loop nh phân b t ñ u b ng t p ñi m là các ñ nh thu t Delaunay s t o ra các b m t lư i tam giác thô. Đ t o ra ñư c c a tam giác. M i phép l p tính m t t p các c nh và các ñi m ñ nh các b m t lư i m n hơn ta có th áp d ng các thu t toán chia nh b m i t o nên các ñ nh m i c a các tam giác nh hơn. Đ c bi t, ñ i v i m t lư i. m i c nh và m t ñi m ñ nh m i thì m t ñi m c nh m i ñư c tính cho Phương pháp Loop chia nh b m t lư i là d a vào các lư i m i ñ nh c a lư i tam giác. tam giác ñ u vào. V i b m t lư i ñ u vào là các b m t tam giác Gi i thu t chia nh Loop ñư c chia làm hai bư c. Bư c ñ u ñư c t o ra t phương pháp t o lư i thông qua gi i thu t Delaunay. tiên t o ra t t c các ñi m và tam giác m i, và bư c th hai s ñ nh v Trong ph m vi c a lu n văn này, tôi ñã t p trung vào phương pháp l i t t c các ñi m cũ. Gi i thu t Loop là gi i thu t tính x p x nghĩa Loop chia nh b m t lư i, b ng các phép tính x p x , nh m t o ra là các ñ nh s ñư c hi u ch nh l i trong su t quá trình phân chia. các b m t có tính liên t c. V i thu t toán Loop, chia nh m i m t Các ñ nh l là các ñ nh ñư c thêm vào trong su t quá trình trong lư i ñ u vào ñư c chia thành b n m t nh hơn. phân chia trong khi ñó các ñ nh ch n là các ñ nh s n có trư c lúc chia. Các c nh biên là c nh n m trên ñư ng biên c a lư i. Nghĩa là, n u t n t i m t c nh ab c a tam giác mà không có chung v i c nh tam giác nào khác thì nó chính là c nh biên. Đ nh a, b có th mô t
11 12 như là các ñ nh biên. Các c nh bên trong (không ph i c nh biên) là Các bư c xây d ng chương trình tái t o b m t lư i t t p t p b sung vào b t c c nh nào có chung 2 tam giác. M t ñ nh bên h p ñi m 3D và phương pháp chia nh b m t lư i ñư c minh h a trong ch n m trên các c nh bên trong. như sau: c β 1/8 a β β 3/8 3/8 b v aa 1-kβ β a a a 1/8 β d a β 1/2 1/2 1/8 3/4 1/8 (a) ñ nh l (b) ñ nh ch n Hình 2.18 Hình minh h a ñ nh l và ñ nh ch n Hình 3.1 Sơ ñ t o lư i tam giác Delaunay và làm m n Chương 3 PHÂN TÍCH XÂY D NG CHƯƠNG TRÌNH XÂY 3.1 T ch c d li u b m t lư i D NG B M T LƯ I 3D Ngày nay, k thu t mô hình hoá các ñ i tư ng 3D ñã có Vi c tái t o l i mô hình t các v t th t các ñ i tư ng th c nhi u ng d ng r ng rãi, ñ c bi t trong thi t k và bi u di n các ñ i b ng công ngh tái t o mô hình v t th trên máy tính. Vi c thu th p tư ng ba chi u. Vi c tái l p l i các ñ i tư ng 3D th c b ng các s d li u c a ñ i tư ng th c dư i d ng các ñi m, liên k t các d li u d ng cơ ch tái t o ngư c b ng các thu th p d li u các ñ i tư ng và tái t o l i mô hình mô hình c a ñ i tư ng th c trong không gian th c dư i d ng ñi m ñ liên k t các d li u và tái t o l i mô hình. Đ 3D. T các d li u ñi m, m t lư i tam giác ñư c xây d ng ñ liên lưu tr t p h p ñi m 3D thu ñư c và mô hình hóa hình h c ta s k t các ñi m 3 chi u trong không gian s d ng thu t toán Delaunay. d ng ngôn ng VRML (Virtual Reality Modeling Language). Mô hình ñ i tư ng ñư c s hoá, sau khi th c hi n m t s bư c tinh 3.2 Xây d ng lư i tam giác Delaunay t t p h p ñi m r i r c ch nh, làm m n, vá l th ng ho c chia nh lư i tam giác ñ tăng 3D cư ng chi ti t hoá mô hình s b ng gi i thu t chia nh Loop. 3.2.1 Sơ ñ kh i c a thu t toán ñư c mô t như sau:
13 14 sau: v i ñ nh g c ñư c ký hi u là e →Goc, ñ nh ñích ký hi u là e→Dich, m t ph ng bên trái ký hi u e→Trai, m t ph ng bên ph i ký hi u là e→Phai, c nh ngư c chi u ký hi u là e→NguocChieu, c nh ti p theo có cùng g c ký hi u là e→Goctiep, c nh ti p theo ngư c chi u kim ñ ng h thu c m t ph ng bên trái là ký hi u là e→Traitiep, cùng chi u kim ñ ng h ký hi u là CCW và ngư c chi u kim ñ ng h ký hi u là CW. V i m t c nh b t kỳ e (ký hi u c nh là e) thì ta d tìm th y các ñ nh lân c n, các c nh, các m t và c nh ñ i x ng theo hư ng ngư c l i. Hình 3.2 Sơ ñ x lý t p h p ñi m t o lư i tam giác Delaunay 3.2.2 C u trúc d li u 3.2.2.1 Phân tích c u trúc d li u Phép chia nh S c t mi n M ch a các ñi m P:={p1,p2,…,p3} thành ba t p h p ñ nh, c nh, m t ph ng liên k t v i nhau có các thu c tính sau: t p ñ nh là các ñi m pi thu c M, t p c nh là các ño n th ng n i các ñ nh thu c M, t p m t ph ng ch a các tam giác ñ u Hinh 3.3 Các thành ph n quanh c nh e thu c M, ñư ng biên c a m t ph ng qua các c nh và ñ nh 3.2.2.2 C nh góc (QuadEdge) Chúng ta bi u di n phép chia nh S b i c u trúc d li u c nh góc (quad-edge). M i m u tin v c nh (edge record) ch a b n c nh e[0], e[1], e[2], e[3] m i c nh e[r] v i r=0,1,2,3 ch a hai trư ng Data và Next. Trư ng Data lưu tr thông tin hình h c, trư ng Next ch a tham chi u c nh ti p theo. V i m i c nh c a phép chia nh luôn có hư ng ng v i chi u các c nh. M i c nh ký hi u là e chúng ta có th ñ nh nghĩa như Hinh 3.4 Bi u di n hư ng theo chi u ngư c chi u kim ñ ng h
15 16 3.2.3 Các toán t thao tác trên c nh góc (Quad-edge) 3.2.3.1 Toán t t o c nh e → MakEdge() Tr v c nh e khi kh i t o c u trúc d li u. Do ñó, có m t c nh duy nh t c a phép chia nh nên không có vòng l p: eGoc # eDich //g c c a c nh e khác v i ñích c a c nh e eTrai = ePhai //c nh bên trái c a e b ng v i c nh bên ph i c a e Hình 3.5 Bi u di n theo hư ng cùng chi u kim ñ ng h eTraitiep = ePhaitiep = eNguocchieu // c nh bên trái ti p c a e b ng v i c nh bên ph i ti p c a e b ng c nh ngư c chi u c a e eGoctiep = eGoctruoc = eNguocchieu // g c bên trái ti p c a e b ng v i g c bên ph i trư c c a e b ng v i c nh e ngư c chi u Hình 3.6 C u trúc c nh góc (quad-edge) e Hình 3.8 Kh i t o c nh e 3.2.3.2 Toán t n i c nh Splice(a,b) Toán t này n i vòng aGoc và bGoc không ph thu c hai Hình 3.7 C u trúc quad-edge c a ñ th (vòng ñ m là ñ nh, vòng nét c nh vòng aTrai và bTrai. Trong trư ng h p ñ t là m t ph ng) N u hai vòng là riêng bi t Splice k t h p chúng thành m t.
17 18 N u c hai cùng m t vòng, Splice b nó thành hai ph n. e.Dich=b.Dich; } N u c hai cùng m t vòng nhưng có chi u ñ i ngư c, Splice 3.2.4 Xây d ng lư i tam giác Delaunay ñ o ngư c th t c a ño n trong vòng. Xây d ng sơ ñ Voronoi và các tam giác Delaunay t c u 3.2.3.3 Toán t ghép c nh Connect(a,b) trúc d li u quad-edge theo phương pháp chia ñ tr “divide and Th c hi n t o c nh e m i ñi t ñ nh c a a ñ n g c c a b do conquer” c a Guibas và Stofi v i b c n log n có c i ti n t i ưu hoá ñó aTrai=eTrai=bTrai. Đư c ñ nh nghĩa qua toán t Splice như sau: c p phát b nh , th t c tr n và ki m tra b n ñi m trong ñư ng tròn connect(a,b) [6]. { e=MakEdge(); e.Goc=a.Dich; N i dung chính là phương pháp chia ñ tr ta chia nh t p e.Dich=b.Goc; ñi m làm hai ph n bên trái L và bên ph i R, xây d ng tam giác splice(e,a.Traitiep); Delaunay theo ñi u ki n ki m tra Incircle(A,B,C,D) tu n t cho các splice(e.Nguocchieu,b); ñi m ph n bên trái L (ký hi u L) và bên ph i R (ký hi u là R) theo return e; } th t tăng c a y. Sau ñó tr n hai ph n có k t qu . 3.2.3.4 Toán t lo i b c nh Delete(e) 3.3 Chia nh b m t lư i Loop Th c hi n lo i b c nh e ra kh i c u trúc c a quad-edge. Chia nh là m t k thu t mà nh m tăng ch t lư ng c a m t Ngư c v i toán t ghép c nh Connect. lư i b ng cách t o ra thêm nhi u ñ nh. S chia b m t là m t quá delete(e) trình l p ñi l p l i. Quá trình này b t ñ u v i m t m t lư i ña giác { splice(e,e.Goctruoc); cho trư c và sau m i bư c l p m t mô hình c th ñư c áp d ng vào splice(e.Nguocchieu,e.Nguocchieu.Go m t lư i. Nhi u ñ nh m i và các m t cơ s ñư c t o d a trên các ctruoc); } c nh xung quanh nó. 3.2.3.5 Toán t hoán v c nh Swap(e) Trong lu n văn này, ñơn gi n tôi th c hi n thu t toán chia swap(e) nh Loop. V n còn nhi u thu t toán chia nh t t hơn nhưng ñ i v i { a=e.Goctruoc; nh ng ngư i m i b t ñ u trong vi c phân chia m t lư i tam giác v i b=e.Nguocchieu.Goctruoc; thu t toán Loop là s kh i ñ u phù h p. splice(e,a); Kh i ñ u cho thu t toán Loop là ñ c lư i tam giác Delaunay, splice(e.Nguocchieu,b); bư c k ti p là áp d ng thu t toán chia nh theo phương pháp Loop, splice(e,a.Traitiep); quá trình chia nh t o ra m t lư i tam giác m n, tô bóng lư i tam splice(e.Nguocchieu,b.Traitiep); giác và xu t ra màn hình theo sơ ñ kh i c a thu t toán Loop như e.Goc=a.Dich; sau:
19 20 Thu t toán chia nh Loop ch có th áp d ng cho m t lư i tam giác nhưng ñó không ph i là v n ñ vì m t lư i các ña giác li n k có th chuy n thành d ng m t lư i tam giác b ng cách phân chia b m t g m 2 bư c: Bư c 1: t o t t c các ñi m và tam giác m i Bư c 2: tinh ch nh t t c các ñi m cũ không ñư c t o trong bư c 1. Đây là thu t toán g n ñúng. Có nghĩa là có s ñi u ch nh các ñ nh ñang t n t i trong su t quá trình phân chia. Trong chương trình ñã xây d ng các l p m i LoopSubdivisionEdge và LoopSubdivision. L p Hình 3.26 Sơ ñ x lý lư i tam giác t o ra lư i tam giác m n LoopSubdivisionEdge lưu tr các thông tin v c nh bao g m các Thu t toán chia nh Loop cũng tương t như thu t toán chia ñi m k t thúc, các tam giác li n k và các ñ nh m i trên c nh này ñ nh ña giác, vì c hai ñ u th c hi n trên các lư i tam giác và chia nh giúp ki m tra xem có ph i là c nh bao quanh hay không và ñ có các m t tam giác thành 4 tam giác trong m i bư c. Trong trư ng h p ñư c m i quan h li n k m t cách nhanh chóng trong thu t toán c a Loop thì m c tiêu là xây d ng m t b m t m n v i m t hình d ng phân chia Loop. L p LoopSubdivision ñ m trách toàn b công vi c t ng quát ñư c ñi u khi n b ng ña giác g c. Khi k t thúc, gi i thu t th c hi n c a thu t toán Loop. loop ñ t các ñ nh m i s d ng m t n g m có 4 ñ nh cũ và ñ t l i Quy trình tính toán : ñ nh cũ b ng cách s d ng m t n khác sáp nh p t t c ñ nh trung G i hàm build_edge_set(mesh, edge_set, adjacent_edge_set) gian ñ tìm t t c các c nh và t o ra danh sách các c nh li n k cho m i ñ nh. Theo s lư ng các c nh và hình tam giác, chúng ta có th bi t s lư ng ñ nh và hình tam giác trong lư i m i. C p phát b nh cho lư i m i. Bư c 1: t o t t c các ñi m m i. LoopSubdivisionEdge có th giúp ki m tra có ñúng là các c nh bao quanh hay không m t cách Hình 3.27 Hình minh h a cho cài ñ t thu t toán Loop nhanh chóng.
21 22 Bư c 2: tinh ch nh t t c các ñi m cũ. S d ng các ñ nh c a toán Delaunay v i t p ñi m 2D danh sách c nh li n k ñ ki m tra ñ nh ranh gi i và tìm các ñ nh V i t p h p ñi m lư i ñ u vào, ñư c lưu tr trong file có ranh gi i li n k . ph n m r ng là Vertex.tri. Chương trình ñ c file và cho hi n th K t n i m i ñ nh và t o lư i m i. dư i d ng ñi m ta thu ñư c như hình. Thay lư i cũ b ng các ñ nh m i và các tam giác m i; Khi quá trình phân chia s làm thay ñ i kích c m t lư i, chương trình ph i c p phát b nh m i cho m i h at ñ ng phân chia. Và chương trình cũng nên xoá b nh cũ sau khi lư i m i ñư c t o ra. 3.4 K t qu th c hi n chương trình Hình 3.30 T p ñi m 3D ñ u vào Hình 3.31 Lư i Delaunay Chương trình ñư c xây d ng trên môi trư ng Visual Studio nhìn theo hư ng hình chi u b ng nhìn theo hư ng hình chi u b ng C++ 6.0, k t h p thư vi n ñ h a OpenGL. V i d li u ñ u vào khác nhau nên trong lu n văn này tôi xây d ng hai chương trình ñ ñ c d li u khác nhau. Sau khi ch y chương trình thì ta có các k t qu th c nghi m như sau: V i t p h p ñi m lư i ñ u vào, ñư c lưu tr trong file có Hình 3.32 T p ñi m 3D ñ u vào theo hư ng hình chi u ñ ng ph n m r ng là Vertex.nod. Chương trình ñ c file và cho hi n th dư i d ng ñi m ta thu ñư c như hình. Th c hi n thu t toán Delaunay v i t p h p ñi m ñ u vào ta thu ñư c k t qu hình sau: Hình 3.33 Lư i Delaunay nhìn theo hư ng hình chi u ñúng Th c hi n ch y chương trình chia nh Loop v i file ñ u vào ch a lư i tam giác Delaunay ta có k t qu sau: Hình 3.28 T p h p ñi m 2D Hình 3.29 Sau khi th c hi n thu t
23 24 K t qu th c nghi m xây d ng ñư c m t lư i tam giác b ng phương pháp Delaunay. Các t p h p ñi m thu th p ñư c thông qua các hình m u (v t th , ñ a hình,…) là t p h p các ñi m 2 chi u và 3 chi u, nh ng t p h p ñi m này không có t ch c. T t p h p ñi m, s d ng phương pháp Delaunay tam giác hoá. Vi c xây d ng ñư c m t lư i tam giác Hình 3.34 Sau khi chia nh m t lư i l n th nh t t các t p ñi m 2 chi u và 3 chi u ch là m t lư i thô nên c n th c hi n m t s thao tác tinh ch và làm m n. Sau m t quá trình x lý thu ñư c m t lư i tam giác ñ c t v hình m u. Đ th c hi n ñi u này lu n văn ñã ñ xu t gi i pháp chia nh m t lư i tam giác b ng cách s d ng gi i thu t Loop. Đ chia nh m t lư i, trong lu n văn ti n hành tìm hi u và nghiên c u lý thuy t v lĩnh v c này. Có r t nhi u thu t toán áp d ng Hình 3.35 Sau khi chia nh m t lư i l n th 2 ñ chia nh lư i ñ t i ưu b m t lư i. Nhưng do ñ tài nghiên c u K T LU N VÀ HƯ NG PHÁT TRI N ch s d ng lư i tam giác Delaunay nên tôi ti n hành nghiên c u v Ngày nay ñ h a máy tính ngày càng phát tri n nhanh chóng gi i thu t Loop chia nh b m t lư i. K t qu ñã xây d ng ñư c m t thì vi c nghiên c u và ng d ng vào t ng lĩnh v c th c t là m t xu chương trình chia nh m t lư i tam giác, làm m n b m t lư i. hư ng t t y u. Trong quá trình tìm hi u, nghiên c u tái t o b m t Tuy nhiên trong lu n văn này ch d ng l i m c xây d ng t lư i t t p h p ñi m ño ñư c trong không gian và chia nh b m t t p h p ñi m ñã có, chưa có th s d ng các thi t b ñ c d ng ñ quét lư i v a t o ra t t p h p ñi m nh m làm m t lư i ñ t ñư c k t qu mô hình v t th trong môi trư ng không gian th c. Nên lu n văn ch t t hơn, lu n văn ñã ñ t ñư c k t qu kh quan. K t qu ñ t ñư c c a d ng l i m c mô hình hoá v t th . lu n văn v m t lý thuy t ñã ñi sâu vào tìm hi u v cơ ch ñ h a Hi n nay công ngh tái t o ngư c ñã và ñang phát tri n r t trên máy tính, tìm hi u các qui trình v x lý, hi n th ñ i tư ng, mô m nh trên th gi i và c Vi t Nam, công ngh ñã ñư c áp d ng hình hoá các v t th trong môi trư ng ñ h a 3 chi u. Nghiên c u r ng rãi vào các lĩnh v c m i như CAD/CAM, th c t i o, ki n trúc, cách xây d ng m t lư i tam giác t t p h p ñi m 3 chi u r i r c b o t n di s n văn hoá nh m tái t o l i các hình m u ñiêu kh c. trong không gian, trong quá trình nghiên c u, tôi nh n th y v i thu t Hư ng phát tri n c a ñ tài là ti p t c hoàn thi n chương toán Delaunay ta có th d dàng xây d ng m t lư i tam giác t m t trình, b sung thêm vào các ch c năng c a các ph n m m thi t k t p h p ñi m. CAD/CAM hi n có.