More Web Proxy on the site http://driver.im/

article

Constraint-based beautification and dimensioning of 3D polyhedral models reconstructed from 2D sketches

Authors:

Y. T. LeeAuthors Info & Claims

Computer-Aided Design, Volume 39, Issue 11

Pages 1025 - 1036

https://doi.org/10.1016/j.cad.2007.08.002

Published: 01 November 2007 Publication History

Abstract

3D models reconstructed from 2D sketches are inaccurate because of the inherent inaccuracies in the input and the reconstruction method. It is therefore necessary to ''beautify'' them before use in CAD systems. We present a method that detects geometric constraints, such as parallel and orthogonal faces, present in the reconstructed model and then selects a subset that constrains the object sufficiently and consistently. The subset selection algorithm first prioritizes the constraints depending on their type and then uses a novel method, based on quasi-Newton optimization, to detect and eliminate redundant and inconsistent constraints. The remaining constraints then define the dimensions of the model fully and consistently. Results from our implementation show that the method can beautify and dimension recovered 3D models correctly at acceptable speed.

References

[1]

Marill, T., Emulating the human interpretation of line drawings as three-dimensional objects. Computer Vision. v6 i2. 147-161.

[2]

Lipson, H. and Shpitalni, M., Optimization-based reconstruction of a 3D object from a single freehand line drawing. Computer-Aided Design. v28 i8. 651-663.

[3]

Liu, J. and Lee, Y.T., A Graph-based method for face identification from a single 2D line drawing. IEEE Transaction on Pattern Analysis and Machine Intelligence. v23 i10. 1089-1106.

[4]

Varley PAC. Automatic creation of boundary-representation models from single line drawings. PhD thesis. Cardiff University; 2002

[5]

Langbein, F.C., Marshall, A.D. and Martin, R.R., Choosing consistent constraints for beautification of reverse engineered geometric models. Computer-Aided Design. v36 i3. 261-278.

[6]

Chen XC. Planarity correction for object constructed from line drawings. Master thesis. Singapore: Nanyang Technological University; 2002

[7]

Wilczkowiak, M., Trombettoni, G., Jermann, C., Sturm, P.F. and Edmond, B., Scene modeling based on constraint system decomposition techniques. In: International conference on computer vision, pp. 1004-1010.

[8]

Martínez, M.L. and Félez, J., A constraint solver to define correctly dimensioned and over-dimensioned parts. Computer-Aided Design. v37 i13. 1353-1369.

[9]

Buchanan, S.A. and de Pennington, A., Constraint definition system: A computer-algebra based approach to solving geometric-constraint problems. Computer-Aided Design. v25 i12. 741-750.

[10]

Gao, X.S. and Chou, S.C., Solving geometric constraint systems. II, a symbolic approach and decision of rc-constructibility. Computer-Aided Design. v30 i2. 115-122.

[11]

Wu, W.-T., Mechanical theorem proving in geometries. 1994. Springer-Verlag Inc., New York, USA.

[12]

Fudos I. Constraint solving for computer aided design. Ph.D. thesis. West Lafayette (IN, USA): Purdue University; 1998

[13]

Owen J. Algebraic solution for geometry from dimensional constraints. In: ACM symposium on foundations of solid modeling, 1991. p. 397-407

Digital Library

[14]

Bouma, W., Fudos, I., Hoffmann, C.M., Cai, J. and Paige, R., A geometric constraint solver. Computer-Aided Design. v27 i6. 487-501.

[15]

Joan-Arinyo R, Soto-Riera A, Vila-Marta S, Vilaplana J. Transforming an under-constrained geometric constraint problem into a well-constrained one. In: Proceedings of the eighth ACM symposium on solid modeling and application, 2003. p. 33-44

Digital Library

[16]

Latham, RS and Middleditch, AE, Connectivity analysis: A tool for processing geometric constraints. Computer-Aided Design. v28 i11. 917-928.

[17]

