Nén Dữ Liệu Bản Đồ Độ Cao
Trong các cảnh quan 3D của game, bản đồ độ cao (heightmap) thường được sử dụng để biểu diễn địa hình ngoài trời. Cấu trúc này dùng mảng hai chiều để lưu trữ thông tin độ cao tương ứng với từng tọa độ mặt phẳng. Việc lựa chọn độ phân giải cho mỗi giá trị độ cao ảnh hưởng trực tiếp đến chất lượng và hiệu suất xử lý.
Vấn đề về dung lượng lưu trữ
Nếu dùng 1 byte để biểu diễn mỗi giá trị độ cao, không gian 256 mức độ cao thường không đủ đáp ứng cho các địa hình phức tạp. Do đó, các nhà phát triển thường chọn kiểu dữ liệu word (2 byte) hoặc float (4 byte) để đạt độ chính xác cao hơn. Trong đó, kiểu float mang lại nhiều lợi thế vì không cần xử lý hệ số tỷ lệ (scale factor), nhưng lại tiêu tốn gấp 4 lần dung lượng so với byte.
Giải pháp nén có mất mát
Dựa trên nguyên lý địa hình thường có sự chuyển tiếp mượt mà giữa các điểm, Cloud (tác giả) đã đề xuất phương pháp nén có mất mát hiệu quả. Ví dụ minh họa với bản đồ độ cao kích thước 256x256:
1. Tạo chuỗi bản đồ đa cấp độ phân giải
- Xây dựng 8 cấp độ bản đồ từ cao xuống thấp: 128x128, 64x64, 32x32… đến 1x1
- Cấp độ 0 (1x1): Giá trị duy nhất là trung bình độ cao toàn bản đồ
- Cấp độ 1 (2x2): Mỗi điểm là trung bình của 4 điểm tương ứng từ cấp độ cao hơn
- Cấp độ 8 (256x256): Bản đồ gốc
2. Quy trình nén từng cấp độ
- Lưu trữ giá trị trung bình ở cấp độ 0
- Với các cấp độ 1-8:
- Tính toán giá trị chênh lệch (delta) giữa độ cao thực tế và độ cao dự đoán từ cấp độ thấp hơn
- Xác định khoảng giá trị [min, max] của bản đồ chênh lệch
- Ánh xạ khoảng này sang dải [0,255] để lưu dưới dạng số nguyên 1 byte
- Dữ liệu mỗi cấp độ cần: size² byte + 8 byte thông tin bổ sung
3. Kết quả nén
- Tổng dung lượng: 87,448 byte (gồm 17 giá trị float và 87,380 byte dữ liệu chênh lệch)
- So với bản gốc 262,144 byte (256x256x4), tỷ lệ nén đạt 33%
- Sai số trung bình khoảng 0.015% qua kiểm thử thực tế
Ứng dụng mở rộng
Với bản đồ độ cao 8-bit (0-255), có thể:
- Chuẩn hóa về dải [0,1] trước khi nén
- Lưu 2 điểm trên 1 byte (dải 0-15)
- Đạt tỷ lệ nén cao hơn mà vẫn giữ được chất lượng hình ảnh gần như nguyên bản (khó phân biệt bằng mắt thường)
Lợi ích phụ
Phương pháp này còn tạo ra các bản đồ độ cao độ phân giải thấp ở các cấp độ trung gian, rất hữu ích cho các ứng dụng cần xử lý đa mức độ chi tiết (LOD - Level of Detail).
Việc trình bày ở đây mang tính định hướng chứ không đi sâu vào các chứng minh toán học chi tiết. Xin phép không cung cấp hình minh họa, mã nguồn hay các mô tả kỹ thuật cụ thể hơn.
Bổ sung: Xử lý các điểm biên trong bản đồ độ cao sau nén cần có kỹ thuật đặc biệt để đảm bảo tính liên tục của địa hình.