Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2002-05-29
2004-09-21
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06795069
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to computer graphics, and more particularly to free-form modeling of renderable objects.
BACKGROUND OF THE INVENTION
A number of graphical user interfaces (GUI) for modeling three-dimensional objects are known. For instance, “Sketch” is an interface designed to help a user with geometric modeling, see Zeleznik et al., “Sketch: An Interface for Sketching 3D Scenes,” Proceedings of SIGGRAPH-96, 1996. Sketch uses a system of intuitive guesses to guide the user through geometrical model generation. For example, if the user draws three line segments meeting at one point and parallel to the projections of the x-, y- and z-axes of the scene, then Sketch generates a parallelepiped whose dimensions are determined by the lengths of the line segments. After the user has mastered a set of agreements like that, more complex models composed of many primitives can be generated.
Another system can be used for sketching CAD-like geometric objects, see Lipson et al., “Conceptual design and analysis by sketching,” Proceedings of AIDAM-97, 1997. In an input sketch, the user draws both visible and hidden contours of a rectilinear object from which its shape is inferred. Their approach is based on correlations among arrangements of lines of the 2D drawing and lines in 3D space. For instance, by experimentation, the user can notice that the more two lines are parallel in the 2D sketch plane, the more the lines are likely to represent parallel lines in 3D space. They rely on a geometric correlation hypothesis that one can evaluate the likelihood of human understanding of the sketch by a joint probability of all correlations in the sketch.
Igarashi et al. also describe an interface for free-form modeling, see Igarashi et al. “Teddy: A sketching interface for 3D freeform design,” Proceedings of SIGGRAPH 99, pp. 409-416, 1999. There, the user inputs a simple closed stroke to form a contour. The system then generates a model in the form of a polygon mesh that matches the contour. The user adds details by editing the polygon mesh. Operations such as extrusion, cutting, bending and drawing on the mesh are allowed. However, because the underlying surface representation is a polygonal mesh, maintaining a smooth surfaced model is a problem.
Tolba et al. describe a system that allows the user to draw a scene with 2D strokes, and then to view the scene from different points of view as if a 3D scene was generated. The system projects the 2D strokes onto a sphere having its center at the viewing frustum. The strokes can then be rendered in perspective. The purpose of their system is to provide perspective drawing and not a 3D model of a scene, see Tolba et al., “Sketching with projective 2d strokes,” ACM Symposium on User Interface Software and Technology, pp. 149-157, 1999, and Tolba et al., “A projective drawing system,” I3D'01, pp. 25-34, 2001.
Another system correlates features in a hand-drawn figure to a textured, 3D model. The 3D model is then distorted with a warp to conform to the hand-drawn figure. The warp distorts the model in two dimensions to match the figure from a given camera perspective, yet preserves 3D effects, such as self-occlusion and foreshortening, see Petrovic, “Shadows for cel animation,” Proceedings of SIGGRAPH 2000,” pp. 511-516, 2000.
With respect to underlying model representations, implicit-surface modeling is described by Bloomenthal, in “Introduction to Implicit Surfaces,” Morgan-Kaufmann, 1997.
The “Skin” system supports a form of constructive drawing. There, the user generates a set of basic forms over which a skin is placed. The characteristics of the forms are then modified by small adjustments to offset distances at various scales of subdivision of the skin mesh. The skin is basically a polygonization of an implicit surface that is defined by a combination of signed-distance representations of the underlying forms, see Markosian, “Skin: A constructive approach to modeling free-form shapes,” Proceedings of SIGGRAPH 99, pp. 393-400, 1999.
In contrast, Wyvill et al. describe a blob-tree. The blob-tree is a CSG like hierarchy of implicit models in which implicit shapes are combined by a rich collection of operators, including various deformation operators. The emphasis in that work is on the representation of complex implicit surfaces through a tree-like structure, see Wyvill et al., “The Blob Tree, Warping, Blending and Boolean Operations in an Implicit Surface Modeling System,” Implicit Surfaces 3, 1998.
Barthe et al. describe a method for blending a pair of implicit surfaces defined as zero-sets of functions ƒand g by considering each point of R
3
as having ƒand g “coordinates,” i.e., by treating a mapping
a. (ƒ, g):R
3
:→R
2
:p→(ƒ(p), g(p))
as a “coordinatization” of 3D space. A first surface is a pre-image of the ƒ=0 axis, and a second is the pre-image of the g=0 axis. By examining pre-images of other curves in (ƒ, g)-space, especially ones containing large portions of these two axes, they can blend between the two surfaces, see Barthe et al., “Implicit extrusion fields,” The 2000 International Conference on Imaging Science, Systems, and Technology (CISST'2000), pp. 75-81, 2000.
Variational implicit surfaces are described by Turk et al., in “Shape transformation using variational implicit functions,” SIGGRAPH'99, 1999. Variational implicit surfaces can be used to represent complex objects, as described by Carr et al. in “Reconstruction and representation of 3d objects with radial basis functions,” Proceedings of SIGGRAPH 2001, pp. 67-76, 2001. Their methods allows one to simplify model representations by judicious deletion of constraint points.
SUMMARY OF THE INVENTION
The present invention uses variational implicit surfaces to support a set of free-form modeling operations. The modeling operations are inflation, hierarchy generation, merging, and modification. The inflation, merging and modification operations are implemented in a similar way by removing some constraints on the variational implicit surface and introducing others. This uniformity leads to simplicity of system structure and process coding.
More particularly, an input device is used to generate input strokes visible on a display device. The input strokes are acquired and resampled to be evenly spaced. Then, depth values are assigned to the resampled 2D points to form 3D contours. Variational implicit surfaces are fitted to the 3D contours to generate 3D blobs that form the 3D model to be rendered on an output device. The blobs can be merged by guidance strokes, and modified by target strokes.
REFERENCES:
patent: 6549201 (2003-04-01), Igarashi et al.
Hughes John F.
Karpenko Olga
Raskar Ramesh
Brinkman Dirk
Curtin Andrew J.
Mitsubishi Electric Research Laboratories Inc.
Santiago Enrique L
Zimmerman Mark
LandOfFree
Free-form modeling of objects with variational implicit... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Free-form modeling of objects with variational implicit..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Free-form modeling of objects with variational implicit... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3252107