Xử Lý Biên Sau Khi Nén Bản Đồ Độ Cao

Vài năm trước, tôi từng viết một bài blog chia sẻ về thuật toán nén bản đồ độ cao do chính mình phát triển. Gần đây, khi áp dụng thuật toán này vào engine đang xây dựng, kết quả hoàn toàn như kỳ vọng - không chỉ cải thiện tốc độ tải tài nguyên nhờ dữ liệu được nén gọn, mà còn nâng cao trải nghiệm người dùng trong cùng điều kiện phần cứng. Điều này xuất phát từ nguyên lý hệ điều hành hiện đại luôn tận dụng bộ nhớ vật lý chưa dùng đến làm bộ đệm đĩa, nên kích thước tệp nhỏ hơn đồng nghĩa với việc lưu trữ được nhiều dữ liệu hơn trong cùng một không gian bộ nhớ.

Trong quá trình phát triển hệ thống tải dữ liệu địa hình động, chúng tôi chia nhỏ dữ liệu độ cao thành các mảnh nhỏ. Tuy nhiên, vấn đề phát sinh khi sử dụng thuật toán nén này là do mất mát dữ liệu trong quá trình nén, các mảnh địa hình kề nhau không thể khớp khít hoàn toàn tại đường biên tiếp giáp.

Để giải quyết vấn đề này, tôi đã thử nghiệm nhiều phương pháp trong vài ngày qua. Một trong những ý tưởng đầu tiên là tách mỗi đỉnh tại đường biên thành hai đỉnh riêng biệt. Trong dữ liệu chưa nén, các đỉnh này có giá trị hoàn toàn bằng nhau. Phương pháp đơn giản nhất là khi tải một mảnh địa hình, sẽ kiểm tra các mảnh lân cận đã được tải vào bộ nhớ chưa, nếu có thì sao chép dữ liệu tại cạnh tiếp giáp sang. Tuy nhiên, giải pháp này làm tăng độ liên kết giữa các dữ liệu, đồng thời yêu cầu tầng đọc dữ liệu phải truy cập thông tin từ tầng cao hơn, vi phạm nguyên tắc thiết kế engine nên bị loại bỏ.

Phương án tiếp theo là lưu trữ thông tin độ cao tại vùng biên dưới dạng không mất mát. Tuy nhiên, với kích thước dữ liệu mỗi mảnh vốn đã nhỏ, việc này sẽ làm giảm đáng kể hiệu quả nén mà chúng tôi đã dày công tối ưu.

Trong suốt buổi sáng hôm nay, tôi tập trung suy nghĩ cách hiệu quả để bảo toàn thông tin đường viền. Một ý tưởng nảy ra là tăng độ chính xác bổ sung cho các đỉnh tại biên (khoảng thêm 1 byte mỗi đỉnh). Dù đã viết xong hàng loạt mã nguồn triển khai, nhưng kết quả chưa thực sự như ý vì cảm giác đã làm vấn đề trở nên phức tạp hơn cần thiết.

Tuy nhiên, sau khi vận động cơ thể tại phòng gym buổi tối, trên đường trở về tôi bỗng nảy ra một giải pháp vô cùng tinh gọn. Thay vì tập trung vào việc tăng độ chính xác (hoặc giữ nguyên vẹn) các đỉnh tại biên, chúng ta chỉ cần đảm bảo các mảnh địa hình kề nhau khớp nối hoàn hảo - tức là các đỉnh tại đường biên phải có giá trị độ cao hoàn toàn bằng nhau.

Thực tế, giải pháp đơn giản là giảm độ chính xác của số thực. Về kỹ thuật này, tôi từng đề cập trong một bài viết trước đây trên sổ lưu bút trực tuyến, đồng thời có bài thảo luận riêng về việc lựa chọn hằng số EPSILON trên blog. Lần này tôi triển khai như sau (chỉ cần truyền con trỏ số thực cần giảm độ chính xác):

1
2
3
4
5
6

static __inline void
reduce_precision(float*fdata)
{
  uint32_t *d=(uint32_t *)fdata;
  *d=(*d + 0x8000) & 0xffff0000;
}

P/s: Spore thực sự là một tựa game tuyệt vời.

Bổ sung ngày 6/9: Phương pháp này gặp vấn đề với các giá trị gần 0 do không xử lý được dấu âm/dương. Giải pháp là khi phát hiện giá trị tuyệt đối nhỏ hơn 1 (số mũ âm trong biểu diễn số thực), ta cần cộng thêm 1 trước khi xử lý, sau đó trừ lại 1 để có kết quả chính xác. Ngoài ra, cần xử lý riêng trường hợp hai giá trị có chênh lệch số mũ - ví dụ một bên là 1.11111111111 và bên kia là 1.000000000 - bằng cách kiểm tra và điều chỉnh thủ công.

Về vấn đề vector pháp tuyến, thực tế chúng được tính toán theo phương pháp thông thường từ độ cao đỉnh. Có thể lưu trữ thêm một vòng đỉnh dữ liệu hoặc tính toán với số đỉnh ít hơn tại vùng biên. Sự khác biệt nhỏ giữa các vector pháp tuyến hầu như không ảnh hưởng đến trực quan hình ảnh (điều này đã được kiểm chứng qua kết quả render thực tế).

Bổ sung ngày 10/9: Nếu mục tiêu chỉ là loại bỏ độ chính xác thập phân ở mức độ nhất định (khoảng 4 chữ số sau dấu phẩy), có thể sử dụng kỹ thuật sau:

1
2

a += 8192.0f; 
a -= 8192.0f;

Cơ chế này giúp giảm độ chính xác mà không cần giải thích chi tiết ở đây. Khi lập trình, cần lưu ý ngăn trình biên dịch tối ưu hóa làm mất hiệu ứng của đoạn mã này.