Mesh boundary smoothing

One embodiment of the present invention sets forth a technique for smoothing boundaries associated with meshes of primitives. The technique involves receiving a mesh of primitives that has a mesh boundary and an initial surface, identifying a first vertex associated with the mesh boundary and having a first location, and identifying a second vertex having a second location and a third vertex having a third location. Both the second vertex and third vertex are proximate to the first vertex. The technique further involves determining a fourth location based on the second location and the third location, projecting the fourth location onto the initial surface to determine a fifth location, and moving the first vertex to the fifth location.

BACKGROUND OF THE INVENTION

Field of the Invention

Embodiments of the present invention generally relate to computer-aided design (CAD) and, more specifically, to techniques for mesh boundary smoothing.

Description of the Related Art

A wide variety of software applications are currently available to end-users, including computer-aided design (CAD) applications, computer graphics applications, and three-dimensional (3D) modeling applications, among others. Many of these software applications allow an end-user to create and modify 2D and/or 3D designs. For example, an end-user may interact with a 3D modeling application to add geometry to a design, remove geometry from a design, extrude portions of the design, or join two or more designs. Such operations typically are performed by modifying a mesh of primitives (e.g., triangles) associated with the design.

In conventional software applications, modifying a triangle mesh associated with a design (e.g., by adding, removing, extruding, or merging geometry) can introduce distortions and irregularities to the mesh. For example, extruding a region of the mesh can produce an extrusion boundary having rough, irregular edges that reflect the boundary triangles of the mesh region selected for extrusion. Moreover, manually smoothing a boundary to perform an extrusion can be tedious and time-consuming for the end-user. Further, applying conventional smoothing algorithms to an extruded boundary often produces unsatisfactory results (e.g., rounded, poorly-defined extrusions).

As the foregoing illustrates, there is a need in the art for a more effective way to enable application end-users to apply smoothing operations to the boundaries of primitive meshes.

SUMMARY OF THE INVENTION

One embodiment of the present invention sets forth a method for smoothing boundaries associated with meshes of primitives. The method involves receiving a mesh of primitives that has a mesh boundary and an initial surface, identifying a first vertex associated with the mesh boundary and having a first location, and identifying a second vertex having a second location and a third vertex having a third location. Both the second vertex and third vertex are proximate to the first vertex. The method further involves determining a fourth location based on the second location and the third location, projecting the fourth location onto the initial surface to determine a fifth location, and moving the first vertex to the fifth location.

Further embodiments provide a non-transitory computer-readable medium and a computing device to carry out at least the method steps set forth above.

Advantageously, the disclosed technique allows a user to perform smoothing of mesh boundaries, for example, to produce mesh extrusions having smooth edges. Boundary smoothing may be performed by incrementally shifting boundary vertices and projecting the smoothed locations of the boundary vertices onto the initial mesh surface to preserve the mesh shape. The disclosed technique, among other things, enables users to more efficiently smooth selected mesh boundaries and perform high-quality mesh extrusions without significantly distorting surrounding regions of the mesh.

DETAILED DESCRIPTION

FIG. 1illustrates a computing device100configured to implement one or more aspects of the present invention. As shown, computing device100includes a memory bridge105that connects a central processing unit (CPU)102, an input/output (L/O) bridge107, a system memory104, and a display processor112.

Computing device100may be a computer workstation, a personal computer, video game console, personal digital assistant, mobile phone, mobile device or any other device suitable for practicing one or more embodiments of the present invention. As shown, the central processing unit (CPU)102and the system memory104communicate via a bus path that may include a memory bridge105. CPU102includes one or more processing cores, and, in operation, CPU102is the master processor of computing device100, controlling and coordinating operations of other system components. System memory104stores software applications and data for use by CPU102. CPU102runs software applications and optionally an operating system. Memory bridge105, which may be, e.g., a Northbridge chip, is connected via a bus or other communication path (e.g., a HyperTransport link) to an I/O (input/output) bridge107. I/O bridge107, which may be, e.g., a Southbridge chip, receives user input from one or more user input devices108(e.g., keyboard, mouse, joystick, digitizer tablets, touch pads, touch screens, still or video cameras, motion sensors, and/or microphones) and forwards the input to CPU102via memory bridge105.

One or more display processors, such as display processor112, are coupled to memory bridge105via a bus or other communication path (e.g., a PCI Express, Accelerated Graphics Port, or HyperTransport link). In one embodiment, display processor112is a graphics subsystem that includes at least one graphics processing unit (GPU) and graphics memory. Graphics memory includes a display memory (e.g., a frame buffer) used for storing pixel data for each pixel of an output image. Graphics memory can be integrated in the same device as the GPU, connected as a separate device with the GPU, and/or implemented within system memory104.

