(12) United States Patent
`Rosasco
`
`US006317137B1
`US 6,317,137 B1
`NOV. 13, 2001
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`(54) MULTI-THREADED TEXTURE
`MODULATION FOR AXIS-ALIGNED
`VOLUME RENDERING
`
`Watt, A. and Watt, M., Advanced Animation and Rendering
`Techniques." Theory and Practice, Copyright 1992, ACM
`Press, pp. xi—xiv and 297—321.
`
`(75) Inventor: John D. Rosasco, Belmont, CA (US)
`(73) Assignee: Silicon Graphics, Inc., Mountain View,
`CA (US)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/201,814
`(22) Filed:
`Dec. 1, 1998
`
`(51) Int. Cl.7 ................................................... .. G06T 11/40
`
`(52) us. Cl. ........................ .. 345/582; 345/467; 345/471;
`345/472
`
`(58) Field of Search ................................... .. 345/430, 424,
`345/423, 419, 429, 505, 425, 439, 472,
`471, 467, 25, 470, 128; 600/461, 407; 382/128,
`203, 217
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`5,570,460 * 10/1996 Ramanujam ....................... .. 345/424
`5,786,826 * 7/1998 Kwok ........... ..
`345/505
`5,797,849 * 8/1998 Vesely et a1. ..
`600/461
`5,831,623 * 11/1998 Negishi et a1.
`345/424
`5,891,030 * 4/1999 Johnson et a1.
`GOO/407
`5,926,568 * 7/1999 Chaney et a1. ..................... .. 382/217
`
`OTHER PUBLICATIONS
`Cabral, B. et al., “Accelerated Volume Rendering and Tomo
`graphic Reconstruction Using Texture Mapping Hardware,”
`Proc. OfACM/IEEE Symp. On Volume Wsulaization, 1994,
`pp. 91—98.
`Drebin, RA. et al., “Volume Rendering,” Computer Graph
`ics, vol. 22, No. 4, Aug. 1988, pp. 65—74.
`Foley, J .D., Computer Graphics Principles and Practice—
`2nd Edition in C, Copyright 1996, Addison—Wesley Pub
`lishing Company, pp. xvi—xxiii, 855—922 and 1034—1039.
`
`* cited by examiner
`
`Primary Examiner—Matthew Luu
`Assistant Examiner—Thu-Thao Havan
`(74) Attorney, Agent, or Firm—Sterne, Kessler, Goldstein
`& Fox, p.l.l.c.
`(57)
`
`ABSTRACT
`
`A method, system, and computer program product are
`provided for multi-threaded texture modulation in axis
`aligned volume rendering. Three texture modulation threads
`are used to modulate texture of three sets of the volumetric
`data (image sets) in accordance with a texture modulation
`request. Control is returned from the ?rst texture modulation
`thread to a main rendering thread while the ?rst texture
`modulation thread is executing. Auser can then interact with
`a display view while the ?rst texture modulation thread is
`executing. An intermediate display view of a texture modu
`lated set of volumetric data can be rendered. In one example,
`a plurality of display connections and contexts are opened
`for the main rendering thread and each texture modulation
`thread respectively. Sets of pixel buffers and look-up tables
`are provided for the respective texture modulation threads.
`A texture object is included in a context of the main
`rendering thread. Each pixel buffer stores a respective image
`set and is associated with the texture object. According to
`further feature, the sets of volumetric data are sorted based
`on the angle between normals to the sets and a current
`viewpoint. The texture modulation threads are then executed
`(unblocked) based on the sorted order of the sets. For a given
`graphics machine and especially on a low end machine, the
`multi-threaded texture modulation of the present invention
`increases speed, provides interactive control, and gives
`intermediate display views in axis-aligned volume render
`ing. A clinician or other user can see intermediate informa
`tion and interact with the intermediate display view accord
`ingly.
`
`16 Claims, 13 Drawing Sheets
`
`(1 of 13 Drawing Sheet(s) Filed in Color)
`
`TD SIEP 13H
`
`Page 1 of 22
`
`Unified Patents Exhibit 1018
`
`

`