Hoffmann, C.M., Lomonosov, A. and Sitharam, M., Decomposition plans for geometric constraint systems, part I: Performance measures for CAD. Journal of Symbolic Computation. v31 i4. 367-408.

[18]

Li, Y.T., Hu, S.M. and Sun, J.G., A constructive approach to solving 3-D geometric constraint systems using dependence analysis. Computer-Aided Design. v34 i2. 97-108.

[19]

Kramer, G., Solving geometric constraint systems. 1992. MIT Press, Cambridge (MA, USA).

[20]

Jermann C, Neveu B, Trombettoni G. A new structural rigidity for geometric constraint systems. In: Proceedings of the 4th international workshop on automated deduction in geometry. 2002. p. 87-106

[21]

Jermann C, Neveu B, Trombettoni G. Algorithms for identifying rigid subsystems in geometric constraint systems. In: Proceedings of the eighteenth international joint conference on artificial intelligence. 2003. p. 233-8

[22]

Hoffmann, C.M., Lomonosov, A. and Sitharam, M., Geometric constraint decomposition. In: Bruderlin, B., Roller, D. (Eds.), Geometric constraint solving and applications, Springer, Berlin. pp. 170-195.

[23]

Zou, H.L. and Lee, Y.T., Detecting minimum over-constrained subgraphs in 2D and 3D based on degree of freedom analysis. Computer-Aided Design and Applications. v2. 393-402.

[24]

Pappas, T., Pappus' theorem & the nine coin puzzle. In: The joy of mathematics, Wide World Publishing, San Carlos (CA).

[25]

Light, R. and Gossard, D.C., Modification of geometric models through variational geometry. Computer-Aided Design. v14 i4. 209-214.

[26]

Chou, S.C., Mechanical geometry theorem proving. 1987. Kluwer Academic Publishers, Norwell (MA).

[27]

Buchberger, B., Grobner bases: An algorithmic method in polynomial ideal theory. In: Bose, N.K. (Ed.), Multidimensional systems theory, D. Reidel Publishing Co.

[28]

Buchberger B. Groebner bases: A short introduction for systems theorists. In: EUROCAST 2001 (8th international conference on computer aided systems theory - formal methods and tools for computer science). 2001

[29]

Li, Y.T., Hu, S.M. and Sun, J.G., On the numerical redundancies of geometric constraint systems. In: Proceedings of Pacific graphics 2001, IEEE Computer Society Press, Tokyo. pp. 118-123.

[30]

Langbein FC, Marshall AD, Martin RR. Numerical methods for beautification of reverse engineered geometric models. In: Proceedings of the geometric modeling and processing - theory and applications. 2002. p. 159-68

[31]

Everitt, B., Cluster analysis. 1986. 2nd ed. Heinemann Educational Books Ltd., London.

[32]

http://www.cs.sandia.gov/opt/survey/main.html

[33]

Deb, K., Optimization for engineering design: Algorithms and examples. 1995. Prentice-Hall, India.

[34]

Paige, C.C. and Saunders, M.A., Algorithm 583: LSQR: Sparse linear equations and least squares problems. ACM Transactions on Mathematical Software. v8 i2. 195-209.

[35]

Golub, G.H. and Van Loan, C.F., . In: Baltimore, M.D. (Ed.), Matrix computations, Johns Hopkins University Press.

[36]

Bischof, C.H. and Quintana-Orti, G., Computing rank-revealing QR factorizations of dense matrices. ACM Transactions on Mathematical Software. v24 i2. 226-253.

[37]

Mathworks. Matlab - The language of technical computing. 2006 {cited 17 Oct.}; Available from: http://www.mathworks.co.uk/products/matlab/

[38]

Langbein FC. Beautification of reverse engineered geometric models. Ph.D. thesis. UK: Cardiff University; 2003

[39]

Gao, X.S., Lin, Q. and Zhang, G., A C-tree decomposition algorithm for 2D and 3D geometric constraint solving. Computer-Aided Design. v38 i1. 1-13.

[40]

