US Patent 8059122 Cartesian mesh generation technique

A highly accurate and robust cubic cell mesh generator “Cubegen” capable of a trillion plus cell meshes on a single processor 4-Gigabyte main memory workstation has been developed. The cells are generated in Yee format for the Finite Difference Time Domain method. Three key techniques were employed to achieve this capability: a highly efficient data storage ray tracing method, a highly accurate ray-facet intersection test, and a novel exact arithmetic tie-breaking algorithm for rays intersecting facet edges and vertices.