Christopher Fox, H. Edwin Romeijn, James F. Dempsey
Fast voxel and polygon ray-tracing algorithms for IMRT treatment planning
We present algorithms that significantly outperform the polygon and voxel ray-tracing algorithms of Siddon for voxel classification (point-in-polygon testing) and dose computation, respectively. With the emergence of adaptive intensity modulated radiation therapy (IMRT), rapid computation of dose and classification of voxels for membership in targets and structures is desired to enable immediate fluence map optimization (FMO). Existing algorithms that deal with these issues can result in unacceptably long computational times when a large voxel space is required to accurately model the patient dosimetry. The polygon ray-tracing algorithm of Siddon spends substantial computational time calculating cross products between polygon vertices and grid points to establish intersection points. The algorithm we present avoids computing cross products by translating the polygons so that rays are cast along, e.g., the +X axis (assuming polygons lie in X-Y planes). Ray-polygon intersections are then observed where consecutive vertices display change in Y coordinate sign and the ray coincides with the polygon boundary when the Y value equals zero. Further, this enables classifying an entire row of a regular 3D grid of points together using the intersections of a single ray and polygon. The majority of the computational time required by the standard Siddon voxel ray-tracing algorithm was found to be in the concatenation of the intersection parameters into a single unique ordered set and determination of intersected voxel indices. To overcome this inefficiency, we present an incremental voxel ray-tracing algorithm that simultaneously computes ordered sets of voxel indices and ray-voxel intersections. Furthermore, a method of virtual stereographic projection was employed with the incremental voxel ray-tracing to allow for down sampling voxel data in close proximity of projected IMRT beamlets. Our new polygon ray-tracing technique was tested on an IMRT treatment planning case that required the classification of 1.7 million voxels on a 2.5 mm isotropic dose grid into 2 targets and 12 structures represented as extruded polygons (a.k.a. Siddon prisms). Incremental voxel ray tracing and voxel down sampling employing virtual stereographic projection was tested on the same IMRT treatment planning case where voxel dose was required for 1,466 beamlets using a finite size pencil beam algorithm in computational time. A 100 fold cpu time improvement (2.1 vs. 213 s on a 3.6 GHz p4 PC) over Siddon’s method was observed for the polygon ray-tracing algorithm to perform classification of voxels for target and structure membership. A 2.7 fold reduction (an average of 1.3 vs. 3.5 s/beamlet) in cpu time over current algorithms was found for the implementation of incremental ray tracing and an additional 1.8 fold improvement (185.2 vs. 334.5 s) was observed for virtual stereographic projection voxel down sampling, yielding a combined improvement of 4.86 fold. We present the first significant improvements in performance over the algorithms of Siddon, which were published in the middle 1980s. The efficiency of these new algorithms should help enable IMRT planning for adaptive image-guided radiation therapy.