Exact geometry operations on shapes using fixed-size integer...

Details Exact geometry operations on shapes using fixed-size integer... Exact geometry operations on shapes using fixed-size integer...

2011-08-23

2011-08-23

Whitmore, Stacy A (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Integrated circuit design processing

Physical design processing

C716S055000, C716S118000, C716S119000, C716S122000, C716S125000, C716S135000

Reexamination Certificate

active

08006214

ABSTRACT:
Techniques for improving efficiency and accuracy of computer-aided design are provided. In one aspect, a method for generating a computer-based representation of a design having one or more shapes is provided comprising the following steps. Each of the shapes in the design is represented with one or more trapezoids, wherein a fixed number of non-vertical lines are used to define an x-coordinate of a left and right base and sides of each trapezoid with intersection points being formed between the non-vertical lines that define the sides. The x-coordinates and intersection points are used to divide the trapezoids into disjoint trapezoids, wherein each disjoint trapezoid is defined by a combination of the same non-vertical lines that are used to define one or more of the trapezoids. An order is assigned to the x-coordinates and intersection points, wherein the x-coordinates and intersection points in the assigned order are representative of the design.

REFERENCES:
patent: 4523851 (1985-06-01), Maheras et al.
patent: 4542397 (1985-09-01), Biegelsen et al.
patent: 5822214 (1998-10-01), Rostoker et al.
patent: 6009251 (1999-12-01), Ho et al.
patent: 6178539 (2001-01-01), Papadopoulou et al.
patent: 6220919 (2001-04-01), Cheng
patent: 6407434 (2002-06-01), Rostoker et al.
patent: 6757876 (2004-06-01), Habitz
patent: 2005/0172251 (2005-08-01), Chang et al.
patent: 8790191 (1980-02-01), None
patent: 361061419 (1986-03-01), None
H. Bronnimann et al., “Computing Exact Geometric Predicates Using Modular Arithmetic with Single Precision,” 13th Annual ACM Symposium on Computational Geometry, Nice France (Jun. 4-6, 1997).
C. Burnikel, et al., “Efficient Exact Geometric Computation Made Easy,” Proceedings of the fifteenth annual symposium on Computational Geometry SCG (Jun. 1999).
C. Burnikel, et al., “Exact Geometric Computation in LEDA,” Proceedings of the eleventh annual symposium on Computational Geometry SCG '95 (Sep. 1995).
Gupta, et al., “Toward a Systematic-Variation Aware Timing Methodology,” Proceedings of the 41st Annual Conference on Design Automation DAC (Jun. 2004).
S. Schirra, “Robustness and Precision Issues in Geometric Computation,” Handbook of Computational Geometry, Chapter 14, pp. 597-632, Elsevier Science Publishers, Amsterdam (2000).
K. Sugihara, “Resolvable Representation of Polyhedra,” Proceedings on the Second ACM Symposium on Solid Modeling and Applications, p. 127-135, Montreal, Quebec, Canada (May 19-21, 1993).
C.K. Yap, et al., “The Exact Computation Paradigm,” Computing in Euclidean Geometry, vol. 4 of Lecture Notes Series on Computing, pp. 452-492, World Scientific, 2nd Edition (1995).
R. Banerjee, et al., “Topologically Exact Evaluation of Polyhedra Defined in CSG With Loose Primitives,” Computer Graphics Forum, vol. 15, No. 4, pp. 205-217 (1996).
Dobkin et al., “An Efficient Algorithm for Finding the CSG Representation of a Simple Polygon,” digital, Systems Research Center (Sep. 1989).
H. Halliwell, “Consistent Shape Check in LSI Masks,” TDB 02-80, p. 4232-4234 (Feb. 1980).
K. Mehlhorn, et al., A platform for combinatorial and geometric computing, Cambridge university press, 1999.
http//gmplib.org/.
http//www.cgal.org/.
C. Hoffmann, Geometric and Solid Modeling, Morgan-Kaufmann, San Mateo, CA, 1989.
C.M. Hoffmann, “The problems of accuracy and robustness in geometric computation,” IEEE Computer 22(3):31-41, Mar. 1989.
C. Yap, “Towards exact geometric computation,” Comput. Geom. Theory Appl., 7(1):3-23, 1997.
Kokichi Sugihara, an intersection algorithm based on Delaunay Triangulation, IEEE Computer Graphics and Applications, v. 12, n. 2, p. 59-67, Mar. 1992.
M. Lavin et al., “CAD Computations for Manufacturability: can we save VLSI Technology from itself?” Proceedings of the 2002 IEEE/ACM International Conference on Computer-Aided design ICCAD '02 (Nov. 2002).

Affiliated with

Also associated with

Rating

Exact geometry operations on shapes using fixed-size integer... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Exact geometry operations on shapes using fixed-size integer..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exact geometry operations on shapes using fixed-size integer... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2771078