0331
`
`Volkswagen 1011 - Part 4 of 6
`
`

`
`Pom MCTDI nrnuulmrtnu (E
`
`intaensittes at this stage. The hemicube algorithm only facilitates the ealeuiatlnn
`of the form factors that are aubteqtnently used in calculating diffuse intensifies
`and I 'iabel buffer’ is maintained indicating which patch is cu.rrent]}r nearest to
`the hemlcube pianeL
`
`0332
`
`

`
`@ THE ttaotosmr alert-too
`
`Each pixel on the heroicube can be considered as a small patch and a differ.
`ential to Eutlte area fortn factor. ltnown as a delta forrn Eactor. defined ior each
`pixel. The font: factor of a pixel is a fraction of the differential to finite area fonn
`meter for the patch and can he defined as-.
`
`fipmu _ mg
`=AF'
`
`where out is the area or’ the pixel.
`These form factors are pre-calculated and stored in a lookup tattle. This Is the
`foundation of the eflicienqr oi the herntcube method. Again. using the fact that
`areas of equal projection onto the receiving surface surrounding the centre at
`patch A. have equal form factors, we can conclude that F., for any patch, is
`obtained by summing the pixel tot-to factors onto which patch in proieccs [Figure
`11.4).
`Thus forth factor evaluation now reduces to protection onto mutually orthog.
`onal planes and a sunimaidorn operation.
`Figure 11.5 {Colour Plate] is an interesting image that shows the statue of a
`hetnicuiie placed on the window [Figure iD.?] after all other patches in the scene
`have been projected onto it. A colour lclerttiftes each patch in the soene (and
`every partial patch} that can be seen by this hemlcube. The algorithm then sim-
`ply surttmates all the hernlcubc element fottn {actors associated with each patch.
`The method can be surnrnariaed in the following stages:
`
`(1) Computation of the form factors. Fe. Each herniculie eutplacerneatt
`calculates {tr-1) torrn factors or one row in the equation.
`
`{2} Solving the radlosity matrix equation.
`[3] Rendering by in|ectirtg the results of stage {2} into a iillinear htterpalatloti
`scheme.
`
`{4} Repeating stages {2} and {3} for the colour bands of Interest.
`
`Patdtj
`
`F_.nar,+aF..+ai-'_ -i-fir;
`
`up
`
`IIIIIIIII-‘Ii.
`
`figurI'I1.-I
`Fri: obtained b-]|'Sl.li'l'II'I'IirIg
`I.|'IIeforrn factors oitlte
`plat-isontmvtichpatrhl
`preterit
`
`0333
`
`

`
`tom Mctoa ocreemmmon @
`
`This process is shown in Figure ll.6. Fonn factors are a. function only of the
`environment and are calculated once only and can be reused in stage {2} for dif-
`ferent retiectitrities and light source values. Thus a solution can be obtained for
`the same entrironment with, for example, some light sources turned oil’. The
`solution protlwced by stage [2] is a View-independent solution and if a different
`triettr is required then only stage {3} is repeated. This approach can be useci, for
`example, when generating an animated waliothrotigh of a building interior.
`Each frame in tire animation is computed by changing the view point and cai-
`culating a new 'ii"lE'i|i from an unchanging radlosity solution. It is only it’ we
`change the geometry of the scene that a re-calculation or the form factors is nec-
`essary. if the lighting is changed and the geometry is unaltered, then only the
`equation needs resolving - we do not have to recalculate the font: factors.
`Stage {2} implies the oomputation of a view-independent rendered version of
`the solution to the radioslty equation which supplies a single value, a ratiiosity.
`for each patch in the environment. From these values vertex raciiositles are ca]-
`culateci and these vertex rariiosities are used In the biiinear interpolation scheme
`to provide a final image. A depth huifer algorithm is used at this stage to evalu-
`ate the Vllllllllljf of each patch at each pixel on the screen. (This stage should not
`be confused with the hernicube operation that has to evaluate inter-patch visi-
`bility during the computation oi form factors.)
`The time taken to complete the tons: factor calculation depends on the square
`of the number of patches. it hemicube calculation is perfonned for every patch
`{onto which all other patches are projected). The overall calculation time thus
`depends on the -complexity of the environorent and the acctuacy oi the solution.
`
`0334
`
`

`
`@ 'l'H£ IADiDilT1" Memoo
`
`as determined by the hernieube resolution. Although diffuse illumination
`changesonlyrslowljvacroasaourfaoeallasmgeanbeeauaedbytoolow;
`hemieube resolution and accuracy is required at shadow boundaries {see Section
`11.1’). Storage requirements. are also a function of the number of patches
`required. All these factors mean that there Is an upward limit on the complexity
`of the scenes that can be handled by the radioslty method:
`
`@)
`
`The Gauss—5ledel rnethod
`
`Cohen and Greenberg (1985} point out that the Gauss-Giedel method is guaran.
`heed to converge rapidly tor equation sets such as Equation 11.1. The sum of any
`row of form factors is by defmitlon less than unity and each form faster 1:
`multiplied by a reileetivlty of less than one. The summation of the row terms in
`Equation 11.1 {excluding the main diagonal term} is thus less than unity. The
`mean diagonal term is always unity (Fe = 0 for all it and these conditions sun.
`antee fast convergence. The Gauss-Siedel method is an extension to the follow-
`ing iterative method. Given a aystent of linear equations:
`Ax-E
`
`such as Equation 11.1, we can rewrite equations for XI. 11, . . .. in in the form:
`
`X:
`
`= E:-aux:-aux:-...-alum
`in
`
`which leadii to the Iteration:
`
`mm, = E:-anxz'"" -no-ta-.. .-an-x-‘”
`
`in general:
`
`MIMI: .Et-fln.I!t“’—. . .
`
`This formula can be used in an iteration procedure:
`
`{1} Choose an initial approttlmation, say:
`E.
`N“-—as
`
`foriu1,2,..-,n,whet'e£;Ianon-torunlttingruiiaoesorlightsourcuordr.
`{2} Detetminethenext iterate:
`xé‘*"fromxr“‘
`
`ualng Equation 11.2.
`
`[3]
`
`Iflx.r-N’-xl"I< athreshold
`f-D1'i=1,2, ...,fl
`
`then stop the iteration, otherwise return to step tz].
`
`0335
`
`

