Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2005-06-30
2008-08-05
Nguyen, Kimbinh T (Department: 2628)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S419000, C345S421000, C345S423000, C345S581000, C345S583000, C700S066000, C700S090000, C700S186000
Reexamination Certificate
active
07408548
ABSTRACT:
A complex procedural surface can be expressed based on some constructive solid geometry operations performed on primitive procedural surfaces. The domain based representation of the complex procedural surface includes implicit curves of intersection. During pre-processing, the parts of the domain based representation to be triangulated are first sub-divided into simple triangles not bound on any side by an edge related to the parameterized regions of the implicit curve and curve visibility triangles. The coarse pre-processed triangulated mesh is later refined during runtime by further sub-dividing the coarse mesh to add triangles with curve based edges and non-curve based edges to generate a mesh of sampling triangles. The more refined sampling triangle mesh is further refined by applying geometry instancing to map appropriate instance meshes into the appropriate sampling triangles to create an even more refined triangulated mesh at runtime for rendering.
REFERENCES:
patent: 6100893 (2000-08-01), Ensz et al.
patent: 6285372 (2001-09-01), Cowsar et al.
patent: 6300958 (2001-10-01), Mallet
patent: 6356263 (2002-03-01), Migdal et al.
patent: 6525727 (2003-02-01), Junkins et al.
patent: 6806875 (2004-10-01), Nakatsuka et al.
patent: 2002/0171643 (2002-11-01), Ernst et al.
patent: 2003/0174133 (2003-09-01), Shehane et al.
patent: 2004/0114794 (2004-06-01), Vlasic et al.
patent: 2004/0263516 (2004-12-01), Michaili et al.
patent: 2005-0044964 (2005-05-01), None
patent: WO 2004-044689 (2004-05-01), None
International Search Report and Written Opinion for PCT/US06/25413 dated Feb. 15, 2007, 5 pages.
International Search Report from PCT/US2006/032227 dated Dec. 28, 2006, 3 pages.
Bühler, “Implicit Linear Interval Estimations,”Proceedings of the 18thSpring Conference On Computer Graphics, Apr. 24-27, 2002, Budumerice, Slovakia.
Duff, “Interval Arithmetic and Recursive Subdivision for Implict Functions and Constructive Solid Geometry,”ACM Siggraph Computer Graphics, Proceedings of the 19thAnnual Conference on Computer Graphics and Interactive Techniques, vol. 26, Issue 2, pp. 131-138, Jul. 1992.
Krishnan et al., “An Efficient Surface Intersection Algorithm Based on Lower-Dimensional Formulation,”ACM Transactions On Graphics(TOG), vol. 16, Issue 1, Jan. 1997, pp. 74-106.
Ponamgi et al., “Incremental Algorithms for Collision Detection Between Solid Models,”Proceedings of The Third ACM Symposium On Solid Modeling and Applications, pp. 293-304, May 17-19, 1995, Salt Lake City, Utah, United States.
Snyder et al., “Generative Modeling: A Symbolic System for Geometric Modeling,” California Institute of Technology, fromProceedings of SIGGRAPH 1992, Association for Computing Machinery Special Interest Group on Computer Graphics (ACM SIGGRAPH), vol. 26, Issue 2, Jul. 1992, pp. 369-378.
Snyder et al., “Interval Methods For Multi-Point Collisions Between Time-Dependent Curved Surfaces,”Proceedings Of The 20th Annual Conference On Computer Graphics and Interactive Techniques, pp. 321-334, Sep. 1993, 11 pages.
Synder, “Interval Analysis for Computer Graphics,”ACM SIGGRAPH Computer Graphics, Proceedings of the 19thAnnual Conference on Computer Graphics and Interactive Techniques, vol. 26, Issue 2, Jul. 1992.
Argyros, “On the comparison of a weak variant of the Newton-Kantorovich and Miranda theorems,”Journal of Computational and Applied Mathematics, vol. 166, Issue 2, Apr. 2004, pp. 585-589, available online as of Feb. 20, 2004.
Argyros, “On the Newton-Kantorovich hypothesis for solving equations,”Journal of Computational and Applied Mathematics, vol. 169, Issue 2, Aug. 2004, pp. 315-332, available online as of Mar. 19, 2004.
Dennis, “On the Kantorovich Hypothesis for Newton's Method,”SIAM J. Numer. Anal., vol. 6, No. 3, Sep. 1969, pp. 493-507.
Gottschalk et al., “OBBTree: A Hierarchial Structure For Rapid Interference Detection,”Proceedings Of The 23rd Annual Conference on Computer Graphics and Interactive Techniques, 1996, pp. 171-180.
Gutierrez et al., “Newton's method under weak Kantorovich conditions,”IMA Journal of Numerical Analysis, vol. 20, 2000, pp. 521-532.
Hernandez, “A modification of the classical Kantorovich conditions for Newton's method,”Journal of Computational and Applied Mathematics, vol. 137, 2001, pp. 201-205.
Kramer, “The Iterative Determination of Model Parameters by Newton's Method,”General Electric Company, Sep. 1967, 20 pages.
Matthews, “Module for Fixed Point Iteration and Newton's Method in 2D and 3D,” http://math.fullerton.edu/mathews
2003/FixPointNewtonMod.html, Mar. 14, 2004, 9 pages.
Nataraj et al., “A New Super-Convergent Inclusion Function Form and its Use in Global Optimization,”SIAM Workshop on Validated Computing, May 2002, pp. 1-9.
Wiethoff, “Interval Newton Method,” http://rz.uni-karlsruhe.de/˜iam/html/language/cxsc
ode12.html, Mar. 29, 1995, 2 pages.
Wikipedia, “Invertible Matrix,” http://en.wikipedia.org/wiki/Singular—matrix, Jul. 31, 2004, 7 pages.
Zlepko et al., “An Application of a Modification of the Newton-Kantorovich Method to the Approximate Construction of Implicit Functions,” Ukrainskii Matematicheskii Zhurnal, vol. 30, No. 2, Mar.-Apr. 1978, 4 pages.
Bartels et al., “An introduction to splines for use in computer graphics & geometric modeling,” Chapter 3, Hermite and Cubic Spline Interpolation, San Francisco, CA, Morgan Kaufmann, pp. 9-17, 1998.
Sederberg et al., “Geometric hermite approximation of surface patch intersection curves,” Computer Aided Geometric Design 8:97-114, 1991.
Gavriliu Marcel
Guenter Brian K.
Klarquist & Sparkman, LLP
Microsoft Corporation
Nguyen Kimbinh T
LandOfFree
Triangulating procedural geometric 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 Triangulating procedural geometric objects, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Triangulating procedural geometric objects will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4004529