An efficient algorithm to construct reduced visibility graph and its FPGA implementation

Abstract

An important geometric structure used in robotic path planning and computer graphics is the visibility graph. In this paper, we present a new parallel algorithm to construct the reduced visibility graph that is appropriate for finding shortest paths in a convex polygonal environment. A key feature of the algorithm is that it supports easy mapping to hardware. The computational complexity is O(p/sup 2/+log((n/p)/sup 2/)) where p is the number of objects and n is the total number of vertices. An efficient FPGA implementation of the algorithm is presented. The design operates at approximately 48 Mhz. Further, the implementation for an environment with roughly 60 vertices requires 90% of an XCV3200E.