Abstract
We investigate three-dimensional visibility problems for scenes that consist of n non-intersecting spheres. The viewing point moves on a flightpath that is part of a “circle at infinity” given by a planeP and a range of angles {α(t)¦tε[0∶1]} ⊂ [0∶2π]. At “time”t, the lines of sight are parallel to the ray inP, which starts in the origin ofP and represents the angleα(t)(orthographic views of the scene). We give an algorithm that computes the visibility graph at the start of the flight, all time parameters at which the topology of the scene changes, and the corresponding topology changes. The algorithm has running time 0(n + k + p) logn), where n is the number of spheres in the scene; p is the number of transparent topology changes (the number of different scene topologies visible along the flight path, assuming that all spheres are transparent); andk denotes the number of vertices (conflicts) which are in the (transparent) visibility graph at the start and do not disappear during the flight.
