United States Patent
`
`[19]
`
`[11] Patent Number:
`
`5,777,621
`
`Schneider et a].
`[45] Date of Patent: Jul. 7, 1998
`
`
`
`USOOS777621A
`
`[54] QUALITY CONTROL MECHANISM FOR
`THREE-DIMENSIONAL GRAPHICS
`RENDERING
`
`[75]
`
`Inventors: Philip J. Schneider: David Jenni.
`both of Boulder Creek. Calif.
`
`[73] Assignee: Apple Computer. Inc. Cupenino.
`Calif.
`
`[21] Appl. No: 482.016
`
`[22] Filed:
`
`Jun. 7. 1995
`
`Related US. Application Data
`
`[63] Continuation-impart of See. No. 362,118. Dis; 22. 1994,
`abandoned.
`
`Int. Cl.“ ........................................... GOCT 15M
`[51]
`[52] US. CL .. ...........
`3451428: 345L129
`
`[58] Field of Search .................................. 3951119. 120.
`393123. 124. 126. 128. 129. 130. 131.
`132. 133. 15213459121. 122. 132. 133.
`136
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`15,043,922
`5,379,371
`5,384,903
`5.448.686
`5,471,572
`5.489.920
`5.555.354
`
`8.1199! mm .......................... 3951122
`
`..... 3951128
`”1995 Usamietal.
`.....
`
`”1995 Mackinlay ......
`.
`.. 395(152
`..... 3951120
`9i’l995 Bone] et al.
`
`
`. 3951139
`1131995 Buchneretal.
`
`211996 Kaasila ............._
`. 3451136
`.................. 3951127
`9f1996 Smmick et. al.
`
`OTHER PUBLICATIONS
`
`Nakamura. fibres—dimensional delineation of map and
`facility data and data control". Functional Diagram Work-
`shop ‘93. Oct. 1993. pp. 1-6.
`
`Ihm et 31.. “On enhancing the speed of splarting with
`indexing“. Wsualjzation. 1995 Conference. pp. 69—76.
`Salsas et 31.. “interactive visualization of large scalar voxez
`fields”. Visualization. 1992 Conference. pp. 29—36.
`Aslheimer. P.. et .11.. “Interactive modeling in high—perfor-
`mance
`scientific visualization—the vis—a—vis project“.
`Computers in Industry. vol. 19. No. 2. May 1992. pp.
`213—225.
`
`IBM. “Multiple Types of Graphical Contexts on a Graphics
`Adapter". Technical disclosure Bulletin. vol. 34. No. TB.
`Dec. 1991. pp. 29-30.
`
`{List continued on next page.)
`
`Primary Examiner—Joseph H. Feild
`Assistant Examiner—Stephen Hong
`Attorney. Agent, or Firm—Fliesler. Dubb. Meyer & Lovejoy
`
`[57]
`
`ABSTRACT
`
`A graphics rendering system includes a continuum. or
`collection. of quality control data groups. each of which
`contains a plurality of quality control type variables. Each of
`the type variables contains a value which selects among a
`pltnality of options in a respective trade-oil between ren-
`dering quality and rendering speed. Each of the quality
`control data groups may be associated with the respective
`quality index. Thus. an application program can select a
`point on the overall rendering speedlquality rendering trade-
`ofi. merely by selecting a quality control
`index value.
`Moreover. the application program can mice the current
`quality control index accessible to a user. for example in
`such an intuitive form as an iconic “quality knob“. The
`mechanism permits the user to have fine control over the
`rendering speedlqualjty rendering trade-011’. without being
`concerned with adjustments to the individual rendering
`parameters.
`
`22 Claims. 11 Drawing Sheets
`
`
`
`MS 1019
`
`MS 1019
`
`1
`
`

`

