Cách tìm đối tượng 3D có vừa với vật thể 3D khác không?

Question

Cho hai đối tượng 3D, làm thế nào tôi có thể tìm thấy nếu một trong những phù hợp với bên trong thứ hai (và tìm vị trí của đối tượng trong container).

Đối tượng phải được dịch và xoay để vừa với vùng chứa - nhưng không được sửa đổi theo cách khác.

biến chứng khác:

1. Tình hình tương tự - nhưng tìm kiếm các giải pháp phù hợp nhất, ngay cả khi nó không phải là một trận đấu thích hợp (giảm thiểu khối lượng của đối tượng không phù hợp trong container)

2. Hỗ trợ cho các đối tượng đàn hồi - tìm ra phù hợp nhất trong khi giảm thiểu sự "méo mó" trong các đối tượng

Đây là một câu hỏi khá chung - và tôi không mong đợi một giải pháp hoàn chỉnh. Bất kỳ con trỏ nào liên quan đến các giấy tờ \ articles \ thư viện \ công cụ sẽ hữu ích

Answer 1

Đây là phương pháp lý tưởng có lẽ ít hơn.

Bạn có thể thử sửa vị trí (trong không gian 3D) của 1 hình dạng. Đặt hình dạng khác lên trên hình dạng đó. Sau đó tạo liên kết kết nối một điểm trong hình dạng với một điểm trong hình dạng khác. Sau đó mô phỏng những gì xảy ra khi các liên kết được kéo chặt chẽ như nhau. Gây điểm không cố định để xoay và dịch cho đến khi nó ổn định.

Nếu phù hợp đủ lỏng, bạn chỉ có thể sử dụng 3 liên kết (số lượng tối thiểu liên kết tối thiểu cho 3D) và thử mọi kết hợp có thể. Tuy nhiên, để phù hợp chặt chẽ hơn, bạn sẽ cần nhiều liên kết hơn, có lẽ đủ để đặt chúng trên mọi điểm của hình dạng với số điểm ít nhất. Có nghĩa là bạn sẽ có một số phương pháp để xác định làm thế nào để đặt các liên kết, mà không phải là tầm thường.

Answer 2

Điều này có vẻ khá khó khăn. Cách tiếp cận có thể xảy ra là để có một số heuristic để đề xuất chuyển đổi và hơn kiểm tra là nó tốt nhất. Nếu phép biến đổi chỉ di chuyển đối tượng một chút ra khỏi bên trong (ví dụ như trên một phần) hơn là điều chỉnh một chút để chuyển đổi và kiểm tra nó. Nếu đối tượng là 'rất nhiều' (ví dụ: trên cùng một/tất cả trục trên cả hai mặt) hơn là đoán phỏng đoán mới.

Chỉ là một ý tưởng chung cho một heuristic. Tạo sự rasterisation của một đối tượng có cùng kích thước pixel. Nó có thể là octree của một khối lượng đối tượng. Tạo biểu đồ kết nối giữa các pixel. Kiểm tra tính đẳng hình đồ thị giữa các đồ thị. Nếu có một đồ thị con hơn vị trí đó là để thử nghiệm.

Phương pháp này cũng hỗ trợ xoay vòng 90 độ.

Một số thử nghiệm có thể được thực hiện ngay cả trên biểu đồ. Nếu tất cả các khối lượng hàng xóm của một đồ thị con đều có đồ thị lớn hơn đối tượng.

Nói chung đây là phương pháp tiếp cận hộp biên 'tinh'.

Answer 3

Một giải pháp khác là dự đoán số điểm bằng nhau trên cả hai đối tượng và làm một hình vuông nhỏ nhất phù hợp nhất trên các tập hợp điểm. Các bộ điểm có thể sẽ không được đặt hàng như vậy để lặp lại giữa các hình vuông nhỏ nhất phù hợp nhất và sắp xếp lại các điểm để các điểm trên cả hai đối tượng gần với cùng một thứ tự. Sự phát triển phương trình cho điều này là rất nhiều đại số nhưng không phức tạp về khái niệm.

Answer 4

Hãy xem xét một đa giác (hình tam giác) trong đối tượng mục tiêu. Đối với đa giác này, hãy tìm đa giác tương đương trong hình học khác (nguồn), tức là.chiều dài của các cạnh, góc giữa các cạnh, khu vực phải giống nhau. Nếu chỉ có một kết quả phù hợp, hãy tìm ma trận biến đổi cứng nhắc, làm thay đổi các đỉnh theo cách đó: X' = M*X. Vì X' AND X được biết đến với tất cả các điểm trên đa giác phù hợp, nên có thể thực hiện được với đại số tuyến tính.

Nếu bạn muốn ánh xạ một-một giữa các đỉnh của đa giác, hãy di chuyển qua các cạnh của đa giác theo cùng thứ tự, và tạo một bảng tra cứu ánh xạ từng đỉnh một đến một đỉnh khác. Nếu bạn có một half edge data structure đối tượng 3d của bạn sẽ đơn giản hóa quá trình này rất nhiều.

Nếu bạn tìm thấy nhiều hơn một đa giác phù hợp, hãy di chuyển đa giác nguồn từ cả hai điểm và tiếp tục so khớp các đa giác lân cận của chúng với đa giác đích. Tiếp tục cho đến khi một trong số chúng bị hỏng, sau đó bạn có thể thực hiện các bước tương tự như phiên bản một trận đấu.

Có nhiều giải pháp nghiêm túc hơn được liệt kê here, nhưng tôi nghĩ phương pháp ở trên cũng sẽ hoạt động.