Patent Publication Number: US-8525838-B2

Title: Associative fillet

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application is related to the following co-pending and commonly-assigned patent(s) and patent application(s), which patents and applications are incorporated by reference herein: 
     U.S. Pat. No. 6,867,771, issued on Mar. 15, 2005, and filed on May 7, 2002, entitled “CONTROLLED FACE DRAGGING IN SOLID MODELS”, by Jiri Kripac; 
     U.S. patent application Ser. No. 10/132,544, filed on Apr. 25, 2002, entitled “FACE MODIFICATION TOOL”, by Sha Wang, William L. Myers, and John R. Wallace; and 
     U.S. patent application Ser. No. 11/376,654, filed on Mar. 15, 2006, entitled “CONTROLLED TOPOLOGY TWEAKING IN SOLID MODELS”, by Jiri Kripac. 
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates generally to two-dimensional and three-dimensional computer-aided design (CAD) drafting systems, and in particular, to a method, apparatus, and article of manufacture for the creation and use of an associative fillet in a 2D or 3D CAD system. 
     2. Description of the Related Art 
     The use of computer-aided design (CAD) application programs is well known in the art. CAD application programs are often used to design, develop, and optimize a two-dimensional (2D) or three-dimensional (3D) representation of a product, tools and machinery used in the manufacture of components, and/or in the drafting and design of buildings. When two geometric objects/entities are joined together in a CAD application, there often is need to round the sharp corner at the joint, and/or to make a smooth transition between the two geometric entities to maintain tangency continuity (G1 continuity). Such transitional shapes that represent smooth transitions between two or more geometric entities are called fillets or blends. Fillets in 2D drafting systems are often represented by circular arcs, but they can be arbitrary curves. 
     Fillets in prior art CAD application programs are independent entities and are not directly associated with the two entities. Accordingly, in the design process, if either one of the two entities is edited, the already created fillet needs to be manually erased and recreated. Such problems may be better understood with an explanation of the use and creation of fillets in the prior art. 
       FIG. 1A  illustrates a fillet created in accordance with the prior art. Most CAD applications (and 2D drafting systems), including AutoCAD™ (available from the assignee of the present invention), contain a tool that creates a fillet  100 A between two selected curves  102  and  104  by adding a circular arc (or, in a general case, an arbitrary blending curve) tangent to the two curves  102  and  104  and extending or trimming the curves  102  and  104  to the endpoints of the new arc  100 A. The fillet arc  100 A is an independent entity not associated with the curves  102  and  104 . When the curves  102  and  104  are edited, the already created fillet arc  100 A needs to be manually erased and recreated. The creation and editing process is as follows: 
     (1) (a) Use a “FILLET” command;
         (b) Select two existing curves  102  and  104 ;   (c) Specify radius; and   (d) A new fillet arc  100 A is created.       

     (2) (a) Edit one or both of the filleted curves  102 / 104 ;
         (b) The fillet arc  100 A does not change.       

     (3) Erase the fillet arc  100 A. 
     (4) (a) Use “FILLET” command;
         (b) Reselect the same curves  102  and  104 ;   (c) Specify radius; and   (d) A new fillet arc  100 B is created.
 