`U.S. Patent
`
`Nov. 13, 2001
`
`Sheet 1 0f 13
`
`US 6,317,137 B1
`
`FIG. 1
`
`IN AXIS—ALIGNED VR
`
`(ROUTINE FOR MULTI-THREAOEO TEXTURE MODULATION) IOO
`I
`
`STORE THREE ORTHOGONAL IMAGE SETS OF VOLUME DATA
`
`/11o
`
`/114
`
`INITIATE MAIN HENDEHING THREAD AND CONTEXT
`I t R
`INITIATE MULTIPLE TEXTURE MODULATION THREADS AND / 118
`CONTEXTS FOR MOOULATING RESPECTIVE IMAGE SETS
`I 11.12. t3
`RENDER VOLUME DATA
`,1,
`TEXTURE MODULATION REQUEST 135 KT
`
`/13°
`TH (EXECUTE)
`t1. t2 I t3 (BLOCK)
`
`SELECT IMAGE SET
`
`/140
`
`RETURN CONTROL
`
`TR (EXECUTE) ‘
`TNETATTATTTATAATT"TTAUTD
`\
`190
`
`151
`/
`
`.
`
`wTTTTE
`
`UNBLOCK t1 /150
`I
`'
`RUN t
`'1
`UNBLOCK T /160
`2
`
`/152
`
`/1B2
`
`HUN t2
`WHITE <—‘
`UNBLOCK t3 /170
`
`WRITE <_T RUN t3
`
`/172
`
`Page 2 of 22
`
`Unified Patents Exhibit 1018
`
`

`

`U.S. Patent
`
`Nov. 13, 2001
`
`Sheet 2 0f 13
`
`US 6,317,137 B1
`
`FIG. 2A
`
`ROUTINE FOR INITIATING TEXTURE MODULATION CONTEXTS
`IN THREADS (t1. t2. t3) FOR MODULATING
`RESPECTIVE IMAGE SETS (Xy, XZ. yz)
`
`119
`
`1
`
`FOR EACH TEXTURE MODULATION THREAD
`
`)/22°
`
`CREATE A PIXEL BUFFER AND LOOK-UP TABLE (LUT)
`
`STORE THE CORRESPONDING IMAGE SET IN THE PIXEL BUFFER
`
`L
`L
`L
`
`ASSOCIATE PIxEL BUFFER wITH TEXTURE OBJECT
`IN THE MAIN RENDERING CONTEXT
`
`OPEN A RESPECTIVE DISPLAY CONNECTION
`AND A RENDERING CONTEXT
`
`NEXT THREAD
`
`/222
`
`/224
`
`/225
`
`/225
`
`Page 3 of 22
`
`Unified Patents Exhibit 1018
`
`

`

`U.S. Patent
`
`Nov. 13, 2001
`
`Sheet 3 0f 13
`
`US 6,317,137 B1
`
`FIG . 28
`
`C EXECUTE MAIN RENDEHING THREAD
`
`)/13°
`
`INITIALIZE THHEAD SEMAPHOHES IN BLOCK /232
`
`I
`
`GENEHATE A VOLUME RENDERED DISPLAY OF /?34
`DATA POINTED T0 BY TEXTURE OBJECT
`
`@
`
`FIG . 2C
`
`135 \
`( UsER INPUTS A TEXTURE NDDULATIDN REDUEsT )?as
`
`TRANsLATE TEXTURE MODULATION REDUEsT T0
`CHANGE IN A LOOK-UP TABLE
`
`?gs
`
`242
`I
`140
`\\ sDRT IMAGE SETS BASED ON ANGLE DETNEEN REsPEcTTvE /
`IMAGE sET PLANES AND CURRENT XIENPDINT
`
`I
`
`DETERMINE IMAGE SEI MOST OHIHOGONAL I0
`CUHHENI VIEWPOINT
`
`@
`
`/ 244
`
`Page 4 of 22
`
`Unified Patents Exhibit 1018
`
`

`

`U.S. Patent
`
`Nov. 13, 2001
`
`Sheet 4 0f 13
`
`US 6,317,137 B1
`
`FIG. 20
`
`( HUN EIRsI UNBLOCKED MODULATION IRREAD D/PZ
`T
`
`UPDATE FIRST LOOK-UP TABLE T0 REPRESENT
`TEXTURE MODULATION REQUEST
`
`/254
`
`T
`
`MODULATE ORIGINAL DAIA OF FIRST IMAGE SET /256
`BASED ON UPDATED EIRsI LOOK-UP TABLE
`
`T
`
`STORE MODULATED DAIA IN EIRsI PIXEL RuEEER /259
`
`FIG . 2E
`
`( RUN SECOND UNBLOCKED MODULATION IRREAD
`
`)/152
`
`uPDAIE SECOND LOOK-UP TABLE I0 REPREsENI
`TEXTURE MODULATION REDuEsI
`
`f2“
`
`MODULATE ORIGINAL DATA 0F SECOND IMAGE SET
`BASED ON UPDATED SECOND LOOK-UP TABLE
`
`fEBE
`
`T
`
`STORE MODULATED DATA IN SECOND PIXEL BUFFER
`
`/255
`
`Page 5 of 22
`
`Unified Patents Exhibit 1018
`
`

