Automated Offline Programming (AOLP) is an emerging programming paradigm where industrial robot programs are generated from computer models with minimal human effort. Arc welding, such as Gas Metal Arc Welding (GMAW) or Tungsten Inert Gas (TIG), is particularly suited for this application due to the unique retooling requirements. A key aspect of the AOLP process is the determination of accurate welding paths. We present a novel algorithm to extract accurate welding paths for regular or irregular 3D bodies. Our process is computationally inexpensive with processing times less than a second for typical applications. We detail three examples with a range of complexity and examine the accuracy of the results and computational performance.