Chuyển đổi 2D hình dạng dựa Tile để hình đa giác đơn giản

Question

Như đã thấy trong hình trên, tôi có một mảng 2D của gạch, mỗi với 4 điểm trong thế giới trò chơi của tôi. Tôi đang tìm một phương pháp để chuyển đổi các hình dạng này được xây dựng từ các ô riêng lẻ thành đơn giản hóa (không cần các đỉnh không cần thiết, chỉ những hình dạng cần thiết để tạo thành đường viền) hình đa giác.

Tôi đã nhìn xung quanh, ở đây và ở nơi khác và đã có rất ít may mắn. Nhưng có lẽ tôi không biết thuật ngữ chính xác để tìm kiếm. Bất kỳ trợ giúp được đánh giá cao.

Thông tin bổ sung: Tôi đang tìm cách sử dụng điều này để tối ưu hóa ánh sáng động. Nếu ai đó có cách tiếp cận khác để hoàn thành các bóng động nhanh trong một thế giới dựa trên nền gạch, điều đó cũng sẽ trả lời câu hỏi.

Answer 1

Tôi đề nghị thuật toán tiếp theo:

1. Lưu trữ tất cả các vị trí cạnh vào mảng 2D (vị trí cạnh là trung tâm của cạnh).
2. Đếm các cạnh trùng lặp trong mảng này (1 không trùng lặp, 2 là giao nhau với một cạnh khác. Các giá trị khác là không thể).
3. Chọn cạnh chưa được đánh dấu đầu tiên từ mảng với tính nhân bản 1 (không trùng lặp) và áp dụng thuật toán điền đệ quy đơn giản theo hướng certaing (ví dụ theo chiều kim đồng hồ) cho đến khi cạnh đầu tiên đạt tới. Tất cả các cạnh này sẽ tạo thành một đa giác đơn giản. Nếu cạnh chưa được đánh dấu chưa được thiết lập, thì GOTO 5.
4. Đánh dấu tất cả các cạnh này từ bước 3 như được sử dụng. GOTO đến bước 3.
5. Kết thúc.

Để đại diện trực quan hơn về thuật toán, tôi đã đăng hình ảnh bên dưới.

Answer 2

Cách tiếp cận ngây thơ sẽ chỉ đơn giản là đi qua từng ô và đánh dấu bất kỳ cạnh chuyển tiếp nào thành đa giác nhưng bạn có thể sử dụng lại thường lệ edge detection để có hiệu suất tốt hơn. Sau đó, bạn có thể muốn quan tâm đến việc loại bỏ các đa giác đó để chuyển đổi chúng thành các bộ sưu tập hình tam giác (làm cho phép toán bóng/ánh sáng sau này đơn giản hơn nhiều), vấn đề duy nhất trong trường hợp này là nếu bạn kết thúc với một đa giác lõm, nhưng một tessellator phong nha nên cho phép bạn phá vỡ nó thành đa giác lồi. Tôi không nghĩ rằng XNA có bất cứ điều gì được xây dựng trong cho tessellation, do đó bạn có thể cần phải tìm một thư viện tiện ích để làm điều đó cho bạn.