The All-k-Nearest-Neighbor (AkNN) operation is common in many applications such as GIS and data analysis/mining. In this paper, for the first time, we study a novel variant of AkNN queries, namely All-Visible-k-Nearest-Neighbor (AVkNN) query, which takes into account the impact of obstacles on the visibility of objects. Given a data set P, a query set Q, and an obstacle set O, an AVkNN query retrieves for each point/object in Q its visible k nearest neighbors in P. We formalize the AVkNN query, and then propose efficient algorithms for AVkNN retrieval, assuming that P, Q, and O are indexed by conventional data-partitioning indexes (e.g., R-trees). Our approaches employ pruning techniques and introduce a new pruning metric called VMDIST. Extensive experiments using both real and synthetic datasets demonstrate the effectiveness of our presented pruning techniques and the performance of our proposed algorithms.