`5,777,621
`Page 2
`__‘——______.—.__—_...———————-
`
`OTHER PUBLICATIONS
`
`Apple Computer. Inc. “QuickDraw (EX—Programmer’s
`Overview" (1994). *1.
`Bergman. et al.. “Image Rendering by Adaptive Refine-
`ment“. Computer Graphics (1986) vol. 20. No. 4. pp. 29—37.
`*1.
`Catmuii. Edwin E. “A Subdivision Algorithm for Computer
`Display of Curved Stn'faees". (Dec. 1974). Ph.D. Thesis.
`Report UfEC—CSo—74—133. Computer Science Depart-
`ment. University of Utah. Salt Lake City. UT. *1.
`(It-ten. Shenchang Eric. et al.. “A Progressive Mold-Pass
`Method for Global illumination." Computer (traphics (Jul.
`1991). vol. 25. No. 4. pp. 165—174. *1.
`Clark. James 11.. "The Geometry Engine: AVLSI Geometry
`System for Graphics." Computa Graphics (1982). vol. 16.
`No. 3. pp. 127—133. *1.
`Haeberli. Paul and Akeley. Kurt. "The Accumulation Buffer:
`Hardware Support for High-Quality Rendering”. Computer
`Graphics (Aug. 1990). vol. 24. No. 4. pp. 309—318. I‘1.
`International Standards Organization. “Information Process-
`ing Systems—Computer Graphics—Graphical Kernel Sys~
`tern for Three Dimensions (GKS—3D) Functional Descrip-
`tion“. (1988) ISO Document No. 8805:1988 (E). *1.
`Kelley. Michael. et al.. “A Scalable Hardware Render Accel-
`erator using a Modified Scanline Algm‘thm.” Computer
`(kaphics (Jul. 1992). vol. 26 No. 2. pp. 241-248. *1.
`Maillot. Patrick-Gilles. "flame—Dimensional Homogeneous
`Clipping of Triangle Strips.” Academic Press. Inc. (1991).
`pp. 219-231. *1.
`Newell. M. E. et al.. “A Solution to the Hidden Surface
`Problem.” Proceedings of the ACM National Conference
`(1972). pp. 443—450. ‘1.
`Pl-HGS Committee. Andries van Dam. (mailman. “PHIGS+
`Functional Description. Revision 3.0." Computer Graphics
`(1988). vol. 22 No. 3. pp. 125418. *1.
`Pixar. "I‘he RenderMan® Interface”. Specification. Version
`3.1 (Sep. 1989). *1.
`
`Potmesil. Michael and l-Ioffert. Eric M" “FRAMES: Soft~
`were Tools for Modeling. Rendering and Animation of 3!)
`Scenes”. Computer Graphics. (Jul. 1937). vol. 21. No. 4. pp.
`85—93. *1.
`Saito. Takafumi. et al.. ‘Comprehensible Rendering of 3—D
`Shapes". Computer Graphics (Aug. 1990). vol. 24. No. 4.
`pp. 197—206. *1.
`Segal. Mark. et 211.. “Fast Shadows and Lighting Efiects
`Using Texture Mapping“. Computer Graphics (Jul. 1992).
`pp. 249—252. *1.
`SiJlion. Francois. et al.. “A General TWO—Pass Method
`Integrating Specular and Diffuse Reflection”. Computer
`Graphics. (Jul. 1989). vol. 23. No. 3. pp. 335—344. *1.
`Snibbe. Scott 8.. et al.. “Using Deformations to Explore 313
`Widget Design“. Computer Graphics. (Jul. 1992). vol. 26.
`No. 2. pp. 351—352. *1.
`Strauss. Paul S.. et 3].. “An Object—Oriented 3D Graphics
`Toolkit“. Computer Graphics. (Jul. 1992). pp. 341—349. *1.
`Tarlton. Mark A.. et al.. “A Framework for Dynamic Visual
`Applications.” hooeedings of the 1992 Symposium on
`Interactive 3D Graphics (1992). pp. 161-164. *1.
`Turkowski. Ken. “Design Considerations for an ObjectrO-
`riented 13D Graphics] Metallic.” Proceedings of the Third
`Eurographics Workshop on Object—(Striated Graphics (Oct.
`1992). pp. 163—169. *1.
`Venolia. Dan. “Facile 3D Direct Manipulation". Proceedings
`of INTERCHI ’93 (May 1993). pp. 31-35. *1.
`Wanger. Leonard. "Ihe Efiect of Shadow Quality on the
`Perception of Spatial Relationships in Computer Generate
`Imagery". Proceedings of the 1992 Symposium on Interac—
`tive 3D Graphics (1992). pp. 39—42. *1.
`Werneclte. Josie. "I‘he Inventor Mentor—Hogramming
`Object-(kicmod
`3D Graphics with Openlnventotn‘.
`Release 2". Addison-Wesley Publishing Company (1994).
`pp. 3—77. 99—136. 211—249. 421—470 and 479-486. *1.
`X Consortium. “PEX Protocol Specification”. Version 5.2—
`Public Review Draft (15 Aug. 1994). *1.
`
`2
`
`

`

`US. Patent
`
`Jul. 7, 1998
`
`Sheet 1 of 11
`
`5,777,621
`
`1&2
`
`103
`
`a
`GRAPHICS
`ACCELERATORI
`h—u—u—u——T—— n..— n- n-
`
`106
`
`
`
`
`RENDERER 3 £06
`
`RENDERER 1
`
`
`RENDERER 2
`
` ESCHER
`PROCEDURES
`
`
`
`215
`
`
`
`
`RENDERER
`QUALITY
`RENDERER
`new
`
`
`
`
`
`INVOCATION
`mmmnon
`BUILDING/
`CONTROL
`BUILDING/
`
`
`
`
`
`
`PROCEDURES WW3"
`EDITING
`PRomEs
`EDITING
`
`
`
`
`
`
`PROCEDURES
`PHIEUMES
`PROCEDURES
`
`
`
`
`
`'rlll
`
`
`
`3
`
`

`

`US. Patent
`
`Jul. 7, 1998
`
`Sheet 2 of 11
`
`5,777,621
`
`INSTALL
`
`RENDERER(S)
`
`BUILD
`
`QUALITY
`COLLECTION
`
`302
`
`303
`
`304
`
`305
`
`
`
`RENDER
`MODEL(S) T0
`VII-3V6)
`
`303
`
`308
`
`
`
`
`SPECIFYING MODEL 3 AND VIBN 1
`
`45?
`
`404
`
`405
`
`493
`
`CALL RENDERER INVOCATION PROCEDURE
`SPECIFY MODEL'IAND VIBN 1
`
`CALL RENDERER INVOCATION PROCEDURE
`SPECIFYING MODEL 1 AND VIEW 2
`
`CALL RENDERER INVOCATION PROCEDURE
`SPECIFYING MODEL 2 AND VIBN 1
`
`CALL RENDERER INVOCATION PROCEDURE
`SPECIFYING MODEL 2 AND VIEw 2
`
`410
`
`CALL RENDERER INVOCATION PROCEDURE
`
`FIG. 3
`
`FIG. 4
`
`4
`
`

`

`US. Patent
`
`Jul. 7, 1993
`
`Sheet 3 of 11
`
`5,777,621
`
`512\
`
`INSTANCE 1
`DATA
`
`METHODS
`
`/ 502
`
`OBJECT
`METHODS
`
`504
`
`SHARED OBJECT
`
`505
`
`RENDERER
`OBJECT
`METHODS
`
`T i
`
`.
`
`
`DISPOSE
`DUPLICATE
`
`UNREGISTER
`
`OBJECT CLASS
`
`REFERENCE
`
`OBJECT
`DATA
`
`534
`
`SHARED
`OBJECT
`DATA
`
`535
`
`RENDERER
`OBJECT
`DATA
`518
`
`WFRBMERBR
`DATA
`
`
`
`
`
`
`INSTANCE 2
`DATA
`
`REFERENCE
`
`F16. 5
`
`5
`
`

`

`US. Patent
`
`Jul. 7, 1993
`
`Sheet 4 of 11
`
`5,777,621
`
`EtStyleDbject
`
`Backfucingstyle
`
`
`
`F16. 5
`
`Rotat
`
`e
`
`EtTransformObject
`
`Scale
`
`EtCumeroObject
`
`EtLightObject
`
`Translate
`
`Line
`
`P0 int
`
`EtGeometryObject
`
`Polygon
`
`EtShupeObject
`
`Po lyLine
`
`Torus
`
`Triangle
`
`EtLightGroup
`
`EtcrouDObject___{EEE EtInfoGroup
` EtShaderObject
`
`EtDispluyGrOUp
`
`EtOrderedGroup
`
`EtLIstGroup
`
`EtRendererOb ject —[
`EtSetObject
`
`ZBuffer
`
`_
`WIFeFrome
`
`EtDruwContext
`
`EtViewObject
`
`EtQuthndihctionObject
`
`EtQuathGroupObject
`
`EtShuredObject
`
`
`
`
`EtObject
`
`6
`
`

`

`US. Patent
`
`Jul. 7, 1998
`
`Sheet 5 of 11
`
`5,777,621
`
`E W iewObject
`Instance
`
`/7M
`
`E W iewObject
`C iass
`
`704
`
`712
`
`/-702
`
`OBJECT
`DATA
`
`714
`
`333%?
`DATA
`
`716'
`
`V IEW
`OBJECT
`
`DATA
`
`OBJECT CLASS
`
`OBJECT
`METHODS
`
`REFERENCE
`COUNT
`
`
`SHARED OBJECT
`METHODS
`
`EtViewPrivate
`
`706
`
`
`
`
`FIG. 7
`
`8‘02
`
`EtD Esp luyGroupOb ject
`
`
`
`
`EtGeometryObject
`
`E tD isp IayG roupOb ject
`
`EtGeometryObject
`
`FIG. 8
`
`7
`
`

`

`US. Patent
`
`Jul. 7, 1998
`
`Sheet 6 of 11
`
`5,777,621
`
`group
`
`[/1904
`
`Ordered Display
`Group Class
`
`//-902
`
`OBJECT CLASS
`
`REFERENCE
`COUNT
`
`
`
`
`(none)
`
`OBJECT
`METHODS
`9&8
`
`SHARED OBJECT
`
`METHODS
`
`310
`
`SHAPE OBJECT
`EtShapeClass METHODS
`
`3L?
`
`GROUP OBJECT
`EtGroupCloss METHODS
`
`
`
`£EW
`OBJECT
`DATA
`
`
`sag
`SHARED
`OBJECT
`DATA
`924
`SHAPE OBJECT
`DATA
`
`
`
`
`BB5
`
`
`
`GROUP OBJECT
`DATA
`
`3&9
`DISPLAY GROUP
`OBJECT
`DATA
`
`
`
`WEBEDDEPUN
`GROUP OBJECT
`DATA
`
`EBB
`
`
`
`
`
`
`
`
`IIIIIIHHHH!IIIIII
`
`
`
`
`EtDispIay—
`GroupPrivote
`
`
`
`E10 isp loy—
`GraupClass
`
`914
`DISPLAY GROUP
`METHODS
`
`9L5
`
`EtOrderedDiSplay—
`GroupPrivate
`
`SubGroup
`
`ifx-SWS
`
`OBJECT
`DATA
`
`SHARED
`OBJECT
`DATA
`
`SHAPE OBJECT
`DATA
`
`GROUP OBJECT
`DATA
`
`DISPLAY GROUP
`OBJECT
`DATA
`
`BEBEDDHTUW
`GROUP OBJECT
`DATA
`
`
`
`
`
`
`
`OBJECT CLASS
`
`REFERENCE
`
`COUNT
`
`IlllllHUUH!lllll|
`
`EtDisplay—
`GroupPrivute
`
`EtOrderedDisplay-
`GroupPrivate
`
`
`
`
`
`
`
`FIG.
`
`.9
`
`8
`
`

`

`US. Patent
`
`Jul. 7, 1993
`
`Sheet 7 of 11
`
`5,777,621
`
`1' 002
`
`1008
`
`Leaf class's 'Nelv' procedure calls its
`parent class 'Nen' procedure with:
`
`
`
`
`
`
`
`
`
`(a) the static variable which. when the
`leaf class was registered. points to the
`top of that
`leaf class's method table
`
` & (h)
`data structure
`
`the size of the leaf class's Private
`
`1004
`
`Each higher class's 'lleu’ procedure calls
`its respective parent class’s 'Nevr’
`procedure lwith:
`
`(a) the object class pointer passsed to it
`
`
`
`
`
`
`
`the size needed by all descendent
`and (b)
`classes so for plus the size needed by the
`current class's private data structure
`
`
`
`
`
`
`
`
`
`Each loner class's 'Nev' procedure then:
` (a) calls its own Get procedure to get a
`
`
`
`
`
`pointer to the current class's avn private
`data structure within the newly allocated
`instance data to lock;
`
`(b)
`
`initializes its own Private data
`structure;
`
`and (c) returns to its caller (which is the
`next
`lover ctoss’s 'Nerv' procedure).
`returning a pointer to the newly allocated
`memory b lock.
`
`
`
`
`
`The Leaf class’s 'Nerr' procedure does
`the same. except
`the caller is typically
`
`the application program.
`
`
`
`
`
`
`
`
`
`1 005
`
`
`Ultimate parent class's 'Neu' procedure
`(EtObjecLNewO):
`
`
`
`
`
`
`
`initializes its arm Private data
`(h)
`structure (by writing the Object Class
`
`pointer passed to it
`into the top at the
`
`newly allocated memory black):
` and (c) returns to its caller (vhich is the
`next
`lower class's 'New’ procedure),
`returning a pointer to the newly allocated
`memory black
`
`
`
`(a) allocates memory space for the
`private data structures needed for its mm
`Private data
`toe the Private data for all
`descendent c asses. This space will
`contain the entire block of instance data
`for
`the nevrly created object.
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 10
`
`9
`
`

`

`US. Patent
`
`Jul. 7, 1993
`
`Sheet 8 of 11
`
`5,777,621
`
`1110
`
`1102
`
`1104
`
`OBJECT CLASS
`
`EtOuaIitygollectionObject [
`EtQualityCollectiorDbject [
`Instance
`lass
`
`
`OBJECT
`MEN-DDS
`
`“05
`
`
`SHARED
`OBJECT
`METHODS
`
`REFERENCE
`COUNT
`
`EtQua IityCo llectionPr ivute
`
`
`
`
`
`1112
`
`
`OBJECT
`DATA
`
`
`
`
`1114
`
`SHARED
`OBJECT
`DATA
`
`1116
`
`colflgfigg
`OBJECT
`DATA
`
`FIG. fl
`
`1210
`
`Ethan IityG roupObject
`EtQualityGroupObject /
`C lass
`
`
`
`
`Instance
`1212
`
`OBJECT
`
`DATA
`OBJECT cuss
`12”
`SHARED
`OBJECT
`DATA
`
`SBJECE
`“"00
`SfiD
`OBJECT
`
`
`
`
`REFERENCE
`COUNT
`
`EtOualityGroupObjectPrivate
`
`QUALITY
`GROUP
`OBJE$TDA A
`
`1216'
`
`FIG. 12
`
`10
`
`10
`
`

`

`US. Patent
`
`Jul. 7, 1998
`
`Sheet 9 of 11
`
`5,777,621
`
`1302
`
`ExSetupQUO lityCO | lection
`
`'
`
`CREATE A NEW QUELI'TY
`COLLECTION OBJ C
`
` CREATE FIRST NEW QUALITY
`
`GROUP OBJECT USING
`INDEX=02
`
`SET PARAMETERS IN FIRST
`QUALITY GROUP OBJECT
`
`1315
`CREATE THIRD NEW QUALITY
`GROUP OBJECT USING INDEX=0.6
`
`1313
`
`SET PARAMETERS IN THIRD
`QUALITY GROUP OBJECT
`
`1330
`
`ADD THIRD QUALITY GROUP
`OBJECT T0 QUALITY COLLECTION
`OBJECT
`
`
`
`2132
`
`CREATE FOURTH NEW QUALITY
`GROUP OBJECT USING INDEX=O.B
`4
`13?
`
`SET PARAMETERS IN FOURTH
`QUALITY GROUP OBJECT
`
`1304
`
`1305
`
`1303
`
`13”
`
`1312
`
`1314
`
`
`
`
`ADD FIRST QUALITY GROUP
`OBJECT TO QUALITY
`COLLECTION OBJECT
`
`CREATE SECOND NEW QUALITY
`GROUP OBJECT USING
`INOEx=o.4
`
`SET PARAMETERS IN SEOONO
`QUALITY GROUP OBJECT
`
`1335
`
`OBJECT
`
`ADD SECOND QUALITY GROUP
`OBJECT TO QUALITY
`COLLECTION OBJECT
`
`1323
`
`ADO FOURTH QUALITY GROUP
`OBJECT T0 QUALITY COLLECTION
`
`F16. 13
`
`11
`
`11
`
`

`

`US. Patent
`
`Jul. 7, 1993
`
`Sheet 10 of 11
`
`5,777,621
`
`
`
`ExGetDesired Quufity Index()
`
`
`
`
`
`
` DISPLAY
`QUALITY KNOB
`ICON
`
`14E?
`
`ACCEPT USER
`
`SELECTION
`
`1404
`
`
`
`RETURN DESIRED
`
`QUALITY INDEX
`
`1405
`
`
`
`FIG. 14
`
`
`
`FIG. 15
`
`12
`
`12
`
`

`

`US. Patent
`
`Jul. 7, 1993
`
`Sheet 11 of 11
`
`5,777,621
`
` ErRT_Geometry_,Tr iang Ie
`
`GET VIEW '5
`QUALITY GROUP
`
`GET
`
`-'504
`
`
`
` COMPUTE
`
`
`
`SHADOWS
`
`
`COMPUTE
`
`SHADOWS
`
`
`
`
`
`RENDER TRIANGLE
`RENOER TRIANGLE
`RENDER TRIANGLE
`RENDER TRIANGLE
`
`
`
`USING RAY DEPTH. USING RAY DEPTH. USING RAY DEPTH. USING RAY DEPTH,
`
`
`
`
`
`N0 SHADOWS. N0
`REFLECTIONS a:
`REFLECTIONS, N0
`SHADOWS. N0
`
`
`
`
`REFLECTIONS
`SHADOWS
`SHADOWS
`REFLECTIONS
`
`
`1516‘ 1618
`
`FIG. 16'
`
`13
`
`13
`
`

`

`5,777.62]
`
`1
`
`QUALITY CONTROL MECHANISM FOR
`THREE-DMNSIONAL GRAPHICS
`RENDERING
`
`CROSS—REFERENCE TO RELATED
`APPLICATIONS
`
`This application is a continuation-in-part of US. patent
`application SCJ'Ser. No. 083152.118. filed Dec. 22. 1994.
`abandoned. entitled MECHANISM FOR W-
`ING SCALABLE AND EX'I'ENSIBLE GRAPHICS
`RENDERING. by inventor David levans. assigned to the
`assignee of the present application and incorporated herein
`by reference.
`
`LIMITED COPYRIGHT WAIVER
`
`A portion of the disclosure of this patent document
`centains material to which the claim of copyright protection
`is made. The copyright owner has no objection to the
`facsimile reproduction by any person of the patent document
`or the patent disclosure. as it appears in the U.S. Patent and
`Trademark Oflice file or records. but reserves all other rights
`whatsoever.
`
`BACKGROUND
`
`1. Field of the Invention
`
`The invention relates to graphics rendering systems. and
`more particularly. to software tools for assisting graphics
`application developers.
`2. Description of Related Art
`Graphics rendering is the process of computing a two-
`dimensional
`image (or part of an irnage) from three-
`dimensional geometric forms. An object is considered herein
`to be three-dimensional if its points are specified with at
`least three coordinates each (whether or not the object has
`any thickness in all three dimensions). A tenderer is a tool
`which performs graphics rendering operations inresponse to
`calls thereto. Some renderers are exclusively software. some
`are exclusively hardware. and some are implemented using
`a combination of both (e.g. software with hardware assist or
`acceleration). Renderers typically render scenes into a bufier
`which is subsequently output to the graphical output device.
`but it is possible for some renderers to write their two-
`dlmensional output directly to the output device. A graphics
`rendering system (or subsystem). as used herein. refers to all
`of the levels of processing between an application program
`and a graphical output device. In many prior art systems. the
`graphics rendering system is coextensive with the tenderer.
`that is. the tenderer is called directly by the application
`program without any intervening layers of processing.
`Graphics rendering systems typically feature an immedi-
`ate mode interface or it retained mode inta'face to the
`application program. An immediate mode interface is a truly
`procedural interface in which the application program speci-
`fies each geometric primitive to the graphics rendering
`system every time the image is to be rendered. The rendering
`system does not maintain a model database from scene-to-
`scene. although the application program may do so. Imme—
`diate mode interfaces are highly attractive for rendering
`scenes where the model is changing at each frame. such as
`for visualization of simulations. previewing of animation
`sequences. or reading a series of models from a file. On the
`other hand. an immediate mode interface requires that the
`entire scene he nansmitted via procedure tails to the ren-
`derer at each frame. resulting in high data bandwidth
`between application program and renderer. Also. the file
`
`10
`
`15
`
`35
`
`45
`
`55
`
`2
`format for a model is often simply a stream of drawing
`commands rather than the model itself. restricting its use-
`fulness as a data interchange format. Immediate mode
`interfaces are also less conducive to providing toolkit mod-
`eling functionality to the application program. and they
`usually preclude a user interface toolkit that operates on
`obfias in the scene.
`In a retained mode system. sometimes called a display list
`system. the graphics rendering system maintains a database
`representation of the three dimensional model. At each
`frame. the rendering system traverses the retained model
`database and draws it. This can be instigated by a single call
`by the application program to the graphic; rendering system.
`instead of a stream of drawing calls describing the entire
`scene. When the model changes. the application program
`edits or updates the model database and again asks the
`rendering system to render the scene. The benefits of a
`retained mode system include reduced bandwidth between
`the application program and any hardware accelerator. The
`file format of the model database also can be used easily as
`a data interchange format since it is not merely a list of
`procedure calls. The existence of an object database also
`provides an additional way of implementing a user interface
`toolkit and modeling functionality. Retained mode renderers
`can also cache rendering information and can also cache
`information for optimization of scene traversal. 0n the other
`hand. retained mode rendering systems have a higher oven
`head for editing the scene database. and they restrict appli-
`cation program design by forcing the scene into a system-
`defined data structure. usually a hierarchy. thus requiring
`many application programs to maintain a duplicate copy of
`the model in their own format.
`
`In Mark A. Tarlton and P. Nong Tarlton. "A Framework
`for Dynamic Visual Applications.” Proceedings of the 1992
`Symposium on Interactive 3!) Graphics. Cambridge. Mass.
`1992. pp. 161—164. incorporated by reference herein. there
`is described a retained mode rendering system which imple—
`ments a general purpose database system to organize the
`model rather than forcing the model to reside in a single
`system hierarchy. Such a technique attempts to provide the
`benefits of the retained mode system without the drawbacks.
`The following list describes some of the graphics reada-
`ing systems which. are currently available.
`GL7“. Silicon Graphics‘ GL is an irnrncdiate mode ren-
`derer used primarily for interactive graphics. 61..
`is
`described in “Graphics Library Programming Guide.” Sili-
`con Graphics Computer Systems. 1991. incorporated by
`reference herein. It was designed as an interface to Silicon
`Graphics IRIS rendering hardware and does not provide a
`file format. hard copy output. modeling capability. or user
`interface tools. 61.. supports simple display lists which are
`essentially mauos for a sequence of GI. commands. The GL
`routines perform rendering operations by issuing commands
`to the IRIS hardware.
`StarBaseT“. Hewlett-Packard's StarBase is an immediate
`mode system that is very similar to GL. sharing most of its
`{wines and disadvantages. StarBase is described in "Star-
`base Graphics Techniques. Hewlett-Packard Company."
`l99l. incorpa'ated by reference herein. Numerous device
`drivers are available for StarBase for outputting the rendered
`(to. two-dimensional) scene on difl‘erent graphics output
`devices ranging from plotters to high~end 3-D graphics work
`stations.
`
`is an immediate
`RenderManT“. Renda'Man. by Pixar.
`mode system designed primarily to support high quality
`rendering. RenderMan is described in Steve Upstill. "The
`
`14
`
`14
`
`

`

`5.777.621
`
`3
`RenderMan Companion.” Addison-Wesley. Reading. Mass.
`1990. incorporated by reference herein. As described in
`Tony Apodaca. ‘RenderMan Interface Specification Version
`4.0 Beta.” January. 1992. incorporated by reference herein.
`recent versions of the RenderMan specification provide new
`routines that bracket the existing RenderMan calls and allow
`difierent renderers to be used The tenderer is specified with
`a single call prior to rendering the scene. and it aflects the
`entire scene. See also Pixar. “Quick RenderMan Interface
`and Implementation Specification.“ 1992.
`incorporated
`herein by reference.
`PHIGS. PHIGS is described in PHIGS Committee. A. van
`Dam. chair. “PHIGS Flinctional Description. Revision 3.0."
`Computer Graphics. 22(3). 1938. pp. 125—218. incorporated
`by reference herein. and is a desoendent of OKs-3D.
`described in International Standards Organization. “Interna—
`tional Standard Information Processing Systems Computer
`Gaphics—Graphical Kernel System for ”three Dimensions
`(OKs-3D) Emotional Description." 130 Document Number
`8805: 198803). American National Standards Institute. New
`York. 1938. incorporated by reference herein. PHIGS was a
`connnitteeoesigned system for interactive 3-D graphics
`display. In PHIGS. the entire model database resides in a
`single hierarchy. Application programmers must learn a host
`of editing and hierardty manipulation calls in order to
`etfectiveiy use the system. PHIGS employs a single tenderer
`mat supports all the rendering modes specified available in
`PHIGS. and does not support alternative rendaers for pho-
`torealism or other efl‘ects.
`PBX. PEX is an extension to the X—Windows system.
`defined by a serial protocol (for transmitting data between an
`application program and the X—Windows system) and a set
`of semantics which were originally derived from PHIGS.
`PEX has several available APIs. all of which support
`retained~mode. immediate-mode. and mixed-mode function
`calls for drawing. changing state. etc. PEX is described in
`“PEX Protocol Specification. Version 5.0P-X Public Review
`Draft.” 14 Sep.. 1990. Massachusetts Institute of
`Technology. incorporated by reference herein.
`HOOPS”. HOOPS. by Ithaca Software. is described in
`Garry Megand and Bob Covey. “HOOPS Reference
`Manual. Version 3.0." Ilham Software. 1991. incorporated
`by reference herein It is a retained mode 3-D graphics
`system. which organizes the model in a hierarchy whose
`nodes are accessed through textual strings in much the same
`way that files in the UNIX file system are referenced Like
`PHIGS. HOOPS supports a single renderer. However.
`HOOPS provides more extensive scene editing functionality
`than PHIGS.
`
`DORE“l DORE. by Kubota. is an example of a 3-D
`graphics system with an object-oriented design.
`It
`is
`described in “Dore Programmer’s Guide.” Release 5.0.
`Kubota Pacific Counselor Inc. 1991. incorporated by refer-
`ence herein. DORE was designed so that scene data is
`renderabie by many kinds of renderers. rather than a single
`monolithic tenderer as provided by PHIGS. Renda'u's can-
`not be added dynamically to DORE. however. as the ren—
`dering methods are built into the system. In DORE. the
`choice of renderers is specified by setting the current ren—
`dering style in the DORE “View object“. DORE then also
`requires the application program to attach the 11106113] to the
`view object before rendering. This restrias DORE to uti—
`lizing only one renderer at a time. Then are other design
`considerations in Donia that use restrict it to using only one
`tenderer at a time: for example. only one set of global
`variables is provided for maintaining the rendering state.
`
`4
`
`DORE is a retained mode system. To relieve much of the
`hassle associated with editing the model hierarchy and to
`facilitate dynamic databases and user interaction. DORE
`supports application callback objects. whereby an applica-
`tion program defines a function to be called when the
`callback object is enowntered during scene traversal.
`Inventor”. Inventor is an object oriented 3-D graphics
`user interaction toolkit that sits on top of the GL graphics
`system. Like DORE. inventor supports multiple rendercrs
`by having a tenderer-specific “render" method for each
`object type. Inventor is it retained mode system with the
`entire scene residing in a “scene graph". Inventor has render
`action objects that take a model as a parameter. The renderer
`is selected by the rendering action that is used when drawing
`the model. The render action draws the entire model by
`traversing the model and calling the appop'iate rendering
`method for each objecL The usual render aaion is the GL
`rendering mode. Inventor is described in Werneclre. “The
`Inventor Mentor". Addison-Wesley (1994). incorporated by
`reference herein.
`
`Other references pertinent to the disclosure herein are the
`following. all incuporated by reference herein: Bergman.
`Fuchs. and Grant. “Image Rendering by Adaptive
`Refinement." Computer Graphics. 20(4). 1986. pp. 29—37;
`Catmull. “ASubdivision Algorithm for Computer Display of
`Curved Surfaces.” PhD. Thesis. Report UTEC-CSc-M—BB.
`Computer Science Department. University of Utah. Salt
`Lake City. Utah. December. 1974: Chen. Rushmeier. Miller.
`and Tin-net. “A Progressive Multi—Pass Method for Global
`Illumination." Computer Graphics. 25(4). 1991. pp.
`165—174; (Hark. ‘The Geometry Engine: A VLSI Geometry
`System for Graphicsf Computer Graphics. 16(3). 1982. pp.
`127—133; Foley. van Dam. Feiner. and Hughes. “Cotnpulet
`Graphics: Principles and Practice.” Addison-Wesley.
`Reading. Mass. 1990: Haeberli and Alreley. "I'he Accumu-
`lation Bufl’er: Hardware Support for High-Quality
`Rendering.” Computer Graphics. 24(4). 1990. pp. 309-318:
`Kelley. Winner. and Gould. “A Scalable Hardware Render
`Accelerator using a Modified Scanline Algorithm." Com-
`puter Graphics. 26(2). 1992. pp. 241—248; Maillot. "three-
`Dimensionai Homogeneous Clipping of Triangle Strips."
`Graphics Gems 11. Academic Press. Inc. San Diego. CaliI..
`1991. pp. 219—231: Nowell. Nowell. and Sancha. “A Solu»
`tion to the Hidden Stn'face Problem.“ Proceedings of the
`ACM National Conference. 1972. pp. 443—450; Pottnesil
`and Holfett. “FRAMES: Sofiware Tools for Modeling.
`Rendering. and Animation of 3D Scenes.” Computer
`Graphics. 21(4). 1987. pp. 85—93: Saito and Takabashi.
`"Comprehensihle Rendering of 3-D Shapes.” Computer
`Graphics. 24(4). 1990. pp. 197—206: Segal. Koroblrin. van
`Widenfelt. Foran. and Haeberli. "Fast Shadows and Lighting
`Effects Using Texune Mapping.” Computer Graphics. 26(2).
`1992. pp. 249—252: Billion and PHCCh. "A General‘l‘wo-Pass
`Method Integrating Specular and Dilfuse Reflection." Com-
`puter Graphics. 23(3). 1989. pp. 335—344; Snibbe. Herndon.
`Robbins. Conner. and van Darn. “Using Deformations to
`Explore 3D Widget Design.” Computer Graphics. 26(2).
`1992. pp. 351—352; Strauss and Carey. “An Object-Oriented
`3D Graphics Toolkit.” Computer ('iraphics. 26(2). 1992. pp.
`341-349; 'I‘urkowsii "Design Considerations for an Object-
`Oriented [3D Graphics] Metafile." Proceedings of the Third
`Eurographics Workshop on Object-Oriented Graphics.
`Charnpery. Switzerland. October. 1992. pp. 163~169;
`Venolja. “Facile 313 Direct Manipulation.” to appear in
`Proceedings of CHI ’93. ACMISIGCI-H. Amsterdam. May.
`1993: Venolia. “Automatic Alignment in Two and Three
`Dimensions.” submitted to SIGGRAPH ’93; and Wanget'.
`
`10
`
`15
`
`35
`
`45
`
`55
`
`65
`
`15
`
`15
`
`

`

`5
`
`6
`
`5 377.621
`
`"The Elfecl of Shadow Quality on the Perception of Spatial
`Relationships in Computer Generate Imagery.” Proceedings
`of the 1992 Symposium on Interactive 3D Graphics.
`Cambridge. Mass. 1992. pp. 3942.
`When a once-dimensional model is to be rendered into a
`scene for display. a classic trade-off exists between the speed
`of the rendering operation. on the one hand. and the quality
`of the result. on the other hand. For example. wire frame
`rendering operates at high speed. but produces a lowquality
`result. whereas a ray-tracer requires a much longer time
`period to render the same model. but can produce extremely
`high-quality results. Thus. an application program which
`permits interactive editing of a three-dimensional model
`may benefit by using a wire frame renderer to draw inter-
`mediate versions on a display. and by using a ray-tracer
`renderer to draw the final version for output. However. the
`interchangeability of renderers is awkward at best using the
`rendering systems described above. Moreover. substitution
`of one renderer for another provides only gross control over
`the specdlquality trade-of continuum. It would be desirable
`to permit an application program to sacrifice a little quality
`in order to gain a little speed. or vice versa. It would be
`desirable to provide a plurality of gradations on the speed)'
`quality trade-oil continuum so that a user or application
`program may select exactly the desired position in the
`nadwlf.
`
`In the past. application programs have provided users
`with control over various incidental parameters of the ten-
`daring process. and users have taken advantage of this
`control by selecting options which. as a side oiled. allied the
`speedi'quality trade—off. For example. by temporarily Dining
`06 certain lights. a user can hasten the rendering process at
`the expense of quality. The same eifect can be accomplished
`by culling objects from the scene before rendering. by
`making the output window smaller. by switching from filled
`mode to edge mode for a render-er that allows such selection.
`and by setting a coarser antialiasing level. In some systems.
`several of the parameters which alters the speedlquality
`trade-off are made accessible to the user in a single dialog
`box. in which the user can select an option for each of the
`controllable parameters. This is a highly piecemeal approadt
`to the problem Other appficarion programs do allow a user
`to select a gross quality for rendering. but usually the user's
`selection causes the program to call a completely different
`renderer. or at
`least causes the renderer to use grossly
`dilferent rendering methods.
`Accordingly. there is a need for a quality control moha-
`nism which allows an application program or user to select
`a desired point in the overall speedlquality rendering trade-
`olf. with relatively fine resolution on the continuum. and
`without being concerned with individual rendering pastu-
`eras.
`
`and rendering speed For example. each of the quality
`conu-ol data groups may include a quality control type
`variable for “level of detail“; those grwps at the lower end
`of the quality continuum may have dtose variables set to
`“low“. whereas data groups at the higher end of the con»
`tinuum may have this variable set to “high".
`In an aspect of the invention. each of the quality control
`data groups is associated with a respective quality index.
`Thus. an application program can select a point on the
`overall rendering speediquality renda'ing trade-03’. merely
`by selecting a quality control index value. Moreover. the
`application program can make the quality control index
`accessible to a user. for example in such an intuitive form as
`an iconic “quality knob". The quality knob may have a
`number of settings. for example. ranging from 0.0 to 1.0.
`each of which corresponds to a respective one of the quality
`control data groups. Thus the mechanism permits the user to
`have fine control over the rendu'ing speediquality rendering
`trade-off. without being concerned with adjustments to the
`individual rendering parameters.
`
`10
`
`15
`
`HRH DESCRIPTION OF THE DRAWINGS
`
`The invention will be described with respect to particular
`embodiments thereof and reference will be made to the
`drawings. in which:
`FIG. 1 is a simplified block diagram of a computer system
`implementing the present invention;
`FIG. 2 illustrates a sofnvare architecture employing the
`invention;
`FIG. 3 is a flowchart illustrating the oviaall flow of a
`program using the invention;
`FlG.disadetailofstep308inFIG.3;
`FIGS. 5. 7. 9. 11 and 12 illustrate object data structures in
`memory;
`FIG. 6 illustrates a class hierarchy used in an embodiment
`of the invention;
`FIG. 8 illustrates a m