We describe geometrical algorithms for interface reconstructions for 3D generalized polyhedral meshes. Three representative piece-wise linear interface calculation methods are considered, namely gradient based method, least squares volume-of-fluid interface reconstruction algorithm, and moment-of-fluid method. Geometric algorithms for the 3D interface reconstructions are described. Algorithm for the intersection of a convex polyhedron with half-space is presented with degenerate cases. Fast iterative methods for volume matching interface computation are introduced. The numerical optimization method for interface normal computation is presented, and its super-linearly convergence is demonstrated. Finally, actual reconstruction of complex geometry is demonstrated.