Một kỹ thuật xây dựng hệ bao tự động cho đối tượng 3D

Bài viết Một kỹ thuật xây dựng hệ bao tự động cho đối tượng 3D nêu lên việc xây dựng hệ bao (Boundiing volume hierrarchy - B VH) tự động cho một đối tượng 3D. Việc xây dựng BVH cho đối tượng thường theo mô hình từ trên xuống (top-down), từ dưới lên (bottoom-up) hoặc thêm vào (add inn); với một dạng hộp bao cụ thể.
Nội dung trích xuất từ tài liệu:
Một kỹ thuật xây dựng hệ bao tự động cho đối tượng 3DKỷ yếu Hội nghị QKQuốc gia lần thứ VIII về Nghiên cứ cơ bản và ứng dụng Công nghệ thông tin (FAIR) Hà Nội, ngày 9ứuệ);9-10/7/2015MỘT KỸ THUẬT XÂY DỰỸTỰNG HỆ BAO TỰ ĐỘNG CHO ĐỐ TƯỢNG 3DỰỐIGNguyễn Đức Hoàng1, Đỗ Năng Toàn2, Nông MnMinh Ngọc31ưuHọc viện Công nghệ Bư chính Viễn thông, 2Viện Công nghệ thnhông tin , 3ĐH Thái NguyênHhooangnd@ptit.eedu.vnTÓM TẮ - Báo cáo n đề cập đến việc xây dựng hệ bao (Boundi volume hierTẮTnàyingrarchy - BVH) tự động cho mộ đối tượngột3D. Việc xây dự BVH cho đố tượng thường theo mô hình từ trên xuống (top-down), từ dưới lên (botto3ựngốigom-up) hoặc thê vào (addêmin với một dạn hộp bao cụ th Kỹ thuật đề xuất xây dựng BVH dựa trên việc sử dụng nhn);nghể.hiều dạng hộp b khác nhau phù hợp vớibaopth tế hoạt độn của đối tượn Kỹ thuật đã được thử nghiệm và tỏ ra hiệ quả đối với c mô hình đố tượng 3D đượ xây dựnghựcngng.ãệucácốiợcth phương phá liên tục.heoápTừ khóa - hệ bao, tự độaộng, nhiều dạng hộp bao, nhận dạng va chạmgnm.I. GIỚI THIỆUGHệ bao BVH [9] đóng vai trò qu trọng trong việc biểu diễn các vật th cho phép giải quyết nhiều vấn đềouanhể,trrong lý thuyế và ứng dụng của nhận dạ va chạm, dò tia. Các kỹ thuật này ch phép giải c bài toán trếtgạngỹhocácrong nhiềulĩ vực như rĩnhrobotic, đồ họ máy tính, đ họa động, tr chơi điện tử thực tại ảo , mô phỏng v biểu diễn có khả năngọađồròử,vàótưương tác.BVH hiện nay là một trong những phương pháp tiếp cận thàn công nhất trgpnhrong các hệ thhống hiện hành [1]. Thờigian tính toán cho các hệ thố này thể hi độ ưu việt của BVH [2]:gốngiệnNT = Nv x Cv + Np x CpHình 1. Ví dụ về một hệ bao sử dụng hình chữ nhật là khối baohhàmT: Tổng thời gian tín toán;gnhNv: Số các phép thử của một cặp h bao chồng lấn;hệCv: Thời gian của ph thử cho m cặp các hệ bao;hépmộtNp: Số các phép thử của một cặp hhình cơ bản chhồng lấn;Cp: Th gian của ph thử cho m cặp các hìn cơ bản.hờihépmộtnhĐiều nà chứng tỏ m hệ thống hàymộthoạt động sẽ dựa trên hai yế tố: độ khít c hệ bao so với đối tượng (Nv, Np)dếucủaogvà độ đơn giản của phép thử chồng lấn trê một cặp hệ bao (Cv).vnửênHệ bao khối cầu (Spphere) [4] và kkhối lập phươ (AABB) [3] tạo ra phép thử chồng lấ đơn giản nhất. Trongơngpấnnkhi đó, hệ bao khối chữ nhậ (OBB) [2] và khối đa diện rời rạc có hướng (k-DO [5] cho biể diễn khít nhất. TrongkoậthOP)ểunbáo cáo này sẽ trình bày về việc ứng dụng hai loại khối biểu diễn để tối ưu cả về m độ khít củ hệ bao và độ đơn giảnbẽgmặtủacủa phép thử ccchồng lấn.Beckma [3] đưa ra giải thuật ch cây AABB Palmer [7] và Hub-bard [ đưa ra giải thuật cho câ khối cầuannahoB,v[4]iâyđể giải quyết v đề đơn giả hóa. Trong khi đó Gottscđvấnảngchalk [2] đưa ra giải thuật c khối OBB còn Klosowski [5] đưachoBra giải thuật c khối đa drchodiện k-DOP để giải quyết vấn đề về độ khít của hộp bao.Van den Bergen [8] đưa ra mộtểvnđphương thức đ giản để ph tách các h chữ nhật OBB được biết đến với tên SpđơnhânhộpOtSAT lite. Giải thuật này chỉ sử dụng 6iỉtrrong số 15 hệ trục tọa độ so giải thuật gốoốc.Trong b cáo này, v đề xây dựn hệ bao (BV cho một đối tượng 3D dựa trên việc sử dụng nhiều dạng hộpbáovấnngVH)đubao được đề cậ tới với hai mục tiêu: giảm thời gian tín toán nhưng vẫn đạt được độ chính xácbậpmnhgcc.Nguyễn Đức Hoàn Đỗ Năng Toà Nông Minh NgNng,àn,gọc413Phần cò lại của báo cáo được tổ cònchức như sau:• Phần 2: Trình bày v Hệ bao (BVvềVH);• Phần 3: Trình bày v Kỹ thuật xâ dựng hệ ba tự động với nhiều dạng h bao;vềâyaoihộp• Phần 4: Thực nghiệệm;• Phần 5: Kết luận.AOING VOLUM HIERARMERCHY)II. HỆ BA (BOUNDIA. Hộp baoAĐối với các đối tượn 3D, việc gi quyết các bài toán như nhận dạng va chạm, dò tia,... cần phải xe xét đếningiảibnembề mặt cũng n phần thể tí bên trong của đối tượng Việc này trở nên phức tạ và rất tốn tà nguyên nếu đối tượngbnhưíchg.ởạpàiuxem xét có hìn dạng phức tạp. Để phân tích các tác động lên các đối tượng này, hộp bao đượ sử dụng. Th vì việcxnhđđ,ợchaycần phải xem x toàn bộ đố tượng, hộp bao cho phép việc chỉ cần tính toán dựa trên các hình hình học đơn giản. Đốicxétốipahnvới các bài toá không yêu cầu độ chính xác quá cao, việc xem xét giới hạn ở ph tích bề m (3D) hoặc đường baovánhhânmặt(2D) của hộp bbao.Tuy nhiên, cùng với độ đơn giản tí toán được giảm xuống, các bài toán c sử dụng hộp bao cần thừa nhận:ínhcópa• Các pphép tính chỉ ddừng lại ở mứ gần đúng;ức• Tính chính xác của các phép tính sẽ dựa trên độ khít của đưahđường bao.Hình 2. Không có chồng lấn hộp bao - Không có va chạmhcbHHình 3. Có chồn lấn hộp bao - Có thể có va cngchạmHiện na để xây dựn hệ bao cho đối tượng, cá dạng hộp ba thường đượ sử dụng gồmay,ngácaoợcm:Hìn 4. Các dạng hộp baonhh4144MỘT KỸ THUUẬT XÂY DỰNG HỆ BAO TỰ ĐGĐỘNG CHO ĐỐI TƯỢNG 3D• Hộp b khối cầu: Sphere;bao• Hộp b khối lập pbaophương: AABBB;• Hộp b khối chữ n có hướng OBB;baonhậtg:• Hộp b khối đa di rời rạc có hbaoiệnP;hướng: k-DOP• Hộp b khối lồi: cbaoconvex hull.Hộp bao khối cầu: đượ biểu diễn bở tâm (c) và bán kính khối cầu (r). Hai khố cầu không choợcởibcốihồng lấn lên nh khi:hau.Hình 5. Va chạm giữa hai khối cầuhHộp ba khối chữ nh AABB: đư biểu diễn bởi tâm hộp (c) và tham s chiều dài c cạnh (rx, ry, rz). Haiaohậtượcnsốcácrkhối hộp lập phương không chồng lấn lên nhau khi (xét trong miền không gian 2DknkD):Hình 6. Va chạm giữa hai khối hộp AABBkBaonướng: được xá định bởi hai tham số: k/2 trung bình; k khoảng các lớn nhấtác2k/2chHộp ba khối đa diện rời rạc có hư- nhỏ nhất. Nh vậy nếu tro miền khôn gian 2D có thể coi AAB là 4-DOP, trong miền khhưongngóBBhông gian 3D có thể coiAABB là 6-DO Hai cặp h đa diện sẽ không chồng lấn lên nhau khi (xét trong mi ...