Extention to multiple 3D scans - Map building.

The calculation of the next best view from multiple 3D scans is an extension to the method described above. Scan matching is used to align the 3D scans to calculate the precise scan position. Polygons are calculated from each single 3D scan and aligned with the precise position. A modified version of Vatti's polygon clipping algorithm [13] is used to merge the polygons. The modification is necessary to ensure the labeling of the edges (seen, unseen), while creating the union of the polygons (fig. 3). A new 3D scan is clipped against the union of the previous scans.

The performance of the proposed planning module can be estimated as follows: The first step converts data points into lines. The Hough transform runs in $O(d^2)$ ($d$ is the maximal distance of a data point in a single 3D scan). Generating candidate points is done in $O(n_c n_l)$ and their evaluation is also in $O(n_c n_l)$ ($n_c$ is the number of candidates and $n_l$ the number of lines). Vatti's polygon clipping algorithm runs in $O(n_p)$ ( $n_p$ is the sum of edges of both polygons). The whole planning algorithm takes on scenes of $20m \times 30m$ up to 2 seconds, running on a Pentium-III-800.

Figure 4: Left: Canidate positions in the map as generated in fig. 3. Right: A trajectory to a candidate position cannot be taken since the path intersects a bounding box of an object (fig. 2).