Safe navigation of robotic vehicles is considered as a key pre-requisite of successful mission operations within highly adverse and unconstrained environments. While there has been extensive research in the perception of positive obstacles, little progress can be accredited to the field of negative obstacles. This paper hypostatizes an elaborative attempt to address the problem of negative obstacle detection and traversability analysis in the form of gaps by processing 3-dimensional range data. The domain of application concerns Urban Search and Rescue scenarios that reflect environments of increased complexity in terms of diverse terrain irregularities. To allow real-time performance and, in turn, timely prevention of unrecoverable robotic states, the proposed approach is based on the application of efficient image morphological operations for noise reduction and border following the detection and grouping of gaps. Furthermore, we reason about gap traversability, a concept that is novel within the field. Traversability assessments are based on features extracted through Principal Component Analysis by exploring the spatial distribution of the interior of the individual gaps or the orientation distribution of the corresponding contour. The proposed approach is evaluated within a realistic scenario of a tunnel car accident site and a challenging outdoor scenario. Using a contemporary Search and Rescue robot, we have performed extensive experiments under various parameter settings that allowed the robot to always detect the real gaps, and either optimally cross over those that were traversable or otherwise avoid them.