we propose a coverage planning algorithm for inspecting large complex structure using a UAV. Inspecting structures (e.g. bridges, ships, wind turbines, aircrafts) is considered a hard task for humans to perform, and of critical nature since missing any detail could affect the structure’s performance and integrity. Additionally, structure inspection is a time and resource intensive task that should be performed as efficiently and accurately as possible. In the paper, we introduce a search space coverage path planner (SSCPP) with a heuristic reward function that exploits our knowledge of the structure model, and the UAV’s onboard sensors’ models to generate optimal paths that maximizes coverage and accuracy, and minimizes travelled distance and turning angle. Our method follows a model based coverage path planning approach to generate an optimized path that passes through a set of admissible waypoints to cover a complex structure. The algorithm provides a prediction of the covered volume percentage by using an existing model of the complex structure as a reference. Critical components of the algorithm were accelerated utilizing the Graphics Processing Unit (GPU) parallel architecture. A set of experiments was conducted in a simulated environment using different models to test the validity of the proposed algorithm.