Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-07-20
2003-03-04
Vo, Cliff N. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06529192
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to the area of 3-dimensional (3D) image processing and more particularly relates to methods and systems for generating wire frame representations of 3D objects.
2. Description of the Related Art
Representing 3-dimensional objects for computer manipulation using a wire frame representation is well known in the art. A wire frame representation or mesh model makes it possible for a user to create a display or reproduction of the real world object and generate other displays such as “morphs”, fantasy or special effects. In applications of structural analysis such as simulation of automobile crashes and sheet metal forming, mesh models are essential for accurate assessment and integration.
Mesh model generation in various forms has been around for decades, but only recently has a mathematical theory rooted in computational geometry (a branch of computer science) laid out for the problem. For a survey of the theory underlying the mesh generation, see M. Bern and D. Eppstein, “Mesh generation and optimal triangulation, Computing in Euclidean Geometry,” edited by F. K. Hwang and D.-Z. Du, World Scientific, 1992.
Largely the motivation for providing a mesh model is based on natural observations. A repeating hexagonal pattern is a common one, observed in soap bubbles floating in liquid, compound eyes of insects, and many other natural phenomena. For example, bubbles of real soap floating in liquid are closely packed and they form a virtually regular hexagonal pattern. By connecting the bubbles' center points, a mesh of basically equilateral triangles is produced. Hence, one of the popular meshing methods is the bubble meshing proposed by simulating such natural phenomena.
The bubble meshing method generates well-shaped meshes, based on the following the heuristics: well-shaped meshes are generated by tightly packing the spherical objects into a given region, and connecting the center of the spherical objects. Therefore the sequences in the bubble meshing involve two steps: (1) packing circles or spheres, called bubbles, closely in a domain, and (2) connecting their centers by Delaunay triangulation, which selects the best topological connection for a set of nodes by avoiding small angles. The key element of bubble meshing lies in the first step, that is, the optimization of mesh node locations by close packing bubbles. A repulsive or attractive force much like an intermolecular van der Waals force is assumed to exist between two adjacent bubbles. A globally stable configuration of tightly packed bubbles is determined by solving the equation of motion.
The bubble meshing method and some other improved meshing methods provide an accurate wire frame representation of 3D objects but involve computations by repeatedly packing bubbles in order to optimize the mesh node locations. When a 3D region of is an object is provided and represented in a volumetric form, the first step in the bubble meshing method becomes unnecessary. There is therefore a need for a method to create a mesh model based on the volumetric cells, such method can be efficiently implemented and improve overall performance of 3D modeling process.
SUMMARY OF THE INVENTION
The present invention has been made in consideration of the above described problems and needs and has particular applications for a 3D modeling system that can be used to generate fully-textured models of objects. According to one aspect of the present invention, a 3D region of an object is generated by a space carving process and represented by volumetric cells encoded in a tree structure, such as an octree tree. Given the 3D region, the mesh process disclosed herein generates a mesh of elements covering the entire 3D region and intersecting with each other either not at all or at common boundary faces. According to one embodiment, the mesh process generates a mesh of self-constraint and intersected triangles that do not cross boundaries to preserve holes or other nonconvexities.
According to one embodiment, the meshing process disclosed herein is a process that begins with an octree structure to find all boundary cubes. For each of six faces of each of the boundary cubes, a “neighborhood configuration” thereof is triangulated in a way to derive only valid triangles bounding a 3D volume. All triangles generated are indexed in a list, which permits an effective post-processing of the triangles to remove duplicated triangles. The process is recursively performed for each of the boundary cubes as such a complete surface mesh or wire frame is generated.
One of the advantages of the present inventions is the elimination of processing a 3D region before a mesh process can be proceeded. The method enables an automatic generation of the mesh model from a 3D region of an object. Another advantage is to have an automatic mesh generator that generates a mesh model from a 3D volumetric representation encoded in an octree structure. The disclosed mesh generator takes as input only one item, namely, a specification of the 3D volumetric representation and results in a complete mesh model therefrom.
Other advantages, objects and features of the present invention, together with the foregoing, are attained in the exercise of the invention in the following description and resulting in the embodiment illustrated in the accompanying drawings.
REFERENCES:
patent: 6137492 (2000-10-01), Hoppe
patent: 6256038 (2001-07-01), Krishnamurthy
patent: 6300958 (2001-10-01), Mallet
Geometrix, Inc.
Vo Cliff N.
Zheng Joe
LandOfFree
Method and apparatus for generating mesh models of 3D objects does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for generating mesh models of 3D objects, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generating mesh models of 3D objects will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3056865