Steps 2-4 may possibly need to be repeated multiple times. Accordingly, each time one of the existing curves  102  or  104  is edited, the fillet needs to be deleted and recreated.
       

       FIG. 1B  illustrates prior art fillet  100 A that is not automatically recalculated when curve  104  of  FIG. 1A  is independently stretched from its prior end point  106 A to its new location  106 B. In addition, the apparent intersection of curves  102  and  104  is not utilized. Instead, the top of vertical curve  104  remains the same and the new endpoint  106 B is used for the bottom of curve  104 . 
     Some 2D drafting systems support constraints between geometric entities. Such systems allow creating fillets in 2D sketches using constraints that preserve the fillet arc when the curves are edited, but behave non-intuitively and ambiguously. For example, the fillet arc  100 A can be defined by tangency constraints between the fillet arc  100 A and the to curves  102 / 104 , a radial constraint, and coincidence constraints between the endpoints of the arc and the corresponding endpoints of the to curves  102 / 104 . When any geometric entities  102 / 104  are edited, the drafting system invokes a constraint solver that automatically changes other geometric entities to satisfy the given constraints. 
     Defining a fillet  100 A by constraints does not guarantee intuitive behavior when the filleted curves  102 / 104  or the fillet radius is edited. For instance, referring to  FIG. 1C , when one curve  104  is edited by the user (i.e., by moving the endpoint  106 A to location  106 B), the constraint solver may decide to reposition the other curve  102  in order to satisfy the constraints instead of updating the fillet arc  100 A. Or, when the fillet arc radius is edited, the constraint solver may decide to reposition the to curves  102 / 104  instead of repositioning the fillet arc  100 A. When the endpoint  106 A of the curve  104  is stretched to its new location  106 B, as illustrated in  FIG. 1C , a prior art constraint solver would likely decide to maintain the fillet arc center fixed as depicted by arc  108 , which would not result in the desired behavior in most cases. 
     In view of the above, what is needed is a method that allows the fillet arcs to automatically update when the filleted curves or the fillet radius is edited. Such an automatic update further needs to behave intuitively and unambiguously. 
     SUMMARY OF THE INVENTION 
     To overcome the problems of the prior art, one or more embodiments of the invention provide for an associative framework that is utilized to provide an associative fillet action. This action within the associative framework utilizes two input curves to be filleted and can also include a fillet radius. The result of the evaluation of this action is a fillet arc that is tangent to the two input curves and trims or extends the input curves to the arc. 
     The fillet arc is associated with the two input curves such that if a property of either input curve is modified (or the radius of the fillet curve is modified), the fillet action is re-evaluated and the fillet curve is automatically and dynamically recalculated. Further, the input curves may be re-trimmed/re-extended to the fillet curve based on the recalculation. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Referring now to the drawings in which like reference numbers represent corresponding parts throughout: 
         FIG. 1A  illustrates a fillet created in accordance with the prior art; 
         FIG. 1B  illustrates a prior art fillet that is not recalculated when a curve is independently stretched; 
         FIG. 1C  illustrates a possible outcome if a prior art constraint solver is used to adjust a fillet arc; 
         FIG. 2  is an exemplary hardware and software environment used to implement one or more embodiments of the invention; 
         FIG. 3  is a block diagram that illustrates the components of a computer graphics program in accordance with one or more embodiments of the invention; 
         FIG. 4  is a block diagram that illustrates the structure of an object list in accordance with one or more embodiments of the invention; 
         FIGS. 5A and 5B  illustrate the use of an associative fillet in accordance with one or more embodiments of the invention; 
         FIGS. 6A-6C  illustrate the result of stretching of geometry when using the new associative fillet ( FIG. 6B ) and when using a prior art constraint solver ( FIG. 6C ) in accordance with embodiments of the invention; and 
         FIG. 7  is a flowchart illustrating the process for updating a filleted curve in accordance with one or more embodiments of the invention. 
     
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     In the following description, reference is made to the accompanying drawings which form a part hereof, and which is shown, by way of illustration, several embodiments of the present invention. It is understood that other embodiments may be utilized and structural changes may be made without departing from the scope of the present invention. 
     Overview 
     A method, apparatus, and article of manufacture provide for the ability to associate a fillet arc with two geometric entities and automatically and dynamically update the fillet arc when one or more of the entities are modified/edited. 
     Hardware and Software Environment 
       FIG. 2  is an exemplary hardware and software environment used to implement one or more embodiments of the invention. Embodiments of the invention are typically implemented using a computer  200 , which generally includes, inter alia, a display device  202 , data storage devices  204 , cursor control devices  206 , and other devices. Those skilled in the art will recognize that any combination of the above components, or any number of different components, peripherals, and other devices, may be used with the computer  200 . 
     One or more embodiments of the invention are implemented by a computer-implemented graphics program  208 , wherein the graphics program  208  is represented by a window displayed on the display device  202 . Examples of such a computer graphics program  208  include a computer-aided design (CAD) application, a modeling application, 2D drafting programs, etc. Generally, the graphics program  208  comprises logic and/or data embodied in or readable from a device, media, carrier, or signal, e.g., one or more fixed and/or removable data storage devices  204  connected directly or indirectly to the computer  200 , one or more remote devices coupled to the computer  200  via a data communications device, etc. 
     In one or more embodiments, instructions implementing the graphics program  208  are tangibly embodied in a computer-readable medium, e.g., data storage device  204 , which could include one or more fixed or removable data storage devices, such as a zip drive, floppy disc drive, hard drive, CD-ROM drive, tape drive, etc. Further, the graphics program  208  is comprised of instructions which, when read and executed by the computer  200 , causes the computer  200  to perform the steps necessary to implement and/or use the present invention. Graphics program  208  and/or operating instructions may also be tangibly embodied in a memory and/or data communications devices of computer  200 , thereby making a computer program product or article of manufacture according to the invention. As such, the terms “article of manufacture” and “computer program product” as used herein are intended to encompass a computer program accessible from any computer readable device or media. 
     Those skilled in the art will recognize that the exemplary environment illustrated in  FIG. 2  is not intended to limit the present invention. Indeed, those skilled in the art will recognize that other alternative environments may be used without departing from the scope of the present invention. 
     Computer-Implemented Graphics Program 
       FIG. 3  is a block diagram that illustrates the components of the computer graphics program  208  in accordance with one or more embodiments of the invention. There are three main components to the graphics program  208 , including: a Graphical User Interface (GUI)  300 , an Image Engine (IME)  302 , and a DataBase (DB)  304  for storing objects in Drawing (DWG) files  306 . 
     The Graphical User Interface  300  displays information to the operator and provides the functionality for the operator&#39;s interaction with the graphics program  208 . 
     The Image Engine  302  processes the DWG files  306  and delivers the resulting graphics to the monitor  202  for display. In one or more embodiments, the Image Engine  302  provides a complete application programming interface (API) that allows other computer programs to interface to the computer graphics program  208  as needed. 
     The Database  304  is comprised of two separate types of databases: (1) a 3D database  308  known as the “3D world space” that stores 3D information; and (2) one or more 2D databases  310  known as the “2D view ports” that stores 2D information derived from the 3D information. 
     Object List 
       FIG. 4  is a block diagram that illustrates the structure of an object list  400  maintained by the 3D databases  308  in accordance with one or more embodiments of the invention. The object list  400  is usually comprised of a doubly linked list having a list head  402  and one or more objects  404  interconnected by edges  406 , although other structures may be used as well. There may be any number of different object lists  400  maintained by the 3D databases  308 . Moreover, an object  404  may be a member of multiple object lists  400  in the 3D databases  308 . 
     Operation of the Software Embodiment 
     In one or more embodiments of the invention, the graphics program  208  provides for an associative fillet.  FIGS. 5A and 5B  illustrate the use of an associative fillet in accordance with one or more embodiments of the invention. In  FIG. 5A , to create the associative fillet, an action takes as its input two curves (e.g., curves  502  and  504 ) to be filleted and the fillet radius. The action creates a fillet arc  500 A tangent to the two input curves and trims or extends the input curves to the arc. It exhibits the following intuitive behaviors: 
     (1) When the user edits one or both filleted curves  502 / 504 , or edits the fillet radius, the fillet arc  500 A is automatically recalculated (into  500 B) and the filleted curves  502 / 504  are re-trimmed/re-extended, but not repositioned. This is happening dynamically in real time. 
     (2) Explicitly repositioning of the fillet arc  500 A is disabled. The fillet arc  500 A is fully defined by the filleted curves  502 / 504  and by its radius. The fillet arc  500 A does not show grips that control its position, only a grip that controls its radius. 
     When stretching one endpoint  506 A of a curve  504  (i.e., to location  506 B) that has an associative fillet  500 A at the opposite end, the apparent intersection  508  of the two curves  502 / 504  is used as the base point for the stretch operation. The result provides intuitive behavior by forming fillet  500 B, unlike if the curve  500 A was stretched independently and then the fillet recalculated. In this regard,  FIG. 5B  illustrates the resulting behavior when the apparent intersection  508  is not utilized during the stretch operation (resulting in the filleted curve  500 B behaving in a non-intuitive manner). If constraints were used to define the fillet  500 A, the constraint solver would likely decide to keep the fillet arc center fixed, which would not be the desired behavior in most cases (i.e., as in  FIG. 1C ). 
     The stretching of geometry is useful to better understand how associative fillets are processed in accordance with the invention.  FIGS. 6A-6C  illustrate the result of stretching of geometry when the new associative fillet is applied ( FIG. 6B ) and when a prior art solution of using a constraint solver is applied ( FIG. 6C ).  FIG. 6A  illustrates the direction  602  the geometry  600  will be stretched. As illustrated in  FIG. 6B , the associative fillets  604  and  606  behave intuitively in accordance with the invention because the associative fillet action recreates the fillet arcs  604 / 606  in the correct orientation and location relative to the filleted curves  600 / 608 / 610 . 
     However, if constraints (as in the prior art) are used to define the fillet arcs  604 / 606 , the fillets do not behave intuitively as illustrated in  FIG. 6C , because the constraint solver treats the fillet arcs as ordinary arcs, not as fillets that have special behaviors. The result illustrated in  FIG. 6B  is possible because the associative fillet actions (i.e., the subject of the invention) remember the relative positions of the fillets  604 / 606  with respect to the filleted/input curves  608 / 600 / 610  and reuse this information every time they recalculate the fillet arcs  604 / 606 . 
     Logic of the Graphics Program 
       FIG. 7  is a flowchart illustrating the process for updating a filleted curve in accordance with one or more embodiments of the invention. At step  700 , a computer-implemented drawing is displayed on a display device. The drawing contains a first input curve and a second input curve. 
     At step  702 , the first input curve and the second input curve are selected. Such selection may be conducted by a user selecting the curves (e.g., via a cursor control device such as a mouse while clicking a mouse button on particular curves in the drawing or selecting curves from a list of curves [e.g., in a properties palette]). Further, such curves may be Bezier curves, lines, geometry, shapes, etc. in accordance with embodiments of the invention. 
     At step  704 , a fillet curve is established. Such an establishing may consist of calculating, creating, and displaying the fillet curve between the first input curve and the second input curve. As described above, the fillet curve may comprise a fillet arc that is tangent to the first and second input curves. Further, the first and second input curves may be trimmed or extended to the fillet arc. 
     At step  706 , a property of one or more of the input curves or the radius of the fillet curve is modified. For example, the endpoint of one of the input curves may be stretched. Alternatively, a selection of geometry (e.g., consisting of the two input curves and the fillet curve) may be stretched. A grip or icon on the fillet curve may also be used to modify the radius of the fillet curve. Such a modification of a property of the input curves or the radius of the fillet curve may be performed by the user via a mouse (or pen and tablet device) to drag a grip or point. Alternatively, the property(ies) may be modified in a properties palette by the user entering a new value for a property. Accordingly, embodiments of the invention may be utilized to both directly manipulate the input curves/radius or utilize a properties palette. While the direct manipulation and/or property palette are described herein, the invention is not limited to such practices and any method that can be used to modify a property of a curve/geometry may be used in accordance with the invention. 
     At step  708 , the fillet curve is recalculated based on the modification to the property/radius. The recalculation is performed automatically (i.e., without additional user input) and may be performed dynamically in real time. For example, the fillet action in an associative framework may be used to create a fillet curve based on particular inputs (e.g., input curves and/or radius). The output from the fillet action is a fillet arc. Thus, each action is therefore associated with particular inputs. If the input changes (e.g., the property of the input curves or the radius of the fillet arc changes), the associative framework collects all the affected actions and re-evaluates them, which updates the outputs based on the changed inputs. 
     Within step  708 , the input curves may be re-trimmed or re-extended to the fillet arc as a result of the recalculation. Further, during such actions, the first and second input curves may not be repositioned when the fillet curve is recalculated. In addition, an apparent intersection of the first input curve and second input curve may be used as the base point when the input curves are stretched. As used herein, an “apparent intersection” is defined as the extrapolated point resulting from unbinding two closed/bound curves and determining the resulting intersection of the two unbound curves. Such a use of a base point provides the ability for the fillet action to behave in a more user intuitive manner when endpoints of the first or of the second input curve are stretched. In addition, the relative position of the fillet curve with respect to the two input curves may be maintained when conducting the recalculating. For example, if the fillet curve provides a certain position with respect to the input curves (e.g., as illustrated in  FIG. 6A ), such a position may be maintained in the recalculation (e.g., see  FIG. 6B ). By maintaining the relative position between input curves and the fillet arc, non-intuitive behavior such as that illustrated in  FIG. 6C  can be avoided. 
     At step  710 , the recalculated fillet curve is displayed. 
     Conclusion 
     This concludes the description of the preferred embodiment of the invention. The following describes some alternative embodiments for accomplishing the present invention. For example, any type of computer, such as a mainframe, minicomputer, or personal computer, or computer configuration, such as a timesharing mainframe, local area network, or standalone personal computer, could be used with the present invention. 
     The foregoing description of one or more embodiments of the invention has been presented for the purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed. Many modifications and variations are possible in light of the above teaching. It is intended that the scope of the invention be limited not by this detailed description, but rather by the claims appended hereto.