Genetic algorithms for optimized re-triangulation in the context of reverse engineering

In reverse engineering, an existing part is first digitized. When a prototype of the digitized data is needed, it can be made by means of rapid prototyping technologies directly from a triangulation of the digitized data without constructing a CAD model. This will be illustrated by the novel method proposed in this article. Firstly, an optimized STL file (the de facto file format for rapid prototyping machines) is constructed directly from digitized part data. In order to reduce storage space and increase computational efficiency for subsequent processes such as slicing, significant data reduction can be achieved by the users' discretion by deleting triangles in planar and near planar regions. Points around the 'blank region' left by deleted triangle are linked through re-triangulation to form triangular facets obeying STL file rules. To obtain optimized re-triangulation result, a genetic algorithm (GA) is developed and implemented. The GA features optimized initial population, constrained crossover operator, constrained mutation operator and multi-objective fitness evaluation function. Finally, experiments on different amount of data reduction over a digitized sample are conducted with satisfactory results. (C) 1999 Elsevier Science Ltd. All rights reserved.