{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T09:43:40Z","timestamp":1648892620998},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2001,10]]},"abstract":"\n Many key problems in computer graphics require the computation of integrals. Due to the nature of the integrand and of the domain of integration, these integrals seldom can be computed analytically. As a result, numerical techniques are used to find approximate solutions to these problems. While the numerical analysis literature offers many integration techniques, the choice of which method to use for specific computer graphic problems is a difficult one. This choice must be driven by the numerical efficiency of the method, and ultimately, by its visual impact on the computed image. In this paper, we begin to address these issues by methodically analyzing deterministic and stochastic numerical techniques and their application to the type of one-dimensional problems that occur in computer graphics, especially in the context of linear light source integration. In addition to traditional methods such as Gauss-Legendre quadratures, we also examine Voronoi diagram-based sampling, jittered quadratures, random offset quadratures, weighted Monte Carlo, and a newly introduced method of compounding known as a\n difficulty driven compound quadrature<\/jats:italic>\n .We compare the effectiveness of these methods using a three-pronged approach. First, we compare the frequency domain characteristics of all the methods using periodograms. Next, applying ideas found in the numerical analysis literature, we examine the numerical and visual performance profiles of these methods for seven different one-parameter problem families. We then present results from the application of the methods for the example of linear light sources. Finally, we summarize the relative effectiveness of the methods surveyed, showing the potential power of difficulty-driven compound quadratures.\n <\/jats:p>","DOI":"10.1145\/502783.502785","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:29:00Z","timestamp":1027769340000},"page":"232-279","source":"Crossref","is-referenced-by-count":5,"title":["On numerical solutions to one-dimensional integration problems with applications to linear light sources"],"prefix":"10.1145","volume":"20","author":[{"given":"Marc J.","family":"Ouellette","sequence":"first","affiliation":[{"name":"University of Toronto, Toronto, Ont., Canada"}]},{"given":"Eugene","family":"Fiume","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, Ont., Canada"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/7529.8927"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"DAVIS P.AND RABINOWITZ P. 1984. Methods of Numerical Integration. Academic Press New York. DAVIS P.AND RABINOWITZ P. 1984. Methods of Numerical Integration. Academic Press New York.","DOI":"10.1016\/B978-0-12-206360-2.50012-1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"C41","DOI":"10.1111\/1467-8659.00396","article-title":"Floating points: A method for computing stipple drawings","volume":"19","author":"DEUSSEN O.","year":"2000","journal-title":"Comput. Graph. Forum"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/325165.325182"},{"key":"e_1_2_1_5_1","first-page":"223","volume-title":"ACM SIGGRAPH '94 Conference Proceedings (August), Annual Conference Series, ACM","author":"DRETTAKIS G.","year":"1994"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01952683"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/311535.311551"},{"key":"e_1_2_1_8_1","first-page":"269","volume-title":"Proceedings of the 11th Eurographics Workshop on Rendering (Brno, Czech Republic), Springer-Verlag\/ Wien, New York, '99 Conference Proceedings (August), Annual Conference Series, ACM","author":"HEIDRICH W.","year":"2000"},{"key":"e_1_2_1_9_1","unstructured":"KAHANER D. MOLER C. AND NASH S. 1989. Numerical Methods and Software. Prentice Hall Englewood Cliffs New Jersey. KAHANER D. MOLER C. AND NASH S. 1989. Numerical Methods and Software. Prentice Hall Englewood Cliffs New Jersey."},{"key":"e_1_2_1_10_1","unstructured":"LYNESS J. 1981. Remarks about Performance Profiles. Tech. Mem. 369 Argonne National Lab Argonne Ill. LYNESS J. 1981. Remarks about Performance Profiles. Tech. Mem. 369 Argonne National Lab Argonne Ill."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/355666.355671"},{"key":"e_1_2_1_12_1","first-page":"94","volume-title":"Graphics Interface '92","author":"MCCOOL M.","year":"1992"},{"key":"e_1_2_1_13_1","unstructured":"MEREDITH-JONES R. 2000. Point sampling algorithms for simulating motion blur. M.S. dissertation University of Toronto Toronto Ont. Canada. MEREDITH-JONES R. 2000. Point sampling algorithms for simulating motion blur. M.S. dissertation University of Toronto Toronto Ont. Canada."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/282918.282938"},{"key":"e_1_2_1_15_1","unstructured":"OUELLETTE M. J. 2002. Numerical methods for illumination integrals. Ph.D. dissertation University of Toronto Toronto Ont. Canada. In preparation. OUELLETTE M. J. 2002. Numerical methods for illumination integrals. Ph.D. dissertation University of Toronto Toronto Ont. Canada. In preparation."},{"key":"e_1_2_1_16_1","first-page":"213 213","volume-title":"Proceedings of the 10th Eurographics Workshop on Rendering","author":"OUELLETTE M.J.","year":"1999"},{"key":"e_1_2_1_17_1","first-page":"66","volume-title":"Graphics Interface '99","author":"OUELLETTE M.J.","year":"1999"},{"key":"e_1_2_1_18_1","first-page":"11","volume-title":"Proceedings of the 11th Eurographics Workshop on Rendering (Brno, Czech Republic), Springer- Verlag\/Wien","author":"PAULY M.","year":"2000"},{"issue":"3","key":"e_1_2_1_19_1","first-page":"377","article-title":"Shading and shadowing with linear light sources. In Eurographics '90","volume":"9","author":"POULIN P.","year":"1990","journal-title":"Comput. Graph., Forum"},{"key":"e_1_2_1_20_1","unstructured":"PRATT W. 1991. Digital Image Processing. John Wiley & Sons New York. PRATT W. 1991. Digital Image Processing. John Wiley & Sons New York."},{"key":"e_1_2_1_21_1","first-page":"213","volume-title":"Proceedings of the 6th Eurographics Workshop on Rendering","author":"RUSHMEIER H.","year":"1995"},{"key":"e_1_2_1_22_1","first-page":"177","volume-title":"Proceedings of the 4th Eurographics Workshop on Rendering","author":"SCHR~DER P.","year":"1993"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"SHIRLEY P. 1991. Physically based lighting calculations for computer graphics. Ph.D. dissertation University of Illinois. SHIRLEY P. 1991. Physically based lighting calculations for computer graphics. Ph.D. dissertation University of Illinois.","DOI":"10.1007\/978-3-662-09287-3_5"},{"key":"e_1_2_1_24_1","unstructured":"SHREIDER Y. 1966. The Monte Carlo Method. Pergamon Press New York. SHREIDER Y. 1966. The Monte Carlo Method. Pergamon Press New York."},{"key":"e_1_2_1_25_1","unstructured":"SOBOL I. 1994. A Primer for the Monte Carlo Method. CRC Press London. SOBOL I. 1994. A Primer for the Monte Carlo Method. CRC Press London."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1036002"},{"key":"e_1_2_1_27_1","first-page":"231","volume-title":"ACM SIGGRAPH '94 Conference Proceedings (August), Annual Conference Series, ACM","author":"STEWART J.A.","year":"1994"},{"key":"e_1_2_1_28_1","unstructured":"TRAUB J. WASILKOWSKI G. AND WOZNIAKOWSKI H. 1998. Information-Based Complexity. Academic Press San Diego Calif. TRAUB J. WASILKOWSKI G. AND WOZNIAKOWSKI H. 1998. Information-Based Complexity. Academic Press San Diego Calif."},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"ULICHNEY R. 1987. Digital Halftoning. MIT Press Cambridge MA. ULICHNEY R. 1987. Digital Halftoning. MIT Press Cambridge MA.","DOI":"10.7551\/mitpress\/2421.001.0001"},{"key":"e_1_2_1_30_1","first-page":"419","volume-title":"ACM SIGGRAPH '95 Conference Proceedings (August), Annual Conference Series, ACM","author":"VEACH E.","year":"1995"},{"key":"e_1_2_1_31_1","first-page":"6","article-title":"Weighted Monte Carlo integration","volume":"15","author":"YAKOWITS S.","year":"1978","journal-title":"SIAM J. Numer. Anal."},{"key":"e_1_2_1_32_1","unstructured":"ZIEMER R.AND TRANTER W. 1990. Principles of Communications: Systems Modulation and Noise 3rd ed. Houghton Mifflin Boston. ZIEMER R.AND TRANTER W. 1990. Principles of Communications: Systems Modulation and Noise 3rd ed. Houghton Mifflin Boston."}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/502783.502785","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,4]],"date-time":"2021-03-04T08:50:35Z","timestamp":1614847835000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/502783.502785"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,10]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2001,10]]}},"alternative-id":["10.1145\/502783.502785"],"URL":"http:\/\/dx.doi.org\/10.1145\/502783.502785","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":["Computer Graphics and Computer-Aided Design"],"published":{"date-parts":[[2001,10]]}}}