ISSN 0718-3291 Versión Impresa

ISSN 0718-3305 Versión en línea

Volumen 17 N° 2, Mayo - Agosto 2009

pdf Índice

Preservación automática de discontinuidades de superficie basada en la estimación de la torsión de curvas de contorno para la reconstrucción de objetos tridimensionales

Germán Sánchez Torres1                    John William Branch2

  

1 Universidad del Magdalena. Facultad de Ingeniería. Programa de Sistemas. Santamarta. Colombia. E-mail: gsanchez@unimagdalena.edu.co
2 Universidad Nacional de Colombia. Escuela de Sistemas e Informática. Medellín, Colombia. E-mail: jwbranch@unalmed.edu.co


RESUMEN 

Los diferentes métodos de ajuste de superficies desde datos dispersos asumen que la superficie reconstruida no presenta ningún tipo de discontinuidad. Las discontinuidades en las superficies son obtenidas a partir de la forma del objeto original y estas aparecen principalmente en el proceso de adquisición debido a problemas de oclusión. Tradicionalmente, para la representación de superficies que tienen discontinuidades se realiza un proceso manual adicional después de la etapa final de ajuste. En este artículo se propone un método para detectar y preservar discontinuidades automáticamente en superficies de topología arbitraria, así como un método para la reducción de los puntos a interpolar, que permite disminuir el costo computacional asociado a la solución del interpolante. Inicialmente, el método realiza una clasificación basada en la estimación de la varianza de la torsión de la curva del contorno. Cuando el valor de la varianza en el contorno de los huecos es muy bajo, entonces se considera que este hueco debe ser preservado. Luego, la superficie descrita por el conjunto de puntos seleccionados es interpolada usando Funciones de Base Radial. Por último, la superficie generada es cortada con cada contorno identificado como preservable.

Palabras clave: Reconstrucción de superficies, funciones de base radial, datos de rango, estrategia evolutiva.

 

ABSTRACT  

Different methods for fitting surfaces from dispersed data interpolation assume the reconstructed surface does not have any type of discontinuity. Discontinuities in the surfaces are obtained from the original shape of the object and they appear mainly in the acquisition process due to occlusion problems. For digital representation of surfaces with discontinuities is commonly found an additional manual process, which is applied after the final stage of fitting surface. In this paper, two methods are proposed, one of them with the aim of  detect and preserve discontinuities in surfaces with arbitrary topology, and the other one to reduce the amount of points to be interpolated, decreasing the computational cost. Initially, the method carries out a classification based on estimation of the torsion variance of the contour curve. When the holes contour has very low values of variances, it is considered that this hole must be preserved. Then, the surface described by the selected set of points is interpolated using Radial Basis Functions. Finally, the generated surface is trimmed with each contour identified like preservable.

Keywords: Surface reconstruction, radial basis functions, range data, evolutionary strategy.


REFERENCIAS 

[1] A. Arge. "Approximation of scattered data using smooth grid functions". Technical Report STF33 A94003, SINTEF. 1994.

[2] H.G. Barrow, J.M. Tanenbaum. "Interpreting line drawings as three-dimensional surfaces". Proc. of AAAI-80, pp. 11 – 14. Stanford, CA. 1980.

[3] B. Baxter. "The Interpolation Theory of Radial Basis Functions". PhD thesis, Trinity College. 1992.

[4] R.K. Beatson. "Fast solution of the radial basis function interpolation equations: Domain decomposition methods". Proceedings of ACM SIGGRAPH. 2005.

[5] P. Blicher. "From images to surfaces: A computational study of the human early visual system". Mit press. SIGART Bull. Vol. 82, pp. 12-14. 1982.

[6] T. Boult and J. Kender. "Visual surface reconstruction using sparse depth data". CVPR86, pp. 68-76. 1986.

[7] M. Buhmann. "Multivariate interpolation in odd-dimensional Euclidean spaces using multiquadrics". Const. Approx. Vol. 6, pp. 21-34. 1990.

[8] M. Buhmann. "Radial Basis Functions: Theory and Implementations". Cambridge University Press. 2003.

[9] J. Carr. "Reconstruction and representation of free-form objects with radial basis function". 2001.

[10] J. Carr, R. Beatson, B. McCallum, W. Fright, T. McLennan and T. Mitchell. "Smooth surface reconstruction from noisy range data". GRAPHITE ’03: Proceedings of the 1st international conference on Computer graphics and interactive techniques in Australasia and South East Asia, pp. 119-ff. New York, NY, USA. ACM Press. 2003.

[11] R. Carlson and B. Natarajan. "Sparse approximate multiquadric interpolation". Computers and Mathematics with Applications. Vol. 26, pp. 99-108. 1994.

[12] J. Duchon. "Spline minimizing rotation-invariant seminorms in sobolev spaces". Constructive Theory of Functions of several Variables. Vol. 571, pp. 85-100. 1997.

[13] M. Floater and A. Iske. "Multistep scattered data interpolation using compactly supported radial basis functions". Journal of Comp. Appl. Math. Vol. 73, pp. 65-78. 1996.

