Efficient editing of solid models by exploiting structural and spatial locality

Computer aided design systems based on solid modellers must provide fast visual feedback to users when objects are edited. This implies that boundary representations must be updated rapidly, because displays typically are generated in current-generation modellers from face, edge and vertex data.This paper describes algorithms for updating a boundary representation when an object's constructive solid geometry (CSG) representation is edited. The algorithms exploit the structural (representational) locality inherent in most object modifications by taking advantage of previously computed boundary representations for (sub-) objects that are not affected by the editing operations. They also exploit spatial locality by re-computing boundaries only within the spatial region where changes can occur. The algorithms are efficient, and are guaranteed to produce valid solids because they are based on CSG.