Patent US2902675A successfully refreshed from Google Patents.
Patent US5367465A successfully refreshed from Google Patents.
US5367465A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Solids surface grid generation for three-dimensional topography simulation
Assignee: NTT Inc
•
Filing: 1992-06-24
•
Granted: 1994-11-22
•
Expires: 2012-06-24
Abstract
Abstract A method for creating regular triangular grid representations of a solid surface from a representation comprised of a plurality of polygons. Such a regular grid is necessary in order to accurately deform a solid during simulation of a process step. The method of the preferred embodiment is comprised generally of the steps of: removing any holes defined by the polygon face; placing a new edge between a first and second vertex of the polygon face; discarding the new edge if the new edge lies outside the polygon face or if the new edge intersects an existing edge of the polygon face; adding the new edge to the polygon face if the new edge does not lie outside the polygon face; identifying a triangle being created by the new edge and existing edges of the polygon; forming a new polygon face from the edges creating a triangle; and repeating the above steps until all polygon faces are triangulated. Once the triangulation of the polygons is completed, adjustments to the triangles is made in order to have only triangles of uniform size.
Inventors
- 👤 Satoshi Tazawa
- 👤 Kazuyuki Saito
- 👤 Francisco A. Leon
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 09:44
CPC Classifications
G; G06; G06T; G06T17/00; G06T17/20
Claims Analysis
Total Claims: 7
Claim 1
Independent Claim
285 words
A method for generating a triangular grid representation of a surface, said surface comprised of polygon faces, said method comprising the steps of: a) providing a polygon face to a triangulation means, said polygon face including an outer loop, said polygon face having holes, a hole including an inner loop; b) removing holes in said polygon face, said removing holes in said polygon face including inserting a new edge between an outer loop vertex point and an inner loop vertex point; c) positioning a potential edge between a first and second vertex of said polygon face; d) testing said potential edge for invalid conditions, said invalid conditions including a first condition where said new edge lies outside a polygon face boundary and a second condition where said new edge intersects said polygon face boundary; e) discarding said potential edge if an invalid condition exists; f) adding said potential edge to said polygon face if an invalid condition does not exist; g) extracting a triangular face from said polygon face, said triangular face having said potential edge as a first edge; h) adding said triangular face to said triangular grid; i) re-defining said polygon face exclusive of said triangular face, and j) adjusting said triangular grid to create triangles within a specified size, including the steps of, identifying a long edge whose length exceeds a predetermined length X, inserting a new vertex at the midpoint of said long edge, adding a first new edge between said new vertex and a first vertex corresponding to a first triangle associated with said long edge, and adding a second new edge between said new vertex and a second vertex corresponding to a second triangle associated with said long edge.
Claim 2
Independent Claim
285 words
A method for generating a triangular grid representation of a surface, said surface comprised of polygon faces, said method comprising the steps of: a) providing a polygon face to a triangulation means, said polygon face including an outer loop, said polygon face having holes, a hole including an inner loop; b) removing holes in said polygon face, said removing holes in said polygon face including inserting a new edge between an outer loop vertex point and an inner loop vertex point; c) positioning a potential edge between a first and second vertex of said polygon face; d) testing said potential edge for invalid conditions, said invalid conditions including a first condition where said new edge lies outside a polygon face boundary and a second condition where said new edge intersects said polygon face boundary; e) discarding said potential edge if an invalid condition exists; f) adding said potential edge to said polygon face if an invalid condition does not exist; g) extracting a triangular face from said polygon face, said triangular face having said potential edge as a first edge; h) adding said triangular face to said triangular grid; i) re-defining said polygon face exclusive of said triangular face, and j) adjusting said triangular grid to create triangles within a specified size, including the steps of, identifying a long edge whose length exceeds a predetermined length X, inserting a new vertex at the midpoint of said long edge, adding a first new edge between said new vertex and a first vertex corresponding to a first triangle associated with said long edge, and adding a second new edge between said new vertex and a second vertex corresponding to a second triangle associated with said long edge.
Claim 3
Dependent Claim
106 words
The method as recited in claim 1 wherein said step of adjusting said triangular grid to create triangles within a specified size further comprises the steps of: a)identifying a short edge which does not exceed a predetermined length Y; b)selecting a moved vertex location along aid short edge; c)identifying edges adjacent to said short edge whose removal would cause the shape of the original structure to be best retained; d)inserting a moved vertex point at said moved vertex location; e)deleting said short edge so that all adjacent edges to said short edge, are adjacent to said moved vertex point; and f)deleting edges identified in step c).
Claim 4
Dependent Claim
103 words
The method as recited in claim 2 wherein said step of adjusting said triangular grid to create triangles within a specified size further comprises the steps of: a) identifying a short triangle which has a height that does not exceed the height Z; b) identifying an edge adjacent the smallest angles of said short triangle, said edge including a first vertex of said short triangle and a second vertex of said short triangle; c) deleting said edge identified in step b); and d) inserting an edge between a third vertex point of said shorttriangle and a corresponding vertex point in a neighboring triangle.
Claim 5
Dependent Claim
23 words
The method as recited in claim 1 wherein said length X is 160% of the nominal size of a device to be manufactured.
Claim 6
Dependent Claim
23 words
The method as recited in claim 2 wherein said length Y is 60% of the nominal size of a device to be manufactured.
Claim 7
Dependent Claim
23 words
The method as recited in claim 3 wherein said distance Z is 28% of the nominal size of a device to be manufactured.
References Cited (Backward Citations)
US4797842A
Cited
US4819161A
Cited
US4912664A
Cited
US4933889A
Cited
US5067101A
Cited
US5070469A
Cited
US5036316A
Cited
US5125038A
Cited
US5214752A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-11-21 | 1998-05-23 | 1998-11-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-11-21 | 2002-05-23 | 2002-11-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-11-21 | 2006-05-23 | 2006-11-22 | $7700.00 | Window Closed / Lapsed |