CAD-CAM-CAE

En este artículo presentamos un nuevo método, basado en lógica proposicional, para interpretar y comprender dibujos de objetos poliédricos formados por vértices de tres caras. El objetivo es obtener modelos 3D a partir de proyecciones axonométricas.

La interpretación espacial de líneas de dibujo es un tema estudiado por las comunidades de Visión Artificial y Geometría Estructural. Éstas desarrollan algoritmos para automatizar la obtención de modelos 3D a partir de dibujos 2D tales que, como sucede con la visión humana, sean capaces de rechazar imágenes imposibles.

En este trabajo partiremos del sistema de etiquetado de Huffman [1] y Clowes [2], que asigna a cada línea o arista de una representación axonométrica R una etiqueta que denota si la arista es convexa, cóncava o de frontera u oclusión. El sistema asigna una etiqueta de tipo + a aquellas aristas que son convexas y en las que las caras que concurren en la arista son visibles en la representación R; asigna una etiqueta de tipo - a aquellas aristas que son cóncavas y en las que las caras que concurren en la arista son visibles en la representación R; y asigna una etiqueta de tipo (Æ, ¨) a aquellas aristas en las que únicamente es visible una cara de las que concurren en la arista. Estas últimas serán las aristas frontera y las caras que concurren en la arista presentarán una oclusión.

Por otra parte, en función del número de aristas que concurren en un vértice y su posición en la representación, el sistema de Huffman y Clowes clasifica las uniones en los vértices. Las uniones pueden ser de cuatro tipos: L, Horquilla, T y Flecha. Además, como las aristas que concurren en un vértice tienen etiqueta, estos cuatro tipos de uniones dan lugar a un catálogo que está formado por 18 uniones que representan todas las uniones que son físicamente realizables en una escena poliédrica 3D. Si una proyección axonométrica admite un etiquetado de las aristas consistente con las uniones del catálogo de Huffman y Clowes, entonces podemos obtener un modelo 3D. En cambio, si el etiquetado es inconsistente, la proyección corresponde a un objeto poliédrico 3D físicamente irrealizable.

Dada una representación axonométrica R de un objeto 3D, nuestro método empieza por representar R y las restricciones de las uniones por un conjunto de fórmulas F de la lógica proposicional, de manera que R corresponde a un objeto 3D si, y sólo si, F es satisfactible (es decir, no es contradictorio). A continuación, determina la satisfactibilidad de F utilizando Satz [3], que es un algoritmo de satisfactibilidad que incorpora técnicas de inteligencia artificial. Finalmente, si F es satisfactible, construye un etiquetado correcto del objeto 3D a partir del modelo lógico de F que ha derivado Satz.

En los experimentos hemos observado que nuestro método de obtención de modelos 3D, a partir de proyecciones axonométricas, es una aproximación altamente eficiente desde el punto vista computacional.

[1] D.A. Huffman, "Imposible objects as nonsense senteces", B. Meltzer y D. Michie Ed., Machine Intelligence 6, Edinburgh University Press, 295-323, Edinburg, 1971.

[2] M.B. Clowes, "On seeing things", Artificial Intelligence 2: 79-116, 1971.

[3] Chu Min Li y 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