Controlled face dragging in solid models

One or more embodiments of the invention provide a method, apparatus, and article of manufacture for modifying a three-dimensional model. A three-dimensional model is displayed in a computer implemented solid modeling system. A first face of the three-dimensional model is then selected. A first constraint that controls a behavior of a repositioning operation for the first face is specified. Once the face and constraint have been selected/specified, the three-dimensional model is modified by repositioning the selected first face, wherein the repositioning operation is constrained in accordance with the specified first constraint.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates generally to three-dimensional modeling systems based on boundary representations, and in particular, to a method, apparatus, and article of manufacture for the controlled dragging of faces in boundary representations and solid bodies.

2. Description of the Related Art

The use of solid modeling application programs is well known in the art. In a 3D solid modeling system, a 3D model (also referred to as an object model) may be constructed, displayed, modified, etc. A solid model may be presented to the user by displaying the boundary of the model (referred to as a boundary representation or B-rep). Further, the boundary representation has multiple individual faces. To manipulate/modify the model, a face of the boundary representation may be dragged/repositioned using a cursor control device such as a mouse. However, when a single face is dragged, adjacent faces (i.e., faces that share common edges and vertices with the face being dragged) may become invalid. For example, an adjacent face that was originally planar may become non-planar when vertices shared between the dragged face and adjacent face are repositioned (such that the vertices of the adjacent face do not lie on the same plane any more).

Additionally, in prior art solid modeling application programs, the user cannot control how adjacent faces should be adjusted during a face dragging operation. For example, without input from the user, a solid modeling application program may adjust adjacent faces in a predetermined manner during a face dragging operation. Thus, the user is not provided with any option(s) and does not have the capability to control or elect between multiple different types of face dragging operations.

Accordingly, what is needed is a method, system, and article of manufacture for repositioning a face of a boundary representation while providing the user with options to control the repositioning operation.

SUMMARY OF THE INVENTION

One or more embodiments of the invention provide a method, apparatus, and article of manufacture for repositioning individual faces in a topological structure of boundary representation solid bodies, such as during the dragging of faces in solid bodies. The boundary representation solid bodies are facetted (i.e., all of the faces are planar and all face vertices lie on the same plane).

Two constraints control the behavior of the face repositioning operation. These two constraints are selectable by the user, who thus controls the outcome of the face repositioning operation.

The first constraint constrains the planes of the faces adjacent to the face being repositioned not to change (i.e., the slopes of adjacent faces remain fixed). The adjacent faces' edges and vertices may change, however, such as the faces may be stretched or shrunk.

The second constraint constrains the geometry of the face being repositioned to be fixed (i.e., the face is repositioned as rigid and only its location changes).

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

Overview

A method, apparatus, and article of manufacture provide for the ability to modify/reposition a face of a three-dimensional model in a solid modeling system based on the boundary representation of the solid models. To control the face repositioning operation, the user is provided with two user selectable constraints. The first constraint allows the user to determine whether to constrain the planes of faces adjacent to the face being repositioned to be fixed. The second constraint allows the user to determine whether to constrain the geometry of the face being repositioned to be fixed.

Hardware and Software Environment

FIG. 1is 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 computer100, which generally includes, inter alia, a display device102, data storage devices104, cursor control devices106, 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 computer100.

One or more embodiments of the invention are implemented by a computer-implemented solid modeling program108, wherein the solid modeling program108is represented by a window displayed on the display device102. Generally, the solid modeling program108comprises 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 devices104connected directly or indirectly to the computer100, one or more remote devices coupled to the computer100via a data communications device, etc.

Those skilled in the art will recognize that the exemplary environment illustrated inFIG. 1is 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 Solid Modeling Program

FIG. 2is a block diagram that illustrates the components of the solid modeling program108in accordance with one or more embodiments of the invention. There are three main components to the solid modeling program108, including: a Graphical User Interface (GUI)200, an Image Engine (IME)202, and a DataBase (DB)204for storing objects in Drawing (DWG) files206.

The Graphical User Interface200displays information to the operator and provides the functionality for the operator's interaction with the solid modeling program108.

The Image Engine202processes the DWG files206and delivers the resulting graphics to the monitor102for display. In one or more embodiments, the Image Engine202provides a complete application programming interface (API) that allows other computer programs to interface to the solid modeling program108as needed.

The Database204is comprised of two separate types of databases: (1) a 3D database208known as the “3D world space” that stores 3D information; and (2) one or more 2D databases210known as the “2D view ports” that stores 2D information derived from the 3D information.

Object List

FIG. 3is a block diagram that illustrates the structure of an object list300maintained by the 3D databases208in accordance with one or more embodiments of the invention. The object list300is usually comprised of a doubly linked list having a list head302and one or more objects304interconnected by edges306, although other structures may be used as well. There may be any number of different object lists300maintained by the 3D databases208. Moreover, an object304may be a member of multiple object lists300in the 3D databases208.

