Source: http://www.google.com/patents/US6874150?dq=No.+6,411,949&ei=AUR7T-LGJqSr0AHy2aSiBg
Timestamp: 2017-01-18 08:26:55
Document Index: 237694305

Matched Legal Cases: ['art9612', 'art4', 'art/9606', 'art4', 'art/9606', 'art7', 'art/9606', 'art5', 'art/9606', 'art6', 'art/9606', 'art8', 'art 2']

Patent US6874150 - Method and system for maintaining connections between surfaces and objects ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsA method and system are provided for controlling the algorithmic elements in 3D graphics systems via an improved 3D graphics API and for managing computing resources utilized in connection with the maintenance of connections between surfaces and objects. When multiple applications are running simultaneously,...http://www.google.com/patents/US6874150?utm_source=gb-gplus-sharePatent US6874150 - Method and system for maintaining connections between surfaces and objects in a graphics display systemAdvanced Patent SearchTry the new Google Patents, with machine-classified Google Scholar results, and Japanese and South Korean patents.Publication numberUS6874150 B2Publication typeGrantApplication numberUS 09/796,579Publication dateMar 29, 2005Filing dateMar 1, 2001Priority dateMar 1, 2001Fee statusPaidAlso published asUS7761884, US20030014562, US20050046627Publication number09796579, 796579, US 6874150 B2, US 6874150B2, US-B2-6874150, US6874150 B2, US6874150B2InventorsJeff M. J. NoyleOriginal AssigneeMicrosoft CorporationExport CitationBiBTeX, EndNote, RefManPatent Citations (26), Non-Patent Citations (62), Referenced by (14), Classifications (8), Legal Events (7) External Links: USPTO, USPTO Assignment, EspacenetMethod and system for maintaining connections between surfaces and objects in a graphics display system
US 6874150 B2Abstract
A method and system are provided for controlling the algorithmic elements in 3D graphics systems via an improved 3D graphics API and for managing computing resources utilized in connection with the maintenance of connections between surfaces and objects. When multiple applications are running simultaneously, it is possible that the demand for overall computing resources may exceed supply; and it is possible that a connection between a surface and object may be lost for one or more applications. In accordance with the present invention, a check for the persistence of a connection between surface space and object space is made substantially at the time of a present function call, and thus multiple redundant checks are avoided. In one embodiment, checks made incident to function calls other than a present function call are spoofed or bypassed in order to avoid previous inefficient use of computing resources.
In an exemplary embodiment, the present invention provides a solution by unifying the command structure that previously checked for lost connections to surfaces. Previously, there were innumerable places where the application checked for and handled resource issues between present calls. This distributed the checkpoints and created multiple, if not hundreds or thousands of places throughout the application where checks occurred between present calls, creating inefficiencies and further opportunities for error due to wasteful devotion of computing resources. In accordance with the present invention, each time data is ‘presented’ to the surface memory space 320 according to a ‘present’ function call, the 3D API of the invention checks for these resource contention issues. Thus, instead of having many different cases occurring at different times for which the API might determine that a connection has been lost, the 3 D API of the invention checks each time a ‘present’ function call is made, thereby providing a single case for a lost connection such that resources may be newly allocated according to the same unified procedure. This check may be performed before or after the present call, or included therein. It can be appreciated that any call, such as a present function call, that is cyclical and occurs once per frame e.g., at a typical 30 or 60 frames per second, or other recurring event may also be utilized to achieve the above goals.
[31:29] 0×2
Stream Data Definition (Load): type=FLOAT3; register—4
As mentioned above, while direct video memory access was once a possibility, it is no longer a possibility according to today's currently utilized graphics architectures. In accordance with today's graphics pipeline architecture, specialized or private drivers and surface formats are used in connection with very fast graphics accelerators. With direct rasterizer/processor access to display memory surfaces, “chunks” of surfaces can be moved around according to the specialized surface format, and pulled for processing as efficiency dictates. Thus, the pipeline between display memory surface space and the display itself has been made more efficient. With reference to FIG. 7A, an example of the type of modern ‘chunk’ manipulation is illustrated at a microcosmic level i.e., only 4 squares or chunks of data are illustrated. Private driver 700 causes chunks 710 a —1 through 710 a —4 to be grabbed as efficiency dictates and are subsequently manipulated with a rasterizer into an intermediate form 710 b, wherein the original image may be unrecognizable. Then, data is moved along the graphics pipeline to render the final image on display 710 c, whereby band B—1 of data may translate to band B—2 in the displayed image. These mathematical transformations, and timing thereof, have advanced algorithms for determining the efficiency of chunk grabbing and placement. In essence, many images involve redundant data, or data that can be exploited based upon temporal and spatial knowledge, and these algorithms exploit such knowledge to create an extremely efficient and fast graphics data rendering pipeline.
Without the API of the present invention, however, display memory surface space must be set up properly by the developer to work with this privatized format. FIG. 7B illustrates API 340 in accordance with the present invention. The API object 340 —1 of the present invention hides the efficiencies gained from the privatized driver format and rasterizer operation as described above from applications and developers. As far as the developer D1 writing application 350 a is concerned, the display memory surface 710 a receives a rectangular image that is then rendered upon the display 710 c, when in fact many efficient operations and data manipulations take place behind the scenes. The present invention thus implements API object 340 —1 such that it exposes more of these efficient pipeline operations to the developer D1 so that developer D1 need be less concerned with the performance of hidden operations, such as locking and unlocking the privatized formats pursuant to various commands and function calls over which the developer has no control.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4805098May 5, 1986Feb 14, 1989Mips Computer Systems, Inc.Write bufferUS4953073Feb 6, 1986Aug 28, 1990Mips Computer Systems, Inc.Cup chip having tag comparator and address translation unit on chip and connected to off-chip cache and main memoriesUS4959779Nov 28, 1988Sep 25, 1990Mips Computer Systems, Inc.Dual byte order computer architecture a functional unit for handling data sets with differnt byte ordersUS5027270Oct 11, 1988Jun 25, 1991Mips Computer Systems, Inc.Processor controlled interface with instruction streamingUS5394524 *Nov 30, 1992Feb 28, 1995International Business Machines CorporationMethod and apparatus for processing two graphics data streams in parallelUS5398328Sep 27, 1993Mar 14, 1995Silicon Graphics, Inc.System for obtaining correct byte addresses by XOR-ING 2 LSB bits of byte address with binary 3 to facilitate compatibility between computer architecture having different memory ordersUS5580232May 4, 1995Dec 3, 1996Kobelco Compressors (America), Inc.Rotor assembly having a slip joint in the shaft assemblyUS5590294May 24, 1995Dec 31, 1996Silicon Graphics, Inc.Method and apparatus for retarting pipeline processingUS5673377Sep 2, 1994Sep 30, 1997Ray Dream, Inc.Method and system for displaying a representation of a three-dimensional object with surface features that conform to the surface of the three-dimensional objectUS5801717Apr 25, 1996Sep 1, 1998Microsoft CorporationMethod and system in display device interface for managing surface memoryUS5812136Oct 30, 1996Sep 22, 1998Microsoft CorporationSystem and method for fast rendering of a three dimensional graphical objectUS5822570Oct 30, 1996Oct 13, 1998Microsoft CorporationSystem and method for parsing and executing a single instruction stream using a plurality of tightly coupled parsing and execution unitsUS5844569Apr 25, 1996Dec 1, 1998Microsoft CorporationDisplay device interface including support for generalized flipping of surfacesUS5864703Oct 9, 1997Jan 26, 1999Mips Technologies, Inc.Method for providing extended precision in SIMD vector arithmetic operationsUS5964843Apr 25, 1996Oct 12, 1999Microsoft CorporationSystem for enhancing device driversUS6008816Apr 25, 1996Dec 28, 1999Microsoft CorporationMethod and system for managing color specification using attachable palettes and palettes that refer to other palettesUS6044408 *Apr 25, 1996Mar 28, 2000Microsoft CorporationMultimedia device interface for retrieving and exploiting software and hardware capabilitiesUS6078942 *Apr 25, 1996Jun 20, 2000Microsoft CorporationResource management for multimedia devices in a computerUS6208361 *Jun 15, 1998Mar 27, 2001Silicon Graphics, Inc.Method and system for efficient context switching in a computer graphics systemUS6215495 *May 30, 1997Apr 10, 2001Silicon Graphics, Inc.Platform independent application program interface for interactive 3D scene managementUS6249294 *Aug 21, 1998Jun 19, 2001Hewlett-Packard Company3D graphics in a single logical sreen display using multiple computer systemsUS6252600 *Oct 2, 1998Jun 26, 2001International Business Machines CorporationComputer graphics system with dual FIFO interfaceUS6289396 *Nov 21, 1995Sep 11, 2001Diamond Multimedia Systems, Inc.Dynamic programmable mode switching device driver architectureUS6414688 *Jan 29, 1999Jul 2, 2002Micron Technology, Inc.Programmable graphics memory methodUS6496183 *Jun 30, 1998Dec 17, 2002Koninklijke Philips Electronics N.V.Filter for transforming 3D data in a hardware accelerated rendering architectureUS6525725 *Mar 15, 2000Feb 25, 2003Sun Microsystems, Inc.Morphing decompression in a graphics system* Cited by examinerNon-Patent CitationsReference1Abrash, M., "Inside Xbox Graphics," Dr. Dobb's J., Aug., 2000, 21-22, 24-26.2Antinori, F. et al., "Experience with a 30 cm<2 >silicon pixel plane in CERN experiment WA97," Nucl. Instr. Meth. Phys. Res. A., 1995, 360, 91-97.3Bachstein, W. et al., "Single-Chip erledigt Multimedia," Elektronik, 1996, 17, 58-62.4Bajaj, C. et al., "Making 3D Textures Practical," IEEE: Proceedings-Seventh Pacific Conference on Computer Graphics and Applications, Oct. 5-7, 1999, 259-269.5Bakalash, R. et al., "A Barrel Shift Microsystem for Parallel Processing," in MICRO 23 Microprogramming and Microarchitecture, IEEE: Proceedings of the 23<rd >Annual Workshop and Symposium, Orlando Florida, Nov. 27-29, 1990, 223-229.6Bankston, J. et al., "Pipeline Processing with Modula-2," J. Pascal, Ada, & Modula-2, 1986, 5(5), 46-51.7Biernat, M.J. et al., "Approximate Shaddow Generation," IEEE Montech Conferences, Nov. 9-12, 1987, 97-101.8Brechbühler, Ch. et al., "Parametrization of Closed Surfaces for 3-D Shape Description," Comp. Vision Image Understanding, Mar., 1995, 61(2), 154-170.9Chen, Li, "Generalization Discrete Object Tracking Algorithms and Implementation," in Vision Geometry VI, Proceedings of SPIE, Melter, R.A. et al. (eds.), Jul. 28-29, 1997, 3168, 184-195.10Chiarulli, D.M. et al., "Draft: A Dynamically Reconfigurable Processor for Integer Arithmetic," IEEE: Proceedings-7<th >Symposium on Computer Arithmetic, University of Illinois, Hwang, K. (ed.), Jun. 4-6, 1985, 309-317.11Conference Paper, "A Shading and Compositing Processor based on Crossbar Switches and SRAM Memory," 1999, 4 pages.12Cox, M. et al., "Multi-Level Texture Caching for 3D Graphics Hardware," IEEE: Proceedings-The 25<th >Annual International Symposium on Computer Architecture, Barcelona, Spain, Jun. 27-Jul. 1, 1998, 86-97.13Dietz, P.H. et al., "Simple Networks for Pixel Plane Median Filtering," IEEE Transactions on Circuits and Systems-II: Analog and Digital Signal Processing, Dec., 1993, 40(12), 799-801.14Gomes, J. et al., "Graphical Objects," The Visual Computer, 1996, 12, 269-282.15Gordon, R.L., Ph.D. et al., "Window Management, Graphics, and Operating Systems," Operating Systems Review, Jul., 1987, 21(3), 5-8.16Goris, A. et al., "A Configurable Pixel Cache for Fast Image Generation," IEEE Computer Graphics and Applications, Mar., 1987, 24-32.17Grimes, J. et al., "A New Processor with 3-D Graphics Capabilities," NCGA '89 Conference Proceedings: 10<th >Annual Conference and Exposition Dedicated to Computer Graphics, Philadelphia, Pennsylvania, Apr. 17-20, 1989, vol. 1, 275-284.18Grimes, J. et al., "The Intel i860 64-Bit Processor: A General-Purpose CPU with 3D Graphics Capabilities," IEEE Computer Graphics and Applications, Jul., 1989, 85-94.19Haig, T., "How to program in machine language," Electronics, Aug., 1982, 94-96, 98, 100-103.20Harrison, J.P. et al., "The Role of Microcomputers in Interactive Graphical Planning,"Engin. Software for Microcomputers, Proc., Apr., 1984, 631-641.21Ho, C-H et al., "Efficient Point-Based Rendering Techniques for Haptic Display of Virtual Objects," Presence, Oct., 1999, 8(5), 477-491.22Hoffman, C. et al., "Automatic Surface Generation in Computer Aided Design," supported by the National Science Foundation, Department of Computer Science, Cornell University, Ithaca, New York, Jan., 1985, 1-22.23Hummel, R., "Render Benders: 26 Graphics Cards for Fast 3-D," Byte, Mar., 1998, 112-119.24James, M., "3-D graphics to become accessible to all," Scientific Computing World, Feb., 1997, 41 and 43.25Johnson, S.P., "Direct3D Revealed: Microsoft's 3-D API provides device-independent access to acceleration hardware. Here's how it works," Core Technologies, http://byte.com/art9612/sec5/art4.htm, Dec. 1996, 5 pages.26Jones, M. et al., "High-Performance Graphics Via Silicon Compilation," VLSI Systems Design, Mar., 1987, 32, 33, 36 and 38.27Kaya, E.M., "New Trends in Graphic Display System Architecture," in Frontiers in Computer Graphics, Proceedings of Computer Graphics, Tokyo '84, Kunii, T.L. (ed.), 1985, 310-320.28Kumar, S. et al., "Efficient rendering of trimmed NURBS surfaces," Computer-Aided Disign, Jul., 1995, 27(7), 509-521.29Labsik, U. et al., "Progressive transmission of subdivision surfaces," Computational Geometry, 2000, 15, 25-39.30Lachaud, J.-O. et al., "Continuous Analogs of Digital Boundaries: A Topological Approach to Iso-Surfaces," Graphical Models, 2000, 62, 129-164.31Lapidous, E. et al., "Optimal Depth Buffer for Low-Cost Graphics Hardware," Trident Microsystems, Inc., 1999, 67-73.32Lastra, A. et al., "Real-Time Programmable Shading," Proceedings: 1995 Symposium on Interative 3D Graphics, Monterey, California, Apr. 9-12, 1995, 59-66.33Lee, J-A. et al., "SPARP: a single pass antialiased rasterization processor," Comput. & Graphics, 2000, 24, 233-243.34Lichten, L., "A Solution to Surface Connectivity Problems in Computer-Aided Design," Computer Graphics, Mar., 1981, 14(4), 168-199.35Mabin, F.H. et al., "A Parallel Algorithm to Reconstruct Bounding Surfaces in 3D Images," J. Supercomputing, 1998, 12, 137-155.36McManus, D. et al., "Optimal Static 2-Dimensional Screen Subdivision for Parallel Rasterization Architectures," Comput. & Graphics, 1997, 21(2), 159-169.37Meyers, D. et al., "Surfaces from Contours," ACM Transactions on Graphics, Jul. 1992, 11(3), 228-258.38Micikevicius, P. et al., "Teaching a Computer Graphics Class Using DirectX," J. Comput. in Small Colleges; Proceedings of the Ninth Annual CCSC South Central Conference, (Jackson, Mississippi, Apr. 17-18), Meinke, J.G. (ed.), Mar., 1998, 13(4), 61-66.39Nishimura, H. et al., "A Multicomputer System Links: Its Architecture and Graphics Applications," IECON '84: International Conference on Industrial Electronics, Control and Instrumentation, Tokyo, Japan, Oct. 22-26, 1984, 1, 270-274.40NVIDIA Corporation, "System Platform Porcessor (SPP) / Integrated Graphics Processor (IGP): Redefining System and Graphics Performance," nForce SPP/IGP Product Overview, Jan., 2002, Version 1, 2 pages.41NVIDIA Corporation, "Technical Brief: NVIDIA nfiniteFX II Engine From Research to Real Time," Jan. 16, 2002, 7 pages.42NVIDIA Corporation, "Technical Brief: NVIDIA nForce Platform Processing Architecture," 2001, 1-9.43Ohbuchi, R. et al., "Embedding Data in 3D Models," in Interactive Distributed Multimedia Systems and Telecommunication Services, 4<th >International Workshop, IDMS '97, Darmstadt, Germany, Sep. 10-12, 1997, 1-10.44Ohhashi, M. et al., "A 32b 3-D Graphic Processor Chip with 10M Pixels/s Gouraud Shading," 1988 IEEE International Solid-State Circuits Conference Digest of Technical Papers, Feb., 1988, 168-169 and 352.45Rowlan, J.S. et al., "A distributed, parallel, interactive volume rendering package," IEEE: Proceedings-Visualization '94, Washington, D.C., Oct. 17-21, 1994, 21-30.46Schneider, B-O. et al., "An adaptive framework for 3D graphics over networks," Comput. & Graphics, 1999, 23, 867-874.47Schneider, B-O. et al., "M-Buffer: A Flexible MISD Architecture for Advanced Graphics," Comput. & Graphics, 1995, 19(2), 239-246.48Senthinathan, R. et al., "A 650-MHz, IA-32 Microprocessor with Enhanced Data Streaming for Graphics and Video," IEEE J. Solid-State Circuits, Nov., 1999, 34(11), 1454-1465.49Shinya, M., "Improvements on the Pixel-tracing Filter: Reflection/Refraction, Shadows, and Jittering," Proceedings: Graphics Interface '95, May 7-19, 1995, 92-102.50Shirali, N.S. et al., "A Parallel Architecture Graphics Processor," IEEE Southeastcon: Conference Proceedings, Knoxville, Tennessee, Apr. 11-13, 1998, 108-111.51Smith, D.R. et al., "A Circuit-Switched Shared-Memory Multiprocessor," International J. Mini Microcomputers, 1995, 17(3), 108-118.52Sussman, H. et al., "Graphics Memory Architectures," Wescon/86 Conference Record, 1986, 1-6.53Swanson, R.W. et al., "A Fast Shaded-Polygon Rendered," Computer Graphics, Aug., 1986, 20(4), 95-101.54Teonnies, K.D. et al., "Volume rendering for interactive 3-d segmentation," in Image Display, Proceeding of SPIE, Newport Beach, California, Feb. 23-25, 1997, 3031, 602-609.55Thompson, T., "An inside look at the most popular 3-D environments: OpenGL, QuickDraw 3D, and Direct3D," Must-See 3-D Engines, Jun., 1996, http://byte.com/art/9606/sec11/art4.htm, 7 pages.56Thompson, T., "Direct3D's Engine," Must-See 3-D Engines, Jun., 1996, http://byte.com/art/9606/sec11/art7.htm, 1 page.57Thompson, T., "Open GL's Command Structure," Must-See 3-D Engines, Jun., 1996, http://byte.com/art/9606/sec11/art5.htm, 1 page.58Thompson, T., "QuickDraw 3D's Command Structure," Must-See 3-D Engines, Jun., 1996, http://byte.com/art/9606/sec11/art6.htm, 1 page.59Thompson, T., "Three Ways to Tackle Multithreading," Must-See 3-D Engines, Jun., 1996, http://byte.com/art/9606/sec11/art8.htm, 1 page.60Wilson, J.L. et al., "Designing a Graphics Application Interface," Proceedings Graphics Interface '85, Montreal, Quebec, May 27-31, 1985, 373-380.61Yoshida, M. et al., "Trend of the computer graphics hardware," Information Processing Soc. of Japan, Oct., 1988, 29(10), 1109-1115.62Zheng, Y. et al., "Three-dimensional unstructed mesh generation: Part 2. Surface meshes," Comput. Methods Appl. Mech. Engrg., 1996, 134, 269-284.Referenced byCiting PatentFiling datePublication dateApplicantTitleUS7525544 *Apr 16, 2004Apr 28, 2009Research In Motion LimitedSystem and method of converting edge record based graphics to polygon based graphicsUS7884817Sep 2, 2004Feb 8, 2011Microsoft CorporationMethod and system for defining and controlling algorithmic elements in a graphics display systemUS7965288Oct 22, 2009Jun 21, 2011Microsoft CorporationMethod and system for defining and controlling algorithmic elements in a graphics display systemUS7999805Mar 13, 2009Aug 16, 2011Research In Motion LimitedSystem and method of converting edge record based graphics to polygon based graphicsUS8194070Jul 11, 2011Jun 5, 2012Research In Motion LimitedSystem and method of converting edge record based graphics to polygon based graphicsUS8432407Jul 30, 2009Apr 30, 2013Microsoft CorporationMethod and system for managing graphics objects in a graphics display systemUS20040208370 *Apr 16, 2004Oct 21, 2004Ken WhatmoughSystem and method of converting edge record based graphics to polygon based graphicsUS20050027682 *Sep 2, 2004Feb 3, 2005Microsoft CorporationMethod and system for defining and controlling algorithmic elements in a graphics display systemUS20070011617 *Dec 1, 2005Jan 11, 2007Mitsunori AkagawaThree-dimensional graphical user interfaceUS20070156664 *Mar 9, 2007Jul 5, 2007Gemini Mobile Technologies, Inc.Automatic user matching in an online environmentUS20070162862 *Mar 9, 2007Jul 12, 2007Gemini Mobile Technologies, Inc.Selective user monitoring in an online environmentUS20090167765 *Mar 13, 2009Jul 2, 2009Research In Motion LimitedSystem and method of converting edge record based graphics to polygon based graphicsUS20100020071 *Jul 30, 2009Jan 28, 2010Microsoft CorporationMethod and system for managing graphics objects in a graphics display systemUS20100039430 *Oct 22, 2009Feb 18, 2010Microsoft CorporationMethod and system for defining and controlling algorithmic elements in a graphics display system* Cited by examinerClassifications U.S. Classification719/328, 345/419International ClassificationG06T15/00, G06F3/00, G06F9/46Cooperative ClassificationG06F9/445, G06T15/00European ClassificationG06T15/00Legal EventsDateCodeEventDescriptionApr 19, 2001ASAssignmentOwner name: MICROSOFT CORPORATION, WASHINGTONFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:BOYD, CHARLES N.;TOELLE, MICHAEL A.;REEL/FRAME:011743/0859Effective date: 20010227Apr 20, 2001ASAssignmentOwner name: MICROSOFT CORPORATION, WASHINGTONFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:NOYLE, JEFF M.;REEL/FRAME:011741/0073Effective date: 20010227Nov 24, 2004ASAssignmentOwner name: MICROSOFT CORPORATION, WASHINGTONFree format text: CORRECTIVE ASSIGNMENT TO CORRECT SERIAL 09/95579 NUMBER SHOULD BE 09/796,579. PREVIOUSLY RECORDED ON REEL 012064 FRAME 0557;ASSIGNOR:NOYLE, JEFF M. J.;REEL/FRAME:015407/0932Effective date: 20010227Sep 22, 2008FPAYFee paymentYear of fee payment: 4Aug 28, 2012FPAYFee paymentYear of fee payment: 8Dec 9, 2014ASAssignmentOwner name: MICROSOFT TECHNOLOGY LICENSING, LLC, WASHINGTONFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:MICROSOFT CORPORATION;REEL/FRAME:034541/0001Effective date: 20141014Sep 15, 2016FPAYFee paymentYear of fee payment: 12RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services