We present an approach to endow an autonomous underwater vehicle with the capabilities to move through unexplored environments. To do so, we propose a computational framework for planning feasible and safe paths. The framework allows the vehicle to incrementally build a map of the surroundings, while simultaneously (re)planning a feasible path to a specified goal. To accomplish this, the framework considers motion constraints to plan feasible 3D paths, that is, those that meet the vehicle's motion capabilities. It also incorporates a risk function to avoid navigating close to nearby obstacles. Furthermore, the framework makes use of two strategies to ensure meeting online computation limitations. The first one is to reuse the last best known solution to eliminate time-consuming pruning routines. The second one is to opportunistically check the states' risk of collision. To evaluate the proposed approach, we use the Sparus II performing autonomous missions in different real-world scenarios. These experiments consist of simulated and in-water trials for different tasks. The conducted tasks include the exploration of challenging scenarios such as artificial marine structures, natural marine structures, and confined natural environments. All these applications allow us to extensively prove the efficacy of the presented approach, not only for constant-depth missions (2D), but, more important, for situations in which the vehicle must vary its depth (3D).