Obtenció de Models 3D a partir de Projeccions axonomètriques
(1) Departament d'Informàtica i Enginyeria Industrial
Universitat de Lleida, Jaume II, 69, E-25001 Lleida
e-mail: {ramon, alba, felip} @ eup.udl.es
(2) Departament d'Expressió Gràfica a l'Enginyeria
Universitat Politècnica de Catalunya, Av Víctor Balaguer, s / n, 08800 Vilanova i la Geltrú
correu electrònic: membrilla@ege.upc.es
01/12/2002La interpretació espacial de línies de dibuix és un tema estudiat per les comunitats de Visió Artificial i Geometria Estructural. Aquestes desenvolupen algorismes per automatitzar l'obtenció de models 3D a partir de dibuixos 2D tals que, com succeeix amb la visió humana, siguin capaços de rebutjar imatges impossibles.
En aquest treball partirem del sistema d'etiquetatge de Huffman [1] i Clowes [2], que assigna a cada línia o aresta d'una representació axonomètrica R és una etiqueta que denota si l'aresta és convexa, còncava o de frontera o oclusió. El sistema assigna una etiqueta de tipus + a aquelles arestes que són convexes i en què les cares que concorren en l'aresta són visibles a la representació R; assigna una etiqueta de tipus - a aquelles arestes que són còncaves i en què les cares que concorren en l'aresta són visibles en la representació R, i assigna una etiqueta de tipus (Æ, ¨) a aquelles arestes en què únicament és visible una cara de les que concorren en l'aresta. Aquestes últimes seran les arestes frontera i les cares que concorren en l'aresta presentaran una oclusió.
D'altra banda, en funció del nombre d'arestes que concorren en un vèrtex i la seva posició en la representació, el sistema de Huffman i Clowes classifica les unions en els vèrtexs. Les unions poden ser de quatre tipus: L, Forquilla, T i Fletxa. A més, com les arestes que concorren en un vèrtex tenen etiqueta, aquests quatre tipus d'unions donen lloc a un catàleg que està format per 18 unions que representen totes les unions que són físicament realitzables en una escena polièdrica 3D. Si una projecció axonomètrica admet un etiquetatge de les arestes consistent amb les unions del catàleg de Huffman i Clowes, llavors podem obtenir un model 3D. En canvi, si l'etiquetatge és inconsistent, la projecció correspon a un objecte polièdric 3D físicament irrealitzable.
Donada una representació axonomètrica R d'un objecte 3D, el nostre mètode comença per representar R i les restriccions de les unions per un conjunt de fórmules F de la lògica proposicional, de manera que R correspon a un objecte 3D si, i només si, F és satisfactible (és a dir, no és contradictori). A continuació, determina la Satisfactibilitat de F utilitzant Satz [3], que és un algorisme de Satisfactibilitat que incorpora tècniques de IA. Finalment, si F és satisfactible, construeix un etiquetatge correcte de l'objecte 3D a partir del model lògic de F que ha derivat Satz.
En els experiments hem observat que el nostre mètode d'obtenció de models 3D, a partir de projeccions axonomètriques, és una aproximació altament eficient des del punt vista computacional.
Referències
[2] MB Clowes, "On seeing things", Artificial Intelligence 2: 79-116, 1971.
[3] Chu Min Li i Anbulagan, "Heuristics based on unit propagation for satisfiabiliy problems", Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI'97), 366-371, Nagoya (Japan), 1997