Patent ID: 7483787

Claim:
A method of determining intersections of a multi-segment three-dimensional path with boundaries of one or more volumes comprising a partitioned three-dimensional space, said method comprising: determining whether a current point of a current segment of the path is included within one of the volumes; when the current point of the current segment is determined to be within a volume: establishing the volume including the current point of the current segment as a current volume; and determining whether the current segment intersects a boundary of the current volume at a location on the current segment between the current point and an end point of the current segment; when the current segment is determined to intersect a boundary of the current volume: setting the location of the current segment where the current segment intersects a boundary of the current volume as an exit point of the path from the current volume; adjusting the current point of the current segment to the exit point of the path from the current volume; identifying a volume adjacent to the boundary of the current volume including the exit point of the path from the current volume; setting the location of the current segment where the current segment intersects a boundary of the adjacent volume as an entry point of the path into the adjacent volume; changing the current volume to the adjacent volume; and returning to said step of determining whether the current segment intersects a boundary of the current volume.