Nén Dữ Liệu Đỉnh Mô Hình 3D

Bối cảnh ra đời:
Trong một lần trò chuyện với nhóm phát triển game Thiên Hạ, tôi được biết họ đang gặp vấn đề về thời gian tải tài nguyên quá lâu do kích thước dữ liệu quá lớn, ảnh hưởng trực tiếp đến trải nghiệm người chơi. Giải pháp tất yếu là phải tiến hành nén dữ liệu.

Cân nhắc về hiệu quả nén:
Khi hệ thống có dung lượng RAM vật lý dồi dào, việc nén dữ liệu đôi khi lại phản tác dụng. Lý do là quá trình giải nén sẽ tiêu tốn nhiều tài nguyên CPU. Tuy nhiên, với RAM lớn, hệ điều hành sẽ tận dụng không gian này làm bộ đệm cho thao tác đọc/ghi đĩa. Ngay cả khi ứng dụng không chiếm nhiều bộ nhớ logic, việc tải dữ liệu lớn từ ổ cứng cũng gần như không bị ảnh hưởng tốc độ. Ngược lại, khi dữ liệu vượt ngưỡng RAM khả dụng, việc trao đổi dữ liệu liên tục giữa RAM và ổ cứng sẽ khiến hiệu suất sụt giảm mạnh. Lúc này, nén dữ liệu lại trở thành giải pháp tối ưu vì thời gian giải nén CPU thấp hơn nhiều so với thời gian chờ đợi từ I/O đĩa.

Bí quyết nâng cấp hiệu năng game:
Đối với các game MMORPG hiện đại với lượng tài nguyên đồ sộ phục vụ cá nhân hóa người chơi, việc nâng cấp RAM thường mang lại hiệu quả rõ rệt hơn so với thay thế CPU hay card đồ họa.

Giải pháp cụ thể của nhóm Thiên Hạ:
Hiện tại nhóm mới chỉ áp dụng nén thông tin xương hoạt ảnh. Trong phạm vi bài viết này, tôi muốn tập trung chia sẻ về phương pháp nén dữ liệu đỉnh mô hình 3D, đặc biệt là thuật toán nén có mất mát chất lượng mà tôi đang nghiên cứu.

Cấu trúc dữ liệu đỉnh cơ bản:
Dữ liệu đỉnh bao gồm hai thành phần chính:

• Tọa độ đỉnh: Xác định vị trí trong không gian 3D
• Bảng chỉ số: Mô tả cấu trúc mô hình thông qua các tam giác (mỗi mặt dùng 3 chỉ số đỉnh)

Phương pháp nén tọa độ đỉnh:

1. Chuyển đổi sang số định điểm:
   Thay vì dùng 3 số float (12 byte/đỉnh), ta thực hiện chuẩn hóa tọa độ về khoảng [0,1), sau đó lưu dưới dạng số short 16-bit. Giải pháp này mang lại độ chính xác toàn bộ 16-bit thay vì chỉ 10-bit như half-float, chỉ cần thêm 6 giá trị float (24 byte) để phục hồi tọa độ gốc.

2. Tối ưu hóa thứ tự đỉnh:
   Sử dụng thuật toán tham lam kết hợp luyện kim mô phỏng (simulated annealing) để sắp xếp đỉnh sao cho khoảng cách giữa các đỉnh liên tiếp là nhỏ nhất. Dù không đạt giải pháp tối ưu nhưng đảm bảo phần lớn khoảng cách không vượt quá ngưỡng 0.5 trên bất kỳ trục tọa độ nào.

3. Mã hóa hiệu số:
   Biến đổi tọa độ thành hiệu số so với đỉnh trước. Nhờ thứ tự tối ưu, hầu hết giá trị hiệu số có nhiều bit 0 ở phần cao. Phân loại thành 5 nhóm theo độ dài chuỗi 0 liên tiếp, áp dụng mã biến chiều dài tương ứng. Nhóm cuối cùng (ít nhất 1 bit 0) được đánh dấu là đỉnh dư thừa, có thể loại bỏ khi giải mã.

Kết quả thử nghiệm:
Áp dụng trên mô hình nhân vật 268 đỉnh (423 mặt), kết quả đạt được:

• Thêm 30 đỉnh dư thừa → Tổng 298 đỉnh
• Dữ liệu nén: 298×3 byte + 24 byte = 900 byte
• Dữ liệu gốc: 268×12 byte = 3216 byte
• Tỷ lệ nén: 28%
• Sai số trung bình: 0.08% (cực đại 0.2%)
  Với độ phân giải màn hình thông thường, sai số này hoàn toàn chấp nhận được vì không vượt quá 1 pixel khi hiển thị.

Hướng phát triển:

• Nén bảng chỉ số (index) không mất mát bằng mã biến chiều dài
• Tối ưu hóa thứ tự đỉnh để tăng hiệu quả nén
• Nghiên cứu phương pháp nén cho dữ liệu pháp tuyến, UV map và thông tin xương

Bổ sung ngày 21/7:
Đã hoàn thiện phiên bản thử nghiệm thuật toán. Kết quả thực tế phù hợp với tính toán lý thuyết, chứng minh tính khả thi của phương pháp.