Phép So Sánh Flatland
Flatland (1884) của Edwin Abbott: cư dân của một mặt phẳng hai chiều. Họ chỉ nhận thức được chiều dài và chiều rộng. Chiều sâu – chiều thứ ba nằm phía trên họ – hoàn toàn vô hình. Họ không thể nhận thức, không thể sử dụng và không thể xây dựng dựa trên nó. Hình học của thế giới họ chứa đựng một chiều mà họ đã loại bỏ về mặt cấu trúc.
MOAD-0007 hoạt động theo cách tương tự. Các đối tượng trong không gian 3D mang theo vị trí, xoay và thể tích bao: một cấu trúc hình học phong phú. Quét tuyến tính coi chúng như một danh sách phẳng. Cấu trúc không gian hiện diện nhưng không được dùng, bị vứt bỏ. Mỗi lần kiểm tra giao cắt phải quét toàn bộ danh sách, như thể các đối tượng không có hình học và không có vị trí.
Ví Dụ Three.js
Three.js Raycaster.intersectObjects(): cho một tia (vị trí & hướng trong không gian 3D), tìm tất cả các đối tượng mà tia giao cắt. Cách triển khai: duyệt qua tất cả N đối tượng trong cảnh, kiểm tra từng đối tượng với tia. Độ phức tạp O(N) mỗi lần gọi.
Một trình xử lý sự kiện hover gọi intersectObjects() một lần mỗi khung hình ở 60 khung hình mỗi giây. Với N=100 đối tượng: 6.000 phép kiểm tra giao cắt mỗi giây. Với N=10.000 đối tượng: 600.000 phép kiểm tra mỗi giây. Chi phí: tỷ lệ thuận với N, không phải với số đối tượng mà tia thực sự giao cắt.
Ở N=100: không nhận thấy. Ngân sách khung hình (16,7ms ở 60fps) hấp thụ chi phí mà không gặp vấn đề.
Ở N=10.000: chiếm ưu thế. 600.000 phép kiểm tra giao cắt mỗi giây làm bão hòa luồng chính. Tốc độ khung hình giảm. Cảnh hoạt động tốt ở N=100 sụp đổ thầm lặng khi N vượt ngưỡng.
Cấu trúc mà việc quét tuyến tính loại bỏ
Các đối tượng chiếm vị trí trong không gian. Một đối tượng ở vị trí (1000, 0, 0) không thể giao cắt với một tia hướng (-1, 0, 0) từ vị trí (0, 0, 0): đối tượng nằm ở hướng ngược lại. Việc quét tuyến tính vẫn kiểm tra nó.
Các đối tượng có thể tích bao quanh: một hình cầu hoặc hộp bao bọc toàn bộ đối tượng. Một tia không giao cắt thể tích bao quanh của đối tượng thì không thể giao cắt với đối tượng. Việc quét tuyến tính vẫn thực hiện phép kiểm tra giao cắt đầy đủ.
Hình học mã hóa những đối tượng cần bỏ qua. Việc quét tuyến tính bỏ qua hình học. Đây là sự loại bỏ.
Ý nghĩa của 'Discarding the Structure'
Phép loại suy Flatland: cư dân của Abbott không thể nhận thức được chiều sâu. Một Flatland Defect loại bỏ cấu trúc hình học tồn tại trong dữ liệu nhưng không bao giờ được đưa vào thuật toán.
Tại sao Tập hợp Băm Không Thể Sửa MOAD-0007
MOAD-0001 fix: thay thế kiểm tra thành viên tuần tự bằng một tập hợp băm. list.contains(x): O(N). set.has(x): O(1). Câu hỏi thành viên: 'x có nằm trong tập hợp này không?' Không liên quan đến hình học không gian.
MOAD-0007 fix: thay thế quét không gian tuyến tính bằng chỉ mục không gian (BVH, octree, k-d tree, R-tree). Câu hỏi không gian: 'các đối tượng nào trong tập hợp này giao với tia/cầu/frustum này?' Yêu cầu khoảng cách không gian.
Một tập hợp băm trả lời câu hỏi thành viên: 'đối tượng chính xác này có hiện diện không?' O(1). Nó không thể trả lời câu hỏi khoảng cách: 'các đối tượng nào gần tia này?' Một tập hợp băm không có khái niệm về khoảng cách hay phạm vi không gian. Băm loại bỏ hình học triệt để như quét tuyến tính.
Một BVH trả lời câu hỏi khoảng cách: 'các đối tượng nào nằm trong truy vấn không gian này?' O(log N + k). Nó tổ chức các đối tượng theo vị trí, vì vậy các truy vấn khoảng cách bỏ qua các đối tượng cách xa về mặt hình học.
| Câu hỏi | Cấu trúc đúng | Cấu trúc sai |
|---|---|---|
| Đối tượng X có nằm trong tập hợp này không? | HashSet (O(1)) | Danh sách tuyến tính (O(N)) |
| Các đối tượng nào giao với tia này? | BVH/octree/k-d tree (O(log N)) | Quét tuyến tính HOẶC HashSet (O(N) hoặc O(N)) |
MOAD-0001 & MOAD-0007: cả hai đều là thao tác O(N) được thay thế bằng thứ gì đó nhanh hơn. Cần các cấu trúc khác nhau vì các câu hỏi khác nhau.
Khi nào xây dựng, khi nào bỏ qua
Xây dựng BVH tốn O(N log N). Truy vấn tốn O(log N + k). Điểm hòa vốn: khi số lần truy vấn đủ lớn để tiết kiệm chi phí truy vấn vượt quá chi phí xây dựng.
Với N=100: quét tuyến tính chỉ mất vài micro giây. Xây dựng BVH thêm chi phí. Bỏ qua BVH.
Với N=10.000 ở 60Hz: quét tuyến tính chiếm gần hết ngân sách khung hình. Truy vấn BVH chỉ tốn 1/1.000 so với quét tuyến tính. Xây dựng BVH một lần; truy vấn 60 lần mỗi giây. Điểm hòa vốn đạt được trước khung hình đầu tiên.
Quy tắc: xây dựng khi N * Q > N log N, trong đó Q = số truy vấn mỗi chu kỳ xây dựng lại. Với cảnh 3D tương tác: Q = 60 lần/giây, ngưỡng N = vài trăm đối tượng.
Chẩn đoán & Sửa cảnh 3D
Một ứng dụng trực quan hóa 3D render 5.000 đối tượng hình học. Trình xử lý hover kích hoạt 60 lần mỗi giây. Mỗi lần hover, handler gọi scene.intersectObjects(ray, objects) duyệt toàn bộ 5.000 đối tượng và kiểm tra từng cái với tia. Tốc độ khung hình giảm từ 60fps xuống 8fps.
Một thành viên trong nhóm gợi ý: 'Đặt tất cả đối tượng vào một Set để tra cứu O(1).'