Rigid registration has been a fundamental problem in 3D reconstruction for decades. Yet existing methods often rely on known point correspondences or fail to scale to millions of points and extreme outlier rates. In this talk, I will present two recent advances that address these challenges. First, I will present ARCS, an algorithm for jointly estimating rotations and unknown correspondences between partially overlapping point sets, which combines efficient geometric search with robust consensus maximization and Riemannian optimization. Second, I will present TEAR, a robust and scalable registration algorithm based on a truncated entry-wise absolute residual objective that decomposes the original six-dimensional optimization into lower-dimensional subproblems, which can be solved globally by efficient branch-and-bound. Together, these methods illustrate how geometric reasoning leads to mathematically principled registration algorithms that can handle million-scale point sets with severe corruption.