Display processor112periodically delivers pixels to a display device110(e.g., conventional cathode ray tube, liquid crystal display, light-emitting diode, plasma, organic light-emitting diode, or surface-conduction electron-emitter based display). Additionally, display processor112may output pixels to film recorders adapted to reproduce computer generated images on photographic film. Display processor112can provide display device110with an analog or digital signal.

A system disk114is also connected to I/O bridge107and may be configured to store content and applications and data for use by CPU102and display processor112. System disk114provides non-volatile storage for applications and data and may include fixed or removable hard disk drives, flash memory devices, and CD-ROM (compact disc read-only-memory), DVD-ROM (digital versatile disc-ROM), Blu-ray, or other magnetic, optical, or solid state storage devices.

A switch116provides connections between I/O bridge107and other components such as a network adapter118and various add-in cards120and121. Network adapter118allows computing device100to communicate with other systems via an electronic communications network and may include wired or wireless communication over local area networks and wide area networks, such as the Internet.

Other components (not shown), including USB or other port connections, film recording devices, and the like, may also be connected to I/O bridge107. For example, an audio processor may be used to generate analog or digital audio output from instructions and/or data provided by CPU102, system memory104, or system disk114. Communication paths interconnecting the various components inFIG. 1may be implemented using any suitable protocols, such as PCI (Peripheral Component Interconnect), PCI Express (PCI-E), AGP (Accelerated Graphics Port), HyperTransport, or any other bus or point-to-point communication protocol(s), and connections between different devices may use different protocols, as is known in the art.

In one embodiment, display processor112incorporates circuitry optimized for graphics and video processing, including, for example, video output circuitry, and constitutes a graphics processing unit (GPU). In another embodiment, display processor112incorporates circuitry optimized for general purpose processing. In yet another embodiment, display processor112may be integrated with one or more other system elements, such as the memory bridge105, CPU102, and I/O bridge107to form a system on chip (SoC). In still further embodiments, display processor112is omitted and software executed by CPU102performs the functions of display processor112.

Pixel data can be provided to display processor112directly from CPU102. In some embodiments of the present invention, instructions and/or data representing a scene are provided to a render farm or a set of server computers, each similar to computing device100, via network adapter118or system disk114. The render farm generates one or more rendered images of the scene using the provided instructions and/or data. These rendered images may be stored on computer-readable media in a digital format and optionally returned to computing device100for display.

Alternatively, CPU102provides display processor112with data and/or instructions defining the desired output images, from which display processor112generates the pixel data of one or more output images. The data and/or instructions defining the desired output images can be stored in system memory104or graphics memory within display processor112. In an embodiment, display processor112includes 3D rendering capabilities for generating pixel data for output images from instructions and data defining the geometry, lighting shading, texturing, motion, and/or camera parameters for a scene. Display processor112can further include one or more programmable execution units capable of executing shader programs, tone mapping programs, and the like.

CPU102, render farm, and/or display processor112can employ any surface or volume rendering technique known in the art to create one or more rendered images from the provided data and instructions, including rasterization, scanline rendering REYES or micropolygon rendering, ray casting, ray tracing, image-based rendering techniques, and/or combinations of these and any other rendering or image processing techniques known in the art.

In one embodiment, application140, mesh refinement engine150, a boundary smoothing engine155, and 3D mesh160are stored in system memory104. AlthoughFIG. 1shows the mesh refinement engine150and boundary smoothing engine155as separate software modules, the mesh refinement engine150and boundary smoothing engine155may be part of the same software executable. Additionally, the mesh refinement engine150and boundary smoothing engine155may be integrated into the application140or offered as software add-ons or plug-ins for the application140. Application140may be a CAD (computer aided design) application program configured to generate and display graphics data included in the 3D mesh160on display device110. For example, the 3D mesh160could define one or more graphics objects that represent a 3D model designed using the CAD system or a character for an animation application program.

The mesh refinement engine150is configured to modify a mesh (e.g., 3D mesh160) by performing one or more refinement operations on the mesh. The refinement operations may be applied to add, remove, replace, shift, etc. vertices and/or edges included in the mesh. For example, an edge operation may be performed on the mesh to add an edge (e.g., a triangle edge) to the mesh, remove an edge from the mesh, and/or shift the position of an edge in the mesh. Additionally, a vertex operation may be performed to add a vertex to the mesh, remove a vertex from the mesh, and/or shift the position of a vertex in the mesh. Other types of refinement operations, such as smoothing operations, also may be performed to improve the visual appearance of a mesh.