`

`U.S. Patent
`
`Nov. 13, 2001
`
`Sheet 5 0f 13
`
`US 6,317,137 B1
`
`FIG. 2F
`
`Q RON THIHD UNBLOCKED MODULATION THREAD Y1”
`
`UPDATE THIRD LOOK-UP TABLE I0 REPRESENT
`TExTuRE MODULATION REOOEsT
`
`f2”
`
`MODULAIE ORIGINAL DAIA 0F THIRD IMAGE SEI
`BASED ON UPDATED THIRD LOOK-UP TABLE
`
`I
`
`STOHE MODULATED OATA IN THIHD PIXEL BUFFEH
`
`fzIs
`
`/279
`
`FIG. 3
`/\
`
`112
`xy IMAGE sET
`
`m
`xz IMAGE SET
`
`m
`yz IMAGE sET
`
`X
`
`v.
`
`N
`
`Page 6 of 22
`
`Unified Patents Exhibit 1018
`
`

`

`U.S. Patent
`
`Nov. 13, 2001
`
`Sheet 6 0f 13
`
`US 6,317,137 B1
`
`FIG. 4
`MAIN MEMORY (UNIFIED CASE)
`L
`
`\
`
`410\
`
`PBUFFER
`1
`
`PBUFFEH
`3
`
`LUT1
`
`um
`
`ORIGINAL
`DATA
`XY
`
`ORIGINAL
`DATA
`YZ
`
`\
`412
`
`\
`430
`
`\
`432
`
`\
`310
`
`\
`330
`
`420
`\ PBUFFEH
`2
`
`LUT2
`
`TEXTUHE
`OBJECT
`
`ORIGINAL
`DATA
`XZ
`
`\
`422
`
`\
`402
`
`X
`
`Page 7 of 22
`
`Unified Patents Exhibit 1018
`
`

`

`U.S. Patent
`
`Nov. 13, 2001
`
`Sheet 7 0f 13
`
`US 6,317,137 B1
`
`GD
`
`4 0
`0 \ MAIN HENDE
`CONTEX
`
`TEXTURE
`OBJECT
`
`FIG. 5
`
`GD
`
`PBUFFEH
`
`41°\
`
`——> W1 1 r~~ 412
`
`MODULATION
`XY cow
`
`EAD
`
`/404
`
`420 @ /
`
`PBUFFEH
`
`I-LUTZ
`
`2
`
`Av422
`
`MODULATION TH
`X2 CONTE
`
`0
`
`/405
`
`430 @
`
`———> LUT3
`
`PBUFFEH
`3 A; 433
`
`MODULATION
`YZ CON
`
`EAD
`
`/40B
`
`Page 8 of 22
`
`Unified Patents Exhibit 1018
`
`

`

`US. Patent
`
`Nov. 13, 2001
`
`Sheet 8 0f 13
`
`US 6,317,137 B1
`
`m2.
`
`
`
`m:éS-~>%V_oo._-Nxnsvaof;
`5928
`
`c928EH28
`
`
`L#
`
`2:.
`
`HXMHZOU
`
`Zing
`
`SHE/Eu
`
`wm<3om<z
`
`omm
`
`:x
`
`$>Ew
`
`mama:mewstzzsElms
`
`m.mHl
`
`SHEEw
`
`E<
`
`21:58
`
`E:2028228
`
`2025;;
`
`$58;
`
`Page 9 of 22
`
`Unified Patents Exhibit 1018
`
`Page 9 of 22
`
`Unified Patents Exhibit 1018
`
`
`
`
`
`
`
`

`

`US. Patent
`
`US 6,317,137 B1
`
`cm.
`
`
`
`mmssmémuEméw
`
`.3m_m53%..N\,wIEE:/Lmm:m..am5E?58%IQ0:ME:Iz:28%me.am:5223%m23$;N»m,m295:Ea#2520a3we.cmW.#9Neat?zmsmwmomofix:9m.mHl
`
`Page 10 of 22
`
`Unified Patents Exhibit 1018
`
`Page 10 of 22
`
`Unified Patents Exhibit 1018
`
`
`

