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

Kỷ yếu Hội nghị Q<br /> K<br /> Quố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<br /> ứu<br /> ệ<br /> );<br /> 9-10/7/2015<br /> <br /> MỘT KỸ THUẬT XÂY DỰ<br /> Ỹ<br /> T<br /> ỰNG HỆ BAO TỰ ĐỘNG CHO ĐỐ TƯỢNG 3D<br /> Ự<br /> ỐI<br /> G<br /> Nguyễn Đức Hoàng1, Đỗ Năng Toàn2, Nông M<br /> n<br /> Minh Ngọc3<br /> 1<br /> <br /> ưu<br /> Học viện Công nghệ Bư chính Viễn thông, 2Viện Công nghệ th<br /> n<br /> hông tin , 3ĐH Thái Nguyên<br /> H<br /> ho<br /> oangnd@ptit.e<br /> edu.vn<br /> <br /> TÓM TẮ - Báo cáo n đề cập đến việc xây dựng hệ bao (Boundi volume hier<br /> TẮT<br /> này<br /> ing<br /> rarchy - BVH) tự động cho mộ đối tượng<br /> ột<br /> 3D. 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 (botto<br /> 3<br /> ựng<br /> ối<br /> g<br /> om-up) hoặc thê vào (add<br /> êm<br /> in 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 nh<br /> n);<br /> ng<br /> hể.<br /> hiều dạng hộp b khác nhau phù hợp với<br /> bao<br /> p<br /> th 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ựng<br /> hực<br /> ng<br /> ng.<br /> ã<br /> ệu<br /> các<br /> ối<br /> ợc<br /> th phương phá liên tục.<br /> heo<br /> áp<br /> Từ khóa - hệ bao, tự độ<br /> a<br /> ộng, nhiều dạng hộp bao, nhận dạng va chạm<br /> g<br /> n<br /> m.<br /> <br /> I. GIỚI THIỆU<br /> G<br /> Hệ 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 đề<br /> o<br /> uan<br /> hể,<br /> tr<br /> rong 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<br /> ết<br /> g<br /> ạng<br /> ỹ<br /> ho<br /> các<br /> rong nhiều<br /> lĩ vực như r<br /> ĩnh<br /> robotic, đồ 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<br /> ọa<br /> đồ<br /> rò<br /> ử,<br /> và<br /> ó<br /> tư<br /> ương tác.<br /> BVH hiện nay là một trong những phương pháp tiếp cận thàn công nhất tr<br /> g<br /> p<br /> nh<br /> rong các hệ th<br /> hống hiện hành [1]. Thời<br /> gian tính toán cho các hệ thố này thể hi độ ưu việt của BVH [2]:<br /> g<br /> ống<br /> iện<br /> N<br /> T = Nv x Cv + Np x Cp<br /> <br /> Hình 1. Ví dụ về một hệ bao sử dụng hình chữ nhật là khối bao<br /> h<br /> h<br /> àm<br /> <br /> T: Tổng thời gian tín toán;<br /> g<br /> nh<br /> Nv: Số các phép thử của một cặp h bao chồng lấn;<br /> hệ<br /> Cv: Thời gian của ph thử cho m cặp các hệ bao;<br /> hép<br /> một<br /> Np: Số các phép thử của một cặp h<br /> hình cơ bản ch<br /> hồng lấn;<br /> Cp: Th gian của ph thử cho m cặp các hìn cơ bản.<br /> hời<br /> hép<br /> một<br /> nh<br /> Điều nà chứng tỏ m hệ thống h<br /> ày<br /> một<br /> hoạt động sẽ dựa trên hai yế tố: độ khít c hệ bao so với đối tượng (Nv, Np)<br /> d<br /> ếu<br /> của<br /> o<br /> g<br /> và độ đơn giản của phép thử chồng lấn trê một cặp hệ bao (Cv).<br /> v<br /> n<br /> ử<br /> ên<br /> Hệ bao khối cầu (Sp<br /> phere) [4] và k<br /> khối lập phươ (AABB) [3] tạo ra phép thử chồng lấ đơn giản nhất. Trong<br /> ơng<br /> p<br /> ấn<br /> n<br /> khi đó, 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. Trong<br /> k<br /> o<br /> ật<br /> h<br /> OP)<br /> ểu<br /> n<br /> bá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ản<br /> b<br /> ẽ<br /> g<br /> mặt<br /> ủa<br /> của phép thử c<br /> c<br /> chồng lấn.<br /> 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ầu<br /> ann<br /> a<br /> ho<br /> B,<br /> v<br /> [4]<br /> i<br /> ây<br /> để giải quyết v đề đơn giả hóa. Trong khi đó Gottsc<br /> đ<br /> vấn<br /> ản<br /> g<br /> chalk [2] đưa ra giải thuật c khối OBB còn Klosowski [5] đưa<br /> cho<br /> B<br /> ra giải thuật c khối đa d<br /> r<br /> cho<br /> diệ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<br /> ể<br /> v<br /> n<br /> đ<br /> phương thức đ giản để ph tách các h chữ nhật OBB được biết đến với tên S<br /> p<br /> đơn<br /> hân<br /> hộp<br /> O<br /> t<br /> SAT lite. Giải thuật này chỉ sử dụng 6<br /> i<br /> ỉ<br /> tr<br /> rong số 15 hệ trục tọa độ so giải thuật gố<br /> o<br /> ốc.<br /> 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ộp<br /> báo<br /> vấn<br /> ng<br /> VH)<br /> đ<br /> u<br /> bao đượ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ác<br /> b<br /> ập<br /> m<br /> nh<br /> g<br /> c<br /> c.<br /> <br /> Nguyễn Đức Hoàn Đỗ Năng Toà Nông Minh Ng<br /> N<br /> ng,<br /> àn,<br /> gọc<br /> <br /> 413<br /> <br /> Phần cò lại của báo cáo được tổ c<br /> òn<br /> chức như sau:<br /> • Phần 2: Trình bày v Hệ bao (BV<br /> về<br /> VH);<br /> • 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;<br /> về<br /> ây<br /> ao<br /> i<br /> hộp<br /> • Phần 4: Thực nghiệ<br /> ệm;<br /> • Phần 5: Kết luận.<br /> <br /> AO<br /> ING VOLUM HIERAR<br /> ME<br /> RCHY)<br /> II. HỆ BA (BOUNDI<br /> A. Hộp bao<br /> A<br /> Đố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 đến<br /> i<br /> ng<br /> iải<br /> b<br /> n<br /> em<br /> bề 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ượng<br /> b<br /> như<br /> ích<br /> g.<br /> ở<br /> ạp<br /> ài<br /> u<br /> xem 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ệc<br /> x<br /> nh<br /> đ<br /> đ<br /> ,<br /> ợc<br /> hay<br /> cầ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. Đối<br /> c<br /> xét<br /> ối<br /> p<br /> a<br /> h<br /> n<br /> vớ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 bao<br /> v<br /> án<br /> h<br /> hân<br /> mặt<br /> (2D) của hộp b<br /> bao.<br /> 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:<br /> ính<br /> có<br /> p<br /> a<br /> • Các p<br /> phép tính chỉ d<br /> dừng lại ở mứ gần đúng;<br /> ức<br /> • Tính chính xác của các phép tính sẽ dựa trên độ khít của đư<br /> a<br /> h<br /> đ<br /> ường bao.<br /> <br /> Hình 2. Không có chồng lấn hộp bao - Không có va chạm<br /> h<br /> c<br /> b<br /> <br /> H<br /> Hình 3. Có chồn lấn hộp bao - Có thể có va c<br /> ng<br /> chạm<br /> <br /> Hiện na để xây dựn hệ bao cho đối tượng, cá dạng hộp ba thường đượ sử dụng gồm<br /> ay,<br /> ng<br /> ác<br /> ao<br /> ợc<br /> m:<br /> <br /> Hìn 4. Các dạng hộp bao<br /> nh<br /> h<br /> <br /> 414<br /> 4<br /> <br /> MỘT KỸ THU<br /> UẬT XÂY DỰNG HỆ BAO TỰ Đ<br /> G<br /> ĐỘNG CHO ĐỐI TƯỢNG 3D<br /> <br /> • Hộp b khối cầu: Sphere;<br /> bao<br /> • Hộp b khối lập p<br /> bao<br /> phương: AABB<br /> B;<br /> • Hộp b khối chữ n có hướng OBB;<br /> bao<br /> nhật<br /> g:<br /> • Hộp b khối đa di rời rạc có h<br /> bao<br /> iện<br /> P;<br /> hướng: k-DOP<br /> • Hộp b khối lồi: c<br /> bao<br /> convex hull.<br /> <br /> 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 ch<br /> o<br /> ợc<br /> ởi<br /> b<br /> c<br /> ối<br /> hồng lấn lên nh khi:<br /> hau<br /> .<br /> <br /> Hình 5. Va chạm giữa hai khối cầu<br /> h<br /> <br /> Hộ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). Hai<br /> ao<br /> hật<br /> ược<br /> n<br /> số<br /> các<br /> r<br /> khố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 2D<br /> k<br /> n<br /> k<br /> D):<br /> <br /> Hình 6. Va chạm giữa hai khối hộp AABB<br /> k<br /> B<br /> <br /> ao<br /> n<br /> ướng: được xá định bởi hai tham số: k/2 trung bình; k khoảng các lớn nhất<br /> ác<br /> 2<br /> k/2<br /> ch<br /> Hộp ba khối đa diện rời rạc có hư<br /> - 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 kh<br /> hư<br /> ong<br /> ng<br /> ó<br /> BB<br /> hông gian 3D có thể coi<br /> AABB 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ền không g<br /> A<br /> OP.<br /> hộp<br /> k<br /> gian 2D):<br /> <br /> Nguyễn Đức Hoàn Đỗ Năng Toà Nông Minh Ng<br /> N<br /> ng,<br /> àn,<br /> gọc<br /> <br /> ∃<br /> <br /> 415<br /> <br /> ∶<br /> <br /> ∨<br /> <br /> Hình 7. Biểu diễn kh OBB<br /> h<br /> hối<br /> <br /> Hộp ba khối chữ nh có hướng OBB: Giống như khối hộp lập phương AABB nhưng có khả năng xoay. Bài<br /> ao<br /> hật<br /> p<br /> g<br /> g<br /> toán xác định k<br /> không chồng l đối với kh hộp OBB đã được nghiên cứu khá chi tiết:<br /> lấn<br /> hối<br /> đ<br /> i<br /> •<br /> <br /> Tro miền khôn gian 2D: O<br /> ong<br /> ng<br /> OBB được biểu diễn bởi các tham số:<br /> u<br /> c<br /> <br /> o<br /> <br /> A1 A2, B1, B2: pháp tuyến v<br /> 1,<br /> vuông góc của hai đối tượng A và B;<br /> g<br /> <br /> o<br /> <br /> a1, a2, b1, b2: số đo các cạnh của hai hộp;<br /> ,<br /> ố<br /> <br /> o<br /> <br /> L: pháp tuyến ch hướng;<br /> hỉ<br /> <br /> o<br /> <br /> T: Khoảng cách giữa A và B;<br /> <br /> o<br /> <br /> pA = a1A1L + a<br /> A<br /> a2A2L;<br /> <br /> o<br /> <br /> pB = b1B1L + b<br /> B<br /> b2B2L;<br /> <br /> o<br /> <br /> A v B không ch<br /> và<br /> hồng lấn nhau khi:<br /> u<br /> ∃ : .<br /> <br /> Hình 8. Xác định va chạm gi hai khối OB<br /> đ<br /> iữa<br /> BB<br /> <br /> 416<br /> 4<br /> <br /> MỘT KỸ THU<br /> UẬT XÂY DỰNG HỆ BAO TỰ Đ<br /> G<br /> ĐỘNG CHO ĐỐI TƯỢNG 3D<br /> <br /> Để xét hai đối tượng lồi có chồng lấn lên nhau hay không, mộ trục tọa độ p<br /> h<br /> ột<br /> phân tách v sẽ được xác địn giữa hai<br /> ẽ<br /> nh<br /> đối tượng. Đối với các đối tư<br /> đ<br /> i<br /> ượng này một số các trục cầ xem xét nh sau:<br /> t<br /> ần<br /> hư<br /> o<br /> <br /> Trụ song song v mặt trung bình của A;<br /> ục<br /> với<br /> <br /> o<br /> <br /> Trụ song song v mặt trung bình của B;<br /> ục<br /> với<br /> <br /> o<br /> <br /> i<br /> Trụ song song v mặt cắt tại các góc của A và B.<br /> ục<br /> với<br /> <br /> Hình 9. Xác đị va chạm giữ hai khối đa d<br /> ịnh<br /> ữa<br /> diện<br /> <br /> • Tron miền khôn gian 3D: Để xác định chồng lấn các tr cần xem x gồm 15 trụ để xác định được trục<br /> ng<br /> ng<br /> rục<br /> xét<br /> ục<br /> h<br /> tọa đ phân tách.<br /> độ<br /> <br /> B. Hệ bao<br /> B<br /> Là một cấu trúc dữ li dạng cây đ<br /> iệu<br /> được xây dựng trên cơ sở ph tích các đ tượng được xem xét dựa trên cơ sở<br /> g<br /> hân<br /> đối<br /> c<br /> a<br /> các hộp bao hì học. Tại cá lá chứa các hình hình học cơ bản.<br /> c<br /> ình<br /> ác<br /> c<br /> <br /> Hình 10. Hệ bảo xây dựng bởi các hộp bao<br /> ệ<br /> o<br /> <br /> Đặc điể của Hệ bao<br /> ểm<br /> o:<br /> •<br /> <br /> Cá nút trong một nhánh phải gần nhau hơn so với các nú khác. Càng xuống thấp t các nút càn phải gần<br /> ác<br /> i<br /> n<br /> út<br /> g<br /> thì<br /> ng<br /> nha hơn.<br /> au<br /> <br /> •<br /> <br /> Mỗ nút trong BV cần có thể tích nhỏ nhấ<br /> ỗi<br /> VH<br /> ể<br /> ất.<br /> <br /> •<br /> <br /> Tổng của các kh bao cần ph tối giản.<br /> hối<br /> hải<br /> <br /> •<br /> <br /> Cá nút càng gần gốc thì càng quan trọng. Việc loại bỏ một nút gần gố sẽ ảnh hưở lớn hơn nh lần so<br /> ác<br /> n<br /> g<br /> m<br /> ốc<br /> ởng<br /> hiều<br /> với các nút ở xa.<br /> i<br /> .<br /> <br /> •<br /> <br /> Th tích trùng nh của các nú đồng cấp ph tối giản.<br /> hể<br /> hau<br /> út<br /> hải<br /> <br />