The mesh refinement engine150enables a user to iteratively refine a mesh, for example, by repairing mesh distortions produced when adding geometry to a mesh, removing geometry from a mesh, modifying the geometry of a mesh, and the like. For example, moving vertices to modify the shape of a mesh boundary may distort the mesh, producing mesh triangles having irregular sizes and angles near the modified boundary. Such irregularities may produce computational issues and/or visual artifacts during subsequent processing of the mesh. However, by performing mesh refinement operations before, while, and/or after modifying a mesh boundary, mesh distortions may be reduced or eliminated.

The boundary smoothing engine155may be configured to prepare a mesh for an extrusion operation by moving vertices associated with a mesh boundary to create a smooth, aesthetic boundary. In addition, the boundary smoothing engine155may be configured to project the smoothed vertex positions onto the initial surface of the mesh (e.g., a surface associated with a position of the mesh prior to performing boundary smoothing) to preserve an approximate shape of the original mesh. Once the mesh boundary has been sufficiently smoothed, an extrusion operation may be performed on the mesh to produce a mesh extrusion having smooth edges. Further, the mesh refinement engine150may perform mesh refinement passes on vertices proximate to the mesh boundary in order to repair mesh distortions produced by the boundary smoothing operation. The details of various mesh refinement operations are described below with respect toFIGS. 2-5.

FIG. 2illustrates edge operations200for refining a mesh, according to one embodiment of the present invention. Edge operations200may be performed on a mesh to add an edge, remove an edge, and/or shift the position of an edge. Edge operations200may be applied to a mesh on a per-edge basis, or multiple edges may be processed in parallel.

As shown, the edge operations200include an edge flip operation202, an edge split operation204, and an edge collapse operation206. An edge flip operation202is performed to rotate an edge210within the quadrilateral225formed by the two triangles220connected to the edge210. An edge split operation204is performed to replace the two triangles220connected to the edge210with four triangles220by inserting a vertex215into the edge210and connecting the vertex215to the two vertices216opposite the edge210. An edge collapse operation206removes the triangles220connected to the edge210and shifts the vertices217connected to the edge210to a new vertex position218(e.g., a midpoint of the initial edge210). Conditions under which these edge operations200may be performed are described in further detail below with respect toFIG. 5.

FIG. 3illustrates a vertex removal operation300for refining a mesh, according to one embodiment of the present invention. The vertex removal operation300may be applied to a mesh on a per-vertex basis, or multiple vertices may be processed in parallel. The vertex removal operation300may be performed to remove a vertex315connected to only three neighboring vertices316(i.e., a vertex315having a valence of three), also known as a tip vertex. Tip vertices315are necessarily surrounded by triangles220having large opening angles and, thus, may cause computational issues during subsequent processing of a mesh. Additionally, tip vertices315may collapse into the plane of their surrounding vertices316(e.g., when applying smoothing algorithms) and, as a result, may add little or no detail to the mesh. Consequently, to avoid such issues, tip vertices315may be removed via a vertex removal operation300. After removal of a tip vertex315, a new triangle221may be added to the mesh. Conditions under which a vertex removal operation300may be performed are described in further detail below with respect toFIG. 5.

FIG. 4illustrates a smoothing operation400for refining a mesh, according to one embodiment of the present invention. The smoothing operation400may be performed to more evenly distribute vertices in the mesh. In addition to improving the overall visual appearance of the mesh, the smoothing operation may be performed to reduce the number of small, irregularly-sized triangles that occur along mesh boundaries. Such triangles may be generated when edge operations are performed along preserved boundaries.

As shown, the smoothing operation400may shift a vertex415from an initial position to a smoothed vertex position416. The location of the smoothed vertex position416may be based on a smoothing algorithm (e.g., a Laplacian smoothing algorithm) and a smoothing strength factor. Additional details regarding the smoothing operation400are described below with respect toFIG. 5.

FIG. 5is a flow diagram of method steps for refining a mesh of primitives, according to one embodiment of the present invention. Although the method steps are described in conjunction with the system ofFIG. 1, persons skilled in the art will understand that any system configured to perform the method steps, in any order, falls within the scope of the present invention. Further, although mesh refinement operations are described as being performed in a particular order, the mesh refinement operations may be reordered and/or various mesh refinement operations may be repeated or omitted.

As shown, a method500begins at step510, where the mesh refinement engine150determines whether to perform an edge flip pass on one or more edges210included in a mesh. During the edge flip pass, the mesh refinement engine150processes the edge(s)210to determine whether an edge flip operation202should be performed on the edge(s)210. If the mesh refinement engine150determines that an edge flip pass should be performed, then subprocess A is executed at step515.

Upon executing subprocess A at step515, the mesh refinement engine150identifies a triangle edge210included in a mesh. The mesh refinement engine150then optionally determines whether the edge210is on a preserved boundary of the mesh. A preserved boundary may include a limit (e.g., an outermost perimeter) of the mesh itself and/or a boundary selected by a user or generated by the mesh refinement engine150. For example, the user may select a region of interest (ROI) in which mesh refinement operations are to be performed. Upon selecting the ROI, the user may further determine whether mesh refinement operations performed within the ROI are permitted to affect regions of the mesh that are outside of the ROI (e.g., in proximity to the ROI). If the mesh refinement operations are permitted to affect regions of the mesh outside of the ROI, then triangles adjacent or proximate to the ROI may be modified when performing mesh refinement operations. If the mesh refinement operations are not permitted to affect regions of the mesh outside of the ROI (i.e., the ROI boundary is a preserved boundary), then the position, shape, etc. of the ROI boundary may be retained, and triangles outside of the ROI are not modified when performing mesh refinement operations. Additionally, the user may pin one or more locations along the ROI boundary to prevent the mesh refinement engine150from modifying the position and shape of vertices and triangles at the pinned locations while allowing the mesh refinement engine150to modify other (e.g., unpinned) locations along the ROI boundary.

If the edge210is located on a preserved boundary (e.g., an ROI boundary, perimeter of the mesh, etc.), then the mesh refinement engine150determines not to flip the edge210. As such, the preserved boundary is not modified. If the edge210is not located on a preserved boundary, then the mesh refinement engine150determines a potential flipped edge210. Next, the mesh refinement engine150computes the length of the flipped edge210and compares this length to the product of a flip threshold Kflipand the length of the initial edge210. The flip threshold Kflipis intended to reduce the occurrence of edge flips that do not significantly improve mesh quality. For example, by setting the flip threshold Kflipto a value of 0.9, an edge210is flipped only if the flipped edge210is appreciably shorter than the initial edge210. Other values for the flip threshold Kflip(e.g., 0.95, 0.8, 0.75, etc.) may be selected as well.

If the length of the flipped edge210is greater than the product of the flip threshold Kflipand the length of the initial edge210, then the mesh refinement engine150determines not to flip the edge210. If the length of the flipped edge210is not greater than the product of the flip threshold Kflipand the length of the initial edge210, then the mesh refinement engine150next determines a distance between the midpoint of the initial edge210and the midpoint of the flipped edge210. The distance is then compared to the product of the midpoint threshold Kmidpointand the length of the initial edge210. The midpoint threshold Kmidpointis intended to reduce the occurrence of edge flips that significantly change the shape of the mesh. For example, by setting the midpoint threshold Kmidpointto a value of 0.2, an edge210is flipped only if the flipped edge210is in a plane that is near the plane in which the initial edge210resides. Other values for the midpoint threshold Kmidpoint(e.g., 0.1, 0.3, etc.) may be selected as well.

If the distance is greater than the product of the midpoint threshold Kmidpointand the length of the initial edge210, then the mesh refinement engine150determines not to flip the edge210. If the distance is not greater than the product of the midpoint threshold Kmidpointand the length of the initial edge210, then the mesh refinement engine150next determines whether flipping the edge210would create a non-manifold edge. A non-manifold edge may be defined as an edge that is shared by more than two faces (e.g., an edge shared by more than two triangles). If flipping the edge210would create a non-manifold edge, then the mesh refinement engine150determines not to flip the edge210. If flipping the edge210would not create a non-manifold edge, then the mesh refinement engine150flips the edge210. Finally, the mesh refinement engine150determines whether to process another edge210included in the mesh. If another edge210is to be processed by the mesh refinement engine150, then the mesh refinement engine150identifies another edge210included in the mesh and repeats the process described above. If no additional edges210are to be processed, then subprocess A ends, and the method proceeds to step520.

At step520, the mesh refinement engine150determines whether to perform an edge split pass on one or more edges210included in a mesh (e.g., to determine whether an edge split operation204should be performed on the edge(s)210). If the mesh refinement engine150determines that an edge split pass should be performed, then subprocess B is executed at step525.

Upon executing subprocess B at step525, the mesh refinement engine150identifies a triangle edge210included in a mesh. The mesh refinement engine150then optionally determines whether the edge210is on a preserved boundary of the mesh. If the edge210is located on a preserved boundary (e.g., an ROI boundary, perimeter of the mesh, etc.), then the mesh refinement engine150determines not to split the edge210. If the edge210is not located on a preserved boundary, then the mesh refinement engine150compares a weighted length of the edge210to a split threshold Ksplit. The split threshold Ksplitmay be defined as the target maximum edge length. That is, by performing this comparison, at the end of an edge split pass, all processed edges210may be shorter than the split threshold Ksplitlength.

