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

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ình 2.3.3a1: Tiếp diện của mặt cầu b. Mặt phẳng tiếp diện của mặt cầu hoặc Ellipsoid Trong phần này ta sẽ đi xâu chi tiết về việc xây dựng mặt phẳng tiếp diện. Để giải đáp vấn đề ta cần sử dụng đến phép vi phân trên mặt chính quy. Mặt chính quy là mặt trơn và tiếp diện tại mỗi điểm sẽ không cắt bất kì phần còn lại nào của mặt đó (ví dụ như mặt cầu, Ellipsoid). Ta không cần định nghĩa lại thế nào là tiếp diện của một mặt phẳng. Xét trong không gian 2 chiều như ta đã biết tiếp tuyến của một đường cong tại một điểm được tính thông qua phép vi phân của đường cong tại điểm đó. Hình 2.3.3b: Tiếp tuyến của đường cong (2D) Hình vẽ trên mô tả đường cong trong không gian 2 chiều nhưng ta có thể coi nó như trong không gian 3 chiều vẫn có thể được. Một đường cong trong không gian 3 chiều và nằm trên mặt chính quy có thể biểu diễn thông qua 3 thông số toạ đoạ x,y,z với tham số là t. Cũng giống như trong không gian 2 chiều phương trình đường cong nói chung sẽ biểu diễn thông qua biến x, chẳng hạn : y = f(x) hoặc thông qua tham số là t, chẳng hạn: x = h(t) y = g(t) Trong không gian 3 chiều (3D) ta có thể biểu diễn đường cong A dưới dạng sau: A(t) = (x(t), y(t), z(t)) – t là tham số Lấy vi phân 2 vế với tham số là t ta được: A’(t) = (x’(t), y’(t), z’(t)) Để tính được mặt phẳng tiếp diện với mặt chính quy ta phải biết được 2 vector không song song nằm trong mặt phẳng tiếp diện. Giả sử ta có điểm P nằm trên mặt chính quy, ta tạo ra 2 đường cong phân biệt A và B nằm trên mặt chính quy và đi qua P. Lấy vi phân 2 đường cong A và B tại điểm P ta được các Vector tương ứng là A’(P) và B’(P). 2 Vector này là tiếp tuyến của đường cong tại P và cũng chính là 2 vector cần tìm. Hình 2.3.3b1: 2 đường cong trên bề mặt xác định được 1 tiếp diện với mặt cầu Vấn đề tiếp theo là làm thế nào để tìm được 2 đường cong A và B. Ta sẽ dựa vào phương trình của mặt cầu hoặc Ellipsoid: Mặt cầu bán kính r là tập các điểm (x,y,z) thoả mãn : Một Ellipsoid với vector bán kính là (a,b,c) là tập các điểm thoả mãn: Theo trên nếu ta đưa vào phương trình Ellipsoid bán kính là (r,r,r) thì ta được phương trình mặt cầu. Ta xét một định lý được phát biểu như sau: Nếu một mặt chính quy được cho bởi : S = { (x,y,z), f(x,y,z) = a} Trong đó : f là hàm vi phân và f: R3 → R a - hằng số thì S là mặt định hướng. Định lý trên đã được chứng minh và ta thấy rằng Ellipsoid của chúng ta thỏa mãn phương trình trên. Hàm f trên có dạng là : Ta có thể biểu diễn Ellipsoid bởi một tập A, sao cho: A = { (x,y,z) | f(x,y,z) = 1 } Như vậy, mọi điều kiện đều được thoả mãn. Cho một điểm P = (xo, yo, zo) trên đường cong có phương trình tham số là : A(t) =(x(t), y(t), z(t)) đường cong này đi qua điểm P tại t = to → A(to) = P Đường cong nằm trên mặt có phương trình f(x(t), y(t), z(t)) = a, với mọi t. Ta lấy vi phân cả 2 vế theo biến t , sau đó cho t = to ta được: Hay: Ta đã biết rằng nếu dot = 0 thì . Như vậy ta có thể nói rằng 2 vector: vuông góc với nhau. Ta có thể thấy ngay được rằng chính là tiếp tuyến của đường cong A tại điểm P ứng với t = to. Nó phải thuộc tiếp diện của Ellipsoid tại điểm P. Theo trên ta thấy vector sẽ vuông góc với mọi vector nằm trong mặt phẳng tiếp diện tại điểm P. Vậy nó chính là pháp tuyến của tiếp diện của Ellipsoid tại điểm P. Để tính được các thành phần của pháp tuyến ta sử dựa vào phương trình của f đó là: Lấy đạo hàm 2 vế lần lượt theo các các biến x,y,z ta được: Vậy pháp tuyến cần tìm có dạng: Trong đó (x,y,z) là điểm nằm trên mặt cầu hoặc Ellipsoid, (a,b,c) là vector bán kính. Ta có thể chuẩn hoá vector pháp tuyến này. Đến đây ta thấy được sự đơn giản khi sử dụng không gian Ellipsoid, khi đó ta có bán kính Ellipsoid là (1,1,1) và vector pháp tuyến trên sẽ có dạng: N(x,y,z) = (2x, 2y, 2z)=2*(x, y, z) Độ lớn của vector N: do P(x,y,z) nằm trên mặt cầu đơn vị nên rõ ràng ta có |P| = 1. Vì vậy, độ dài của 2*(x,y,z) là 2. Để chuẩn hoá vector này thành vector đơn vị ta chia mỗi thành phần vector này cho 2, ta được : Như vậy pháp tuyến của mặt phẳng tiếp diện tại một điểm P(x,y,z) của mặt cầu đơn vị là (x,y,z). Nó chính là vector bán kính nối từ điểm P vào tâm cầu. Hình 2.3.3b2: Tất cả các pháp tuyến của tiếp diện của mặt cầu đều có hướng vào tâm cầu c. Xử lí trượt trên mặt phẳng: Ở phần trên chúng ta đã tính được mặt phẳng trượt. Chúng ta sẽ vận dụng lý thuyết đó để thực hiện tính toán tiếp. Các bước thực hiện có thể như sau: Di chuyển khối cầu gần bề mặt tam giác đến mức có thể (tam giác mà khối cầu sẽ va chạm). Tính toán mặt phẳng trượt dựa trên vị trí mới. Chiếu vector vận tốc lên mặt phẳng trượt để nhận được hướng mới. Tính vận tốc mới bằng cách trừ điểm va chạm giả định với điểm giao thực sự. Tiếp tục thực hiện phát hiện va chạm với vị trí và hướng chuyển động mới. Quá trình phát hiện và xử lí va chạm là một quá trình đệ quy. Mỗi bước đệ quy chúng ta sẽ kiểm tra tất cả các tam giác. Chúng ta sẽ tiếp tục đệ quy cho đến khi: Khối cầu không còn va chạm với bất kỳ đối tượng nào nữa, công việc còn lại chỉ là cập nhật vị trí mới. Vận tốc của khối cầu là rất nhỏ (≈ 0). Hình vẽ sau sẽ mô tả độ lớn và hướng của vector vận tốc mới khi khối cầu va chạm phải tam giác: Hình 2.3.3c: Độ lớn và hướng của vector vận tốc khi va chạm với mặt phẳng Để tính được vận tốc, ta chiếu vận tốc cũ lên mặt phẳng trượt, chúng ta sẽ tìm được hình chiếu này dễ dàng. Hình chiếu này chính chiều và độ lớn của vector vận tốc mới. Ta sẽ thực hiện tiếp chuyển động của khối cầu theo vector này. 2.4. Phát hiện va chạm giữa các đối tượng cơ sở 2.4.1. Phát hiện va chạm giữa hộp bao và tam giác (Box – Triangle) Tam giác được biểu diễn bởi tập 3 đỉnh , với i = 0,1,2. Các cạnh của tam giác là: Pháp tuyến của mặt phẳng chứa tam giác là: . Không nhất thiết là vector đơn vị. Các điểm thuộc tam giác là: a. Sự phân tách giữa tam giác và hộp bao Hộp bao (OBB) có tâm là , các trục , và các gia số a0, a1, a2. Tam giác có các đỉnh là Các cạnh của tam giác là: Pháp tuyến của mặt phẳng chứa tam giác là: Đặt . Các trục phân tách sẽ có dạng , trong đó là một trong các Vector sau : , hoặc với i = 0,1,2 và j = 0,1,2. Đối với OBB, khoảng cách hình chiếu của các đỉnh theo đường gốc là : Khoảng ngắn nhất bao gồm hình chiếu của 8 đỉnh có tâm 0 và bán kính là: Khoảng cách của hình chiếu của các đỉnh tới đường gốc là: với k = 0,1,2. Hình chiếu của tam giác không có tâm hoặc bán kính như hình chiếu của hộp bao. Kiểm tra sự không giao nhau bây giờ trở thành việc chỉ ra rằng khoảng ngắn nhất bao gồm hình chiếu của 3 đỉnh được phân tách với các khoảng hình chiếu của hộp bao. Đăt: (6) (7) Từ (6) và (7) ta có bảng sau: Bảng 3: Các giá trị của R, po, p1 và p2 để kiểm tra điều kiện không giao giữa Tam giác và hộp bao nhau : min(p0,p1,p2) > R hoặc max(p0,p1,p2) < -R Nếu chiếu vào trục thì hình chiếu của các đỉnh của tam giác là trùng nhau. Chính vì vậy, việc kiểm tra giao nhau tương đương với việc chỉ ra rằng không thuộc khoảng [-R, R]. Khi chiếu lên các trục , thì hình chiếu của các đỉnh của tam giác là phân biệt. Đối với , có 2 đỉnh phân biệt nhau. Nếu khoảng hình chiếu của tam giác là [min(p0,p1,p2), max(p0,p1,p2)] và của hộp bao là [-R, R] thì hộp bao và tam giác không giao nhau khi min(p0,p1,p2) > R hoặc max(p0,p1,p2) < -R. b. Kiểm tra va chạm giữa hộp bao và tam giác Trường hợp tĩnh Kiểm tra sự giao nhau trong trường hợp này ta cần xử lý trên 13 trục phân tách có thể. Nếu một trục được tìm thấy thì không phải xử lý các trụccòn lại. Các hệ số cần thiết để dùng nhiều lần trong các phép nhân được tính toán chỉ một lần và chỉ khi cần thiết. Pháp tuyến : điều kiện không giao nhau là . Ta sẽ kiểm tra nếu p không thuộc khoảng [-R, R]: if(|p| > R) return no_intersection; Các trục : Các giá trị của p là p, p+d0, p+d1. Điều kiện không giao nhau là: min(p, p+d0, p+d1) > R hoặc max(p, p+d0, p+d1) < -R. if (p > R) { if (d0 >= 0) { if (d1 >= 0) return no_intersection; // pmin = p > R if (p+d1 > R) return no_intersection; // pmin = p+d1 > R }else if (d1 <= d0) { if (p+d1 > R) return no_intersection; // pmin = p+d1 > R }else { if (p+d0 > R) return no_intersection; // pmin = p+d0 > R } } else if (p < -R) { if (d0 <= 0) { if (d1 <= 0) return no_intersection; // pmax = p < -R if (p+d1 < -R) return no_intersection; // pmax = p+d1 < -R } else if (d1 >= d0) { if (p+d1 < -R) return no_intersection; // pmax = p+d1 < -R } else { if (p+d0 < -R) return no_intersection; // pmax = p+d0 < -R } } Các trục : Tồn tại 2 giá trị phân biệt pi, ta gọi là p và p+d. Điều kiện khoôg giao nhau là min(p, p+d) > R hoặc max(p, p+d) < -R. if (p > R) { if (d >= 0) return no_intersection; // pmin = p > R if (p+d > R) return no_intersection; // pmin = p+d > R } else if (p < -R) { if (d <= 0) return no_intersection; // pmax = p < -R if (p+d < -R) return no_intersection; // pmax = p+d < -R } Trường hợp động - vận tốc không đổi Trong trường hợp Tam giác và hộp bao thêm yếu tố vận tốc, ta cần phải sửa lại đôi chút thuật toán. Nếu ta coi tam giác là đối tượng tĩnh còn hộp bao là đối tượng động thì vận tốc của hộp bao phải trừ đi vận tốc của tam giác và ngược lại, nếu coi tam giác là tĩnh thì vận tốc của nó phải trừ đi vận tốc của hộp bao. Nếu vận tốc của hộp bao là và vận tốc của tam giác là , đặt . Thời điểm ban đầu và kết thúc là t = 0 và t = T. Đặt: và . Đoạn hình chiếu của hộp bao [-R, R] là cố định. Hình chiếu của tam giác phụ thuộc vào thời gian, [min(p)(t), max(p)(t)]. Điều kiện để kiểm tra không giao nhau (phải được thực hiện suốt khoảng thời gian [0, T]) là min(p)(t) > R với mọi hoặc max(p)(t) < -R với mọi . Bởi vì ở đây vận tốc ta xét là vận tốc dài không đổi, nên điều kiện cần và đủ để kiểm tra sự không giao nhau là cần chỉ ra: min{ min(p)(0), min(p)(T)} > R hoặc max{ max(p)(0), max(p)(T)} < -R. Pháp tuyến :Điều kiện kiểm tra không giao nhau là với , ,. if (p > R) { if (p+T*w > R) return no_intersection; } else if (p < -R) { if (p+T*w < -R) return no_intersection; } Các trục : Vấn đề ở đây là phải chắc chắn rằng đoạn nhỏ nhất chứa các điểm : { p + T.w, p + d0 + T.w, p + d1 + T.w} không giao với đoạn [-R, R] Khi w = 0 - trường hợp tĩnh, ta đã thảo luận trước đây. Khi w ≠ 0, khi t = 0 thì không có sự giao nhau. if (p > R){ if (d0 >= 0) { if (d1 >= 0) { min = p; if (min + T*w > R) return no_intersection; } else { min = p + d1; if (min > R && min + T*w > R) return no_intersection; } } else if (d1 <= d0) { min = p + d1; if (min > R && min + T*w > R) return no_intersection; } else { min = p + d0; if (min > R && min + T*w > R) return no_intersection; } } else if (p < -R) { if (d0 <= 0) { if (d1 <= 0) { max = p; if (max + T*w < -R) return no_intersection; } else { max = p + d1; if (max R) return no_intersection; } } else if (d1 >= d0) { max = p + d1; if (max < -R && max + T*w < -R) return no_intersection; } else { max = p+d0; if (max < -R && max + T*w < -R) return no_intersection; } } Các trục : Vấn đề của chúng ta ở đây là phải có được đoạn ngắn nhất chứa các điểm: { p + T.w , p + d + T. w } không giao với đoạn [ -R , R ]. if (p > R) { if (d >= 0) { min = p; if (min+T*w > R) return no_intersection; } else { min = p+d; if (min > R && min+T*w > R) return no_intersection; } } else if (p < -R) { if (d <= 0) { max = p; if (max+T*w < -R) return no_intersection; } else { max = p+d; if (max < -R && max+T*w < -R) return no_intersection; } } c. Tìm điểm va chạm giữa hộp bao và tam giác Kiểm tra va chạm trả về một giá trị boolean. Giải thuật trả về true nếu có một va chạm, ngược lại là false. Không có thông tin nào được cung cấp về nơi va chạm xảy ra (có thể có nhiều điểm va chạm). Nhưng ứng dụng tốt sẽ đưa ra được thông tin về lần va chạm đầu tiên và điểm (nhiều điểm) xảy ra va chạm ở thời điểm đó. Những trường hợp sẽ cho ra một điểm va chạm nếu có là : đỉnh - đỉnh, đỉnh - cạnh, đỉnh - mặt, cạnh - mặt (không trùng nhau), khi đó điểm giao sẽ là duy nhất. Trong trường hợp khác, canh - mặt hoặc mặt - mặt sẽ cho ra điểm giao không phải duy nhất (nhiều điểm), tuy nhiên chúng ta sẽ cung cấp thông tin về một trong những điểm giao đó. 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 ở thời điểm nào sau đó. Giải thuật cần thiết của chúng ta là phải cung cấp lần va chạm đầu tiên của 2 đối tượng nêu trên nếu có. Lần va chạm đầu tiên sẽ xảy ra và được tính toán trong khoảng thời gian lớn nhất là T > 0, trong khoảng thời gian này tối thiểu sẽ tồn tại một trục phân tách với , nhưng tại thời điểm T không tồn tại một trục phân tách nào cả. Ta cần kiểm tra tất cả các trục phân tách có thể. Tìm điểm va chạm Nếu T là lần va chạm đầu tiên, vấn đề của ta là tìm được một điểm P là giao điểm của tam giác và hộp bao khi xảy ra va chạm. Như vậy ta cần giải phương trình: (8) Ở đây và |xi| ≤ ai, i = 0,1,2 , 0 ≤ y0 ≤ 1, 0 ≤ y1 ≤ 1 và y0 + y1 ≤ 1. Từ phương trình (8) ta có : (9) Với i = 0,1,2 và j = 0,1. giá trị của x có thể nằm ở các đỉnh của tam giác : (0,0) , (1,1) và (1,0). . Các giá trị lớn nhất và nhỏ nhất là: (10) Ta cũng có : . y đạt các giá trị cực đại hoặc cực tiểu khi tất cả các |xi| = ai. Với : (11) Ta định nghĩa một vài hàm sau: Từ các hàm ở trên ta thấy: . Xét pháp tuyến : Nếu trục phân tách ở thời điểm T là thì va chạm phải xảy ra trên mặt của tam giác. Nhân vô hướng 2 vế của phương trình (8) với ta được: Chú ý rằng với . Do đó: (12) Với |xi| ≤ ai và , nên ta sẽ có : . Nếu thì thoả mã phương trình (12). Nếu có thì phương trình (12) không phụ thuộc vào xi. Điều này xảy ra trong trường hộp giao nhau cạnh – tam giác hoặc mặt – tam giác. Khi đó, bất ta có thể chọn bất kì để làm điểm va chạm. Xét các trục : Nếu trục phân tách tại thời điểm T là thì giao điểm phải nằm trên 1 trong 2 mặt của hộp bao vuông góc với và R = ai. Công thức tính xi trong phương trình (9) sẽ có 3 giá trường hợp của : Trường hợp 1: p0 = minj(pj) = ai ,trong đó hoặc p0 = maxj(pj) = -ai, trong đó Như vậy, và . Sự va chạm xảy ra trên bề mặt của hộp bao vuông góc với , vì vậy và:: (13) Nếu và , thì y0 = 0 và y1 = 0. Nếu và thì phương trình (13) cần y1 = 0, y0 tuỳ ý. Trong trường hợp với min(y0) và max(y0) được cho bởi phương trình (11). Nếu và thì phương trình (13) cần y0 = 0, y1 tùy ý. Trong trường hợp , với min(y1) và max(y1) được cho trong phương trình (11). Nếu và thì phương trình (13) không phụ thuộc vào một trong các giá trị y0 hoặc y1. Hộp bao giao với Tam giác trong trường hợp mặt - mặt, trục phân tách là . Trường hợp 2: Nếu: p1 = minj(pj) = ai với hoặc p1 = maxj(pj) = -ai với Thì: và Với , ta có: (14) Nếu và thì 1 – y0 – y1 = 0 và y1 = 1 → y0 = 0 và y1 = 1 Nếu và thì phương trình (14) cần có y1 = 0 và không phụ thuộc vào y0. Trong trường hợp , với min(y0) và max(y0) được cho trong phương trình (11). Nếu và thì phương trình (14) cần có y0 + y1 = 1 và không phụ thuộc vào y1. Trong trường hợp , với min(y1) và max(y1) được cho trong phương trình (11). Nếu ta có được y1 thì y0 = 1 – y1. Nếu thì hoặc y0 hoặc y1 bị phụ thuộc. Nếu và song song thì ta có thể chọn trục phân tách để kiểm tra là . Trường hợp 3: p2 = minj(pj) = ai với p2 = maxj(pj) = -ai với Như vậy: và ta được: và (15) Nếu và thì phải có 1-y0-y1 = 0 và y0 = 0. Do đó : y0 = 0 và y1=1. Nếu và thì phương trình (15) có y0 = 0 và y1 tuỳ ý. Trong đó được cho trong phương trình (11). Nếu ta có y1 thì y0=1-y1. Nếu và thì phương trình (15) có 1-y0-y1=0 và không phụ thuộc vào y0. Nếu ta chọn được y0 thì y1 = 1-y0. Nếu thì một trong 2 giá trị y0 hoặc y1 sẽ bị ràng buộc. Trong trường hợp và song song thì ta có thể chọn trục phân tách là . Xét trục : Cho (i0,i1,i2) và (j0,j1,j2) là hoán vị của (0,1,2) trong tập {(0,1,2),(1,0,2),(2,1,0)} Nhân vô hướng phương trình với ta được: Sau khi rút gọn ta được: (16) Ở đây, được cho trong bảng 3. Hình chiếu của các đỉnh của tam giác có thể cho ta 2 giá trị p phân biệt, , có 2 trường hợp có thể tuỳ thuộc vào giá trị của p là cực đại hay cực tiểu. Với mọi trường hợp có thể xảy ra ta sẽ có: Trường hợp thứ nhất là : với hoặc với . Như vậy và . Phương trình (16) tương đương với phương trình sau: Nếu thì Nếu thì . Nếu thì Như vậy, ta đã biết được 3 trong 5 phương trình cần phải có. 2 Phương trình còn lại có thể suy được từ phương trình (9). Nếu bất cứ xi và yj không bị ràng buộc (tuỳ ý) thì hệ số của chúng phải bằng 0. Các hệ số cần thiết để cho ra điểm giao duy nhất được tổng kết trong các bảng sau: Bảng 4a: Các hệ số để có các điểm giao duy nhất giữa hộp bao và tam giác Trục và Bảng 4b: Các hệ số cho các điểm giao duy nhất giữa hộp bao và tam giác trục là . Bảng 4c: Các hệ số cho các điểm giao duy nhất giữa hộp bao và tam giác trục là . Bảng 4d: Các hệ số cho các điểm giao duy nhất giữa hộp bao và tam giác trục là 2.4.2. Phát hiện va chạm giữa 2 tam giác (Triangle-Triangle) a. Sự phân tách giữa 2 tam giác Tam giác thứ nhất có các đỉnh là , các cạnh Pháp tuyến : Tam giác thứ hai có các đỉnh là : , các cạnh: Pháp tuyến: Đặt . Việc phát hiện va chạm giữa các tam giác trong môi trường 3D được thực hiện thông qua các trục phân tách (dùng để kiểm tra tam giác không giao nhau). Tập các trục phân tách có thể phụ thuộc vào 2 tam giác có song song với nhau hay không.. Nếu 2 tam giác song song với nhau nhưng không đồng phẳng thì pháp tuyến các pháp tuyến của 2 tam giác sẽ là trục phân tách. Tuy nhiên nếu các tam giác đồng phẳng thì pháp tuyến của một tam giác sẽ là trục phân tách. Tích có hướng của một vector pháp tuyến với một cạnh của tam giác sẽ cho ta trục phân tách có thể có.Tích có hướng giữa các cạnh tam giác cũng cho ta trục phân tách có thể. Cho 2 tam giác không song song, các trục phân tách có thể có dạng là: , trong đó là một trong các trục hoặc với i=0,1,2 và j=0,1,2. Trường hợp các tam giác đồng phẳng hoặc song song thì có thể là một trong các thành phần sau với i=0,1,2. Ta đặt: (17) và: (18) Từ các đại lượng trong (17) và (18) ta có được bảng mô tả các trục phân tách có thể của 2 tam giác không song song là: Bảng 5: các giá trị của pi và pj để kiểm tra điều kiện không giao nhau của 2 tam giác không đồng phẳng: mini(pi) > maxj(qj) hoặc maxi(pi) < minj(qj). Bảng các trục phân tách có thể đối với 2 tam giác đồng phẳng được cho trong bảng sau. Các đại lượng trong bảng là: Với i = 0,1 và j=0,1. Bảng 6: Các giá trị của pivà qj kiểm tra sự không giao nhau của 2 tam giác đồng phẳng: mini(pi) > maxj(qj) hoặc maxi(pi) < minj(qj) b. Phát hiện va chạm giữa 2 tam giác không đồng phẳng Ta chỉ xét trường hợp 2 tam giác không đồng phẳng. Với hệ thống va chạm trong môi trường 3D thì các đối tượng chủ yếu được chia mặt thành các tam giác (ít khi chia thành các đa giác: 4 hoặc nhiều hơn ... các cạnh). Tam giác tĩnh Việc kiểm tra va chạm trong trường hợp này vẫn là xử lý các trục phân tách. Các hệ số trong các phép nhân phức tạp được tính toán một lần và chỉ khi cần thiết. Để kiểm tra các trục phân tách cơ sở ta đi xét các khoảng [mini(pi),maxi(pi)] và [minj(pj),maxj(pj)] . Cuối cùng để kiểm tra xem 2 tam giác có giao nhau hay không ta so sánh các khoảng này. Xét các trục hoặc : Đây là các pháp tuyến của các tam giác, nên nếu chọn một pháp tuyến làm trục thì hình chiếu của tam giác đó lên trục này sẽ được 1 điểm p duy nhất, tam giác còn lại khi chiếu các đỉnh lên sẽ cho ta 3 điểm q, q + do và q + d1. Điều kiện không giao nhau là : min(q, q+d0, q+d1) > p hoặc max(q, q+d0, q+d) < p. Thủ tục được cài đặt như sau: if (q > p) { if (q+d0 > p && q+d1 > p) return no_intersection; } else if (q < p) { if (q+d0 < p && q+d1 < p) return no_intersection; } Xét các trục : Mỗi tam giác sẽ chiếu lên trục này sẽ cho ta 2 điểm, tam giác thứ nhất cho 0 và p,tam giác thứ 2 cho q và q+d. Điều kiện kiêm tra không giao nhau là : min(q, q+do, q+d1) > max{0, p} hoặc: max(q, q+do, q+d1) < min{0, p} Thủ tục được cài đặt như sau: if (p >= 0) { if ((q p && q+d > p)) return no_intersection; } else { if ((q > 0 && q+d > 0) || (q < p && q+d < p)) return no_intersection; } Trường hợp động - vận tốc không đổi Trường hợp tam giác tĩnh cần được chỉnh lại để phù hợp với trường hợp tam giác có thành phần vận tốc. Nếu lấy một tam giác làm gốc thì tam giác vận tốc của tam giác còn lại phải được trừ đi độ lớn của tam giác thứ nhất, vì vậy tất cả các trường hợp ta có thể quy về cho một tam giác tĩnh (giả sử là tam giác thứ nhất). Giả sử vận tốc của các tam giác lần lượt là: và , đặt . Gọi thời điểm ban đầu và kết thúc là t = 0 và t = T. Xét các trục hoặc : Như đã trình bày ở trên, sẽ tồn tại một tam giác mà khi chiếu lên một trong 2 trục này sẽ cho hình chiếu là một điểm p duy nhất. Tam giác còn lại khi chiếu lên sẽ cho 3 điểm di động q. Vấn đề của chúng ta ở đây là cần chỉ ra rằng: min(q+t.w, q+do+t.w, q+d1+t.w) > p hoặc: max(q+t.w, q+do+t.w, q+d1+t.w) < p Với . Thủ tục được cài đặt như sau: if (q > p) { if (d0 >= 0) { if (d1 >= 0) { min = q; if (min+T*w > p) return no_intersection; } else { min = q+d1; if (min > p && min+T*w > p) return no_intersection; } } else if (d1 <= d0) { min = q+d1; if (min > p && min+T*w > p) return no_intersection; } else { min = q+d0; if (min > p && min+T*w > p) return no_intersection; } } else if (q < p) { if (d0 <= 0) { if (d1 <= 0) { max = q; if (max+T*w < p) return no_intersection; } else { max = q+d1; if (max < p && max+T*w < p) return no_intersection; } } else if (d1 >= d0) { max = q+d1; if (max < p && max+T*w < p) return no_intersection; } else { max = q+d0; if (max < p && max+T*w < p) return no_intersection; } } Xét trục : Hình chiếu của tam giác thứ nhất là 0 và p. Hình chiếu của tam giác thứ hai là q + tw và q + d + tw với Vấn đề của chúng ta là phải chỉ ra được rằng: min(q+tw, q+d+tw) > max(0,p) hoặc: max(q+tw, q+d+tw) < min(0,p) Thủ tục được cài đặt như sau: if (p >= 0) { if (q < 0) { if (d <= 0) { max = q; if (max+T*w < 0) return no_intersection; } else { max = q+d; if (max < 0 && max+T*w < 0) return no_intersection; } } else if (q > p) { if (d >= 0) { min = q; if (min+T*w > p) return no_intersection; } else { min = q+d; if (min > p && min+T*w > p) return no_intersection; } } } else { if (q > 0) { if (d >= 0) { min = q; if (min+T*w > 0) return no_intersection; } else { min = q+d; if (min > 0 && min+T*w > 0) return no_intersection; } } else if (q < p) { if (d <= 0) { max = q; if (max+T*w < p) return no_intersection; } else { max = q+d; if (max < p && max+T*w < p) return no_intersection; } } } c. Tìm va chạm giữa 2 tam giác không đồng phẳng Tìm lần va chạm đầu tiên Cho 2 tam giác không giao nhau ở thời điểm t = 0, nhưng sẽ giao nhau ở thời điểm nào đó (sau t = 0). Thuật toán của chúng ta cần cung cấp lần va chạm đầu tiên (nếu có). Lần va chạm đầu tiên được tính trong khoảng thời gian lớn nhất là T > 0 trong khoảng thời gian này tồn tại tối thiểu một trục phân tách, nhưng sẽ không tồn tại trục phân tách nào ở thời điểm T. Tìm điểm va chạm Nếu T là lần va chạm đầu tiên, vấn đề của chúng ta là tìm ra được một điểm P là giao điểm của 2 tam giác. Các tam giác không đồng phẳng, khả năng tập giao điểm sẽ là một điểm hoặc một đoạn thẳng giao nhau. Ta cần giải phương trình: (19) Trong đó: Với: 0 ≤ x0 ≤ 1, 0 ≤ x1 ≤ 1, x0 + x1 ≤ 1 0 ≤ y0 ≤ 1, 0 ≤ y1 ≤ 1, y0 + y1 ≤ 1 Giải phương trình (19) ta được: với i = 0,1 và j = 0,1. Giá trị cực trị của nghiệp phương trình cho ta các khoảng của mỗi biến: và . Các điểm mút là: (20) Ở đây: Xét trục phân tách : Nhân vô hướng phương trình (19) với ta được: Hình chiếu của các đỉnh của tam giác sẽ cho ta một điểm p có giá trị 0. Các đỉnh của tam giác thứ 2 sẽ cho ta các điểm q phân biệt {q0,q1,q2} được định nghĩa trong Bảng 5. Có 3 trường hợp: Trường hợp 1: q0 = mini(qi) với hoặc q0 = maxi(qi) với Như vậy: , và: (21) Nếu và thì y0=0 và y1=1. Nếu và thì y1=0 và không phụ thuộc vào y0. Điểm va chạm sẽ là bất cứ điểm trong đó min(y0) và max(y0) được cho trong phương trình (20). Nếu và phương trình (21) cần y0 = 0 và không phụ thuộc vào y1. Điểm va chạm sẽ là bất cứ điểm trong đó min(y1) và max(y1) được cho trong phương trình (20). Nếu và thì và phải song song và 2 tam giác phải đồng phẳng. Trong phần này chúng ta đã giả sử rằng 2 vector không song song, như vậy giả thuyết trên là sai. Chúng ta sẽ thảo luận về va chạm giữa 2 tam giác đồng phẳng sau. Trường hợp 2: q1 = mini(qi) với hoặc q1 = maxi(qi) với Như vậy: và: (20) Nếu và thì y0 + y1 =1 và y0 = 0. Do đó: y0=1 và y1=0. Nếu và thì phương trình (22) cần y1 = 0 nhưng không phụ thuộc vào y0. Với trong đó min(y0) và max(y0) được cho trong phương trình (20). Nếu và thì phương trình (22) cho y0 + y1 =1 nhưng không phụ thuộc vào y1. Trong trường hợp này với min(y1) và max(y1) được cho trong phương trình (20). Nếu ta chọn y1 thì y0=1-y1. Nếu và thì và phải song song, suy ra 2 tam giác đồng phẳng. Trường hợp 3: q2 = mini(qi) với hoặc q2 = maxi(qi) với Như vậy: và: (23) Nếu và thì y0 = 0 và y0+y1=0 do đó: y0=0, y1=1. Nếu và thì y0 = 0 và y0+y1=0 do đó: y0=0, y1=1. Trong trường hợp này với min(y0) và max(y0) được cho trong (20).g ph Nếu ta chọn y0 thì y1 = 1-y0. Nếu và thì phương trình (23) cần y0=0 và không phụ thuộc vào y1. Trong trường hợp này: với min(y1) và max(y1) được cho trong (20). Nếu và thì và phải song song, suy ra 2 tam giác đồng phẳng. Xét các trục : Nhân vô hướng phương trình (19) với ta được: Các đỉnh của tam giác thứ nhất chiếu lên trục này sẽ cho các điểm p phân biệt {p0,p1,p2}. Các đỉnh của tam giác thứ 2 khi chiếu lên trục này sẽ cho giá trị q, q0 được cho trong Bảng 5. Có 3 trường hợp xảy ra: Trường hợp 1: p0 = mini(pi) với hoặc p0 = maxi(pi) với Như vậy: và: (24) Nếu và thì x0=0 và x1=0. Nếu và thì phương trình (24) cần x1=0 và không phụ thuộc vào x0. Điểm giao được cho bởi x0 bất kì sao cho với min(x0) và max(x0) được cho trong (20). Nếu và thì phương trình (24) cần x0=0 và không phụ thuộc vào x1. Điểm giao là x1 bất kì sao cho với min(x1) và max(x1) được cho trong phương trình (20). Nếu và thì và phải song song dẫn đến 2 tam giác đồng phẳng (không xét). Trường hợp 2: p1 = mini(pi) với hoặc p1 = maxi(pi) với Như vậy: và: (25) Nếu và thì x0 + x1 = 1 và x1 = 0. Do đó: x1=0 và x0=1. Nếu và thì phương trình (25) cần x1 = 0 và không phụ thuộc vào x0. Trong trường hợp này với min(x0) và max(x0) được cho trong (20). Nếu và thì phương trình (25) cần x0+x1=1 và không phụ thuộc vào x1. Trong trường hợp này với min(x1) và max(x1) được cho trong (20). Chọn một điểm x1 thì x0 = 1-x1. Nếu và thì và song song với nhau , do đó 2 tam giác đồng phẳng. Trường hợp 3: p2 = mini(pi) với hoặc p2 = maxi(pi) với Như vậy: và: (26) Nếu và thì x0 + x1 = 1 và x0 = 0. Do đó: x1=1 và x0=0. Nếu và thì phương trình (25) cần x0+x1=1 và không phụ thuộc vào x0. Trong trường hợp này với min(x0) và max(x0) được cho trong (20). Chọn một điểm x0 thì x1 = 1-x0. Nếu và thì phương trình (25) cần x0 = 0 và không phụ thuộc vào x1. Trong trường hợp này với min(x1) và max(x1) được cho trong (20). Nếu và thì và song song với nhau , do đó 2 tam giác đồng phẳng. Xét các trục : Cho (i0,i1,i2) và (j0,j1,j2) là các hoán vị của (0,1,2) trong tập {(0,1,2),(1,0,2),(2,1,0)}. Các hàm được định nghĩa trong phần phát hiện va chạm giữa OBB và tam giác. Nhân vô hướng phương trình (19) với ta được: Sau khi rút gọn phương trình trên ta được: (27) Chiếu các đỉnh của tam giác thứ nhất lên trục này ta được 2 giá trị p phân biệt là: p0 = 0 Chiếu các đỉnh của tam giác thứ 2 lên trục này ta được 2 giá trị q phân biệt là: Có 4 trường hợp xảy ra tuỳ thuộc vào hình chiếu có giá trị lớn nhất hoặc nhỏ nhất. Trong mỗi trường hợp ta sẽ đưa ra giải pháp để tìm được điểm va chạm duy nhất. Nhân vô hướng phương trình (19) với và ta được: (28) Trường hợp 1: min(q)=q0 và max(p)=0 với hoặc max (q)=q0 và min(p)=0 với Như vậy: Phương trình (27) tương đương với phương trình sau: Nếu và thì ta phải có: Phương trình (28) sẽ cho nghiệm duy nhất x0,x1,y0 và y1. Trường hợp 2: min(q)=q0 và với hoặc max(q)=q0 và với Như vậy: và Phương trình (27) tương đương với phương trình sau: Nếu và thì ta phải có: Với điều kiện như trên thì phương trình (28) sẽ cho nghiệm duy nhất x0, x1, y0 và y1. Trường hợp 3: và max(p) = 0 với hoặc và min(p) = 0 với Như vậy: Phương trình (27) tương đương với phương trình sau: Nếu và thì : Với điều kiện như trên thì phương trình (28) sẽ cho duy nhất nghiệm x0, x1, y0 và y1. Trường hợp 4: và với hoặc max(q) = và với Như vậy: Phương trình (27) tương đương với phương trình sau: Nếu và thì : Với điều kiện như trên thì phương trình (28) sẽ cho nghiệm duy nhất x0, x1, y0 và y1. Bảng sau sẽ tổng kết các hệ số trong các trường hợp để cho ra điểm va chạm duy nhất: Bảng 7: Các hệ số cho ra điểm giao duy nhất giữa 2 Tam giác Chương 3: PHẦN THỰC NGHIỆM Phần thực nghiệm mô phỏng một tình huống trong thực tế đó là va chạm giữa 2 ôtô. 1.Bài toán : Tình huống được đặt ra là có 2 ôtô đang chuyển động trên 2 xa lộ vuông góc với nhau, hợp với nhau một góc 90o. Xe thứ nhất phóng với tốc độ cao và xe thứ 2 phóng với tốc độ trung bình. Khi đến đoạn đường giao nhau do xe 1 không giảm tốc độ nên đã đâm vào xe 2. Phần thực nghiệm sẽ phát hiện (cài đặt) được va chạm và xử lý hậu va chạm để mô phỏng được tình huống đã đặt ra ở trên. 2. Hướng giải quyết Ta sẽ sử dụng hộp bao OBB để bao lấy mỗi xe và xử lý trên các hộp bao OBB này. Ta sẽ chiếu hộp bao này lên mặt phẳng chính là mặt đường và việc phát hiện sự va chạm giữa 2 ôtô chính là phát việc phát hiện giao nhau giữa 2 hình chiếu này. Ta chưa cần chiếu lên pháp tuyến của mặt đường vì trong quá trình chuyển động, 2 ôtô luôn luôn chuyển động trên cùng một mặt phẳng (chính là mặt đường). Việc xử lý hậu va chạm: dùng các định luật 2 và 3 của Newton, phương trình Euler và định lý về momen. Các lực tác dụng lên các vị trí khác nhau của ôtô thì sẽ gây ra tình huống va chạm (hay kết quả) khác nhau. Dưới đây là một số khung cảnh của vụ va chạm và tình huống va chạm được xử lý… KẾT LUẬN Sau một thời gian tìm hiểu, nghiên cứu về việc phát hiện và xử lý va chạm trong thực tế để mô phỏng vào máy tính, tôi thấy rằng đây là một lĩnh vực rất khó nhưng nếu được quan tâm, phát triển nó sẽ giải quyết được rất nhiều vấn đề của thực tiễn và khoa học. Việc nghiên cứu các vấn đề về phát hiện va chạm trên thế giới hiện nay đã tiến được một bước xa và đã thu được rất nhiều thành tựu vô cùng khả quan. Ở Việt Nam hiện nay vấn đề này còn rất mới mẻ nhưng dần dần đã được sự quan tâm, phát triển nhằm mở ra một hướng giải quyết vấn đề mới cho xã hội . Trong khoá luận, tôi đã tìm hiểu và trình bày tổng quan về va chạm, về các vấn đề phát hiện va chạm trong thực tế và mô phỏng chúng vào trong máy tính bao gồm : các khái niệm cơ bản liên quan đến va chạm và ứng dụng của nó, các phương pháp phát hiện va chạm giữa các đối tượng. Khoá luận cũng mô phỏng va chạm ôtô trong thực tế. Tuy nhiên do sự hạn chế về thời gian, trí tuệ cũng như các tài liệu, do đó các khái niệm, các vấn đề mà tôi đưa ra có thể chưa chính xác, đầy đủ và chưa phản ánh được đầy đủ về toàn bộ vấn đề mà bạn mong muốn. Chương trình còn đơn giản, chưa phản ánh hết được những vấn đề của việc nghiên cứu phát hiện va chạm mô phỏng vào máy tính. Vì vậy rất mong sự lượng thứ và đóng góp ý kiến của mọi người. TÀI LIỆU THAM KHẢO: David Eberly - Geometric Tools, Inc. Copyright c 1998-2005. All Rights. Flipcode Image Of The Day (IOTD) on 06 September 2006. Marco Monster, November, 2003. Stefan Gottschalk, Ming Lin, and Dinesh Manocha, OBBTree: A Hierarchical Structure for Rapid Interference Detection, In Proceedings of ACM Siggraph, pp. 171–180, 2005. Tomas Moller, A Fast Triangle–Triangle Intersection Test, Journal of Graphics Tools, vol. 2, no. 2, pp. 25–30, 2004. W.H. Press, B.P. Flannery, S.A. Teukolsky, and W.T. Vetterling, Numerical Recipes in C: The Art of Scientific Computing, Cambridge University Press, Cambridge, England, 2004.