Technical Report # UM-MEAM-91-10 Reconstructing Curved Solids From Two Orthographic Views Debasish Dutta* and Y. L. Srinivast Design Laboratory Department of Mechanical Engineering The University of Michigan Ann Arbor, MI 48109

C-7 (St -

Submitted to the Journal of Computer Aided Desig Reconstructing Curved Solids From Two Orthographic Views Debasish Dutta' and Y. L. Srinivast Design Laboratory Department of Mechanical Engineering The University of Michigan Ann Arbor, MII 48109 July 24, 1991 Abstract It has long been known that the two-view orthographic representation of a mechanical part is ambiguous. Existing literature addresses recognition/reconstruction of solids, mostly polyhedral, from either one-view (perspective) drawings, or from three orthographic views. In this paper, we present algorithms for reconstructing curved solids from only two orthographic views. First, we reconstruct all polyhedral solids that correspond to the pair of prespecified orthogonal views and then develop the associated third views. For each solid, we analyze the three views simultaneously and reason about the possibilities of including circular arcs in the newly generated third view. This corresponds to the inclusion of solids that are bounded by quadrics. Application areas include computer-aided design, machine vision and automated inspection systems. Supported in part by NSF Grant DDNM 90-10411 tSupported by the University of Michigan Rackham Award and by NSF Grant DDMN 9010411 1

1 Introduction 1.1 Two-view Orthographic Representation The use of parallel projections for unambiguous representations of solid objects was developed by the French mathematician Gaspard Monge, in mid-18th century. It has since formed the basis of what is now referred to as engineering drawing, multiview drawing, and orthographic drawing. In this paradigm, every three dimensional object can be completely described by a set of three orthographic views (projections) on mutually perpendicular planes. Of the six possible orthographic views (obtained when the object is thought of as enclosed in a transparent box) the ones most commonly used in engineering are the front. top and the right-side views. While simple objects such as cylinders, bushings and bolts can typically be dtescribed by only a. pair of orthographic views, the precise description of complex machine elements often require sectional and/or auxiliary views in addition to the three views. In this paper we are interested in the inverse problem. that of developing solids whose orthographic views are given. In particular, we consider the problem where only two of the three views are given. There are two aspects of this problem that contribute to its complexity. First, it is well known that a pair of orthogonal views (e.g., the front and top) will, in general, correspond to more than one solid, each giving rise to a unique third view (i.e.. the right-side view). Thus, the two-view representation of most objects is ambiguous. Second, straight lines in one of the two views can correspond to curves in the missing third view, giving rise to solids bounded by non-planar surfaces. Fundamental in engineering graphics and descriptive geometry, and usually encountered by students in their first engineering drawing/graphics course. is the missing-view problem: Given two views, generate the third view(s). This problem can be surprisingly complicated. It is so because every correct solution to this problem first requires the visualization of a solid corresponding to the two given views. The third view can then be determined. Therefore. vizualization in 3-dimensions is requisite, and that in itself is cause for frustration. Furthermore, since a two-view representation is non-unique the completeness of the solution can be difficult to verify. If an object has several features that project to a single line in one or more views, the reconstruction of the same object starting from the three views can be very complicated. Lines and points on the given views must be systematically analyzed in the process of developing a correct solid. XWhen only two views are given, the problem is clearly more difficult. For a simple object, it is best to visualize it partially from the two given views and then complete the process bv adding consistent right side views. one by one. However. if the given views 2

are complex, powers of spatial visualization become inadequate in guiding the analysis which is inherently combinatorial. That there has been no reliable way to determine exactly how many solids correspond to a given pair of orthogonal views is therefore not surprising. In this paper, we present an algorithm for reconstructing all solids bounded by planes and quadrics when only two orthographic views are given. First, the algorithm generates all polygonal third views (i.e., composed of straight lines only) that correspond to a given pair of orthogonal views. It does so by reconstructing all polyhedral solids that correspond to the orthogonal views. The three views are then analyzed to identify the line segments in the right view which can be replaced by circular arcs (other conics can be included easily). Finally, the non-polyhedral solids are generated fiom the modified three views. Akin to the gift wrapping method of generating convex hulls. our reconstruction procedure begins from a vertex and faces are added one by one. until a solid is generated. Considering every valid triple of vertices, the algorithm evaluates all candidate faces for inclusion. It considers all valid configurations of faces and determines the complete set of valid solids corresponding to the given views. An empty solution set proves that the given views a.re inconsistent. We conclude this section by reviewing prior work in generating solids from line drawings, and mentioning potential applications. In section 2, we analyze the problem and discuss the algorithm. Sections 3 and 4 contain the algorithms for polyherdal and curved solid generation. Examples are shown in Section 5. 1.2 Previous Work Motivated by the use of digital computer for image processing, various aspects of automatic recognition and reconstruction of line drawings have been researched since the 1960s. In particular, two variants of our problem, viz., reconstruction from single-view and three-view drawings. have received attention thus far. An excellent survey of the research on machine interpretation of line drawings can be found in the first few pages of the text by Sugihara [Sugihara 1986]. In his book, Sugihara addresses, in particular, the recognition of polyhedral objects and scenes described by single-view line drawings (also referred to as perspective drawings). An important subclass of this problem is the interpretation of multiview line drawings. Idesawa presented a method to reconstruct solid models from three orthographic projections [Idesawa 1973]. The method. however. was capable of producing invalid objects. Lafue developed heuristics to detect such invalid objects by imposing a prespecified input format [Lafue 1976]. In 1980. WIesley and Markowsky developed an algorithm for producing orthographic views from wire-;3

frame models of mechanical parts [Wesley and SIarkowski 1980]. They further extended the method to construct polyhedral solids from the three orthographic projections [Wesley and Markowsky, 1981]. Methods for extracting 3-D information from orthographic views can also be found in [Preiss 1981] and [Aldefeld 1983]. In [Sakurai and Gossard 1983], the Wesley and Markowski approach was extended to include circular arcs in the orthographic views. The resulting solids, therefore. could include quadrics and toroidal surfaces. The problem of generating all solids from only two views, to the best of our knowledge, was first examined in [Wilde 1991]. Wilde examined the difficulties involved in spatial visualization, and in particular, in the reconstruction of solids from two orthogonal views. In this paper, we present algorithms for the reconstruction of polyhedral and curved solids from two views. 1.3 Applications An automatic procedure to generate solids from line drawings has many applications in engineeering. For example, one can then verify the consistency of complicated engineering drawings automatically. Such an algorithm can also be part of an interactive system to assist a designer during the development of new product designs. Moreover, drawings continue to be the most natural way of conveying geometric information for designers. Therefore, a system to automatically convert engineering drawings into solid models can be very useful. The conversion of engineering drawings into solid models is a task many industries have to address in the process of adopting solid modelling systems. Recognizing orthographic projections will also have applications in machine vision and automated inspection. 2 Analysis of the Reconstruction Problem 2.1 Canonical Orientation It is a common practice in engineering drawing to orient the object such that it yields the simplest orthographic views. It is easy to see that a simple object can produce complicated orthographic views if it is not oriented in the best possible way. For example, a cube standing on its vertex would produce a rather complicated set of orthographic views. with all edges foreshortened. However, when three sides of the cube are parallel to the three principal planes of projection the orthographic views are three squares. In the latter orientation, there is no foreshortening of edges and they appear in their true lengths. W'e refer to that orientation of an object xwhich maximizes the number of egdes appearing in true

lengths in all three views, as the object's canonical orientation. HIowever. not all objects can be oriented such that the edges comprising the three views appear in their true lengths (e.g., an equilateral tetrahedra). 2.2 Edge and Vertex Multiplicities When three orthographic views are provided, there is enough information in the drawings to deduce which lines appear in true lengths. Reconstructing the solid is not difficult thereafter. However, when only two views are provided, the reconstruction procedure requires a systematic analysis of the views. Central to this analysis is the detection of line multiplicity which is achieved by reasoning about vertex multiplicities. It is easy to see that more than one edge of a solid can project to the same line in one orthographic view. We consider such lines as multiple lines. The multiplicity 7in of a line I in any view refers to the maximum number of edges that can project onto I whllile being consistent with the other view. Detection of multiple edges is enabled b)y reasoning about multiple vertices. since each edge must correspond to a pair of vertices. Therefore. multiplicity m of vertex v refers to the maximum number of distinct vertices it can conceal, consistent with the views. The multiplicity of vertex v in the top/front can be obtained by counting the vertices in the front/top view that lie on the vertical line through v. The following is intuitive. Proposition 2.1 If vertices with multiplicities > 1 exist in two orthographic views. the pair corresponds to more than one valid solid. 2.3 A Combinatorial Analysis An important difference between our problem and its two well known variations (i.e., generating solids from a persplective vtieu and from three orthographic views) is that our problem has multiple solutions. whereas the other two have exactly one solution each. In other words. it is necessary for us to determine both correctness and completeness of the solution. whereas the other two problems are solved by a correct solution. It is this lifference tllat leads to the combinatorial nature of our problem. A bound on the number of right views (and hence distinct polyhedral solids) corresponding to a pair of orthographic views can b)e derived by analyzing the standard technique employed in engineering drawing to develop third views from two given views. We illustrate the procedure in Figure 1 but omit discussions. An explanation can )e found in any standard text on engineering drawing, e.g.

45'Mitre Line i F R Figure 1: Constructing a right view from top and front views ILuzadder 1986]. In Figure 1. let us assume that the top and front views. shown in the top quadrant (TQ) and front quadrant (FQ) respectively, were generated by analyzing a solid S with 7n vertices and n edges. By construction. all candidate vertices in the right quadrant (RQ) are the intersections of the horizontal and vertical lines drawn from the vertices in FQ and' TQ, respectively. There are O(m) vertices in TQ and in FQ. So RQ has 0(nm2) candidate vertices. But the right view cannot have more vertices than its progenitor S. Thus, each correct right view Ri developed from the ca.ndidate vertices in RQ is a graph Gi(V, E) and V = O(m). (Note: Firm lines in the right view cannot intersect but at the candidate vertices. However, intersections between firm and hidden lines can create new vertices.) Letting lf = in2. there are C;/ possibilities for the vertex set V. Let us consider a vertex set 1'. of cardinalitv mn. With 7n vertices. we can have O(m!) trees. 1 But, the orthographic views cannot contain any trees since trees correspond to dangling faces and edges (i.e.. unbounded solids). Therefore, the set of valid right views P, corresponding to vertex set V, consists of all graphs but no trees or dangling edges. For example. every triangulation of Vk is a topologically valid right view since it contains cycles. It is easy to see that the cardinality of the set P will. in general. be exponential in m. Since there are Ca' such vertex sets. the possibilities for right views are exponential in number. Clearly, this is a loose bound on the number of right views since consistency with the top and front views is the final check for a valid right view. Moreover, inclusion of non-polyhedral solids in the above analysis will result in an infinite number of valid right views. 1For example. wvith three vertices A. B and C we can have trees like A-B-C. A-C-B, B-A-C and so on. (5o

2.4 Correctness of Procedure We begin by asserting that a two-view representation can be unique under special conditions. Lemma 2.2 If at least one of the two given orthographic views has no multiple vertices, then the two-view representation is unambiguous. Proof Let the top and front views be given, the former without any multiple vertices. The top view then determines the total number of vertices in the object and their unique connectivities (i.e.. the edges). Clearly, the top view determines the unique topology of the solid. By definition, the front view contains the elevation of each vertex that appears ill the top view. Therefore. the given representation is unambiguous. C Note. that a pair of orthographic views, as per Lemma. 2.2 will, in general, not facilitate visualization. IHowever, for the purposes of our reconstruction algorithms they are valid inputs. If the multiplicity of a vertex is n, it could conceal upto n- vertices in the view. Therefore, we account for such a vertex in the construction procedure by considering the view in which the vertex appears n times, once with each value of the vertex multiplicity (i.e.. 0,... n - 1). Theorem 2.3 In the reconstruction of all valid solids from a pair of orthographic views, it is necessary and sufficient to analyze only one view and account for all vertices in that view that have multiplicity > 1. Proof That it is necessary follows from Proposition 2.1: we argue for sufficiency. Accounting for a multiple vertex v in a view requires consideration of n instances of the view, once with each value of the multiplicity of v. The companion view is used for validity checks. Clearly such and accounting procedure is exhaustive. Sufficiency is now an immediate consequence of Lemma 2.2. 0 Any procedure that does not account for all vertices with mutiplicity > 1 is, by Theorem 2.3 incomplete. dWie account for multiple vertices in one view by directly constructing the solid wnhile using the other view fQr verifying consistency. The algorithm is based on an enumeration scheme. It considers all possible configuration that can arise from the two given views. From these candidate configurations. only those which correspond to valid representations of solids are identified and stored. Since all candidate configurations are enumerated, the algorithm insures that the solution set is complete. i.e., there are no solids other than those in the solution set that will generate the given pair of orthographic views.

%10of lll ~3 ~ 4 5 6 2 3 4 8 9 10 IO fru I 111 Figure 2: Orthogonal views 3 Overview of Algorithm 3.1 Algorithm Input The input to the algorithm are two vertex connectivity matrices that correspond to the given views. Coordinates of each vertex are also supplied to the algorithm. Each connectivity matrix is a (ni x n) square matrix, where n is the number of distinct vertices in the corresponding view. Figure 2 shows a pair of orthographic views, and the associated connectivity matrices are shown in Figure 3. An element C(i,j) of the matrix has a value of 0 if node i is not connected to node j, a value of 1 if node i is connected to node j by a complete solid line, and a value of 2 if node i is connected to node j by a complete or partially hidden line. For example. in Figure 2 (Front View). vertex 5 is connected to vertex 7 11100000000 11110001000 11000000001 11111000100 1 0 1 1 1 1 0 O 0 0 0 11 1 1 0 1 0 0 0 1 0 00111110010 111 1 0010001 0 0 1 1 1 1 0 1 0 0 1 0 ~ 1 0 0 1 1 2 0 1 0 0 00111101000 01001120100 001111001 0 01 001 0112001 1 0 000100 111 0 00012210001 00001011100 10000001111 00000111101 01001001111 0 O O 1. 0 0 1 0 0 1 1 0 0 1 0 0 1 0 1 1 1 1 0001001 0 0 11 001001 1111 Top View Front View Figure 3: ('onlllectivitV Matrices 8S

by a partially hidden line and so C(5. 7) = 2. Tile connectivity matrices are symmetric. 3.2 Description of Algorithm The algorithm works as follows. Since a vertex in any view can actually correspond to the orthogonal projections of one or more lines, a vertex analysis is first performed to detect such multiple vertices and their multiplicities are recorded. For example, vertex 11 in Figure 2 (front view) has a multiplicity of 4 since, there are at most four vertices ill tile top view. viz., 6, 9, 11 and 2, whose projections can coincide with it. Next, the vertex with least ilultipilicity. say t,1. is selected. From the connectivity matrices. all neighbors of i1l are id(entified and store(l in V'. Every non-collinear triple in V containingl'l (lefinles a plane passing tlhrough r1. These planes are generated and stored in P. Finally. a set of faces F is created by systematically detecting all vertices. except 1ll and its neighbors. that lie on each element of P. Therefore. eacli elemlelnt of F is a face containing the vertex v1. Next. we analyze the faces in F. In particular, we need to determine how many faces of F can lead to a valid solid. A solid is considered valid only if it corresponds to the given views. The analysis involves expanding faces of F and proceeds as follows. A face fl is selected from F. If fi is to be the face of a valid solid, each edge of fl must be sha.red by exactly one more face. 2 The neighbors of fl are identified and stored in GCl. This process is repea.ted for every face in F. The set GC includes only those faces encountered in the analysis that do not intersect any face in GC; l, -;i-'..... (;1 (i.e.. excludes non-manifolds). Furthermore. consistency with the giveii orthograplhic views is verified prior to adding a. face in Gi. A depth first strategy is employed and the faces of G1 are expanded next. Concurrently with the face expansion procedure for G'1, the constructed solids are checked for completeness (i.e.. bounded solid) and validity (i.e.. consistency with the given orthographic projections). Any solid that passes this check is a vaild solid and is stored in the solution set. The connectivity matrix corresponding to the right view is then generated. The face expansion process is carried out for all sets G'i, until all faces are expanded. The algorithm tlhen terminates. since all solids corresponding to the given pair of orthographic views have been identified and their right view connectivity matrix stored. Now we have the three views for each solid. The last step is to identify from these views. which lines in the rilght view ca-n be replaced by circular arcs. (Note, we are only concerned with introducing curves in the right view and not in the 2\Ve do not consider non-lnanifoldl orbjects!)

top and front views which were prespecified). We assume that the solid being analyzed is in a canonical orientation. Once again. we analyze one view and use the other for checking consistency. Clearly, all vertical lines in the top view are candidates for curved edges.when viewed from the right. Furthermore, a vertical line in the top view can only correspond to an inclined line, or a horizontal line, in the right view. If it corresponds to an inclined line 11 = (u,v), it can be replaced directly by a circular arc C. C passes through u and v, and has 12 and 13 as tangents, where 12 and 13 intersect 11 at ui and v respectively. If the vertical line in the top view corresponds to a horizontal line in the right view, the corresponding solid has a sharp corner (and an edge) that is a candidate for "rounding" or "filleting". Further checks are done to ensure consistency with the front view and the corner/edge in the solid is rounded. or filleted, by replacing the appropriate vertex in the right view with a. circular arc. The blend radius can be chosen by the user and (letermines the point of tangencies. 4 Algorithm The main algorithm invokes three substeps, viz., Form-Face, Expand-Face and Curves. The first two are recursive. 4.1 Algorithm MAIN Input: Connectivity matrices for orthographic view R and T Output: Solids corresponding to R and T begin for each vertex in R, compute multiplicity for minimum multiplicity vertex vl, while multiplicity > 0 F - Form-Face (vi) while F not empty, Expand-Face(F) P ~ polyhedral solids; Q *= right views while Q not empty, Curves(Q) C t= Curved solids output P and C end The algorithm MAIN requires that in the orthographic views there be a path from each vertex to every other vertex (i.e., no edge loop ill is properly contained in another). This condition disqualifies solids that have holes and pockets that 10

open on planes. Thle algorithm can be modified to overcome this limitation by adding dummy edges between tile appropriate vertices of the (lisconnected loops. A brief description of the procedures used by the program MAIN is given below. 1. Input-connectivity- matrices (top-view, front-view): Reads the data for both views from the input file and retruns the data in matrices top-view and front-view. 2. Generate-multiple-nodes (top-view, front- view. multiple-node-list): Generates all the possible multiple nodes in the front view from the information given in top-view and front-view matrices and returns the list of multiple nodes. properly labelled, in multiple-node-list. 3. Get-min-mnode (nuultiple- ode-li0t. in in-l): Determines the no(le in thle front view tlhat has the least numb)er of multiple nodes in the front view-,. and returns tlhe identification ot the iiode in Imin-loc. 4. Get-mnodes (nmin-ioc. inzul/tip/ -iode-list, Izllotle-li-s't): Extracts all the mnodes at norde min-loc in the front view ftrom the multiplenode-list and returns the resultant list in ninode-li-st. 5. Get-connected nodes (nmnode. connected-list): Determines all the mnodes in the mTzultiple-node-list that are connected to mnode and returns the resultant set in connected-list. 6. Get-next-plane (nmnode. connected-list, face): Determines the next candidate plane in the conrnected-list that passes through mnode. The previous plane. if any. is passed via face. The resultant plane is returned in face. 7. Get-nodes-in-plane (face. v'crtices): Determines all nmnodes that lie in tile plane (lefined 1)y face and returns this rnnodes list in vertices. 8. Initial-solid (solid, face): Sets up the initial.:olid with a. single face (lefinedl by face. 9. Output-solution(): Outputs the solution set of solids. 11

4.2 Algorithm Form-Face: Form-face procedure recursively generates all the possible faces that can be produced from the vertex set. Algorithm: 1. Identify all neighbors of last vertex of the face 2. For each of the vertices inl this list. repeat 2.1 Add the vertex to face at the current last vertex 2.2 If face is complete and valid add to the list of possible faces 2.3 kMark this vertex as USED in the list of vertices that lie in plane 2.4 Invoke form-face( ) to generate thle p)ossil)le faces for lupdated face 2.5 Remove this vertex (tile last vertex) from face'2.6 Maark verltex as FREE ill tiie list of verltices tihat lie it the l)lane 3. End of preocedure: Ret Irn The procedures used I)v Formi-Face are )riellv dlescril)eld below. 1. Get-next-vertex-list (face. vertice.s, nezt-li.st): This procedure returns all the FREE members of vertex list vertices that can be connected to the last vertex of face. The list of t.!ese vertices is returned in next-list. 2. Add-vertex-to-face (face. vertex): This procedure expands the partially constructed face by adding'ertez to the last vertex of face and updatillg vertex as the last vertex of face. 3. Valid-face (face/: This procedure verifies if a. given face is a colll)lete aiid consistent face. i.e. edges form a closed loop and dco not cross eacil otlher. 4. Add-face (face): This procedure stores face in the list of candidate valid faces. 5. Mark-vertex-list (vertices. vertex. cvale): This procedure marks vertez in the list vertices with the value ahlule. IF value is USED. then vertex will not be llsel as a. cand(idate in subsequent searclhes. If value is FREE. vertex will be used. 6. Remove-vertex-from-face (face. tcertex): Tlhis procedure renloves v'rtc.rt firoll tile eiid of the l)artiallY constructed( face. The previous vertex in fice 11ow i)becotmees thle last vertex. 12

4.3 Algorithm Expand-Face Expand-Face() recursively expands all the ed(ges of the face. It also checks for the consistency and validity of the partially constructed solid and stores any valid solids that may be encountered during the process. Algorithm: 1. For each edges of the face repeat 1.1 Extract vertices in face that correspond to the edge 1.2 If edge is already shared by two faces go to Step 1.5 1.3 Generate list of faces that can be incident to edge 1.4 For each face in this list repeat 1.4.1 Add face to thle partially collstrllcted solid l.1.2 If solid is comnplete aill vali(l. add to solution.-1.3 Invoke expand-facet ) to expl)all(n tills face 1.4.4 Reimove face frolnm solid 1.5 Continue until the list is cornpletely processed 2. End of procedure: Return The procedures used by Expand-Face are briefly described below. 1. Number-of-edges (face): Determines the number of edges in face. 2. Extract-edge (face. i. edge): Extracts the edge i from face. This edlge is returned in the varialble edge. 3. Already-shared (edge. solid): Checks if edge is already shared by two of the faces of the partially constructed.solid. If so. if returns TRUE: else returns FA-LSE. 4. Get-next-face-list (edge, face. solid,. face-list): Gets the list of all otlier possible faces for the edge which lies on face. This procedure checks and returns only those faces tlhat. wlien added. preserve the consistency of the partially constructed solid. Thle result is returned in face - list. 5. Add-face-to-solid (.soli. fa(ce): Grows the partially constructed solid by addilng face as one more face of solid. It assumes that face (lualifies to be a, valid face of solid. 6. Valid-solid (s.olld): Checks if solid represents a valid solid tllat can I)e a rnember of solution set. It checks (i) if all the edlges are shared bv exactly two nodes and (ii) the solid produces all thle vertices and linles ill tile giveti viow illforllatlrionl. If.solil passes 13

these checks, it returns TRUE. else returns FALSE. 7. Store-solid (solid): Adds solid as a member of the solution set. 8. Remove-face-from-solid (solid. face): Removes the face face from a partially constructed solid solid. It assumes that the resulting partial solid is still valid (i.e.. does not contain discontinuities) 4.4 Algorithm Curves Curves( ) detects the edges in thle newly generated right views tllat can be replaceds by circular arcs. while remainiing consistent with the specified top and front views. Algorithm: i. E all vertical lines ill top view. 2. For each element ci of' I repeat 2.1. Find corresponding edge r; in right-side view 2.2. If ri is not horizontal replace r7 by a circular arc 2.3. If r; is horizontal. repeat 2.3.1 If edges intersecting iri a-re vertical. replace 7'i by circular arc 2.3.2 Else, for each vertex u;L of ri repeat 2.3.3 If ui has vertical and hlorizontal neighbours. blend ui 3. Output valid solids: STOP This algorithm identifies the surfaces of the solid which can be curved. At present it replaces with circular arcs only. IIowever. extension to include all conics is straightforward; e.g., using Liming's method [Faux and Pratt 1987, page 31]. The input to the algorithm are the three connectivity matrices corresponding t6 the three orthogonal views of the solid. It is required that these views consist entirely of straight line segments only (i.e.. we assume that projections of the curved surfaces are stright lines in the top and front views). The algorithm then determines the edges in the right view that can be curved. The limits on the parameter values of the circular arcs can b)e adljusted suchl that no two curves overlap or intersect and the solid remains valid. The procedures used by Curves Iare b)riefly de scribedt lelow. 1. Get-vertical-edges (cdlg-lis.t): Generates a list of edges that correspond to the vertical edges in top and front views. These edge project as eitlher straighlt lilnes of poilts in both these views. 14

The list is returned in edge-list. 2. Horizontal (edge-list. i): Determines if i th edge in the edge-list is horizontal. It returns TRUE if the edge is horizontal. Otherwise, it returns FALSE. 3. Mark-parametric-curve (edge-list. i): Records that the i th edge in tile edge-list can be replaced by a family of circular arcs that can be represented in the parametric form. 4. Get-descrete-points (right-view, point-list): Identifies all the points in the right-view that have their p)rojections as horizontal lines in both front and top views. The list of resultant points is returned in pointlist. 5. Valid-descrete-curve ((Iye-li.st. i. floil-list. j'): Determines if edge i can b)e rep(l)aced >)v a c(irculjar arc that sI)ans lipto the point j. Returns TRUE if the edge (1anll he repllacied. 6. Mark-descrete-curve (cdge-list. i. pJoint-list. j): Records that edge i in the (clgc-lis. canl be replacedl 1)y a circular arc that spans upto point j in the point-list. 7. Get-tangent-nodes (iright-view. edge-list): Identifies all the nodes in the riqght-zieuw that can be removed and replaced by a set of parametric arc that are tangent to the edges that joint at that node. The result is returned in node-list. 8. Mark-tangent-node (odle-list. i): Records that node i in the ntode-list can be relnoved and replaced by a set of parametric tangent curves. 5 Examples We illustrate the working of our algorithm l)y three examples. The algorithm was implemented in C and run on an Apollo DN 4000 workstation. The first example solves for polyhedral solids only, while in the second and third we generate solids bounded by quadrics. 5.1 Polyhedral Solids The first example has been borrowed fronm [\ilde 1!)91] where ten solids were generated corresponding to the pair of ortlographlic views shown in Figure 2. Using our algorithm we generatedl thle complete set of solids (sixteen) and the corresponding right-side views. Thlley are sllowll ill Figure -1. )On thle Apollo DN 15

4000. it took 2.6 seconds to generate all right view connectivity matrices (from which the right views were drawn). While solving the above problem we made the assumption that every solid has a planar (rectangular) base, the boundary of which corresponds to the boundary (i.e., the outer edge loop) on the top view in Figure 2. This assumption disallows any prismatic protrusions below the base. \Vhen this restriction is removed, (i.e., prismatic protrusions below the base that do not affect other views are allowed) the number of solutions increase rapidly. Tile reader can visualize the new solids when, for example, triangular prisms are attached to the bottom face of the solutions 9, 10. 11. 12. 15 and 16 such that tile top and front views are unaffected. 5.2 Solids bounded by Curved Surfaces HIere we illustrate the reconstruction of curved( solids fromn a pair of orthographic views (straight lines ollly). The top and front views were intentionally chosen to be simple. They permit us to (lenlonstrate the working of our algorithm,. and most importantly show the large number of possible solutions. In Figure 5 and Figure 6. instead of drawing the complex curved solids, we have shown two right views for each case, viz.. a polygonal right view and a right view with circular arcs. In Figure 5, the top and front views are given, as shown. The corresponding five right views are shown in the numbered boxes alongside. This simple example took less than a second each. for polygonal right views and curved right view on the Apollo DN L4000. Note. all views (1o not permit curves. For example. the replacing sharp corner ( by any circular curve is imnpermissible if one is to remain consistent with the (limensions in the top and front views. Views 4 and 5 are similar. In Figure 6 the top and front views are given, as shown. For this set, the algorithm identifies 14 polygonal right views in:3.2 seconds. and the corresponding curved right views in 2.1 seconds. on the Apollo DN 4000. As before. not all right views permit curves. User interaction, sulch as in Exalnple I (Figure -1) is helpful in the reconstruction of the solids. The searcll I)rocess c(an then b)e guileld to include. or exclude, certain features on tile solid. Also. in Examples 2 and:3. the radius for rounding and filleting can be chosen biy tile user. Furthermore. using Liming's method the circular arcs can easily l)e replaced by otller conics such as elliptical. parabolic or hyperbolic arcs; e.g.. see [Faux and Pratt 1979. page:31]. 16

1 2 3 4 5 6 7 8 EI L JI 9 1 0 11 12 1 3 1 4 1 5 16 Figure -9: Example 1: 1olyhedral solids

Top View -font View > 4 / 5Figure 5: Example 2: Cullrvedl Solids 1S

Top View I~ I ua~I m Front View 3 4 5 4 7n a 1109 12 13 14 Fiigure (j: ExaIll)le 3: C'lrvt ol Solids'19

6 Summary We have presented an algorithml that reconstructs all solids, bounded by planes and quadrics, that correspond to a pair of prespecified orthogonal views. As a byproduct, the missing third views are also obtained. The algorithm insures completeness by considering all candidate faces for inclusion ill the solid. Consistency with the given views guarantees validity of the generated solids and correctness of the algorithm. Visualization in three dimensions is a difficult task. For complex solids, even when all three views are provided, a manuual reconstruction process can be very complicated. It requires ascertaining correspondence between the given views and then construction of the solid based on the views. The reconstruction problem considered in this paper is lore dlifficult blecause of the combinatorial nature of the solution brought al)out by the incomplete specification. The solution procedure can benefit extelsivelv frolll ser illteraction (a.s in Example 1). Since. a two-view representation typically corresponds to multiple solids. the search process can be guided to exclude classes of solids that the user deems unnecessarv. Acknowledgements We thank Professor Doug W\ilde of Stanford University for suggesting this problem for further study. 7 References 1. Aldefield. B.. (1983) ".-utomlatic;3-D reconlstruction from 2-D geometric part descriptions." in Proceedings of IEEE C'onference on Comlputer Vlision and Pattern Recognition 1983. pp.66-72. 2. Faux. I.D. and Pratt. M[.J.. (1979) Conlput ttional Geom1etry for Design and,M1anufacture, Ellis Iforwood Publishers. 3. tlarlick. R. MI.. and Shapiro. L. G.. (1982) "Unlerstanding Engineering Drawings" Conmputer (Graphic.s iznd Iinzagc Poces.sinlg Vol. 20. pp. 2 14-258 4. Idesawa. MI.. Soma. T.. Goto. E.. and Shibata. S.. (197,5) "Automatic Input of Line Drawings and Generation of Solid Figure from Tllree-View Data' Proceedings of fnterrnatihonl C'oznlputer.5ynllposilizn. V'ol II. pp.:304-:311 3. Lafue, G.. (1976) "Recognitioni of Tllhree-Dimensio lla l Olbjects from Orthographic V'iews" C'olpupter (G'l'aphlic.s \'ol. 0l..o. 2 20

6. Luzadder. W.J.. (1986) Fulndamclztals of El2ginuering Drawing, Ninth Edition, Prentice Iall 7. Markowsky G.. and NWesley, I. A.. (1980) "Fleshing out Wire Frames," IBAM Journal of Research and Development Vol. 2-1, No. 5, pp. 582-597. 8. TMarkowsky G.. and Wesley. MI. A.. (1981) "Fleshing out Projections." IBM1 Journal of Research and Developnent Vol. 2-t, No. 6. pp. 934-9354. 9. Preiss, K., (1981)'.Algorithms for automatic conversion of a 3-view drawing of a plane-faced part to the;3-D respresentation." Conmputers in Industry vol. 2, pp. 133-139. 10. Sakurai. II.. and Gossard D.C.. ( 198:3) "Solid Mlodel Input through Orthographic Views" Coomrpultcr G,(Y'phlics vol. 17. No. 3. pp. 2 13-247. 11. Sugilhara. I; (1.985).lHIchl.ile lntcrpreptlatioi of Linze Drwnlzngs.. MIT Press 12. CWilde. D. J.. (1991)'Tlhe Geomietry of Spatial Visualization: Two Problems." manuscript. To b)e l)Iresetlted(l t tl Sh ITO.1I Ill'old COIngrcss Prague, August 1991. 21

3 9015 02924