Luận văn Thạc sĩ: Nghiên cứu một số kỹ thuật tính toán va chạm trong thực tại ảo

Chia sẻ: Tomjerry001 | Ngày: | Loại File: PDF | Số trang:60

Thêm vào BST

Báo xấu

17
lượt xem 4
download

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

Mục tiêu nghiên cứu của đề tài là tìm hiểu về lý thuyết va chạm và bài toán phát hiện va chạm; Tìm hiểu một số kỹ thuật phát hiện va chạm trong thực tại ảo; Cài đặt thử nghiệm.

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ĩ: Nghiên cứu một số kỹ thuật tính toán va chạm trong thực tại ảo

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ ĐỖ THỊ CHI NGHIÊN CỨU MỘT SỐ KỸ THUẬT TÍNH TOÁN VA CHẠM TRONG THỰC TẠI ẢO LUẬN VĂN THẠC SĨ Hà Nội - 2014
2 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ ĐỖ THỊ CHI NGHIÊN CỨU MỘT SỐ KỸ THUẬT TÍNH TOÁN VA CHẠM TRONG THỰC TẠI ẢO Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60480104 LUẬN VĂN THẠC SĨ NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS ĐỖ NĂNG TOÀN Hà Nội - 2014
3 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của bản thân. Các đoạn trích dẫn và số liệu có nguồn gốc rõ ràng tuân thủ đúng nguyên tắc và nội dung trình bày trong luận văn thu thập được trong quá trình nghiên cứu là trung thực. Tôi xin chịu hoàn toàn trách nhiệm nội dung khoa học này. Hà Nội, Tháng 10 năm 2014 Học viên Đỗ Thị Chi
4 LỜI CẢM ƠN Luận văn được thực hiện dưới sự hướng dẫn của PGS. TS Đỗ Năng Toàn – Viện Công nghệ thông tin – Đại học Quốc gia Hà Nội. Em xin bày tỏ lòng biết ơn sâu sắc tới Thầy đã hướng dẫn và có ý kiến chỉ dẫn quý báu trong quá trình em làm luận văn. Em xin cám ơn các anh chị trong Phòng Thực tại ảo – Viện Công nghệ thông tin - Viện Hàn lâm khoa học Việt Nam đã nhiệt tình giúp đỡ em trong quá trình làm luận văn. Em xin chân thành cảm ơn các Thầy giáo trong Bộ môn Các hệ thống thông tin – Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội đã tạo điều kiện trong quá trình học tập và đã có những đóng góp ý nghĩa giúp em hoàn thành bản luận văn này. Hà Nội, Tháng 10 năm 2014 Học viên Đỗ Thị Chi
5 MỤC LỤC LỜI CAM ĐOAN.................................................................................................. 3 LỜI CẢM ƠN ....................................................................................................... 4 MỤC LỤC ............................................................................................................. 5 DANH MỤC HÌNH VẼ ........................................................................................ 7 LỜI MỞ ĐẦU ....................................................................................................... 9 Chương 1: Khái quát về động học và bài toán mô phỏng tính toán va chạm trong thực tại ảo ............................................................................................................ 12 1.1. Thực tại ảo .............................................................................................. 12 1.2. Một số phương pháp và công cụ phần mềm dựng mô hình 3D ............. 13 1.3. Khái quát về động học áp dụng vào thực tại ảo ..................................... 16 1.3.1. Lý thuyết về va chạm ....................................................................... 16 1.3.2. Những đặc trưng của động lực học .................................................. 17 1.3.3. Động lượng ....................................................................................... 18 1.4. Bài toán mô phỏng tính toán va chạm trong thực tại ảo......................... 19 1.5. Tổng quan một số phương pháp phát hiện va chạm............................... 19 1.5.1. Phương pháp sử dụng khối bao ........................................................ 20 1.5.2. Phương pháp phân vùng không gian ................................................ 22 1.6. Ứng dụng và tầm quan trọng của phát hiện va chạm ............................. 25 Chương 2: Một số kỹ thuật phát hiện va chạm ................................................... 27 2.1. Kỹ thuật phát hiện va chạm dựa vào hộp bao AABB ............................ 27 2.1.1. Định nghĩa hộp bao AABB ................................................................ 27 2.1.2. Xây dựng hộp bao AABB .................................................................. 27 2.1.3. Phát hiện va chạm giữa hai hộp bao AABB ...................................... 28 2.2. Kỹ thuật phát hiện va chạm dựa vào hộp bao OBB ............................... 29 2.2.1. Định nghĩa hộp bao OBB ................................................................. 29 2.2.2. Xây dựng hộp bao OBB ................................................................... 29 2.2.3. Phát hiện va chạm giữa hai hộp bao OBB ....................................... 30 2.3. Kỹ thuật phát hiện va chạm dựa vào khối bao cầu ................................. 33
6 2.3.1. Định nghĩa khối bao cầu................................................................... 33 2.3.2. Xây dựng khối bao cầu..................................................................... 34 2.3.3. Phát hiện va chạm giữa hai khối bao cầu ............................................ 38 2.4. Kỹ thuật phát hiện va chạm dựa vào hộp bao elip ................................. 40 2.4.1. Không gian vector và sự tịnh tiến của vật thể trong không gian ..... 40 2.4.2. Phát hiện va chạm ............................................................................ 42 2.5. Kỹ thuật phát hiện va chạm dựa vào hộp bao đa diện lồi (k-Dop) ........ 44 2.6. Phát hiện va chạm sử dụng BVH............................................................ 46 2.6.1. Mô hình BVH (Bounding Volume Hierarchy) ................................... 46 2.6.2. Các đặc điểm của BVH ....................................................................... 47 2.6.3. Chiến lược xây dựng cây phân cấp ..................................................... 49 2.6.4. Xây dựng BVH ................................................................................... 49 2.6.5. Phát hiện va chạm sử dụng BVH ........................................................ 50 2.6.6. Hàm đánh giá BVH ............................................................................. 50 Chương 3: Chương trình thực nghiệm ................................................................ 52 3.1. Mô tả bài toán ......................................................................................... 52 3.2. Lựa chọn công cụ mô phỏng .................................................................. 53 3.3. Một số kết quả ........................................................................................ 54 PHẦN KẾT LUẬN ............................................................................................. 58 TÀI LIỆU THAM KHẢO ................................................................................... 59
7 DANH MỤC HÌNH VẼ Hình 1.1: Mô phỏng tĩnh vật ............................................................................... 14 Hình 1.2: Mô phỏng đối tượng động................................................................... 15 Hình 1.3: Bounding Box, Bounding Sphere và những đặc tính của chúng ........ 21 Hình 1.4: Cá heo được bao bởi khối bao cầu, khối AABB, khối OBB và k-Dop 21 Hình 1.5: Một số cấu trúc phân vùng không gian dạng lưới và dạng cây ......... 22 Hình 1.6: Mô hình cấu trúc lưới ......................................................................... 23 Hình 1.7: Mô hình cấu trúc Octree ..................................................................... 23 Hình 1.8: Dùng BSP – tree để phân lớp trong và ngoài đa giác ........................ 24 Hình 1.9: Truy vấn điểm bên trong đa giác trên BSP - tree ............................... 25 Hình 1.10: Truy vấn điểm bên ngoài đa giác trên BSP - tree ............................ 25 Hình 2.1: Hộp bao AABB .................................................................................... 27 Hình 2.2: Xây dựng hộp bao AABB .................................................................... 27 Hình 2.3: Hợp nhất và kiểm tra va chạm giữa AABB và OBB ........................... 28 Hình 2.4: Phát hiện va chạm giữa 2 hộp bao AABB .......................................... 28 Hình 2.5: Hộp bao OBB ...................................................................................... 29 Hình 2.6: Hình chiếu các đối tượng lên các trục tọa độ .................................... 30 Hình 2.7: Kết quả chiếu 2 hình hộp lên trục cô lập ............................................ 31 Hình 2.8: Kiểm tra va chạm giữa 2 OBB ............................................................ 32 Hình 2.9: Bảng các giá trị của R, Ro,R1 để kiểm tra điều kiện 2 OBB không giao nhau: R>Ro+R1 ................................................................................................... 33 Hình 2.10: Khối bao cầu ................................... 34Error! Bookmark not defined. Hình 2.11: Hợp nhất và kiểm tra va chạm giữa 2 khối bao cầu......................... 34 Hình 2.12: Xây dựng khối bao cầu .................. Error! Bookmark not defined.35 Hình 2.13: Hai khối cầu xảy ra va chạm ............................................................ 38 Hình 2.14: Hộp bao dạng đa diện lồi ................................................................. 45 Hình 2.15: Minh họa một số hộp bao K-Dop ..................................................... 45 Hình 2.16: Độ phức tạp trong tính toán đối với các hộp bao............................. 46 Hình 2.17: Mô hình BVH với khối bao cầu ........................................................ 47 Hình 2.18: Các đặc điểm của cây phân cấp ....................................................... 47
8 Hình 2.19: Cây phân cấp 4 đối tượng sử dụng top –down, bottom –up và chèn 49 Hình 3.1: Mô hình ứng dụng game XNA............................................................. 53 Hình 3.3: Thực nghiệm với khối bao AABB ........................................................ 55
9 LỜI MỞ ĐẦU Ngày nay, sự phát triển của máy tính đã đem đến cho con người những cơ hội mới để nghiên cứu các vấn đề của thực tế. Bằng việc xây dựng lên môi trường thực tại ảo, con người có thể xây dựng thế giới thực vào máy tính, mô phỏng những sự kiện có thật hoặc giả định trong thực tế vào vi tính để tìm hiểu. Thực tại ảo (VR – Virtual Reality) [1] là một môi trường ba chiều được phát sinh, tổng hợp và điều khiển thông qua máy vi tính nhằm mục đích mô phỏng lại thế giới thực hoặc một thế giới theo tưởng tượng của con người. Nó cho phép người dùng thông qua các thiết bị ngoại vi tương tác với các sự vật, hiện tượng của thế giới ảo giống như tương tác với các sự vật, hiện tượng của thế giới thực. Các ứng dụng VR ngày càng trở nên hấp dẫn và phong phú hơn đặc biệt là trong lĩnh vực y học, kiến trúc, kỹ thuật, khoa học, giáo dục và giải trí. Trong môi trường ảo, hầu hết các ứng dụng đều ở chế độ tạo mẫu ảo. Các đối tượng được tạo ra trong thế giới nhân tạo ở dạng mô hình hình học. Về cơ bản, có ba đặc điểm quan trọng cần được xem xét khi phát triển các ứng dụng VR: - Thứ nhất: tất cả các mô hình đối tượng là tổng hợp của các đa giác phức hợp. - Thứ hai: các đối tượng được tạo ra không có bất kỳ thông tin topo nào. - Thứ ba: các đối tượng chuyển động không thể dự đoán hoặc dự đoán trước đó. Việc tạo ra các mô hình đối tượng có độ chân thực và sức hấp dẫn hoàn toàn phụ thuộc vào cách ta lựa chọn phương pháp để thể hiện chúng. Mỗi phương pháp có những ưu điểm và nhược điểm riêng, vì thế tuỳ vào mức độ quan trọng của đối tượng trong hệ mà ta có thể chọn phương pháp phù hợp để xây dựng. Do đó việc tìm hiểu xây dựng các đối tượng và các kỹ thuật phát hiện va chạm của các đối tượng trong Thực tại ảo là một công việc cần thiết. Vấn đề về va chạm thường là những vấn đề rất khó nghiên cứu trong thực tế, chẳng hạn như va chạm giữa các ô tô, xe máy hay lớn hơn nữa là tàu hỏa,
10 máy bay… Những vấn đề này đã được nghiên cứu thử nghiệm trong thực tế nhưng còn rất nhiều hạn chế vì nhiều lý do, còn rất nhiều trường hợp va chạm mà chúng ta cần nghiên cứu nhưng chưa thể thực hiện được. Một vấn đề khác đó chính là chi phí cung cấp cho việc thử nghiệm trên thực tế là quá lớn. Chính vì vậy giải pháp sử dụng máy tính để mô phỏng các vụ va chạm này là rất cần thiết. Đây là một vấn đề hết sức cần thiết cho cuộc sống của con người. Nội dung của luận văn đề cập đến vấn đề phát hiện va chạm và một số kỹ thuật được sử dụng để phát hiện va chạm trong thực tại ảo. Có nhiều phương pháp khác nhau để phát hiện va chạm giữa các đối tượng chuyển động trong thực tại ảo, một số cách tiếp cận tập trung vào tốc độ xử lý, một số khác thì xem độ chính xác là vấn đề chính. Tuy nhiên, hiệu suất của thuật toán liên quan đến độ phức tạp và độ khó khi thực hiện. Lin và đồng nghiệp [7] phân loại phương pháp dựa trên việc sử dụng loại mô hình hình học, trong khi Jimenez và đồng nghiệp [6] quan tâm đến quá trình va chạm. Bài viết tổng hợp một số nghiên cứu phát hiện va chạm trong những năm gần đây. Các phương pháp tiếp cận khác nhau đều có những ưu điểm và khuyết điểm riêng. Có hai cách tiếp cận phổ biến là: sử dụng khối bao và phân vùng không gian mà chúng ta sẽ tìm hiểu chi tiết ở phần sau. Mục tiêu nghiên cứu của đề tài là: - Tìm hiểu về lý thuyết va chạm và bài toán phát hiện va chạm. - Tìm hiểu một số kỹ thuật phát hiện va chạm trong thực tại ảo. - Cài đặt thử nghiệm. Từ nội dung đề ra và mục tiêu nghiên cứu của đề tài, nội dung luận văn gồm có 3 chương: Chương 1: Nghiên cứu tổng quan về lý thuyết va chạm và bài toán phát hiện va chạm; Các ứng dụng quan trọng trong việc phát hiện va chạm; Đưa ra cái nhìn tổng quan về một số kỹ thuật phát hiện va chạm phổ biến hiện nay. Chương 2: Nghiên cứu một số kỹ thuật phát hiện va chạm phổ biến dựa trên khối bao và kỹ thuật phân cấp khối bao dựa trên các khối bao cơ sở.
11 Chương 3: Chương trình cài đặt thực nghiệm với một số kỹ thuật trên, từ đó đánh giá và so sánh dựa trên các kết quả thu được từ chương trình.
12 Chƣơng 1: Khái quát về động học và bài toán mô phỏng tính toán va chạm trong thực tại ảo 1.1. Thực tại ảo Theo cách truyền thống, việc tương tác với máy tính được thực hiện thông qua các thiết bị như bàn phím, chuột hay Joystick/Trackball/Keyboard/Styplus để cung cấp thông tin đầu vào và sử dụng khối hiển thị trực quan (Video Display Unit-VDU) để nhận thông tin đầu ra từ hệ thống. Với sự ra đời của các hệ thống Thực tại ảo (Virtual Reality-VR), các phương thức giao tiếp mới được phát triển cho phép người sử dụng tương tác một cách tích cực với máy tính. Thực tại ảo là công nghệ sử dụng các kỹ thuật mô hình hoá không gian ba chiều với sự hỗ trợ của các thiết bị đa phương tiện hiện đại để xây dựng một thế giới mô phỏng bằng máy tính – môi trường ảo (Virtual Environment). Trong thế giới ảo này, người sử dụng không còn được xem như người quan sát bên ngoài, mà đã thực sự trở thành một phần của hệ thống. Một cách lý tưởng, người sử dụng có thể tự do chuyển động trong không gian ba chiều, tương tác với các vật thể ảo, quan sát và khảo cứu thế giới ảo ở những góc độ khác nhau về mặt không gian. Ngược lại, môi trường ảo lại có những phản ứng tương ứng với mỗi hành động của người sử dụng, tác động vào các giác quan như thị giác, thính giác, xúc giác của người sử dụng trong thời gian thực và tuân theo những quy tắc vật lý tự nhiên, làm anh ta có cảm giác như đang tồn tại trong một thế giới thực. Ngoài thuật ngữ Thực tại ảo (Virtual Reality) người ta cũng hay đề cập tới thuật ngữ Thế giới ảo (Virtual World). Thực chất đây là hai khái niệm tương đồng để chỉ một không gian ảo mà trong không gian này những người sử dụng có thể tương tác với các đối tượng của không gian ảo hoặc những người sử dụng có thể tương tác với nhau trong không gian đó. Những lĩnh vực đang được nghiên cứu ứng dụng thực tại ảo một cách mạnh mẽ hiện nay là: y học, giáo dục, tin học, thương mại, giao thông, hàng không, xây dựng, khoa học quân sự, quốc phòng, thiết kế nội thất và trang trí nhà cửa, giải trí, quân sự, điện ảnh…
13 1.2. Một số phƣơng pháp và công cụ phần mềm dựng mô hình 3D Mô phỏng (Simulation) là quá trình “bắt chước” hay mô tả các sự vật hiện tượng, cảnh vật có thực trong thiên nhiên hoặc trong trí tưởng tượng của con người. Hệ mô phỏng là một hệ thống thông tin đầy đủ về một môi trường nào đó mà con người có thể giao tiếp được. Thực tại ảo là một hệ mô phỏng có tương tác hai chiều và xử lý thời gian thực, đặc biệt với kỹ thuật Stereo 3D cho phép người quan sát được chìm đắm trong không gian ảo. Để xây dựng hệ thống Thực tại ảo thì việc xây dựng mô hình 3D là khâu quan trọng đầu tiên. Cho đến nay, nhìn chung có 2 xu hƣớng để thực hiện mô phỏng đối tƣợng 3D: - Cách thứ nhất: thể hiện các mô hình 3D nhờ các ngôn ngữ lập trình truyền thống như C, C++. . . Cách này không đòi hỏi sự chạy đua về công nghệ cũng như cấu hình mạnh của phần cứng, hơn nữa nó có thể thực hiện các mô phỏng phức tạp đòi hỏi sự chính xác cao. Tuy nhiên nó không được nhiều người sử dụng vì đó không phải là công việc đơn giản, nó đòi hỏi trình độ lập trình cao, các thuật toán phức tạp, mất nhiều thời gian và nhất là rất khó trong việc tạo ra những cảnh rộng lớn. Mặc dù ít được ưa thích nhưng đôi khi nó lại là lựa chọn duy nhất cho những ai muốn mô phỏng chính xác các hiện tượng thiên nhiên đúng với bản chất của nó. Tuy nhiên nó chỉ phù hợp với những mô phỏng có quy mô nhỏ, phù hợp với việc học tập. - Cách thứ hai: sử dụng các công cụ mô phỏng đã được xây dựng sẵn. Cách này không đòi hỏi trình độ lập trình cao, không tốn nhiều thời gian thực hiện, nó phù hợp với các mô phỏng có tính chất mô hình không yêu cầu độ chính xác cao. Một nhược điểm là nó yêu cầu cấu hình hệ thống mạnh để cài đặt và chạy chương trình, nhất là khi kết xuất (Rendering).Tuy nhiên, hiện nay cách này đang rất phổ biến, rất được ưa chuộng, nhất là trong các công việc làm Game 3D, Web3D, Phim 3D.v.v... Một số bộ công cụ mô phỏng thông dụng là: 3DsMax, Maya,
14 Autocad, Painter3D, VirtualML, Softimage, Renderman, Houdili, Lightware, Flash.v.v... Trạng thái đối tƣợng mô phỏng có 2 dạng chính: mô phỏng tĩnh và mô phỏng động: - Mô phỏng tĩnh: Là dạng mô phỏng chỉ thể hiện được mô hình tĩnh, trong kết quả mô phỏng không có sự chuyển động, không có sự biến đổi. Đây là dạng mô phỏng thường chỉ áp dụng cho các vật tĩnh. Đây là dạng mô phỏng đơn giản nhất. Hình 1.1: Mô phỏng tĩnh vật - Mô phỏng động: mô phỏng động được tách thành 2 loại, đó là mô phỏng động theo thời gian thực và mô phỏng động không theo thời gian thực: + Mô phỏng động theo thời gian thực: là dạng mô phỏng đối tượng có sự chuyển động hoặc có tính chất thay đổi theo thời gian, không gian và khi có tương tác thì hệ phải đáp ứng sự kiện đó trong một khoảng thời gian nhất định (quá thời gian đó thì kết quả không còn có ý nghĩa). Đây là dạng mô phỏng phức tạp nhất, khó khăn nhất nhưng đó lại là một đặc tính của Virtual Reality. + Mô phỏng động không theo thời gian thực: Đây là dạng mô phỏng không quan tâm tới thời gian đáp ứng của yêu cầu. Nó phù hợp cho xây dựng các hệ mô phỏng không có sự tương tác nhiều, không cần đáp ứng thời gian.
15 Hình 1.2: Mô phỏng đối tượng động Để thực hiện mô phỏng sự vật ta lại có 2 phƣơng pháp chính: Phƣơng pháp giả mô phỏng và phƣơng pháp mô phỏng thật. - Phương pháp giả mô phỏng là ta dùng các kỹ thuật xử lý ảnh để tạo ra những đối tượng và những hiệu ứng giả đánh lừa mắt nhìn của con người. Ví dụ, như biến đổi ảnh không gian 2D thành hình ảnh của vật như trong không gian 3D, hay các phương pháp Texture. - Phương pháp mô phỏng thật là dùng các kỹ thuật tạo đối tượng và hiệu ứng dựa trên cơ sở khoa học là các thuật toán biểu diễn tính chất vật lý của đối tượng và hàm biến đổi để thể hiện đối tượng một cách chính xác. Tóm lại, một hệ mô phỏng được thiết kế tốt, kết hợp với các thiết bị trình chiếu hiện đại và các thiết bị tương tác ngoại vi sẽ giúp con người tiếp cận được với thế giới ảo đó như đang ở trong thế giới thực. Việc tạo ra các mô hình đối tượng có độ chân thực và sức hấp dẫn hoàn toàn phụ thuộc vào cách ta lựa chọn phương pháp để thể hiện chúng. Mỗi phương pháp có những ưu điểm và nhược điểm riêng, vì thế tuỳ vào mức độ quan trọng của đối tượng trong hệ mà ta có thể chọn phương pháp phù hợp để xây dựng. Vấn đề hiện nay không phải là có thể biểu diễn được các sự vật hiện tượng trong thế giới thực trên máy tính được hay không, mà vấn đề là phải sớm tự xây dựng được một quy trình công nghệ sản xuất dựa trên điều kiện hiện tại của nước ta để cho ra đời các hệ Thực tại ảo một cách nhanh chóng, chính xác dựa trên những công cụ đã và đang được phát
16 triển. Và bước đầu tiên là phải hiểu biết một cách chắc chắn về phương pháp, do đó việc tìm hiểu xây dựng các đối tượng và các kỹ thuật phát hiện va chạm của các đối tượng trong Thực tại ảo là một công việc điển hình. 1.3. Khái quát về động học áp dụng vào thực tại ảo Để xây dựng được các đối tượng trong thế giới ảo thì vấn đề động học là một phần rất quan trọng trong việc xây dựng mô hình đối tượng, để làm cho các đối tượng trở lên sinh động hơn. Các đối tượng chuyển động không theo một hướng cụ thể mà nó chuyển động theo những lực tác động đến chúng, chẳng hạn như: ảnh hưởng của trọng lực, lực hấp dẫn, lực ma sát ... Do đó, hình dạng và chuyển động của đối tượng rất phong phú, đa dạng ... Điều này làm cho các đối tượng trong thực tại ảo trở lên giống thật hơn là nhờ giữa các đối tượng có tính tương tác với nhau. Chính vì vậy việc phát hiện va chạm giữa các đối tượng là hết sức quan trọng. Dựa trên lý thuyết về va chạm, báo cáo lựa chọn những yếu tố quan trọng tác động tới đối tượng để đưa vào trong quá trình mô phỏng đối tượng 1.3.1. Lý thuyết về va chạm 1.3.1.1. Định nghĩa Nói chung sự tương tác giữa các vật xung quanh ta vô cùng phức tạp. Nhưng để đơn giản hơn, trong vật lý người ta bỏ qua các tương tác nhỏ không đáng kể. Do đó, khi hai vật ở gần nhau, lực tương tác giữa chúng là khá lớn thì ta nói chúng có tương tác với nhau. Nếu chúng ở khá xa nhau lực tương tác giảm và nếu lực tương tác giữa các vật quá nhỏ thì ta coi như chúng không còn tương tác nữa. Nếu sự tương tác xảy ra giữa các vật trong một khoảng thời gian tương đối ngắn thì ta gọi đó là va chạm. Ví dụ: bắn bi, đá bóng, chơi bi – đa... Va chạm là một hiện tượng thường gặp trong đời sống và trong kỹ thuật. Việc áp dụng các định luật động lực học để giải bài toán va chạm thường gặp nhiều khó khăn do thời gian va chạm giữa các vật thường rất ngắn (chỉ vào khoảng đến giây) nên cường độ tác động của các lực lên vật thường rất lớn.
17 1.3.1.2. Các loại va chạm Va chạm cũng là một vấn đề khá phức tạp, nhưng trong vật lý người ta phân va chạm ra làm hai loại chính là va chạm đàn hồi và va chạm mềm. Va chạm đàn hồi: là va chạm sau khi tương tác với nhau chúng tách rời nhau (Là va chạm giữa các vật mà sau khi va chạm cơ năng của hệ được bảo toàn. Trong thực tế không có va chạm nào được xem là tuyệt đối đàn hồi. Nhưng với những va chạm mà sau khi kết thúc cơ năng của hệ thay đổi rất ít thì ta có thể xem đó là va chạm đàn hồi). Ví dụ va chạm giữa các trái bi trên bàn bi –da... - Trường hợp đặc biệt: va chạm đàn hồi xuyên tâm là va chạm mà trước và sau va chạm hai vật đều chuyển động trên cùng một đường thẳng. - Phạm vi áp dụng: áp dụng hai định luật bảo toàn là bảo toàn động lượng hoặc bảo toàn cơ năng. Va chạm mềm: là loại va chạm mà sau khi va chạm hai vật dính vào nhau và chuyển động với cùng một vận tốc (Là va chạm xảy ra giữa các vật mà sau khi va chạm cơ năng của hệ các vật đó không được bảo toàn. Một phần cơ năng của hệ được chuyển sang một số dạng năng lượng khác như nhiệt năng, sinh công ...). Ví dụ dùng búa rèn dao thì động năng của búa gần như chuyển hết thành nhiệt năng làm nóng dao và sinh công gây ra sự biến dạng của dao. - Phạm vi áp dụng: áp dụng định luật bảo toàn động lượng. 1.3.2. Những đặc trƣng của động lực học Khác với động học, động lực học nghiên cứu chuyển động có xét đến nguyên nhân đã gây ra chuyển động đó (lực). Ngoài ra động lực học còn thiết lập các mối liên hệ giữa các đặc trưng động học và động lực học, tạo nên một sự hoàn chỉnh về nghiên cứu chuyển động nói chung. 1.3.2.1. Lực Để mang một vật từ vị trí này sang vị trí khác ta cần phải đặt vào nó lực và chính lực này đã làm thay đổi trạng thái của vật (nó thu được một gia tốc). Tuy nhiên cũng có khi tương tác của hai vật không gây ra chuyển động mà chỉ tạo ra
18 sự thay đổi hình dạng chẳng hạn khi ta nén một lò xo, hay một miếng cao su, một cục đất sét, v.v... Độ dài (có đơn vị đo bằng mét) đặc trưng cho kích thước của vật theo một phương nào đó; một vật cân nặng hay nhẹ ta dùng khái niệm khối lượng để đặc trưng và có đơn vị là kg.v.v. Hoàn toàn tương tự như vậy để đặc trưng cho sự tương tác và để đo tương tác người ta dùng khái niệm lực và có đơn vị đo là N (Newton). “Lực là đại lượng đặc trưng cho sự tương tác giữa các vật mà kết quả truyền cho chúng một gia tốc hay làm cho chúng biến dạng”. Để xác định một lực thì cần biết lực đó tác dụng theo phương chiều nào và có độ lớn bằng bao nhiêu, điểm đặt của nó ở đâu. Do vậy, lực là một đại lượng vector, thường ký hiệu bằng chữ F. Người ta lấy đơn vị lực là Newton (N) để kỷ niệm nhà bác học Newton đã có công lớn trong việc xây dựng khái niệm lực và tìm ra các định luật động lực học tổng quát nhất. 1.3.2.2. Khối lƣợng Khối lượng của một vật (hay một hệ vật) là đại lượng đặc trưng cho lượng vật chất chứa trong vật (hay một hệ vật). Khối lượng thường được ký hiệu bằng chữ m và đơn vị trong hệ SI là kg. 1.3.2.3. Động lực học Động lực học là một phần của cơ học nghiên cứu chuyển động có xét đến nguyên nhân đã gây ra chuyển động đó. 1.3.3. Động lƣợng Dễ dàng thấy rằng để đặc trưng cho sự truyền chuyển động (truyền lực) từ vật này sang vật khác, thì phải dùng cả hai đại lượng là vận tốc và khối lượng vì thiếu một trong hai đại lượng này thì hoặc là không hoặc sự truyền tương tác rất yếu. Đương nhiên khối lượng càng lớn và vận tốc càng lớn thì sự truyền tương tác càng mạnh (một thí dụ rất dễ thấy là đoàn tàu lửa có khả năng truyền tương tác rất lớn vì khối lượng và vận tốc của nó đều lớn, một cục bông có khả năng truyền chuyển động yếu vì khối lượng của nó rất bé nhưng chiếc tàu lửa đứng yên lại không có khả năng truyền chuyển động cho vật nào cả).
19 Từ lập luận trên ta có thể tìm biểu thức động lượng từ định luật 2 Newton: Đặt = thì là động lượng của chất điểm theo logic mà ta đã nói ở trên, ngoài ra càng lớn thì cũng càng lớn, sự truyền chuyển động càng lớn và như vậy động lượng có đơn vị là kgm/ Tóm lại động lượng: = Động lượng là đại lượng đặc trưng cho sự truyền chuyển động từ vật này lên vật khác, có trị số bằng tích số giữa khối lượng của chất điểm và vận tốc của nó. 1.4. Bài toán mô phỏng tính toán va chạm trong thực tại ảo Trong thế giới thực tồn tại rất nhiều các đối tượng, mỗi đối tượng có hình thái và tính chất vật lý khác nhau. Để mô phỏng chính xác các tương tác vật lý, các nhà nghiên cứu quan tâm tới hai vấn đề lớn: một là việc xác định chính xác va chạm giữa các đối tượng [2]-[5]-[6]-[7]; hai là quá trình xử lý tương tác động học khi các đối tượng đó va chạm với nhau [5]. Trong nội dung báo cáo tập trung nghiên cứu, giải quyết các vấn đề liên quan tới phát hiện va chạm và ứng dụng các nghiên cứu đó trong việc mô phỏng động học. Bài toán phát hiện va chạm [6]: Cho một không gian U với một tập các đối tượng O, giải thuật phát hiện va chạm sẽ cho biết sự va chạm giữa các cặp đối tượng từng đôi một Cp O x O x R3 với mọi đối tượng o1, o2 và cho biết các điểm va chạm giữa chúng p1,2 R3. Phát hiện va chạm là một trong những vấn đề trọng tâm của mỗi hệ thống thực tại ảo, các đối tượng trong hệ thống thực tại ảo có những chuyển động của riêng nó. Trong khi chuyển động, đối tượng có thể va chạm với đối tượng khác hoặc có thể va chạm với môi trường, chướng ngại vật, ... Do vậy, mỗi hệ thống thực tại ảo đều phải có khả năng phát hiện khi nào thì có va chạm xảy ra và có những đối tượng nào tham gia va chạm để có những xử lý hậu va chạm thích hợp. 1.5. Tổng quan một số phƣơng pháp phát hiện va chạm
20 Có nhiều phương pháp khác nhau để phát hiện va chạm giữa các đối tượng chuyển động trong thực tại ảo, một số cách tiếp cận tập trung vào tốc độ xử lý, một số khác thì xem độ chính xác là vấn đề chính. Bài viết tổng hợp một số nghiên cứu phát hiện va chạm trong những năm gần đây. Các phương pháp tiếp cận khác nhau đều có những ưu điểm và khuyết điểm được so sánh một cách chi tiết. Có hai cách tiếp cận phổ biến [6]: - Sử dụng khối bao: khối bao hộp, khối bao cầu, khối bao elip, khối bao k – Dop, cây phân cấp khối cầu, ... - Phân vùng không gian: dạng lưới, dạng cây. 1.5.1. Phƣơng pháp sử dụng khối bao Phát hiện va chạm [6][7] là việc giải quyết bài toán có hay không sự va chạm giữa các đối tượng trong môi trường thực tại ảo. Để phát hiện va chạm giữa hai đối tượng một cách chính xác ta kiểm tra từng mặt của đối tượng này có cắt một mặt nào đó của đối tượng kia hay không. Cách làm này có ưu điểm là cho ta chính xác điểm va chạm, tuy nhiên, mỗi đối tượng 3D được tạo thành từ rất nhiều mặt [8] (thông thường là các tam giác) nên chi phí để kiểm tra giao nhau của từng cặp mặt rất tốn kém về mặt thời gian. Mặt khác, các hệ thống thực tại ảo lại đòi hỏi xử lý trong thời gian thực [1]. Vì vậy, để giải quyết vấn đề này hầu hết các hệ thống đều sử dụng phương pháp gần đúng để phát hiện va chạm [6]. Điển hình là sử dụng khối hình học bao quanh đối tượng [3]. Với mỗi đối tượng, ta tìm một khối bao thích hợp quanh nó, việc phát hiện va chạm bây giờ được đưa về bài toán phát hiện giao nhau giữa các khối bao. Một số khối bao điển hình với chi phí tính toán thấp có thể nhắc tới như: khối bao hộp, khối bao cầu,... mà chúng ta sẽ tìm hiểu chi tiết hơn ở chương 2. Trước khi nghiên cứu chi tiết từng kỹ thuật chúng ta sẽ tìm hiểu khái niệm khối bao. Ta thấy rằng, các đối tượng trong thực tế thường có hình dạng rất phức tạp, nếu ta sử dụng trực tiếp đối tượng đó thì rất khó có thể áp dụng vào thuật toán. Chính vì vậy, cần mô phỏng đối tượng đó bằng một đối tượng khác đơn giản hơn, từ đó sinh ra khái niệm khối bao (Bounding volume).