Operation of the Software Embodiment

One or more embodiments of the invention provides a new method within solid modeling program108for repositioning individual faces in a topological structure of boundary representation solid bodies, such as during the dragging (e.g., grip-point editing) of faces in solid bodies. Two constraints are introduced to control the behavior of the face move/repositioning operation. The two constraints are selectable by the user (e.g., through a selectable option), who thus controls the outcome of the face repositioning operation.

The first constraint constrains the planes of faces adjacent to the face being repositioned not to change. Thus, while the edges and vertices of adjacent faces may change, the slopes of adjacent faces remain fixed. In other words, the adjacent faces may be stretched or shrunk on the same plane.

The second constraint constrains the geometry of the face being repositioned to be fixed. Thus, while the location of the face may change, the face (i.e., its size, rotation, etc) is repositioned as rigid.

FIGS. 4A-4Fillustrate examples of the behavior of the face repositioning operation for different configurations of the constraints.FIG. 4Aillustrates an oral pyramid400whose top face402is to be moved upwards.FIG. 4Billustrates the direction the vertices of face402will be moved when the first constraint is preserved during a repositioning operation.FIG. 4Cillustrates the result of the operation after dragging the face402while preserving the first constraint. As illustrated, the planes of the adjacent faces404are not changed. Instead, the geometry of face402(i.e., the face being moved) is changed.

FIG. 4Dillustrates the direction the vertices of face402will be moved when the second constraint is preserved during a repositioning operation.FIG. 4Eillustrates the result of the operation after dragging the face402while preserving the second constraint. As illustrated, the geometry of face402(i.e., the face being moved) is not changed. Instead, the planes of the adjacent faces404are changed.

FIG. 4Fillustrates the result of the operation after dragging the face402while preserving both the first constraint and the second constraint. As illustrated, the planes of the adjacent faces404are not changed. Additionally, geometry of face402(i.e., the face being moved) is not changed. Instead, the resulting model400appears to be a composite model having a bottom component406similar to the original pyramid400and an upper component408comprised of the cubic structure formed by the repositioned face402.

Logic of the Graphics Program

FIG. 5is a flowchart that illustrates the general logic of a message or event-driven solid modeling program108performing the steps in accordance with one or more embodiments of the invention. In such a solid modeling program108, operations are performed when transitions are made, based upon the receipt of messages or events, from present or current states to new states. Those skilled in the art will recognize that this logic is provided for illustrate purposes only and that different logic may be used to accomplish the same results.

Generally, the flowchart begins by waiting at block500for an event (e.g., a mouse button click). It should be appreciated that, during this time, other operating system tasks, e.g., file, memory, and video tasks, etc., may also be carried out. When an event occurs, control passes to block502to identify the event. Based upon the event, as well as the current state of the graphics solid modeling program108determined in block504, a new state is determined in block506. In block508, the logic transitions to the new state and performs any actions required for the transition. In block510, the current state is set to the previously determined new state, and control returns to block500to wait for more input events.

The specific operations that ate performed by block508when transitioning between states will vary depending upon the current state and the event. The various operations required to implement and maintain the preferred embodiment of the present invention represent particular events handled by the logic. However, it should be appreciated that these operations represent merely a subset of all of the events handled by the computer100.

FIG. 6is a flowchart illustrating a controlled face dragging operation in accordance with one or more embodiments of the invention. At step600, the user selects a first face of a boundary representation solid body (i.e., a three-dimensional model) that the user desires to drag. The selection (and future repositioning operation) may be performed/controlled graphically on the display device102by picking a face402using a graphical user interface of the modeling system/solid modeling program108. However, the face402selection may be performed by any other means.

At step602, the user specifies whether the one or more of the constraints described above (referred to as first constraint and second constraint) are required to be satisfied. Such specifying may be performed by the user specifying (or selection of an option for) a constraint that controls the behavior for the repositioning operation. For example, the user may press the <SHIFT> or <CTRL> keys on the keyboard. If no key is pressed, the first constraint may not be required to be satisfied and the second constraint may be required to be satisfied. If the <SHIFT> key is pressed, it may indicate the first constraint is required to be satisfied and the second constraint is not required to be satisfied. If the <CTRL> key is pressed, it may indicate that both constraints are required to be satisfied. Additionally, it should be noted that the selection of a constraint may be represented through the use of a Boolean flag.

FIG. 7illustrates the input to and output from solid modeling program108during a face repositioning operation in accordance with one or more embodiments of the invention. Boundary representation400, face402(selected at step600), drag vector702(specified at step604) and constraint flags704(selected at step602) are used as input into solid modeling program108. The repositioning operation is performed at steps604-616, and the modified boundary representation706, and a success indicator708(e.g., a flag indicating the success or failure of the operation) is returned as output.

