Mesh optimization for surface approximation using an efficient coarse-to-fine evolutionary algorithm

✍ Scribed by Hui-Ling Huang; Shinn-Ying Ho

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 901 KB
• Volume: 36
• Category: Article
• ISSN: 0031-3203
• DOI: 10.1016/s0031-3203(02)00113-9

✦ Synopsis

The investigated mesh optimization problem C(N; n) for surface approximation, which is NP-hard, is to minimize the global error between a digital surface and its approximating mesh surface by e ciently locating a limited number n of grid points which are a subset of the original N sample points. This paper proposes an e cient coarse-to-ÿne evolutionary algorithm (CTFEA) with a novel orthogonal array crossover (OAX) for solving the mesh optimization problem. OAX adaptively divides the meshes of parents into a number of parts using a tuning parameter for applying a coarse-to-ÿne technique. Meshes of children are formed from an intelligent combination of the good parts from their parents rather than the conventional random combination. The better one of two parts in two parents is chosen by evaluating the contribution of the individual parts to the ÿtness function based on orthogonal experimental design. The coarse-to-ÿne technique of CTFEA can advantageously solve large mesh optimization problems. Furthermore, CTFEA using an additional inheritance technique can further e ciently locate the grid points in the mesh surface. It is shown empirically that CTFEA outperforms the existing evolutionary algorithm in terms of both approximation quality and convergence speed, especially in solving large mesh optimization problems.