Representation of implicit curves for procedural surfaces

Details Representation of implicit curves for procedural surfaces Representation of implicit curves for procedural surfaces

2004-10-28

2008-09-16

Chauhan, Ulka (Department: 2628)

Computer graphics processing and selective visual display system

Computer graphics processing

Shape generating

Reexamination Certificate

active

07425959

ABSTRACT:
Compact and accurate piecewise parametric representations of implicit functions may be achieved by iteratively selecting ranges of parameterizing regions and testing each for satisfying an intervalized super convergence test. In one aspect, the implicit function is represented as a compact form of one or more representations of such convergence regions. In yet another aspect, iteration is begun with applying the intervalized convergence test to an entire pameterization region. In yet another aspect, the range being tested for super convergence is iteratively sub-divided to generate other ranges for testing. In one aspect, such sub-dividing comprises dividing the selected ranges by half. In one further aspect, Newton iterate steps are applied to selected ranges to change such ranges for further testing of super convergence of such ranges. Parametric representations that use such representations of convergence regions to express implicit functions consume far less memory for storage than conventional representations. Algorithms are described herein for quickly calculating such representations.

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-44964 (2005-05-01), None
patent: WO 2004-044689 (2004-05-01), None
Argyros, Ioannis. “On the comparison of weak variant of the Newton-Kantorovich and Miranda theorems”. Jouranl of Computational and Applied Mathematics. vol. 166, Issue 2, Apr. 15, 2004, pp. 585-589.
Argyros, Ioannis. “On the Newton-Kantorovich hypothesis for solving equations”. Jouranl of Computational and Applied Mathematics. vol. 169, Issue 2, Aug. 15, 2004, pp. 315-332.
Dennis, Jr., J. E. “On the Kantorovich Hypothesis for Netwon's Method”. Siam J. Numer. vol. 6, No. 3. Sep. 1969. pp. 493-507.
Gutierrez et al. “Newton's Method Under Weak Kantorovich Conditions”. IMA Journal of Numerical Analysis. vol. 20. 2000. pp. 521-532.
Hernandez, M. A. “A Modification of the Classical Kantorovich Conditions for Newton's Method”. Journal of Computational and Applied Mathematics. vol. 137. 2001. pp. 201-205.
Kramer, Henry P. “The Iterative Determination of Model Parameters by Newton's Method”. General Electric Company. Sep. 1967. pp. 1-12.
Matthews, John H. “Module for Fixed Point Iteration and Newton's Method in 2D and 3D”, http://math.fullerton.edu/mathews
2003/FixPointNewtonMod.html. Mar. 14, 2004.
Nataraj et al. “A New Super-Convergent Inclusion Function Form and its Use in Global Optimization”. pp. 1-9.
Wiethoff, Andreas. “Interval Newton Method”. http://rz.uni-karlsruhe.de/˜iam/html/language/cxsc
ode12.html. Mar. 29, 1995.
Wikipedia. “Invertible Matrix”. http://en.wikipedia.org/wiki/Singular—matrix. Jul. 31, 2004.
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. pp. 222-226.
Bühler, “Rendering: Implicit Linear Interval Estimations”,Proceedings Of The 18thSpring Conference On Computer Graphics, Apr. 24-27, 2002, Budmerice, Slovakia.
Duff, “Interval Arithmetic Recursive Subdivision for Implicit Functions and Constructive Solid Geometry”,ACM Siggraph Computer Graphics, Proceedings of the 19thAnnual Conference on Computer Graphics and Interactive Techniques, vol. 26, Issue 2, p. 131-138, Jul. 1992.
Gottschalk et al., “OBBTree: A Hierarchical Structure For Rapid Interference Detection”,Proceedings Of The 23rdAnnual Conference On Computer Graphics And Interactive Techniques, 1996.
Krishnan et al., An Efficient Surface Intersection Algorithm Based On Lower-Dimensional Formulation,ACM Transactions On Graphics(TOG), vol. 16, Issue 1, Jan. 1997.
Ponamgi et al., “Incremental Algorithms for Collision Detection Between Solid Models”,Proceedings of The Third ACM Symposium On Solid Modeling And Applications, p. 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, p. 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, p. 321-334, Sep. 1993.
Snyder, “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.
International Search Report from PCT/US2006/032227 dated Dec. 28, 2006, 3 pages.
Dennis, “On the Kantorovich Hypothesis for Netwon's Method,” Siam J. Numer. Anal., vol. 6, No. 3, Sep. 1969, pp. 493-507.
International Search Report from PCT/US06/25413 dated Feb. 15, 2007, 7 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.

Affiliated with

Also associated with

Rating

Representation of implicit curves for procedural surfaces does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Representation of implicit curves for procedural surfaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Representation of implicit curves for procedural surfaces will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3991427