Código Fuente para encontrar caras (Finding Faces)

Abril 2010

Estamos interesados en crear herramientas basadas en computador para ayudar a los ingenieros
de diseño durante la primera etapa del proceso de diseño, conocida como diseño conceptual.
Por tanto, desarrollamos sistemas de modelado basado en bocetos (SBM por sus siglas en inglés).
Nuestra aproximación al SBM se basa en encontrar indicios o regularidades, que son aquellas
propiedades del boceto que revelan propiedades del objeto tridimensional representado en el boceto.
En este contexto, las caras son indicios. En concreto, el algoritmo para encontrar-caras que
consideramos aquí (FF) está encaminado a encontrar circuitos de líneas que representan caras
de la forma poligonal representada en representaciones mediante modelos de alambres de
objetos poliédricos.

Se adjunta una implementación en C++ del código del nuevo algoritmo FF.

Usted puede descargar el código de FF desde aquí.

Aunque muchos de los indicios están relacionados mutuamente, nosotros intentamos detectar
cada indicio usando información mínima. Para que FF funcione, el boceto de entrada debe haber
sido previamente vectorizado, para convertir los trazos del boceto en líneas del dibujo lineal.
Por tanto, la entrada para el código es un dibujo 2D, que incluye una lista de vértices y ejes
en el siguiente formato:

· Las coordenadas de cada vértice se guardan en una instancia de la clase POINT2D.
El conjunto de todos los vertices se guarda en un vector estándar (std::vector <POINT2D>Vertex)

o VertexCount= número de vertices del dibujo lineal

o VertexX[i]= coordenada X del i-esimo vértice

o VertexY[i]= coordenada Y del i-esimo vértic

· Las aristas se definen mediante sus vértices de cabeza y cola. El conjunto de todas
las cabezas de aristas se guarda en un vector estándar (std::vector <long> EdgeU)
y el conjunto de todas las colas de aristas se guarda en otro vector estándar (std::vector <long> EdgeV):

o EdgeCount= número de aristas del dibujo lineal

o EdgeU[i]= Vértice de cabeza que define a la i-esima arista

o EdgeVl[i]= Vértice de cola que define a la i-esima arista

El lector debe notar que la vectorización del boceto requerida para que funcione éste método
incluye la fusión previa de los extremos de todas las aristas que comparten vértices de la forma
poliédrica (fusionando en un único vértice todos los extremos de aristas que son percibidos
por los seres humanos como una esquina o unión común).

La salida es un conjunto de listas de líneas del dibujo, cada una listando las líneas que pertenecen
a una cara particular de la forma representada en el dibujo. El conjunto de listas de vertices que
pertenecen a cada cara se devuelve también.

· La información se guarda en un vector de instancias de la clase FACE,
(std::vector <FACE> Face), donde cada instancia FACE incluye:

int C= úmero de aristas/vertices que definen la cara
std::vector <int> E= Lista de aristas que defien la cara
std::vector <int> V= Lista de vertices que definen la cara

El método está encapsulado dentro de una clase principal CFacesVarley, que comparte fichero
con algunas clases auxiliares (CueFacesVarley.cpp). Se incluyen, además, otros tres ficheros
auxiliares (CueFacesV.Geometry.cpp, CueFacesV_Nuts.cpp and CueFacesV_Ortholin.cpp).

Este método para encontrar caras se describe extensamente en:

Varley P.A.C. and Company P. (2010).
A new algorithm for finding faces in wireframes.
Computer-Aided Design, 42(4), pages 279-309.

Para ayudar a entender cómo funciona el código, y para ofrecer un entorno de prueba,
se suministra también el siguiente fichero:

· Main.cpp, y su fichero de encabezamiento Main.h.

Finalmente, queremos remarcar que el código fue escrito para hacerlo legible. La eficiencia
nunca fue un objetivo.

******************************************************************************************************************

El código FF es software libre. Pero si usted lo encuentra útil para su propia investigación,
por favor cite nuestro artículo:

Varley P.A.C. and Company P. (2010).
A new algorithm for finding faces in wireframes.
Computer-Aided Design, 42(4), pages 279-309.

*******************************************************************************************************************