Phát hiện va chạm giữa các quả cầu tăng tốc

Question

Tôi đang viết một công cụ mô phỏng/vật lý kết hợp chuyến bay không gian 3D, lực hấp dẫn hành tinh/sao, lực đẩy tàu và các hiệu ứng tương đối. Cho đến nay, nó sẽ rất tốt, tuy nhiên, một điều mà tôi cần giúp đỡ là toán học của thuật toán phát hiện va chạm.

Mô phỏng lặp đi lặp lại của phong trào mà tôi đang sử dụng về cơ bản là như sau:

(Lưu ý:. 3D Vectors là ALL CAPS)

For each obj 

    obj.ACC = Sum(all acceleration influences) 

    obj.POS = obj.POS + (obj.VEL * dT) + (obj.ACC * dT^2)/2  (*EQ.2*) 

    obj.VEL = obj.VEL + (obj.ACC * dT) 

Next 

đâu:

obj.ACC is the acceleration vector of the object 
obj.POS is the position or location vector of the object 
obj.VEL is the velocity vector of the object 

obj.Radius is the radius (scalar) of the object 

dT is the time delta or increment 

Những gì tôi về cơ bản cần làm là tìm một số công thức hiệu quả có nguồn gốc từ (EQ.2) ở trên cho hai đối tượng (obj1, obj2) và cho biết liệu chúng có bao giờ va chạm, nếu có, vào thời điểm nào. Tôi cần thời gian chính xác để tôi có thể xác định xem nó có tăng thời gian cụ thể không (bởi vì accelleratons sẽ khác nhau ở các khoảng thời gian khác nhau) và để tôi có thể xác định vị trí chính xác (mà tôi biết cách làm, thời gian)

Đối với động cơ này, tôi đang mô hình hóa tất cả các đối tượng như hình cầu, tất cả điều này công thức/algortithim cần làm là phải tìm ra những gì chỉ:

(obj1.POS - obj2.POS).Distance = (obj1.Radius + obj2.Radius) 

nơi .Distance là một giá trị vô hướng tích cực. (Bạn cũng có thể vuông cả hai mặt nếu điều này dễ dàng hơn, để tránh hàm căn bậc hai ẩn trong tính toán .Distance).

(vâng, tôi biết nhiều, nhiều câu hỏi phát hiện va chạm khác, tuy nhiên, giải pháp của chúng dường như rất cụ thể đối với động cơ và giả định của chúng, và dường như không phù hợp với điều kiện của tôi: 3D, hình cầu và gia tốc . trong gia số mô phỏng Hãy cho tôi biết nếu tôi sai)

---

Một số Làm rõ:.

1) Nó không phải là đủ cho tôi để kiểm tra * Intersection * của hai quả cầu trước và sau khi tăng thời gian. Trong nhiều trường hợp vận tốc và thay đổi vị trí của chúng sẽ vượt xa bán kính của chúng.

2) RE: hiệu quả, tôi không cần trợ giúp (vào thời điểm này) để xác định khả năng ứng cử viên cho các vụ va chạm, tôi nghĩ rằng tôi có bảo hiểm.

---

Một làm rõ, mà dường như được mọc lên rất nhiều:

3) Phương trình của tôi (EQ.2) của phong trào gia tăng là một phương trình bậc hai mà áp dụng cho cả Velocity và Acceleration:

obj.POS = obj.POS + (obj.VEL * dT) + (obj.ACC * dT^2)/2 

các công cụ vật lý mà tôi đã nhìn thấy, (và chắc chắn mỗi công cụ trò chơi mà tôi từng nghe nói về) chỉ tuyến tính phương trình của phong trào gia tăng áp dụng chỉ Velocity:

obj.POS = obj.POS + (obj.VEL * dT) 

Đây là lý do tại sao tôi không thể sử dụng các giải pháp thường được công bố để phát hiện va chạm phát hiện trên stack Tràn, trên Wikipedia và trên toàn bộ Web, chẳng hạn như tìm giao lộ/cách tiếp cận gần nhất của hai đoạn đường. Mô phỏng của tôi giao dịch với các gia tốc biến đổi là nền tảng cho kết quả, vì vậy cái tôi cần là giao lộ/phương pháp gần nhất của hai phân đoạn parabol.

Answer 1

Trên trang web AShelley được gọi, phương pháp Tiếp cận điểm gần nhất được phát triển cho trường hợp hai đối tượng di chuyển với vận tốc không đổi. Tuy nhiên, tôi tin rằng phương pháp tính toán vectơ giống nhau có thể được sử dụng để lấy kết quả trong trường hợp hai đối tượng đều di chuyển với gia tốc không đều không đổi (phụ thuộc thời gian bậc hai).

