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

ong đó: . Độ dài ngắn nhất gồm tất cả 8 khoảng hình chiếu có tâm và bán kính: Hai khoảng chiếu sẽ không giao nhau khi và chỉ khi khoảng cách giữa các tâm lớn hơn tổng của các bán kính: |K1 - K0| > r0 + r1. Mỗi đại lượng ở 2 vế có cùng mẫu số . Do đó ta bỏ đi mẫu số này, điều kiện không giao nhau sẽ là: Đặt: (1) điều kiện không giao nhau là R > R0 + R1. Các trục của OBB thứ 2 có thể được viết dưới dạng tổ hợp các trục của OBB thứ nhất: với i = 0, 1, 2. Gọi: A là ma trận với cột là các thành phần của B là ma trận với cột là các thành phần của C là ma trận với cột là các thành phần cij Khi đó, ta có: B = AC → C = ATB trong đó T là toán tử chuyển vị. Cũng như vậy các trục của OBB thứ nhất có thể viết dưới dạng tổ hợp các trục của OBB thứ hai: với i = 0, 1, 2. Kiểm tra điều kiện không giao nhau gồm tích vô hướng của các bộ ba sau: (2) Trong đó: Sign(0,1) = Sign(1,2) = Sign(2,0) = +1 và Sign(1,0) = Sign(2,1) = Sign(0,2) = -1. Từ phương trình (1) và (2) ta có bảng sau: Bảng 1: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 2.2.2. Kiểm tra sự va chạm giữa các OBB a. Đối tượng tĩnh Kiểm tra sự giao nhau được xử lí trên 15 khả năng có thể của các trục phân tách. Nếu một trục nào được tìm thấy thì các trục còn lại không cần phải xử lý. Các đại lượng cij và |cij| được tính toán khi cần thiết. Điều này để tránh những tính toán không cần thiết khi có một trục nào đó được tìm thấy và một vài cij không cần được tính. Để tìm ra các trục phân tách ta dựa trên các điều kiện về Ro,R1 và R và kiểm tra điều kiện không giao nhau bằng cách so sánh R>Ro+R1. b. Đối tượng động - vận tốc không đổi Việc phát hiện giao nhau như các OBBs cần phải được sửa đổi đôi chút để có thể nắm được sự va chạm khi các OBBs có các thành phần vận tốc (giả sử là vận tốc không đổi). Nếu coi OBB thư nhất là đối tượng tĩnh thì vận tốc của OBB thư hai phải trừ đi vận tốc của OBB thứ nhất. Nếu vận tốc của các OBB lần lượt là và , đặt . Gọi thời gian ban đầu và kết thúc quá trình là t = 0 và t = T. Đặt với . Giả sử trục phân tách có dạng . Các đại lượng R0 và R1 độc lập đối với t và có thể được tính trong trường hợp đối tượng tĩnh, R phụ thuộc vào thời gian. Việc kiểm tra điều kiện không giao nhau sẽ là R(t) > R0 + R1 với . Do vận tốc dài (hay vận tốc tuyến tính) nên ta chỉ cần chỉ ra điều kiện không giao nhau sẽ là R(0) > R0 + R1, R(T)>R0+R1 và . Ý tướng của vấn đề là chỉ ra rằng |p + tw| > r > 0. if(p > r) { if(p + T*w > r) return no_intersection; } else if(p < -r) { if(p + T*w < -r) return no_intersection; } Nếu như có bất cứ một trục phân tách nào trong 15 trục có thể phân tách được 2 OBB trong toàn bộ khoảng thời gian thì sẽ không có va chạm xảy ra. Tuy nhiên, nếu không có trục nào trong 15 trục phân tách 2 OBB trong khoảng thời gian trên thì vẫn có khả năng không có sự giao nhau xảy ra. Ở đây trục phân tách chỉ có tác dụng chính là nếu nó được tìm thấy thì chắc chắn 2 OBB sẽ không giao nhau. Sự chuyển động của OBB đôi khi cũng khá phức tạp. Nếu như bạn nhìn các OBB dọc theo hướng chuyển động thì OBB xuất hiện như một đối tượng tĩnh. Do vậy hình chiếu của OBB lên bất kì một mặt phẳng nào vuông góc với hướng chuyển động sẽ không chuyển động khi OBB chuyển động. Nếu các hình chiếu không giao nhau thì 2 OBB không giao nhau trong khoảng thời gian đang xét. Nếu các hình chiếu giao nhau thì các OBB giao nhau. việc kiểm tra các hình chiếu không giao nhau yêu cầu thực hiện kiểm tra trên 6 trục bổ xung, các trục đó là : và với 0 ≤ i ≤ 2. Đặt: và với 0 ≤ i ≤ 2 Bảng 1': bảng các giá trị của R, Ro, R1 để kiểm tra điều kiện không giao nhau theo hướng chuyển động của 2 OBB: R > R0 + R1 2.2.3. Tìm va chạm giữa 2 OBBs Kiểm tra sự giao nhau của các OBB dùng toán tử boolean. Thuật toán trả về giá trị true nếu có sự giao nhau xảy ra và false trong trường hợp ngược lại. Không có thông tin thêm nào được cung cấp về vị trí xảy ra va chạm (có thể va chạm ở nhiều điểm). Trong trường hợp va chạm giữa các đối tượng tĩnh, vùng va chạm có thể được tính toán hơi khó. Đây là lĩnh vực tính toán của các đối tượng cứng. Đối với hệ thống động, các đối tượng chuyển động thì phải khởi tạo ban đầu không giao nhau và kiểm tra giao nhau trong suốt khoảng thời gian được chỉ định. Những trường hợp giao nhau sau có thể cho ra một điểm va chạm (nếu có): đỉnh - đỉnh, đỉnh - cạnh, đỉnh - mặt, cạnh - cạnh (không song song hoặc trùng nhau !) khi đó giao điểm là duy nhất. Trong trường hợp mặt - mặt hoặc cạnh - cạnh thì điểm giao không phải là duy nhất. Ta cần cung cấp thông tin về một trong những điểm va chạm. a. Tìm lần va chạm đầu tiên Cho 2 đối tượng không giao nhau tại thời điểm t = 0, nhưng chúng sẽ giao nhau ở một điểm sau đó, ta cần sử đổi thuật toán để quá trình kiểm tra giao nhau nếu phát hiện giao nahu thì sẽ cung cấp thời điểm va chạm đầu tiên. Lân va chạm đầu tiên sẽ phải nằm khoảng thời gian giới hạn lớn nhất là Tmax > 0, trong khoảng thời gian này tối thiểu phải tìm thấy một trục phân tách với mọi 0 ≤ t < T nhưng không tồn tại một trục phân tách nào ở thời điểm T. b. Tìm điểm va chạm Nếu T là thời điểm xảy ra lần va chạm đầu tiên, vấn đề hiện tại là phải tìm ra một điểm P là điểm giao của 2 OBB vào thời điểm đó. Ta cần giải phương trình sau: (3) Trong đó: , |xi| ≤ ai với i = 0,1,2, |yj| ≤ bj với j = 0,1,2. Trục : Nếu trục phân tách ở thời điểm T là thì sự giao nhau phải xảy ra trên một trong 2 mặt vuông góc với . Nhân vô hướng 2 vế của phương trình (3) với ta được: Nếu thì , 2 khoảng giao nhau ở điểm phía phải của [-R0, R0] Nếu thì ,2 khoảng giao nhau ở điểm phía trái của [-R0, R0] Do đó, , ở đây và : (4) Trong đó, và ; Vậy, , Tương tự, , trong trường hợp Nếu cij ≠ 0 thì phương trình (4) thoả mãn khi : Nếu mọi cij = 0 thì phương trình (4) không phụ thuộc vào yj. Điều này xảy ra khi khả năng giao nhau là cạnh - mặt hoặc mặt - mặt. Nhân vô hướng cả 2 vế của phương trình (3) với ta được : Từ |xk| ≤ ak ta được: Hơn nữa, chúng ta biết rằng |yj| ≤ bj. Chúng ta phải chọn giá trị của yj sao cho: . Va chạm xảy ra khi min(yj) ≤ bj và –bj ≤ max(yj). Nếu bj ≤ max(yj) thì yj = bj là một điểm giao. Nếu –bj ≥ min(yj) thì yj = -bj là một điểm giao, Ngược lại, ta sẽ chọn yj = min(yj) như một điểm giao. Trục : Nếu trục phân tách ở thời điểm T là thì sự giao nhau phải xảy ra ở trên một trong 2 mặt vuông góc với . Nhân vô hướng 2 vế của phương trình (3) với ta được: Cũng tương tự như lý luận ở trên ta có : với , hơn nữa: (5) Với |xj| ≤ aj và , do vậy Tương tự, , trong trường hợp . Nếu mọi cji =0 thì tổng ở phương trình trên không phụ thuộc vài xi. Chẳng hạn, điều này xảy ra khi giao nhau ở trường hợp cạnh - mặt hoặc mặt - mặt. Ta lại nhân 2 vế của phương trình (3) với được: Do |yk| ≤ bk nên ta có: Thêm nữa ta biết rằng: |xj| ≤ aj. Do vậy ta phải chọn xj sao cho: Sự giao nhau chỉ xảy ra khi : min(xj) ≤ aj và –aj ≤ max(xj). Nếu –aj ≥ min(xj) thì xj = -aj là một điểm giao. Nếu aj ≤ max(xj) thì xj = aj là một điểm giao. Các trường hợp còn lại chúng ta có thể chọn xj = min(xj) như một điểm giao. Trục : Các chỉ số (io, i1, i2) và (jo, j1, j2) là hoán vị của (0, 1, 2) trong tập : { (0, 1, 2),(1, 0, 2), (2, 0, 1) }. Nhân vô hướng 2 vế của phương trình (3) với ta được: Ở đây: . Chuyển về một vế, sau khi nhóm các số hạng lại với nhau ta được: Như đã nói ở phần trước, khi cij ≠ 0 thì tất cả các số nhân với |cij| phải bằng 0 để thỏa mãn phương trình trên. Trường hợp đầu tiên là : ci2jo ≠ 0, ci1jo ≠ 0, cioj2 ≠ 0 và cioj1 ≠ 0 thì: Để giải tìm xio và yjo, ta nhân vô hướng 2 vế của phương trình (3) với và ta được: Sau khi thay các giá trị cần thiết vào ta được kết quả là: Mẫu số của phân số trên khác không khi: , suy ra và Về phương diện hình học, các số cij phải bằng 0 trong trường hợp: va chạm cạnh - cạnh và điểm giao là duy nhất hoặc va chạm cạnh - cạnh trong đó các cạnh thực sự sắp thẳng hàng Những khả năng cần thiết để sinh ra điểm giao duy nhất được tổng kết lại trong bảng sau: Bảng 2: các khả năng cho giao điểm duy nhất giữa 2 OBB 2.3. Phương pháp Elipsoid 2.3.1. Không gian vector và sự tịnh tiến các vật thể trong không gian Thuật toán sử dụng phương pháp Elipsoid sau đây thiên về việc sử dụng không gian vector không phải thuộc dạng chuẩn để làm đơn giản hoá việc tính toán. Chúng ta sẽ đi tìm hiểu sơ qua cách chuyển từ một không gian vector này sang không gian vector khác. Phần lớn chúng ta chưa từng bắt gặp bấ kì không gian vector nào khác 2 loại không gian mà chúng ta đã học ở trường và sử dụng rất nhiều đó là không gian 2 và 3 chiều hay R2 và R3. Những không gian này được dùng trong hệ toạ độ chuẩn. Chúng ta cũng dễ dàng định nghĩa các không gian có số chiều lớn hơn (4 , 5 hoặc vô hạn) bằng cách đưa ra các luật mà tất cả các vector trong không gian đó phải tuân theo. Tất nhiên R2 và R3 cũng phải tuân theo. Tất nhiên chúng ta cũng khó có thể tưởng tượng loại không gian có số chiếu lớn hơn 3 và rõ ràng đây là một thách thức rất lớn khi chúng ta phải làm việc với các loại không gian vector như vậy. Tuy nhiên trong phần này chúng ta cũng chỉ sử dụng không gian 3 chiều mà thôi. Sau đây sẽ đưa ra các luật mà một không gian vector đều phải theo: Thỏa mãn luật cộng và nhân. Có nghĩa là cho 2 vector X, Y thuộc không gian vector đang xét thì Z = X + Y cũng thuộc không gian đó. Cho một số thực r, nếu X nằm trong không gian thì r*X cũng thuộc không gian đó. Tồn tại vector không V0 sao cho với mọi vector X trong không gian đó thì V0+X=X. Với mọi vector X thì X*0 = V0. Nó phải thoả mãn các phép toán học chuẩn như : luật kết hợp và luật giao hoán. Khái niệm về tổ hợp tuyến tính của các vector trong một không gian vector: đó là một vector nhận được khi ta tổ hợp các vector trong không gian vector bởi các phép cộng và phép nhân với một số vô hướng. Ví dụ, nếu bạn có các Vector X, Y ,Z và phép tổ hợp được thực hiện như sau: V = 2*X + (-3)*Y + 4*Z Rõ ràng theo luật 1 ở trên ta thấy rằng vector V nằm trong cùng không gian với các vector X, Y, Z. Tiếp theo ta đi định nghĩa một cơ sở cho một không gian vector. Cơ sở cho một không gian Vector là các Vector nằm trong không gian đó và được theo các luật sau đây: Tất cả các Vector trong không gian vector là tổ hợp tuyến tính của các vector cơ sở. Mỗi vector cơ sở không thể được tạo thành bằng cách tổ hợp các vector còn lại trong cơ sở đó. Số lượng các vector cần thiết để tạo nên cơ sở cho không gian vector đó bằng với số chiều của không gian đó. R3 là một không gian Vector và cơ sở của nó là: e1 = (1,0,0) e2 = (0,1,0) e3 = (0,0,1) Toạ độ của một điểm trong không gian vector chính là các thành phần vô hướng trong phép nhân với các vector cơ sở trong phép tổ hợp tuyến tính. Ví dụ, ta có điểm v =(5,2,4), ta có thể phân tích thành như sau: v = 5*e1 + 2*e2 + 4*e3 (OK) Đi thẳng vào vấn đề chính của chúng ta đó là làm thể nào để tạo ra được một không gian vector (ta sẽ tạo không gian Elipsoid). Chúng ta sẽ bắt đầu đi từ cơ sở của không gian đó (và đó cũng là đủ để định nghĩa không gian vector). Nếu như một ellipsoid được định nghĩa bởi vector các bán kính là (x,y,z) thì chúng ta sẽ chọn cơ sở của không gian đó là: v1 = (x,0,0) v2 = (0,y,0) v3 = (0,0,y) Trong không gian ellipsoid này thì bán kính của ellipsoid sẽ là (1,1,1). Vấn đề cuối cùng của chúng ta là làm thế nào để chuyển được một điểm từ không gian R3 vào không gian mới (không gian Ellipsoid). Chúng ta sẽ sử dụng cơ sở ở trên để thực hiện việc này (thông qua phép tổ hợp tuyến tính): Từ đó ta có được ma trận chuyển là : 2.3.2. Phát hiện va chạm Ý tưởng của thuật toán là mô phỏng đối tượng trong thế giới thực bởi Ellipsoid (hình bao Ellipsoid). Ellipsoid này được định nghĩa bởi tâm và bán kính của nó theo 3 trục tọa độ. Ví dụ như hình sau: Vị trí của tâm Ellipsoid được ta coi như là vị trí của đối tượng… Ta di chuyển đối tượng bằng cách tác dụng lực lên đối tượng theo một hướng nào đó. Hướng này được biểu diễn bởi vector vận tốc. Vị trí mới của Ellipsoid sau khi di chuyên được tính bằng cách cộng vị trí hiện tại với vector vận tốc. Giả sử thế giới ta giả lập được tạo bởi các tam giác (phân chia bề mặt vật thể hay mặt nền bởi các tam giác). Chúng ta không thể biết được chính xác là Ellipsoid trong lúc di chuyển sẽ va chạm chính xác vào tam giác nào. Chính vì vậy ta sẽ phải kiểm tra tất cả các tam giác đó (ta cũng có thể chia các vật thể thành các đơn vị nhỏ hơn). Kiểm tra tất cả các khả năng va chạm nếu có. Nếu phát hiện có một va chạm xảy ra (với một tam giác nào đó) thì ta không được dừng lại mà phải kiểm tra với các tam giác khác để tìm ra va chạm xảy ra gần nhất. Hình vẽ sau mô tả hiện tượng xảy ra khi ta tìm thấy một va chạm với tam giác A và không kiểm tra các tam giác còn lại (bao gồm tam giác B – cũng va chạm với Ellipsoid): Để làm giảm độ phức tạp của vấn đề ta sẽ chuyển tất cả các đối tượng vào trong không gian mới của chúng ta – không gian Ellipsoid. Trong không gian này thì Ellipsoid thực sự là hình cầu đơn vị. Thao ta và tính toán trên hình cầu tất nhiên là dễ dàng hơn rất nhiều (chỉ có bán kính và không bị ảnh hưởng bởi phép quay quanh trục đi qua tâm). Tiếp theo chúng ta sẽ kiểm tra tất cả các mặt (tam giác). Thủ tục kiểm tra mỗi mặt có thể được chia làm 5 bước nhỏ như sau: Tính mặt phẳng chứa tam giác. Tính điểm giao trên hình cầu khi chúng sẽ va chạm với mặt phẳng. Tính điểm giao trên mặt phẳng khi hình cầu va chạm với mặt phẳng. Tính toán nếu điểm va chạm trên mặt phẳng nằm trong tam giác. Nếu không ta phải tính lại điểm va chạm thực sự. Nếu xảy ra khả năng điểm giao không thực sự và khoảng cách tới điểm giao nhỏ hơn hoặc bằng độ lớn của khoảng cách mà chúng ta muốn di chuyển đối tượng, chúng ta sẽ kiểm tra điểm va chạm gần nhất có thể. Lưu thông tin va chạm. Khi thuật toán kết thúc, chúng ta sẽ lưu thông tin về điểm va chạm gần nhất (nếu có), những thông tin này là cần thiết để xử lý phản hồi sau va chạm (response). Khi toàn bộ quá trình phát hiện và xử lý va chạm kết thúc chúng ta sẽ chuyển toàn bộ kết quả vào không gian R3 chuẩn để được kết quả cuối cùng, cập nhật vị trí mới của đối tượng. Ta sẽ lần lượt thực hiện 5 bước trên: a. Tính mặt phẳng chứa tam giác. Ta cần nhớ mặt phẳng là vô hạn còn tam giác là một tập con của mặt phẳng đó (tập đóng). Chúng ta định nghĩa một mặt phẳng bởi một điểm gốc và một vector pháp tuyến vuông góc với mọi vector nằm trong mặt phẳng đó. Để xác định vector pháp tuyến ta dựa vào 2 vector không song song nằm trong mặt phẳng. Giả sử ta có mặt phẳng chưa tam giác ABC. Chọn A làm gốc và ta có 2 vector không song song được tính bởi công thức: v1 = B – A v2 = C – A Vector pháp tuyến được tính thông qua tích có hướng của 2 vector v1,v2 . H ình 2.3.2a: Tính mặt phẳng chứa tam giác inline D3DVECTOR wedge(D3DVECTOR v1, D3DVECTOR v2) { D3DVECTOR result; // Tính tích có hướng của 2 vector v1 và v2 result.x = (v1.y * v2.z) - (v2.y * v1.z); result.y = (v1.z * v2.x) - (v2.z * v1.x); result.z = (v1.x * v2.y) - (v2.x * v1.y); return (result); } D3DVECTOR pOrigin = A; D3DVECTOR pNormal = wedge(v1,v2); Chú ý rằng thứ tự của các Vector v1,v2 là rất quan trọng, nó xác định chiều của vector pháp tuyến. Chuẩn hóa vector pháp tuyến (độ dài bằng 1): inline void normalizeVector(D3DVECTOR& v) { double len = sqrt(v.x*v.x + v.y*v.y + v.z*v.z); v.x /= len; v.y /= len; v.z /= len; } normalizeVector(pNormal); Như vậy ta đã có được mặt phẳng chứa tam giác đang xét. Ta cũng cần phải chuyển tam giác vào không gian Ellipsoid trước khi thao tác với chúng bởi vì chúng ta đang làm việc trong không gian Ellipsoid. b. Tính điểm va chạm giả định trên hình cầu (cầu đơn vị) Trong bước này chúng ta sẽ tính trước điểm giao (nằm trên mặt cầu) khi mặt cầu va chạm với tam giác. Chúng ta chỉ dựa vào hình cầu và mặt phẳng chứa tam giác. Nếu ta sử dụng Ellipsoid thì bước này cũng hơi khó, tuy nhiên ta phải tận dụng không gian Ellipsoid để làm giảm độ phức tạp của vấn đề. Vấn đề hiện tại được mô tả bởi hình sau: Hình 2.3.2b: Tìm điểm va chạm giả định Hình vẽ trên có vẻ hơi phức tạp ! Tuy nhiên ý tưởng của nó được thể hiện rất rõ: ta sẽ tính điểm giao trên hình cầu trước khi di chuyển hình cầu bằng cách tịnh tính (giả định) mặt phẳng tới làm mặt phẳng tiếp diện với mặt cầu và ta được tiếp điểm chính là giao điểm sẽ xảy ra va chạm. Đường chấm chấm ở trên biểu diễn mặt phẳng tiếp diện khi ta tịnh tiến mặt phẳng. Thuật toán thực hiện việc này rất đơn giản chỉ là: eIPoint = source – pNormal; c. Tính điểm va chạm giả định nằm trên mặt phẳng Bước tiếp theo chúng ta sẽ tính điểm giao trên mặt phẳng khi hình cầu di chuyển dọc theo vector vận tốc sẽ va chạm với mặt phẳng tại điểm này. Để tìm điểm này thì rất đơn giản, ta chỉ cần kéo một tia từ điểm nằm trên mặt cầu dọc theo vector vận tốc, tia này cắt mặt phẳng tại đầu thì nó chính là điểm giao. Còn điểm nằm trên mặt cầu đó là điểm khi ta vẽ bán kính của mặt cầu song song và ngược chiều với vector pháp tuyến của mặt phẳng. Hình vẽ sau sẽ minh hoạ rõ điều này: Hình 2.3.2c: Tính điểm va chạm giả định nằm trên mặt phẳng Cài đặt như sau: inline float dot(D3DVECTOR& v1, D3DVECTOR& v2) { return (v1.x * v2.x + v1.y * v2.y + v1.z * v2.z); } double intersectRayPlane(D3DVECTOR rOrigin, D3DVECTOR rVector, D3DVECTOR pOrigin, D3DVECTOR pNormal) { double d = - (dot(pNormal,pOrigin)); double numer = dot(pNormal,rOrigin) + d; double denom = dot(pNormal,rVector); if (denom == 0) // không xảy ra va chạm //nếu pháp tuyến trực giao với vector vận tốc return (-1.0f); return -(numer / denom); } Trong thủ tục trên thì rVector là hướng của tia và vector này phải được chuẩn hoá. Hàm trả về độ dài của tia, tức là khoảng cách từ điểm sẽ va chạm trên hình cầu tới điểm sẽ va chạm trên mặt phẳng. // kéo tia theo vector vận tốc distToPlaneIntersection = intersectRayPlane(eIPoint, normalizedVelocity, pOrigin, pNormal); // tính điểm va chạm trên mặt phẳng pIPoint.x = eIPoint.x + distToPlaneIntersection * normalizedVelocity.x; pIPoint.y = eIPoint.y + distToPlaneIntersection * normalizedVelocity.y; pIPoint.z = eIPoint.z + distToPlaneIntersection * normalizedVelocity.z; eIPoint: điểm va chạm nằm trên Ellipsoid pIPoint: điểm va chạm nằm trên mặt phẳng Tuy nhiên, thủ tục nêu trên chưa xét hết tất cả các trường hợp. Ta hãy xét trường hợp mặt phẳng cắt mặt cầu như hình dưới, như vậy sẽ có chuyện gì xảy ra. Ta thấy rằng điểm va chạm bây giờ không phải là một điểm mà là một tập các điểm dẫn đến thủ trên sẽ gặp vấn đề. Hình 2.3.2c1: điểm va chạm sẽ là một tập các điểm Ta phải chọn điểm nằm trên mặt phẳng chính là điểm khi ta vẽ bán kính theo hướng của vector pháp tuyến của mặt phẳng, bán kính này giao với mặt phẳng tại điểm nào thì điểm đó là điểm cần tìm. Ta chỉ phải làm việc này khi mặt phẳng cắt mặt cầu. Thủ tục để kiểm tra trường hợp này là: DWORD classifyPoint(D3DVECTOR point, D3DVECTOR pO, D3DVECTOR pN) { D3DVECTOR dir = pO - point; double d = dot(dir, pN); if (d<-0.001f) return PLANE_FRONT; else if (d>0.001f) return PLANE_BACKSIDE; return ON_PLANE; } Thủ tục ở trên kiểm tra xem có hay không một điểm nằm ở trước, sau hoặc nằm trên mặt phẳng. Nếu điểm va chạm nằm sau mặt phẳng thì mặt phẳng sẽ cắt mặt cầu. Thủ tục quản lý trường hợp này như sau: DWORD pClass = classifyPoint(eIPoint, pOrigin, pNormal); // tìm điểm va chạm trên mặt phẳng if (pClass == PLANE_BACKSIDE) { // Mặt phẳng cắt mặt cầu // Tìm điểm va chạm bằng cách keo một tia dọc theo pháp tuyến của mặt phẳng distToPlaneIntersection = intersectRayPlane(eIPoint, pNormal, pOrigin, pNormal); // Tính điểm va chạm trên mặt phẳng pIPoint.x = eIPoint.x + distToPlaneIntersection * pNormal.x; pIPoint.y = eIPoint.y + distToPlaneIntersection * pNormal.y; pIPoint.z = eIPoint.z + distToPlaneIntersection * pNormal.z; } Từ lúc này ta không cần quan tâm đến vấn đề là mặt phẳng có cắt mặt cầu hay không. d. Tính toán điểm giao thực (nếu có) Đây là bước mà ta tính được điểm xảy ra va chạm thực sự (nếu có) - điểm mà hình cầu sẽ va chạm với tam giác. Có 2 trường hợp xảy ra: hoặc là điểm va chạm nằm trong tam giác chúng ta đang xét hoặc là nằm ngoài tam giác (thuộc mặt phẳng) - tất nhiên là không tính trường hợp mặt cầu không va chạm với mặt phẳng. Nếu điểm giao trên mặt phẳng nằm trong tam giác thì ta được điểm giao thực sự. Nếu không ta rơi vào tình huống là cả điểm giao trên mặt cầu và mặt phẳng đều không đúng và tất nhiên ta phải tính toán lại. Trong trường hợp điểm va chạm với mặt phẳng nằm ngoài tam giác. Ta sẽ lấy điểm nằm trên cạnh của tam giác sao cho điểm này nằm gần với điểm va chạm với mặt phẳng nhất. Từ điểm này ta sẽ kéo một tia song song với vector vận tốc và cắt mặt cầu tại điểm nào thì điểm đó chính là điểm va chạm thực sự. Trong trường hợp tia không cắt hình cầu thì sẽ không có va chạm xảy ra. Hình vẽ sau đây sẽ cho thấy rõ ý tưởng của bước này. Hình 2.3.2d: Tính điểm giao thực Nói tóm lại là chúng ta chỉ cần tính toán xem điểm va chạm có nằm trong tam giác hay không. Chắc chắn rằng điểm này nằm trong cùng một mặt phẳng với tam giác. Ta sẽ làm giảm độ phức tạp của vấn đề khi đưa chúng xét trong không gian 2 chiều. Sử dụng thuật toán nhỏ sau đây để giải quyết vấn để trên. Hình 2.3.2d1: Kiểm tra một điểm nằm trong tam giác Giả sử ta có điểm P bất kì. Ta nối điểm P với các đỉnh của tam giác ABC. Khi đó: Nếu P nằm trong tam giác ABC thì : góc(APB) + góc(BPC) + góc(CPA) = 360o Nếu P nằm ngoài tam giác ABC thì : góc(APB) + góc(BPC) + góc(CPA) < 360o Ta có thể cài đặt thuật toán như sau (chú ý rằng tích vô hướng của 2 vector đơn vị bằng cosin của góc giữa chúng): BOOL CheckPointInTriangle(D3DVECTOR point ,D3DVECTOR a, D3DVECTOR b, D3DVECTOR c) { double total_angles = 0.0f; // Tạo ra 3 vector D3DVECTOR v1 = point-a; D3DVECTOR v2 = point-b; D3DVECTOR v3 = point-c; normalizeVector(v1); normalizeVector(v2); normalizeVector(v3); total_angles += acos(dot(v1,v2)); total_angles += acos(dot(v2,v3)); total_angles += acos(dot(v3,v1)); // cho phép sai số trong khoảng xác định – vì thao tác với số dấu phảy động if (fabs(total_angles-2*PI) <= 0.005) return (TRUE); return(FALSE); } Thủ tục trên đây chỉ giải quyết được 1 trường hợp. Trường hợp còn lại ta phải giải quyết là khi điểm va chạm nằm ngoài tam giác. Như vậy theo lý thuyết trên ta phải tính toán điểm nằm trên cạnh của tam giác và gần với điểm va chạm giả định nhất. Điều này thực hiện quá đơn giản. Ta chỉ việc hạ 3 đường vuông góc từ điểm va chạm giả định xuống 3 cạnh của tam giác. Lấy đường vuông góc có độ dài nhỏ nhất. Nếu chân đường vuông góc nằm trên cạnh của tam giác thì chân đường vuông góc đó chính là điểm cần tìm. Ngược lại ta sẽ lấy một trong 2 đỉnh gần nhất của cạnh ứng với đường vuông góc đó: Hình 2.3.2d2: Kiểm tra điểm va chạm xác nhận điểm va chạm e. Va chạm xảy ra ? Qua 4 bước ở trên chúng ta đã tính được : Khoảng cách tới điểm va chạm (nếu có) Điểm va chạm trên mặt cầu Điểm va chạm trên tam giác Trước hết ta thấy rằng va chạm xảy ra thì khoảng cách tới điểm va chạm phải nhỏ hơn hoặc bằng quãng đường di chuyển của hình cầu (độ lớn của vector vận tốc). Tất nhiên ta vẫn chỉ xét riêng với tam giác hiện tại. Trong lúc di chuyển bất chợt nó có thể va chạm với các tam giác khác… 2.3.3. Xử lý va chạm Công việc xử lý va chạm có thể đơn giản ở mức ta cho khối cầu (Ellipsoid) dừng lại không di chuyển nưa. Tuy nhiên như vậy có vẻ không chuyên nghiệp…Chúng ta muốn sau va chạm khối cầu có thể nảy lên, hoặc trượt trên mặt phẳng hoặc nhảy qua một chướng ngại vật nào đó, như thế có vẻ hay hơn. a. Mặt phẳng trượt Nếu chúng ta muốn trượt trên mặt phẳng, cũng có nghĩa là khi va chạm với tam giác hay nền trong mối trường thì hướng của vector vận tốc sẽ thay đổi theo phương vuông góc với pháp tuyến của mặt phẳng và khối cầu tiếp tục chuyển động theo hướng mới. Hình 2.3.3: Xử lí trượt khi va chạm với tam giác Chúng ta sẽ đi tìm hiểu về mặt phẳng trượt, là mặt phẳng mà đối tượng của chúng ta sẽ tiếp tục chuyển động sau va chạm. Từ hình dưới đây bạn sẽ có những khái niệm về mặt phẳng trượt (mặt phẳng này chứa tam giác). Trong một vài trường hợp thì nó mô tả đúng nhưng cũng có một vài trường hợp nó không được chính xác. Hình 2.3.3a: Khái niệm mặt phẳng trượt Một cách chung chung thì mặt phẳng trượt là tiếp diện với cầu tại điểm va chạm mà ta tìm được trong phần phát hiện va chạm ở trên. Chính vì vậy ta phải tìm cách tính được mặt phẳng này khi biết điểm va chạm. Ta đã biết cách xây dựng mặt phẳng từ một điểm thuộc mặt phẳng và Vector pháp tuyến của mặt phẳng đó. Như vậy ta đã biết điểm va chạm chính là điểm cần tìm còn pháp tuyến của mặt phẳng trượt chính là Vector nối điểm va chạm này với tâm của hình cầu. Ở đây ta thấy lợi thế của việc sử dụng không gian Ellipsoid, việc xác định vector pháp tuyến rõ ràng là đơn giản hơn nhiều khi ta sử dụng nguyên hình Ellipsoid vì khi đó đường nối tâm với điểm va chạm chưa chắc có thể làm Vector pháp tuyến: H