Luận văn Nghiên cứu một số vấn đề về động lực học chất rắn trong xử lý va chạm

như hình cầu, hình trụ, hình hộp, mặt phẳng, đường cong,…Từ các đối tượng nguyên thuỷ này ta sử dụng các thao tác như dịch chuyển, xoay, co giãn cùng với các kỹ thuật chỉnh sửa như cắt xén, mở rộng, thêm bớt … để tạo nên đối tượng mong muốn trong thế giới thực. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 12 Các đối tượng sau đó sẽ được bổ sung thêm xương (nếu có), tính chất bề mặt (như màu sắc, da, tóc, mắt …) và được tạo các chuyển động mô phỏng một cách sinh động các thể hiện của đối tượng trong thế giới thực. Khi làm việc với các phần mềm ta sẽ thao tác trên 4 khung nhìn khác nhau của đối tượng, 4 khung nhìn này sẽ cho ta nhìn được đối tượng đồng thời ở các góc độ khác nhau. - Các công cụ lập trình: Công cụ lập trình trong các ứng dụng Thực tại ảo thường là các thư viện đồ hoạ 3D được xây dựng sẵn, miễn phí như DirectX, OpenGL, OpenSG, OpenSceneGraph. Trước đây, chúng ta hay sử dụng các thư viện OpenGL và DirectX, nhưng do mức độ hỗ trợ người lập trình trong các thư viện đó chưa cao nên người ta đã mở rộng chúng thành OpenSG, OpenSceneGraph. Hai thư viện lập trình OpenSG, OpenSceneGraph được xây dựng trên nền tảng OpenGL và đưa vào khái niệm rất mới đó là “Đồ thị ngữ cảnh” – Scene Graphs. Theo đó, mỗi đối tượng được biễu diễn như là một cây ngữ cảnh, mỗi nút Hình 1.7 Các khung nhìn khác nhau trong phần mềm Maya Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 13 có một nhân (core), nhân của mỗi nút có thể là một đối tượng geometry, đối tượng transform, ánh sáng (light)...Việc Render một đối tượng xuất phát từ nút gốc, đi đến từng nút lá và thực hiện các hành động tương ứng trong quá trình duyệt cây. Trong OpenSG hỗ trợ các hàm và các đối tượng đồ hoạ cơ sở như Light, Geometry, Transform, Material, Windows, Viewport,... ngoài nó còn hỗ trợ cơ chế đa luồng, lập trình hiển thị stereo. Để sử dụng được thư viện OpenSG, bạn cần dùng bộ biên dịch FrameNet, thông thường OpenSG hay dùng với ngôn ngữ lập trình Visual C.Net. Để biết thêm về thư viện đồ hoạ OpenSG, bạn có thể tìm hiểu và download miễn phí OpenSG tại địa chỉ: 1.2. Động lượng vật rắn trong thực tại ảo: 1.2.1. Va chạm là gì? Trong ngôn ngữ hàng ngày va chạm xảy ra khi một vật va vào một vật khác, các vật va chạm có thể là những quả bi a, một cái búa và cái đinh, một quả bóng chày và chày đập bóng, và quá trình thường xuyên nũa là giữa các ô tô… Vậy, va chạm là một sự kiện riêng lẻ trong đó một lực tương đối mạnh tác dụng vào từng vật, trong hai hoặc hơn hai vật va chạm, trong một thời gian tương đối ngắn. Ngoài ra, có thể nêu sự rõ ràng giữa các thời gian trước, trong và sau va chạm. Trước Đang Sau Hình 1.8. Sơ đồ động trình bày một hệ có va chạm đang xảy ra Biên giới của hệ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 14 Đường biên của hệ, bao quanh các vật trong các hình ấy cho ta biết rằng trong một va chạm lý tưởng, chỉ có các nội lực (giữa các vật) là có tác dụng. Khi một cây vợt đập vào quả bóng thì lúc bắt đầu và lúc kết thúc thực sự va chạm có thể xác định được chính xác thời gian tiếp xúc vợt – bóng (chừng 4ms) là ngắn so với thời gian mà bóng bay tới vợt và từ vợt bay đi. Hình 1.9 cho thấy lực tác dụng vào bóng là đủ lớn làm cho bóng bị biến dạng tạm thời. Trong va chạm giữa nắm đấm và bao cát thì thời gian lâu và dài hơn, ta trông thấy rõ sự biến dạng trên bao cát, và bằng cảm giác chồn của nắm tay và cánh tay dưới. Định nghĩa chính thức của ta về va chạm không đòi hỏi sự phá vỡ không chính thức của ta. Khi một trạm thám sát đến gần một hành tinh lớn, quay quanh nó và rồi lại tiếp tục hành trình của nó với một tốc độ tăng thêm (cuộc chạm chán kiểu ná cao su) thì đây cũng là một va chạm. Trạm thám sát và hành tinh không thực sự “chạm vào nhau” nhưng, va chạm không đòi hỏi phải có tiếp xúc và một lực va chạm không cần phải là một lực tiếp xúc, nó có thể đơn thuần là một lực hấp dẫn. Trong vật lý có nhiều kiểu va chạm: như va chạm đàn hồi một chiều, va chạm không đàn hồi một chiều (trong bài toán va chạm một chiều), va chạm hai chiều. Hình 1.9 Bóng va chạm với vợt Nắm đấm bị núm vào bao cát Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 15 1.2.2. Động lượng là gì? Động lượng là một từ có nhiều nghĩa trong ngôn ngữ hàng ngày, nhưng chỉ có một nghĩa chính xác trong vật lý, động lượng (p) là một vectơ và được xác định bởi khối lượng (m) và vận tốc (v), thông thường người ta bỏ đi chữ tuyến tính và nó được dùng để phân biệt với động lượng góc, do m là một đại lượng vô hướng, dương nên p và v có cùng hướng. 1.2.3. Mối liên quan giữa động lượng và va chạm Trên thực tế động lượng có ảnh hưởng trực tiếp tới chuyển động của vật, bởi lẽ khi một vật chuyển động thì nó liên quan tới hai yếu tố đó là khối lượng và vận tốc mà khối lượng và vận tốc lại chính là động lượng. Một vật đang chuyển động, hay đứng yên khi xảy ra va chạm thì đều làm cho động lượng của chúng thay đổi. Sự thay đổi này còn phụ thuộc vào khối lượng của vật và các vật trong một hệ vật. Khi xảy ra va chạm thì độ biến thiên động lượng của vật hoặc hệ vật lại phụ thuộc vào xung lượng của lực tác dụng, ca hai vectơ này có cùng đơn vị và cùng thứ nguyên. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 16 Chương 2: MỘT SÔ VẤN ĐỀ VỀ ĐỘNG LƯỢNG HỌC CHẤT RẮN 2.1. Tính toán va chạm Phát hiện va chạm là một trong những vấn đề trọng tâm của mỗi hệ thống thực tại ảo. Các đối tượng trong các hệ thống thực tại ảo có những chuyển động riêng của nó. Trong khi chuyển động đối tượng có thể va chạm với đối tượng khác, hoặc có thể va chạm với môi trường, chướng ngại vật,... Do vậy, mỗi hệ thống thực tại ảo đều phải có khả năng phát hiện khi nào thì có va chạm xảy ra và có những đối tượng nào tham gia trong lần va chạm để có những xử lý hậu va chạm thích hợp. Trong luận văn này, tôi xem xét các đối tượng trong không gian ba chiều nên khi nói đến va chạm có nghĩa là va chạm trong không gian ba chiều. Một cách đơn giản nhất để phát hiện va chạm giữa hai đối tượng đó là kiểm tra từng mặt của đối tượng này có cắt một mặt nào đó của đối tượng kia, cách này có ưu điểm là cho ta chính xác điểm va chạm. Tuy nhiên vì mỗi đối tượng 3D được tạo thành từ rất nhiều các mặt (thông thường là các tam giác) cho nên chi phí để kiểm tra giao nhau của từng cặp mặt như vậy là rất tốn kém về mặt thời gian, nhất là ta luôn phải đảm bảo tính thời gian thực trong các hệ thống thực tại ảo. Do vậy, hầu hết các hệ thống thực tại ảo đều sử dụng phương pháp gần đúng để phát hiện va chạm, phương pháp gần đúng hay được sử dụng đó là phương pháp dùng các hình bao quanh đối tượng [13]. Với mỗi đối tượng, ta tìm một hình bao “thích hợp” quanh nó, việc phát hiện va chạm bây giờ được đưa về bài toán phát hiện va chạm giữa các hình bao. Việc sử dụng hình bao gì cho đối tượng là tuỳ thuộc vào từng hệ thống, để giảm độ phức tạp khi tính toán thì người ta hay sử dụng các hình bao là các hình elipsoid, hình hộp, hoặc là hình cầu... Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 17 Đối với phương pháp phát hiện va chạm theo các hộp bao thì ta lại có hai kỹ thuật khác nhau đó là sử dụng hộp bao có các cạnh song song với các trục toạ độ (Axis-Aligned Bounding Boxes - AABBs) hoặc là hộp bao theo hướng của đối tượng (Oriented Bounding Boxes - OBBs). Việc phát hiện va chạm giữa các hộp bao AABBs được thực hiện nhanh chóng nhưng sai số lớn, trong khi đó phát hiện va chạm giữa các hộp bao OBBs tuy phức tạp hơn nhưng cho sai số nhỏ hơn nhiều. 2.1.1. Kĩ thuật phát hiện va chạm dựa vào hộp bao AABB 2.1.1.1. Định nghĩa hộp bao AABB 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ình 2.1). Hình 2.1 Hộp bao AABB của đối tượng Hộp bao AABB bao gồm một tâm C, ba hệ số a0, a1, a2 tương ứng là độ dài theo ba trục toạ độ của hình hộp. 2.1.1.2. Phát hiện va chạm giữa hai AABB Cho hai hộp bao AABB xác định bởi [C1, a0, a1, a2] và [C2, b0, b1, b2] với giả sử ai>0, bj>0, i,j = 0,1,2. Để kiểm tra va chạm, chúng ta xác định toạ độ cao nhất và thấp nhất của mỗi hộp bao. Kí hiệu (xmin1, ymin1, zmin1), (xmax1, ymax1, zmax1) là toạ độ thấp nhất và cao nhất của hộp bao có tâm C1: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 18 2 , 2 2 , 2 2 , 2 0 01max 0 01min 0 01max 0 01min 0 01max 0 01min c Cz c Cz b Cy b Cy a Cx a Cx    Tương tự, ta tính được (xmin2, ymin2, zmin2), (xmax2, ymax2, zmax2) là toạ độ thấp nhất và cao nhất của hộp bao xác định bởi tâm C2. Hai hộp bao AABB va chạm nhau nếu xảy ra một trong bốn điều kiện sau:  (xmin1, ymin1, zmin1)  [(xmin2, ymin2, zmin2), (xmax2, ymax2, zmax2)]  (xmax1, ymax1, zmax1) [(xmin2, ymin2, zmin2), (xmax2, ymax2, zmax2)]  (xmin2, ymin2, zmin2)  [(xmin2, ymin2, zmin2), (xmax2, ymax2, zmax2)]  (xmax2, ymax2, zmax2)  [(xmin2, ymin2, zmin2), (xmax2, ymax2, zmax2)] Để tìm điểm va chạm, chúng ta có chọn điểm va chạm là đỉnh tương ứng với một trong bốn trường hợp trên. 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 AABB 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. Thực tế trong các hệ thống thực tại ảo, người ta chỉ sử dụng kĩ thuật hộp bao AABB để giới hạn vùng va chạm, sau đó để kiểm tra và tìm điểm va chạm chính xác hơn, người ta sẽ sử dụng kĩ thuật hộp bao theo hướng OBB sẽ được trình bày trong phần tiếp theo. 2.1.2. Kỹ thuật hộp bao theo hướng (Oriented Bounding Boxes) 2.1.2.1. Định nghĩa hộp bao theo hướng (OBB) 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, mặc dù vậy người Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 19 ta vẫn dùng loại hộp bao này nhiều hơn vì nó cho độ chính xác cao hơn nhiều so với hộp bao AABB (Hình 2.2). Hình 2.2 Hộp bao OBB của đối tượng Một hình hộp OBB bao gồm một tâm C, ba vector 210 ,, AAA  chỉ hướng của hình hộp và 3 hệ số độ dài tương ứng với kích thước của hình hộp là a0 >0, a1>0, a2>0. Khi đó, 8 đỉnh của hình hộp sẽ được xác định như sau:    2 0 .2,1,0,1||* i iiii isAasC  Kỹ thuật phát hiện hộp bao theo hướng được chia làm hai mức [6]. Mức một là kiểm tra “nhanh” xem có va chạm nào xảy ra không? Nếu không có va chạm nào xảy ra thì hệ thống vẫn làm việc bình thường, ngược lại nếu ở mức một phát hiện có ít nhất một va chạm xảy ra thì sẽ chuyển sang mức hai đó là tìm chính xác điểm va chạm. Ở mức một, ta có thể kiểm tra nhanh xem có va chạm nào xảy ra không nhờ dựa vào định lý sau đây. Định lý 2.3.1 Hai khối đa diện lồi không giao nhau nếu có thể cô lập được chúng bằng một mặt phẳng P thoả mãn một trong hai điều kiện sau:  P song song với một mặt nào đó của một trong hai khối đa diện.  Hoặc là P chứa một cạnh thuộc đa diện thứ nhất và một đỉnh thuộc đa diện thứ hai. Từ định lý trên, ta rút ra nhận xét sau cho phép kiểm tra nhanh sự giao nhau của hai khối đa diện lồi: Điều kiện cần và đủ để kiểm tra hai khối đa diện lồi có giao nhau hay không là kiểm tra giao nhau giữa các hình chiếu của chúng lên đường Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 20 thẳng vuông góc với mặt phẳng P ở trên, đường thẳng này được gọi là trục cô lập. Ta thấy rằng các hộp bao OBBs là những khối đa diện lồi, bởi vậy ta hoàn toàn có thể áp dụng định lý trên để kiểm tra va chạm giữa chúng. 2.1.2.2. Kiểm tra nhanh va chạm giữa hai hộp bao OBBs Cho hai hình bao OBBs xác định bởi các thông số [C0,A0,A1,A2,a0,a1,a2] và [C1,B0,B1,B2,b0,b1,b2]. Ta thấy rằng các tình huống mà hai OBBs tiếp xúc với nhau (không cắt nhau) chỉ có thể là một trong 6 trường hợp sau đây: mặt - mặt, mặt - cạnh, mặt - đỉnh, cạnh - cạnh, cạnh - đỉnh, đỉnh - đỉnh. Do vậy, tập ứng cử viên các trục cô lập chỉ tối đa là 15 trục sau:  3 trục chỉ hướng của hộp bao thứ nhất ( iA  )  3 trục chỉ hướng của hộp bao thứ hai ( jB  )  9 trục tạo bởi tích có hướng của một trục thuộc hộp bao thứ nhất và một trục thuộc hộp bao thứ hai ( ji BA   ). Mặt khác, ta biết rằng nếu một trục là trục cô lập thì khi tịnh tiến đến vị trí nào, nó vẫn là trục cô lập. Bởi vậy, không mất tính tổng quát ta sẽ gọi trục cô lập có vector chỉ phương là V và đi qua tâm C0 của hộp bao thứ nhất, do vậy nó có phương trình như sau: d = 0C  + t*V Trong đó, t là tham số. V có thể là ji BA  , hoặc ji BA   với i, j = 0,1,2. Gọi P là một điểm bất kỳ, hình chiếu của P lên đường thẳng d với gốc C0 sẽ là đoạn thẳng C0H xác định như sau (hình 2.3). || *)( ),( 0 V VCP dPhc     d C0 P H Hình 2.3 Hình chiếu của P lên đường thẳng d Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 21 Như vậy, khi chiếu 8 đỉnh của hộp bao thứ nhất lên trục cô lập d với gốc C0 thì sẽ thu được 4 cặp đoạn thẳng có độ dài bằng nhau nằm về hai phía so với C0 (hình 2.4), độ dài của mỗi đoạn thẳng được xác định như sau : | || *)**( |),**( 2 0 2 0 0 V VAas dAasChc i iii i iii         (2.1) Như vậy, khoảng cách nhỏ nhất chứa 8 đoạng thẳng (2.1) sẽ có tâm là C0 và bán kính r0 được xác định như sau : r0 = max { | || *)**( | 2 0 V VAas i iii     } Với mọi |si| = 1. Đặt R0 = r0* ||V  , ta có:  R0 = max{ | a0* VA  *0 + a1* VA  *1 + a2* VA  *2 | | a0* VA  *0 + a1* VA  *1 - a2* VA  *2 | | a0* VA  *0 - a1* VA  *1 + a2* VA  *2 | | a0* VA  *0 - a1* VA  *1 - a2* VA  *2 | Hình 2.4 Chiếu 8 đỉnh của hình hộp lên trục cô lập d Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 22 |-a0* VA  *0 + a1* VA  *1 + a2* VA  *2 | |-a0* VA  *0 + a1* VA  *1 - a2* VA  *2 | |-a0* VA  *0 - a1* VA  *1 + a2* VA  *2 | |-a0* VA  *0 - a1* VA  *1 - a2* VA  *2 | } = a0*| VA  *0 | + a1*| VA  *1 | + a2*| VA  *2 | Tương tự, ta xác định hình chiếu 8 đỉnh của hộp bao thứ hai lên d với gốc C0 như sau. | || *)**( | || * ),**( 2 0 2 0 1 V VBbs V DV dBbsChc i iii i iii           (2.2) Với 01 CCD   Chú ý rằng, 8 đoạn thẳng này được nhóm thành 4 cặp đối xứng nhau qua C1. Do vậy, khoảng cách nhỏ nhất chứa 8 đoạng thẳng (2.2) sẽ có tâm là C1 và bán kính R1 được xác định như sau : r1 = max { | || *)**( | 2 0 V VBbs i iii     } Với mọi |si| = 1. Đặt R1 = r1* ||V  , tương tự như trên ta suy ra : R1 = b0*| VB  *0 | + b1*| VB  *1 | + b2*| VB  *2 |. Hai khoảng cách trên sẽ không giao nhau nếu: C0C1 > r0+r1  ||V  *C0C1 > ||V  *r0 + ||V  *r1  R > R0 + R1 (2.3) Trong đó: R = C0C1* ||V  . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 23 Bây giờ ta sẽ giải cụ thể các phương trình trên. Với mỗi vector iB  ta có thể viết thành: 221100 AcAcAcB iiii   với i = 0,1,2. Đặt : A = (A0, A1, A2) và B= (B0, B1, B2)            222120 121110 020100 ccc ccc ccc C (2.4)  B = C*A  AT*B = C  C = 210 2 1 0 * BBB A A A =           221202 211101 201000 BABABA BABABA BABABA (2.5) Từ (2.4) và (2.5) suy ra: jiij BAc  * , hay cij chính là tích vô hướng của hai vector Ai, Bj. Mặt khác, từ B = C*A  A = C T *B  221100 BcBcBcA iiii   Như trong phần đầu đã nói, tập các trục cô lập ứng cử viên V  = { iA  , jB  , ji BA   }với i, j = 0,1,2. Để tính toán các hệ số R0, R1, R ở trên thì ta sẽ làm minh họa cho hai trường hợp V  = iA  và V = ji BA   , các trường hợp còn lại được tính toán tương tự. Hình 2.5 Kết quả chiếu 2 hình hộp lên trục cô lập d Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 24  Xét trường hợp V  = 0A  :  R0 = a0*| VA  *0 | + a1*| VA  *1 | + a2*| VA  *2 | = a0.  R1 = b0*| VB  *0 | + b1*| VB  *1 | + b2*| VB  *2 | = b0*|c00| + b1*|c01| + b2*|c02|.  R = 0A  *D  Xét trường hợp V  = 00 BA   :  R0 = a0*| 000 * BAA   | + a1*| 001 * BAA   | + a2*| 002 * BAA   | Mặt khác : V  = 00 BA   = )( 2201100000 AcAcAcA   = 120210 AcAc    R0 = a1*|c20| + a2*|c10|  R1 = b0*| VB  *0 | + b1*| VB  *1 | + b2*| VB  *2 |.  R = V  * D  = DAcAc  *)( 120210  Ta có viết lại V  dưới dạng: V  = 00 BA   = 0202101000 )( BBcBcBc   = - 10221 BcBc    VB  *0 = )(* 1022010 BcBcB   = 0 VB  *1 = )(* 1022011 BcBcB   = c02 VB  *2 = )(* 1022012 BcBcB   = -c01  R1 = b1*|c02|+ b2*|c01| Tiếp tục làm cho các trường hợp còn lại, ta xây dựng được bảng các giá trị cho R, R0, R1 như sau : Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 25 V  R0 R1 R 0A  a0 b0|c00|+b1|c01|+b2|c02| |.| 0 DA  1A  a1 b0|c10|+b1|c11|+b2|c12| |.| 1 DA  2A  a2 b0|c20|+b1|c21|+b2|c22| |.| 2 DA  0B  a0|c00|+a1|c10|+a2|c20| b0 |.| 0 DB  1B  a0|c01|+a1|c11|+a2|c21| b1 |.| 1 DB  2B  a0|c02|+a1|c12|+a2|c22| b2 |.| 2 DB  00 BA   a1|c20|+a2|c10| b1|c02|+b2|c01| DAcDAc  .... 120210  10 BA   a1|c21|+a2|c11| b0|c02|+b2|c00| DAcDAc  .... 121211  20 BA   a1|c22|+a2|c12| b0|c01|+b1|c00| DAcDAc  .... 122212  01 BA   a0|c20|+a2|c00| b1|c12|+b2|c11| DAcDAc  .... 200020  11 BA   a0|c21|+a2|c01| b0|c12|+b2|c10| DAcDAc  .... 201021  21 BA   a0|c22|+a2|c02| b0|c11|+b1|c10| DAcDAc  .... 202022  02 BA   a0|c10|+a1|c00| b1|c22|+b2|c21| DAcDAc  .... 010100  12 BA   a0|c11|+a1|c01| b0|c22|+b2|c20| DAcDAc  .... 011101  22 BA   a0|c12|+a1|c02| b0|c21|+b1|c20| DAcDAc  .... 012102  Bảng2.1 Bảng các giá trị R, R0, R1 được tính toán trước. 2.1.3. Tìm điểm va chạm Phát hiện va chạm trong mức thứ nhất chỉ trả lời được câu hỏi có hay không một va chạm xảy ra mà không đưa ra được chính xác điểm va chạm. Trong trường Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 26 hợp kết quả mức thứ nhất cho ta biết là có va chạm xảy ra thì ta phải chuyển sang mức hai để tìm chính xác điểm va chạm [9]. Trong các hệ thống thực tại ảo, phần lớn chúng ta chỉ quan tâm đến thời điểm đầu tiên mà các đối tượng va chạm nhau, nghĩa là thời điểm mà các đối tượng đó tiếp xúc nhau. Điều này cũng đúng trong thế giới thực, khi mà các đối tượng va chạm nhau thì hậu quả va chạm sẽ xảy ra ngay khi chúng vừa “chạm” vào nhau. Do vậy, chúng ta chỉ cần quan tâm đến thời điểm mà các đối tượng tiếp xúc nhau và điểm tiếp xúc đó (hình 2.6). Hình 2.6 Tìm điểm va cham khi hai đối tượng tiếp xúc nhau Đối với hai hộp bao, nếu chúng va chạm với nhau ở dạng đỉnh - đỉnh, đỉnh - cạnh, cạnh - cạnh, đỉnh - mặt thì điểm tiếp xúc là duy nhất. Nhưng nếu chúng va chạm với nhau ở dạng mặt - mặt, cạnh - mặt thì sẽ có vô số điểm tiếp xúc, khi đó chúng ta chỉ cần đưa ra một điểm bất kỳ là được. Ý tưởng để tìm thời điểm va chạm đầu tiên như sau. Mỗi khi ta thực hiện công việc kiểm tra nhanh va chạm ở mức thứ nhất, nếu tìm được một trục cô lập thì ta sẽ ghi lại nhãn thời gian cho trục cô lập đó. Nếu không tìm được một trục cô lập nào thì có nghĩa là hai hộp bao đã va chạm với nhau, khi đó nhãn thời gian được gán cho trục cô lập ở lần kiểm tra liền trước sẽ là thời điểm đầu tiên mà hai hộp bao va chạm nhau, gọi T là nhãn thời gian đó. Khi đó, ta có thế coi như R = R0+R1(thời điểm hai hình hộp tiếp xúc nhau). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 27 Gọi P là điểm tiếp xúc của hai hộp bao thì suy ra tồn tại một vector x = {x0, x1, x2} và y = {y0, y1, y2} sao cho:    2 0 2 0 ** j jj i ii ByDAx  với |xi|  ai, |yj|  bj và i,j = 0,1,2. (2.6) Việc tìm điểm va chạm sẽ phụ thuộc vào trục cô lập V  ở thời điểm T là trục nào trong số 15 trục cô lập ứng cử viên. Ta xét 3 trường hợp sau.  V  là vector iA  : Nhân hai vế của (6) với iA  ta thu được: xi =    2 0 ** j jiji BAyDA  = Sign( DAi  * )*(R0+R1) +   2 0 * j ijj cy Đặt  = Sign( DAi  * )  xi = *(R0+R1) +   2 0 * j ijj cy . Thay các giá trị của R0, R1 trong bảng 1 ở trên ta được: xi = *(ai +   2 0 ||* j jij cb ) +   2 0 * j ijj cy Nhân cả hai vế với  ta được.  (ai-*xi) +   2 0 ||* j jij cb +   2 0 * j ijj cy = 0  (ai-*xi) + )*)(**(|| 2 0 jij j jij ycSignbc    = 0 (2.7) Ta thấy: (ai-*xi)  0 và )*)(*( jijj ycSignb   0       0*)(* 0* jijj i ycSignb xia   Nếu cij  0       .2,1,0*)(* * jbjcSigny ax ijj ii   Nếu cij = 0 (ứng với trường hợp cạnh va chạm mặt, mặt va chạm mặt). Khi đó, nhân hai vế của (2.6) với jB  ta được: yj = -    2 0 ** k kjkj cxDB  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 28 )max(||.||.)min( 2 0 2 0 j k kkjjj k kkjji yacDByacDBy     Mặt khác, vì |yj|  bj nên ta có: ],[)]max(),[min( jjjjj bbyyy  . Do vậy, ta chỉ cần chọn một giá trị yj thuộc đoạn trên.  V  là vector iB  : Tương tự như trường hợp trên, ta tính được. Nếu cji  0       .2,1,0*)(* * jacSignx by jjij ii   Nếu cji = 0, nhân hai vế của (6) với iA  ta có:    2 0 . k jkkjj cyDAx  Tương tự như trên, ta có: )max(||.||.)min( 2 0 2 0 j k kjkjj k kjkji xbcDAxbcDAx     Khi đó, chọn xj thuộc đoạn sau làm điểm tiếp xúc: ],[)]max(),[min( jjjjj aaxxx   V  là vector ji BA   : Để dễ trình bày, chúng ta sẽ làm minh hoạ cho một trường hợp V  = 00 BA   = 120210 AcAc   = 102201 BcBc   , các trường hợp khác sẽ được tính tương tự. Nhân hai vế (6) với 00 BA   ta được: x2*c10 - x1*c20 = DBA  *)( 00  + )(** 102201 2 0 BcBcBy j jj     x2*c10 - x1*c20 = DBA  *)( 00  + y1*c02 - y2*c01 (2.8) Chú ý rằng, theo hàng 7 trong bảng 1 thì : ||*||*||*||*|*)(||| 0120211022011000 cbcbcacaRRDBAR    } ||*||*||*||*{*)*)(( 01202110220100 cbcbcacaDBASignR   Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 29 Đặt )*)(( 00 DBASign   , ta có (8) tương đương với : x2*c10 - x1*c20 = *( ||*||*||*||* 012021102201 cbcbcaca  ) + y1*c02 - y2*c01 |c20|*(a1+*Sign(c20)*x1)+|c10|*(a2-*Sign(c10)*x2)+|c01|*(b2-*Sign(c01)*y2)+ |c02|*(b1+*Sign(c02)*y1) = 0 (2.9) Nhận thấy: Để tìm x0 và y0, nhân 2 vế của (2.6) với 0A  và 0B  :       00220110000 020210100000 **** **** yDBxcxcxc ycycycDAx   Giải hệ phương trình trên, cùng với các hệ số y1, y2, x1, x2 ở trên Ta tìm x0, y0.                 22011020210100002 00 0 20210122011000002 00 0 **)***(** 1 1 **)***(** 1 1 xcxcycycDAcDB c y ycycxcxcDBcDA c x   Đối với các trường hợp V  ={ 10 BA   , 20 BA   , 01 BA   , 11 BA   , 21 BA   , 02 BA   , 12 BA   , 22 BA   } cũng tính toán tương tự như trên để tìm điểm tiếp xúc. Cuối cùng ta có bảng tổng hợp về toạ độ của tiếp điểm trong mọi trường hợp sau: a1+*Sign(c20)*x1  0 a2-*Sign(c10)*x2  0 b2-*Sign(c01)*y2  0 b1+*Sign(c02)*y1  0 a1+*Sign(c20)*x1 = 0 a2-*Sign(c10)*x2 = 0 b2-*Sign(c01)*y2 = 0 b1+*Sign(c02)*y1 = 0 Từ (9) suy ra: x1 = -*Sign(c20)*a1 x2 = *Sign(c10)*a2 y1 = -*Sign(c02)*b1 y2 = *Sign(c01)*b2  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 30 V  Tiếp điểm iA  2,1,0)(  jbcSigny jijj  jB  2,1,0)(  iacSignx iiji  00 BA   ))(( 1 1 )(,)(,)(,)( 2021012201100002 00 0 2012102121021201 ycycxcxcDBcDA c x bcSignybcSignyacSignxacSignx       10 BA   ))(( 1 1 )(,)(,)(,)( 20200022111110102 01 0 2002002021121211 ycycxcxcDBcDA c x bcSignybcSignyacSignxacSignx       20 BA   ))(( 1 1 )(,)(,)(,)( 20100022211220202 02 0 1001001021221221 ycycxcxcDBcDA c x bcSignybcSignyacSignxacSignx     