Octree

Cây octree là một cấu trúc dữ liệu dạng cây mà mỗi nút trong có chính xác tám con. Cây octree thường được sử dụng để phân chia không gian ba chiều bằng việc chia đệ quy không gian ra thành 8 phần. Cây octree là một cấu trúc trong không gian ba chiều tương tự như cây quadtree. Tên của cây octree được đặt bằng việc kết hợp giữa hai từ oct + tree, nhưng thông thường, chữ "octree" chỉ có một chữ "t". Cây octree thường được sử dụng trong đồ họa 3D và các game engine 3D.

Mô tả trong không gian

Mỗi nút trong một cây octree chia không gian ra thành 8 phần. Ở cây octree chia theo điểm, mỗi nút lưu một điểm ba chiều cụ thể và điểm này là "trung tâm" của phép chia không gian tại nút đó. Điểm này là một trong số 8 góc của tám con của nút đó. Ở cây octree dựa theo ma trận, điểm chia không gian được ngầm định là tâm của vùng không gian mà nút đó đại diện. Nút gốc của cây octree dựa theo ma trận có thể đại diện cho không gian vô hạn; nút gốc của cây octree chia theo điểm mô tả một vùng không gian hữu hạn có biên vì vậy trung tâm ngầm định là rõ ràng. Chú ý rằng cấu trúc octree không giống như cấu trúc k-d tree: k-d tree chia không gian dọc theo một chiều cụ thể nào đó còn octree chia không gian xung quanh một điểm cụ thể. Một điểm khác nữa đó là: k-d tree luôn là một cây nhị phân còn octree thì không phải. Nếu sử dụng thuật toán duyệt theo chiều sâu, các node được duyệt qua tương ứng với các phần bề mặt bên ngoài của khối lập phương.

Lịch sử

Việc sử dụng cấu trúc octree cho đồ họa 3D trên máy tính lần đầu tiên được thực hiện bởi Donald Meagher ở học viện Rensselaer Polytechnic. Quá trình sử dụng được mô tả trong một báo cáo năm 1980 với tên gọi "Octree Encoding: A New Technique for the Representation, Manipulation and Display of Arbitrary 3-D Objects by Computer". Từ đó, đến năm 1995, Donald đăng ký bằng sáng chế với công trình "High-speed image generation of complex solid objects using octree encoding". Bằng sáng chế này hết hạn vào năm 1984.