Hoffmann, C.M., Lomonosov, A. and Sitharam, M.J., Decomposition plans for geometric constraint problems, part II: New algorithms. Symbolic Computation. v31 i4. 409-427.

[41]

Sitharam, M., Combinatorial approaches to geometric constraint solving: Problems, progress, directions. In: Janardan, R., Smid, M., Dutta, D. (Eds.), AMS-DIMACS series in discrete mathematics and computer science, vol. 67. pp. 117-164.

Cited By

Wang SZhang QWang SJing XGao M(2020)Endpoint fusing method of online freehand-sketched polyhedronsThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-018-1608-536:2(291-303)Online publication date: 1-Feb-2020
https://dl.acm.org/doi/10.1007/s00371-018-1608-5
Changqing Zou Shifeng Chen Hongbo Fu Jianzhuang Liu (2015)Progressive 3D Reconstruction of Planar-Faced Manifold Objects with DRF-Based Line Drawing DecompositionIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2014.235403921:2(252-263)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1109/TVCG.2014.2354039
Liu YLee Y(2012)Optimization-based freeform shape reconstruction3D Research10.1007/3DRes.03(2012)33:3(1-6)Online publication date: 1-Sep-2012
https://dl.acm.org/doi/10.1007/3DRes.03%282012%293
Show More Cited By

Index Terms

Constraint-based beautification and dimensioning of 3D polyhedral models reconstructed from 2D sketches

Recommendations

Interactive beautification: a technique for rapid geometric design
SIGGRAPH '07: ACM SIGGRAPH 2007 courses

We propose interactive beautification, a technique for rapid geometric design, and introduce the technique and its algorithm with a prototype system Pegasus. The motivation is to solve the problems with current drawing systems: too many complex commands ...
Interactive beautification: a technique for rapid geometric design
SIGGRAPH '06: ACM SIGGRAPH 2006 Courses

We propose interactive beautification, a technique for rapid geometric design, and introduce the technique and its algorithm with a prototype system Pegasus. The motivation is to solve the problems with current drawing systems: too many complex commands ...
Interactive beautification: a technique for rapid geometric design
UIST '97: Proceedings of the 10th annual ACM symposium on User interface software and technology

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computer-Aided Design

Computer-Aided Design Volume 39, Issue 11

November, 2007

111 pages

ISSN:0010-4485

Issue’s Table of Contents

Copyright © Elsevier Ltd © 2007.

Publisher

Butterworth-Heinemann

United States

Publication History

Published: 01 November 2007

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang SZhang QWang SJing XGao M(2020)Endpoint fusing method of online freehand-sketched polyhedronsThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-018-1608-536:2(291-303)Online publication date: 1-Feb-2020
https://dl.acm.org/doi/10.1007/s00371-018-1608-5
Changqing Zou Shifeng Chen Hongbo Fu Jianzhuang Liu (2015)Progressive 3D Reconstruction of Planar-Faced Manifold Objects with DRF-Based Line Drawing DecompositionIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2014.235403921:2(252-263)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1109/TVCG.2014.2354039
Liu YLee Y(2012)Optimization-based freeform shape reconstruction3D Research10.1007/3DRes.03(2012)33:3(1-6)Online publication date: 1-Sep-2012
https://dl.acm.org/doi/10.1007/3DRes.03%282012%293
Murugappan SSellamani SRamani KCarr NSamavati FGrimm CLaViola J(2009)Towards beautification of freehand sketches using suggestionsProceedings of the 6th Eurographics Symposium on Sketch-Based Interfaces and Modeling10.1145/1572741.1572754(69-76)Online publication date: 1-Aug-2009
https://dl.acm.org/doi/10.1145/1572741.1572754
Santos TFerreira ADias FFonseca M(2008)Using sketches and retrieval to create LEGO modelsProceedings of the Fifth Eurographics conference on Sketch-Based Interfaces and Modeling10.5555/2386301.2386317(89-96)Online publication date: 11-Jun-2008
https://dl.acm.org/doi/10.5555/2386301.2386317

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents