Search

This paper presents a method to find the faces of objects in 2D line drawings, using an approach totally different from existing ones. It consists of two stages: decomposition and face forming. In decomposition, a drawing is decomposed into chains of connected edges. Each chain belongs to one face only, but may not yet form a closed loop. The decomposition is local to a vertex, and takes no account of the overall structure of the drawing. The algorithm ensures that there is a chain for every face in the object. The face forming stage completes the loop for each chain to form a face. Our method can deliver both the real faces and the internal faces separately. It depends only on the topology of the drawing and not on the geometry, and is therefore applicable to line drawings with curves and straight lines, and 3D wireframes. We implemented our algorithm and tested it with hundreds of objects, including objects used in previous publications. It always delivers the correct result. Comparison with the latest methods shows that it is faster often by tens of times and, in some cases, hundreds of times. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents an algorithm for decomposing complex line drawings which depict connected 3D manifolds into multiple simpler drawings of individual manifolds. The decomposition process has three stages: decomposition at non-manifold vertices, along non-manifold edges and across internal faces. Once non-manifold vertices and/or edges are found, the decomposition can be performed straightforwardly. Thus the major task in this paper is decomposition across internal faces. This has two steps: basic decomposition and repair of incomplete parts. The decomposition process is performed before face identification which is computationally expensive. After decomposition, the time for face finding is much reduced and this, in turn, greatly improves the process for 3D reconstruction, which is the ultimate goal. [Copyright &y& Elsevier]

Several studies have been made in finding the faces of an object depicted in a line drawing, but the problem has not been completely solved. Although existing methods can find the correct faces in most cases, there is no mechanism to ascertain that they are indeed correct, leaving the human user to do so. This paper uses a two-stage approach--find potential faces, then validate their correctness--to ensure that only correct faces are delivered ultimately. The face finding itself uses a double breadth-first search algorithm, which yields the shortest path, to find the potential faces. The basic premise is that the smallest faces found are more likely the correct ones. They serve as the "seed" potential faces, from which the algorithm proceeds to search for more faces. If the potential faces found satisfy the validation rules, then they are accepted as correct. Otherwise, the wrong potential faces are identified and removed, and new ones found in their place. The validation process is then repeated. The algorithm is fast and reliable, can deal with planar-faced manifold and nonmanifold objects, and can deliver the different results when a drawing has multiple interpretations. Our extensive tests show that the method can deal with most cases efficiently, including those that previous methods cannot solve. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents a direct method to recover the geometry of the 3D polyhedron depicted in a single parallel projection. It uses two sets of information, the list of faces in the object, obtained automatically from the drawing, and a user-identified cubic corner, to compute for the coordinates of the vertices in the drawing and thus establish the 3D geometry of the whole polyhedron. The algorithm exploits the topological structure of the polyhedron, implicit in the connectivities between the faces, resulting in a complexity that is linear in the number of faces. The method is extended to objects with no cubic corners as well. The algorithm works well for recovering objects from accurate line drawings, producing accurate 3D objects. A simple extension to the algorithm allows it to handle inaccurate drawings such as sketches, and produce 3D objects that are consistent with our human perception of the drawings. [Copyright &y& Elsevier]