Methods and apparatuses for generating sculptured surfaces
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to methods and apparatuses for generating sculptured surfaces for use with the designing apparatus for CAD/CAM (computer aided design/computer aided manufacturing) applications. 
     2. Description of the Related Art 
     In a geometric modeling application where an object with a sculptured surface is to be designed, the designer designates a plurality of points (called nodes) in the three-dimensional space to be traversed by that surface. The designated nodes are calculated using a desired vector function so that the nodes are connected by a boundary curve network. This provides a surface expressed by what is known as a wire frame. In this manner, there are generated a large number of frame spaces enclosed by boundary curves (this is called a framing process). 
     The boundary curve network generated by the framing process presents itself approximately as what the designer wants to design. In this case, a surface may be interpolated as the expression of a predetermined vector function using the boundary curves that enclose each frame space. Taken as a whole, this is the sculptured surface designated by the designer (and not defined by secondary functions). Each surface occupying each frame space constitutes a component that makes up the entire surface. The component is called a patch. 
     As disclosed in a Japanese Laid-Open Patent Application 62-135965 published in June 1987, there was proposed a free curve generating method whereby the control side vectors around a common boundary between two adjacent frame spaces are modified in order to establish a patch that will satisfy the condition for tangent plane condition on that common boundary. The major object of this prior art method is to provide the entire sculptured surface with a more natural external shape. 
     FIG. 1 shows the prior art sculptured surface generating method involves first locating a patch vector S(u,v)l and a patch vector S(u,v)2 in a rectangular frame space and having them expressed by a vector function S(u,v) constituting a cubic Bezier equation. The two patch vectors S(u,v)1 and S(u,v)2 are connected smoothly as follows. When node vectors P(00), P(30)1, P(33)1, P(03), P(33)2, and P(30)2 are furnished by the framing process, there are accordingly established control side vectors a1, a2, c1, and c2 in such a manner that the condition for tangent plane continuation is met on a common boundary COM between adjacent patch vectors S(u,v)1 and S(u,v)2. These control side vectors are used to modify control point vectors P(11)1, P(12)1, P(11)2, and P(12)2. 
     The above method is applied consecutively to other common boundaries. This eventually results in the smooth connection of the patch vectors S(u,v)l and S(u,v)2 on the condition of tangent plane continuation with the adjacent patches. The vector function S(u,v) constituted by a cubic Bezier equation is expressed as: 
     
         S(u,v)=(1-u+uE).sup.3 (1-v+vF).sup.3 P(00)                 (1) 
    
     where, &#34;u&#34; and &#34;v&#34; are parameters for &#34;u&#34; and &#34;v&#34; directions respectively, and E and F are shift operators. Furthermore, the vector function S(u,v) has those relations with a control point vector P(ij) which are defined as: 
     
         E·P(ij)=P(i+1j) (i,j=0,1,2)                       (2) 
    
     
         E·P(ij)=P(i j+1) (i,j=0,1,2)                      (3) 
    
     
         0≦u≦1                                        (4) 
    
     
         0≦v≦1                                        (5) 
    
     The tangent plane is a plane formed by tangent vectors in the &#34;u&#34; and &#34;v&#34; directions at each of the nodes on a common boundary. For example, where the patch vectors S(u,v)1 and S(u,v)2 in FIG. 1 share the same tangent plane on a common boundary COM12, the condition of tangent plane continuation is met. 
     The above prior art method allows the designer to design cubic shapes that are otherwise difficult to design, such as those whose surfaces change smoothly. 
     Quality design reflecting the sensitivity of the designer may be obtained by using such a designing apparatus to generate between two free curves spaced at a non-uniform distance in the three-dimensional space, a sculptured surface corresponding to a track obtained by rotating a sphere. In this case, one of the free curves is used as a base line, while the other is used as a relative line. A plane is defined using, as the normal, a tangent at each point on the base line, and the intersection of each of the defined planes and the relative line is determined. This is inconvenient in that as many planes as the points on the base line must be defined and that the intersections of all the planes and the relative line must be determined. 
     In addition, circular arcs of a specified radius are generated on each of the planes using a point on the base line and the corresponding intersection on the relative line as endpoints. Since these circular arcs are generated using the point on the base line and the intersection on the relative line, the center of the circular arc must be determined. Processing for selecting between two circular arcs generated is also required. Since this processing must be performed for all the points on the base line, it takes a large amount of time and inconvenience. 
     Furthermore, although such a group of circular arcs are converted into a free curve patch to generate a sculptured surface between the two free lines, a free curve patch cannot be generated easily from a group of circular arcs, resulting in an inaccurate patch. In addition, sculptured surfaces generated may have a non-uniform curvature, and a sculptured surfaces cannot be generated easily when curves have very inconstant geometries. 
     SUMMARY OF THE INVENTION 
     In view of the foregoing, an object of this invention is to provide a methods and an apparatuses for generating sculptured surfaces which enable a sculptured surface of a specified radius to be generated easily between two free curves. 
     The foregoing object and other objects of the invention have been achieved by the provision of a method for generating a sculptured surface corresponding to the track of a sphere rotated between a first and a second free curves in the three-dimensional space, comprising the steps of: setting a plurality of base points Qi on the first free curve A; generating a plurality of planes PLi using, as the normal, a tangent Vi of the first free line A at each of the base points Qi, the planes including that base point Qi; determining a plurality of intersections Pi of the second free curve B and the plurality of planes PLi; generating a plurality of circular arcs ARCi of a specified radius on each of the plurality of planes PLi using the base point Qi and the intersection Pi as endpoints, and generating a sculptured surface based on the first free curve A, the second free curve B, and the plurality of circular arcs ARCi. 
     This invention also comprises a plane generation means for setting a plurality of base points Qi on the first free curve A and generating a plurality of planes PLi using, as the normal, a tangent Vi of the first free line A at each of the base points Qi, the planes including that base point Qi; an intersection detection means for determining a plurality of intersections Pi of the second free curve B and the plurality of planes PLi generated by the plane generation means; a circular arc generation means for generating a plurality of circular arcs ARCi of a specified radius on each of the planes PLi using the base point Qi and the intersection Pi as endpoints; and a sculptured surface generation means for generating a sculptured surface based on the first free curve A, the second free curve B, and the plurality of circular arcs ARCi. 
     A sculptured surface of a specified radius can be generated easily between two free curves by setting a plurality of base points Qi on the first free curve A; generating a plurality of planes PLi using, as the normal, a tangent Vi of the first free line A at each of the base points Qi, the planes including that base point Qi; determining a plurality of intersections Pi of the second free curve B and the plurality of planes PLi; generating a plurality of circular arcs ARCi of a specified radius using the base point Qi and the intersection Pi as endpoints on each of the plurality of planes PLi, and generating a sculptured surface based on the first free curve A, the second free curve B, and the plurality of circular curves ARCi. 
     The nature, principle and utility of the invention will become more apparent from the following detailed description when read in conjunction with the accompanying drawings in which like parts are designated by like reference numerals or characters. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     In the accompanying drawings: 
     FIG. 1 is a schematic view explaining the prior art sculptured surface; 
     FIG. 2 is a block diagram showing the overall configuration of an embodiment of a CAD/CAM system to which a method and an apparatus for generating sculptured surfaces according to this invention are applied; 
     FIG. 3 is a schematic diagram explaining a method for expressing a free curve by a vector function; 
     FIG. 4 is a flowchart showing a procedure for generating a sculptured surface between two free curves; 
     FIG. 5 is a schematic diagram showing two free curves specified by the operator; 
     FIG. 6 is a schematic diagram showing a plane defined using, as the normal, a tangent at a point specified on one of the free curves in FIG. 5; 
     FIG. 7 is a schematic diagram showing the intersection of the plane in FIG. 6 and the other free curve; 
     FIG. 8 is a schematic diagram showing the intersections of two circles drawn using the respective points on the two free curves in FIG. 7 as centers; 
     FIG. 9 is a schematic view showing circular arcs with the respective intersections of the circles in FIG. 8 as their centers; 
     FIG. 10 is a schematic view showing tangential vectors of the respective circular arcs in FIG. 9 and their cross product; 
     FIG. 11 is a schematic view showing a group of circular arcs generated from a group of points set on one of the free curves; 
     FIG. 12 is a schematic view showing a sculptured surface generated between the two free curves in FIG. 5; 
     FIG. 13 is a schematic view showing another sculptured surface generated between the two free curves in FIG. 5; and 
     FIGS. 14A to 14C are schematic views showing examples of sculptured surfaces generated between two free curves. 
    
    
     DETAILED DESCRIPTION OF THE EMBODIMENT 
     Preferred embodiments of the invention will be described with reference to the accompanying drawings: 
     (1) Overall configuration of CAD/CAM system 
     In FIG. 2, reference numeral 10 is a typical CAD/CAM system in its entirety to which the invention is applied. A sculptured surface generating device 12 generates shape data DTS representing a sculptured surface. After generation of the shape data DTS, a tool path generating device 13 generates cutting data DTCL for cutting work. 
     The sculptured surface generating device 12 has a central processing unit (CPU) that controls a display 16. The designer responds to indications on the display 16 and operates an input device 17 accordingly. In doing so, the designer designates a wire frame model and establishes therein a patch using a cubic Bezier equation. The patch is then modified in order to generate the shape data DTS representing the desired object having a sculptured surface. 
     Using the shape data DTS, the tool path generating device 13 generates the cutting data DTCL for roughing and finishing a metal die. Thereafter, the cutting data DTCL is output illustratively via a floppy disk 15 to a numerically controlled (NC) milling machine 14. The NC milling machine 14 illustratively drives an NC miller using the cutting data DTCL. This completes work on the metal die by which to produce the product represented by the shape data DTS. 
     (2) Principles of free curve 
     As shown in FIG. 3, a Bezier curve is expressed by use of a cubic Bezier equation representing a parametric space curve vector R(t) given as: 
     
         R(t)=(1-t+tE).sup.3 P0                                     (6) 
    
     where &#34;t&#34; is the parameter varying from &#34;0&#34; to &#34;1&#34;, i.e., 
     
         0≦t≦1                                        (7) 
    
     The range of (7) above holds from a node vector P0 to another node vector P3 along a curve segment KSG. 
     Two control point vectors P1 and P2 are designated using a shift operator E between the node vectors P0 and P3. The curve segment KSG, expressed by the cubic Bezier equation, is represented by the points given by the position vector R(t) relative to origin 0 of an XYZ space, the vector being furnished by expanding the equation: 
     
         R(t)=(1-t).sup.3 P0+3(1-t).sup.2 tP1+3(1-t)t.sup.2 P2+t.sup.3 P3(8) 
    
     The shift operator E has certain relations with control point vectors Pi on the curve segment KSG, the relations being given as: 
     
         E·Pi=Pi+1                                         (9) 
    
     Where, 
     
         i=0, 1, 2                                                  (10) 
    
     When Equation (6) is expanded and Equation (9) is inserted therein, one gets: ##EQU1## As a result of this , Equation (8) is obtained. 
     Thus the curve segments KSG1, KSG2, and KSG3 expressed by the Bezier curve are represented by two node vectors and two control point vectors each, i.e., P(0)1 through P(0)3, P(1)1 through P(1)3, P(2)1 through P(2)3, and P(3)1 through P(3)3, based on Equation (8). When the control point vectors P(1)1 through P(1)3 and P(2)1 through P(2)3 are established between the node vectors P(0)1 through P(0)3 on the one hand and P(3)1 on the other, a free curve is established whose shape is determined by the control point vectors P(0)1 through P(0)3, P(1)1 through P(1)3, P(2)1 through P(2)3 and P(3)1 through P(3)3, the shape passing through the node vectors P(0)1 through P(0)3 and P(3)1. 
     (3) Procedure for generating a sculptured surface between two free curves 
     The sculptured surface generating device 12 generates a sculptured surface between two free curves provided by the operator in the three-dimensional space and having a non-uniform distance between themselves, using a track obtained by moving a sphere between the two free curves. That is, in the procedure for generating a sculptured surface between two free curves shown in FIG. 4, the sculptured surface generating device 12 starts processing at step SP0 and proceeds to step SP1. As shown in FIG. 5, when the operator specifies two Bezier curve vectors A and B in the three-dimensional space, the data on the two vectors is loaded into the device. In this case, the Bezier curve vector A is used as a base line, while the Bezier curve vector B is used as a relative line. 
     In fact, base line vector A specified in this manner is defined by node vector PA0, vector PA3, internal control point vector PA1, and vector PA2, and expressed by the following equation: 
     
         A(t)=(1-t).sup.3 PA0+3(1-t).sup.2 tPA1+3(1-t)t.sup.2 PA2+t.sup.3 PA3(12) 
    
     that is obtained by modifying Equation (11). 
     Similarly, relative line vector B is defined by node vector PB0, vector PB3, internal control point vector PB1, and vector PB2, and expressed by the following equation: 
     
         B(t)=(1-t).sup.3 PB0+3(1-t).sup.2 tPB1+3(1-t)t.sup.2 PB2+t.sup.3 PB3(13) 
    
     that is obtained by modifying Equation (11). 
     At step SP2, the sculptured surface generating device 12 determines ten point vectors Qi (i=1 to 10) on base line vector A using parameter division. These point vectors Qi (i=1 to 10) are arbitrary points that can move on base line vector A, and are expressed by the following expression: 
     
         Qi(t)=(1-t).sup.3 PA0+3(1-t).sup.2 tPA1+3(1-t)t.sup.2 PA2+t.sup.3 PA3(14) 
    
     The sculptured surface generating device 12 then proceeds to step SP3 to determine a tangent of each of point vectors Qi on base line vector A. The tangent of point vector Qi can be expressed by the following expression: 
     
         Vi(t)=-3(1-t).sup.2 PA0+3(3t.sup.2 -4t-1)PA1+3(2t-3t.sup.2)PA2+3t.sup.2+3 t.sup.2 PA3                                               (15) 
    
     Since a plane can be defined by a single point and a normal, as shown in FIG. 6, tangential vector Vi of point vector Qi is defined as a normal to determine plane vector PLi from point vector Qi and normal vector Vi. 
     After determining plane vector PLi at step SP3, the sculptured surface generating device 12 proceeds to step SP4. As shown in FIG. 7, the device determines point vector Pi on relative line vector B which corresponds to each of the point vector Qi on base line vector A. Point vector Pi can be determined from the intersection of plane vector PLi and relative line vector B. 
     The sculptured surface generating device 12 then determines two circular arcs passing point vectors Pi and Qi at step SP5, as shown in FIG. 8. First, the end of the circular arcs is referred to as point vector Qi on base line vector A, while the beginning of the circular arcs is referred to as point vector Pi on relative line vector B. To locate the circular arcs on plane vector PLi, the centers of the circular arcs must exist on plane vector PLi. Circle vector C1i of an arbitrary radius &#34;r&#34; is thus generated on plane vector PLi using point vector Qi on base line vector A as the center of the circle. 
     Similarly, circle vector C2i of an arbitrary radius &#34;r&#34; is generated on plane vector PLi using point vector Pi on relative line vector B as the center of the circle. In this case, the intersections of circle vector C1i and circle vector C2i are referred to as vectors R1i and R2i, respectively. Circular arc vector ARCi1 with beginning vector Qi, end vector Pi, and radius &#34;r&#34; is then generated using intersection vector R1i of circle vector C1i and vector C2i, as shown in FIG. 9. Similarly, circular arc vector ARCi2 with beginning vector Qi, end vector Pi, and radius &#34;r&#34; is then generated using intersection vector R2i of circle vector C1i and vector C2i. 
     After two circular arc vectors ARCi1 and ARCi2 have been generated, the process proceeds to step SP6. First, directional vector from point vector Qi on base line vector A to point vector Pi on relative line vector B is referred to as vector Wi. If the cross product of tangential vector Vi and directional vector Wi at point vector Qi on base line vector A is referred to as vector Xi, it is expressed by the following expression: 
     
         Xi=Vi * Wi                                                 (16) 
    
     In addition, as shown in FIG. 10, tangential vectors Y1i and Y2i at point vector Qi on both circular arc vectors ARC1i and ARC2i are expressed by the following equations: 
     
         Y1i=(R1i-Qi) * Vi                                          (17) 
    
     
         Y2i=(R2i-Qi) * Vi                                          (18) 
    
     Angle θ1i between cross product vector Xi and tangential vector Y1i can be expressed by the following equation: 
     
         θ1i=acos (Xi·Y1i)                           (19) 
    
     Angle θ2i between cross product vector Xi and tangential vector Y2i can be expressed by the following equation: 
     
         θ2i=acos (Xi·Y2i)                           (20) 
    
     In selecting from two circular arcs, circular arc ARC1i or ARC2i having tangential vector Y1i or Y2i close to cross product Xi is selected so that a plurality of circular arcs generated from point vector Qi (i=1 to 10) are all located on one side relative to point vectors Pi and Qi (i=1 to 10). That is, since the smaller of two angles θ1i, θ2i is selected, circular arc vector ARCi2 is selected if angle θ2i is smaller than angle θ1i, whereas circular arc vector ARCi1 is selected if angle θ1i is smaller than angle θ2i. 
     At step SP7, the process determines whether or not circular arc vectors ARCi (i=1 to 10) have been determined from all the ten point vectors Qi (i=1 to 10) on base line. If the result is negative, the process returns to step SP3 to continue processing. If the result is affirmative (FIG. 11), the process returns to step SP8 to determine point group vector ARij on each of the circular arcs by dividing each of the circular arc vectors ARCi (i=1 to 10) using parameter &#34;j&#34; (j=1 to 10). 
     The process then proceeds to step SP9 to generate a sculptured patch, as shown in FIG. 12, by means of least square approximation based on point group vector ARij (i, j=1 to 10) within four boundary curves: base line vector A, relative line vector B, circular arc vector ARC1, and circular arc vector ARC10. It terminates processing at step SP10. The method of least square approximation is disclosed in Ser. No. 08/267,838 which was filed by the same applicant on Jun. 28, 1994 and is now U.S. Pat. No. 5,410,645. Ser. No. 08/267,838 is a continuation of Ser. No. 07/853,918 filed on Mar. 19, 1994, now abandoned. The corresponding EP Patent Application was laid open on Sep. 23, 1992, published as 0504889 A2. 
     In generating a sculptured surface between two free curves spaced at a non-uniform distance using a track obtained by moving a sphere between the two free curves, the above configuration can generate a plane, determine the intersection of the relative line and the plane, generate circular arcs from the intersection, and generate a sculptured surface, thereby reducing processing time and enabling a sculptured surface of a uniform curvature to be generated. In addition, quality design reflecting the designer&#39;s sensitivity can be obtained. 
     (4) Other embodiments 
     In the above embodiment, in generating circular arcs, the smaller of angles θ1i and θ2i is selected to select a circular arc having a tangential vector constituting this angle. This invention is, however, not limited to this aspect, but the same effect can be produced by selecting the larger of angles θ1i and θ2i to select a circular arc having a tangential vector constituting this angle. A sculptured surface generated in this manner is shown in FIG. 13. 
     In addition, in the above embodiment, a sculptured surface is produced between two free curves spaced at a non-uniform distance. This invention is, however, not limited to this aspect, but a sculptured surface can be produced between two circles or two intersecting free curves spaced at a non-uniform distance, as shown in FIGS. 14A to 14C. 
     Furthermore, in the above embodiment, a sculptured surface is produced based on a plurality of circular arc vectors ARCi (i=1 to 10) generated using an arbitrary specified radius &#34;r&#34;. This invention is, however, not limited to this aspect, but a sculptured surface can be produced based on a plurality of circular arcs of different radius. 
     As described above, this invention enables a sculptured surface of a specified radius to be generated easily between two free curves by generating a plane using, as the normal, a tangent at a base point on the first free curve; determining the intersection of the second free curve and the plane; generating circular arcs for each of the points on the first free curve using the base point and the intersection as endpoints; and generating a sculptured surface. 
     While there has been described in connection with the preferred embodiments of the invention, it will be obvious to those skilled in the art that various changes and modifications may be aimed, therefore, to cover in the appended claims all such changes and modifications as fall within the true spirit and scope of the invention.