We present a novel and fast algorithm to estimate penetration depth (PD) between two polyhedral models. Given two overlapping polyhedra, it computes the minimal translational distance to separate them using a combination of discretized computations and hierarchical refinement. The algorithm computes pairwise Minkowski sums of decomposed convex pieces, performs closest point query using rasterization hardware, and refines the estimated PD by incremental walking. It uses bounding volume hierarchies, model simplification, and culling algorithms to further accelerate the computation and refines the estimated PD in a hierarchical manner. We highlight its performance on complex models.