Last Time Radiosity Converting the LTE into the radiosity equation Solving with Gauss Seidel relaxation Form factor computations 02 18 05 2005 University of Wisconsin Today Progressive Radiosity Assorted optimizations 02 18 05 2005 University of Wisconsin Problems with Gauss Seidel All the form factors are required before any image can be generated So you wait a long time to see anything Reducing the number of form factors requires reducing the number of patches which severely impacts quality We desire a progressive solution that starts with a rough approximation and refines it This also opens the possibility of computing some pieces the bits you can see before others 02 18 05 2005 University of Wisconsin Radiosity Eqn to Energy Eqn The radiosity equation is in terms of power per unit area Rewrite this equation in terms of energy values per patch instead of per unit area Bi Ei i j i B j Fij for 1 i N Let i Ai Bi i Ai Ei j Ai Bi Ai Ei i j i Ai Fij Aj i i i j i j F ji Note that the form factor is now from j to i K with K ij ij i F ji 02 18 05 2005 University of Wisconsin Relaxation and Residuals Relaxation methods start with an initial guess 0 and perform a sequence of relaxation steps each resulting in a new k The residual is defined as r k K k At each step relaxation methods zero one element of the residual e g Gauss Seidel zeros each one in turn Note the residual is zero when the equation is solved 02 18 05 2005 University of Wisconsin Southwell Relaxation Southwell relaxation zeros the largest residual at each step 0 ri k 1 i N k 1 K ij j j 1 j i j k 1 j k k 1 i i k 1 02 18 05 k i K ij j j i ri k k i K ii 1 K ii We can update the radiosity for the patch i in a single step But we need to update all the other residuals 2005 University of Wisconsin Updating Residuals r k 1 j j N Using the definition of residuals k 1 K jm m m 1 rj k N k 1 k K jm m m m 1 Note that only one component of changed i Hence we only need one element of K for every j one row in total r 02 18 05 k 1 j r k j K ji k 1 i k i r k j 2005 University of Wisconsin K ji K ii ri k Southwell Summary Each patch has two components energy ik and undistributed energy rik Start with some i0 and hence ri0 At each step k 1 Choose the i with maximum residual Update ik 1 and rik 1 0 Update all the rjk 1 02 18 05 2005 University of Wisconsin Physical Interpretation Assume that all the initial patch energies are 0 Then the initial residuals are the amounts of energy to be emitted by each patch Each step redistributes the residual according to rj k 1 rj k j Fij ri k Recall the form factor Fij is the amount of power radiated by i that j receives So each patch gets its own share of the residual that is shot according to the form factors 02 18 05 2005 University of Wisconsin Gathering and Shooting Gauss Seidel gathers radiosity from every patch to a specific patch k 1 i B Ei i B Fij k j j i Southwell shoots energy from one patch onto all the other patches k 1 j r k j r j Fij ri k The terms gathering and shooting are used commonly in the literature Eg do a final gather means gather radiance to the image plane 02 18 05 2005 University of Wisconsin Progressive Refinement After any number of iterations an estimate of each patch s final energy can be obtained by Bi k i k ri k Ai These intermediate results can be displayed as the algorithm proceeds giving faster feedback 02 18 05 2005 University of Wisconsin Typical Equations Typically work in terms of radiosity which result in equations similar to those from the previous slides Define radiosity and un shot radiosity i k ri k Bi Ai ri k Bi Ai k r On each step find the highest residual i Ai Bi Compute all the form factors out of patch i Continued 02 18 05 2005 University of Wisconsin More Equations Ai B j B j j Fij Bi Aj B j B j j Fij Ai Bi Aj Bi 0 Display partial solution by displaying Bj 02 18 05 2005 University of Wisconsin Ambient Correction Progressive radiosity images look dark at first because shooters hold onto their energy until it s their turn An ambient correction can be added to the display only N 1 i RU k R U rj Bi N 1 avg j 1 Ai i 1 02 18 05 2005 University of Wisconsin The Effect of Patch Size There is a trade off in patch size large patches give faster solution small patches give better results Doubling the patch resolution increases computation by 16x 4x in each patch but N2 computation so 16x Effect of large patches is most obvious in receiving patch size indicates largest resolvable illumination feature Particularly important when Large patches are not so bad for emitting What impact will large vs small patches have 02 18 05 2005 University of Wisconsin Shooting to Vertices Standard progressive radiosity shoots from points to areas Point is middle of shooting patch Area is the area of a receiving element Better to shoot from area to points 02 18 05 Area is source patch point is receiving vertex Progressive radiosity really needs Fji Less aliasing under certain circumstances Radiosity is needed at vertices for display Greater control over receivers 2005 University of Wisconsin Ray casting For Form Factors Aim compute Fy Pi cos cos V x y dx 2 x Pi r Cast rays from y to sub patches Pik of Pi Ray determines constant visibility for each sub patch ni Then Fy Pi k 1Vk Fk cos cos Fk k dx 2 x Pi r Not Monte Carlo but similar 02 18 05 2005 University of Wisconsin Delta Form Factors We need to compute Fk Several possibilities Assume constant evaluated using angles and radius for a point at the center of the patch can be very bad Use analytic methods point polygon costly Use disc approximation Assume sub patch is a small disc Form factor for point disc is known u2 Fy disc 2 2 u 2 Aik v r u v Aik cos cos Fk Aik r 2 02 18 05 2005 University of Wisconsin Automated Meshing The patch and element resolution should be decided based on the complexity of the illumination situation It is unreasonable to expect a user to know what is required they are after all using the software to find a solution Automated meshing strategies are desired 02 18 05 …