The weighting applied to the length of the edge210may be based on the per-vertex refinement weights assigned to the two vertices217to which the edge210is connected. The per-vertex refinement weights may be assigned to vertices by the mesh refinement engine150, or the per-vertex refinement weights may be based on user selection (e.g., based on a weight refinement mask). In general, refinement weights assigned to vertices, edges, etc. may control the conditions under which a refinement operation is performed. For example, assigning a higher weighting to a vertex may increase the likelihood that a refinement operation will be performed on the vertex (e.g., a vertex collapse operation300) or on an edge associated with the vertex (e.g., an edge split operation204). Conversely, assigning a lower weighting to a vertex may decrease the likelihood that a refinement operation will be performed on the vertex or on an edge associated with the vertex. Further, assigning a zero weighting to a vertex may indicate that a refinement operation will not be performed on the vertex or on an edge associated with the vertex.

If the weighted length of the edge210is not greater than the split threshold Ksplit, then the mesh refinement engine150determines not to split the edge210. If the weighted length of the edge210is greater than the split threshold Ksplit, then the mesh refinement engine150adds the edge210to a split edge list. Next, the mesh refinement engine150determines whether to process another edge210included in the mesh. If another edge210is to be processed by the mesh refinement engine150, then another edge210included in the mesh is identified, and the process described above is repeated. If no additional edges210are to be processed, then the edge(s)210included in the split edge list are optionally sorted by length. Finally, the edge(s)210included in the split edge list are split. If the edges210were sorted, then the edges210included in the split edge list may be split in order of longest edge length to shortest edge length. Once all edges on the split edge list have been split, subprocess B ends, and the method proceeds to step530.

At step530, the mesh refinement engine150determines whether to perform an edge collapse pass on one or more edges210included in a mesh (e.g., to determine whether an edge collapse operation206should be performed on the edge(s)210). If the mesh refinement engine150determines that an edge collapse pass should be performed, then subprocess C is executed at step535.

Upon executing subprocess C at step535, the mesh refinement engine150identifies a triangle edge210included in a mesh. The mesh refinement engine150then optionally determines whether the edge210is on a preserved boundary of the mesh. If the edge210is located on a preserved boundary (e.g., an ROI boundary, perimeter of the mesh, etc.), then the mesh refinement engine150determines not to collapse the edge210. If the edge210is not located on a preserved boundary, then the mesh refinement engine150next determines whether at least one of two inequalities are satisfied. With reference to the first inequality, the mesh refinement engine150determines whether a weighted length (e.g., based on per-vertex refinement weights described above) of the edge210is greater than a collapse threshold Kcollapse.

The collapse threshold Kcollapseis intended to collapse edges210that are shorter than the value assigned to this threshold. With reference to the second inequality, the mesh refinement engine150determines whether a minimum opposing angle of one of the two triangles connected to the edge210is less than a target angle Tcollapse. The target angle Tcollapseis intended to collapse triangles220having an angle that is less than the value assigned to this target. Thus, after an edge collapse pass, all angles included in the processed triangles220may be greater than the target angle Tcollapse. Furthermore, because this criterion is scale-independent (e.g., the target angle Tcollapsedoes not depend on the relative size of triangles in the mesh), mesh quality may be significantly improved even if Kcollapseis assigned an inappropriate value.

If one or both of the first inequality and second inequality are satisfied, the mesh refinement engine150then determines whether collapsing the edge210would create a non-manifold edge. If collapsing the edge210would create a non-manifold edge, then the mesh refinement engine150determines not to collapse the edge210. If collapsing the edge210would not create a non-manifold edge, then the mesh refinement engine150collapses the edge210. Finally, the mesh refinement engine150determines whether to process another edge210included in the mesh. If another edge210is to be processed by the mesh refinement engine150, then another edge210included in the mesh is identified, and the process described above is repeated. If no additional edges210are to be processed, then subprocess C ends, and the method proceeds to step540.

At step540, the mesh refinement engine150determines whether to perform a vertex collapse pass on one or more vertices315included in a mesh (e.g., to determine whether a vertex collapse operation300should be performed on the vertices315). If the mesh refinement engine150determines that a vertex collapse pass should be performed, then subprocess D is executed at step545.