`

`U.S. Patent
`
`Nov. 13, 2001
`
`Sheet 10 0f 13
`
`US 6,317,137 B1
`
`FIB/k B
`
`THREAD ’[ 1
`
`/310
`GRAPHICS
`DI?A ‘—_ HARLDJJTAHE
`
`/410
`‘_-—|- PBUIZFEH
`
`/412
`
`MAIN HENDEHING
`THREAD tH
`
`_/412
`
`/E30
`
`_/710
`
`‘
`
`PBUFFER
`1
`
`I
`
`i
`(TEXTURE MAPPING)
`
`I
`
`FRAME
`BUFFER
`
`Page 11 of 22
`
`Unified Patents Exhibit 1018
`
`

`

`U.S. Patent
`
`Nov. 13, 2001
`
`Sheet 11 0f 13
`
`US 6,317,137 B1
`
`FIG. 9
`
`cDMPuIER SYSTEM 900
`
`PRocEssoR
`/904
`<l:ll> GRAPHICS /-903
`SUBSYSTEM
`
`905
`DISPLAY /
`INTERFACE
`
`90s
`
`<I:l> MAIN MEMDRY
`
`_/H08
`
`COMMUNICATIONS fgog
`INFRASTRUCTURE
`
`sEcoMDARY MEMDRY
`
`HARD DISK DRIvE
`
`910
`/
`
`fm
`
`<:>
`
`REMOVABLE STORAGE DRIvE -------- --
`
`'914
`’
`
`9/18
`REMOVABLE
`STORAGE
`UNIT
`
`/520
`
`REMOVABLE
`
`INTERFACE
`
`~- ------ --
`
`sIDRADE
`
`UNIT
`
`\
`922
`PEDHEIvPIHcEERsAL
`E§E}'~sa2
`<J\:> BHAPHICAL
`COMMUNICATIONS
`USEH'INTEHFACE \"ggd
`PATH
`/924
`92s
`
`COMMUNICATIONS ....... -
`
`INTERFACE
`
`------- -
`
`Page 12 of 22
`
`Unified Patents Exhibit 1018
`
`

`

`U.S. Patent
`
`Nov. 13, 2001
`
`Sheet 12 0f 13
`
`US 6,317,137 B1
`
`FIG. 10
`EXAMPLE OF VOLUME HENDEHED IMAGE 0F SKULL DATA SET
`
`1000
`
`FAT
`
`TISSUE
`
`BONE
`
`135
`
`nlllv. '10
`
`0
`
`100
`
`100%
`
`Page 13 of 22
`
`Unified Patents Exhibit 1018
`
`

`

`U.S. Patent
`
`Nov. 13, 2001
`
`Sheet 13 0f 13
`
`US 6,317,137 B1
`
`FIG. 1.1
`
`Page 14 of 22
`
`Unified Patents Exhibit 1018
`
`

`

`US 6,317,137 B1
`
`1
`MULTI-THREADED TEXTURE
`MODULATION FOR AXIS-ALIGNED
`VOLUME RENDERING
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`The present invention relates to computer data processing
`and graphics, and in particular, to computational tasks
`including, but not limited to, volume rendering and image
`processing operations.
`2. Related Art
`Volumetric data representing spatial volumes arises in
`many applications. Computed tomography (CT) and mag
`netic resonance imaging (MRI) scanners create a volume by
`imaging a series of cross-sections, also called slices or
`samples. Astrophysical, meteorological, and geophysical
`measurements, and business or economics data also natu
`rally lead to a volumetric data set. Computer graphics
`systems use a volume rendering algorithm to display a
`visualiZation of volumetric data. See, Watt and Watt,
`Advanced Animation and Rendering Techniques." Theory
`and Practice, (ACM Press: NeW York, NY. 1992), Chapter
`13, pages 297—321; Foley et al., Computer Graphics, Sec
`ond Ed. In C, Addison-Wesley Publishers, USA. (1996),
`pp. 1034—39; R. Drebin, L. Carpenter, and P. Hanrahan,
`“Volume Rendering,” Computer Graphics, Vol. 22, No. 4,
`(SIGGRAPH ’88, Atlanta, Ga.), August 1988, pp. 65—74;
`and B. Cabral, N. Cam and J. Foran, “Accelerated Volume
`Rendering and Tomographic Reconstruction Using Texture
`Mapping HardWare,” Proceedings of ACM/IEEE Sympo
`sium on Volume Visualization (IEEE CS Press), pp. 91—98,
`1994 (Order No. PR07067, 1995) (each of Which is incor
`porated in its entirety herein by reference).
`In axis-aligned volume rendering, volumetric data is
`represented by three sets of tWo-dimensional textures or
`images. Each set typically corresponds to a cardinal vieW
`(i.e., a vieW along an X, y, or Z direction). To render a volume
`image an axis-aligned volume rendering (VR) algorithm
`volume renders each set of data relative to a current vieW
`point. Typically, an axis-aligned VR algorithm begins With
`the set most nearly perpendicular to a vieW from eye point.
`Blending and accumulation operations are performed on
`samples along the selected axis to obtain a ?nal frame buffer
`image. The frame buffer image is then output for display.
`See, e.g., the Volume Imaging application programming
`interface (also called OPENGL VOLUMIZER) released by
`Silicon Graphics, Inc.
`Clinicians and other users Want to modulate texture to
`accentuate different features in the volumetric data. For
`example, a radiologist observing a volume rendered display
`vieW of a human head may Want to analyZe only soft tissue.
`Such texture modulation, hoWever, is dif?cult to perform in
`real-time on most graphics platforms. Indeed, on loW-end
`graphics machines (platforms Without three-dimensional
`(3-D) texturing), texture modulation is the single biggest
`performance limiting factor. Performance is further limited
`in the case of axis-aligned volume rendering as three copies
`of the volume data (that is, all three orthogonal sets of 2-D
`textures)need to be modulated.
`These performance limitations sloW texture modulation.
`In axis-aligned volume rendering, a user must Wait until
`texture is modulated in each copy of the volume data. In
`addition, control is also lost during this time of texture
`modulation. In other Words, a user cannot interact With the
`current volume rendered image until the texture modulation
`of all three copies of the volume data and the volume
`
`10
`
`25
`
`35
`
`45
`
`55
`
`65
`
`2
`rendering of the current vieW based on a copy of the
`modulated volume data is complete.
`As recogniZed by the inventor, What is needed is a
`technique Which alloWs faster texture modulation in axis
`aligned volume rendering even on loWer end graphics plat
`forms. Control needs to be returned to a user during texture
`modulation processing. A user needs to be able to interact
`With a volume rendered image after a texture modulation
`request is made, that is, While texture modulation processing
`is being performed. A user needs to be able to see an
`intermediate texture modulated vieW, that is, a vieW Which
`is rendered and displayed While texture modulation is pro
`ceeding.
`
`SUMMARY OF THE INVENTION
`A method, system, and computer program product pro
`vide multi-threaded texture modulation in axis-aligned vol
`ume rendering. Three sets of volumetric data are provided.
`Each set corresponds to a different vieW.
`In one embodiment, When a texture modulation request is
`made an image set (also called a copy of the volumetric data)
`is selected. Image sets are sorted based on an angle betWeen
`the respective image set planes and a current vieWpoint. The
`image set Which is selected ?rst is determined to be the most
`orthogonal to a current vieWpoint. For example, an x-y
`image set is selected for current vieWpoints closest to a
`surface normal from the x-y plane (that is, points closest to
`the Z axis). Alternatively, a y-Z image set is selected ?rst for
`current vieWpoints points closest to the x axis. A X-Z image
`set is selected ?rst for current vieWpoints closest to the y
`axis. In this Way, the ?rst image set Which is to be texture
`modulated is the image set that is likely to provide the most
`helpful and informative display vieW (With the most relevant
`foreground or front surface information).
`This sorting then identi?es the order in Which the copies
`of the volumetric data Will be modulated. More speci?cally,
`this sorting identi?es the order in Which three threads Will be
`executed to modulate texture in their respective image sets
`(i.e., the respective copies of the volumetric data). Depend
`ing upon the results of the sorting operation then different
`threads Will be executed ?rst, second and third.
`After sorting, a main rendering thread and a ?rst texture
`modulation thread are executed. The ?rst texture modulation
`thread is simply the thread that corresponds to the selected
`image set. The ?rst texture modulation thread executes to
`modulate texture of a ?rst set of the volumetric data in
`accordance With a texture modulation request.
`Control returns from the ?rst texture modulation thread to
`the main rendering thread While the ?rst texture modulation
`thread is executing. In this Way, a user can interact With a
`display vieW While the ?rst texture modulation thread runs.
`Second and third texture modulation threads also execute to
`modulate texture of second and third sets of the volumetric
`data in accordance With the texture modulation request.
`Such multi-threaded processing, according to the present
`invention, de-couples rendering and texture modulation
`operations and leverages processing in multiple threads. The
`time to satisfy an input texture modulation request is
`reduced to one-third the time required in conventional
`axis-aligned volume rendering.
`When the ?rst texture modulation thread completes, a
`?nal texture modulated vieW can be rendered. The rendering
`has the ?nal texture modulated result for the current vieW. A
`?nal display vieW representative of the input texture modu
`lation request is draWn based on a copy of a set of texture
`modulated volumetric data. Preferably, the set of texture
`
`Page 15 of 22
`
`Unified Patents Exhibit 1018
`
`

`

`US 6,317,137 B1
`
`3
`modulated volumetric data used corresponds to the current
`vieW, that is, the set having a cardinal axis most parallel With
`a line of sight from an eyepoint of the current vieW.
`According to a further feature of the present invention, an
`intermediate texture modulated vieW can be displayed
`before modulation of an image set is complete, that is, While
`the ?rst texture modulation thread is executing. This is
`possible because the main rendering thread and texture
`modulation threads are de-coupled from each other. In an
`intermediate texture modulated display vieW, a user sees
`immediate feedback on the changes in the image Wrought by
`the input texture modulation request. Such feedback is
`visually compelling and informative. A user remains
`engaged. A user can gauge the effect of the texture modu
`lation even before the vieW is complete. For instance, by
`observing the intermediate texture modulated vieW, a user
`can Without delay plan the next texture modulation request
`he or she Wants to study or can move to another vieWpoint
`While the ?rst texture modulation thread continues to
`execute.
`Thread semaphores are used to block and unblock the
`texture modulation threads. In one example, the texture
`modulation threads are executed (unblocked) based on a
`sorted order of the sets or a predetermined or default order.
`In one feature of the present invention, the sets of volumetric
`data are sorted based on the angle betWeen normals to the
`sets (that is, the cardinal axes) and a current vieWpoint. Sets
`more closely parallel With the line sight are given priority in
`the sorting.
`In one example client/server implementation, a further
`feature is provided in that a plurality of display connections
`and contexts are used. For example, a display connection
`can be a socket-based VI event connection betWeen a host
`X.11 server and a client application. In this case, a client
`application is the multi-threaded axis-aligned volume ren
`derer. A display connection and graphics state context is
`opened for the main rendering thread and each texture
`modulation thread respectively. Sets of pixel buffers (also
`called off-screen buffers) and look-up tables are provided for
`the respective texture modulation threads. A texture object is
`included in a context of the main rendering thread. Each
`pixel buffer stores a respective image set and is associated
`With the texture object.
`One or more processors can be used to perform the Work
`of the main rendering thread or the texture modulation
`threads. In one example, four processors are dedicated to
`each thread.
`In one example implementation compatible With an IRIX
`machine, a display connection and context are opened in
`initiating each texture modulation thread. Each texture
`modulation thread is initiated by creating a respective pixel
`buffer and look-up table, storing a respective image set in the
`pixel buffer, and associating the pixel buffer With a texture
`object in a context of the main rendering thread. Each
`texture modulation thread then executes (in series or in
`parallel depending upon the number of processors available
`on a machine) to update a respective look-up table and to
`modulate original data (texture) based on the respective
`updated look-up table. Entries in the updated look-up tables
`represent the texture modulation request. Modulated volu
`metric data is stored in respective pixel buffers.
`For example, When a ?rst texture modulation thread is
`executed the folloWing steps are performed. A respective
`?rst look-up table is updated in accordance With the texture
`modulation request. A ?rst image set of original volumetric
`data is modulated based upon the update ?rst look-up table.
`
`10
`
`15
`
`25
`
`35
`
`45
`
`55
`
`65
`
`4
`Modulated volumetric data is stored in a ?rst pixel buffer.
`The contents of the ?rst pixel buffer can be reformatted (i.e.,
`texture mapped) to a frame buffer for display at any time
`during modulation. Thus, the main rendering thread can
`output an intermediate texture modulated display vieW for
`display that represents the current ?rst pixel buffer contents
`at any time during modulation, that is, as the ?rst texture
`modulation thread progresses. A ?nal texture modulated
`display vieW is rendered When the ?rst texture modulation
`thread completes. Second and third texture modulation
`threads execute similar steps to update respective look-up
`table entries and to store modulated data into respective
`pixel buffers based on the input texture modulation request.
`In practice, the frame buffer is periodically updated With
`the contents of the pixel buffer. The rate at Which the frame
`buffer is updated can be dependent upon the duration of
`texture modulation processing. For example, a frame buffer
`can be updated every 100 milliseconds for relatively quick
`texture modulation threads that complete in one or tWo
`seconds. SloWer frame buffer update rates can be used for
`longer texture modulation requests, such as, oil and gas data
`samples Where modulation requests can take considerably
`longer.
`In one example implementation, processing logic
`(softWare and/or hardWare) sWitches control of at least one
`processor from executing a ?rst texture modulation thread to
`executing the main rendering thread While the ?rst texture
`modulation thread is executing. Graphics hardWare is used
`to update look-up table entries to represent a texture modu
`lation request. Based on the updated look-up table, original
`data (texture) for an image set is modulated to obtain
`intermediate results. The graphics hardWare then reformats
`(e.g., texture maps) the intermediate results to a frame buffer
`for display. In this Way, dedicated hardWare for look-ups can
`be avoided. Such hardWare is expensive because a lot of die
`space is required on a chip.
`The present invention is described primarily With respect
`to an example volume rendering and texture modulation
`embodiment. As Would be apparent to a person skilled in the
`art given this description, of multi-threaded operations the
`present invention can be used in other computational tasks
`including, but not limited to, image processing.
`Multi-threaded, uni-processor and multi-processor graph
`ics platforms have become increasingly popular as their cost
`decreases and their applications Widen. The present inven
`tion alloWs faster texture modulation in axis-aligned volume
`rendering even on loWer end graphics platforms. Three
`texture modulation threads can operate de-coupled from a
`main rendering thread to increase performance by a factor of
`three. In other Words, frame rate is increased by a factor of
`three. Response time is reduced to one-third.
`Control is returned to a user (ie to a main rendering
`thread) during texture modulation processing. In this Way, a
`user can interact With a volume rendered image after a
`texture modulation request is made While the multi-threaded
`texture modulation processing is being performed. Further,
`intermediate display vieWs are shoWn as a texture modula
`tion thread progresses. Consequently, a clinician or other
`user can see intermediate information and interact With the
`intermediate display vieW accordingly.
`These are signi?cant and practical advantages to an end
`user. For a given graphics machine and especially on a loW
`end machine, the multi-threaded texture modulation of the
`present invention increases speed, provides interactive
`control, and gives intermediate display vieWs in axis-aligned
`volume rendering.
`
`Page 16 of 22
`
`Unified Patents Exhibit 1018
`
`

`

