In this paper, the authors present a new algorithm for constructing a solid model when the given input is only one partial-view sketch (“natural sketch”). This algorithm is a two-step process, where first a complete (wireframe) sketch is derived, which is then transformed into a 3D polyhedron. The paper details topological and geometric aspects of the process, as well as the essential “user-interaction” components dealing with cases where the sketch-to-solid problem does not have a unique solution.
Top1. Introduction
Throughout the history of Computer Graphics and Engineering Visualization it is evident the desire of users to be able to define geometric objects using an interface mimicking as much as possible the traditional “sketching on paper” (Lipson, 1998). Obviously, 3D Geometric Modeling (for engineering, entertainment or artistic applications) is one of the most challenging fields for Sketch-based User Interfaces (SUIs), as in that the SUI must derive from the given 2D sketch the missing 3D information.
This research deals with the problem of defining a Polyhedron from a given Single Sketch (PSS problem) (Lamb & Bandopadhay, 1990; Wang & Grinstein, 1993; Grimstead & Martin, 1995; Schweikardt & Gross, 2000; Varley, 2002; Sapidis, Kyratzi, & Azariadis, 2005; Company, Piquer, Contero, & Naya, 2005; Fahiem, Haq, & Saleemi, 2007; Cao, Liu, & Tang, 2008). A sketch is a set of straight lines on a plane that intersect at junctions. Loops of lines and junctions form regions of the sketch. The given sketch is either a complete wireframe sketch (Figure 1(a)) or a natural sketch, i.e., a sketch without hidden lines (Figure 1(b)). The two different types of sketches correspond to two distinct versions of the PSS problem. A given sketch is called realizable if it is the correct projection of a polyhedron (Ros & Thomas, 2005).
Figure 1. The two types of sketches involved in the PSS problem
This paper deals with the PSS problem for the case of a natural sketch, as this is most often involved in industrial applications. Moreover, this investigation is limited to the simplest case of a trihedral polyhedron (where exactly three faces meet at each vertex), which is still unsolved (Cao, Liu, & Tang, 2008), and references therein.
The strict majority of published PSS methods are heavily based on the “line labeling” method and on “image regularities”, which are known to have significant disadvantages; see an analysis in Section 2. Thus, the present research focuses on a “minimal-completion” algorithm (Kyratzi & Sapidis, 2008, 2009) employing robust tools from Graph Theory, Solid Modeling and Euclidean Geometry. Indeed, these fields offer an abundance of results and algorithmic tools that have found, up to the present time, limited application to the PSS problem. Kyratzi and Sapidis (2009) present the initial part of the “minimal-completion” algorithm focusing on the topological construction of the polyhedron corresponding to a given natural sketch. This paper completes the “minimal-completion” algorithm with its part dealing with the geometric construction of the polyhedron (see sections “Step S5: Geometric construction of the wireframe sketch” and “Step S6: Geometric construction of polyhedron”). Furthermore, this work addresses the issue that, in general, when the PSS problem is solvable, more than one polyhedra correspond to the given natural sketch. In this case, the user should get involved in the polyhedron-construction process to guide it towards a desirable solution; appropriate “user-interaction” methods are developed in the sections “Step S5: Geometric construction of the wireframe sketch” and “Step S6: Geometric construction of polyhedron”. Section 5 details application of the “minimal-completion” algorithm on a typical sketch, demonstrating the effectiveness of the proposed methodology.