Trong trường hợp này, đạo hàm thời gian của hàm bình phương khoảng cách là thứ tự thứ 3 (khối) thay vì thứ tự đầu tiên. Do đó sẽ có 3 giải pháp cho Thời gian tiếp cận gần nhất, điều này không đáng ngạc nhiên vì đường dẫn của cả hai đối tượng bị cong nên có thể có nhiều giao lộ. Đối với ứng dụng này, có thể bạn sẽ muốn sử dụng giá trị sớm nhất của t trong khoảng thời gian được xác định bởi bước mô phỏng hiện tại (nếu có thời gian như vậy).

tôi làm việc ra các phương trình đạo hàm mà nên cung cấp cho các lần tiếp xúc gần nhất:

0 = |D_ACC|^2 * t^3 + 3 * dot(D_ACC, D_VEL) * t^2 + 2 * [ |D_VEL|^2 + dot(D_POS, D_ACC) ] * t + 2 * dot(D_POS, D_VEL)

nơi:

D_ACC = ob1.ACC-obj2.ACC

D_VEL = ob1.VEL-obj2.VEL (trước khi cập nhật)

D_POS = ob1.POS-obj2.POS (cũng trước khi cập nhật)

và dot(A, B) = A.x*B.x + A.y*B.y + A.z*B.z

(Lưu ý rằng bình phương của cường độ |A|^2 có thể được tính bằng dot(A, A))

Để giải quyết điều này cho t, có thể bạn sẽ cần phải sử dụng công thức giống như những người found on Wikipedia.

Tất nhiên, điều này sẽ chỉ cho bạn thời điểm cách tiếp cận gần nhất. Bạn sẽ cần phải kiểm tra khoảng cách tại thời điểm này (sử dụng một cái gì đó như phương trình 2). Nếu nó lớn hơn (obj1.Radius + obj2.Radius), nó có thể được bỏ qua (tức là không có va chạm). Tuy nhiên, nếu khoảng cách ít hơn, điều đó có nghĩa là các quả cầu va chạm trước thời điểm này. Sau đó, bạn có thể sử dụng tìm kiếm lặp lại để kiểm tra khoảng cách vào các thời điểm trước đó. Nó cũng có thể có thể đưa ra một dẫn xuất khác (thậm chí phức tạp hơn) có kích thước trong tài khoản, hoặc có thể tìm thấy một số giải pháp phân tích khác, mà không cần phải giải quyết lặp đi lặp lại.

Chỉnh sửa: vì thứ tự cao hơn, một số giải pháp cho phương trình thực sự là khoảnh khắc của tách xa nhất. Tôi tin rằng trong mọi trường hợp, 1 trong 3 giải pháp hoặc 2 trong số 3 giải pháp sẽ là thời gian tách biệt xa nhất. Bạn có thể kiểm tra phân tích cho dù bạn đang ở một phút hoặc một tối đa bằng cách đánh giá đạo hàm thứ hai liên quan đến thời gian (tại các giá trị của t mà bạn tìm thấy bằng cách thiết lập phái sinh đầu tiên zero):

D''(t) = 3 * |D_ACC|^2 * t^2 + 6 * dot(D_ACC, D_VEL) * t + 2 * [ |D_VEL|^2 + dot(D_POS, D_ACC) ]

Nếu đạo hàm thứ hai đánh giá một số dương, thì bạn biết khoảng cách ở mức tối thiểu, không phải là cực đại, cho thời gian đã cho t.

Answer 2

Có vẻ như bạn muốn số Closest Point of Approach (CPA). Nếu nó nhỏ hơn tổng của bán kính, bạn có va chạm. Có mã ví dụ trong liên kết. Bạn có thể tính toán từng khung hình với tốc độ hiện tại và kiểm tra xem thời gian CPA có nhỏ hơn kích thước của bạn hay không. Bạn thậm chí có thể nhớ cache thời gian cpa, và chỉ cập nhật khi tăng tốc được áp dụng cho một trong hai mục.

Answer 3

Vẽ một đường thẳng giữa vị trí bắt đầu và vị trí kết thúc của mỗi hình cầu. Nếu các đoạn thẳng kết quả giao nhau với các quả cầu chắc chắn va chạm ở một số điểm và một số toán học thông minh có thể tìm thấy vào thời điểm xảy ra va chạm. Ngoài ra, hãy đảm bảo kiểm tra xem khoảng cách tối thiểu giữa các đoạn (nếu chúng không giao nhau) có nhỏ hơn 2 * bán kính hay không. Điều này cũng sẽ chỉ ra một vụ va chạm.

Từ đó bạn có thể lùi thời gian delta của bạn để xảy ra chính xác khi va chạm để bạn có thể tính toán chính xác lực.

Bạn đã cân nhắc sử dụng thư viện vật lý đã thực hiện công việc này chưa? Nhiều thư viện sử dụng các hệ thống tiên tiến hơn và ổn định hơn (tích hợp tốt hơn) để giải quyết các hệ phương trình mà bạn đang làm việc. Bullet Physics xuất hiện trong đầu bạn.