`
`sremr: A raI'rIaL sottrnorr - raooaesstvr IEFINEHENT @
`
`1111s is known as Jacobi iteration. The Gauss-Eiedei method improves on the
`convergence of this method by rnodiiying Equation 11.2 to use the latest avail-
`able in formation. when the new iterate xr""“ is being calculated. new values:
`
`x1rrn1r_ _hrr.tr_ _
`
`_
`
`_
`
`_ Intro:
`
`have already been calculated and Equation 11.2 is modified to:
`
`- __
`El - flr:|XI“"'" - .
`.
`. - I-‘-‘at-I-’I.'I-t“"" - fi‘r.rrr.li.1""‘-. + . - in. x.'''
`tie
`
`xF'”
`
`[1 I .3]
`
`Note that when i - 1 the right-hand side at the equation contains tertrts with
`superscript it only, and Equation 11.3 reduces to Equation li.2. When in rt the
`right-ha.rid side contains terms with superscript r.t+1} only.
`Convergence of the Gauss-Siedei method can be improved by the following
`method. Having produced a new value all”, a better value is given by a weighted
`average of the old and new values:
`
`xi”-"'= rxr"""' + [l — r].:r.P'
`
`where r [:0] is a parameter independent of it and 1. Cohen er oi‘. [1933] report
`that a relaxation factor of 1.1 worlts for most environments.
`
`Seeing a partial solution - progressive refinement
`
`Using the radiosity method in a practical context. such as in the design of build-
`lng interiors, means that the designer has to wait a long time to see a completed
`image. This is disadvantageous since one oi the rtrisnrrs d'étre of computer-based
`design is to allow the user tree and East experimentation with the design pa»
`rameters. A long feedback time discourages experimentation and stuitiiies the
`design process.
`In 1938 the Cornell team developed an approach. called ‘progressive refine-
`ment’ that enabled a designer to see an early {but approximate] solution. at this
`stage ma|or errors can be seen and oorrected. and another solution executed. as
`the solution beoomes more and more aocur-ate, the designer may see more sub-
`tle changes that have to be made. We introduced this method in the previous
`chapter. we will now look at the details.
`'l'he general goal of progressive or adaptive refinement can be taken up by any
`slow image synthesis technique and it attempts to Find a oompromise between
`the competing demands of interactivity and image quality. A synthesis rrtethoci
`that provides adaptive refinement would present an initial quickly rendered
`image to the user. This image is then progressively refined in a ‘graceful’ way.
`'l'his is defined as a progression towards higher quality, greater realism etc., in a
`way that is atrtornatic, continuous and not distracting to the user. Early avail-
`ability ot an approrrlmation can greatly assist in the development of techniques
`and images, and reducing the teedbacit loop by approxirnatlnn is a necessary
`adiunct to the rariiosity method.
`
`0336
`
`

`
`'ri-is iriuriosirr METHOD
`
`The ma major cost factors in the rariicisitjr method are the storage costs and
`the calculation of the form factors. For an environment of SD x 103 patches, even
`although the resulting square matrix of form factors maybe 9|J‘lii sparse {many
`patches cannot see each other} this still requires 109 bytes of storage (at Eon;
`bvies per Eonn factor].
`Both the requirements at progressive refinement and the elirniriation oi
`prre-calculation and storage of the form factors are met by an ingenious restruc-
`turing of the basic rarliosity algorithm. The stages in the progressive refinement
`are obtained by displaying the results as the iterative solution progresses. The
`solution is restructured and the form factor evaluation order is optimizecl so that
`the convergence is ‘visually graceful’. This restructuring enables the radiosltv
`of all patches to be updated at each step in the solution, rather than a step
`providing the solution for a single patch. Maximum visual diiierertce between
`steps in the solution can be achieved by processing patches according
`to their energy contribution to the environment. The radlosity method is
`particularly suited to a progressive refinement approach because it computes
`a view-indieperident solution. Viewing this solution {I1}! rendering from a
`particular view point} can proceed independently as the radioslty solution
`progresses.
`In the conventional evaluation of the radiositv matrix (rising. for example,
`the Gauss-seidei method) a solution for one row provides the racitositv for a
`single patch i:
`
`BilEi+.lij§_.Bj.Fs
`
`This is an estimate of the radiositv of patch ihased on the current estimate of all
`other patches. This is called ‘gathering’. The equation means that (algorithmi-
`ca]]j.r] for patch free visit event other patch in the scene and transfer the appro-
`priate amount of light from each patch I to patch if according to the form factor.
`The algorithm proceeds on a row-by-row hasis and the entire solution is updated
`for one step through the matrix iaititorugh the Gauss—5eiciel method uses the
`i1eiv values as soon as they are computed}. if the process is viewed dynamically.
`as the solution proceeds, each patch intensity is updated according to its row
`position in the majority matrix. Light is gathered tron-i every other patch in the
`scene and used to update the single patch currently being considered.
`The idea oi the progressive reilnemerit method is that the entire image of
`all patches is updated at every iteration. Thzis is tens:-ed ‘shooting’, where
`the contribution from each patch i is distributed to all other patch. The dif-
`ference between these two processes is illustrated cilagrarriatlcailv in Figures
`li.?'[a] and {is}. This re-ordering of the algorithm is accomplished in the follow-
`ing way.
`A single term detennlnes the contrihtrtlon to the radlosliy of patch 17 due ID
`that from patch 1':
`
`Bi dueto B;=lipBiFii
`
`0337
`
`

`
`SEEING A iuutmt sotunon — ritoonrsswt iteriutmtur
`
`(El?)
`
`Chlhei'hi,3:|sln,glniiei'fli1li[-il"lldIteaIsinq,iep1iehihy
`],I1IEl.'lI13 coliirilauliuu fmmaiiuihrrpliclna.
`
`Sliontiugrlainzleitepeoniptliealormfiarizorafromiiieshootirig
`pattJttoIHreouivin.gpatcl|eeanddisirilIiies[il1slIct}cIIcrxy AB‘.
`
`is
`,.
`a.“*"= Er-s it, Elaine"
`
`= Hfl
`
`iorailjt
`a,e+'i= sign + it,i=_....iiiI.
`
`Eqtuitairmtogaiheringiigiuenemr
`rruunaliiiiepaiciiesiaiiiewaie.
`
`Eq-ahrnlenitinaiiootinxliglitatlemrfirntn
`apudiwallodiapauiiuinflicsouie.
`
`ea’
`
`[H1 Gaihcfifll
`
`#51:.
`
`{bl 3l1fl'D|1|'|.l
`
`Fiiiure 11-?
`to tiattieuing and
`taisiiooti-igsmaaiasity
`mm an an igmmm h
`Cohen et ai. (1938)).
`
`This relationship can be reversed by using the reciprocity relationship:
`
`H; dueto B:=RiBtFubiAi
`and this is true for all patches I. This relationship can be used to determine the
`contribution to each patch i‘ In the environment [ruin the single patch r'. all sin‘
`gle radiosltjr {patch 3] shoots light into the environment and the radlositles of all
`patches _.I' are updated slniultaneousiy. The first complete update {oi all the
`radiosities in the ert'I-'i|'oni'nent] is obtained from ‘on the i1}r' form factor C0\l'.l.'ipLl-
`tations. Thus an initial approxlrnation to the complete scene can appear when
`only the first row of form factors has been calculated. This eliminates high start-
`up or pre-calculation costs.
`This process is repeated until convergence is achieved. All radiosliies are ini-
`tially set either to zero or to their emission values. its this process is repeated for
`each patch l the solution is displayed and at each step the tadiosihes for each
`patch _i' are updated. its the solution progresses the estimate of the radio.-.it-y at a
`patch 1' becomes more and more accurate. For an iteration the environment
`already contains the contribution of the pcretrious eslirrtate of ii,- and the so-called
`'unsl1ort' radiostty — the difference between the current and previous estimates —
`is all that is injected into the entrironmenr.
`it the output fiorn the algorithm is displayed without further elaboration,
`then a scene. initially dark, gradually gets lighter as the incremental tadiosities
`are added to each patch. The ‘visual convergence’ oi‘ this prticess can be
`
`0338
`
`

`
`-nte tutoiositr iuitntoo
`
`optimized by sorting the order in which the patches are processed according ta
`tlte amount of energy that they are likely to radiate. This means, for exai'i:iple_
`that emitting patches, or light sources, should be treated first. This gives an early
`well lit solution. The next patches to be processed are those that received most
`light from the light sources and so on. By using this ordering scheme. the solu-
`tion proceeds in a way that approidn-rates the propagation of light through an
`environment. Although this produces a better visual sequence than an unsorted
`process, the solution still progresses from a dark scene to a iuliy illuminated
`scene. To overcome this effect an arbitrary ambient light term is added to the
`intermediate radlosities. This items is used only to enhance the display and is not
`part of the solution. The value of the ambient tenn is based on the current eso-
`maie oi the radioslties of all patches in the environment, and as the solution
`proceeds and becom ‘better lit‘ the ambient contribution is decreased.
`Four main stages are completed for each iteration in the algorithm. These are:
`
`it) Find the patch with the greatest (unshoti radlosity or emitted energy.
`(1) Evaluate a column of form factors, that is, the form factors from this patch
`to every other patch in the environment.
`
`{3} Update the radios-ity of each of the receiving patches.
`
`{4} Reduce the temporary attihieni term as a function oi the sum of the
`differences between the current values calculated in step (31 and the
`previous values.
`
`An example of the progressive refinement during execution is shown in Figure
`11].? and Section 1ii.3.2 contains a full description of this iigute.
`
`Problems with the radlosity method
`
`There are three significant problems associated with radiosity tendering. 'I‘hey
`are algorithm arteiacis that appear in the image, the inability to deal with spec-
`ular interaction and the inordinate tin-ie talten to render a scene of moderate
`
`complexity. Curiousty, hardly any research effort has been devoted to the lime
`factor, and this is perhaps the reason that radiosity has not generally migrated
`into applications programs This contrasts with the situation in ray tracing
`research in the 19305, where quite soon after the first ray isaced imagery
`appeared, a large and energetic research eifon was devoted to making the
`method faster. In the remainder of the chapter we will deal exclusively with
`image quality, rioting in passing that it is usually related to execution tlrne -
`quality can be improved by defining the scene more accurately which in the
`mainstream method moans allowing more ltetafions in the program.
`Developments in the radiosity method beyond the techniques described In
`the previous chapter have mostly been motivated by defects or artefacts that
`arise out of the representation of the scene as a set of iargish patches. itltisough
`other factors. such as taking into account scattering atmospheres and the incor-
`
`0339
`
`

`
`aarssscrs IN ttanioslrr Iwuoss
`
`pnratloti of specular 1'E'El.ECl:lD2IJ. are importaiztt. addressing the visual defects due
`to meshing accounts for most research emphasis and it is with this aspect that
`we will deal.
`
`ufcts nrdlos lmas
`
`The common artefacts in rarliosity images that use the classical approach of the
`previous chapter are due to:
`
`(I) hpproicimatlons in the hemicube method for determining the form factors.
`
`{2} Using biiinear interpolation as a reconstruction of the radioslty function
`front the oonstant radiosity solution.
`
`{3} Using a meshing or subdivision of the scene that is Independent of the
`nature of the variations in the radiosity function.
`
`‘I111.-. visibility and thus the importance of these depends, of course, on the nature
`or the scene; but usually the third category is the most noticeable and the most
`diiiicult to deal with. in practice the arteiacts cannot be treated independently:
`there is little point in developing a powerful meshing strategy without also deal-
`ing with arts-facts that emerge from bilinear interpolation. We will now look at
`these image defects detailing both the cause and the possible cure.
`
`Hemlcube artefacts
`
`The serious problem of the hemlcube method is aliasing caused by the regular
`division of the hemicube into uriiforrn pixels. Errors occur as a function of the
`size of the hemicube pixels due to the assumption that patches will project
`exactly onto an integer number of pixels, which in general, of course, they do
`not. This is similar to aliasing in ray tracing. We attempt to gather information
`from a thnee-dimensional environment by looking in a hired number of direc-
`tions. In ray tracing these directions are given initially by evenly spaced eye-to-
`phrei rays. in the radiosity method, by projecting the patches onto hemicuh-es
`we are effectively sampling with projection rays from the hernicube origin.
`Figure 11.3 shows a two-dimensional analogue of the problem where a number
`of identical polygons project onto either one or two pixels depending on the
`interference between the projection rays and the polygon grid. The polygons are
`of equal size and equal orientation with respect to patch I. Their form factors
`should be different — because the number at‘ pixels onto which each polygon
`projects is different for each polygon. However. as the example shows, neigh-
`bouring polygons which should have almost equal form factors will produce
`values in the ratio 2:1.
`
`The geometry of any practical scene can cause problems with the hemicube
`method. its accuracy depends on the distance between the patches involved In
`the calculation. When distances become small the method falls down. This
`
`0340
`
`

`
`(iii) Ti-IE eamosm iusruoo
`
`lternitube sampling and a
`set of equal polygons (alt-er
`Wallace It at‘. [1939]].
`
`-1—-—-T
`Dinueu from
`henicuhe origin
`lltueues
`
`er-
`Dilllncefrum
`belri-l:l.IhetI'l3iI
`
`Nuniberolpirek
`Iiutb.d.f.lI.j
`pru'p:tonto
`
`Nlntibnmfpiazeis
`IhIJI.e.e.g.i
`prltflectorito
`
`situation occurs in practice, for example, when an oblect is placed on a support.
`ing surface. The errors in fiorrn factors occur precisely in those regions from
`which we expect the radloiity technique to excel and produce subtle phenom-
`ena such as colour bleeding and soft shadows. liaum er oi. iislfliil quantify the
`error involved in form factor determination for proximal surfaces. and demon-
`strate the heruicube method is only accurate in contexts where the inner-peed:
`distance is at least five paicit diameters.
`‘let another hemicube problem ciccurs with light sources. in scenes which the
`radiosity method is used to render, we are usually concerned with area sources
`such as fluorescent Eights. As intith any other surface In the environment we divide
`the light sources into patches and herein lies the problem. For a standard solution
`an environment will be dlscreifleed into patches where the subdivision resolution
`depends on the area of surface (and the accuracy of the solution required}.
`However, in the case or light sources the number of hernicubes required or the
`number of patches required depends on the distance front the closest surface it
`illuminates. it hemicube operation effectively reduces an emitting patch to a
`point source. Errors will appear on a close surface as isolated areas of light if the
`light source is insuflicientiy subdivided. with strip lights. where the length to
`breadth ratio is great. insufiicient subdivision can give rise to banding or aliasing
`artelacts that run parallel Witlt the long axis of the light source. An example of
`the effect of insuificient light source subdivision is shcmrn in Figure 11.14.
`Hernicube aliasing can. of course. be ameliorated by increasing the rest:-lutlml
`of the herrilcube, but this is ineflicient, increasing the computation required for
`all elements in the scene irrespective of whether they are allased by the .
`hemicube or not; eitactly the same situation which occurs with conventional
`{context independent} anti-aliasing measures (Chapter 14].
`
`'
`
`0341
`
`

`
`atrsnrrrs IN ruiotosrrir Inuuses (33)
`
`Problems emerge from the approxjination {see the previous chapter}:
`
`-Fl"'Fd.»l.W
`
`The hemicube evaluates a form factor from a differential area - effectively a
`point — to a finite area. There are two consequences of this. Figure 11.9 illustrates
`a problem that can arise with intervening patches. Here the form [actor from
`patch ito patch I is calculated as If the intervening patch did not exist because
`patch 1 can be seen in its entirety from the he-micube origin.
`Finally, consider the sampling 'eEflcienc}r' of the hernieube- Patches that can
`be 'seen’ from the hemiculie in the normal direction are more important than
`patches in the horizon clirectlon. i,"l"he3r pru|et:t onto l'l.vEl:l:l.iCl.ll‘.'IIE cells that have
`higher delta form iactors.) If we oonsider distributing the computational effort
`evenly on the basis of importance sampling then cells nearer the horizon are less
`important. an investigation reported in Hart and Irouunan [1993] derives opti-
`mal resolution. shapes and grid cell spacings. in this work a top-face resolution
`40% higher than that oi the sides and a side height of ?i}% of the width is
`suggested. Note that this leads also to a reclucclon in aliasing artefacts caused by
`uniform hemtcube cells.
`
`Reconstruction artefacts
`
`Reconstruction artefacts are so called because they originate from the nature of
`the method used to reconstruct or approximate the continuous l'al1lO5lt]l' func-
`tion from the constant racliosity solution. We recall that raiiiosltjr methods can
`only iunction under the constant radiosityr assumption which Is that we divide
`the environment up into patches and solve a system of equations on the basis
`that the racliosity is constant across each patch.
`The commonest approach — bilinear interpolation - is overviev-red in Figure
`11.111 Here we assume that the curved surface shown in Figure ll.'i0{a]- will
`exhibit a continuous variation in radiosity value along the dotted line as shown.
`
`W!-|l'!‘l‘l.9
`Illufpltcltfclnb-Issm
`lfllnthchntnictlaaoiigitt
`Idlhsfiwlflflmtimathn
`llsdown.
`
`0342
`
`

`
`(E2) mt nmurmr suntan
`
`Flgure11.1III
`NOl'1'I‘d-|'HD|'|$1.I'L|C.|.iCI'|
`qrproavch used hlhe
`rar:liosityrnelhot:l.
`[I] compute a constant
`ndosiq solution.
`(hi Calculate the vertex
`radiosities.
`(:1 I1-eenrtstrur.tlan by linear
`interpolation,
`
`B.- - 'MB‘.+ 3.1- .fl¢.+ 3;}
`
`IL‘)
`
`The first step in the radiosity method is to compute a constant raclioslty solution
`which will result III a staircase approximation to the continuous function. The
`radinslty values at a vertex are calculate-:1 by averaging the patch radiositles that
`share the trettex (Figure 1l.1Il]{h]}. These are then lnlected into a billnear inter-
`polation scheme and me surface is effectitreljr Gourautl shacled resulting in the
`piecewise linear approximation {Figure 11.1i1(c}J.
`The most noticeable defect arising out of this process is Mach bands which.
`of oourse, we also eatperienoe in normal Goutaud shading, where the same inter-
`polation method is used. The ‘visual trnpm-tanoe' nl‘ these can be reduced by
`using texture mapping but they tend to be it problem in radiosity applications
`because many of these exi1.li:lt large area tnextureless surfaces - interior walls in
`huhdlngs, for example. Subdivision meshing strategies also reduce the visibility
`
`0343
`
`

`
`aarsracrs IN il.il.i‘.'IIOsIT'i‘ tmusss (E)
`
`of Mach bands because by reducing the size of the elements they reduce the
`difference between vertex radiosities.
`
`More advanced strategies involve surfaoe interpolation methods {Chapter 3].
`Here the radiosity values are treated as samples of a continuous radiosity func-
`tion and quadratic or cubic flézlerrtll--spline patch meshes are fitted to these. The
`obvious diificuliies with this approach - its inherent cost and the need to
`prevent wanted discontinuities being smoothed out - has meant that the most
`popular reconstruction method Is still linear interpolation.
`
`Meshing artefacts
`
`,
`
`One of the most d.|.lfir.1.IIt aspects of the tadiotslty approach, and one that is still
`a rnalor research area, is the issue of meshing. in the discussions above we have
`simply described patches as entities Into which the scene is divided with the pro-
`viso that these should be large to enable a solution which is not prohibitively
`expensive. Howesrer, the way in which we do this has a strong bearing on the
`quality of the final image. How should we do this so that the appearance of
`artefacts is minimized? The reason this is difficult
`is that we can only do
`this when we already have a solution. so that we can see where the problems
`occur. Alternatively we have to predict where the problems will occur and sub
`divide accordingly. We begin by iooiiing at the nature and origin of meshing
`arteiacts.
`
`Fifi!‘ SOHIE T£'l'1'l'llI'lOl‘.".|g}":
`
`I Meshing This is a general term used in the context of ratilosity to describe
`either the initial scene subdivision or the act of further subdivision that may
`take place while a program is executing. The ‘initial scene subdivision’ may
`be a general scene database not necessarily created for input to a radiosity
`tenderer. However, for reasons that will soon become apparent It is more
`likely to be a preprocessed version of such a database or a scene that has
`been specifically created for a radiosity solution.
`
`Patches These are the entities in the initial representation of the scene.
`in a standard radioslty solution, where subdivision occurs during the
`solution. patches form the input to the program.
`
`I Elements These are the portions into which patches are subdivided.
`
`The simplest type of meshing artetact — a so-called D“ discontinuity — is a dis-
`continuity in the value oi‘ the racliosity function. The common sources of such
`a discontinuity are shadow boundaries caused by a point light source and objects
`which are in contact. in the tonne: case the light source suddenly becomes vis-
`ible as we move across a surface and the reoonstniction and meshing "spreads'
`the shadow edge inwards the mesh boundaries. Thus the shadow edge will tend
`to taint the shape of the mesh edges giving it a staircase appearance. However,
`because we tend to use area light sources in radiosity applications the disconn-
`nuitles that occur are higher than D“. Nevertheless these still cause visible
`
`0344
`
`

`
`‘rue uoloslnr Mrmoo
`
`rlgun 'i'i.'l'l
`Slredor-rand Ight heirlge.
`
`artefaets. Disoontinuities In the tiertvaurrea of the radloeity function occur at
`penumbra and umhra boundaries in shadow: in scenes illuminated by area light
`sources. Again therets 'inieeEerertce’betweventh:ebourtdarie:tantIihenauh,gi|t'-
`ing a characteristic ‘staircase’ appearance to the shadow edges. These are more
`diI.‘fit-nit to deal with than D“ discontinuities.
`
`When otlieets are in contact, then unless the intersection boundary ooineidet
`withamesh boundary, shadawocl-llghtieaitager-ri]]occt:r."i'heideaisshownto
`Figure 11.1] for a simple scene. Here, the room Is divided by a floor-to-ceiling
`partition, which does not coincide with patch boundaries on the door. One half
`of the room contain: a light souroe end the other is completely dark. Depending
`on the position or the patch boundaries, the recortrtruetion will prodooe either
`light leakage into the dark region or shadow leakage into the lit region. Figflfl‘-'
`13.16 shows the effect of shadow and light leakage for a more compiea stem-
`Despite the fact that the representation contains many more patches than we
`
`0345
`
`

`
`irltsiiino sriursoies @
`
`require for a conventional computer graphics rendering i-Gouraud shorting) the
`quality is unacceptably low.
`it should be apparent that iurther subdivision of the scene cannot entirely
`eliminate shadow and light leakage — it can only reduce it to an acceptable level.
`it can, however. be eliminated entirely by forcing a meshing along the curve of
`intersection between objects in contact. Figure 13.13 is the result of meshing the
`area around a wall light by considering the intersection between the lamp and
`the wau. Now the wall patch boundaries oolocide with the lamp patch bound+
`aries eliminating the leakage that occurred before this meshing.
`
`@”r""' ' “' “‘a.i:..'.-...,, strategies
`
`Meshing strategies that attempt to overcome these cietccts can be categorized In
`a number of ways. An important distinction can he made on the basis of when
`the subdivision takes place:
`
`(1)
`
`it priorf - meshing is completed before the rariiosiry solution is Invoked: that
`is we predict where discontinuities are going to occur and mesh accordingly.
`This is also called discontinuity meshing.
`[2] A posterior-i — the solution is Initiated with a ‘start’ rnesh which is refined as
`the solution progresses. This is also called adaptive meshing.
`
`as we have seen, when two ohiects are in contact, we can eliminate shadow
`and light leakage by ensuring that mesh element boundaries from each obit-ct
`coincide, which is thus an H piioii hlrtg.
`Another distinction can be made depending on the geometric nature of the
`meshing. We can, for example, simply subdivide square patches {non-uniformly}
`reducing the error to an acceptable level. The commonest approach to date,
`Cohen and Wallace [I993] term this ii--refi nement. iitlternatlireiry we could adopt
`an approach where the discontinuities in the radloslty function are tracked
`across a surfaoe and the mesh boundaries placed along the discontinuity bound-
`ary. A four: of this approach is called r-refinement by Cohen and Wallace [1993]
`where the nodes of the initial mesh are moved in a way that equaiiaes the error
`in the elements that share the node. These approaches are illustrated corice1:itu-
`ally in Figure 11.12.
`
`Adaptive or o porteriori irieshing
`
`The classic adaptive algorithm, called substructuring, was described by Cohen. et
`ai. (1936). Reported before the detreloprner-it of the progressive refinement algo-
`rithm, this approach was initially Incorporated into a full matrix solution.
`Adaptive subdivision prooeeds by considering the radlosity variation at the
`nodes or vertlces of an element and subdividing ii‘ the diiference exceeds sortie
`threshold.
`
`0346
`
`

`
`THE naulomv memon
`
`Figur|11.12
`Enu1'q'Jh:<:uf|'el’n'Ierneu'rl
`strategies In pumdmtu.
`
`The idea is to generate an accurate solution for the radioslty of I point fl'Dl1|
`the ‘giuhaf redlositles obtained from the lnltial ‘coarse’ patch computation.
`Patches are sub-dlvlded lnbn elements. Element-to-patch Eonn factors are calcu-
`lated where the relatiernsllip between element-to-patch and patch-tn-patch form
`Eactotsisglvenhjr:
`I
`Fgsfili E Faulty]
`1-I
`
`0347
`
`

`
`Mesnmc. srutsarss @
`
`where:
`
`F; is the ionn factor from patch i to patch if
`F” is the form [actor from element q of patch I to patch _f
`As.» is the subdiviried area of element q of patch i
`it is the number of elements in patch i
`
`Patch fiorcrt factors obtained in this way are then used in a standard radiosity
`solution.
`
`This increases the number of form factors Etc:-in N