Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-05-24
2003-04-08
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S420000
Reexamination Certificate
active
06545676
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
The present invention relates to obtaining an approximation of an outer envelope of a geometrical representation of an object. In particular, the present invention relates to obtaining a tessellated approximation of an outer envelope of the object. Tessellation as used herein refers to representing a surface by a plurality of triangles.
BACKGROUND OF THE INVENTION
Conventional computer aided design (CAD)/computer aided manufacturing (CAM) systems provide models of three dimensional objects that include geometrical representations of the objects.
A designer employing a CAD/CAM system may want to create an approximation of the outer surfaces of a geometrical representation of an object. For example, the designer may need access to data representing the outer surfaces of the object to be able to incorporate the object into a structure to be designed. In many applications, such a designer needs to access a geometrical representation of only the outer surfaces without a need to access data corresponding to the inner components and/or structures of the object. For example, a designer of a motorcycle gas tank may need data corresponding to the surface geometry of the engine, to be able to shape the tank to avoid the engine. Such a designer does not need to know about the interior components of the engine or the detailed structure of the cooling lines to accomplish her task. In an alternative example, a manufacturer intent on protecting proprietary information may want to provide a designer with data corresponding to the outer envelope of an object without disclosing to the designer the proprietary components and/or structures contained within the object.
In another application, a designer may need an approximate envelope of a volume of space swept by a moving object as it moves within its full range of motion. Alternatively, a designer may need an approximate envelope of a volume of space within which a plurality of static objects reside. In yet another application, a designer may need an approximation of the outer envelope of a digital image of a physical object, i.e., a point cloud of the object.
SUMMARY OF THE INVENTION
The present invention provides a computer-implemented method for creating a tessellated approximation of an outer envelope of a geometrical representation of an object. The method of the invention typically receives a geometrical representation that is enclosed within a bounding structure. Alternatively, the method of the invention can receive a geometrical representation that is not enclosed within a bounding structure. In such a case, the method of the invention initially encloses the geometrical representation within a bounding structure, which can have a variety of different shapes. The bounding structure is preferably selected to be a rectangular parallelepiped.
The method of the invention includes a step of sub-dividing the bounding structure into a number of cells, wherein each cell can be selected to be a rectangular parallelepiped. In a subsequent step, the method of the invention provides an outermost subset of the cells dividing the bounding structure by iteratively removing from consideration those boundary cells that do not contain any portion of the geometrical representation such that each cell in the outermost subset contains at least a portion of the outer envelope of the geometrical representation and includes at least an exposed face.
Subsequently, the method of the invention partitions each exposed face of each cell in the outermost subset into two triangles to form a first set of triangles. The method then projects the vertices of each triangle in the first set onto the outer envelope of the geometrical representation, to obtain a second set of triangles whose vertices lie on the outer envelope. The triangles in this second set provide a tessellated approximation of the outer envelope of the geometrical representation.
One aspect of the present invention relates to providing in a computer platform having a facility for generating a geometrical representation of an object, a computer readable-medium holding computer-executable instructions for creating a tessellated approximation of a geometrical representation according to the method of the present invention.
Another aspect of the invention relates to providing in a computer platform having a facility for generating a geometrical representation of an object, a transmission medium for transmitting computer-executable instructions for creating a tessellated approximation of a geometrical representation of an object according to the method of the present invention.
In accordance with yet another aspect of the invention, a computer-readable medium is provided that holds computer-executable instructions for obtaining a tessellated approximation of a geometrical representation of an object through the method of the present invention.
The method of the invention can be implemented in a computer platform having a facility for generating a geometrical representation of an object. For example, a CAD/CAM system is particularly suited for implementation of the method of the invention. Such a computer platform can be programmed to produce executable instructions for practicing the method of the invention, i.e., to create a tessellated approximation of the outer envelope of a geometrical representation. Further, executable instructions for practicing the method of the invention can be stored in a computer readable medium, such as a floppy disk, a hard disk, or a CD-ROM.
One aspect of the invention relates to providing a visual display of an outer envelope, i.e., outer surfaces, of a geometrical representation without displaying components and/or structures contained within the outer envelope.
Another aspect of the invention relates to creating a tessellated approximation of a digital image of an outer envelope of a physical object, i.e., a point cloud of the object. Such a digital image can be obtained by a scanner, and be subsequently represented as a model in a CAD/CAM system. The method of the invention can be practiced on such a model to create a tessellated approximation of its outer envelope.
Another aspect of the invention relates to providing a tessellated approximation of an outer envelope of a union of a plurality of geometrical representations, e.g., a plurality of models. Each of such plurality of models can correspond to the geometrical representation of a moving object at a particular location as it moves within its full range of motion. A tessellated approximation of the outer envelope of such a union of models in accordance with the teachings of the invention is herein referred to as a motion envelope of the object. Alternatively, the plurality of models can correspond to the geometrical representations of a plurality of static objects. The tessellation method of the invention can also be employed to create an approximation of an outer envelope of a union of geometrical representations of a number of static objects.
The method of the invention for creating a tessellated approximation of a union of a set of models includes an initial step of producing an additive model that contains data corresponding to all surfaces of the set of models. The additive model can optionally include data corresponding to a number of points in the space between the surfaces of the set of models, obtained through interpolation between such surfaces. Subsequently, the method of the invention creates a tessellated approximation of the outer envelope of the additive model in accordance with the teachings of the present invention.
Illustrative embodiments of the present invention will be described below relative to the following drawings.
REFERENCES:
patent: 4685070 (1987-08-01), Flinchbaugh
patent: 5272642 (1993-12-01), Suzaki
patent: 5428718 (1995-06-01), Peterson et al.
patent: 5819016 (1998-10-01), Watanabe et al.
patent: 5912675 (1999-06-01), Laperrière
patent: 5988862 (1999-11-01), Kacyra et al.
patent: 6044306 (2000-03-01), Shapiro et al.
patent: 6172679 (2001-01-01), L
Elnitsky Serge
Ryan Kevin M.
Lahive & Cockfield LLP
Padmanabhan Mang
Parametric Technology Corporation
Zimmerman Mark
LandOfFree
Method and system for creating a tessellated approximation... 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 system for creating a tessellated approximation..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for creating a tessellated approximation... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3093099