Upon executing subprocess D at step545, the mesh refinement engine150identifies a triangle vertex315included in a mesh. The mesh refinement engine150then optionally determines whether the vertex315is on a preserved boundary of the mesh. If the vertex315is located on a preserved boundary (e.g., an ROI boundary, perimeter of the mesh, etc.), then the mesh refinement engine150determines not to collapse the vertex315. If the vertex315is not located on a preserved boundary, then the mesh refinement engine150determines whether the vertex315has a valence equal to three (i.e., the vertex315is connected to only three neighboring vertices316). If the vertex315does not have a valence equal to three, then the vertex315is not collapsed.

If the vertex315has a valence equal to three, then the mesh refinement engine150optionally determines whether all triangles connected to the vertex315are located within the ROI. If all triangles connected to the vertex315are not located within the ROI, then the vertex315is not collapsed. If all triangles connected to the vertex315are located within the ROI, then the mesh refinement engine150next determines whether a neighboring vertex316has a valence higher than three. If no neighboring vertex316has a valence higher than three, then the vertex315is not collapsed. If a neighboring vertex316has a valence higher than three, then the vertex315is collapsed and a new triangle221is added to the mesh. Finally, the mesh refinement engine150determines whether to process another vertex315included in the mesh. If another vertex315is to be processed by the mesh refinement engine150, then another vertex315included in the mesh is identified, and the process described above is repeated. If no additional vertices315are to be processed, then subprocess D ends, and the method proceeds to step550.

At step550, the mesh refinement engine150determines whether to perform a smoothing operation400on one or more vertices415included in a mesh. If the mesh refinement engine150determines that a smoothing operation400should be performed, then subprocess E is executed at step555.

Upon executing subprocess E at step555, the mesh refinement engine150identifies a triangle vertex415included in a mesh. The mesh refinement engine150then determines a smoothed vertex position416. The smoothed vertex position416may be determined using a smoothing algorithm, such as a uniform Laplacian smoothing algorithm. Next, a smoothing weight may be determined based on a strength factor and/or a weight function value. The strength factor may be a user-defined value (e.g., a brush tool parameter in application140). The weight function value may be based on a weight mask generated by the mesh refinement engine150or defined by the user.

Next, a weighted vertex position is determined based on the smoothed vertex position416and (optionally) based on the smoothing weight. For example, the weighted vertex position may be computed by interpolating the initial vertex position415and the smoothed vertex position416or by performing linear blending using the initial vertex position415(V), the smoothed vertex position416(V′), and the smoothing weight (WS). An exemplary formula for performing linear blending to determine a weighted vertex position (V″) is provided in Equation 1, below.
V″=(1−WS)×V+(WS)×V′(Eq. 1)

Finally, at step560, the mesh refinement engine150determines whether to perform additional mesh refinement passes. If the mesh refinement engine150determines that additional refinement passes should be performed, then the method returns to step510, as previously described herein. Alternatively, upon determining that additional refinement passes should be performed, the method may return to any of step510, step520, step530, step540, and/or step550, as also previously described herein. Furthermore, the flow diagram may be traversed such that one or more of the edge operations200are performed before and/or after the vertex collapse operation300and/or the smoothing operation400. If the mesh refinement engine150determines that additional refinement passes should not be performed, then the method ends.

In addition to repairing mesh distortions and irregularities, the mesh refinement engine150enables a user to perform other types of mesh operations. For example, when used in conjunction with the boundary smoothing engine155, the mesh refinement engine150enables a user to produce a mesh extrusion having smooth edges in a manner that requires relatively little pre-processing workload. Such techniques are described below in further detail.

Mesh Boundary Smoothing

FIGS. 6A and 6Billustrate an extrusion operation performed on a mesh605-1, according to one embodiment of the present invention. To perform an extrusion operation, a user may select a mesh boundary610(e.g.,610-1) associated with a 3D mesh605(e.g.,605-1) and extrude the mesh boundary610by an extrusion length. In general, the edges of a mesh extrusion630are based on the characteristics of the mesh boundary610selected for extrusion. Consequently, because the mesh boundary610-1selected by the user inFIG. 6Aincludes jagged triangle edges, the resulting mesh extrusion630has a rough, unattractive appearance, as shown inFIG. 6B.

FIG. 6Cillustrates region A of the mesh605-1illustrated inFIG. 6A, according to one embodiment of the present invention. As shown, the mesh boundary610-1includes a plurality of vertices620(e.g.,620-1,620-2,620-3) which form a jagged boundary. As described above, the edges of a mesh extrusion630are generally based on the characteristics of the mesh boundary610selected for extrusion. Consequently, in order to produce a mesh extrusion630having smooth edges, the boundary smoothing engine155and mesh refinement engine150may be used to perform one or more boundary smoothing and mesh refinement passes on the 3D mesh605-1. An exemplary method for smoothing mesh boundaries610is described below with respect toFIG. 7.

