Abstract: Many techniques have already been proposed to improve the efficiency of maximum intensity projection (MIP) volume rendering, but none of them considered the possible hypothesis of a better complexity than either O(n) for finding the maximum value of n samples along a ray or O(n³) for an object-order algorithm. Here, we fully model and analyze the use of octrees for MIP, and we mathematically show that the average MIP complexity can be reduced to O(n²) for an object-order algorithm, or to O(log(n)) per ray when using the image-order variant of our algorithm. Therefore, this improvement establishes a major advance for interactive MIP visualization of large-volume data.In parallel, we also present an object-order implementation of our algorithm, satisfying the theoretical O(n²) result. It is based on hierarchical occlusion maps that perform on-the-fly visibility of the data, and our results show that it is the most efficient solution for MIP available to date.