The overall aim of the authors' work is to create a computer aid to support the macroplanning of five-axis parts, and in this context this paper presents the methodology developed to enable the determination of set-up orientations on five-axis machine-tools. The process starts with an access model that encompasses all the machining directions encountered in five-axis operations. Then an enhanced visibility-based modeling and algorithm are proposed in order to solve accessibility constraints while planning the setups for double-sided parts. The proposed algorithm is illustrated on an industrial aircraft structural part. To conclude, options to integrate the proposed method in a computer assisted process planning system are discussed. [DOI: 10.1115/1.3243632]