FIG. 7is a flow diagram of method steps for smoothing a mesh boundary610associated with a mesh605of primitives, according to one embodiment of the present invention. Although the method steps are described in conjunction with the system ofFIG. 1, persons skilled in the art will understand that any system configured to perform the method steps, in any order, falls within the scope of the present invention.

As shown, a method700begins at step710, where the boundary smoothing engine155receives a mesh605(e.g.,605-1) of primitives having an initial surface and a plurality of vertices620(e.g.,620-1,620-2,620-3) associated with a mesh boundary610(e.g.,610-1). The vertices620may define a mesh boundary610on which a mesh extrusion operation is to be performed. The initial surface of the mesh605may include the locations (e.g., locations defined in three-dimensional space) of one or more planes, edges, points, etc. associated with the mesh605prior to performing a boundary smoothing operation on the mesh605. That is, the initial surface may represent the general shape of the mesh605prior to modifying the mesh via a boundary smoothing operation.

At step720, the boundary smoothing engine155determines whether one or more pinned vertex constraints have been assigned to vertices620associated with the mesh boundary610. When a pinned vertex constraint is assigned to a vertex620, the location of the vertex620is not modified by the boundary smoothing engine155and/or mesh refinement engine150during boundary smoothing and/or mesh refinement passes. Pinned vertex constraints may be assigned to one or more vertices by a user (e.g., to manually preserve the shape of one or more regions of a mesh605) or pinned vertex constraints may be assigned by the boundary smoothing engine155. For example, the boundary smoothing engine155may detect a sharp corner associated with a mesh boundary610and assign a pinned vertex constraint to a vertex620associated with the sharp corner (e.g., in order to preserve a detailed shape of a mesh boundary610), and/or the boundary smoothing engine155may detect a preserved boundary in the mesh605(e.g., an outermost boundary or interior boundary of the mesh605) and assign a pinned vertex constraint to a vertex620associated with the preserved boundary. In another example, the boundary smoothing engine155may identify a known geometric shape (e.g., plane, cylinder, triangle, square, etc.) in the mesh605and assign pinned vertex constraints to one or more vertices620in order to preserve the approximate shape of the geometric shape.

Next, at step730, the boundary smoothing engine155selects a vertex620(e.g.,620-1) associated with the mesh boundary610(e.g.,610-1). The vertex620selected by the boundary smoothing engine155may be selected according to a vertex ordering (e.g., the order of vertices on a mesh boundary610), or the vertex620may be selected based on user input. For example, a user may operate a brush tool to select vertices620to which a boundary smoothing operation is to be applied, providing the user with the ability to control the amount of smoothing applied to different regions of the mesh boundary610.

At step740, the boundary smoothing engine155determines whether a pinned vertex constraint is assigned to the vertex620. If a pinned vertex constraint is assigned to the vertex620, then no smoothing is applied to the vertex620, and the boundary smoothing engine155determines whether to process another vertex620at step760. If a pinned vertex constraint is not assigned to the vertex620, then in step750the boundary smoothing engine155determines a smoothed location625of the vertex620. The smoothed location625(Vi″) may be determined by first calculating an average location (Vi′) based on the locations (Vi−1, Vi+1) of neighboring vertices620(e.g.,620-2and620-3). For example; an average location Vi′ may be determined by adding a vector associated with the location of the first neighboring vertex Vi−1to a vector associated with the location of the second neighboring vertex Vi+1and dividing the resulting vector by two. The boundary smoothing engine155may then apply a smoothing strength factor k to the average location Vi′ to determine a smoothed location Vi″. The smoothing strength factor k may be used to control the amount of smoothing applied to the mesh boundary610(e.g., the amount of smoothing per boundary smoothing pass). InFIG. 6C, a smoothing strength factor k of 0.9 has been applied; in other implementations, a smoothing strength factor of 0.5 may produce high-quality results. An exemplary formula for determining a smoothed location Vi″ using a smoothing strength factor k is provided in Equation 2, below, where k is in the range [0,1].
Vi″=Vi+k(Vi′−Vi), whereVi′=0.5*(Vi−1+Vi+1)  (Eq. 2)

At step760, the boundary smoothing engine155determines whether to process another vertex620. If another vertex is to be processed, then the boundary smoothing engine155returns to step730, where another vertex620is selected. If another vertex620is not processed, then in step770the boundary smoothing engine155optionally projects the smoothed location(s) onto the initial surface of the mesh605to determine one or more projected locations.

