Proceedings: GI 1997

A heuristic method for generating 2D CSG trees from bitmaps

Sarah Gibson, Joe Marks, Danielle Feinberg, Manuel Sosa

Proceedings of Graphics Interface '97: Kelowna, British Columbia, Canada, 21 - 23 May 1997, 163-172

DOI 10.20380/GI1997.19

  • BibTeX

      title = {A heuristic method for generating {2D CSG} trees from bitmaps},
      author = {Sarah F. Gibson and Joe Marks and Danielle Feinberg and Manuel Sosa},
      booktitle = {Proceedings of the Graphics Interface 1997 Conference, May 21-23, 1997, Kelowna, BC, Canada},
      year = {1997},
      month = {May},
      pages = {163--172},
      url = {}


This paper presents a method for generating compact and effective constructive-solid-geometry (CSG) object representations from 2D bitmap representations. The method consists of two parts: a stochastic search procedure for finding candidate CSG trees and a local optimization procedure that modifies the primitives of a given CSG tree to effect a better match. Results for several sample input bitmaps are presented and an application of this method to automatic geometric morphing between pairs of bitmaps is shown.