Tổ Chức Vật Liệu Trong Hệ Thống Hạt

2020-12-01 Khoảng 1000 từ 5 phút

Nội dung

Trong một hệ thống hạt, việc sử dụng đa dạng các loại vật liệu là điều không thể tránh khỏi. Có hai cách tiếp cận chính: thứ nhất là phân chia các vật liệu khác nhau thành các đối tượng quản lý riêng biệt; thứ hai là tập trung toàn bộ hạt trong cùng một bộ quản lý, đồng thời bổ sung thuộc tính phân loại vật liệu. Mỗi phương pháp đều có những ưu điểm và hạn chế riêng, đòi hỏi sự cân nhắc kỹ lưỡng trong thiết kế kiến trúc hệ thống.

So sánh hai cách tổ chức

Với phương pháp phân chia theo vật liệu, dù các hạt có cùng các thuộc tính khác như kích thước hay tốc độ, chúng vẫn bị tách biệt hoàn toàn về mặt xử lý dữ liệu. Trong khi đó, phương pháp tập trung đòi hỏi phải giải quyết bài toán phân loại vật liệu hiệu quả để tối ưu hiệu suất rendering.

Một nguyên tắc quan trọng trong rendering là không thể bỏ qua thuộc tính vật liệu của hạt. Không một hệ thống nào có thể chấp nhận việc mỗi hạt gửi riêng lẻ vật liệu của mình đến bộ render - điều này sẽ phá hủy hiệu quả batching. Dù là hạt dạng mặt phẳng (billboard) hay mô hình 3D, dữ liệu không gian của nhóm hạt cần được gửi hàng loạt. Đối với hạt mặt phẳng, thông tin đỉnh của nhiều hạt nên được chứa trong cùng một buffer; với hạt mô hình phức tạp, các ma trận không gian của từng hạt nên được tổ chức trong instance buffer.

Mô hình quản lý theo ECS

Trong thiết kế hệ thống được đề cập trong bài viết “Thiết kế hệ thống hạt”, chúng tôi áp dụng mô hình ECS (Entity-Component-System). Bộ quản lý không lưu trữ dữ liệu trực tiếp mà tập trung vào mối liên kết giữa các thuộc tính, tạo độ linh hoạt cao trong việc xử lý thuộc tính vật liệu.

Khi số lượng vật liệu đồng thời tối đa trong một bộ quản lý hạn chế (ví dụ dưới 8 loại), phương pháp đơn giản nhất là tạo các thuộc tính tag M0 đến M7. Lúc này, chỉ cần sử dụng API lọc tag của bộ quản lý để lấy các tập hạt theo vật liệu.

Tuy nhiên, với số lượng vật liệu lớn, cách tiếp cận tag trở nên không hiệu quả. Một giải pháp tự nhiên là thiết kế một cấu trúc dữ liệu chuyên dụng cho việc quản lý vật liệu. Bộ quản lý chỉ cần hỗ trợ hai giao diện cốt lõi: thêm mới dữ liệu và sắp xếp lại dữ liệu, trong khi chi tiết cấu trúc nội bộ có thể thay đổi linh hoạt.

Quản lý vật liệu qua ID

Một phương pháp tối ưu là sử dụng ID vật liệu kết hợp với kỹ thuật sắp xếp. Giả sử mỗi hạt có thuộc tính id vật liệu, việc render có thể được thực hiện hiệu quả qua các bước:

Sắp xếp mảng hạt theo ID vật liệu
Các hạt cùng vật liệu sẽ liên tiếp nhau trong mảng, cho phép duyệt tuần tự

Tuy nhiên, độ phức tạp O(N log N) của sắp xếp truyền thống có thể không tối ưu. Chúng tôi đề xuất giải pháp thay thế với độ phức tạp tuyến tính O(N) thông qua kỹ thuật “sắp xếp theo thùng” (bucket sort), với điều kiện giới hạn số lượng vật liệu đồng thời tối đa ở mức 255 loại.

Cấu trúc dữ liệu tối ưu với giới hạn vật liệu

Với giới hạn 255 loại vật liệu, chúng ta có hai lợi thế:

Sử dụng byte đơn (8 bit) để lưu trữ ID vật liệu
Áp dụng thuật toán sắp xếp theo thùng hiệu quả

Cấu trúc dữ liệu được đề xuất bao gồm hai mảng:

1
2
3
4


struct material_context {
    particle_id index[MAX_PARTICLE];  // Danh sách liên kết cho từng vật liệu
    particle_id head[MAX_MATERIAL];   // Con trỏ đầu chuỗi cho mỗi vật liệu
};

Quá trình phân loại hạt được thực hiện như sau:

Khởi tạo mảng head[] với giá trị INVALID_PARTICLE
Duyệt qua toàn bộ hạt một lần để xây dựng danh sách liên kết trong index[]
Mỗi phần tử head[mat_id] trỏ đến hạt đầu tiên trong chuỗi cùng loại vật liệu

Ví dụ với 10 hạt có chuỗi ID vật liệu 0 1 0 1 0 1 0 1 0 1, cấu trúc dữ liệu sẽ hình thành hai chuỗi liên kết:

Head[0] → 9 → 7 → 5 → 3 → 1 → INVALID
Head[1] → 8 → 6 → 4 → 2 → 0 → INVALID

Xử lý việc xoá hạt

Vấn đề xoá hạt được giải quyết thông qua cơ chế remap table:

Khi xoá hạt i, hệ thống ghi lại mối liên hệ remap (old_index → new_index)
Trong quá trình render, mỗi tham chiếu đến hạt sẽ được tra cứu bảng remap để cập nhật chỉ số mới

Để tối ưu hiệu suất, chúng ta cũng có thể theo dõi số lượng hạt theo từng vật liệu. Khi một loại vật liệu không còn hạt nào, ID đó sẽ được đánh dấu rảnh để tái sử dụng.

Tích hợp với hệ thống Lua

Trong hệ thống của chúng tôi, tầng Lua đóng vai trò đóng gói bên ngoài:

Toàn bộ vật liệu được lưu trữ trong bảng Lua với khóa phức tạp (ví dụ tên vật liệu)
Tầng C duy trì cache 255 vật liệu đang sử dụng để truy xuất nhanh
Một ID vật liệu đặc biệt được dành riêng cho “vật liệu trống”, dùng khi vượt quá giới hạn 255 loại

Phương pháp này che giấu chi tiết kỹ thuật về ID vật liệu nội bộ, mang lại trải nghiệm lập trình trực quan cho người dùng trong khi vẫn đảm bảo hiệu suất rendering tối đa.