[14] F. Girosi. "Some extensions of radial basis functions and their applications in artificial intelligence". Computers and Mathematics with Applications. Vol. 24 Nº 12, pp. 61-80. 1992.

[15] W. Grimson. "From Images to Surfaces: A Computational Study of the Human Early Visual System". MIT Press, Cambridge, MA. 1981.

[16] N. Kojekine and V. Savchenko. "Surface reconstruction based on compactly supported radial basis functions". Geometric modeling: techniques, applications, systems and tools, pp. 218-231. Kluwer Academic Publishers. 2004.

[17] D. Marr and T. Poggio. "A theory of human stereo vision". Technical report, Cambridge, MA, USA. 1997.

[18] McMahon and R. Franke. "Knot selection for least squares thin plate splines". SIAM Journal on Scientific and Statistical Computing. Vol. 13 Nº 2, pp. 484-498. 1992.

[19] Y. Ohtake. "3D scattered data approximation with adaptive compactly supported radial basis functions". In SMI ’04: Proceedings of the Shape Modeling International 2004 (SMI’04). IEEE Computer Society, pp. 31-39. Washington, D. C., USA. 2004.

[20] M. Powell. "The theory of radial basis function approximation", in Advances in Numerical Analysis II, W.A. Light, ed., Clarendon Press, Oxford, pp. 105. 1990.

[21] K. Salkauskas. "Moving least squares interpolation with thin-plate splines and radial basis functions". Computers and Mathematics with Applications. Vol. 24 Nº 12, pp. 177–185. 1992.

[22] R. Schaback. "Creating surfaces from scattered data using radial basis functions". In M. Daehlen, T. Lyche, and L. L. Schumaker, editors, Mathematical Methods in AGD III. Vanderbilt Press. 1995.

[23] H. Wendland. "Piecewise polynomial, positive definite and compactly supported radial functions of minimal degree". Advances in computational Mathematics 4, pp. 389-396. 1995.

[24] G. Sánchez. "Selección de centros de Interpolación de funciones de Base Radial para el Ajuste de superficies de Objetos de forma libre". CLEI-XXXII Conferencia Latinoamericana de Informática. Santiago de Chile, Chile. Agosto de 2006.

[25] N. Amenta, M. Bern and M. Kamvysselis. "A new voronoi-based surface reconstruction algorithm". Proceedings of the SIGGRAPH’98, pp. 415-421. 1998.

[26] M. Gopi and S. Krishnan. "A fast and efficient projection based approach for surface reconstruction". International Journal of High Performance Computer Graphics, Multimedia and Visualisation. Vol. 1 Nº 1, pp. 1-12. 2000.

[27] H. Hoppe, T. DeRose, T. Duchamp, J.A. McDonald and W. Stuetzle. "Surface reconstruction from unorganized points". Proceedings of the IGGRAPH’92, pp. 71-78. 1992.

[28] G. Farin. "Curves And Surfaces For Computer Aided Geometric Design". A Practical Guide.  Academic Press, Inc. ISBN 0-12-249052-5. 1993.

[29] I.D. Faux and M.J. Pratt. "Computational Geometry for Design and Manufacture". Ellis Horwood Ltd, Publishers. ISBN 0-85312-114-1. 1979.

[30] M. Pauly, M. Gross and L. Kobbelt. "Efficient simplification of point-sampled surfaces". In: Proceedings of IEEE visualization 2002, pp. 163-170. 2002.

[31] J. Branch, F. Prieto and P. Boulanger. "Automatic Hole-Filling of Triangular Meshes Using Local Radial Basis Function". In Proceedings of the Third international Symposium on 3D Data Processing, Visualization, and Transmission (3dpvt'06). 3DPVT. IEEE Computer Society, Washington, DC, 727-734. June 14 - 16, 2006.

[32] Brian Curless and Marc Levoy. "A volumetric method for building complex models from range images". In SIGGRAPH '96: Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, pp. 303-312, New York, NY, USA. ACM Press. 1996.


Recibido 8 de abril de 2008, aceptado 30 de marzo de 2009


Artículos Relacionados

# Título Ver
1
Reducción de características usando una red tipo RBFpara clasificar estilos de aprendizaje en estudiantes de primer año de ingeniería (2014)
Oswaldo Velez-Langs
HTML | PDF


Otros Artículos

# Título Ver
1
Enrutamiento y asignación de longitud de onda: una solución con búsqueda Tabú en tráfico dinámico (2014)
Arturo Rodríguez García, Leonardo Ramírez López, Luis Rivera Méndez, Antonio Gutiérrez Osorio
HTML | PDF
2
Selección determinística y cruce anular en algoritmos genéticos: aplicación a la planificación de unidades térmicas de generación (2009)
Boris Pavez-Lazo, Jessica Soto-Cartes, Carlos Urrutia, Millaray Curilem
HTML | PDF
3
Integracion de una celula flexible de mecanizado, de tipo docente (2007)
Abraham Farias F., Luis Moraga G., Ambrosio Martinich L.
HTML | PDF

Desarrollado por: Cristian Díaz Fonseca - cfonseca@matiasluke.cl