Luận văn Nghiên cứu phát hiện va chạm và ứng dụng

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ể mô phỏng thế giới thực vào máy vi 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 - ở đây chúng tôi chỉ nói đến một trường hợp đó là chính là mô phỏng các va chạm trong thực tế, để từ đó tìm ra giải pháp thích hợp mà không cần phải kiểm nghiệm bằng thực 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, máy bay v.v 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. Vấn đề phát hiện va chạm còn được ứng dụng rất nhiều trong các lĩnh vực khác như: y học, các bộ mô phỏng vật lý hay trong một lĩnh vực có nhu cầu rất lớn đó là giải trí v.v. Phát hiện va chạm được ứng dụng rất nhiều trong các môi trường thực tại ảo.

doc68 trang | Chia sẻ: tuandn | Ngày: 21/05/2013 | Lượt xem: 1919 | Lượt tải: 2download
Bạn đang xem nội dung tài liệu Luận văn Nghiên cứu phát hiện va chạm và ứng dụng, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
MỤC LỤC 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ể mô phỏng thế giới thực vào máy vi 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 - ở đây chúng tôi chỉ nói đến một trường hợp đó là chính là mô phỏng các va chạm trong thực tế, để từ đó tìm ra giải pháp thích hợp mà không cần phải kiểm nghiệm bằng thực 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, máy bay v.v…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. Vấn đề phát hiện va chạm còn được ứng dụng rất nhiều trong các lĩnh vực khác như: y học, các bộ mô phỏng vật lý hay trong một lĩnh vực có nhu cầu rất lớn đó là giải trí v.v.. Phát hiện va chạm được ứng dụng rất nhiều trong các môi trường thực tại ảo. Khoá luận này nhằm mục đích nghiên cứu, tìm hiểu va chạm chung giữa các đối tượng trong thực tế được mô phỏng vào máy tính, hướng giải quyết sau va chạm (hậu va chạm). Khoá luận gồm có 3 chương: Chương 1: Giới thiệu chung về môi trường thực tại ảo và các khái niệm liên quan khi nghiên cứu phát hiện va chạm Chương 2: Giới thiệu một số phương pháp phát hiện va chạm phổ biến. Chương 3: Xây dựng ứng dụng va chạm ôtô. Trong quá trình thực hiện khoá luận tốt nghiệp này, tôi đã nhận được nhiều sự giúp đỡ của các thầy cô giáo, bạn bè đồng nghiệp và gia đình. Tôi xin cảm ơn sự giúp đỡ nhiệt tình của thầy Đỗ Năng Toàn, là người trực tiếp hướng dẫn đề tài tốt nghiệp của tôi, anh Phạm Thế Anh cùng các anh chị trong Viện Công nghệ thông tin đã giúp tôi hoàn thành khoá luận này, tôi cũng xin chân thành cảm ơn các bạn bè đồng nghiệp, người thân trong gia đình đã tạo điều kiện, động viên tôi trong quá trình làm đồ án. Vì điều kiện thời gian không có nhiều, kinh nghiệm còn hạn chế nên không tránh khỏi thiếu sót. Tôi mong nhận được ý kiến đóng góp của các thầy cô giáo và các đồng nghiệp. Chương 1: TỔNG QUAN VỀ VA CHẠM Phát hiện va chạm (Collision detection) là tiến trình giải quyết vấn đề có hay không sự va chạm giữa các đối tượng trong môi trường mà các đối tượng đó tồn tại. Sự va chạm này có thể giữa các đối tượng cùng loại hoặc giữa các đối tượng khác nhau, va chạm với các đối tượng tĩnh (ví dụ như : nền nhà, tường nhà, mặt đường v.v...) hoặc va chạm với các đối tượng động (ví dụ như : ôtô, máy bay v.v...). Định nghĩa [collision detection] : 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 chỉ là một trường hợp đặc biệt trong môi trường giả lập vật lý (được thể hiện vào máy tính). Thực chất ở đây chúng ta chỉ tìm hiểu sự va chạm giữa các đối tượng hình học thể hiện các đối tượng (sau này ta gọi đó là các hình bao). Do các đối tượng trong đời sống có hình dạng khá phức tạp nên ta sẽ đưa chúng về những vật thể có hình dạng tương đương và đơn giản hơn (mô phỏng vào máy tính), thuật toán phát hiện va chạm chủ yếu thao tác trên các đối tượng này và chúng ta sẽ sử dụng môi trường vật lý giả lập nếu cần thiết – Môi trường thực tại ảo. 1.1. Môi trường thực tại ảo (Virtual Reality) Có nhiều khái niệm khác nhau vể thực tại ảo xong một cách chung nhất chúng ta có thể định nghĩa thực tại ảo như sau: Thực tại ảo 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 trong 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 và bộ chuyển đổi tương tác với những sự vật, hành động của thế giới ảo mà như tương tác với các sự kiện, hành động của thế giới thực. Ví dụ người dùng có thể dich chuyển một vật trong thế giới ảo, hoặc có thể cảm nhận được một vật khi chạm vào nó vv… Trong đó thiết bị ngoại vi sẽ làm nhiệm vụ chuyển những hoạt động của người sử dụng vào bộ chuyển đổi từ bộ chuyển đổi sau đó bộ chuyển đổi sẽ chuyển những tín hiệu này thành các tương tác vào môi trường ảo, đồng thời môi trường cũng chuyển những tác dụng của nó đến bộ chuyển đổi và bộ chuyển đổi chuyển đến các thiết bị ngoại vi, sau đó các thiết bị ngoại vi sẽ tác động đến người sử dụng. Vì vậy người sử dụng sẽ có khả năng tương tác với môi trưởng ảo như là tương tác trên chính môi trường 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 có điều thuật ngữ hướng tới môi trường, 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 này, thậm chí những người sử dụng này có thể tương tác với nhau trong không gian đó. Nói chung, các hệ thống thực tại ảo phải xử lý mội khối lượng lớn thông tin (đa phần là các thông tin của các đối tượng 3D do đó tốn bộ nhớ và đòi hỏi thời gian xử lý là thời gian thực), vì thế nó đòi hỏi một lượng tài nguyên bộ nhớ RAM lớn và bộ xử lý cùng các thiết bị vào ra có tốc độ cao. Vì vậy mặc dù bắt đầu nghiên cứu từ khá lâu, xong trong một số năm gần đây thực tại ảo mới có được sự phát triền và mở rộng ứng dụng đáng kể. Thực tại ảo có rất nhiều ứng dụng trong thực tế như : khoa học quân sự, quốc phòng, Giáo dục và đào tạo, y học, thiết kế, khoa học cơ bản, thương mại du lịch, giải trí v.v… 1.2. Tầm quan trọng của việc tìm hiểu phát hiện va chạm trong môi trường thực tại ảo Như đã nói ở trên, môi trường thực tại ảo nhằm mô phỏng thế giới thực hoặc thế giới theo sự tưởng tượng của con người vào máy vi tính. Trong thế giới thực tồn tại rất nhiều các đối tượng, các đối tượng này có các hành vi của chúng. Chính vì vậy để môi trường thực tại ảo mô phỏng được thực tế thì các đối tượng trong môi trường này cũng phải có các hành vi như trong thế giới thực. Chính vì vậy ta cần nghiên cứu các phương pháp để mô phỏng các hành vi này, mô phỏng sự tương tác giữa các đối tượng trong môi trường thực tại ảo hay nói khác đi chính là nghiên cứu việc phát hiện va chạm giữa các đối tượng trong môi trường… 1.3. Một số khái niệm cơ bản Dưới đây là một số khái niệm thường dùng : 1.3.1. Khối bao (Bounding volumes) Như đã nói ở trên, 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 ta 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). Khối bao (BV) đơn giản chỉ là một khối hình học bao vừa đối tượng cần thao tác. Khối bao càng bao vừa khít đối tượng thì thuật toán sẽ càng chính xác. Các khối bao nên là các khối hình học đơn giản. BV được sử dụng hầu như trong tất cả các cơ chế phát hiện va chạm hiện nay. Phần lớn các thuật toán phát hiện va chạm đều sử dụng đến chúng bởi vì nó có xu hướng làm giảm độ phức tạp của thuật toán. Có rất nhiều loại BV khác nhau, mỗi loại có những điểm mạnh và điểm yếu riêng. Có thể phân BV thành 2 loại đó là Bounding Box (BB - hộp bao) và Bounding Sphere (BS - cầu bao). BB thường có 2 loại đó là loại hướng theo trục toạ độ và loại hướng bất kỳ (Axis – Oriented), loại này được xác định bởi vị trí 2 đỉnh của hộp, còn BS được xác định bởi tâm và bán kính. Hình 1.3.1: Bounding Box, Bounding Sphere và những đặc tính của chúng Có thể liệt kê các loại BV như sau : Khối bao cầu – Bounding Sphere Hộp bao theo trục – AABB (Axis Aligned Bounding Box) Hộp bao định hướng – OBB (Oriented Bounding Box) Hộp bao dạng đa diện lồi – k-Dop Ta sẽ lần lượt định nghĩa các khối bao này. a. Khối bao hình cầu (Bounding spheres) - khối bao cầu. Bounding spheres là các khối bao có dạng hình cầu bao lấy đối tượng. Được xác định bởi 4 giá trị : toạ độ tâm C(xc, yc, zc) và bán kính r. Khối bao dạng này rất dễ tạo ra và rất đơn giản trong các thao tác kiểm tra va chạm. Nói là dễ dàng kiểm tra va chạm là bởi vì khi đối tượng quay hay chuyển động thì hình dạng, hướng của hình cầu đều không bị thay đổi, hình cầu không bị tác động khi vật thể tự quay. Hình cầu không phụ thuộc vào trục. Hình 1.3.1a1: Bounding Sphere Ta cũng có thể thay thế các hình bao cầu bởi các khối ellipsoid. Hình bao cầu chỉ là trường hợp riêng của hình bao ellipsoid. Tuy nhiên, hình bao cầu lại có rất nhiều nhược điểm. Nó thường biểu diễn không chính xác hình dạng các vật thể nếu như các vật thể này không có dạng khối cầu, đặc biệt khi hình dạng của vật thể có dạng dẹt, hoặc dài thì càng không chính xác. Chính vì vậy thuật toán sẽ không được tối ưu. Khối bao này tạo ra nhiều không gian trống giữa vật thể và khối cầu. Rất khó hợp nhất 2 hay nhiều BS loại này bởi vì sẽ tạo ra sai số rất lớn. Hình 1.3.1b2: Hợp nhất và kiểm tra va chạm giữa 2 Bounding Sphere b. Axis – Oriented Bounding Box Trong không gian 3 chiều, một axis – oriented bounding box được xác định bởi 6 giá trị của các đỉnh có toạ độ lớn nhất (xmax, ymax, zmax) và nhỏ nhất (xmin, ymin, zmin). Loại BV này rất dễ tạo ra , dễ hợp nhất lại với nhau và thuận tiện cho việc phát hiện va chạm. Lợi thế lớn nhất của loại BV này là xử lý nhanh, tuy nhiên không chính xác cho lắm. Hình 1.3.1b: Hợp nhất và kiểm tra va chạm giữa 2 Axis-Oriented Bounding Box Hộp bao theo trục toạ độ - AABB (Axis Aligned Bounding Box) AABB là hộp bao có dạng hình hộp chữ nhật có các cạnh (trục)song song với các trục toạ độ tương ứng và bao lấy vật thể. Hộp bao này rất đơn giản, dễ tạo ra và thao tác trong kiểm tra va chạm cũng rất dễ dàng. Tuy nhiên hộp bao loại này cũng tạo ra nhiều khoảng trống giữa vật thể và hộp bao. Khi vật thể không nằm song song với các trục toạ độ và có dạng dài thì khoảng trống này càng lớn. Hình 1.3.1b1: AABB Hộp bao có hướng – OBB (Oriented Bounding Box) OBB là hộp bao AABB nhưng trục có hướng bất kỳ. OBB có ưu điểm hơn AABB đó là giảm không gian trống giữa vật thể và hộp bao. Tuy nhiên việc tạo ra và thao tác trên hộp bao loại này phức tạp hơn loại AABB nhiều. Tuy nhiên người ta vẫn dùng loại hộp bao này nhiều hơn vì nó không đến độ quá phức tạp. Loại hộp bao này bao khá vừa các dạng vật thể. Tuy nhiên với các vật thể có nhiều các đỉnh cao như hình bên thì rõ ràng chưa phải tối ưu. Hình 1.3.1b2: OBB c. Các dạng hộp bao khác Có rất nhiều dạng BV phức tạp khác được dùng trong một vài trường hợp đặc biệt. Để tạo ra chúng đòi hỏi rất nhiều các thông số. Tuy nhiên càng phức tạp thì càng làm giảm được khoảng không gian trống giữa đối tượng và hộp bao. Sự lựa chọn phụ thuộc rất nhiều vào hình dạng của vật thể, chẳng hạn như nếu vật thể có dạng khối dài thì giải pháp có thể chọn là khối bao cầu (bounding sphere) hoặc khối bao trụ (bounding cylinder). Hình 1.3.1c: Hộp bao dạng đa diện lồi Hộp bao dạng da đa diện lồi (k-Dop) Với hộp bao dạng này ta hạn chế được rất nhiều khoảng không gian trống giữa vật thể và hộp bao. Tuy nhiên việc tao ra hộp bao dạng này đôi khi quá phức tạp (phức tạp nhất) và việc thao tác trên chúng mất quá nhiều công đoạn. Nó chỉ được sử dụng đối với các chương trình cần độ chính xác cao. Đối với các chương trình nhỏ yêu cầu tốc độ thì không nên chọn hộp bao dạng này. Thông thường, người ta thường giới hạn số mặt hay số cạnh của đa diện tới một giá trị nào đó (chẳng hạn k = 5,6,7 ...) tuỳ thuộc vào từng ứng dụng cụ thể. Theo trên ta thấy rằng để giảm khoảng không gian trống thì hộp bao tạo ra và sử dụng càng trở nên phức tạp (xem biểu đồ). Hình 1.3.1c1: Độ phức tạp trong tính toán đối với các hộp bao Tiếp theo ta sẽ tìm cách xây dựng các hộp bao trên (tạm gọi chung là hộp bao) để có thể dùng được trong các thuật toán sẽ được sử dụng: 1.3.2. Xây dựng các khối bao cơ sở a. Xây dựng hộp bao AABB: Xây dựng hộp bao loại này khá đơn giản, hộp bao này được tạo bởi 2 điểm có toạ độ nhỏ nhất và lớn nhất của vật thể như hình vẽ 1.3.2a: Hình 1.3.2a: Hộp bao AABB b. Xây dựng hộp bao có hướng OBB Việc xây dựng hộp bao OBB có vẻ phức tạp hơn nhiều so với xây dựng hộp bao AABB. Trước hết ta tìm đa diện lồi bao vật thể (bằng cách mở rộng các mặt phẳng trên vật thể). tiếp theo ta phân chia các mặt của đa diện thành các tam giác. Giả sử sau bước này ta được n tam giác với các định lần lượt là : pk , qk , rk Diện tích của mỗi tam giác là ak , vậy ta có tổng diện tích là : Gọi trọng tâm của tam giác thứ i là mi = (pi + qi + ri)/3 Trọng tâm của đa diện lồi mH được cho bởi công thức sau; Sử dụng công thức trên ta được một ma trận C để từ đó xác định được vector định hướng cho 8 cạnh của OBB là: c. Xây dựng khối bao hình cầu – khối cầu bao (BS: Bounding Sphere) Cách tạo đơn giản : Ta dễ dàng tạo được hộp bao AABB như hình bên Lấy tâm của hộp bao AABB làm tâm của hinh cầu. Chọn đường kính của hình cầu bằng độ dài đường chéo của hộp bao AABB Với cách tạo đơn giản này cho ta một khối bao hình cầu không được tối ưu cho lắm. Tuy nhiên cách này tương đối đơn giản, dễ dàng thực hiện. Ta hãy xem một phương pháp cải tiến của phương pháp nêu trên: Lấy tâm của khối cầu là tâm của hộp bao AABB Duyệt tất cả các đỉnh của đối tượng Tìm đỉnh mà khoảng cách từ tâm khối cầu đến đó là lớn nhất và lấy khoảng cách đó làm bán kính của hình cầu Với phương pháp này thì hạn chế được khoảng không gian trống hơn phương pháp trên, tuy nhiên cần phải thực hiện nhiều phép toán so sánh và tìm kiếm. Qua 2 phương pháp xây dựng nhanh BS ở trên ta thấy rằng giải pháp trên là không phải tối ưu. Rõ ràng cả 2 phương pháp đều tạo ra những khoảng không gian trống quá lớn. Chúng ta cần tìm ra giải pháp hạn chế được khoảng không gian trống càng nhiều càng tốt. Giải pháp tối ưu nhất được trình bày như sau: Giả sử S là một tập các đỉnh của một đối tượng (hay đơn giản S là tập các điểm). Với tất cả các đỉnh V thuộc tập S ta thực hiện các bước sau: Bước 1 : Tìm tất cả các đỉnh Vmax là đỉnh có toạ độ lớn nhất theo các trục toạ độ (x,y,z) Bước 2 : Tìm tất cả các đinh Vmin là đỉnh có toạ độ nhỏ nhất theo các trục toạ độ (x,y,z) Bước 3 : Chọn ra cặp đỉnh Vmin, Vmax sao cho khoảng cách giữa chúng theo các trục toạ độ là lớn nhất. Bước 4 : Chọn tâm C của khối cầu là trung điểm của vector Vmax - Vmin Bước 5 : Chọn bán kính của khối cầu bằng một nửa độ dài vector Vmax - Vmin Bước 6 : Duyệt tất cả các đỉnh còn lại, gọi d là khoảng cách từ đỉnh đang xét tới tâm của khối cầu. Nếu một đỉnh nào đó nằm ngoài khối cầu thì ta di chuyển tâm C của khối cầu một khoảng (d+r)/2 và chọn bán kính mới của khối cầu là (d+r)/2 Khi đã duyệt tất cả các đỉnh thì chắc chắn rằng khối cầu đã bao tất cả các đỉnh (hay các điểm). Chương 2 : CÁC PHƯƠNG PHÁP PHÁT HIỆN VA CHẠM Chúng ta cần giải quyết 3 câu hỏi chính trong việc phát hiện va chạm đó là: có hay không , khi nào và ở đâu : Đối với 2 đối tượng bất kỳ có xảy ra hay không sự va chạm giữa chúng (bằng việc kiểm tra sự va chạm giữa các đối tượng hình học đơn giản) ? Nếu xảy ra va chạm thì chúng sẽ va chạm vào thời điểm nào ? Sự va chạm xảy ra tại vị trí nào trên bề mặt đối tượng ? Việc giải quyết va chạm giữa các đối tượng thường rất khó. Chính vì vậy, giải thuật phát hiện va chạm thường được phân thành các bước nhỏ hơn, mỗi giai đoạn chúng ta lại kiểm tra điều kiện thích hợp, chỉ xử lý bước tiếp theo khi bước trước nó đã thành công. Với một hệ thống gồm N đối tượng thì chúng ta cần phải duyệt qua (N2-N)/2 bước kiểm tra - O(N2). Với N nhỏ thì công việc này là khá dễ dàng, nhưng với N lớn thì chi phí để thực hiện nó sẽ là rất cao. Vấn đề tiếp theo cũng rất quan trọng đó là vấn để giải quyết sau va chạm hay phản ứng lại va chạm (Collision response). Để giải quyết vấn đề này chúng ta thường sử dụng các khái niệm về động học như momen hay lực tác dụng, tức là chúng ta cần tính toán đến các đại lượng vật lý (như: khối lượng, vận tốc ...). Ở đây, để vấn đề trở nên đơn giản hơn thì đôi khi ta chỉ giải quyết các va chạm mang tính chất đàn hồi (2 vật không “dính” vào nhau sau va chạm). 2.1. Phương pháp dùng bao cầu - Bounding Sphere Trong phần này ta sẽ lần lượt xét một số thuật toán phát hiện va chạm, đồng thời giải quyết thêm vấn đề sau va chạm. Ta sẽ sử dụng các khối bao thay cho các đối tượng cần thể hiện.Từ những thuật toán riêng cho từng đối tượng ta sẽ đi đến một thuật toán chung cho tất cả các đối tượng. 2.1.1. Phát hiện va chạm Phát hiện có va chạm Khối cầu - Mặt phẳng Khối cầu - Khối trụ Khối cầu - Khối cầu Sử dụng các định luật vật lý để phản hồi sau va chạm Lực tác dụng trở lại đối tượng khi va chạm Sử dụng trọng lực trong việc di chuyển đối tượng a. Tìm giao điểm giữa một tia với mặt phẳng Để phát hiện va chạm chúng ta sử dụng một thuật toán đơn giản tạm gọi là lần theo tia (ray tracing). Trước hết ta sẽ định nghĩa thế nào là một tia. Một tia được xác định bởi một điểm hay còn gọi là gốc và một vector xác định hướng mà tia đó sẽ đi theo. Nói tóm lại, một tia có thể được biếu diễn bởi một điểm gốc và vector định hướng. Phương trình của một tia có dạng: PointOnRay = RayStart + t * Raydirection (1) Trong đó: t là số thực , t PointOnRay : một điểm thuộc tia Raystart : điểm gốc của tia Raydirection : hướng của tia Theo phương trình (1) ở trên thì khi t = 0 thì PointOnRay chính là điểm gốc. Với các giá trị khác của t thì PointOnRay chạy khắp tia. PointOnRay, Raystart, Raydirection là các đại lượng Vector trong không gian R3 nhận các giá trị (x,y,z). Tiếp theo chúng ta sẽ sử dụng tia để biểu diễn và tính toán sự va chạm của khối cầu với mặt phẳng và các khối cầu. Phương trình mặt phẳng biểu diễn thông qua Vector có dạng : Xn dot X = d (2) Trong đó: Xn, X là các vector và d nhận giá trị thực Xn là pháp tưyến của mặt phẳng X là một điểm thuộc mặt phẳng đang xét d – là khoảng cách từ gốc của hệ toạ độ Oxyz tới mặt phẳng Theo phương trình (2), để biểu diễn một mặt phẳng trong không gian 3D hay R3 ta chỉ cần một điểm nằm trên mặt phẳng đó và một Vector pháp tuyến tại điểm đó (Vector pháp tuyến là Vector vuông góc với mặt phẳng). Để có thể xác định được vector pháp tuyến của mặt phẳng ta chỉ cần xác định được 2 vector không song song trong mặt phẳng đó. Tích có hướng của 2 Vector này sẽ tạo thành vector pháp tuyến. Ví dụ : Giả sử ta có điểm O(0,0,0) và một vector pháp tuyến (0,1,0) như vậy ta xác định được mặt phẳng (xOz). Như vậy, một điểm và một vector pháp tuyến là đủ để định nghĩa một mặt phẳng. Sử dụng phương trình Vector của mặt phẳng thì pháp tuyến là Xn và điểm 3D (cũng là gốc của vector) là X. Chỉ có một giá trị cần phải chú ý là d (giá trị này cũng có thể tính được từ phương trình vector) Chú ý: Phương trình Vector trên hoàn toàn tương đương với phương trình mà ta thường dung là Ax + By + Cz + D = 0. Ở đây, ta chỉ cần thay Xn = (A,B,C) và X = (x,y,z) thì 2 phương trinh hoàn toàn tương đương. Tổng kết ta có được 2 phương trình: PointOnRay = RayStart + t * Raydirection (1) Xn dot X = d (2) Nếu tia giao với đường thẳng tại điểm nào đó thì điểm đó thì điểm đó thoả mãn cả 2 phương trinh (1) và (2). Vậy từ (1), (2): Xn dot PointOnRay = d hay: (Xn dot RayStart)+ t * (Xn dot Raydirection) = d Giải phương trình với ẩn t ta có : Thay d vào ta được : Cuối cùng: Ta nhận thấy rằng t chính là khoảng cách tử điểm gốc (gốc của tia) cho đến giao điểm của tia với mặt phẳng. Do vậy thông qua phương trình Vector ta nhận được t, từ đó có thể tìm thấy giao điểm của tia với mặt phẳng. Có một số trường hợp đặc biệt. Chẳng hạn : Nếu Xn dot Raydirection = 0 thì 2 vector này song song với nhau. Tức là tia song song với mặt phẳng và như vậy không có giao điểm nào. Nếu như tia không hướng vào mặt phẳng thì cũng không có giao điểm nào. int TestIntersionPlane(co