Abstract : We present a method to automatically compute a decomposition of a polygonal scene into a simple cell-and-portal graph. The resulting cell-and-portal graph satisfies the following user-defined constraints: an upper bound on the rendering cost of each cell, and lower or upper bounds on the size of each cell. This is useful to achieve real-time rendering of large indoor models, and is especially suited to architectural walk-throughs and game engines. Our method relies on a binary space-subdivision preprocessing step, then on a portal grouping algorithm that selects or rejects portals generated by the subdivision. Finally the cell-and-portal graph (CPG) is built and post-processed to satisfy the constraints on the cells. We also propose a metrics for measuring the quality of portals, which is used to guide the post-processing. Furthermore, our simplification algorithm can be used on any CPG in order to reduce its complexity according to a user threshold. We present both a general algorithm and a complete implementation with practical details. Results show that portals created by our method have good geometrical properties (e.g. they often lie on doors and windows). The generated decomposition can be used for online occlusion culling.