The ability to detect changes is an essential competence that robots should possess for increased autonomy. In several applications, such as surveillance, a robot needs to detect relevant changes in the environment by comparing current sensory data with previously acquired information from the environment. We present an efficient method for point cloud comparison and change detection in 3D environments based on spatial density patterns. Our method automatically segments 3D data corrupted by noise and outliers into an implicit volume bounded by a surface, making it possible to efficiently apply Boolean operations in order to detect changes and to update existing maps. The method has been validated on several trials using mobile robots operating in real environments and its performance was compared to state-of-the-art algorithms. Our results demonstrate the performance of the proposed method, both in greater accuracy and reduced computational cost.