“Design-driven quadrangulation of closed 3D curves”
Conference:
Type(s):
Title:
- Design-driven quadrangulation of closed 3D curves
Session/Category Title: Generating and Understanding Models
Presenter(s)/Author(s):
Abstract:
We propose a novel, design-driven, approach to quadrangulation of closed 3D curves created by sketch-based or other curve modeling systems. Unlike the multitude of approaches for quad-remeshing of existing surfaces, we rely solely on the input curves to both conceive and construct the quad-mesh of an artist imagined surface bounded by them. We observe that viewers complete the intended shape by envisioning a dense network of smooth, gradually changing, flow-lines that interpolates the input curves. Components of the network bridge pairs of input curve segments with similar orientation and shape. Our algorithm mimics this behavior. It first segments the input closed curves into pairs of matching segments, defining dominant flow line sequences across the surface. It then interpolates the input curves by a network of quadrilateral cycles whose iso-lines define the desired flow line network. We proceed to interpolate these networks with all-quad meshes that convey designer intent. We evaluate our results by showing convincing quadrangulations of complex and diverse curve networks with concave, non-planar cycles, and validate our approach by comparing our results to artist generated interpolating meshes.
References:
1. Abbasinejad, F., Joshi, P., and Amenta, N. 2011. Surface patches from unorganized space curves. Comput. Graph. Forum 30, 5, 1379–1387.
2. Bae, S., Balakrishnan, R., and Singh, K. 2008. ILoveSketch: as-natural-as-possible sketching system for creating 3d curve models. In Proc. Symposium on User interface software and technology, ACM, 151–160.
3. Bommes, D., Vossemer, T., and Kobbelt, L. 2010. Quadrangular parameterization for reverse engineering. In Proceedings of the 7th international conference on Mathematical Methods for Curves and Surfaces, Springer-Verlag, Berlin, Heidelberg, MMCS’08, 55–69.
4. Bommes, D., Lempfer, T., and Kobbelt, L. 2011. Global Structure Optimization of Quadrilateral Meshes. Computer Graphics Forum 30, 2, 375–384.
5. Bordegoni, M., and Rizzi, C. 2011. Innovation in Product Design: From CAD to Virtual Prototyping. Springer.
6. Brewer, M., Diachin, L. F., Knupp, P., Leurent, T., and Melander, D. 2003. The mesquite mesh quality improvement toolkit. In Proceedings, 12th International Meshing Roundtable, 239–250.
7. Coons, S. 1964. Surfaces for computer aided design. Technical Report, MIT.
8. Daniels, J., Silva, C. T., Shepherd, J., and Cohen, E. 2008. Quadrilateral mesh simplification. ACM Transactions on Graphics 27, 5, 1.
9. Daniels, J., Silva, C. T., and Cohen, E. 2009. Semi-regular quadrilateral-only remeshing from simplified base domains. In Proc. Symposium on Geometry Processing, 1427–1435.
10. Das, K., Diaz-Gutierrez, P., and Gopi, M. 2005. Sketching free-form surfaces using network of curves. Sketch-based interfaces and modeling SBIM.
11. de Goes, F., Goldenstein, S., Desbrun, M., and Velho, L. 2011. Exoskeleton: Curve network abstraction for 3d shapes. Computer and Graphics 35, 1, 112–121.
12. Farin, G., and Hansford, D. 1999. Discrete Coons patches. Computer Aided Geometric Design 16, 691–700.
13. Farin, G. 1992. Curves and surfaces for computer aided geometric design: a practical guide. Academic Press.
14. Finch, M., and Hoppe, H. 2011. Freeform Vector Graphics with Controlled Thin-Plate Splines. ACM Trans. on Graphics (SIGGRAPH Asia) 30, 6.
15. Gahan, A. 2010. 3D Automotive Modeling: An Insider’s Guide to 3D Car Modeling and Design for Games and Film. Elsevier Science.
16. Gao, K., and Rockwood, A. 2005. Multi-sided attribute based modeling. Mathematics of Surfaces XI, 219–232.
17. Irving, R. W. 1985. An efficient algorithm for the “stable roommates” problem. J. Algorithms 6, 4, 577–595.
18. Kälberer, F., Nieser, M., and Polthier, K. 2007. Quad-cover – surface parameterization using branched coverings. Computer Graphics Forum 26, 3, 375–384.
19. Levy, B., and Liu, Y. 2010. Lp centroidal voronoi tesselation and its applications. ACM Trans. Graph..
20. Levy, B. 2003. Dual domain extrapolation. ACM Transactions on Graphics (Proc. SIGGRAPH) 22, 3, 364–369.
21. Malraison, P. 2000. N-SIDED Surfaces: a Survey. Defense Technical Information Center.
22. Marinov, M., and Kobbelt, L. 2006. A Robust Two-Step Procedure for Quad-Dominant Remeshing. Computer Graphics Forum 25, 3 (Sept.), 537–546.
23. McCrae, J., and Singh, K. 2009. Sketching piecewise clothoid curves. Comput. Graph. 33 (August), 452–461.
24. McCrae, J., Singh, K., and Mitra, N. J. 2011. Slices: a shape-proxy based on planar sections. In Proceedings of the 2011 SIGGRAPH Asia Conference, SA ’11, 168:1–168:12.
25. Mehra, R., Zhou, Q., Long, J., Sheffer, A., Gooch, A., and Mitra, N. J. 2009. Abstraction of man-made shapes. TOG (Proc. SIGGRAPH Asia) 28, 5, 1–10.
26. Mitchell, S. A. 1997. High fidelity interval assignment. In Proceedings, 6th International Meshing Roundtable, 33–44.
27. Nasri, A., Sabin, M., and Yasseen, Z. 2009. Filling N -Sided Regions by Quad Meshes for Subdivision Surfaces. Computer Graphics Forum 28, 6 (Sept.), 1644–1658.
28. Nealen, A., Igarashi, T., Sorkine, O., and Alexa, M. 2007. Fibermesh: designing freeform surfaces with 3d curves. ACM Trans. Graph. 26 (July).
29. Orbay, G., and Kara, L. B. 2011. Sketch-based modeling of smooth surfaces using adaptive curve networks. In Proceedings of the Eighth Eurographics Symposium on Sketch-Based Interfaces and Modeling, SBIM ’11, 71–78.
30. Owen, S. 1998. A survey of unstructured mesh generation technology. In Proc. International Meshing Roundtable.
31. Rose, K. 2007. Modeling developable surfaces from arbitrary boundary curves. Processing, August.
32. Ruiz-Gironés, E., and Sarrate, J. 2010. Generation of structured meshes in multiply connected surfaces using submapping. Adv. Eng. Softw. 41 (February), 379–387.
33. Salomon, D. 2006. Curves and Surfaces for Computer Graphics. Springer-Verlag.
34. Schaefer, S., Warren, J., and Zorin, D. 2004. Lofting curve networks using subdivision surfaces. Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing – SGP ’04, 103.
35. Schmidt, R., Khan, A., Singh, K., and Kurtenbach, G. 2009. Analytic drawing of 3d scaffolds. ACM Trans. on Graph. (Proc. SIGGRAPH Asia) 28, 5.
36. Singh, K., Pedersen, H., and Krishnamurthy, V. 2004. Feature based retargeting of parameterized geometry. In Proceedings of the Geometric Modeling and Processing 2004, IEEE Computer Society, Washington, DC, USA, GMP ’04, 163–.
37. Stevens, K. A. 1981. The visual interpretation of surface contours. Artificial Intelligence 17.
38. Tan, J. J. M. 1991. A necessary and sufficient condition for the existence of a complete stable matching. J. Algorithms 12, 1 (Jan.), 154–178.
39. Tong, Y., Alliez, P., Cohen-Steiner, D., and Desbrun, M. 2006. Designing quadrangulations with discrete harmonic forms. In Proceedings of the fourth Eurographics symposium on Geometry processing, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, SGP ’06, 201–210.
40. Várady, T., Rockwood, A., and Salvi, P. 2011. Transfinite surface interpolation over irregular n-sided domains. Computer-Aided Design, iv.
