Thuật toán hoặc phần mềm để cắt lưới

Question

Cách tiếp cận đúng để cắt lưới 3D là gì? Lưới là tất cả các bề mặt đóng và các lát cần phải là hình ảnh nhị phân của những gì bên trong lưới. Vì vậy, ví dụ, một lưới đại diện cho một hình cầu và lát hình ảnh là những hình tròn đầy.

Tôi đang tìm thư viện phần mềm hoặc thuật toán mà tôi có thể tích hợp vào dự án C++ hiện tại của mình.

Answer 1

Thư viện trò chơi nguồn mở của tôi chứa triển khai cắt lưới. Nó hoạt động với api Irrlicht, nhưng có thể được viết lại để sử dụng một API khác với một nỗ lực khiêm tốn. Bạn có thể sử dụng mã theo các điều khoản của giấy phép BSD, hoặc học hỏi từ nó một thực hiện của riêng bạn.

Xem MeshTools :: splitMeshZ trong this file for an implementation of mesh slicing.

Nếu bạn chỉ muốn biết các thuật toán, đây là một mô tả cấp cao về những gì tôi đã làm:

Tôi ban đầu nghĩ đến việc sử dụng một hộp bounding trục thẳng hàng để xác định nơi để cắt lưới. Đây là vấn đề bởi vì nó đã giới thiệu nhiều trường hợp đặc biệt. Ví dụ, một cạnh vượt qua góc của hộp có thể được chia thành ba phần thay vì chỉ hai.

Sử dụng máy bay để cắt lưới thành lưới bên trái và lưới phải giảm số lượng trường hợp đặc biệt, vì cạnh nằm ở một bên của mặt phẳng hoặc mặt khác, hoặc nó đi ngang mặt phẳng và như vậy cắt thành hai miếng chính xác.

Bất kỳ cấu hình cắt giảm mong muốn nào cũng có thể được thực hiện đơn giản bằng cách cắt một lần, lấy một trong các mắt lưới và cắt lại ở vị trí khác, v.v. Cụ thể trong trường hợp bạn mô tả trong phần, một vòng tròn có thể được cắt từ một quả cầu bằng cách cắt một nửa quả cầu, di chuyển máy bay một lượng nhỏ và cắt nửa còn lại chỉ còn lại một dải mỏng. (Bạn không thể cắt một lưới xuống theo nghĩa đen không sâu với mã tôi đã viết, nhưng bạn có thể cắt một lưới lên đến bất cứ điều gì bạn đã thiết lập ngưỡng bình đẳng nổi điểm của bạn được. Tôi nghĩ rằng tôi tự ý chọn 0,001 trong mã của tôi.)

Sử dụng logic tương tự, bất kỳ góc mong muốn nào của mặt phẳng cắt có thể đạt được bằng mặt phẳng cố định; bạn chỉ cần chuyển đổi lưới để xoay nó tương đối so với mặt phẳng cắt cố định, và sau đó biến đổi kết quả trở lại. (Đối với trò chơi của tôi, tôi chỉ cần cắt giảm vuông góc với mặt phẳng XY, do đó, để đơn giản tôi chỉ cho phép giá trị Z của cắt được thiết lập, và giả định cắt là tại vị trí đó Z.)

OK, bây giờ chúng tôi đã đơn giản hóa vấn đề, thuật toán không quá tệ:

Điều kiện khởi động: Bạn có mặt phẳng cắt. Bạn có một tập hợp các hình tam giác nguồn. Bạn có hai bộ đích gồm các đa giác đa giác (không phải hình tam giác; các tứ giác có thể được tạo bằng cách cắt hình tam giác). Hai bộ đích được gọi là Trái và Phải.

Quy trình: Lặp lại ba điểm của tam giác. Đếm số điểm nhỏ hơn mặt cắt. Tôi sẽ gọi những cái đó ít hơn mặt phẳng cắt Trái và những cái lớn hơn mặt phẳng cắt Phải. Chỉ có một số ít các trường hợp:

• Tất cả các điểm tam giác đang ở trên trái: đặt hình tam giác trong Left thiết
• Tất cả các điểm đang trên bên phải: đưa hình tam giác trong Ngay lập
• Một điểm là trái, những người khác là phải: nếu bạn cắt một tam giác trên hai cạnh, và bạn đang nắm giữ một trong những điểm, bạn sẽ chỉ giữ một hình tam giác nhỏ hơn. Đặt một tam giác trong tập hợp trái được tạo thành từ điểm bên trái, và hai điểm mà các cạnh đi qua mặt phẳng. Đặt một quad trong tập hợp phải (xem trường hợp tiếp theo).

• Hai điểm còn lại, một điểm là Phải. Nếu bạn đang giữ một cạnh của một hình tam giác và cắt nó qua hai cạnh khác, bạn đang giữ một hình thang. Đặt một quad trong bộ còn lại tạo thành hai điểm trong tay của bạn, cộng với hai điểm mà qua cắt. Đặt một hình tam giác vào đúng bộ (hình ảnh phản chiếu của trường hợp trên).

• Khi hoàn tất, lần lượt các quads thành hình tam giác bằng cách thêm một liên kết trên một phần ngắn nhất.

Vậy đó. Đó là thuật toán cơ bản. Mã thực tế xử lý thêm một vài trường hợp như thế nào nếu cạnh chính xác bằng cắt, nếu hình tam giác chính xác trên cạnh, không thêm đa giác thoái hóa (ví dụ: điểm không có thân), v.v.

Misc. vấn đề (tất cả bao gồm trong các mã liên kết):

• Đừng overcomplicate toán cho LERP'ing nơi mà cạnh đi qua mặt phẳng cắt. Nó không cần một nội suy tuyến tính đầy đủ, nó thực sự chỉ là Đại số II Đại số: tăng lên chạy, lần tỷ lệ

• Có lợi thế cho việc tạo các điểm được tạo ra (LERP'ed) sao cho tam giác chia sẻ đỉnh lưới chưa cắt sẽ chia sẻ các đỉnh mới tương ứng trong lưới cắt.

• Nếu bạn định giữ nguyên chia sẻ đỉnh và bạn đang sử dụng bộ đệm chỉ mục hình tam giác, rất tiếc bạn không biết chỉ mục khi bạn tạo hình dạng để đặt trong bộ Trái và Phải lần đầu tiên. Tôi sử dụng một lớp được gọi là "PossibleVertex" để đại diện cho một số chỉ mục tam giác trong tương lai.

• Nếu bạn đang đi để hiển thị lưới, quanh co vấn đề trật tự. Hãy suy nghĩ cẩn thận về cách bạn mã hóa nó có thể đảm bảo các đa giác kết quả sử dụng cùng thứ tự quanh co như các hình tam giác mà chúng xuất phát. Điều này đặc biệt khó khăn khi triangulating quads. Tôi không thể nhớ chi tiết nhưng tất cả đều được xử lý trong mã được liên kết.

• Đối với trò chơi của tôi, tôi muốn làm một dải ruy băng phẳng kết nối hai mắt lưới cắt. Đó là lý do tại sao kết quả splitMeshZ trong 3 mắt lưới, thay vì chỉ hai.Bạn có thể sử dụng lưới giữa, hoặc chỉ cần bỏ qua nó.

Answer 2

Tôi giả sử bạn đang nói về lưới tam giác?

Cách tiếp cận "đúng" phụ thuộc mạnh mẽ vào chi tiết cụ thể của trường hợp sử dụng của bạn là gì.

Phương pháp OpenGL do Jerry đề xuất có thể phù hợp với bạn.

Một cách tiếp cận khác là tính toán rõ ràng các vết cắt. Bạn có thể làm điều này với CGAL. Cụ thể hơn với hạt nhân 3D của nó. Nó có tính năng function có thể tính toán giao lộ giữa tất cả các loại nguyên thủy, bao gồm mặt phẳng và hình tam giác. Sử dụng chức năng này, bạn có thể tính chính xác phác thảo giao lộ của bạn và đưa nó vào một hình ảnh. - Bằng cách này bạn sẽ không phụ thuộc vào OpenGL mà thay vào đó là CGAL.

Answer 3

Tôi đã vạch ra thuật toán để tính toán giao lộ khối lượng mặt phẳng trong this answer. Một thực hiện trong Java được cung cấp.

Answer 4

Nó sẽ nhanh hơn (cho chính mình, không chạy theo thời gian) nếu bạn thực hiện nó tự hỏi: Đây là những bước đơn giản bạn cần làm:

1-Giải nén tất cả các tam giác của lưới

2-đối với mỗi hình tam giác,

2-1- kiểm tra nếu có các điểm tam giác đang ở trên lát mặt phẳng,

2-2- nếu không, sau đó cho mỗi người trong số ba cạnh của nó, tìm giao lộ ion với mặt cắt lát của bạn (nếu có). Bạn phải có 2 trong số họ giao nhau với máy bay hoặc không có máy bay nào.

2-2-1 Nếu 2 cạnh giao nhau với mặt phẳng, sau đó bạn thêm một đường thẳng giữa 2 điểm này trên mặt phẳng.

Answer 5

Một dự án trong không gian 3D lưới cắt (với mã nguồn trong C++):

http://www.dainf.ct.utfpr.edu.br/~rminetto/projects/slicing/