Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2006-07-11
2006-07-11
Chauhan, Ulka (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S428000, C345S624000, C716S030000, C716S030000
Reexamination Certificate
active
07075532
ABSTRACT:
A tetrahedralization and triangulation method used with the proximity based rounding method to satisfy topological consistency of tetrahedralization with the bounded precision of a digital computer is described. Tetrahedralization is applied to a VLSI design, and more specifically for solving Maxwell's equation to extract parasitic capacitances and 3-D optical proximity correction applications. The exactness of solving Maxwell's equation and finite element analysis depends on the correctness of the topological properties of the tetrahedralization. Among the important aspects of the correctness of the topological properties is the absence of spurious intersection of two or more tetrahedra. In a typical digital computer, numbers are represented using finite sized words. Round-off errors occur when a long number is represented using the finite word size. As a result, tetrahedralization loses its topological consistency. The proximity based rounding method finds potential locations of spurious intersections and pre-corrects these locations to avoid the generation of any topological inconsistencies.
REFERENCES:
patent: 4933889 (1990-06-01), Meshkat et al.
patent: 5428717 (1995-06-01), Glassner
patent: 5553009 (1996-09-01), Meshkat et al.
patent: 5553206 (1996-09-01), Meshkat
patent: 5751591 (1998-05-01), Asada
patent: 5966140 (1999-10-01), Popovic et al.
patent: 6008102 (1999-12-01), Alford et al.
patent: 6046744 (2000-04-01), Hoppe
patent: 6100893 (2000-08-01), Ensz et al.
patent: 6106567 (2000-08-01), Grobman et al.
patent: 6141676 (2000-10-01), Ramirez-Angulo et al.
patent: 6373489 (2002-04-01), Lu et al.
patent: 6377865 (2002-04-01), Edelsbrunner et al.
patent: 6381730 (2002-04-01), Chang et al.
patent: 6526549 (2003-02-01), You
patent: 6643831 (2003-11-01), Chang et al.
patent: 6690385 (2004-02-01), Mukherjee
patent: 6693631 (2004-02-01), Hubeli et al.
patent: 6725430 (2004-04-01), Draxler et al.
patent: 6760023 (2004-07-01), Hubeli et al.
patent: 6806874 (2004-10-01), Biermann et al.
patent: 6812925 (2004-11-01), Krishnan et al.
patent: 2002/0167513 (2002-11-01), Baraff et al.
patent: 2003/0052875 (2003-03-01), Salomie
patent: 2003/0151604 (2003-08-01), Kaufman et al.
Mukherjee, M., “An efficient and simple polygon intersection algorithm”, Proc. of First ACM Symposium on Solid Modeling Foundations and CAD/CAM Applications (Austin, Tx, Jun. 5-7, 1991), SMA '91, ACM Press, N. Y., NY.
Christoph M. Hoffman, 37 The Problems of Accuracy and Robustness in Geometric Computation”, IEEE, vol. 22, Issue 3, Mar. 1989, pp. 31-41.
Christoph M. Hoffman, “Robust set operations on polyhedral solids”, □□ Computer Graphics and Applications, IEEE, vol. 9, Issue 6, Nov. 1989 pp. 50-59.
Victor Milenkovic, “Double Precision Geometry: A General Tehnique for Calculating Line and Segment Intersections Using Rounded Arithmetic”, IEEE, Fndns of Comp. Sci., 1989., 30th Ann'l Symposium, pp. 500-505.
Victor J. Milenkovic, “Verifiable Implementations of Geometric Algorithms Using Finite Precision Arithmetic”, Tech. Report CS-88-168, Carnegie Mellon Univ., Pittsburgh, Dec. 1987, pp. 378-401.
Segal, M. and Séquin, C. H., “Consistent calculations for solids modeling”, Proc. of the First Ann'l Symp. on Computational Geometry (Baltimore, Md, Jun. 5-7, 1985). ACM Press, NY, NY, 29-38.
Jerke, et al., “Hierarchical Current Density Verification for Electromigration Analysis in Arbitrary Shaped Metallization Patterns of Analog Circuits”, Proc. of Conference on Design, Automation and Test in Europe, 2002, IEEE Computer Society.
Hoffmann, et al., “Towards implementing robust geometric computations”, Proc. of the Fourth Annual Symposium on Computational Geometry, SCG '88, ACM Press, New York, NY, pp. 106-117.
Segal, M., “Using tolerances to guarantee valid polyhedral modeling results”, Proc. of the 17th Annual Conference on Computer Graphics and interactive Techniques, SIGGRAPH '90, ACM Press, New York, NY, pp. 105-114.
Christoph M. Hoffmann, “The Problems of Accuracy and Robustness in Geometric Computation”, IEEE, Mar. 1989, pp. 31-41.
Christoph M. Hoffmann et al., “Robust Set Operations on Polyhedral Solids”, IEEE, Nov. 1989, pp. 50-59.
Victor Milenkovic et al. “Double Precision Geometry: A General Technique for Calculating Line and Segment Intersections Using Rounded Arithmetic”, IEEE, 1989, pp. 500-505.
Victor J. Milenkovic, “Verifiable Implementations of Geometric Algorithms Using Finite Precision Arithmetic”, MIT Press, Cambridge, Massachusetts, 1989, pp. 377-401.
Mark Segal et al., “Consistent Calculations for Solids Modeling”, Computer Science Division, Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, Mar. 1984, pp. 29-38.
Maharaj Mukherjee, “An Efficient and Simple Polygon Intersection Algorithm”, The ACM Digital Library, Jul. 28, 2006, pp. 527.
Dewey, III Lewis William
Mukherjee Maharaj
Chauhan Ulka
Prendergast Roberta
Schnurmann H. Daniel
LandOfFree
Robust tetrahedralization and triangulation method with... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Robust tetrahedralization and triangulation method with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Robust tetrahedralization and triangulation method with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3559572