Method for fast detecting the intersection of a plane and a cube in an octree structure to find point sets within a convex region

摘要

Performing efficient view frustum culling is a fundamental problem in computer graphics. In general, an octree is used for view frustum culling. The culling checks the intersection of each octree node (cube) against the planes of the view frustum. However, this involves many calculations. We propose a method for fast detecting the intersection of a plane and a cube in an octree structure. When we check which child of the octree node intersects a plane, we compare the coordinates of the corner of the node and the plane. Using an octree, we calculate the vertices of the child node by using the vertices of the parent node. To find points within a convex region, a visibility test is performed by AND operation with the result of three or more planes. In experiments, we tested the problem of searching for the visible point with a camera. The method was two times faster than the conventional method, which detects a visible octree node by using the inner product of the plane and each corner of the node.