`US 6,317,137 B1
`
`5
`Further features and advantages of the present invention,
`as well as the structure and operation of various embodi
`ments of the present invention, are described in detail below
`with reference to the accompanying drawings.
`
`BRIEF DESCRIPTION OF THE FIGURES
`
`The ?le of this patent application contains at least one
`drawing executed in color. Copies of this patent with color
`drawing(s) will be provided by the Patent and Trademark
`Of?ce upon request and payment of the necessary fee.
`The accompanying drawings, which are incorporated
`herein and form part of the speci?cation, illustrate the
`present invention and, together with the description, further
`serve to explain the principles of the invention and to enable
`a person skilled in the pertinent art to make and use the
`invention.
`FIG. 1 is a diagram of a routine for multi-threaded texture
`modulation in axis-aligned volume rendering according to
`one embodiment of the present invention.
`FIGS. 2A, 2B, 2C, 2D, 2E, and 2F are diagrams of an
`example routine implementing the routine of FIG. 1.
`FIG. 3 is a diagram of example orthogonal image sets of
`volumetric data.
`FIG. 4 is an example of main memory allocation in a
`uni?ed case according to one example of the present inven
`tion.
`FIG. 5 is a diagram of context information relating to a
`main rendering thread and each texture modulation thread
`according to an example of the present invention.
`FIG. 6 is a diagram of display connections and contexts
`opened for the main rendering thread and each texture
`modulation thread in an example graphics API and server
`environment.
`FIG. 7 is a diagram showing the processing of data during
`the execution of the main rendering thread and texture
`modulation threads according to an example of the present
`invention.
`FIG. 8 is a diagram of the transfer of data in the execution
`of an example texture modulation thread and the main
`rendering thread.
`FIG. 9 is a diagram of an example computer system for
`implementing the routine 100 according to one example of
`the present invention.
`FIG. 10 is an example display view of a volume-rendered
`image of a human head data set according to the present
`invention.
`FIG. 11 is an example color image of an intermediate
`texture modulated view of a human head data set, according
`to a further feature of the present invention.
`The present invention is described with reference to the
`accompanying drawings. An effort is made to adhere to the
`following convention. In the drawings, like reference num
`bers indicate identical or functionally similar elements.
`Additionally, the left-most digit(s) of a reference number
`identi?es the drawing in which the reference number ?rst
`appears.
`
`10
`
`15
`
`25
`
`35
`
`45
`
`55
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`
`Overview
`The present invention relates to multi-threaded texture
`modulation in axis-aligned volume rendering. One embodi
`ment of the present invention will be described with respect
`to routine 100 in FIG. 1. In describing routine 100, reference
`
`65
`
`6
`will be made to example display views in FIGS. 10 and 11.
`Next, an example implementation of routine 100 will be
`described with respect to FIGS. 2A—2F and 3—9.
`Terminology
`“Volumetric data” as used herein refers to any digital data
`that can be expressed as a three-dimensional or spatial
`volume. Such digital data can include, but is not limited to,
`three-dimensional arrays or a set of one or two dimensional
`arrays. For example, three-dimensional arrays can represent
`scienti?c and business data. Two-dimensional arrays or
`slices are found in computer tomography, magnetic reso
`nance imaging, ultrasound video images, and other medical
`imaging applications. A set or sequence of sampled 2-D
`images can be used as volumetric data. Volumetric data can
`be one channel or multi-channel data. These examples are
`illustrative. The present invention is not so limited, and in
`general, can be used with any application of volumetric data.
`“Voxel” or “voxel value” are used interchangeably to
`refer to a point in volumetric data. The voxel is represented
`by a location in three-dimensional space (e.g., Cartesian
`coordinates (x,y,Z)) and one or more channel values or
`components (e.g., four-channel data can have red, green,
`blue, and alpha components). “Volume renderer” refers to
`any type of volume-rendering algorithm or system
`including, but not limited to, an axis-aligned volume ren
`derer. “Intermediate texture modulated view” refers to a
`view which is rendered and displayed while texture modu
`lation is proceeding according to the present invention.
`Multi-Threaded Texture Modulation
`FIG. 1 shows a routine 100 for multi-threaded texture
`modulation in axis-aligned volume rendering according to
`an embodiment of the present invention. Three orthogonal
`image sets of volume data are stored in memory (step 110).
`This storage operation can be performed during a pre
`processing stage or on-the-?y. A main rendering thread (tR)
`and associated context or state information is initiated (step
`114). According to the present invention, multiple texture
`modulation threads (t1, t2, t3) and associated contexts or
`states for modulating the respective image sets are initiated
`(step 118).
`In step 130, the main rendering thread tR executes an
`axis-aligned volume-rendering algorithm to render volume
`data. Texture modulation threads t1, t2, t3 are blocked. For
`example, as shown in FIG. 10, a display view 1000 of a
`human head may be drawn from a human head volume data
`set. Different features in the volume data are represented by
`different texture values. To accentuate or diminish features
`which are displayed, a clinician or user inputs a texture
`modulation request 135 into a graphical user-interface. For
`example, in FIG. 10, fat, tissue, and bone information may
`be highlighted by controlling the respective fat, tissue and
`bone sliders in the display view 1000. For example, FIG. 10
`shows a user moving the fat slider to a new fat value to input
`a texture modulation request 135.
`Once an input texture modulation request 135 is made, an
`image set is selected (step 140). For example, an image set
`corresponding to the texture modulation thread t1 may be
`selected. Texture modulation t1 is then unblocked to enable
`it to run (step 150). Control immediately returns to the main
`rendering thread tR (step 151).
`Texture modulation thread t1 which has been unblocked
`proceeds to run (step 152). Texture modulation thread t1 runs
`to modulate original data of a corresponding image set to
`represent the input texture modulation request 135. As
`texture modulation thread t1 progresses, the main rendering
`thread tR reads the intermediate modulated results stored in
`a buffer (e.g., a pixel buffer or off-screen buffer) and
`
`Page 17 of 22
`
`Unified Patents Exhibit 1018
`
`

`

`US 6,317,137 B1
`
`7
`generates a ?rst intermediate or ?nal texture modulation
`volume data display vieW (step 190). FIG. 11 shoWs an
`example ?rst intermediate display vieW 1192 of the human
`head in FIG. 10 modulated in accordance With texture
`modulation request 135. In display vieW 1192, the image is
`draWn based on an intermediate modulated result in a pixel
`buffer, that is, one image set that has been partially modu
`lated as thread t1 progresses to represent input texture
`modulation request 135.
`Once texture modulation thread t1 completes, the main
`rendering thread tR generates a ?nal texture modulation
`volume data display vieW. In a ?nal modulated display vieW,
`the image is draWn based on a ?nal result for a current vieW
`When thread t1 ends, that is, When one image set has been
`completely modulated to represent input texture modulation
`request 135.
`In step 160, the next texture modulation thread t2 is
`unblocked. Texture modulation thread t2 runs to modulate
`the texture of another corresponding image set to represent
`input texture modulation request 135 (step 162). Finally, the
`third texture modulation thread t3 is unblocked (step 170)
`and begins to run (step 172). When texture modulation
`thread t3 runs, texture is modulated in the ?nal im