The vertex (or vertices) are then moved to the projected locations. As described above, projecting the vertices onto the initial surface preserves the approximate shape of the mesh605during the boundary smoothing operation. Alternatively, if the vertices are not projected onto the initial surface, then the vertex (or vertices) may be moved to the smoothed location(s).

Optionally, at step780, one or more mesh refinement passes (e.g., a smoothing operation400) may be performed on vertices proximate to the mesh boundary610, for example, in order to repair mesh distortions produced during the boundary smoothing operation. After performing the one or more mesh refinement passes, the vertices proximate to the mesh boundary610optionally may be projected onto the initial surface in order to approximate the initial shape of the mesh at step785.

At step790, the boundary smoothing engine155determines whether an additional boundary smoothing pass is to be performed. In one implementation, the boundary smoothing operation described above may be repeated on vertices620associated with a mesh boundary610N times (i.e., N boundary smoothing passes). In one implementation, N is equal to approximately 30.

Prior to performing an additional boundary smoothing pass, the user may be provided with an option to assign additional pinned vertex constraints to vertices620in the mesh605. Additionally, the user may be provided with an option to re-draw portions of the mesh boundary610. Additional boundary smoothing passes may then be performed based on the pinned constraints and/or re-drawn portions inputted by the user.

If an additional boundary smoothing pass is to be performed, then the boundary smoothing engine155selects another vertex620at step730. If no additional boundary smoothing passes are to be performed, then the boundary smoothing engine155optionally performs an inflation operation at step795. In general, performing a boundary smoothing pass on the mesh boundary610may shrink the mesh boundary610. Consequently, in order to return the mesh boundary610to its initial shape and size, an inflation operation may be performed. During the inflation operation, vertices620associated with the mesh boundary610are moved by an inflation distance in a direction that is perpendicular to the mesh boundary610. In one implementation, the inflation distance may be approximately the same distance that a vertex620was moved during one or more boundary smoothing passes. Additional discussion of the inflation operation is provided below with respect toFIGS. 9A-9C.

FIGS. 8A-8Cillustrate a smoothed mesh boundary611-1and smoothed mesh extrusion631generated with the boundary smoothing engine155, according to one embodiment of the present invention. As shown, performing multiple boundary smoothing passes on a mesh boundary610produces a smoothed mesh boundary611-1. Additionally, performing one or more mesh refinement passes on a region of vertices620-1that are proximate to the mesh boundary610may reduce mesh distortions generated during the boundary smoothing operation and produce a regular mesh of relatively uniform primitives in and around the mesh boundary610. Finally, as shown inFIG. 8C, the smoothed mesh extrusion631generated from the smoothed mesh boundary611-1has a dean, aesthetic appearance.

FIGS. 9A-9Cillustrate a smoothed mesh boundary611-2and an inflated mesh boundary612generated with the boundary smoothing engine155, according to one embodiment of the present invention. As shown, performing multiple boundary smoothing passes on the mesh boundary610-2produces a smoothed mesh boundary611-2while preserving the approximate initial shape of the mesh boundary610-2. Additionally, by performing an inflation operation, the initial shape of the mesh boundary610-2may be more accurately represented. For example, as shown inFIG. 9C, one or more vertices620associated with the smoothed mesh boundary611-2may be moved an inflation distance in a direction perpendicular to the smoothed mesh boundary611-2. Thus, shrinkage of the one or more regions of the mesh boundary610-2may be corrected by performing an inflation operation on one or more vertices620associated with the smoothed mesh boundary611-2.

In sum, a boundary smoothing engine receives a selection of a mesh boundary and performs one or more smoothing passes which shift and align the locations of the vertices associated with the mesh boundary. The boundary smoothing engine may further project the smoothed locations of the boundary vertices onto the initial surface of the mesh to preserve the mesh shape during smoothing. An inflation step also may be performed by the boundary smoothing engine to compensate for boundary shrinkage that may occur during the smoothing process.

One advantage of the techniques described herein is that a user is able to perform smoothing of a mesh boundary (e.g., to produce a high-quality mesh extrusion having smooth edges) without significantly distorting surrounding regions of the mesh. Additionally, by incrementally shifting vertex locations, re-projecting the smoothed locations onto the initial surface, and/or performing an inflation step, the general size and shape of the mesh boundary and mesh may be preserved during the smoothing process.

The invention has been described above with reference to specific embodiments. Persons of ordinary skill in the art, however, will understand that various modifications and changes may be made thereto without departing from the broader spirit and scope of the invention as set forth in the appended claims. The foregoing description and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense.

Therefore, the scope of embodiments of the present invention is set forth in the claims that follow.