25 - 29 de Noviembre de 2002

Montevideo, Uruguay

Radisson Victoria Plaza Hotel

 
CL44
 
Construcción de Árboles BSP Vía Algoritmos Genéticos

Paul Kienholz
Universidad Central de Venezuela, Escuela de Computación
pakienholz@aol.com
Rhadamés Carmona
Universidad Central de Venezuela, Escuela de Computación
rcarmona@strix.ciens.ucv.ve
Héctor Navarro
Universidad Central de Venezuela, Escuela de Computación
hnavarro@strix.ciens.ucv.ve
 
Abstract

An algorithm to construct Binary Space Partition (BSP) trees based on genetic algorithms was implemented. Traditional methods for constructing BSP trees limit the search to planes obtained from the scene polygons, or parallel to the planes x=0, y=0 or z=0. In our case, to find each partition plane, the genetic algorithm is executed to find the plane's coefficients, without additional restrictions. Time measures were taken with scenes from the Quake III game, and scenes created with Lightwave, that demonstrated on practice that the results obtained using genetic algorithms are superiors than using traditional methods, with an acceptable response time.

Keywords: BSP tree, Genetic Algorithms, Scenes Navigation.

 
Resumen

Se implementó un algoritmo para construir árboles de Partición Binaria del Espacio (BSP) basado en algoritmos genéticos. Los métodos tradicionales de construcción de árboles BSP, limitan la búsqueda a planos obtenidos a través de los polígonos de la escena, o paralelos a los planos x=0, y=0 o z=0. En nuestro caso, para hallar cada plano de partición, se corre el algoritmo genético para encontrar los coeficientes de dicho plano, sin restricciones adicionales. Se realizaron mediciones de tiempo con escenas del juego Quake III, y otras creadas en Lightwave, que demostraron en la práctica que los resultados con algoritmos genéticos son superiores que con métodos tradicionales, con un tiempo de respuesta aceptable.

Palabras Clave: Árbol BSP, Algoritmo s Genéticos, Navegación de Escenas.



Texto completo        Volver

infoUYclei 2002