A 3D Rapid, GlObally Optimal Surface Estimation (R-GOOSE) algorithm for fat-water decomposition in MRI is proposed. The fat-water separation is formulated as an optimization problem with data consistency and field-map smoothness penalty. The data consistency only contains exact minimizers from the fully discretized field-map value volume. The proposed method employs a connectivity-reduced graph construction that enables the new formulation to be solved efficiently. The method is validated by the 17 datasets from the 2012 ISMRM Challenge with thirty-fold computational gain compared to our previous method GOOSE while the high quantitative accuracy is maintained. Fat fraction maps obtained from the proposed method also provides a good marker for degenerative muscle diseases in newly collected lower limb datasets.