Luận văn:Mô hình hóa đối tượng 3D bằng phương pháp biểu diễn biên B-Rep

Chia sẻ: Nhung Thi | Ngày: | Loại File: PDF | Số trang:26

Thêm vào BST

Báo xấu

139
lượt xem 16
download

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

Luận văn:Mô hình hóa đối tượng 3D bằng phương pháp biểu diễn biên B-RepLuận văn:Mô hình hóa đối tượng 3D bằng phương pháp biểu diễn biên B-RepLuận văn:Mô hình hóa đối tượng 3D bằng phương pháp biểu diễn biên B-RepLuận văn:Mô hình hóa đối tượng 3D bằng phương pháp biểu diễn biên B-Rep

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:Mô hình hóa đối tượng 3D bằng phương pháp biểu diễn biên B-Rep

1 B GIÁO D C VÀ ĐÀO T O Đ I H C ĐÀ N NG NGUY N VĂN TÌNH MÔ HÌNH HÓA Đ I TƯ NG 3D B NG PHƯƠNG PHÁP BI U DI N BIÊN B-REP Chuyên ngành: Khoa h c máy tính Mã s : 60.48.01 TÓM T T LU N VĂN TH C SĨ K THU T Đà N ng - Năm 2011
2 Công trình ñư c hoàn thành t i Đ I H C ĐÀ N NG Ngư i hư ng d n khoa h c: TS NGUY N T N KHÔI Ph n bi n 1: PGS.TSKH. TR N QU C CHI N Ph n bi n 1: TS. NGUY N M U HÂN Lu n văn ñư c b o v t i H i ñ ng b o v ch m Lu n văn t t nghi p th c sĩ k thu t, h p t i Đà N ng vào ngày 10 tháng 9 năm 2011 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 - Thư vi n trư ng Đ i h c Sư ph m Đ i h c Đà n ng
3 M Đ U 1. Lý do ch n ñ tài Trong nh ng năm g n ñây s phát tri n c a ñ h a máy tính ñã làm thay ñ i hoàn toàn vi c tương tác gi a ngư i và máy. Nh ñó mà m t lo t các ng d ng c a máy tính ra ñ i, ñáp ng ñư c nhi u nhu c u khác nhau c a xã h i. C th như trong lĩnh v c gi i trí là s ra ñ i c a hàng lo t các game 3D, phim 3D và các phim ho t hình khác. Trong lĩnh v c k thu t là s phát tri n c a nhi u ph n m m thi t k CAD/CAM n i ti ng như AutoCAD, Pro-Engineer, Esprit, Cimatron, MasterCam... Không nh ng th , ñ h a máy tính ñóng vai trò ch y u trong vi c cung c p ki n th c cho ngành thi t k k thu t, phát huy kh năng tư duy c a ngư i thi t k , giúp cho con ngư i ñ t phá vào nh ng lĩnh v c m i.Các ph n m m này h tr t vi c thi t k mô hình ñ i tư ng 3D, ñ n vi c l p ráp các chi ti t, mô ph ng chuy n ñ ng c a c m chi ti t, và cu i cùng là vi c gia công s n ph m. Tuy nhiên, Các ph n m m này ch cho phép ngư i s d ng thi t k mô hình, l p trình gia công, ño ñ c, k t xu t ra các t p tin d li u theo ñ nh d ng c a ph n m m, vi c tái t o mô hình v t th chưa ñư c h tr hoàn ch nh. Do v y, vi c nghiên c u xây d ng mô hình hóa ñ i tư ng 3D linh ho t, ph c v quá trình nghiên c u, ti n t i tái t o các v t th t máy ño 3 chi u CMM hay t máy quét là m t yêu c u c p thi t. M t v n ñ quan tr ng trong vi c xây d ng công c mô hình hóa là bi u di n b m t các ñ i tư ng 3D. Trong bi u di n b m t các ñ i tư ng 3D, ngoài các v n ñ bi u di n b m t ñ m b o ch t lư ng còn ph i ñáp ng yêu c u v tính ñơn 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 b m t ph c v cho các bư c mô ph ng sau này.Vì v y ta c n nghiên c u xây d ng m t c u trúc d
4 li u ñ mô hình hóa ñ i tư ng 3D d a trên phương pháp bi u di n biên B-Rep (Boundary Reprernsentation). Đ tài t p trung nghiên c u k thu t bi u di n ñ h a 3D; bi u ñư ng và m t cong tham s B-Spline, NURBS ñ mô hình hóa ñ i tư ng 3D theo phương pháp bi u di n biên B-Rep. 2. Ý nghĩa khoa h c - Xây d ng các ñ i tư ng 3D d a trên ñư ng cong và m t cong tham s NURBS. - Cung c p ch c năng mô hình hóa ñ i tư ng 3D, thao tác trên ñ i tư ng 3D và hi n th các thông s hình h c c a ñ i tư ng, k t xu t ra t p tin mô t thông tin v ñ i tư ng. - Là cơ s ñ ti n t i tái t o các v t th th c ño ñư c t máy ño 3 chi u CMM hay t máy quét hình lazer. 3. Ý nghĩa th c ti n H tr cho Game3D, phim ho t hình 3D… Mô ph ng o, ph c v ng d ng trong ngành khoa h c k thu t như y h c, xây d ng … Ph c v cho công tác gi ng d y và th c hành thi t k mô hình ñ i tư ng tham s 3D cho sinh viên các ngành k thu t. 4. M c ñích c a ñ tài - Xây d ng c u trúc d li u theo mô hình B-Rep lưu tr ñ i tư ng 3D. - Mô hình hóa và hi n th ñ i tư ng 3D theo c u trúc B-Rep ñư c xây d ng. - Quan sát và hi u ch nh ñ i tư ng 3D,k t xu t m t mô hình B-Rep m u ra file ñ nh d ng nh m ph c v cho các bư c ti p theo trong quá trình s n xu t gia công nh tr giúp máy tính (CAM).
5 5. Đ i tư ng và ph m vi nghiên c u - Tìm hi u các lý thuy t và cách bi u di n ñ i tư ng 3D - Tìm hi u, nghiên c u công c ph n m m cho phép mô hình hóa 3D - Xây d ng c u trúc d li u ñ lưu tr và bi u di n các ñ i tư ng 3D d a trên mô hình B-Rep. - Nghiên c u các ñ c ñi m, tính ch t c a ñư ng cong, m t cong B-Spline và NURBS. - Tìm hi u b thư vi n openNURBS. - Đ tài t p trung vào nghiên c u và xây d ng c u trúc d li u cho phép mô hình hóa ñ i tư ng 3D b ng phương pháp B-Rep. Đ ng th i xây d ng chương trình minh h a dùng ñ mô hình hóa và bi u di n ñ i tư ng 3D theo mô hình B-Rep. 6. Phương pháp nghiên c u - Thu th p, phân tích các tài li u có liên quan ñ n ñ tài - Nghiên c u và l a ch n phương hư ng gi i quy t ñ tài. - Nghiên c u phương pháp mô hình hóa ñ i tư ng 3D theo phương pháp bi u di n biên B-Rep. - Phân tích yêu c u ñ t ra, t ch c c u trúc d li u cho mô hình B-Rep, t ñó xây d ng chương trình minh h a cho ñ tài. - Ki m tra, th nghi m và ñánh giá k t qu . 7. B c c c a lu n văn N i dung lu n văn ñư c chia thành 3 chương: Chương 1: T ng quan v mô hình hóa ñ i tư ng 3D Chương 2: Đư ng và m t cong tham s Chương 3: Xây d ng ñ i tư ng 3D theo phương pháp B-Rep
6 Chương 1 T NG QUAN V MÔ HÌNH HÓA Đ I TƯ NG 3D 1.1 T ng quan v mô hình hóa Trong k thu t bi u di n, ngư i ta phân thành hai nhóm: mô hình hóa v t th và mô hình hóa hình h c. K thu t mô hình hóa hình h c ñư c phát tri n trong các ngành công nghi p t ñ ng hóa và ch y u ñư c s d ng ñ thi t k các hình d ng c a xe hơi. Hi n nay, mô hình này còn ñư c ng d ng trong các ngành như công nghi p hàng không, h i quân… và m t s 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 m t hình d ng. K thu t mô hình hóa v t th ñư c xây d ng d a trên các thông tin bi u di n ñ y ñ , chính xác, rõ ràng m t ñ i tư ng trong không gian chúng có th t o ra các mô hình trên máy tính v i kh năng phân lo i b t kỳ ñi m nào trong không gian ba chi u: phía trong, phía ngoài, ho c là trên b m t c a ñ i tư ng. 1.2 Mô hình hóa ñ i tư ng 3D Hai mô hình cơ b n c a ng d ng ñ h a là d a trên m u s hóa và d a trên ñ c trưng hình h c. Trong ng d ng ñ h a d a trên m u s hóa thì các ñ i tư ng ñ h a ñư c t o ra b i lư i các ñi m nh r i r c. Các ñi m nh này có th ñu c t o ra b ng các chương trình v , máy quét ... Các ñi m nh này mô t t a ñ xác ñ nh v trí và giá tr m u. Thu n l i c a ng d ng này là d dàng thay ñ i nh b ng cách thay ñ i màu s c hay v trí c a các ñi m nh, ho c di chuy n vùng nh t nơi này sang nơi khác. Tuy nhiên, ñi u b t l i là không th xem xét ñ i tư ng t các góc nhìn khác nhau. ng d ng ñ h a d a trên ñ c trưng hình h c bao g m các ñ i tư ng ñ h a cơ s như ño n th ng, ña giác ... Chúng ñư c lưu tr b ng các mô hình
7 và các thu c tính. Ví d : ño n th ng ñư c mô hình b ng hai ñi m ñ u và cu i, có thu c tính như màu s c, ñ dày. Ngư i s d ng không thao tác tr c ti p trên các ñi m nh mà thao tác trên các thành ph n hình h c c a ñ i tư ng. 1.2.1 H t a ñ trong không gian 1.2.1.1 H t a ñ Descartes 1.2.1.2 H t a ñ c c 1.2.2 Quá trình x lý hi n th trong ñ h a 3D Hình 1.4 Quá trình x lý và hi n th 3D 1.3 Bi u di n ñ i tư ng 3D Có nhi u phương pháp khác nhau ñ mô t các ñ i tư ng 3D. Tùy thu c vào t ng ñ i tư ng c th , ta dùng phương pháp sao cho phù h p v i thu c tính c a các lo i ñ i tư ng ñó. Ch ng h n ñ bi u di n các ñ i tư ng Euclid ñơn gi n như là các kh i ellipse, kh i ña di n ta s d ng các m t ña giác và m t b c hai. Đ bi u di n các m t tròn xoay, và các ñ i tư ng dùng ñ thi t k các mô hình máy bay, bánh răng và các c u trúc công ngh khác thư ng ñư c bi u
8 di n thông qua m t cong (curves). Các phương pháp ti p c n th t c (procedural method) như Fractal cho phép chúng ta bi u bi n m t cách chính xác các ñ i tư ng như mây, th m c và các ñ i tư ng t nhiên khác. 1.3.1 Bi u di n m t lư i 3D Vi c s d ng mô hình khung lư i cho phép ta hình dung ñư c k t c u bên trong c a m t mô hình 3D b ng cách xoay chuy n ñ i tư ng và ch n l a xóa các ñư ng n (nh ng ñư ng mà thư ng khi ngư i ta không th trông th y-thông qua các m t ph ng c t ngang). Khi th hi n b ng mô hình này, các ñ i tư ng này không gi ng th c t l m. Vì v y ngư i ta dùng các k thu t t o bóng và lo i b các ñư ng và m t khu t. Mô hình này thư ng nhanh nên ngư i ta thư ng dùng nó trong vi c xem phác th o (preview) các ñ i tư ng, ñ c bi t là trong các h CAD. M t d ng thông thư ng c a lư i ña giác là các dãy tam giác (triale strip). Khi ña giác ñư c mô t b i nhi u hơn ba ñ nh, các ñ nh c a nó có th không ñ ng ph ng. Đi u này có th d n ñ n các l i tính toán. M t phương pháp ñơn gi n là phân ña giác này thành các tam giác. Hình 1.7 Lư i tam giác và lư i t giác
9 1.3.2 Bi u di n b m t trơn tham s Trong trư ng h p các ñ i tư ng th c s ph c t p, ngư i ta thư ng dùng m t hay nhi u m t cong trơn ghép n i l i v i nhau. M i thành ph n dùng ñ ghép n i ñư c g i là m t vá (patch). 1.3.3 M t cong d ng n 1.3.3.1 M t tròn xoay 1.3.3.2 M t c u 1.3.3.3 M tEllipsoid 1.4 K t lu n chương Trong chương này nêu ra phương pháp bi u di n ñ i tư ng 3D, quy trình x lý và hi n th ñ i tư ng trong không gian 3D. Đ ng th i nêu cách xây d ng các ñ i tư ng là ñư ng cong, m t cong ñư c xây d ng b i phương trình không tham s . Tuy nhiên trong các ng d ng ñ h a máy tính, h u h t các ñ i tư ng ñư c bi u di n dư i d ng phương trình không tham s chưa th hi n ý tư ng ngư i thi t k . V i nh ng b có ñ l i lõm b t kỳ thì ñòi h i khi thay ñ i v trí c a m t ñi m ñi u khi n thì yêu c u ph i có s thay ñ i c c b ch không ph i toàn c c trên b m t. Đ ñáp ng yêu c u trên ta s d ng ki u vectơ nút (vector knot) không ñ u và m t cong NURBS cho vi c bi u di n các ñ i tư ng h c h p 3D.Do v y trong chương 2 s ñưa ra phương pháp t ng th v nh ng mô hình toán h c ñ bi u di n và xây d ng các lo i ñư ng và m t cong ph c h p trong không gian 3D trên máy tính mà ta g i là ñư ng cong và m t cong tham s .
10 Chương 2 BI U DI N ĐƯ NG VÀ M T CONG THAM S 2.1 Gi i thi u Khác v i nh ng phương pháp bi u di n ñư ng và m t b i các công th c toán h c chu n t c, tư ng minh. ñây chúng ta s quan tâm ñ n các công c cho phép ch ra các d ng ñư ng và m t khác nhau d a trên các d li u. Đi u này có nghĩa là v i m t ñư ng cong cho trư c mà ta chưa xác ñ nh công th c toán h c c a nó thì làm th nào ñ có th n m b t ñư c d ng c a ñư ng cong ñó m t cách tương ñ i chính xác qua vi c s d ng m t t p các ñi m P0, P1 … cùng v i m t phương pháp n i suy nào ñó t t p ñi m này ñ t o ra ñư ng cong mong mu n v i m t ñ chính xác cho phép. 2.2 Đư ng cong Bezier 2.2.1 Gi i thi u 2.2.2 Phương trình bi u di n 2.2.3 Thu t toán v ñư ng congbezier qua 3 ñi m 2.2.4 Tính ch t ñư ng cong Bezier 2.3 Đư ng cong tham s B-Spline 2.3.1 Gi i thi u 2.3.2 Phương trình bi u di n 2.3.3 Các tính ch t ñư ng cong B-Spline 2.4 M t cong tham s B-Spline 2.4.1 Gi i thi u 2.4.2 Phương trình bi u di n 2.4.3 Các tính ch t c a m t cong tham s B-Spline 2.5 Đư ng cong tham s NURBS 2.5.1 Gi i thi u 2.5.2 Phương trình bi u di n ñư ng cong tham s NURBS
11 2.5.3 Tính ch t ñư ng cong tham s NURBS 2.6 M t cong tham s NURBS 2.6.1 Phương trình bi u di n m t cong tham s NURBS 2.6.2 Tính ch t m t cong tham s NURBS 2.7 Vector nút không ñ u ( non-uniform) Vector nút là m t t p giá tr ki m soát ñ cong c a b m t, nó th hi n ki u ñư ng cong ñ u hay không ñ u, tu n hoàn hay không tu n hoàn… S ph n t c a m t vetor nút ñư c tính b ng t ng (n + k +1); v i n là s ñi m ñi u khi n, k là b c c a ñư ng cong. Trong vectơ nút không tu n hoàn, giá tr các nút xu t hi n t i các biên ñư c l p l i và các nút bên trong các bư c nút b ng nhau. N u m t trong hai ñi u ki n này ho c c hai ñi u ki n này không ñư c th a mãn thì vectơ nút g i là không ñ u. Ví d các nút không ñ u có th t o ra b ng cách ñ t các giá tr l p l i ñ i v i các nút kho ng gi a [0 1 2 3 3 4 5] hay t o ra các bư c nh y không b ng nhau gi a các nút [0 0. 2 0.5 0. 75 1]. 2.8 Thu t toán NURBS g c NURBS là m t b m t cong ñư c dùng ñ bi u di n, mô hình hóa hình d ng và mô ph ng các ñ i tư ng 3D. Hình d ng c a các ñ i tư ng ñư c xác ñ nh b i các ñi m ñi u khi n. NURBS có tính cơ ñ ng cao, d dàng ñi u ch nh hình d ng t ng ph n c a b m t và không nh hư ng ñ n toàn b b m t, t c là tính ñi u khi n c c b trên b m t c a ñ i tư ng [2]. M t b m t NURBS ñư c bi u di n b ng công th c sau: (2.18)
12 Trong ñó: Pi,j: là các ñi m ñi u khi n W: là ñ r ng c a vector nút Ni,k-u(u), Nj,k-v(v): là các hàm cơ b n n,m : là s ñi m ñi u khi n K-u, k-v: là b c c a các hàm cơ b n theo hư ng u và v Ni,k-u(u), Nj,k-v(v) ñư c bi u di n b ng m t hàm ñ quy Cox- de Boor Hàm ñ quy Cox-de Boor ñư c bi u di n như sau:[2] (2.19) 2.9 Tính liên t c c a ñư ng cong tham s Tính liên t c c a m t ñư ng cong t i m t ñi m d ng mô t làm th nào nh ng ñư ng cong g p nhau t i các ñi m d ng[16]. 2.10 Xây d ng m t cong tham s 2.10.1 Các m nh Bezier (Bezier surface patches) Xét ñư ng cong Bezier như là m t hàm theo tham s v và có các ñi m ki m soát thay ñ i theo u. Ta có công th c: (2.20) Lúc này, khi u thay ñ i ta s có các ñi m ki m soát thay ñ i kéo theo ñư ng cong Bezier cũng thay ñ i theo. S bi n thiên c a các ñư ng cong Bezier này trong không gian s t o ra m t m t cong.
13 2.10.2 N i các m nh Bezier l i v i nhau M c ñích là ñ t o ra m t d ng m t cong ph c t p g m nhi u m nh Bezier k t h p l i v i nhau sao cho trơn tru t i các biên chung. Khi n i hai m nh Bezier l i v i nhau (m i m nh có m t kh i ña di n ki m soát riêng và cùng s d ng công th c trên v i u,v bi n thiên trong ño n [0, 1]), v n ñ là làm sao ñ chúng có th n i vào nhau m t cách trơn tru? Hai m nh s g n vào nhau t t c các ñi m d c biên chung n u các ña di n ki m soát c a chúng trùng kh p v i nhau biên. Đi u này có ñư c là do d ng c a ñư ng cong Bezier biên ch ph thu c vào ña giác ki m soát n m biên c a kh i ña di n ki m soát. Do ñó, ñ dán ñư c ta ch c n ch n các ña giác ki m soát biên cho hai m t là trùng nhau. Hình 2.12 Minh h a hai m nh Bezier dán l i v i nhau V tính liên t c t i ti p tuy n, ñi u ki n ñ là m i c p c nh c a các kh i ña di n t i biên ph i là c ng tuy n. 2.10.3 Các m nh B-Spline (B-Spline patches) Các hàm B-Spline có th dùng d ng tích tensor thay cho d ng ña th c Bernstein ñ ñ t ñư c tính ki m soát cao hơn khi thi t k m t cong
14 (2.23) Kh i ña di n ki m soát có (M+1)x(n+1) ñ nh và u, v bi n thiên t 0 t i giá tr l n nh t c a nút trong các vector nút tương ng c a chúng. 2.11 Bi u di n ñ i tư ng 3D theo phương pháp B-Rep 2.11.1 Gi i thi u M t v n ñ quan tr ng trong vi c bi u di n b m t các ñ i tư ng 3D là ñ m b o ch t lư ng và ph i ñáp ng yêu c u v tính ñơn 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 b m t ph c v cho các bư c mô ph ng sau này. Trong th c t khi bi u di n b m t 3D, không ph i b m t nào cũng trơn hay cong ñ u. Có nh ng b m t trơn nhưng l i có nh ng ñ l i lõm b t kỳ. V i nh ng b m t có ñ cong như v y, thì ñòi h i khi thay ñ i v trí c a m t ñi m ñi u khi n thì yêu c u ph i có s thay ñ i c c b ch không ph i toàn c c trên b m t. Đ ñáp ng yêu c u trên ta s d ng ki u vectơ nút (vector knot) không ñ u và m t cong NURBS cho vi c bi u di n các ñ i tư ng h c h p 3D. Phương pháp bi u di n b m t (bi u di n biên) mô t các ñ i tư ng ba chi u b ng m t t p h p các b m t gi n h n ph n bên trong và ph n bên ngoài[5]. 2.11.2 Khái ni m B-Rep (hay phương pháp bi u di n biên) là phương pháp bi u di n v t th d a trên các gi i h n b m t c a chúng. Phương pháp này này d a trên khái ni m c u trúc hình h c mà các ñ i tư ng v t th ñư c gi i h n b i t p h p các m t. Nh ng m t này là các vùng ho c các m t con c a các b m t ñóng và ñ nh hư ng. M t b
15 m t ñóng là b m t mà trong ñó nó liên t c và không b phân m nh, chia nh . B m t ñ nh hư ng có th ñư c phân bi t thành hai ph n rõ r t b ng cách s d ng các vectơ pháp tuy n nh m ch ra ph n bên trong và ph n bên ngoài c a mô hình v t th ñư c xây d ng (hay nói cách khác là m t trong và m t ngoài). M i m t ñư c bao quanh b i các c nh và m i c nh ñư c gi i h n b i các ñ nh. Do ñó, theo c u trúc hình h c, m t mô hình bi u di n biên c a m t ñ i tư ng bao g m các m t, các c nh, và các ñ nh c a ñ i tư ng liên k t v i nhau ñ ñ m b o s th ng nh t c a m t mô hình[8]. 2.11.3 Các thành ph n cơ b n c a B-Rep Phương pháp B-Rep có 2 thành ph n cơ b n: C u trúc hình h c (topology): Bao g m nh ng thông tin v m i liên h gi a các ñ nh, c nh, m t ñ t o ra hình d ng c a v t th . Đ ng th i nó bao g m cách ñ nh hư ng gi a các c nh và các m t. Hình h c (geometry): Xác ñ nh các ñ i tư ng c a c u trúc hình h c trong không gian, ví d như t a ñ c a m t ñ nh, phương trình c a ñư ng cong và m t cong [10]. Thông tin hai thành ph n cơ b n này c a phương pháp B- Rep có quan h ch t ch v i nhau và không th tách r i nhau. N u ñi u ñó x y ra thì s t o nên các ñ i tư ng không xác ñ nh trong không gian. Thêm vào ñó, cách ñ nh hư ng c a m t m t r t quan tr ng. Thông thư ng, m t m t ñư c bao quanh b i t p các ñ nh. S d ng quy t c bàn tay ph i, th t các ñ nh ñ mô t m t m t c th ph i ñ m b o r ng các vectơ pháp tuy n c a m t ñó hư ng ra ngoài v t th . Thông thư ng thì th t này là theo ngư c chi u kim ñ ng h . Vì v y, b ng cách ki m tra các vectơ pháp tuy n chúng ta có th xác ñ nh ph n bên trong và ph n bên ngoài c a m t v t th theo
16 phương pháp B-Rep. S ñ nh hư ng ñư c th c hi n trên cho t t c các m t. Như v y, các y u t cơ b n c a m t mô hình B-Rep là các m t, các c nh và các ñ nh. 2.11.4 Công th c Euler-Poincaré Công th c Euler-Poincaré miêu t m i quan h gi a s ñ nh, s c nh và s m t c a m t v t th . Nói cách khác nó ñư c dùng ñ ki m tra tính h p l c a m t v t th [8] V – E + F – (L - F) – 2(S - G) = 0 Trong ñó - V: s ñ nh (vertices) - E: s c nh (edges) - F: s m t (faces) - G: s l xuyên qua v t th (penetrated holes) - S: s shell.Shell là t p h p các m t k t n i trong v t th . Chú ý s shell này luôn l n hơn ho c b ng m t. - L: s vòng l p trong và vòng l p ngoài. 2.11.5 Bi u di n v t th theo phương pháp B-Rep Phương pháp B-Rep b t ngu n t mô hình ña di n ñư c s dùng ñ bi u di n nh ng ñ i tư ng ho c các c nh (scenes) có các ñư ng khu t và các m t không nhìn th y ñư c. Phương pháp này g m ba th c th , ñó là các m t, ñ nh, c nh và các thông tin hình h c kèm theo ñ t o nên thành ph n cơ b n c a phương pháp B-Rep. Ngoài các thông tin hình h c như phương trình các m t và t a ñ ñi m, phương pháp này còn ch ra các m t, c nh, ñ nh liên k t v i các thành ph n khác như th nào, chúng ñư c g i là c u trúc hình h c (topology). Có th nói c u trúc hình h c là ch t k t dính các y u t hình h c l i v i nhau.
17 V i m c tiêu làm ñơn gi n hóa các gi i thu t, ph n l n ñ xác ñ nh chu trình c a các c nh bao quanh m t m t, ta s d ng c u trúc half-edge. C u trúc half-edge miêu t cách k t n i gi a các m t, c nh, và ñ nh (g i t t là các thành ph n c a c u trúc). Nó ñư c s d ng ñ mô t hình d ng các kh i ña giác. Tuy nhiên, c u trúc d li u c a nó ch dùng ñ mô t s g n k t. Nhi u cách bi u di n khác nhau ñư c xác ñ nh b ng cách g n k t các thông tin hình h c v i các thành ph n c a c u trúc. 2.12 Thư vi n OpenNURBS Chương trình ñư c xây d ng d a trên b thư vi n openNURBS. Đây là b thư vi n d a trên ngôn ng C++ ñư c phát tri n b i Robert McNeel c a hãng Rhinoceros. Nó h tr các ph n m m ñ h a, quy trình CAD/CAM phát tri n nh ng b công c dùng ñ chuy n ñ i chính xác các mô hình hình h c 3D gi a các ng d ng. Đ c bi t, openNURBS dùng ñ ñ c, xu t các mô hình ñ nh d ng file 3dm, h tr trên t t c các h ñi u hành như Window, Mac, Linux. 3dm là ñ nh d ng file dùng ñ xây d ng các mô hình v t th 3D d a trên các b m t NURBS. Do tính uy n chuy n và linh ho t, NURBS ñư c s d ng trong t t c các lĩnh v c liên quan ñ n thi t k và bi u di n mô hình 3D [6],[9]. 2.13 K t lu n chương Chương này trình bày tính ch t, phương trình bi u di n cũng như thu t toán xây d ng ñư ng cong, m t cong tham s . Ngoài ra cũng nêu khái ni m v B-Rep và gi i thi u qua thư vi n mã ngu n m OpenNURBS, công th c Euler-Poincaré. M c ñích c a chương này là cơ s lý thuy t xây d ng d ng chương trình mô hình hóa ñ i tư ng 3D theo phương pháp bi u di n biên (B-Rep).
18 Chương 3 XÂY D NG Đ I TƯ NG 3D THEO PHƯƠNG PHÁP B-REP M t ñ i tư ng ñư c bi u di n theo phương pháp B-Rep ñư c mô t b i hai thành ph n là hình h c (Geometric) và c u trúc hình h c (Topological). M i thành ph n ñ u ch a các ph n t mang m t s thông tin k t n i. Đ mô t các thông tin k t n i gi a các ñ nh, c nh và m t thì c n s d ng c u trúc n a giao tuy n (half- edge). 3.1 C u trúc half-edge theo phương pháp B-Rep C u trúc half-edge cho bi t ñư c c nh nào ñư c liên k t v i ñ nh nào; m t nào ñư c liên k t v i ñ nh nào. Half-edge là ngu n thông tin k t n i. Các thành ph n khác ñơn gi n ch là g n k t v i half-edge v i nhau. Đ miêu t half-edge, ñ i v i không gian hai chi u ñó là m t ño n th ng có hư ng và b t ngu n t m t ñ nh. M t half-edge ñ u g n li n v i m t c nh trư c nó và m t c nh ti p theo, mà chúng cũng là các half-edge. M t c p half-edge có chung hai ñi m ñ u cu i nhưng ngư c chi u nhau. Hình 3.1C u trúc d li u half-edge 3.2 Thành ph n hình h c trong B-Rep Trong các ñ i tư ng cong, chúng ta bi u di n hình d ng c a ñư ng cong và m t cong như nh ng thu c tính các c nh và m t. C u trúc d li u s d ng trong phương pháp này ñư c xây d ng d a trên
19 c u trúc d li u half-edge. Nh ng ñ i tư ng cơ b n sau ñư c s d ng trong c u trúc c a mô hình v t th là: kh i ñ c (solid), khu v c (region), v (shell), b m t (face), vòng l p (loop), c nh (edge), n a giao tuy n (half-edge), ñ nh (vertex). M t region ñ nh nghĩa m t th tích duy nh t trong không gian. Như v y, m i c nh là m t con tr tr ñ n m t b n ghi ñ nh rõ cách bi u di n chính xác các ñư ng cong cơ s . Nó có th mô hình ñư c v t th khi duy t qua danh sách các c nh, ñ ng th i thu ñư c nh ng thông tin c a các m t li n k . Hình 3.3 Thành ph n hình h c (Geometric) trong B-Rep
20 3.3 Thành ph n c u trúc hình h c trong B-Rep Chúng ta ñưa ra m t c u trúc d li u có hai m c ñ bi u di n mô hình hình h c c a m t v i s lư ng c nh b t kỳ và không làm nh hư ng ñ n các m t xung quanh. M t m t có m t con tr tr ñ n b n ghi liên k t v i t p các m t có b n c nh. Sau ñó, m t m t không ñư c chia nh trong c u trúc d li u B-Rep ban ñ u. M t m t trư c h t ph i ñư c sao chép sang c u trúc d li u m i và ñư c chia nh ñ ñ nh nghĩa duy nh t m t m t b n c nh. B ng cách này thì vi c phân chia không nh hư ng ñ n các m t xung quanh trong c u trúc B-Rep ban ñ u. T t c các m t b n c nh trong c u trúc m i ñ u có m t con tr tr ñ n m t b n ghi khác trong ñó m t b n c nh ñư c bi u di n như là m t x p x ña di n[5],[8]. Hình 3.4 Liên k t các b m t trong c u trúc B-Rep