A method of generating a 3D complex octree map. A plurality of points each having 3D location information are detected from a range image. A space having the detected plurality of points is represented using grids. If points in a grid forms a plane, the grid is not subdivided and planar information about the plane is stored. A space not forming a plane is subdivided, thereby enhancing the storage efficiency.