Phát hiện va chạm tam giác đến tam giác trong 3D

Question

Tôi hiểu tam giác để phát hiện va chạm tam giác betwheen 2 hình tam giác. Ai đó có thể giải thích làm thế nào tôi có thể sử dụng điều này với một đối tượng 3D được tạo thành từ 1000 đỉnh? Làm cách nào để tạo danh sách hình tam giác cho mỗi Lưới? Tôi có phải thực hiện mọi hoán vị đỉnh không? Điều đó sẽ dẫn đến O (n^3) mà tôi thấy rất tệ.

Tôi có thể khái quát hóa điều này bằng cách nào?

Tôi sẽ yêu cầu đọc dữ liệu từ một định dạng. Nếu mọi thứ khác thất bại, ai đó có thể đề xuất một định dạng mà làm cho lưới từ hình tam giác? Tôi cũng sẽ cần một danh mục các Lưới cho định dạng, ít nhất là cho người mới bắt đầu.

Cảm ơn rất nhiều.

Answer 1

http://en.wikipedia.org/wiki/Binary_space_partitioning

Một cây BSP là một cách rất hiệu quả của kiểm tra va chạm của mắt lưới tĩnh, nhưng nó đòi hỏi một số tiền xử lý của lưới để đảm bảo không tam giác giao nhau. Nó hoạt động bằng cách phân vùng lưới thành nửa không gian. Điều này làm cho việc kiểm tra va chạm và vật lý dễ dàng hơn.

EDIT:

Tôi cảm thấy như thể tôi cũng nên đề cập đến Octree. Ý tưởng chung giống như cây BSP nhưng nó phân vùng mô hình thành các hình khối đệ quy nhỏ hơn thay vì một nửa không gian.

http://en.wikipedia.org/wiki/Octree

Trong câu trả lời cho câu hỏi thứ hai của bạn, giống như định dạng file .obj có thể là những gì bạn đang tìm kiếm.

http://en.wikipedia.org/wiki/Wavefront_.obj_file

Answer 2

Có rất nhiều tối ưu, bạn có thể áp dụng đối với va chạm phát hiện giữa mắt lưới:

• Space phân vùng, như mô tả của James.

• Từ chối sớm sử dụng bounding volumes. Ví dụ, va chạm sphere sphere là giá rẻ, vì vậy trước khi kiểm tra xem mắt lưới A và B va chạm, bạn có thể thấy nếu một quả cầu xung quanh A va chạm với một quả cầu bao quanh B. Nếu các quả cầu bỏ lỡ, rõ ràng là các mắt lưới không thể va chạm, cần phải kiểm tra chúng. Các loại đối tượng khác nhau có thể cần các loại khối lượng giới hạn khác nhau: hình khối và hình trụ được căn chỉnh trục là phổ biến.

• Caching nhân chứng. Trong một số thử nghiệm va chạm, bạn sẽ kết thúc tính toán một "nhân chứng" đối với vụ va chạm, ví dụ khi bạn áp dụng các separating axis test bạn tính toán một trục tách. Nếu trục tách hai đối tượng tại thời điểm t, có khả năng nó tiếp tục tách chúng tại thời điểm t + δ, vì vậy nó có thể trả tiền cho bộ nhớ cache mà bạn tìm thấy và thử nó lần đầu tiên (xem Thỏz, "Nhanh" Phát hiện va chạm của Moving Polyphedra lồi "trong Đồ họa Gems IV).