Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-09-30
2001-10-23
Luu, Matthew (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S423000, C345S421000, C345S440000, C345S441000
Reexamination Certificate
active
06307555
ABSTRACT:
BACKGROUND
This invention relates to Boolean operations for subdivision surfaces.
Computer modeling of surfaces finds use in a number of disciplines, from automotive design to fine art. A number of methods for constructing surfaces, especially smoothly-varying surfaces, have been developed. One example is NURBS surfaces constructed from piecewise polynomial representations. Recently, another method has been developed to construct complex surfaces. Subdivision surface methods allow for constructing any arbitrary surface (e.g., a human face, or a complex, yet smoothly-varying automobile surface) from a number of polygonal “faces”.
Subdivision surfaces comprise a significant generalization of the tensor product B-spline surfaces (or the slightly more general NURBS surfaces) which have been widely used in computer aided geometric modeling, as described above. With tensor product surfaces, the control vertices generally require a rectangularly gridded structure, where each interior vertex is connected to four neighboring vertices (“valance=4”). This can place serious restrictions on the designer. (For instance, closed surfaces can require special handling.) One advantage of subdivision surfaces (over NURBS surfaces) is that subdivision surfaces allow control meshes of arbitrary topology. Thus the vertices can have different valences and the faces of the control mesh need not be four sided.
A subdivision surface is generally defined in the following way. One starts with a base polygonal mesh (a set of control vertices together with their corresponding connectivity structure) M
0
. A subdivision scheme (consisting of a small number of rules) is applied to yield a refined new mesh M
1
, which can be called a derived mesh. (New vertices are introduced, and each old face is thereby replaced by several new smaller ones.) This is repeated recursively to give derived meshes M
n
, n=2, 3, . . . , with progressively denser vertices, as in
FIGS. 1A through 1D
. It can be proved that these polygonal meshes will converge to a limit surface S. This limit surface is called a subdivision surface.
The subdivision rules are adapted from the corresponding rules which hold for B-splines. Hence the tensor product B-spline surfaces form a subclass of subdivision surfaces. Subdivision surfaces were introduced in 1978 by Doo-Sabin (generalizing bi-quadratic splines) and Catmull-Clark (generalizing bi-cubic splines). In the Catmull-Clark scheme, after one subdivision step, (i.e., from M
1
onwards) all faces are quadrilaterals. A different type of subdivision scheme introduced by Loop uses triangular meshes (i.e., meshes with only triangular faces).
Since the subdivision rules for refining meshes are fixed, the final surface S is uniquely determined by the initial mesh M
0
. Thus S can be stored compactly as M
0
(or as any M
n
since each M
n
can be regarded as the base mesh for the same final surface.) The surface S can be modified by simply modifying the control vertices in the base mesh (or in any intermediate mesh M
n
, again treated as the new base mesh). One editing system for interactively modifying subdivision surfaces locally by moving selected mesh vertices, is shown in U.S. patent application, Ser. No. 08/839,349, entitled “Editing a Surface”, incorporated by reference.
Since S is the limit of M
n
, to render the subdivision surface, one can usually and simply render an intermediate mesh M
n
at some appropriately large n. Alternatively, one can render S by evaluating the limit surface (points and normals) exactly. One method for evaluating S in this manner is shown in U.S. patent application, Ser. No. 09/116,553, filed Jul. 15, 1998, entitled “Surface Evaluation”, incorporated by reference.
One problem with subdivision surfaces is that the base mesh for a complex surface may be difficult or time-consuming to construct. Mesh data for a real surface may be obtained from measurement or scanning of an existing object. This generally results in a rather dense mesh. Moreover, since subdivision does not generally interpolate mesh vertices, the limit surface may not reproduce the original real surface. In free form design, mesh data may be painstakingly entered by a designer and modified later. Modifying a large number of vertices in some intermediate mesh M
n
can prove time-consuming.
SUMMARY
In general, in a first aspect, the invention features a method for creating a new subdivision surface from one or more prior subdivision surfaces using a computer, the computer having a processor and a memory, the method including establishing in the memory a data structure storing data representing the structures of the prior subdivision surfaces, performing Boolean operations upon prior meshes defining the one or more prior subdivision surfaces to form a resulting mesh defining the new subdivision surface, and storing the resulting mesh in the memory.
Embodiments of the invention may include one or more of the following features. The Boolean operations may include a subtraction operation wherein a portion of one of the prior meshes is deleted. The portion that is deleted may be on one side of an intersection curve formed by the intersection of two or more of the prior meshes. The Boolean operations may include a join operation wherein at least a portion of one of the prior meshes is joined with at least a portion of another of the prior meshes. The subtraction operation may further include determining an intersection between at least two prior meshes, the intersection defining an intersection curve, tessellating faces of the prior meshes incident to the intersection curve, selecting surviving portions of the prior meshes using the intersection curve, and deleting faces of the prior meshes according to the selected surviving portions. The Boolean operations may further include a join operation including combining remaining faces of the prior meshes into a new combined mesh.
In general, in another aspect, the invention features a method for performing Boolean operations upon two base meshes using a computer, where each base mesh comprises a plurality of faces, the computer having a processor and a memory, the method including establishing in the memory a data structure storing data representing the structures of the two base meshes, determining intersections of the two base meshes, the intersections defining an intersection curve, tessellating faces incident to the intersection curve, selecting surviving portions of the intersecting faces, deleting faces of the two base meshes according to the selected surviving portions, and combining remaining faces of the two base meshes into a resultant base mesh.
Embodiments of the invention may include one or more of the following features. Selecting the surviving portions of the two base meshes may be by user input through an input device of the computer, or be automatically calculated by the processor. Tessellating the faces of the base meshes incident to the intersection curve may convert any face having greater than three sides into two or more new faces having only three sides, or convert any face having a number of sides different from four into two or more new faces having only four sides. A surface may be constructed from the resultant base mesh, and the surface may be constructed using subdivision rules. A plurality of intersections between intersecting faces of the two base meshes may be computed, the plurality of intersections defining a plurality of intersection curves.
In general, in another aspect, the invention features a computer program, residing on a computer-readable medium, comprising instructions for creating a new subdivision surface from one or more prior subdivision surfaces by causing a computer to establish in a memory of the computer a data structure storing data representing the structures of the prior subdivision surfaces, perform Boolean operations upon prior meshes defining the one or more prior subdivision surfaces to form a resulting mesh defining the new subdivision surface, and store the resulting mesh in the memory.
In
Luu Matthew
Sajous Wesner
Silicon Graphics Inc.
Staas & Halsey , LLP
LandOfFree
Boolean operations for subdivision surfaces does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Boolean operations for subdivision surfaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Boolean operations for subdivision surfaces will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2593682