Referring back toFIG. 6, steps604-618provide for modifying the three-dimensional model by repositioning the face402selected at step600, wherein the repositioning operation is constrained in accordance with the specified constraint(s). At step604, the user specifies the dragging vector (i.e., the displacement of the face402relative to its original position). The dragging vector is perpendicular to the face402plane. The specification of the dragging vector is often performed graphically using the graphical user interface of the modeling system/solid modeling program108, but it may also be performed by entering a numerical value or by any other means.

At step606, the original solid body (e.g., body400) is cloned. At step608, the controlled face dragging operation is performed on the cloned solid body obtained in step606, on the face402selected at step600, using the dragging vector specified at step604, in accordance with the constraint(s) specified at step602. Accordingly, the cloned solid body is modified by the operation.

At step610, a determination is made regarding whether the dragging operation on the clone was successful. If the drag operation returns a success status, the dragging is accepted and the modified cloned solid body is displayed on display device102at step612. Otherwise, the dragging is rejected and the last modified cloned solid body for which the dragging succeeded is displayed on display device102at step614.

At step616, a determination is made regarding whether the user keeps dragging the same face402. If the same face402continues to be dragged, processing continues with step602. Otherwise, the original solid body is replaced with the last modified cloned body for which the dragging operation succeeded at step618and the user interaction is complete.

Steps606-618are described in detail with respect toFIGS. 4A-F,6,7,8,9,10, and11.FIG. 9is a flow chart illustrating the details of steps606-618. A temporary face802(as illustrated inFIG. 8) that is a clone of original face402is created at step900with vertices repositioned relative to the vertices of original face402. How the vertices are repositioned depends on the value of the constraint options/flags704.

At step902a determination is made regarding whether the value of the second constraint flag C2is true (i.e., whether the user has elected to preserve the geometry of the face being moved). If the second constraint is to be preserved (i.e., the value of the flag C2is true), the vertices are repositioned along the drag vector702at step904as illustrated inFIGS. 4D and 4E. If the value of the second constraint flag C2is false, each vertex is repositioned along a vector that is the cross product of the normal vectors of the side faces404incident at the vertex at step906as illustrated inFIGS. 4B and 4C.

At step908, a determination is made regarding whether the value of the first constraint flag C1is true (i.e., the user has elected to preserve the planes of the adjacent faces404). If the first constraint is to be preserved (i.e., the value of the flag C1is true), a solid body is created that is defined by the two faces—the original face402and the cloned face802(with the repositioned vertices), and by adding side faces404between the two faces at step910as illustrated in FIG.8. At step912, a Boolean operation is performed between the original solid body and the cloned solid body (created at step910). If the drag vector702is in the direction of the face402normal vector, a Boolean operation union is performed. If the drag vector702is in the opposite direction, a Boolean operation subtraction is performed. The process is then complete and returns an indicator that the operation completed successfully.

If the value of the first constraint flag C1is false (as determined at step908), the coordinates of the vertices of face402are replaced with the coordinates of the repositioned vertices of face802at step914. The planes and vertices of the side faces404(faces sharing an edge with face402) are attempted to be adjusted so that the side faces404remain planar (i.e., all vertices of each side face404still lie on the same plane) at step916.FIGS. 10A and 10Billustrates an example of the result of the adjustment of the vertices and planes of side faces404in a more complex solid body where the side faces contain holes, cuts, and ribs.

FIG. 11shows how the new plane of each side face is determined. The plane is defined by vertices V1, V2of an edge of the repositioned face402and a third vertex V3that is most distant from the edge. Specifically, for each side face404that shares an edge (bounded by vertices V1and V2) with face402repositioned at step914, a third vertex V3that is most distant from the edge is found on the side face404. A new plane of the side face404is then calculated from the three vertices V1, V2, and V3at step918. The vertices of each side face404that do not already lie on the new plane are adjusted to lie on the new plane at step920. To perform the adjustment at step920, the planes of all faces incident at the vertex (i.e., the planes of the repositioned face402and side faces404) are collected. For the side faces404, the newly calculated face planes, calculated at step918, are used instead of the original planes.

To adjust the vertices at step920, the number of planes are examined. If there are at least three non-coplanar planes, the intersection of any three planes is calculated and the resulting intersection point becomes the new coordinates of the adjusted vertex. If there are two non-coplanar planes, the coordinates of the original vertex are projected perpendicularly on a line that is the intersection between the two planes. The projected point becomes the new coordinates of the adjusted vertex. If there is a single plane (i.e., the plane of the repositioned face402), the coordinates of the original vertex are projected perpendicularly to the plane. The projected point becomes the new coordinates of the adjusted vertex.

After the planes and vertices of all side faces404have been adjusted at steps918and920, the validity of modified solid body706is checked at step922. If the solid body706is valid, a flag708indicating a success may be returned. Otherwise, a flag708indicating a failure may be returned.

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.