| This dissertation presents novel dose computation algorithms based on the use of spatial data structures derived from octrees and quadtrees. This data structure makes approximate dose computation possible. Our methods approximate the scatter effect due to a cluster of proximate points which are far away from the point of interest. The scatter effect of the cluster is approximated by the scatter effect due to a single point at the center of this cluster.; To compute dose contribution from one point to another point, ray tracing is performed to compute radiological distance between two points. We used a region growing scheme to reduce the number of regions: That decreases the number of intersection points. This region growing scheme using three dimensional real computed tomography (CT) data could eliminate about 80 percent of the regions produced by a regular region partitioning scheme, which is a variant of the octree based scheme.; For region growing, an efficient binary search tree scheme with supernodes that have multiple elements has been developed. It is shown that this supernode scheme is better than binary search trees with single element nodes in terms of space efficiency and run time performance.; Our experimental results of dose computation on homogeneous phantoms show that the resultant algorithm is two to three orders of magnitude faster than the collapsed cone algorithm while achieving similar levels of accuracy. |
