%!PS-Adobe-1.0 %%Creator: HOSTESS.GRAPHICS.CS.CMU.EDU:ph (Paul Heckbert) %%Title: stdin %%CreationDate: Wed Jun 15 11:43:14 1994 %%DocumentFonts: Times-Roman Times-Italic Times-Bold Symbol Times-Roman DIThacks %%Pages: (atend) %%EndComments % Start of pscat.pro -- prolog for troff translator % Copyright (c) 1985,1987 Adobe Systems Incorporated. All Rights Reserved. % GOVERNMENT END USERS: See Notice file in TranScript library directory % -- probably /usr/lib/ps/Notice % RCS: $Header: pscat.pro,v 2.2 91/02/21 18:00:13 ern Exp $ % % HISTORY % $Log: pscat.pro,v $ % Revision 2.2 91/02/21 18:00:13 ern % orig % [91/02/20 15:27:53 ern] % % save /pscatsave exch def /$pscat 50 dict def $pscat begin /fm [1 0 0 1 0 0] def /xo 0 def /yo 0 def /M /moveto load def /R /show load def /S {exch currentpoint exch pop moveto show}def /T {exch currentpoint pop exch moveto show}def /U {3 1 roll moveto show}def /siz 0 def /font 0 def /Z {/siz exch def SF}def /F {/font exch def SF}def /SF{font 0 ne {catfonts font 1 sub get fm 0 siz put fm 3 siz neg put fm makefont setfont}if}def /BP{save/catsv exch def 0 792 translate 72 432 div dup neg scale xo yo translate 0 0 moveto}def /EP{catsv restore showpage}def % definitions for PPROC callback functions % each PPROC is called with the following number on the stack: % pointsize charcode railmag pswidth pschar x y wid /$pprocs 50 dict def /fractm [.65 0 0 .6 0 0] def % fractions /PS1{gsave $pprocs begin /wid exch def pop pop pop pop pop /ch exch def /size exch def /pair $pprocs ch get def /cf currentfont def cf fractm makefont setfont 0 .3 size mul 6 mul 2 copy neg rmoveto pair 0 get show rmoveto currentfont cf setfont (\244) show setfont pair 1 get show grestore wid .06 div 0 rmoveto end}def $pprocs begin 8#34 [(1)(4)] def 8#36 [(1)(2)] def 8#46 [(3)(4)] def end % DIThacks fonts for some special chars 50 dict dup begin /FontType 3 def /FontName /DIThacks def /FontMatrix [.001 0.0 0.0 .001 0.0 0.0] def /FontBBox [-220 -280 900 900] def% a lie but ... /Encoding 256 array def 0 1 255{Encoding exch /.notdef put}for Encoding dup 8#040/space put %space dup 8#110/rc put %right ceil dup 8#111/lt put %left top curl dup 8#112/bv put %bold vert dup 8#113/lk put %left mid curl dup 8#114/lb put %left bot curl dup 8#115/rt put %right top curl dup 8#116/rk put %right mid curl dup 8#117/rb put %right bot curl dup 8#120/rf put %right floor dup 8#121/lf put %left floor dup 8#122/lc put %left ceil dup 8#140/sq put %square dup 8#141/bx put %box dup 8#142/ci put %circle dup 8#143/br put %box rule dup 8#144/rn put %root extender dup 8#145/vr put %vertical rule dup 8#146/ob put %outline bullet dup 8#147/bu put %bullet dup 8#150/ru put %rule dup 8#151/ul put %underline pop /DITfd 100 dict def /BuildChar{0 begin /cc exch def /fd exch def /charname fd /Encoding get cc get def /charwid fd /Metrics get charname get def /charproc fd /CharProcs get charname get def charwid 0 fd /FontBBox get aload pop setcachedevice 40 setlinewidth newpath 0 0 moveto gsave charproc grestore end}def /BuildChar load 0 DITfd put %/UniqueID 5 def /CharProcs 50 dict def CharProcs begin /space{}def /.notdef{}def /ru{500 0 rls}def /rn{0 750 moveto 500 0 rls}def /vr{20 800 moveto 0 -770 rls}def /bv{20 800 moveto 0 -1000 rls}def /br{20 770 moveto 0 -1040 rls}def /ul{0 -250 moveto 500 0 rls}def /ob{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath stroke}def /bu{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath fill}def /sq{80 0 rmoveto currentpoint dround newpath moveto 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath stroke}def /bx{80 0 rmoveto currentpoint dround newpath moveto 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath fill}def /ci{355 333 rmoveto currentpoint newpath 333 0 360 arc 50 setlinewidth stroke}def /lt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 add exch s4 a4p stroke}def /lb{20 800 moveto 0 -550 rlineto currx -200 2cx s4 add exch s4 a4p stroke}def /rt{20 -200 moveto 0 550 rlineto currx 800 2cx s4 sub exch s4 a4p stroke}def /rb{20 800 moveto 0 -500 rlineto currx -200 2cx s4 sub exch s4 a4p stroke}def /lk{20 800 moveto 20 300 -280 300 s4 arcto pop pop 1000 sub currentpoint stroke moveto 20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def /rk{20 800 moveto 20 300 320 300 s4 arcto pop pop 1000 sub currentpoint stroke moveto 20 300 4 2 roll s4 a4p 20 -200 lineto stroke}def /lf{20 800 moveto 0 -1000 rlineto s4 0 rls}def /rf{20 800 moveto 0 -1000 rlineto s4 neg 0 rls}def /lc{20 -200 moveto 0 1000 rlineto s4 0 rls}def /rc{20 -200 moveto 0 1000 rlineto s4 neg 0 rls}def end /Metrics 50 dict def Metrics begin /.notdef 0 def /space 500 def /ru 500 def /br 0 def /lt 250 def /lb 250 def /rt 250 def /rb 250 def /lk 250 def /rk 250 def /rc 250 def /lc 250 def /rf 250 def /lf 250 def /bv 250 def /ob 350 def /bu 350 def /ci 750 def /bx 750 def /sq 750 def /rn 500 def /ul 500 def /vr 0 def end DITfd begin /s2 500 def /s4 250 def /s3 333 def /a4p{arcto pop pop pop pop}def /2cx{2 copy exch}def /rls{rlineto stroke}def /currx{currentpoint pop}def /dround{transform round exch round exch itransform} def end end /DIThacks exch definefont pop /catfonts [ /Times-Roman findfont /Times-Italic findfont /Times-Bold findfont /Symbol findfont /Times-Roman findfont /DIThacks findfont ] def %%EndProlog %%Page: ? 1 BP 1 F 60 Z 16 -42(--)U 3259(--)S 3 F 96 Z 1079 654(SURVEY)U 1504(OF)S 1670(TEXTURE)S 2165(MAPPING)S 2 F 60 Z 1642 798(Paul)U 1776(S.)S 1841(Heckbert)S 1710 1215(A)U 1 F 1762 906(PIXAR)U 2 F 1747 1215(BSTRACT)U 1 F 3121 1308(e)U 556 1380(c)U 556 1308(Texture)U 767(mapping)S 1001(is)S 1064(one)S 1173(of)S 1245(the)S 1341(most)S 1480(successful)S 1749(new)S 1871(techniques)S 2151(in)S 2220(high)S 2349(quality)S 2539(image)S 2709(synthesis.)S 2986(Its)S 3068(us)S 583 1380(an)U 662(enhance)S 882(the)S 978(visual)S 1144(richness)S 1363(of)S 1435(raster)S 1591(scan)S 1720(images)S 1913(immensely)S 2200(while)S 2356(entaili)S 2508(ng)S 2590(only)S 2719(a)S 2767(relative)S 2949(ly)S 3017(small)S 556 1524(c)U 556 1452(increase)U 784(in)S 861(computati)S 1103(on.)S 1228(The)S 1352(technique)S 1617(has)S 1726(been)S 1869(applied)S 2076(to)S 2152(a)S 2208(number)S 2421(of)S 2500(surface)S 2703(attribute)S 2905(s:)S 2974(surface)S 583 1524(olor,)U 718(surface)S 915(normal,)S 1124(specularity,)S 1427(transparency,)S 1773(illumina)S 1975(tion,)S 2107(and)S 2217(surface)S 2414(displaceme)S 2686(nt,)S 2771(to)S 2841(name)S 2994(a)S 3043(few.)S 556 1668(c)U 556 1596(Although)U 804(the)S 899(list)S 994(is)S 1055(potential)S 1267(ly)S 1335(endless,)S 1548(the)S 1643(techniques)S 1922(of)S 1993(texture)S 2182(mapping)S 2413(are)S 2507(essentially)S 2782(the)S 2876(same)S 3020(in)S 3087(all)S 583 1668(ases.)U 746(We)S 858(will)S 980(survey)S 1168(the)S 1270(fundamental)S 1572(s)S 1623(of)S 1700(texture)S 1895(mapping,)S 2148(which)S 2322(can)S 2433(be)S 2517(split)S 2648(into)S 2769(two)S 2886(topics:)S 3074(the)S 556 1812(a)U 556 1740(geometric)U 825(mapping)S 1063(that)S 1181(warps)S 1351(a)S 1405(texture)S 1600(onto)S 1734(a)S 1787(surface,)S 2002(and)S 2115(the)S 2215(\256ltering)S 2432(that)S 2549(is)S 2615(necessary)S 2875(in)S 2948(order)S 3101(to)S 583 1812(void)U 710(aliasing.)S 953(An)S 1046(extensive)S 1294(bibliography)S 1622(is)S 1682(included.)S 3 F 556 2193(W)U 556 2049(INTRODUCTION)U 616 2193(hy)U 699(Map)S 839(Texture?)S 1 F 556 2286(I)U (n)R 631(the)S 730(quest)S 882(for)S 977(more)S 1126(realistic)S 1343(imagery,)S 1581(one)S 1693(of)S 1767(the)S 1865(most)S 2006(frequent)S 2231(critici)S 2373(sms)S 2490(of)S 2564(early)S 2709(synthesized)S 3014(raster)S 3128 2358(r)U 556 2430(\256)U 556 2358(images)U 756(was)S 878(the)S 980(extreme)S 1203(smoothness)S 1511(of)S 1589(surfaces)S 1814(-)S 1862(they)S 1994(showed)S 2205(no)S 2293(texture,)S 2504(bumps,)S 2707(scratches,)S 2971(dirt,)S 3098(o)S 589 2430(ngerprints.)U 891(Realism)S 1112(demands)S 1349(complexit)S 1591(y,)S 1659(or)S 1732(at)S 1799(least)S 1933(the)S 2030(appearanc)S 2275(e)S 2325(of)S 2398(complexit)S 2640(y.)S 2727(Texture)S 2937(mapping)S 3118 2502(g)U 556 2574(a)U 556 2502(is)U 622(a)S 675(relative)S 857(ly)S 930(ef\256cient)S 1154(means)S 1334(to)S 1406(create)S 1576(the)S 1675(appearanc)S 1920(e)S 1972(of)S 2047(complexit)S 2289(y)S 2344(without)S 2553(the)S 2652(tedium)S 2845(of)S 2920(modelin)S 583 2574(nd)U 663(rendering)S 914(every)S 1068(3-D)S 1181(detail)S 1336(of)S 1406(a)S 1453(surface.)S 556 2667(T)U (he)R 683(study)S 846(of)S 929(texture)S 1130(mapping)S 1374(is)S 1447(valuable)S 1685(because)S 1909(its)S 1999(methods)S 2236(are)S 2343(applicabl)S 2565(e)S 2624(throughout)S 2920(computer)S 3128 2739(-)U 556 2811(f)U 556 2739(graphics)U 788(and)S 902(image)S 1077(processing.)S 1396(Geometric)S 1678(mappings)S 1939(are)S 2040(relevant)S 2262(to)S 2336(the)S 2437(modeling)S 2692(of)S 2769(parametri)S 3001(c)S 3055(sur)S 576 2811(aces)U 701(in)S 769(CAD)S 916(and)S 1024(to)S 1092(general)S 1291(2-D)S 1405(image)S 1574(distortions)S 1848(for)S 1938(image)S 2106(restoration)S 2384(and)S 2491(artistic)S 2676(uses.)S 2834(The)S 2948(study)S 3098(of)S 3128 2883(-)U 556 2955(i)U 556 2883(texture)U 747(\256ltering)S 961(leads)S 1108(into)S 1225(the)S 1322(development)S 1657(of)S 1730(space)S 1887(variant)S 2078(\256lters,)S 2252(which)S 2421(are)S 2517(useful)S 2686(for)S 2778(image)S 2948(process)S 573 2955(ng,)U 668(artistic)S 853(effects,)S 1049(depth-of-\256eld)S 1400(simulation,)S 1690(and)S 1797(motion)S 1988(blur.)S 556 3192(W)U 3 F 556 3099(De\256nitions)U 1 F 613 3192(e)U 661(de\256ne)S 829(a)S 2 F 877(texture)S 1 F 1066(rather)S 1228(loosely:)S 1440(it)S 1494(can)S 1598(be)S 1675(either)S 1833(a)S 1880(texture)S 2068(in)S 2135(the)S 2229(usual)S 2376(sense)S 2526(\(e.g.)S 2653(cloth,)S 2809(wood,)S 2977(gravel\))S 3131 3264(l)U 556 3336(i)U 556 3264(-)U 599(a)S 648(detaile)S 810(d)S 862(pattern)S 1052(that)S 1165(is)S 1227(repeate)S 1402(d)S 1454(many)S 1610(times)S 1763(to)S 1832(tile)S 1932(the)S 2028(plane,)S 2196(or)S 2268(more)S 2414(generally,)S 2676(a)S 2725(multidime)S 2974(nsiona)S 573 3336(mage)U 726(that)S 839(is)S 901(mapped)S 1114(to)S 1183(a)S 1232(multidime)S 1481(nsional)S 1677(space.)S 1868(The)S 1984(latter)S 2131(de\256nition)S 2383(encompasses)S 2718(non-tiling)S 2977(images)S 2 F 556 3501(T)U 1 F 556 3408(such)U 686(as)S 756(billboards)S 1017(and)S 1124(paintings.)S 2 F 589 3501(exture)U 764(mapping)S 1 F 998(means)S 1176(the)S 1274(mapping)S 1509(of)S 1583(a)S 1634(function)S 1858(onto)S 1988(a)S 2038(surface)S 2235(in)S 2305(3-D.)S 2456(The)S 2573(domain)S 2777(of)S 2850(the)S 2947(function)S 3131 3573(l)U 556 3645(f)U 556 3573(can)U 660(be)S 737(one,)S 859(two,)S 984(or)S 1054(three-dime)S 1316(nsional,)S 1525(and)S 1632(it)S 1686(can)S 1790(be)S 1867(represented)S 2165(by)S 2245(either)S 2403(an)S 2480(array)S 2624(or)S 2694(by)S 2774(a)S 2821(mathema)S 3043(tica)S 576 3645(unction.)U 813(For)S 917(example,)S 1158(a)S 1206(1-D)S 1320(texture)S 1509(can)S 1614(simulate)S 1840(rock)S 1968(strata;)S 2136(a)S 2183(2-D)S 2296(texture)S 2484(can)S 2588(represent)S 2829(waves,)S 3014(vege-)S 3128 3717(r)U 556 3789(m)U 556 3717(tation)U 716([Nor82],)S 946(or)S 1018(surface)S 1214(bumps)S 1396([Per84];)S 1615(a)S 1664(3-D)S 1779(texture)S 1969(can)S 2075(represent)S 2317(clouds)S 2495([Gar85],)S 2721(wood)S 2875([Pea85],)S 3098(o)S 603 3789(arble)U 744([Per85a].)S 1006(For)S 1109(our)S 1209(purposes)S 1442(textures)S 1653(will)S 1767(usually)S 1961(be)S 2038(2-D)S 2151(arrays.)S 48 Z 556 4002(a)U 6 F 556 3942(hhhhhhhhhhhhhhhhhh)U 1 F 577 4002(uthor's)U 729(address:)S 902(PIXAR,)S 1075(P.O.)S 1177(Box)S 1273(13719,)S 1421(San)S 1509(Rafael,)S 1661(CA,)S 1756(94913.)S 2913 4062(s)U 556 4122(p)U 556 4062(This)U 662(paper)S 789(appeared)S 982(in)S 2 F 1040(IEEE)S 1163(Computer)S 1375(Graphics)S 1574(and)S 1666(Applications)S 1 F (,)R 1939(Nov.)S 2054(1986,)S 2182(pp.)S 2262(56-67.)S 2422(An)S 2501(earlier)S 2642(version)S 2803(of)S 2863(thi)S 580 4122(aper)U 679(appeared)S 868(in)S 2 F 921(Graphics)S 1116(Interface)S 1304('86)S 1 F (,)R 1396(May)S 1500(1986,)S 1624(pp.)S 1700(207-212.)S 1904(This)S 2005(postscript)S 2207(version)S 2364(is)S 2412(missing)S 2577(all)S 2640(of)S 2696(the)S 2770(paste-up)S 60 Z 16 4710(-)U 48 Z 556 4182(\256gures.)U 60 Z 36 4710(-)U 3259(--)S EP %%Page: ? 2 BP 1 F 60 Z 556 438(T)U 1797 246(-)U 1837(2)S 1887(-)S 593 438(he)U 673(source)S 853(image)S 1024(\()S 2 F (texture)R 1 F (\))R 1255(is)S 1318(mapped)S 1532(onto)S 1662(a)S 1711(surface)S 1907(in)S 1976(3-D)S 2 F 2091(object)S 2261(space)S 1 F (,)R 2435(which)S 2604(is)S 2666(then)S 2792(mapped)S 3005(to)S 3074(the)S 3125 510(s)U 556 582(l)U 556 510(destination)U 848(image)S 1023(\()S 2 F (screen)R 1 F (\))R 1247(by)S 1334(the)S 1434(viewing)S 1654(projection.)S 1960(Texture)S 2174(space)S 2334(is)S 2400(labeled)S 2601(\()S 2 F (u)R 1 F 2661(,)S 2 F (v)R 1 F 2713(\),)S 2774(object)S 2948(space)S 3108(i)S 573 582(abeled)U 751(\()S 2 F (x)R 1 F 829(,)S 2 F (y)R 1 F 902(,)S 2 F (z)R 1 F 971(\),)S 1026(and)S 1133(screen)S 1307(space)S 1461(is)S 1521(labeled)S 1716(\()S 2 F (x)R 1 F 1773(,)S 2 F (y)R 1 F 1825(\).)S 556 675(W)U 2 F 42 Z 798 594(o)U 871(o)S 940(o)S 1 F 60 Z 613 675(e)U 661(assume)S 858(the)S 952(reader)S 1123(is)S 1183(familia)S 1355(r)S 1395(with)S 1522(the)S 1616(terminology)S 1931(of)S 2001(3-D)S 2114(raster)S 2268(graphics)S 2492(and)S 2599(the)S 2693(issues)S 2856(of)S 2926(antiali)S 3078(as-)S 3 F 556 891(U)U 1 F 556 747(ing)U 653([Rog85],)S 888([Fol82].)S 3 F 599 891(ses)U 692(for)S 789(Texture)S 1013(Mapping)S 1 F 556 984(T)U (he)R 682(possible)S 911(uses)S 1046(for)S 1148(mapped)S 1371(texture)S 1571(are)S 1677(myriad.)S 1915(Some)S 2084(of)S 2166(the)S 2272(paramete)S 2494(rs)S 2568(that)S 2690(have)S 2835(been)S 2980(texture)S 556 1056(mapped)U 767(to)S 834(date)S 955(are,)S 1064(in)S 1131(roughly)S 1338(chronological)S 1690(order:)S 772 1164(surface)U 966(color)S 1110(\(the)S 1224(most)S 1361(common)S 1592(use\))S 1712([Cat74],)S 772 1308(n)U 772 1236(specular)U 993(re\257ection)S 1241([Bli76],)S 802 1308(ormal)U 963(vector)S 1134(perturbation)S 1449(\(``bump)S 1666(mapping''\))S 1957([Bli78a],)S 772 1452(t)U 772 1380(specularity)U 1057(\(the)S 1171(glossiness)S 1434(coef\256cient\))S 1729([Bli78b],)S 789 1452(ransparency)U 1100([Gar85],)S 1394 1524(,)U 772 1596(s)U 772 1524(diffuse)U 959(re\257ection)S 1207([Mil84])S 795 1596(hadows,)U 1013(surface)S 1207(displaceme)S 1479(nt,)S 1561(and)S 1668(mixing)S 1859(coef\256cients)S 2157([Coo84],)S 556 1797(O)U 772 1668(local)U 910(coordinate)S 1185(system)S 1372(\(``frame)S 1593(mapping''\))S 1884([Kaj85].)S 599 1797(ur)U 671(focus)S 822(in)S 890(this)S 998(paper)S 1153(is)S 1214(on)S 1295(the)S 1390(computati)S 1632(onal)S 1757(aspects)S 1952(of)S 2023(texturing:)S 2279(those)S 2427(tasks)S 2568(common)S 2800(to)S 2868(all)S 2950(types)S 3098(of)S 3128 1869(f)U 556 1941(t)U 556 1869(texture)U 751(mapping.)S 1024(We)S 1135(will)S 1256(not)S 1360(attempt)S 1569(a)S 1623(thorough)S 1866(survey)S 2052(of)S 2128(the)S 2228(optical)S 2419(and)S 2532(semantic)S 2773(implica)S 2955(tions)S 3098(o)S 573 1941(exturing,)U 811(a)S 860(careful)S 1050(review)S 1236(of)S 1308(which)S 1477(is)S 1539(availabl)S 1731(e)S 1780([Car85].)S 2024(One)S 2145(type)S 2270(of)S 2341(texture)S 2530(mapping)S 2762(warrants)S 2990(partic-)S 2 F 556 2106(I)U 1 F 556 2013(ular)U 670(attenti)S 822(on,)S 917(however:)S 1161(illumina)S 1363(tion)S 1477(mapping.)S 2 F 576 2106(llumination)U 882(mapping)S 1 F 1120(is)S 1188(the)S 1290(mapping)S 1529(of)S 1607(specular)S 1836(or)S 1914(diffuse)S 2108(re\257ection.)S 2398(It)S 2462(is)S 2529(also)S 2653(known)S 2843(as)S 2920(re\257ection)S 3128 2178(-)U 556 2250(e)U 556 2178(mapping)U 789(or)S 861(environment)S 1188(mapping.)S 1455(Mapping)S 1693(illumina)S 1895(tion)S 2010(is)S 2071(rather)S 2233(different)S 2462(from)S 2600(mapping)S 2832(other)S 2977(param)S 583 2250(ters,)U 707(since)S 853(an)S 932(illumina)S 1134(tion)S 1250(map)S 1376(is)S 1438(not)S 1537(associated)S 1807(with)S 1936(a)S 1985(particula)S 2197(r)S 2239(object)S 2409(in)S 2478(the)S 2574(scene)S 2730(but)S 2829(with)S 2958(an)S 3037(ima-)S 3128 2322(-)U 556 2394(t)U 556 2322(ginary)U 734(in\256nite)S 929(radius)S 1100(sphere,)S 1296(cylinder,)S 1533(or)S 1607(cube)S 1745(surrounding)S 2059(the)S 2157(scene)S 2315([Gre86a].)S 2591(Whereas)S 2826(standard)S 3054(tex)S 573 2394(ure)U 674(maps)S 825(are)S 923(indexed)S 1138(by)S 1222(the)S 1320(surface)S 1518(paramete)S 1740(rs)S 2 F 1807(u)S 1 F 1871(and)S 2 F 1982(v)S 1 F 2019(,)S 2058(a)S 2109(specular)S 2334(re\257ection)S 2586(map)S 2714(is)S 2777(indexed)S 2991(by)S 3074(the)S 556 2538([)U 556 2466(re\257ected)U 790(ray)S 893(direction)S 1134([Bli76])S 1334(and)S 1447(a)S 1499(diffuse)S 1691(re\257ection)S 1944(map)S 2073(is)S 2138(indexed)S 2354(by)S 2439(the)S 2538(surface)S 2737(normal)S 2933(direction)S 576 2538(Mil84].)U 810(The)S 936(technique)S 1203(can)S 1318(be)S 1406(generaliz)S 1628(ed)S 1716(for)S 1817(transparency)S 2156(as)S 2237(well,)S 2387(indexing)S 2629(by)S 2720(the)S 2825(refracte)S 3010(d)S 3071(ray)S 3118 2610(d)U 556 2682(o)U 556 2610(direction)U 795([Kay79].)S 1054(In)S 1128(the)S 1226(special)S 1418(case)S 1546(that)S 1661(all)S 1746(surfaces)S 1967(have)S 2105(the)S 2203(same)S 2351(re\257ectanc)S 2586(e)S 2637(and)S 2748(they)S 2876(are)S 2974(viewe)S 586 2682(rthographical)U 908(ly)S 978(the)S 1075(total)S 1206(re\257ected)S 1437(intensity)S 1668(is)S 1731(a)S 1781(function)S 2005(of)S 2077(surface)S 2273(orientati)S 2475(on)S 2557(only,)S 2701(so)S 2776(the)S 2872(diffuse)S 3061(and)S 3128 2754(-)U 556 2826(t)U 556 2754(specular)U 781(maps)S 932(can)S 1040(be)S 1120(merged)S 1324(into)S 1441(one)S 1551([Hor81].)S 1802(Ef\256cient)S 2033(\256ltering)S 2247(is)S 2310(especial)S 2505(ly)S 2575(important)S 2833(for)S 2926(illumina)S 573 2826(ion)U 670(mapping,)S 916(where)S 1083(high)S 1210(surface)S 1404(curvature)S 1652(often)S 1796(necessitat)S 2031(es)S 2101(broad)S 2258(areas)S 2402(of)S 2472(the)S 2566(sky)S 2669(to)S 2736(be)S 2813(averaged.)S 3121 2919(e)U 556 2991(r)U 556 2919(Illuminat)U 778(ion)S 894(mapping)S 1144(facilit)S 1286(ates)S 1419(the)S 1532(simulation)S 1825(of)S 1913(complex)S 2159(lighting)S 2385(environments,)S 2766(since)S 2928(the)S 3040(tim)S 576 2991(equired)U 779(to)S 848(shade)S 1007(a)S 1056(point)S 1202(is)S 1264(independent)S 1581(of)S 1653(the)S 1749(number)S 1955(of)S 2027(light)S 2160(sources.)S 2397(There)S 2559(are)S 2654(other)S 2799(reasons)S 3000(for)S 3091(its)S 3131 3063(t)U 556 3135(i)U 556 3063(recent)U 725(popularity:)S 1011(it)S 1066(is)S 1127(one)S 1234(of)S 1304(the)S 1398(few)S 1508(demonstrated)S 1853(techniques)S 2131(for)S 2221(antiali)S 2373(asing)S 2520(highlights)S 2781([Wil83],)S 3007(and)S 3114(i)S 573 3135(s)U 623(an)S 707(inexpensive)S 1022(approximati)S 1314(on)S 1401(to)S 1475(ray)S 1578(tracing)S 1772(for)S 1868(mirror)S 2048(re\257ection)S 2302(and)S 2415(to)S 2488(radiosity)S 2725(methods)S 2955([Gor84])S 3 F 556 3351(M)U 1 F 556 3207(for)U 646(diffuse)S 833(re\257ection)S 1081(of)S 1151(objects)S 1342(in)S 1409(the)S 1503(environment.)S 3 F 613 3351(APPING)U 1 F 556 3444(T)U (he)R 673(mapping)S 907(from)S 1047(texture)S 1238(space)S 1394(to)S 1463(screen)S 1639(space)S 1795(is)S 1857(split)S 1983(into)S 2099(two)S 2211(phases,)S 2408(as)S 2480(shown)S 2658(in)S 2727(\256gure)S 2889(1.)S 2976(First)S 3108(is)S 556 3588(a)U 556 3516(the)U 651(surface)S 846(paramete)S 1068(rization)S 1274(that)S 1386(maps)S 1534(texture)S 1723(space)S 1878(to)S 1946(object)S 2115(space,)S 2285(followed)S 2520(by)S 2601(the)S 2696(standard)S 2920(modeling)S 583 3588(nd)U 666(viewing)S 883(transformations)S 1284(that)S 1398(map)S 1525(object)S 1696(space)S 1852(to)S 1921(screen)S 2097(space,)S 2268(typicall)S 2450(y)S 2502(with)S 2631(a)S 2680(perspective)S 2977(projec-)S 556 3732(s)U 556 3660(tion)U 677([Fol82].)S 919(These)S 1090(two)S 1207(mappings)S 1468(are)S 1569(composed)S 1840(to)S 1914(\256nd)S 2034(the)S 2135(overall)S 2329(2-D)S 2448(texture)S 2642(space)S 2802(to)S 2875(2-D)S 2994(screen)S 579 3732(pace)U 714(mapping,)S 964(and)S 1075(the)S 1173(intermedi)S 1405(ate)S 1500(3-D)S 1617(space)S 1775(is)S 1839(often)S 1987(forgotten.)S 2267(This)S 2398(simpli\256cati)S 2670(on)S 2754(suggests)S 2980(texture)S 3 F 556 3948(S)U 1 F 556 3804(mapping's)U 830(close)S 974(ties)S 1078(with)S 1205(image)S 1373(warping)S 1590(and)S 1697(geometric)S 1959(distortion.)S 3 F 589 3948(canning)U 812(Order)S 1 F 556 4041(T)U (here)R 719(are)S 815(three)S 958(general)S 1158(approaches)S 1451(to)S 1520(drawing)S 1739(a)S 1788(texture)S 1978(mapped)S 2191(surface:)S 2404(a)S 2452(scan)S 2580(in)S 2648(screen)S 2823(space,)S 2993(a)S 3041(scan)S 16 4710(-)U 556 4113(in)U 623(texture)S 811(space,)S 980(and)S 1087(two-pass)S 1320(methods.)S 1579(The)S 1693(three)S 1834(algorithms)S 2112(are)S 2206(outlined)S 2424(below:)S 36 4710(-)U 3259(--)S EP %%Page: ? 3 BP 3 F 60 Z 772 438(SCREEN)U 1034(SCANNI)S 1262(NG:)S 1 F 1797 246(-)U 1837(3)S 1887(-)S 872 510(for)U 962(y)S 972 582(for)U 1062(x)S 1072 654(compute)U 1300(u\(x,y\))S 1465(and)S 1572(v\(x,y\))S 1736 726(])U 3 F 772 870(T)U 1 F 1072 726(copy)U 1209(TEX[u,v])S 1461(to)S 1528(SCR[x,y)S 3 F 812 870(EXTURE)U 1081(SCANNI)S 1309(NG:)S 1 F 872 942(for)U 962(v)S 972 1014(for)U 1062(u)S 1072 1086(compute)U 1300(x\(u,v\))S 1465(and)S 1572(y\(u,v\))S 1736 1158(])U 1072(copy)S 1209(TEX[u,v])S 1461(to)S 1528(SCR[x,y)S 3 F 1085 1302(:)U 772(TWO-PASS)S 1 F 872 1374(for)U 962(v)S 972 1446(for)U 1062(u)S 1072 1518(compute)U 1300(x\(u,v\))S 1072 1590(c)U (opy)R 1209(TEX[u,v])S 1461(to)S 1528(TEMP[x,v])S 872 1662(for)U 962(x)S 972 1734(for)U 1062(v)S 1072 1806(compute)U 1300(y\(x,v\))S 1072 1878(c)U (opy)R 1209(TEMP[x,v])S 1504(to)S 1571(SCR[x,y])S 556 2058(w)U (here)R 729(TEX)S 872(is)S 938(the)S 1038(texture)S 1232(array,)S 1397(SCR)S 1536(is)S 1602(the)S 1701(screen)S 1880(array,)S 2044(and)S 2156(TEMP)S 2341(is)S 2406(a)S 2458(temporary)S 2731(array.)S 2915(Note)S 3057(that)S 556 2223(S)U 556 2130(copying)U 770(pixels)S 934(involves)S 1158(\256ltering.)S 589 2223(creen)U 741(order,)S 904(sometimes)S 1183(called)S 1349(inverse)S 1544(mapping,)S 1791(is)S 1852(the)S 1947(most)S 2085(common)S 2316(method.)S 2552(For)S 2655(each)S 2786(pixel)S 2927(in)S 2994(screen)S 3125 2295(s)U 556 2367(p)U 556 2295(space,)U 733(the)S 835(pre-image)S 1108(of)S 1186(the)S 1288(pixel)S 1437(in)S 1512(texture)S 1708(space)S 1870(is)S 1938(found)S 2106(and)S 2221(this)S 2336(area)S 2465(is)S 2533(\256ltered.)S 2766(This)S 2900(method)S 3108(i)S 586 2367(referable)U 825(when)S 979(the)S 1077(screen)S 1255(must)S 1396(be)S 1477(written)S 1672(sequentiall)S 1934(y)S 1988(\(e.g.)S 2119(when)S 2272(output)S 2449(is)S 2512(going)S 2672(to)S 2742(a)S 2792(\256lm)S 2912(recorder\),)S 556 2532(T)U 556 2439(the)U 650(mapping)S 881(is)S 941(readily)S 1129(invertible)S 1361(,)S 1396(and)S 1503(the)S 1597(texture)S 1785(is)S 1845(random)S 2049(access.)S 593 2532(exture)U 769(order)S 921(may)S 1050(seem)S 1199(simpler)S 1405(than)S 1534(screen)S 1713(order,)S 1880(since)S 2029(inverting)S 2272(the)S 2371(mapping)S 2607(is)S 2672(unnecessary)S 2990(in)S 3061(this)S 556 2676(s)U 556 2604(case,)U 704(but)S 810(doing)S 976(texture)S 1173(order)S 1329(correctly)S 1573(requires)S 1796(subtlety.)S 2050(Unfortunately,)S 2431(uniform)S 2653(sampling)S 2902(of)S 2980(texture)S 579 2676(pace)U 714(does)S 848(not)S 949(guarantee)S 1208(uniform)S 1426(sampling)S 1671(of)S 1745(screen)S 1923(space)S 2081(except)S 2263(for)S 2357(af\256ne)S 2518(\(linear\))S 2720(mappings.)S 3013(Thus,)S 556 2820(w)U 556 2748(for)U 648(non-af\256ne)S 917(mappings)S 1173(texture)S 1363(subdivision)S 1662(must)S 1801(often)S 1947(be)S 2026(done)S 2165(adaptivel)S 2387(y;)S 2455(otherwise,)S 2725(holes)S 2873(or)S 2944(overlaps)S 599 2820(ill)U 677(result)S 838(in)S 912(screen)S 1092(space.)S 1287(Scanning)S 1537(the)S 1637(texture)S 1831(is)S 1897(preferable)S 2168(when)S 2324(the)S 2424(texture)S 2618(to)S 2691(screen)S 2871(mapping)S 3108(is)S 556 2964(w)U 556 2892(dif\256cult)U 774(to)S 848(invert,)S 1031(or)S 1108(when)S 1265(the)S 1366(texture)S 1561(image)S 1735(must)S 1878(be)S 1961(read)S 2091(sequentiall)S 2353(y)S 2409(\(for)S 2525(example,)S 2771(from)S 2914(tape\))S 3061(and)S 599 2964(ill)U 670(not)S 767(\256t)S 837(in)S 904(random)S 1108(access)S 1282(memory.)S 556 3057(T)U (wo-pass)R 811(methods)S 1037(decompose)S 1330(a)S 1379(2-D)S 1494(mapping)S 1727(into)S 1842(two)S 1953(1-D)S 2067(mappings,)S 2337(the)S 2432(\256rst)S 2546(pass)S 2670(applied)S 2869(to)S 2937(the)S 3032(rows)S 3131 3129(l)U 556 3201(f)U 556 3129(of)U 627(an)S 705(image)S 874(and)S 982(the)S 1077(second)S 1265(pass)S 1389(applied)S 1588(to)S 1656(the)S 1751(columns)S 1975([Cat80].)S 2214(These)S 2378(methods)S 2602(work)S 2745(particula)S 2957(rly)S 3044(wel)S 576 3201(or)U 652(af\256ne)S 815(and)S 928(perspective)S 1229(mappings,)S 1504(where)S 1677(the)S 1777(warps)S 1946(for)S 2042(each)S 2179(pass)S 2308(are)S 2408(linear)S 2572(or)S 2648(rational)S 2858(linear)S 3021(func-)S 556 3345(a)U 556 3273(tions.)U 731(Because)S 955(the)S 1052(mapping)S 1286(and)S 1396(\256lter)S 1533(are)S 1630(1-D)S 1746(they)S 1873(are)S 1970(amenable)S 2225(to)S 2295(stream)S 2479(processing)S 2758(techniques)S 3038(such)S 583 3345(s)U 632(pipelining.)S 938(Two-pass)S 1197(methods)S 1427(are)S 1527(preferable)S 1798(when)S 1954(the)S 2054(source)S 2237(image)S 2411(cannot)S 2598(be)S 2681(accessed)S 2917(randomly)S 3 F 556 3561(P)U 1 F 556 3417(but)U 653(it)S 707(has)S 807(rapid)S 951(row)S 1064(and)S 1171(column)S 1372(access,)S 1561(and)S 1668(a)S 1715(buffer)S 1882(for)S 1972(the)S 2066(intermedi)S 2298(ate)S 2389(image)S 2557(is)S 2617(availabl)S 2809(e.)S 3 F 593 3561(arameteri)U 848(zation)S 1 F 556 3654(M)U (apping)R 800(a)S 853(2-D)S 972(texture)S 1166(onto)S 1299(a)S 1352(surface)S 1552(in)S 1625(3-D)S 1744(requires)S 1964(a)S 2017(paramete)S 2239(rization)S 2450(of)S 2526(the)S 2626(surface.)S 2861(This)S 2994(comes)S 3128 3726(r)U 556 3798(o)U 556 3726(naturally)U 801(for)S 901(surfaces)S 1128(that)S 1249(are)S 1353(de\256ned)S 1560(parametri)S 1792(cally,)S 1955(such)S 2095(as)S 2175(bicubic)S 2383(patches,)S 2609(but)S 2715(less)S 2834(naturally)S 3078(fo)S 586 3798(ther)U 705(surfaces)S 927(such)S 1062(as)S 1136(polygons)S 1380(and)S 1491(quadrics,)S 1734(which)S 1905(are)S 2003(usually)S 2201(de\256ned)S 2402(implici)S 2574(tly.)S 2697(The)S 2815(paramete)S 3037(riza-)S 3128 3870(-)U 556 3942(m)U 556 3870(tion)U 674(can)S 782(be)S 863(by)S 947(surface)S 1145(coordinates)S 2 F 1447(u)S 1 F 1511(and)S 2 F 1622(v)S 1 F 1659(,)S 1697(as)S 1770(in)S 1840(standard)S 2067(texture)S 2258(mapping,)S 2507(by)S 2590(the)S 2687(direction)S 2925(of)S 2998(a)S 3048(nor)S 603 3942(al)U 670(vector)S 844(or)S 917(light)S 1051(ray,)S 1166(as)S 1239(in)S 1309(illumina)S 1511(tion)S 1628(mapping,)S 1876(or)S 1948(by)S 2030(spatial)S 2210(coordinates)S 2 F 2510(x)S 1 F 2568(,)S 2 F 2605(y)S 1 F 2663(,)S 2700(and)S 2 F 2809(z)S 1 F 2885(for)S 2977(objects)S 2 F 42 Z 2537 3954(o)U 2632(o)S 2832(o)S 1 F 60 Z 3105 4014(D)U 556 4086(f)U 556 4014(that)U 674(are)S 775(to)S 849(appear)S 1037(carved)S 1225(out)S 1329(of)S 1406(a)S 1460(solid)S 1604(materia)S 1786(l.)S 1865(Solid)S 2019(textures)S 2237(can)S 2348(be)S 2431(modeled)S 2665(using)S 2821(arbitrary)S 3055(3-)S 576 4086(unctions)U 800([Per85a])S 1027(or)S 1097(by)S 1177(sweeping)S 1424(a)S 1471(2-D)S 1584(function)S 1805(through)S 2012(space)S 2166([Pea85],)S 2388([Bie86].)S 3279 4710(-)U 16(--)S 3259(-)S EP %%Page: ? 4 BP 1 F 60 Z 1797 246(-)U 1837(4)S 1887(-)S 556 531(W)U 3 F 556 438(Parameter)U 831(izing)S 975(Planes)S 1162(and)S 1278(Polygons)S 1 F 613 531(e)U 668(will)S 790(focus)S 948(our)S 1055(attenti)S 1207(on)S 1294(on)S 1381(the)S 1482(simplest)S 1710(surfaces)S 1934(for)S 2031(texture)S 2226(mapping:)S 2481(planar)S 2659(polygons.)S 2941(First)S 3078(we)S 556 696(A)U 556 603(discuss)U 749(the)S 843(paramete)S 1065(rization)S 1270(and)S 1377(later)S 1505(we)S 1595(consider)S 1819(the)S 1913(composite)S 2181(mapping.)S 622 696(triangle)U 830(is)S 893(easily)S 1057(paramete)S 1279(rized)S 1423(by)S 1506(specifying)S 1780(the)S 1877(texture)S 2067(space)S 2223(coordinates)S 2523(\()S 2 F (u)R 1 F 2583(,)S 2 F (v)R 1 F 2635(\))S 2677(at)S 2743(each)S 2876(of)S 2948(its)S 3027(three)S 3133 768(,)U 556(vertices.)S 804(This)S 936(de\256nes)S 1131(an)S 1213(af\256ne)S 1375(mapping)S 1611(between)S 1837(texture)S 2030(space)S 2189(and)S 2301(3-D)S 2419(object)S 2592(space;)S 2768(each)S 2904(of)S 2 F 2978(x)S 1 F 3036(,)S 2 F 3075(y)S 42 Z 3005 780(o)U 3102(o)S 1 F 60 Z 556 840(a)U 2 F 42 Z 697 852(o)U 1 F 60 Z 583 840(nd)U 2 F 674(z)S 1 F 759(has)S 870(the)S 975(form)S 2 F 1123(Au)S 4 F 1200(+)S 2 F (Bv)R 4 F 1307(+)S 2 F (C)R 1 F 1390(.)S 1456(For)S 1570(polygons)S 1821(with)S 1958(more)S 2112(than)S 2246(three)S 2397(sides,)S 2562(nonlinear)S 2820(functions)S 3074(are)S 3125 912(s)U 556 984(t)U 556 912(needed)U 750(in)S 820(general,)S 1036(and)S 1146(one)S 1255(must)S 1394(decide)S 1574(whether)S 1790(the)S 1886(\257exibility)S 2143(is)S 2205(worth)S 2367(the)S 2463(expense.)S 2714(The)S 2830(alternat)S 3012(ive)S 3108(i)S 573 984(o)U 623(assume)S 820(linear)S 978(paramete)S 1200(rizations)S 1428(and)S 1535(subdivide)S 1789(into)S 1903(triangles)S 2131(where)S 2298(necessary.)S 556 1077(One)U 676(nonlinear)S 924(paramete)S 1146(rization)S 1351(that)S 1462(is)S 1522(sometimes)S 1800(used)S 1930(is)S 1990(the)S 2084(bilinear)S 2289(patch:)S 1325 1407([)U 2 F (x)R 1443(y)S 1541(z)S 1 F 1595(])S 4 F 1655(=)S 1 F 1728([)S 2 F (uv)R 1855(u)S 1935(v)S 1 F 2012(1])S 6 F 2092 1239(R)U 2092 1299(J)U 2092 1359(J)U 2092 1419(J)U 2092 1479(J)U 2092 1539(Q)U 2 F 2127 1521(D)U 2128 1437(C)U 2130 1353(B)U 2130 1269(A)U 2210 1521(H)U 2210 1437(G)U 2213 1353(F)U 2213 1269(E)U 2296 1521(L)U 2293 1437(K)U 2299 1353(J)U 2303 1269(I)U 6 F 2363 1239(H)U 2363 1299(J)U 2363 1359(J)U 2363 1419(J)U 2363 1479(J)U 2363 1539(P)U 1 F 556 1713(w)U 2 F 42 Z 1372 1419(o)U 1470(o)S 1564(o)S 1 F 60 Z 599 1713(hich)U 733(maps)S 889(rectangle)S 1111(s)S 1163(to)S 1239(planar)S 1419(or)S 1498(nonplanar)S 1768(quadrilate)S 2010(rals)S 2126([Hou83].)S 2393(This)S 2529(paramete)S 2751(rization)S 2965(has)S 3074(the)S 3131 1785(t)U 556 1857(p)U 556 1785(strange)U 758(property)S 989(of)S 1066(preserving)S 1347(lines)S 1488(and)S 1602(equal)S 1760(spacing)S 1971(along)S 2132(vertical)S 2341(and)S 2455(horizontal)S 2727(texture)S 2922(axes,)S 3071(bu)S 586 1857(reserves)U 815(neither)S 1015(along)S 1181(diagonals.)S 1479(The)S 1605(use)S 1717(of)S 1799(this)S 1918(paramete)S 2140(rization)S 2357(for)S 2458(planar)S 2640(quadrilate)S 2882(rals)S 3000(is)S 3071(not)S 556 2022(A)U 556 1929(recommende)U 868(d,)S 933(however,)S 1175(since)S 1319(inverting)S 1557(it)S 1611(requires)S 1825(the)S 1919(solution)S 2133(of)S 2203(quadratic)S 2448(equations.)S 619 2022(better)U 777(paramete)S 999(rization)S 1204(for)S 1294(planar)S 1465(quadrilate)S 1707(rals)S 1814(is)S 1874(the)S 1968(`perspective)S 2283(mapping')S 2534([Hec83]:)S 2 F 2442 2280(K)U 2448 2196(J)U 6 F 2512 2184(H)U 2512 2244(J)U 2512 2304(J)U 2512 2364(P)U 2 F 2445(L)S 2359 2280(H)U 2359 2196(G)U 2370 2364(I)U 2276 2196(D)U 2279 2280(E)U 2279 2364(F)U 1 F 1177 2280([)U 2 F (x)R 1255(w)S 1366(y)S 1424(w)S 1535(z)S 1589(w)S 1700(w)S 1 F 1771(])S 4 F 1831(=)S 1 F 1904([)S 2 F (u)R 2004(v)S 1 F 2081(1])S 6 F 2161 2184(R)U 2161 2244(J)U 2161 2304(J)U 2161 2364(Q)U 2 F 2196(C)S 2197 2280(B)U 2197 2196(A)U 42 Z 1224 2292(o)U 1295(o)S 1393(o)S 1464(o)S 1558(o)S 1629(o)S 1740(o)S 1 F 60 Z 556 2538(w)U 2 F 42 Z 764 2550(o)U 1 F 60 Z 599 2538(here)U 2 F 724(w)S 1 F 816(is)S 877(the)S 972(homogeneous)S 1327(coordinate)S 1603(that)S 1715(is)S 1776(divided)S 1978(through)S 2186(to)S 2254(calcula)S 2426(te)S 2491(the)S 2585(true)S 2699(object)S 2867(space)S 3021(coor-)S 556 2610(dinates)U 793([Rob66],)S 1074([Fol82].)S 1355(Object)S 1582(coordinates)S 2 F 1926(x)S 1 F 1984(,)S 2 F 2064(y)S 1 F 2122(,)S 2202(and)S 2 F 2354(z)S 1 F 2473(are)S 2612(thus)S 2777(of)S 2892(the)S 3031(form)S 2 F 42 Z 1953 2622(o)U 2091(o)S 2377(o)S 1 F 60 Z 3125 2682(s)U 556 2754(e)U 556 2682(\()U 2 F (Au)R 4 F 653(+)S 2 F (Bv)R 4 F 760(+)S 2 F (C)R 1 F 843(\))S 4 F (/)R 1 F (\()R 2 F (Ju)R 4 F 967(+)S 2 F (Kv)R 4 F 1077(+)S 2 F (L)R 1 F 1153(\).)S 1241(The)S 1368(perspective)S 1676(mapping)S 1920(preserves)S 2180(lines)S 2327(at)S 2404(all)S 2498(orientati)S 2700(ons)S 2815(but)S 2924(sacri\256ce)S 583 2754(qual)U 711(spacing.)S 954(Af\256ne)S 1131(mappings)S 1389(are)S 1487(the)S 1585(subset)S 1759(of)S 1833(perspective)S 2132(matrice)S 2314(s)S 2361(for)S 2455(which)S 2 F 2626(J)S 4 F 2663(=)S 2 F (K)R 4 F 2746(=)S 1 F (0.)R 2867(Note)S 3007(that)S 3121(a)S 3125 2826(s)U 556 2898(p)U 556 2826(perspective)U 858(mapping)S 1096(might)S 1264(be)S 1348(used)S 1485(for)S 1582(the)S 1683(paramete)S 1905(rization)S 2117(whether)S 2338(or)S 2414(not)S 2517(the)S 2617(viewing)S 2837(projection)S 3108(i)S 586 2898(erspective)U 831(.)S 3 F 1051 3063(s)U 2 F 556 3207(O)U 3 F 556 3063(Projecting)U 844(Polygon)S 2 F 599 3207(rthographic)U 906(Projection)S 1 F 556 3300(O)U (rthographic)R 906(projections)S 1202(of)S 1280(linearly-pa)S 1542(rameteri)S 1744(zed)S 1856(planar)S 2035(textures)S 2254(have)S 2396(an)S 2481(af\256ne)S 2646(composite)S 2922(mapping.)S 556 3444(s)U 556 3372(The)U 674(inverse)S 872(of)S 946(this)S 1057(mapping)S 1292(is)S 1355(af\256ne)S 1515(as)S 1588(well,)S 1730(of)S 1803(course.)S 2018(This)S 2148(makes)S 2325(them)S 2469(particula)S 2681(rly)S 2771(easy)S 2901(to)S 2971(scan)S 3101(in)S 579 3444(creen)U 735(order:)S 904(the)S 1003(cost)S 1125(is)S 1190(only)S 1322(two)S 1437(adds)S 1572(per)S 1674(pixel,)S 1835(disregarding)S 2161(\256ltering)S 2377([Smi80].)S 2634(It)S 2695(is)S 2759(also)S 2880(possible)S 3101(to)S 3133 3516(.)U 556 3588(M)U 556 3516(perform)U 780(af\256ne)S 947(mappings)S 1210(by)S 1299(scanning)S 1542(the)S 1645(texture,)S 1857(producing)S 2130(the)S 2233(screen)S 2416(image)S 2593(in)S 2669(non-scanline)S 3006(order)S 609 3588(ost)U 699(of)S 769(these)S 913(methods)S 1137(are)S 1231(quite)S 1372(ingenious.)S 556 3681(B)U (raccini)R 794(and)S 913(Marino)S 1122(show)S 1280(that)S 1403(by)S 1495(depositing)S 1778(the)S 1884(pixels)S 2060(of)S 2142(a)S 2201(texture)S 2401(scanline)S 2631(along)S 2797(the)S 2903(path)S 3039(of)S 3121(a)S 3125 3753(s)U 556 3825(r)U 556 3753(Bresenham)U 853(digital)S 1034(line,)S 1166(an)S 1249(image)S 1423(can)S 1533(be)S 1615(rotated)S 1808(or)S 1883(sheared)S 2092([Bra80].)S 2339(To)S 2431(\256ll)S 2523(the)S 2622(holes)S 2774(that)S 2890(sometime)S 576 3825(esult)U 716(between)S 943(adjace)S 1098(nt)S 1171(lines,)S 1326(they)S 1456(draw)S 1602(an)S 1684(extra)S 1830(pixel)S 1976(at)S 2045(each)S 2181(kink)S 2313(in)S 2385(the)S 2484(line.)S 2635(This)S 2767(results)S 2949(in)S 3021(some)S 556 3969(a)U 556 3897(redundancy.)U 899(They)S 1050(also)S 1174(use)S 1281(Bresenham's)S 1622(algorithm)S 1884([Fol82])S 2090(in)S 2163(a)S 2216(totally)S 2397(different)S 2631(way:)S 2774(to)S 2847(resample)S 3091(an)S 583 3969(rray.)U 738(This)S 867(is)S 929(possible)S 1148(because)S 1361(distributing)S 2 F 1661(m)S 1 F 1736(source)S 1915(pixels)S 2081(to)S 2 F 2150(n)S 1 F 2212(screen)S 2388(pixels)S 2554(is)S 2616(analogous)S 2882(to)S 2951(drawing)S 556 4134(W)U 556 4041(a)U 603(line)S 714(with)S 841(slope)S 2 F 988(n)S 4 F 1028(/)S 2 F (m)R 1 F 1098(.)S 613 4134(eiman)U 789(also)S 914(uses)S 1044(Bresenham's)S 1385(algorithm)S 1647(for)S 1744(scaling)S 1942(but)S 2046(does)S 2183(not)S 2287(draw)S 2434(diagonally)S 2716(across)S 2893(the)S 2994(screen)S 3118 4206(d)U 556 4278(y)U 556 4206([Wei80].)U 825(Instead)S 1032(he)S 1122(decomposes)S 1449(rotation)S 1670(into)S 1797(four)S 1930(scanline)S 2161(operations:)S 2461(xscale,)S 2659(yscale,)S 2857(xshear,)S 3061(an)S 586 4278(shear.)U 768(He)S 858(does)S 988(box)S 1098(\256ltering)S 1309(by)S 1389(averaging)S 1647(together)S 1865(several)S 2056(phases)S 2236(of)S 2306(the)S 2400(scaled)S 2571(image.)S 3279 4710(-)U 16(--)S 3259(-)S EP %%Page: ? 5 BP 1 F 60 Z 1797 246(-)U 1837(5)S 1887(-)S 3118 438(h)U 556 510(d)U 556 438(Af\256ne)U 738(mappings)S 1001(can)S 1114(be)S 1199(performed)S 1478(with)S 1613(multiple)S 1843(pass)S 1974(methods)S 2206(in)S 2281(several)S 2480(ways.)S 2666(Catmull)S 2889(and)S 3004(Smit)S 586 510(ecompose)U 857(such)S 997(mappings)S 1261(into)S 1384(a)S 1440(composition)S 1767(of)S 1846(two)S 1965(shear-and-scale)S 2369(passes:)S 2568(one)S 2684(horizontal)S 2958(and)S 3074(the)S 556 654(i)U 556 582(other)U 703(vertical)S 908([Cat80].)S 1150(In)S 1223(a)S 1273(simpler)S 1476(variation)S 1713(discovered)S 1996(by)S 2078(Paeth,)S 2249(a)S 2298(rotational)S 2552(mapping)S 2785(is)S 2847(decomposed)S 573 654(nto)U 678(three)S 827(passes)S 1008(of)S 1086(shears:)S 1281(the)S 1383(\256rst)S 1504(horizontal,)S 1792(the)S 1894(second)S 2089(vertical)S 2271(,)S 2314(and)S 2429(the)S 2531(third)S 2673(horizontal)S 2946([Pae86].)S 556 798(s)U 556 726(Filtering)U 791(for)S 888(this)S 1002(three)S 1149(pass)S 1278(rotate)S 1442(is)S 1508(particula)S 1720(rly)S 1813(simple)S 2000(because)S 2217(resampling)S 2511(the)S 2611(scanlines)S 2858(involves)S 3088(no)S 579 798(caling.)U 2 F 556 942(P)U (erspectiv)R 811(e)S 858(Projection)S 1 F 556 1035(A)U 624(naive)S 780(method)S 986(for)S 1081(texture)S 1274(mapping)S 1510(in)S 1582(perspective)S 1882(is)S 1947(to)S 2019(linearly)S 2229(interpolat)S 2461(e)S 2513(the)S 2612(texture)S 2805(coordinates)S 2 F 3108(u)S 1 F 3118 1107(g)U 556 1179([)U 556 1107(and)U 2 F 671(v)S 1 F 736(along)S 898(the)S 1000(sides)S 1148(of)S 1226(the)S 1328(polygon)S 1553(and)S 1668(across)S 1846(each)S 1985(scanline,)S 2226(much)S 2388(as)S 2466(Gouraud)S 2704(or)S 2781(Phong)S 2961(shadin)S 576 1179(Rog85])U 779(is)S 842(done.)S 1017(However,)S 1275(linear)S 1436(interpolat)S 1668(ion)S 1768(will)S 1885(never)S 2042(give)S 2169(the)S 2266(proper)S 2446(effect)S 2606(of)S 2678(nonlinear)S 2928(foreshor-)S 556 1323(s)U 556 1251(tening)U 728([Smi80],)S 961(it)S 1016(is)S 1077(not)S 1175(rotational)S 1407(ly)S 1475(invariant,)S 1726(and)S 1834(the)S 1929(error)S 2067(is)S 2128(obvious)S 2339(in)S 2407(animati)S 2589(on.)S 2705(One)S 2826(solution)S 3041(is)S 3101(to)S 579 1323(ubdivide)U 815(each)S 951(polygon)S 1173(into)S 1292(many)S 1451(small)S 1607(polygons.)S 1887(The)S 2005(correct)S 2197(solution,)S 2430(however,)S 2676(is)S 2740(to)S 2811(replace)S 3010(linear)S 556 1467(s)U 556 1395(interpolat)U 788(ion)S 886(with)S 1014(the)S 1109(true)S 1223(formula,)S 1449(which)S 1616(requires)S 1830(a)S 1877(division)S 2091(at)S 2155(each)S 2286(pixel.)S 2462(In)S 2532(fact,)S 2658(Gouraud)S 2888(and)S 2995(Phong)S 579 1467(hading)U 769(in)S 842(perspective)S 1117(,)S 1158(which)S 1331(are)S 1431(usually)S 1631(impleme)S 1843(nted)S 1973(with)S 2106(linear)S 2269(interpolat)S 2501(ion,)S 2618(share)S 2770(the)S 2869(same)S 3018(prob-)S 556 1632(P)U 556 1539(lem,)U 682(but)S 779(the)S 873(errors)S 1033(are)S 1127(so)S 1200(slight)S 1354(that)S 1465(they're)S 1656(rarely)S 1817(noticed.)S 589 1632(erspective)U 854(mapping)S 1085(of)S 1155(a)S 1202(planar)S 1373(texture)S 1561(can)S 1665(be)S 1742(expressed)S 1999(using)S 2149(homogeneous)S 2503(matrix)S 2681(notation)S 2899([Hec83]:)S 2 F 2254 1890(H)U 2254 1806(G)U 6 F 2327 1794(H)U 2327 1854(J)U 2327 1914(J)U 2327 1974(P)U 2 F 2265(I)S 2171 1806(D)U 2174 1890(E)U 2174 1974(F)U 1 F 556 2148(T)U 1362 1890([)U 2 F (xw)R 1499(yw)S 1616(w)S 1 F 1666(])S 4 F 1726(=)S 1 F 1799([)S 2 F (u)R 1899(v)S 1 F 1976(1])S 6 F 2056 1794(R)U 2056 1854(J)U 2056 1914(J)U 2056 1974(Q)U 2 F 2091(C)S 2092 1890(B)U 2092 1806(A)U 1 F 593 2148(his)U 685(mapping)S 918(is)S 980(analogous)S 1245(to)S 1313(the)S 1408(more)S 1553(familia)S 1725(r)S 1766(3-D)S 1880(perspective)S 2176(transformation)S 2552(using)S 2703(4x4)S 2814(homogeneous)S 556 2220(matrice)U 738(s.)S 816(The)S 930(inverse)S 1124(of)S 1194(this)S 1301(mapping)S 1532(\(calcula)S 1724(ted)S 1818(using)S 1968(the)S 2062(adjoint)S 2250(matrix\))S 2448(is)S 2508(of)S 2578(the)S 2672(same)S 2816(form:)S 829 2478([)U 2 F (uq)R 959(vq)S 1066(q)S 1 F 1106(])S 4 F 1166(=)S 1 F 1239([)S 2 F (x)R 1336(y)S 1 F 1413(1])S 6 F 1493 2382(R)U 1493 2442(J)U 1493 2502(J)U 1493 2562(Q)U 2 F 1529(c)S 1528 2394(a)U 1528 2478(b)U 1603 2562(f)U 1599 2394(d)U 1600 2478(e)U 1676 2562(i)U 1670 2394(g)U 1670 2478(h)U 6 F 1730 2382(H)U 1730 2442(J)U 1730 2502(J)U 1730 2562(P)U 4 F 1785 2478(=)U 1 F 1858([)S 2 F (x)R 1955(y)S 1 F 2032(1])S 6 F 2112 2382(R)U 2112 2442(J)U 2112 2502(J)U 2112 2562(Q)U 2 F 2147(BF)S 4 F 2231(-)S 2 F (CE)R 2152 2478(C)U (H)R 4 F 2245(-)S 2 F (BI)R 2154 2394(E)U (I)R 4 F 2221(-)S 2 F (FH)R 2381 2562(CD)U 4 F 2474(-)S 2 F (AF)R 2389 2478(A)U (I)R 4 F 2456(-)S 2 F (CG)R 2388 2394(F)U (G)R 4 F 2478(-)S 2 F (DI)R 2627 2562(AE)U 4 F 2711(-)S 2 F (BD)R 2624 2478(B)U (G)R 4 F 2714(-)S 2 F (AH)R 2621 2394(D)U (H)R 4 F 2717(-)S 2 F (EG)R 6 F 2860 2382(H)U 2860 2442(J)U 2860 2502(J)U 2860 2562(P)U 1 F 3121 2736(e)U 556 2808(u)U 556 2736(The)U 678(composition)S 1004(of)S 1082(two)S 1200(perspective)S 1503(mappings)S 1765(is)S 1833(also)S 1958(a)S 2013(perspective)S 2316(mapping.)S 2590(Consequently,)S 2963(a)S 3017(plan)S 586 2808(sing)U 707(a)S 755(perspective)S 1050(paramete)S 1272(rization)S 1477(that)S 1588(is)S 1648(viewed)S 1842(in)S 1909(perspective)S 2204(will)S 2318(have)S 2452(a)S 2499(compound)S 2773(mapping)S 3004(of)S 3074(the)S 556 2880(perspective)U 851(form.)S 1023(For)S 1126(screen)S 1300(scanning)S 1534(we)S 1624(compute)S 2 F 1852(u)S 1 F 1912(and)S 2 F 2019(v)S 1 F 2076(from)S 2 F 2213(x)S 1 F 2270(and)S 2 F 2377(y)S 1 F 2434(as)S 2504(follows:)S 2 F 1425 3012(u)U 4 F 1485(=)S 2 F 1558 3054(gx)U 4 F 1625(+)S 2 F (hy)R 4 F 1725(+)S 2 F (i)R 1553 2976(a)U (x)R 4 F 1620(+)S 2 F (by)R 4 F 1720(+)S 2 F (c)R 6 F 1544 2994(h)U 1549(hhhhhhhh)S 1 F 1795 3012(,)U 2 F 1910(v)S 4 F 1967(=)S 2 F 2041 3054(gx)U 4 F 2108(+)S 2 F (hy)R 4 F 2208(+)S 2 F (i)R 2035 2976(d)U (x)R 4 F 2102(+)S 2 F (ey)R 4 F 2199(+)S 2 F 2237(f)S 6 F 2026 2994(h)U 2033(hhhhhhhh)S 1 F 3121 3150(e)U 556 3222(i)U 556 3150(Perspective)U 859(mapping)S 1095(simpli\256es)S 1354(to)S 1426(the)S 1525(af\256ne)S 1687(form)S 1829(when)S 2 F 1983(G)S 4 F 2036(=)S 2 F (H)R 4 F 2122(=)S 2 F (g)R 4 F 2195(=)S 2 F (h)R 4 F 2268(=)S 1 F (0,)R 2370(which)S 2541(occurs)S 2722(when)S 2876(the)S 2974(surfac)S 573 3222(s)U 616(parallel)S 818(to)S 885(the)S 979(projection)S 1244(plane.)S 556 3315(A)U (oki)R 698(and)S 807(Levine)S 997(demonstrate)S 1314(texture)S 1504(mapping)S 1737(polygons)S 1979(in)S 2048(perspective)S 2345(using)S 2497(formulas)S 2733(equivalent)S 3006(to)S 3074(the)S 3121 3387(e)U 556 3459(c)U 556 3387(above)U 722([Aok78].)S 982(Smith)S 1148(proves)S 1330(that)S 1443(the)S 1539(division)S 1755(is)S 1817(necessary)S 2073(in)S 2142(general,)S 2357(and)S 2465(shows)S 2635(how)S 2 F 2759(u)S 1 F 2820(and)S 2 F 2928(v)S 1 F 2986(can)S 3091(b)S 583 3459(alculat)U 745(ed)S 825(increment)S 1067(ally)S 1181(from)S 2 F 1321(x)S 1 F 1381(and)S 2 F 1490(y)S 1 F 1549(as)S 1621(a)S 1670(polygon)S 1889(is)S 1951(scanned)S 2167([Smi80].)S 2421(As)S 2509(discussed)S 2761(earlier,)S 2953(Catmull)S 3133 3531(,)U 556 3603(P)U 556 3531(and)U 672(Smith)S 845(decompose)S 1145(perspective)S 1449(mappings)S 1712(into)S 1835(two)S 1954(passes)S 2136(of)S 2215(shears)S 2394(and)S 2510(scales)S 2682([Cat80].)S 2929(Gangnet)S 589 3603(erny,)U 734(and)S 844(Coueignoux)S 1161(explore)S 1365(an)S 1445(alternat)S 1627(e)S 1677(decomposition)S 2055(that)S 2168(rotates)S 2351(screen)S 2527(and)S 2636(texture)S 2826(space)S 2982(so)S 3057(that)S 556 3768(H)U 556 3675(the)U 650(perspective)S 945(occurs)S 1122(along)S 1276(one)S 1383(of)S 1453(the)S 1547(image)S 1715(axes)S 1842([Gan82].)S 599 3768(eckbert)U 809(promotes)S 1065(the)S 1171(homogeneous)S 1537(matrix)S 1727(notation)S 1957(for)S 2059(perspective)S 2366(texture)S 2565(mapping)S 2807(and)S 2925(discusses)S 3125 3840(s)U 556 3912(o)U 556 3840(techniques)U 839(for)S 934(scanning)S 1173(in)S 1245(screen)S 1423(space)S 1581([Hec83].)S 1837(Since)S 1995(the)S 2093(formulas)S 2331(for)S 2 F 2425(u)S 1 F 2489(and)S 2 F 2600(v)S 1 F 2661(above)S 2829(are)S 2927(quotient)S 586 3912(f)U 629(linear)S 790(expressions,)S 1108(they)S 1235(can)S 1342(be)S 1422(computed)S 1683(increment)S 1925(ally)S 2039(at)S 2106(a)S 2156(cost)S 2276(of)S 2349(3)S 2402(adds)S 2535(and)S 2645(2)S 2698(divides)S 2895(per)S 2994(screen)S 3133 3984(,)U 556 4056(a)U 556 3984(pixel.)U 735(Heckbert)S 979(also)S 1099(discusses)S 1345(methods)S 1572(for)S 1665(computing)S 1946(the)S 2043(3x3)S 2156(matrice)S 2338(s.)S 2419(Since)S 2576(they)S 2703(are)S 2799(homogeneous)S 583 4056(ll)U 640(scalar)S 804(multiple)S 1006(s)S 1052(of)S 1125(these)S 1272(matrice)S 1454(s)S 1500(are)S 1597(equivalent)S 1849(.)S 1907(If)S 1970(we)S 2063(arbitraril)S 2275(y)S 2328(choose)S 2 F 2518(i)S 4 F 2545(=)S 1 F (1)R 2630(this)S 2739(leaves)S 2912(8)S 2964(degrees)S 3133 4128(,)U 556 4200(w)U 556 4128(of)U 628(freedom.)S 886(These)S 1051(8)S 1102(values)S 1277(can)S 1382(be)S 1460(computed)S 1719(empirica)S 1931(lly)S 2016(by)S 2097(solving)S 2295(an)S 2373(8x8)S 2484(system)S 2672(of)S 2743(linear)S 2902(equations)S 599 4200(hich)U 723(is)S 783(de\256ned)S 980(by)S 1060(the)S 1154(texture)S 1342(and)S 1449(screen)S 1623(coordinates)S 1921(of)S 1991(four)S 2111(points)S 2278(in)S 2345(the)S 2439(plane.)S 3279 4710(-)U 16(--)S 3259(-)S EP %%Page: ? 6 BP 1 F 60 Z 1797 246(-)U 1837(6)S 1887(-)S 556 531(T)U 3 F 556 438(Patches)U 1 F 593 531(exture)U 768(mapping)S 1003(is)S 1067(quite)S 1211(popular)S 1418(for)S 1511(surfaces)S 1731(modeled)S 1962(from)S 2102(patches,)S 2321(probably)S 2558(for)S 2651(two)S 2764(reasons:)S 2984(\(a\))S 3074(the)S 556 675(r)U 556 603(paramete)U 778(rization)S 989(comes)S 1169(for)S 1265(free,)S 1400(\(b\))S 1496(the)S 1595(cost)S 1717(of)S 1792(texture)S 1985(mapping)S 2221(is)S 2286(small)S 2442(relative)S 2649(to)S 2721(the)S 2820(cost)S 2942(of)S 3017(patch)S 576 675(endering.)U 843(Patches)S 1048(are)S 1143(usually)S 1338(rendered)S 1569(using)S 1719(a)S 1766(subdivision)S 2063(algorithm)S 2318(whereby)S 2545(screen)S 2719(and)S 2826(texture)S 3014(space)S 3133 747(,)U 556 819(t)U 556 747(areas)U 705(are)S 804(subdivided)S 1093(in)S 1165(parallel)S 1372([Cat74].)S 1615(As)S 1705(an)S 1786(alternat)S 1968(ive)S 2066(technique,)S 2340(Catmull)S 2559(and)S 2670(Smith)S 2838(demonstrate)S 573 819(heoretica)U 795(lly)S 881(at)S 947(least,)S 1095(that)S 1208(it)S 1264(is)S 1326(possible)S 1545(to)S 1614(perform)S 1830(texture)S 2020(mapping)S 2252(on)S 2333(bilinear,)S 2554(biquadratic)S 2826(,)S 2862(and)S 2970(bicubic)S 3128 891(-)U 556 963(l)U 556 891(patches)U 757(with)S 884(two-pass)S 1117(algorithms)S 1395([Cat80].)S 1634(Shantz)S 1818(and)S 1925(Fraser,)S 2110(Schowengerdt,)S 2489(and)S 2596(Briggs)S 2776(explore)S 2977(a)S 3024(simi)S 573 963(ar)U 654(method)S 869(for)S 973(the)S 1081(purpose)S 1305(of)S 1389(geometric)S 1665(image)S 1847(distortions)S 2135([Sha82],)S 2374([Fra85].)S 2623(Two-pass)S 2890(algorithms)S 3 F 556 1251(F)U 1 F 556 1035(require)U 747(1-D)S 860(space)S 1014(variant)S 1202(texture)S 1390(\256lters.)S 3 F 593 1251(ILTERING)U 1 F 556 1344(A)U (fter)R 708(the)S 806(mapping)S 1041(is)S 1105(computed)S 1367(and)S 1478(the)S 1576(texture)S 1768(is)S 1832(warped,)S 2048(the)S 2146(image)S 2318(must)S 2459(be)S 2540(resampled)S 2812(on)S 2896(the)S 2994(screen)S 556 1509(T)U 556 1416(grid.)U 708(This)S 835(process)S 1035(is)S 1095(called)S 2 F 1260(\256ltering)S 1 F (.)R 593 1509(he)U 677(cheapest)S 912(texture)S 1107(\256ltering)S 1325(method)S 1533(is)S 1600(point)S 1751(sampling,)S 2013(wherein)S 2233(the)S 2333(pixel)S 2480(nearest)S 2677(the)S 2777(desired)S 2977(sample)S 3125 1581(s)U 556 1653(a)U 556 1581(point)U 705(is)S 770(used.)S 940(It)S 1002(works)S 1172(relative)S 1354(ly)S 1425(well)S 1553(on)S 1637(unscaled)S 1872(images,)S 2082(but)S 2183(for)S 2277(stretched)S 2519(images)S 2714(the)S 2812(texture)S 3004(pixel)S 583 1653(re)U 650(visible)S 831(as)S 901(large)S 1042(blocks,)S 1234(and)S 1341(for)S 1431(shrunken)S 1671(images)S 1862(aliasing)S 2070(can)S 2174(cause)S 2328(distracting)S 2603(moire)S 2764(patterns.)S 556 1890(A)U 3 F 556 1797(Aliasing)U 1 F 599 1890(liasing)U 789(can)S 902(result)S 1065(when)S 1224(a)S 1280(signal)S 1453(has)S 1562(unreproducible)S 1956(high)S 2092(frequencie)S 2347(s)S 2399([Cro77],)S 2633([Whi81].)S 2901(In)S 2980(texture)S 3128 1962(-)U 556 2034(i)U 556 1962(mapping,)U 806(it)S 864(is)S 928(most)S 1069(noticeabl)S 1291(e)S 1342(on)S 1426(high)S 1557(contrast,)S 1787(high)S 1918(frequency)S 2182(textures.)S 2431(Rather)S 2615(than)S 2742(accept)S 2920(the)S 3017(alias)S 573 2034(ng)U 658(that)S 774(results)S 956(from)S 1098(point)S 1247(sampling)S 1493(or)S 1568(avoid)S 1727(those)S 1879(models)S 2078(which)S 2250(exhibit)S 2443(it,)S 2517(we)S 2612(prefer)S 2781(a)S 2833(high)S 2965(quality,)S 556 2178(c)U 556 2106(robust)U 728(image)S 898(synthesis)S 1140(system)S 1328(that)S 1440(does)S 1571(the)S 1666(extra)S 1808(work)S 1952(required)S 2174(to)S 2242(elimina)S 2424(te)S 2489(it.)S 2579(In)S 2650(practice)S 2842(,)S 2878(total)S 3007(eradi-)S 583 2178(ation)U 730(of)S 806(aliasing)S 1020(is)S 1086(often)S 1236(impracti)S 1438(cal,)S 1550(and)S 1662(we)S 1757(must)S 1899(settle)S 2052(for)S 2147(approximati)S 2439(ons)S 2547(that)S 2663(merely)S 2856(reduce)S 3042(it)S 3101(to)S 556 2343(T)U 556 2250(unobjectiona)U 868(ble)S 962(levels.)S 593 2343(wo)U 686(approaches)S 977(to)S 1044(the)S 1138(aliasing)S 1346(problem)S 1567(are:)S 616 2487(b)U 616 2415(a\))U 683(Point)S 830(sample)S 1021(at)S 1085(higher)S 1259(resolution)S 646 2487(\))U 686(Low)S 816(pass)S 939(\256lter)S 1073(before)S 1247(sampling)S 556 2580(T)U (he)R 678(\256rst)S 798(method)S 1006(theoretic)S 1218(ally)S 1336(implies)S 1541(sampling)S 1789(at)S 1860(a)S 1914(resolution)S 2182(determine)S 2424(d)S 2481(by)S 2568(the)S 2669(highest)S 2870(frequencie)S 3125(s)S 3125 2652(s)U 556 2724(r)U 556 2652(present)U 760(in)S 837(the)S 941(image.)S 1154(Since)S 1318(a)S 1375(surface)S 1579(viewed)S 1783(obliquely)S 2041(can)S 2155(create)S 2330(arbitraril)S 2542(y)S 2602(high)S 2739(frequencie)S 2994(s,)S 3061(thi)S 576 2724(esolution)U 823(can)S 933(be)S 1016(extremel)S 1228(y)S 1284(high.)S 1452(It)S 1515(is)S 1581(therefore)S 1825(desirable)S 2069(to)S 2142(limit)S 2283(dense)S 2446(supersampling)S 2823(to)S 2896(regions)S 3098(of)S 3133 2796(.)U 556 2868(W)U 556 2796(high)U 687(frequency)S 952(and)S 1062(high)S 1192(contrast)S 1406(by)S 1489(adapting)S 1720(the)S 1817(sampling)S 2061(rate)S 2175(to)S 2245(the)S 2342(local)S 2483(intensity)S 2714(variance)S 2942([Lee85])S 613 2868(hether)U 785(adaptive)S 1011(or)S 1082(uniform)S 1297(point)S 1442(sampling)S 1683(is)S 1743(used,)S 1888(stochastic)S 2146(sampling)S 2387(can)S 2491(improve)S 2712(the)S 2806(appearanc)S 3051(e)S 3098(of)S 556 3033(T)U 556 2940(images)U 747(signi\256cantly)S 1065(by)S 1145(trading)S 1336(off)S 1426(aliasing)S 1634(for)S 1724(noise)S 1871([Coo86].)S 593 3033(he)U 673(second)S 863(method,)S 1082(low)S 1195(pass)S 1321(\256ltering)S 1535(before)S 1712(sampling,)S 1971(is)S 2034(preferable)S 2302(because)S 2515(it)S 2571(addresses)S 2823(the)S 2919(causes)S 3098(of)S 556 3177(f)U 556 3105(aliasing)U 770(rather)S 936(than)S 1065(its)S 1147(symptoms.)S 1454(To)S 1546(elimina)S 1728(te)S 1797(aliasing)S 2010(our)S 2115(signals)S 2307(must)S 2449(be)S 2531(band-limit)S 2783(ed)S 2865(\(contain)S 3088(no)S 576 3177(requencie)U 811(s)S 856(above)S 1022(the)S 1118(Nyquist)S 1330(limit\).)S 1522(When)S 1688(a)S 1737(signal)S 1903(is)S 1965(warped)S 2163(and)S 2271(resampled)S 2540(the)S 2635(following)S 2890(steps)S 3031(must)S 556 3249(theoretic)U 768(ally)S 879(be)S 956(performed)S 1227([Smi83]:)S 616 3321(1.)U 681(reconstruct)S 969(continuous)S 1253(signal)S 1417(from)S 1554(input)S 1698(samples)S 1912(by)S 1992(convolution)S 616 3465(3)U 616 3393(2.)U 681(warp)S 821(the)S 915(abscissa)S 1132(of)S 1202(the)S 1296(signal)S 646 3465(.)U 681(low)S 791(pass)S 914(\256lter)S 1048(the)S 1142(signal)S 1306(using)S 1456(convolution)S 1824 3537(s)U 556 3609(T)U 616 3537(4.)U 681(resample)S 919(the)S 1013(signal)S 1177(at)S 1241(the)S 1335(output)S 1509(sample)S 1700(point)S 593 3609(hese)U 725(methods)S 954(are)S 1053(well)S 1182(understood)S 1474(for)S 1569(linear)S 1732(warps,)S 1915(where)S 2087(the)S 2186(theory)S 2365(of)S 2440(linear)S 2603(systems)S 2817(lends)S 2968(support)S 556 3753(m)U 556 3681([Opp75];)U 801(but)S 903(for)S 998(nonlinear)S 1251(warps)S 1419(such)S 1554(as)S 1629(perspective)S 1904(,)S 1943(the)S 2041(theory)S 2219(is)S 2283(lacking,)S 2500(and)S 2611(a)S 2662(number)S 2870(of)S 2944(approxi-)S 603 3753(ate)U 694(methods)S 918(have)S 1052(sprung)S 1235(up.)S 556 3990(F)U 3 F 556 3897(Space)U 726(Invariant)S 989(Filteri)S 1151(ng)S 1 F 589 3990(or)U 661(af\256ne)S 820(image)S 990(warps)S 1155(the)S 1251(\256lter)S 1387(is)S 2 F 1449(space)S 1608(invariant)S 1 F (;)R 1868(the)S 1964(\256lter)S 2100(shape)S 2259(remains)S 2472(constant)S 2694(as)S 2765(it)S 2820(moves)S 2998(across)S 556 4062(the)U 650(image.)S 853(The)S 967(four)S 1087(steps)S 1227(above)S 1391(simplify)S 1612(to:)S 616 4134(1.)U 681(low)S 791(pass)S 914(\256lter)S 1048(the)S 1142(input)S 1286(signal)S 1450(using)S 1600(convolution)S 616 4278(3)U 616 4206(2.)U 681(warp)S 821(the)S 915(abscissa)S 1132(of)S 1202(the)S 1296(signal)S 646 4278(.)U 681(resample)S 919(the)S 1013(signal)S 1177(at)S 1241(the)S 1335(output)S 1509(sample)S 1700(points)S 3279 4710(-)U 16(--)S 3259(-)S EP %%Page: ? 7 BP 1 F 60 Z 1797 246(-)U 1837(7)S 1887(-)S 3131 438(t)U 556 510(o)U 556 438(Space)U 722(invariant)S 959(\256ltering)S 1171(is)S 1232(often)S 1377(done)S 1515(using)S 1666(an)S 1744(FFT,)S 1883(a)S 1931(multiply,)S 2172(and)S 2280(an)S 2358(inverse)S 2553(FFT)S 2677([Opp75].)S 2936(The)S 3051(cos)S 586 510(f)U 626(this)S 733(operation)S 981(is)S 1041(independent)S 1356(of)S 1426(the)S 1520(\256lter)S 1654(size.)S 556 747(N)U 3 F 556 654(Space)U 726(Variant)S 946(Filteri)S 1108(ng)S 1 F 599 747(onlinear)U 824(mappings)S 1085(require)S 2 F 1283(space)S 1447(variant)S 1 F 1648(\256lters,)S 1827(whose)S 2007(shape)S 2171(varies)S 2342(as)S 2419(they)S 2549(move)S 2709(across)S 2885(the)S 2985(image.)S 556 912(I)U 556 819(Space)U 720(variant)S 908(\256lters)S 1065(are)S 1159(more)S 1303(complex)S 1531(and)S 1638(less)S 1748(well)S 1872(understood)S 2159(than)S 2283(space)S 2437(invariant)S 2672(\256lters.)S 576 912(n)U 635(general,)S 857(a)S 913(square)S 1099(screen)S 1282(pixel)S 1432(that)S 1552(intersects)S 1809(a)S 1865(curved)S 2058(surface)S 2261(has)S 2370(a)S 2426(curvilinea)S 2668(r)S 2717(quadrilate)S 2959(ral)S 3051(pre-)S 556 1056(o)U 556 984(image)U 726(in)S 795(texture)S 985(space.)S 1176(Most)S 1321(methods)S 1547(approximate)S 1870(the)S 1965(true)S 2080(mapping)S 2312(by)S 2393(the)S 2488(locally)S 2674(tangent)S 2873(perspective)S 586 1056(r)U 627(linear)S 786(mapping,)S 1033(so)S 1107(that)S 1219(the)S 1314(curvilinea)S 1556(r)S 1597(pre-image)S 1862(is)S 1922(approximate)S 2224(d)S 2274(by)S 2354(a)S 2401(quadrilate)S 2643(ral)S 2727(or)S 2797(parallel)S 2979(ogram.)S 556 1200(b)U 556 1128(If)U 627(pixels)S 802(are)S 907(instead)S 1109(regarded)S 1351(as)S 1432(circles,)S 1636(their)S 1777(pre-images)S 2075(are)S 2179(ellipses.)S 2425(This)S 2562(model)S 2743(is)S 2813(often)S 2967(simpler)S 586 1200(ecause)U 768(an)S 846(ellipse)S 1024(has)S 1124(\256ve)S 1234(degrees)S 1438(of)S 1508(freedom)S 1729(\(two)S 1859(for)S 1949(position,)S 2178(two)S 2288(for)S 2378(radii,)S 2524(and)S 2631(one)S 2738(for)S 2828(angle\),)S 3014(while)S 3125 1272(s)U 556 1344(h)U 556 1272(a)U 607(quadrilate)S 849(ral)S 937(has)S 1040(eight.)S 1219(Figure)S 1399(2)S 1452(shows)S 1624(the)S 1721(pre-images)S 2012(of)S 2085(several)S 2279(square)S 2459(screen)S 2636(pixels)S 2803(and)S 2913(illustrate)S 586 1344(ow)U 680(pixels)S 845(near)S 970(a)S 1018(horizon)S 1223(or)S 1294(silhouette)S 1550(require)S 1742(\256ltering)S 1954(of)S 2025(large,)S 2182(highly)S 2356(elongated)S 2611(areas.)S 2790(One)S 2910(of)S 2980(texture)S 3125 1416(s)U 556 1488(a)U 556 1416(\256ltering's)U 819(greatest)S 1036(challenge)S 1268(s)S 1320(is)S 1389(\256nding)S 1588(ef\256cient)S 1815(algorithms)S 2102(for)S 2201(\256ltering)S 2421(fairly)S 2581(general)S 2788(areas)S 2940(\(such)S 3098(a)S 583 1488(rbitrarily)U 818(oriented)S 1036(ellipses)S 1237(or)S 1307(quadrilate)S 1549(rals\).)S 556 1581(T)U (he)R 672(cross)S 817(sectional)S 1054(shape)S 1212(of)S 1283(the)S 1378(\256lter)S 1513(is)S 1574(also)S 1692(important.)S 1983(Theoretic)S 2215(ally)S 2327(we)S 2418(should)S 2599(use)S 2700(the)S 2795(ideal)S 2934(low)S 3045(pass)S 556 1725(m)U 556 1653(\256lter,)U 2 F 712(sinc)S 1 F 819(\()S 2 F (x)R 1 F 876(\))S 4 F (=)R 1 F (sin\()R 4 F (p)R 2 F (x)R 1 F 1089(\))S 4 F (/p)R 2 F (x)R 1 F 1196(,)S 1238(but)S 1342(its)S 1426(in\256nite)S 1623(width)S 1786(makes)S 1966(it)S 2026(impracti)S 2228(cal)S 2325(for)S 2421(computati)S 2663(on.)S 2784(In)S 2860(practice)S 3078(we)S 603 1725(ust)U 696(use)S 799(a)S 849(\256nite)S 996(impulse)S 1210(response)S 1443(\(FIR\))S 1599(\256lter)S 1736([Opp75].)S 1997(Commonly)S 2291(used)S 2424(FIR)S 2539(\256lters)S 2698(are)S 2794(the)S 2890(box,)S 3017(trian-)S 556 1890(M)U 556 1797(gle,)U 665(cubic)S 816(b-spline,)S 1045(and)S 1152(truncated)S 1397(gaussian)S 1624(\(\256gure)S 1804(3\).)S 609 1890(ost)U 702(algorithms)S 983(for)S 1076(texture)S 1267(\256ltering)S 1481(allow)S 1638(\256ltering)S 1852(requests)S 2072(to)S 2142(be)S 2222(made)S 2376(in)S 2446(arbitrary)S 2676(order.)S 2860(Such)S 3002(a)S 3051(ran-)S 556 2034(p)U 556 1962(dom)U 692(access)S 875(capabili)S 1067(ty)S 1143(is)S 1212(important)S 1476(for)S 1575(applicat)S 1767(ions)S 1896(such)S 2034(as)S 2112(re\257ection)S 2368(mapping)S 2607(or)S 2685(ray)S 2790(tracing,)S 3001(which)S 586 2034(roduce)U 770(widely)S 954(scattere)S 1139(d)S 1189(requests.)S 556 2127(M)U (ethods)R 786(for)S 876(random)S 1080(access)S 1254(space)S 1408(variant)S 1596(\256ltering)S 1807(can)S 1911(be)S 1988(categoriz)S 2210(ed)S 2287(as)S 2357(follows:)S 772 2307(2)U 772 2235(1.)U 837(direct)S 995(convolution)S 802 2307(.)U 837(pre\256ltering)S 1125(\(pyramid)S 1366(or)S 1436(integrate)S 1648(d)S 1698(array\))S 3 F 556 2559(D)U 1 F 772 2379(3.)U 837(fourier)S 1021(series)S 3 F 599 2559(irect)U 737(Convolution)S 1 F 556 2652(T)U (he)R 675(most)S 817(straightforward)S 1213(\256ltering)S 1429(technique)S 1688(is)S 2 F 1752(direct)S 1917(convolution)S 1 F (,)R 2241(which)S 2412(directly)S 2621(computes)S 2876(a)S 2927(weighted)S 2 F 556 2868(C)U 1 F 556 2724(average)U 764(of)S 834(texture)S 1022(samples.)S 1271(We)S 1375(now)S 1498(summarize)S 1783(several)S 1974(direct)S 2132(convolution)S 2440(methods.)S 2 F 596 2868(atmull,)U 785(1974)S 1 F 556 2961(I)U (n)R 642(his)S 748(subdivision)S 1061(patch)S 1228(renderer,)S 1480(Catmull)S 1710(computes)S 1976(an)S 2068(unweighted)S 2384(average)S 2607(of)S 2692(the)S 2801(texture)S 3004(pixels)S 3128 3033(-)U 556 3105(t)U 556 3033(corresponding)U 921(to)S 989(each)S 1120(screen)S 1294(pixel)S 1435([Cat74].)S 1674(He)S 1764(gives)S 1911(few)S 2021(details,)S 2214(but)S 2311(his)S 2401(\256lter)S 2535(appears)S 2739(to)S 2806(be)S 2883(a)S 2930(quadrila)S 573 3105(eral)U 684(with)S 811(a)S 858(box)S 968(cross)S 1111(section.)S 556 3342(B)U 2 F 556 3249(Blinn)U 707(and)S 817(Newell,)S 1020(1976)S 1 F 596 3342(linn)U 712(and)S 821(Newell)S 1017(improve)S 1239(on)S 1320(this)S 1428(with)S 1556(a)S 1604(triangular)S 1860(\256lter)S 1995(that)S 2107(forms)S 2268(overlapping)S 2577(square)S 2755(pyramids)S 3000(2)S 3051(pix-)S 3128 3414(-)U 556 3486(l)U 556 3414(els)U 646(wide)S 786(in)S 856(screen)S 1033(space)S 1190([Bli76].)S 1422(At)S 1505(each)S 1639(pixel)S 1782(the)S 1878(pyramid)S 2101(is)S 2163(distorted)S 2396(to)S 2465(\256t)S 2537(the)S 2633(approximati)S 2925(ng)S 3007(paral)S 573 3486(elogram)U 791(in)S 858(texture)S 1046(space,)S 1215(and)S 1322(a)S 1369(weighted)S 1610(average)S 1818(is)S 1878(computed.)S 556 3723(T)U 2 F 556 3630(Feibush,)U 785(Levoy,)S 964(and)S 1074(Cook,)S 1236(1980)S 1 F 593 3723(he)U 670(\256lter)S 804(used)S 934(by)S 1014(Feibush,)S 1239(Levoy,)S 1428(and)S 1535(Cook)S 1685(is)S 1745(more)S 1889(elaborate)S 2131([Fei80].)S 556 3909(\()U 556 3816(The)U 670(following)S 924(steps)S 1064(are)S 1158(taken)S 1309(at)S 1373(each)S 1504(screen)S 1678(pixel:)S 576 3909(1\))U 706(Center)S 888(the)S 983(\256lter)S 1118(function)S 1340(\(box,)S 1486(cylinder,)S 1720(cone,)S 1870(or)S 1941(gaussian\))S 2189(on)S 2270(the)S 2365(pixel)S 2507(and)S 2615(\256nd)S 2729(its)S 2807(bounding)S 3054(rec-)S 556 4074(\()U 706 3981(tangle.)U 576 4074(2\))U 706(Transform)S 985(the)S 1084(rectangle)S 1331(to)S 1403(texture)S 1596(space,)S 1770(where)S 1942(it)S 2001(is)S 2066(a)S 2118(quadrilate)S 2360(ral.)S 2483(The)S 2601(sides)S 2745(of)S 2819(this)S 2930(quadrila-)S 16 4710(-)U 706 4146(teral)U 834(are)S 928(assumed)S 1155(to)S 1222(be)S 1299(straight.)S 1535(Find)S 1665(a)S 1712(bounding)S 1959(rectangle)S 2201(for)S 2291(this)S 2398(quadrilate)S 2640(ral.)S 36 4710(-)U 3259(--)S EP %%Page: ? 8 BP 1 F 60 Z 1797 246(-)U 1837(8)S 1887(-)S 2298 438(.)U 556 531(\()U 556 438(\(3\))U 706(Map)S 836(all)S 917(pixels)S 1081(inside)S 1245(the)S 1339(texture)S 1527(space)S 1681(rectangle)S 1923(to)S 1990(screen)S 2164(space)S 576 531(4\))U 706(Form)S 867(a)S 925(weighted)S 1177(average)S 1396(of)S 1477(the)S 1582(mapped)S 1804(texture)S 2003(pixels)S 2178(using)S 2339(a)S 2397(two-dimensional)S 2833(lookup)S 3030(table)S 556 696(S)U 706 603(indexed)U 917(by)S 997(each)S 1128(sample's)S 1362(location)S 1577(within)S 1751(the)S 1845(pixel.)S 589 696(ince)U 710(the)S 804(\256lter)S 938(function)S 1159(is)S 1219(in)S 1286(a)S 1333(lookup)S 1520(table)S 1658(it)S 1712(can)S 1816(be)S 1893(a)S 1940(gaussian)S 2167(or)S 2237(other)S 2381(high)S 2508(quality)S 2696(\256lter.)S 556 933(T)U 2 F 556 840(Gangnet,)U 798(Perny,)S 977(and)S 1087(Coueignoux,)S 1413(1982)S 1 F 593 933(he)U 684(texture)S 886(\256lter)S 1034(proposed)S 1288(by)S 1382(Gangnet,)S 1634(Perny,)S 1822(and)S 1942(Coueignoux)S 2269(is)S 2342(quite)S 2496(similar)S 2697(to)S 2777(the)S 2884(method)S 3098(of)S 556 1098(P)U 556 1005(Feibush)U 766(et.)S 845(al.,)S 939(but)S 1036(they)S 1160(subdivide)S 1414(uniformly)S 1675(in)S 1742(screen)S 1916(space)S 2070(rather)S 2231(than)S 2355(texture)S 2543(space)S 2697([Gan82].)S 589 1098(ixels)U 725(are)S 821(assumed)S 1050(to)S 1119(be)S 1198(circular)S 1405(and)S 1514(overlapping.)S 1859(The)S 1975(pre-image)S 2242(of)S 2313(a)S 2361(screen)S 2536(circle)S 2692(is)S 2753(a)S 2801(texture)S 2990(ellipse)S 3128 1170(-)U 556 1242(s)U 556 1170(whose)U 736(major)S 904(axis)S 1028(corresponds)S 1345(to)S 1419(the)S 1520(direction)S 1762(of)S 1838(greatest)S 2052(compression.)S 2417(A)S 2486(square)S 2669(intermedi)S 2901(ate)S 2998(super)S 579 1242(ampling)U 808(grid)S 936(that)S 1058(is)S 1129(oriented)S 1358(orthogonally)S 1697(to)S 1775(the)S 1880(screen)S 2065(is)S 2136(constructed.)S 2480(The)S 2605(supersampling)S 2987(rate)S 3108(is)S 3128 1314(f)U 556 1386(t)U 556 1314(determine)U 798(d)S 854(from)S 997(the)S 1097(longest)S 1297(diagonal)S 1530(of)S 1605(the)S 1704(parallel)S 1886(ogram)S 2065(approximati)S 2357(ng)S 2442(the)S 2541(texture)S 2734(ellipse.)S 2952(Each)S 3098(o)S 573 1386(he)U 652(sample)S 845(points)S 1014(on)S 1096(the)S 1191(intermedi)S 1423(ate)S 1515(grid)S 1633(is)S 1694(mapped)S 1906(to)S 1974(texture)S 2163(space,)S 2333(and)S 2441(bilinear)S 2647(interpolat)S 2879(ion)S 2977(is)S 3038(used)S 3128 1458(-)U 556 1530(c)U 556 1458(to)U 624(reconstruct)S 912(the)S 1006(texture)S 1194(values)S 1368(at)S 1432(these)S 1576(sample)S 1767(points.)S 1969(The)S 2083(texture)S 2271(values)S 2445(are)S 2539(then)S 2663(weighted)S 2904(by)S 2984(a)S 3031(trun)S 583 1530(ated)U 2 F 704(sinc)S 1 F 831(2)S 881(pixels)S 1045(wide)S 1182(in)S 1249(screen)S 1423(space)S 1577(and)S 1684(summed.)S 3128 1623(')U 556 1695(m)U 556 1623(The)U 685(paper)S 854(contrasts)S 1103(Feibush's)S 1371(``back)S 1560(transforming'')S 1946(method)S 2162(with)S 2303(their)S 2448(own)S 2585(``direct)S 2797(transforming')S 603 1695(ethod,)U 777(claimi)S 929(ng)S 1014(that)S 1130(the)S 1229(latter)S 1379(produces)S 1621(more)S 1770(accurat)S 1945(e)S 1997(results)S 2179(because)S 2395(the)S 2493(sampling)S 2738(grid)S 2859(is)S 2923(in)S 2994(screen)S 3125 1767(s)U 556 1839(m)U 556 1767(space)U 720(rather)S 891(than)S 1025(in)S 1102(texture)S 1300(space.)S 1499(Other)S 1666(difference)S 1911(s)S 1964(are)S 2068(more)S 2222(signi\256cant.)S 2538(For)S 2651(example,)S 2901(Gangnet')S 603 1839(ethod)U 759(requires)S 975(a)S 1024(bilinear)S 1231(interpolat)S 1463(ion)S 1562(for)S 1654(each)S 1787(sample)S 1980(point,)S 2141(while)S 2297(Feibush's)S 2552(method)S 2755(does)S 2887(not.)S 3020(Also,)S 556 1983(t)U 556 1911(Gangnet)U 787(samples)S 1008(at)S 1079(an)S 1163(unnecessarily)S 1518(high)S 1652(frequency)S 1920(along)S 2081(the)S 2182(minor)S 2353(axis)S 2476(of)S 2552(the)S 2652(texture)S 2846(ellipse.)S 3065(For)S 573 1983(hese)U 700(two)S 810(reasons,)S 1025(Feibush's)S 1278(algorithm)S 1533(is)S 1593(probably)S 1827(faster)S 1981(than)S 2105(Gangnet's.)S 556 2220(T)U 2 F 556 2127(Greene)U 753(and)S 863(Heckbert,)S 1119(1986)S 1 F 593 2220(he)U 678(ellipti)S 820(cal)S 919(weighted)S 1168(average)S 1384(\256lter)S 1526(\(EWA\))S 1731(proposed)S 1979(by)S 2067(Heckbert)S 2316([Gre86b])S 2564(is)S 2632(similar)S 2827(to)S 2901(Gangnet's)S 3125 2292(s)U 556 2364(l)U 556 2292(method)U 761(in)S 832(that)S 947(it)S 1005(assumes)S 1229(overlapping)S 1541(circular)S 1750(pixels)S 1918(that)S 2033(map)S 2161(to)S 2232(arbitraril)S 2444(y)S 2498(oriented)S 2720(ellipses,)S 2940(and)S 3051(it)S 3108(i)S 573 2364(ike)U 668(Feibush's)S 922(because)S 1134(the)S 1229(\256lter)S 1364(function)S 1586(is)S 1647(stored)S 1815(in)S 1883(a)S 1931(lookup)S 2119(table,)S 2273(but)S 2371(instead)S 2562(of)S 2632(mapping)S 2863(texture)S 3051(pix-)S 3128 2436(-)U 556 2508(t)U 556 2436(els)U 645(to)S 714(screen)S 890(space,)S 1061(the)S 1157(\256lter)S 1293(is)S 1355(mapped)S 1568(to)S 1637(texture)S 1827(space.)S 2018(The)S 2134(\256lter)S 2270(shape,)S 2444(a)S 2492(circularl)S 2694(y)S 2745(symmetric)S 3021(func)S 573 2508(ion)U 674(in)S 745(screen)S 923(space,)S 1096(is)S 1160(warped)S 1361(by)S 1445(an)S 1526(ellipti)S 1668(c)S 1718(paraboloid)S 1999(function)S 2223(into)S 2340(an)S 2420(ellipse)S 2601(in)S 2671(texture)S 2862(space.)S 3054(The)S 3121 2580(e)U 556 2652(i)U 556 2580(ellipti)U 698(c)S 748(paraboloid)S 1029(is)S 1092(computed)S 1353(increment)S 1595(ally)S 1709(and)S 1819(used)S 1952(for)S 2045(both)S 2175(ellipse)S 2356(inclusion)S 2600(testing)S 2784(and)S 2894(\256lter)S 3030(tabl)S 573 2652(ndex.)U 757(The)S 883(cost)S 1012(per)S 1121(texture)S 1321(pixel)S 1474(is)S 1546(just)S 1665(a)S 1724(few)S 1845(arithmet)S 2047(ic)S 2122(operations,)S 2419(in)S 2497(contrast)S 2719(to)S 2797(Feibush's)S 3061(and)S 3121 2724(e)U 556 2796(v)U 556 2724(Gangnet's)U 826(methods,)S 1068(which)S 1238(both)S 1368(require)S 1562(mapping)S 1796(each)S 1930(pixel)S 2074(from)S 2213(texture)S 2403(space)S 2559(to)S 2628(screen)S 2804(space,)S 2975(or)S 3047(vic)S 586 2796(ersa.)U 2 F 556 2940(C)U (omparison)R 872(of)S 939(Direct)S 1113(Convolution)S 1431(Methods)S 1 F 556 3033(A)U (ll)R 654(\256ve)S 765(methods)S 990(have)S 1125(a)S 1173(cost)S 1291(per)S 1389(screen)S 1564(pixel)S 1706(proportional)S 2025(to)S 2093(the)S 2188(number)S 2393(of)S 2463(texture)S 2651(pixels)S 2815(accessed,)S 3061(and)S 3121 3105(e)U 556 3177(o)U 556 3105(this)U 669(cost)S 792(is)S 858(highest)S 1058(for)S 1154(Feibush)S 1370(and)S 1483(Gangnet.)S 1748(Since)S 1908(the)S 2008(EWA)S 2171(\256lter)S 2311(is)S 2377(comparable)S 2685(in)S 2758(quality)S 2952(to)S 3024(thes)S 586 3177(ther)U 705(two)S 820(techniques)S 1103(at)S 1172(much)S 1331(lower)S 1493(cost,)S 1630(it)S 1689(appears)S 1898(to)S 1970(be)S 2052(the)S 2151(fastest)S 2330(algorithm)S 2590(for)S 2685(high)S 2817(quality)S 3010(direct)S 3 F 556 3393(P)U 1 F 556 3249(convolution.)U 3 F 593 3393(re\256ltering)U 1 F 556 3486(E)U (ven)R 707(with)S 841(optimiza)S 1053(tion,)S 1188(the)S 1288(methods)S 1518(above)S 1688(are)S 1788(often)S 1938(extremel)S 2150(y)S 2206(slow,)S 2360(since)S 2510(a)S 2563(pixel)S 2710(pre-image)S 2981(can)S 3091(be)S 556 3630(r)U 556 3558(arbitraril)U 768(y)S 830(large)S 983(along)S 1149(silhouettes)S 1439(or)S 1521(at)S 1597(the)S 1703(horizon)S 1919(of)S 2001(a)S 2060(textured)S 2290(plane.)S 2488(Horizon)S 2717(pixels)S 2892(can)S 3007(easily)S 576 3630(equire)U 751(the)S 849(averaging)S 1111(of)S 1185(thousands)S 1449(of)S 1523(texture)S 1715(pixels.)S 1917(We)S 2024(would)S 2197(prefer)S 2364(a)S 2414(texture)S 2605(\256lter)S 2742(whose)S 2918(cost)S 3038(does)S 556 3795(T)U 556 3702(not)U 653(grow)S 796(in)S 863(proportion)S 1137(to)S 1204(texture)S 1392(area.)S 593 3795(o)U 645(speed)S 804(up)S 886(the)S 982(process,)S 1199(the)S 1295(texture)S 1484(can)S 1589(be)S 1667(pre\256ltered)S 1936(so)S 2010(that)S 2122(during)S 2300(rendering)S 2552(only)S 2680(a)S 2728(few)S 2839(samples)S 3054(will)S 556 3939(v)U 556 3867(be)U 635(accessed)S 868(for)S 960(each)S 1093(screen)S 1269(pixel.)S 1447(The)S 1563(access)S 1739(cost)S 1858(of)S 1929(the)S 2024(\256lter)S 2159(will)S 2274(thus)S 2395(be)S 2473(constant,)S 2710(unlike)S 2882(direct)S 3041(con-)S 586 3939(olution)U 786(methods.)S 1054(Two)S 1193(data)S 1323(structures)S 1586(have)S 1729(be)S 1814(used)S 1952(for)S 2050(pre\256ltering:)S 2363(image)S 2539(pyramids)S 2791(and)S 2906(integrate)S 3118(d)S 556 4104(P)U 556 4011(arrays.)U 589 4104(yramid)U 782(data)S 905(structures)S 1161(are)S 1257(commonly)S 1537(used)S 1669(in)S 1738(image)S 1907(processing)S 2185(and)S 2293(computer)S 2542(vision)S 2710([Tan75],)S 2940([Ros84].)S 16 4710(-)U 556 4176(Their)U 707(applicat)S 899(ion)S 996(to)S 1063(texture)S 1251(mapping)S 1482(was)S 1595(apparently)S 1870(\256rst)S 1983(proposed)S 2223(in)S 2290(Catmull's)S 2548(PhD)S 2674(work.)S 36 4710(-)U 3259(--)S EP %%Page: ? 9 BP 1 F 60 Z 556 438(S)U 1797 246(-)U 1837(9)S 1887(-)S 589 438(everal)U 768(texture)S 967(\256lters)S 1135(that)S 1257(employ)S 1469(pre\256ltering)S 1768(are)S 1873(summarized)S 2199(below.)S 2412(Each)S 2563(method)S 2774(makes)S 2958(its)S 3045(own)S 2 F 556 654(p)U 1 F 556 510(trade-off)U 787(between)S 1008(speed)S 1165(and)S 1272(\256lter)S 1406(quality.)S 2 F 586 654(yramid)U 776(\261)S 826(Dungan,)S 1054(Stenger,)S 1273(and)S 1383(Sutty,)S 1539(1978)S 1 F 556 747(D)U (ungan,)R 793(Stenger,)S 1024(and)S 1143(Sutty)S 1302(pre\256lter)S 1525(their)S 1668(texture)S 1867(``tiles'')S 2079(to)S 2157(form)S 2305(a)S 2363(pyramid)S 2595(whose)S 2779(resolutions)S 3074(are)S 3121 819(e)U 556 891(b)U 556 819(powers)U 752(of)S 825(two)S 938([Dun78].)S 1198(To)S 1287(\256lter)S 1423(an)S 1502(ellipti)S 1644(cal)S 1737(texture)S 1927(area)S 2050(one)S 2159(of)S 2231(the)S 2327(pyramid)S 2550(levels)S 2713(is)S 2775(selecte)S 2940(d)S 2992(on)S 3074(th)S 586 891(asis)U 700(of)S 774(the)S 872(average)S 1084(diamete)S 1276(r)S 1320(of)S 1394(the)S 1492(ellipse)S 1673(and)S 1783(that)S 1897(level)S 2038(is)S 2101(point)S 2248(sampled.)S 2507(The)S 2624(memory)S 2848(cost)S 2968(for)S 3061(this)S 3128 963(-)U 556 1035(e)U 556 963(type)U 684(of)S 758(texture)S 950(pyramid)S 1175(is)S 1239(1)S 4 F 1289(+)S 1 F 1342(1)S 4 F (/)R 1 F (4)R 4 F 1439(+)S 1 F 1492(1)S 4 F (/)R 1 F (16)R 4 F 1619(+)S 2 F 1672 945(...)U 4 F 1737 963(=)U 1 F 1790(4)S 4 F (/)R 1 F (3)R 1891(times)S 2046(that)S 2161(required)S 2385(for)S 2478(an)S 2558(un\256ltered)S 2812(texture.)S 3038(Oth)S 583 1035(rs)U 650(have)S 788(used)S 922(four)S 1046(dimensional)S 1365(image)S 1537(pyramids)S 1785(which)S 1956(pre\256lter)S 2171(differentia)S 2423(lly)S 2511(in)S 2 F 2581(u)S 1 F 2644(and)S 2 F 2754(v)S 1 F 2814(to)S 2884(resolutions)S 556 1107(of)U 626(the)S 720(form)S 857(2)S 4 F 944(\264)S 1 F (2)R 1062(.)S 4 F 42 Z 887 1083(D)U 2 F (u)R 4 F 1007(D)S 2 F (v)R 60 Z 1172 1251(3)U 1 F 556 1344(H)U 2 F 556 1251(pyramid)U 776(\261)S 826(Heckbert,)S 1082(198)S 1 F 599 1344(eckbert)U 804(discusses)S 1054(Willia)S 1206(ms')S 1323(trilinea)S 1495(r)S 1542(interpolat)S 1774(ion)S 1878(scheme)S 2086(for)S 2183(pyramids)S 2434(\(see)S 2558(below\))S 2752(and)S 2866(its)S 2950(ef\256cient)S 556 1488(a)U 556 1416(use)U 661(in)S 733(perspective)S 1033(texture)S 1226(mapping)S 1462(of)S 1537(polygons)S 1782([Hec83].)S 2039(Choosing)S 2294(the)S 2393(pyramid)S 2619(level)S 2761(is)S 2825(equivalent)S 3101(to)S 583 1488(pproximating)U 931(a)S 981(texture)S 1172(quadrilate)S 1414(ral)S 1501(with)S 1631(a)S 1681(square,)S 1876(as)S 1949(shown)S 2128(in)S 2198(\256gure)S 2361(4a.)S 2476(The)S 2593(recommende)S 2905(d)S 2957(formula)S 556 1632(r)U 556 1560(for)U 655(the)S 758(diamete)S 950(r)S 2 F 999(d)S 1 F 1068(of)S 1147(the)S 1250(square)S 1436(is)S 1505(the)S 1608(maximum)S 1882(of)S 1961(the)S 2064(side)S 2190(lengths)S 2393(of)S 2472(the)S 2575(quadrilate)S 2817(ral.)S 2944(Aliasing)S 576 1632(esults)U 736(if)S 796(the)S 893(area)S 1017(\256ltered)S 1211(is)S 1274(too)S 1374(small,)S 1543(and)S 1653(blurring)S 1870(results)S 2050(if)S 2110(it's)S 2209(too)S 2308(big;)S 2424(one)S 2533(or)S 2605(the)S 2701(other)S 2847(is)S 2909(inevitabl)S 3121(e)S 2 F 556 1848(p)U 1 F 556 1704(\(it)U 630(is)S 690(customary)S 961(to)S 1028(err)S 1115(on)S 1195(the)S 1289(blurry,)S 1471(conservative)S 1796(side\).)S 2 F 586 1848(yramid)U 776(\261)S 826(Williams,)S 1075(1983)S 1 F 556 1941(W)U (illia)R 708(ms)S 809(improves)S 1064(upon)S 1215(Dungan's)S 1479(point)S 1634(sampling)S 1886(by)S 1977(proposing)S 2248(a)S 2306(trilinea)S 2478(r)S 2528(interpolat)S 2760(ion)S 2867(scheme)S 3078(for)S 3128 2013(r)U 556 2085(i)U 556 2013(pyramidal)U 827(images)S 1024(wherein)S 1244(bilinear)S 1455(interpolat)S 1687(ion)S 1790(is)S 1856(performed)S 2132(on)S 2217(two)S 2332(levels)S 2498(of)S 2573(the)S 2672(pyramid)S 2898(and)S 3010(linea)S 573 2085(nterpolati)U 805(on)S 886(is)S 947(performed)S 1219(between)S 1441(them)S 1583([Wil83].)S 1830(The)S 1945(output)S 2120(of)S 2191(this)S 2299(\256lter)S 2434(is)S 2495(thus)S 2616(a)S 2663(continuous)S 2947(function)S 3128 2157(r)U 556 2229(s)U 556 2157(of)U 627(position)S 842(\()S 2 F (u)R 1 F 902(,)S 2 F (v)R 1 F 954(\))S 995(and)S 1103(diamete)S 1295(r)S 2 F 1336(d)S 1 F 1376(.)S 1432(His)S 1536(\256lter)S 1671(has)S 1772(a)S 1820(constant)S 2042(cost)S 2160(of)S 2231(8)S 2282(pixel)S 2424(accesses)S 2649(and)S 2757(7)S 2808(multiplie)S 3027(s)S 3071(pe)S 579 2229(creen)U 732(pixel.)S 910(Willia)S 1062(ms)S 1154(uses)S 1279(a)S 1327(box)S 1438(\256lter)S 1573(to)S 1641(construct)S 1883(the)S 1978(image)S 2147(pyramid,)S 2384(but)S 2482(gaussian)S 2710(\256lters)S 2868(can)S 2973(also)S 3091(be)S 2 F 556 2445(E)U 1 F 556 2301(used)U 686([Bur81].)S 931(He)S 1021(also)S 1138(proposes)S 1371(a)S 1418(particula)S 1630(r)S 1670(layout)S 1841(for)S 1931(color)S 2075(image)S 2243(pyramids)S 2487(called)S 2652(the)S 2746(``mipmap''.)S 2 F 593 2445(WA)U 700(on)S 780(pyramid)S 1000(\261)S 1050(Greene)S 1247(and)S 1357(Heckbert,)S 1613(1986)S 1 F 556 2538(A)U (ttempting)R 861(to)S 938(decouple)S 1186(the)S 1290(data)S 1421(structure)S 1662(from)S 1809(the)S 1913(access)S 2097(function,)S 2343(Greene)S 2547(suggests)S 2780(the)S 2884(use)S 2994(of)S 3074(the)S 3128 2610(r)U 556 2682(i)U 556 2610(EWA)U 721(\256lter)S 863(on)S 950(an)S 1034(image)S 1209(pyramid)S 1437([Gre86b].)S 1719(Unlike)S 1910(the)S 2011(other)S 2162(pre\256ltering)S 2457(techniques)S 2742(such)S 2879(as)S 2956(trilinea)S 573 2682(nterpolati)U 805(on)S 893(on)S 981(a)S 1036(pyramid)S 1265(or)S 1343(the)S 1445(summed)S 1677(area)S 1806(table,)S 1967(EWA)S 2131(allows)S 2315(arbitraril)S 2527(y)S 2584(oriented)S 2809(ellipses)S 3017(to)S 3091(be)S 2 F 556 2898(s)U 1 F 556 2754(\256ltered,)U 762(yielding)S 980(higher)S 1154(quality.)S 2 F 579 2898(ummed)U 772(area)S 902(table)S 1043(\261)S 1093(Crow,)S 1261(1984;)S 1421(Ferrari)S 1621(and)S 1731(Sklansky,)S 1977(1984)S 1 F 3133 2991(,)U 556 3063(w)U 556 2991(Crow)U 721(proposes)S 966(the)S 2 F 1071(summed)S 1298(area)S 1439(table)S 1 F (,)R 1606(an)S 1694(alternat)S 1876(ive)S 1981(to)S 2059(the)S 2164(pyramidal)S 2440(\256ltering)S 2662(of)S 2743(earlier)S 2929(methods)S 599 3063(hich)U 725(allows)S 904(orthogonally)S 1234(oriented)S 1454(rectangula)S 1706(r)S 1748(areas)S 1894(to)S 1963(be)S 2042(\256ltered)S 2234(in)S 2302(constant)S 2524(time)S 2653([Cro84].)S 2899(The)S 3014(origi-)S 3133 3135(.)U 556 3207(T)U 556 3135(nal)U 651(texture)S 840(is)S 901(pre-integrat)S 1183(ed)S 1261(in)S 1329(the)S 2 F 1424(u)S 1 F 1485(and)S 2 F 1593(v)S 1 F 1651(directions)S 1910(and)S 2018(stored)S 2186(in)S 2254(a)S 2302(high-precision)S 2670(summed)S 2894(area)S 3015(table)S 593 3207(o)U 644(\256lter)S 779(a)S 827(rectangula)S 1079(r)S 1120(area)S 1242(the)S 1337(table)S 1476(is)S 1537(sampled)S 1759(in)S 1827(four)S 1948(places)S 2119(\(much)S 2293(as)S 2363(one)S 2470(evaluate)S 2672(s)S 2715(a)S 2762(de\256nite)S 2963(integral)S 556 3351(i)U 556 3279(by)U 640(sampling)S 884(an)S 964(inde\256nite)S 1215(integral\).)S 1478(To)S 1568(do)S 1651(this)S 1761(without)S 1968(artifact)S 2140(s)S 2186(requires)S 2403(16)S 2486(accesses)S 2713(and)S 2823(14)S 2906(multiplie)S 3125(s)S 573 3351(n)U 628(general,)S 845(but)S 946(an)S 1027(optimiza)S 1239(tion)S 1357(for)S 1451(large)S 1596(areas)S 1744(cuts)S 1865(the)S 1963(cost)S 2084(to)S 2155(4)S 2209(accesses)S 2437(and)S 2548(2)S 2602(multiplie)S 2821(s.)S 2903(The)S 3021(high-)S 556 3516(T)U 556 3423(precision)U 797(table)S 935(requires)S 1149(2)S 1199(to)S 1266(4)S 1316(times)S 1467(the)S 1561(memory)S 1782(cost)S 1899(of)S 1969(the)S 2063(original)S 2271(image.)S 593 3516(he)U 678(method)S 887(was)S 1008(developed)S 1284(independentl)S 1596(y)S 1654(by)S 1742(Ferrari)S 1934(and)S 2049(Sklansky,)S 2312(who)S 2443(show)S 2596(how)S 2726(convolution)S 3041(with)S 556 3681(T)U 556 3588(arbitrary)U 784(rectili)S 926(near)S 1050(polygons)S 1290(can)S 1394(easily)S 1555(be)S 1632(performed)S 1903(using)S 2053(a)S 2100(summed)S 2324(area)S 2445(table)S 2583([Fer84],)S 2798([Fer85].)S 593 3681(he)U 671(summed)S 896(area)S 1018(table)S 1157(is)S 1218(generally)S 1464(more)S 1609(costly)S 1774(than)S 1899(the)S 1994(texture)S 2183(pyramid)S 2405(in)S 2473(both)S 2600(memory)S 2821(and)S 2928(time,)S 3071(but)S 556 3825(s)U 556 3753(it)U 619(can)S 732(perform)S 955(better)S 1122(\256ltering)S 1342(than)S 1475(the)S 1578(pyramid)S 1808(since)S 1961(it)S 2023(\256lters)S 2188(rectangula)S 2440(r)S 2488(areas,)S 2655(not)S 2760(just)S 2875(squares,)S 3098(as)S 579 3825(hown)U 733(in)S 801(\256gure)S 962(4b.)S 1078(Glassner)S 1308(has)S 1408(shown)S 1584(how)S 1707(the)S 1801(rectangle)S 2043(can)S 2147(be)S 2224(successively)S 2545(re\256ned)S 2732(to)S 2799(approximate)S 3121(a)S 3128 3897(f)U 556 3969(h)U 556 3897(quadrilate)U 798(ral)S 884([Gla86].)S 1128(As)S 1216(an)S 1295(optimiza)S 1507(tion)S 1622(he)S 1700(also)S 1818(suggests)S 2042(that)S 2154(this)S 2262(re\256nement)S 2541(be)S 2619(done)S 2757(only)S 2885(in)S 2953(areas)S 3098(o)S 586 3969(igh)U 690(local)S 835(texture)S 1030(variance)S 1235(.)S 1297(To)S 1391(compute)S 1626(variance)S 1857(over)S 1990(a)S 2043(rectangle)S 2291(he)S 2374(pre-computes)S 2728(variance)S 2933(s)S 2982(of)S 3058(3x3)S 3128 4041(-)U 556 4113(a)U 556 4041(areas)U 704(and)S 815(forms)S 979(a)S 1029(summed)S 1256(area)S 1380(table)S 1521(of)S 1594(them.)S 1773(A)S 1839(more)S 1986(accurat)S 2161(e)S 2211(method)S 2415(for)S 2508(computing)S 2789(rectangle)S 3034(vari)S 583 4113(nce)U 689(would)S 861(be)S 940(to)S 1009(pre-compute)S 1336(summed)S 1562(area)S 1685(tables)S 1848(of)S 1920(the)S 2016(texture)S 2206(values)S 2382(and)S 2491(their)S 2624(squares.)S 2860(Using)S 3024(these)S 556 4185(two)U 670(tables)S 835(variance)S 1064(can)S 1172(be)S 1253(computed)S 1515(as)S 4 F 1588(s)S 1646(=S)S 2 F (x)R 4 F 1776(/)S 2 F (n)R 4 F 1833(-)S 1 F (\()R 4 F (S)R 2 F (x)R 4 F 1970(/)S 2 F (n)R 1 F 2027(\))S 2068(.)S 2126(Of)S 2212(course)S 2392(there)S 2536(is)S 2599(considerable)S 2927(overhead)S 42 Z 1625 4161(2)U 2 F 1741 4197(i)U 1 F 1755 4161(2)U 2 F 1948 4197(i)U 1 F 2047 4161(2)U 60 Z 16 4710(-)U 556 4257(in)U 623(time)S 751(and)S 858(memory)S 1079(to)S 1146(access)S 1320(a)S 1367(variance)S 1592(table.)S 36 4710(-)U 3259(--)S EP %%Page: ? 10 BP 1 F 60 Z 1782 246(-)U 1822(10)S 1902(-)S 2 F 2564 438(6)U 1 F 556 531(T)U 2 F 556 438(repeated)U 787(integration)S 1075(\256ltering)S 1286(\261)S 1336(Perlin,)S 1522(1985;)S 1682(Heckbert,)S 1938(1986;)S 2098(Ferrari)S 2298(et.)S 2377(al.,)S 2474(198)S 1 F 593 531(his)U 691(elegant)S 894(generaliz)S 1116(ation)S 1265(of)S 1343(the)S 1445(summed)S 1677(area)S 1806(table)S 1952(was)S 2072(developed)S 2347(independentl)S 2659(y)S 2716(by)S 2803(Perlin)S 2974(and)S 3088(by)S 3128 603(-)U 556 675(n)U 556 603(Ferrari)U 741(et.)S 821(al.)S 901([Per85b],)S 1147([Hec86],)S 1380([Fer86].)S 1616(If)S 1677(an)S 1755(image)S 1924(is)S 1985(pre-integrat)S 2267(ed)S 2345(in)S 2 F 2413(u)S 1 F 2474(and)S 2 F 2581(v)S 2638(n)S 1 F 2698(times,)S 2864(an)S 2941(orthogo)S 586 675(ally)U 700(oriented)S 921(ellipti)S 1063(cal)S 1157(area)S 1281(can)S 1388(be)S 1468(\256ltered)S 1662(by)S 1745(sampling)S 1989(the)S 2086(array)S 2233(at)S 2300(\()S 2 F (n)R 4 F 2360(+)S 1 F (1\))R 2486(points)S 2655(and)S 2764(weighting)S 3027(them)S 42 Z 2443 651(2)U 60 Z 3121 747(e)U 556 819(s)U 556 747(appropriatel)U 848(y.)S 935(The)S 1051(effective)S 1285(\256lter)S 1421(is)S 1483(a)S 1532(box)S 1644(convolved)S 1917(with)S 2046(itself)S 2 F 2189(n)S 1 F 2251(times)S 2404(\(an)S 2 F 2503(n)S 1 F 2543(th)S 2612(order)S 2760(b-spline\))S 2995(whos)S 579 819(ize)U 671(can)S 776(be)S 854(selecte)S 1019(d)S 1070(at)S 1135(each)S 1267(screen)S 1442(pixel.)S 1619(If)S 2 F 1680(n)S 4 F 1720(=)S 1 F (0)R 1804(the)S 1899(method)S 2101(degenerat)S 2336(es)S 2407(to)S 2474(point)S 2618(sampling,)S 2874(if)S 2 F 2931(n)S 4 F 2971(=)S 1 F (1)R 3054(it)S 3108(is)S 3128 891(-)U 556 963(a)U 556 891(equivalent)U 829(to)S 897(the)S 992(summed)S 1217(area)S 1339(table)S 1478(with)S 1606(its)S 1684(box)S 1795(\256lter,)S 2 F 1945(n)S 4 F 1985(=)S 1 F (2)R 2069(uses)S 2193(a)S 2241(triangular)S 2497(\256lter,)S 2647(and)S 2 F 2755(n)S 4 F 2795(=)S 1 F (3)R 2879(uses)S 3003(a)S 3051(par)S 583 963(bolic)U 731(\256lter.)S 907(As)S 2 F 1000(n)S 1 F 1067(increases,)S 1330(the)S 1431(\256lter)S 1572(shape)S 1736(approaches)S 2034(a)S 2088(gaussian,)S 2337(and)S 2451(the)S 2552(memory)S 2780(and)S 2894(time)S 3028(costs)S 556 1107(m)U 556 1035(increase.)U 818(The)S 941(method)S 1150(can)S 1262(be)S 1347(generaliz)S 1569(ed)S 1654(to)S 1729(arbitrary)S 1965(spline)S 2137(\256lters)S 2302([Hec86].)S 2562(One)S 2690(dif\256culty)S 2939(with)S 3074(the)S 603 1107(ethod)U 757(is)S 817(that)S 928(high)S 1055(precision)S 1296(arithmet)S 1498(ic)S 1562(\(more)S 1726(than)S 1850(32)S 1930(bits\))S 2057(is)S 2117(required)S 2338(for)S 2 F 2428(n)S 4 F 2468(\263)S 1 F (2.)R 556 1344(T)U 2 F 556 1251(Comparison)U 872(of)S 939(Pre\256ltering)S 1237(Methods)S 1 F 593 1344(he)U 670(following)S 924(table)S 1062(summarizes)S 1370(the)S 1464(pre\256ltering)S 1752(methods)S 1976(we)S 2066(have)S 2200(discussed:)S 6 F 3018 1392(i)U 655(i)S 678(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)S 1 F 889 1464(REFERENCE)U 1527(FILTER)S 1837(SHAPE)S 2133(DOF)S 2427(TIME)S 2749(MEMORY)S 6 F 3018 1476(i)U 655(i)S 678(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)S 1 F 878 1548(point)U 1022(sampling)S 1533(impulse)S 1870(point)S 2177(2)S 2463(1,0)S 2841(1)S 2916 1620(3)U 726 1692(t)U 778 1620(point)U 922(sampled)S 1143(pyramid)S 1584(box)S 1853(square)S 2177(3)S 2463(1,0)S 2841(1.3)S 743 1692(rilinear)U 938(interp.)S 1114(on)S 1194(pyramid)S 1584(box)S 1853(square)S 2177(3)S 2463(8,7)S 2841(1.33)S 685 1764(4-D)U 798(pyramid)S 1019(\(scaling)S 1230(u)S 1280(and)S 1387(v\))S 1584(box)S 1821(rectangle)S 2177(4)S 2433(16,15)S 2841(4)S 842 1836(EWA)U 999(on)S 1079(pyramid)S 1585(any)S 1853(ellipse)S 2177(5)S 2371(unlimite)S 2573(d?)S 2841(1.33)S 6 F 3018 1848(i)U 655(i)S 678(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)S 1 F 829 1920(summed)U 1053(area)S 1174(table)S 1584(box)S 1821(rectangle)S 2177(4)S 2342(16,14;)S 2514(or)S 2584(4,2)S 2821(2-4)S 2871 1992(6)U 6 F 655 2004(i)U 1 F 699 1992(repeate)U 874(d)S 924(integrati)S 1126(on)S 1206(\(order)S 1373(2\))S 1536(triangle)S 1821(rectangle)S 2177(4)S 2342(36,31;)S 2514(or)S 2584(9,4)S 2821(2-)S 6 F 678 2004(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)U 655 2088(i)U 1 F 838 2076(direct)U 996(convolution)S 1585(any)S 1888(any)S 2161(5+)S 2384(unlimite)S 2586(d)S 2841(1)S 6 F 678 2088(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)U 655(c)S 2052(c)T 1992(c)T 1932(c)T 1872(c)T 1812(c)T 1752(c)T 1692(c)T 1632(c)T 1572(c)T 1512(c)T 1452(c)T 1482 2088(c)U 2052(c)T 1992(c)T 1932(c)T 1872(c)T 1812(c)T 1752(c)T 1692(c)T 1632(c)T 1572(c)T 1512(c)T 1452(c)T 1776 2088(c)U 2052(c)T 1992(c)T 1932(c)T 1872(c)T 1812(c)T 1752(c)T 1692(c)T 1632(c)T 1572(c)T 1512(c)T 1452(c)T 2088 2088(c)U 2052(c)T 1992(c)T 1932(c)T 1872(c)T 1812(c)T 1752(c)T 1692(c)T 1632(c)T 1572(c)T 1512(c)T 1452(c)T 2297 2088(c)U 2052(c)T 1992(c)T 1932(c)T 1872(c)T 1812(c)T 1752(c)T 1692(c)T 1632(c)T 1572(c)T 1512(c)T 1452(c)T 2704 2088(c)U 2052(c)T 1992(c)T 1932(c)T 1872(c)T 1812(c)T 1752(c)T 1692(c)T 1632(c)T 1572(c)T 1512(c)T 1452(c)T 3048 2088(c)U 2052(c)T 1992(c)T 1932(c)T 1872(c)T 1812(c)T 1752(c)T 1692(c)T 1632(c)T 1572(c)T 1512(c)T 1452(c)T 1 F 3101 2196(m)U 556 2268(f)U 556 2196(The)U 673(high)S 803(quality)S 994(direct)S 1155(convolution)S 1466(methods)S 1693(of)S 1766(Feibush)S 1978(and)S 2087(Gangnet)S 2313(have)S 2449(been)S 2585(included)S 2815(at)S 2881(the)S 2977(botto)S 576 2268(or)U 655(comparison.)S 1000(In)S 1079(this)S 1195(table,)S 1357(FILTER)S 1590(means)S 1773(cross)S 1925(section,)S 2140(while)S 2303(SHAPE)S 2521(is)S 2590(2-D)S 2712(\256lter)S 2854(shape.)S 3054(The)S 3128 2340(r)U 556 2412(q)U 556 2340(number)U 764(of)S 838(degrees)S 1046(of)S 1120(freedom)S 1345(\(DOF\))S 1528(of)S 1602(the)S 1700(2-D)S 1817(\256lter)S 1955(shape)S 2116(provides)S 2347(an)S 2428(approximate)S 2754(ranking)S 2961(of)S 3034(\256lte)S 586 2412(uality;)U 764(the)S 861(more)S 1008(degrees)S 1215(of)S 1288(freedom)S 1512(are)S 1609(availabl)S 1801(e)S 1851(the)S 1948(greater)S 2139(is)S 2202(the)S 2299(\256lter)S 2436(shape)S 2596(control.)S 2825(The)S 2941(numbers)S 3133 2484(.)U 556 2556(M)U 556 2484(under)U 720(TIME)S 894(are)S 995(the)S 1096(number)S 1307(of)S 1384(texture)S 1579(pixel)S 1727(accesses)S 1958(and)S 2072(the)S 2173(number)S 2384(of)S 2461(multiplie)S 2680(s)S 2729(per)S 2832(screen)S 3012(pixel)S 609 2556(EMORY)U 845(is)S 905(the)S 999(ratio)S 1130(of)S 1200(memory)S 1421(required)S 1642(relative)S 1844(to)S 1911(an)S 1988(un\256ltered)S 2239(texture.)S 3121 2649(e)U 556 2721(t)U 556 2649(We)U 663(see)S 763(that)S 877(the)S 974(integrate)S 1186(d)S 1239(array)S 1386(techniques)S 1667(of)S 1740(Crow)S 1896(and)S 2006(Perlin)S 2173(have)S 2309(rather)S 2472(high)S 2601(memory)S 2824(costs)S 2966(relativ)S 573 2721(o)U 631(the)S 733(pyramid)S 962(methods,)S 1209(but)S 1314(allow)S 1476(rectangula)S 1728(r)S 1776(or)S 1853(orthogonally)S 2188(oriented)S 2413(ellipti)S 2555(cal)S 2653(areas)S 2804(to)S 2878(be)S 2962(\256ltered.)S 556 2886(S)U 556 2793(Traditiona)U 808(lly)S 892(pyramid)S 1113(techniques)S 1391(have)S 1525(lower)S 1682(memory)S 1903(cost)S 2020(but)S 2117(allow)S 2271(only)S 2398(squares)S 2598(to)S 2665(be)S 2742(\256ltered.)S 589 2886(ince)U 712(pre\256ltering)S 1002(usually)S 1198(entails)S 1378(a)S 1427(setup)S 1576(expense)S 1792(proportional)S 2112(to)S 2181(the)S 2277(square)S 2456(of)S 2528(the)S 2624(texture)S 2814(resolution,)S 3091(its)S 3125 2958(s)U 556 3030(u)U 556 2958(cost)U 675(is)S 737(proportional)S 1056(to)S 1124(that)S 1236(of)S 1307(direct)S 1466(convolution)S 1775(\261)S 1826(if)S 1884(the)S 1979(texture)S 2168(is)S 2229(only)S 2357(used)S 2488(once.)S 2658(But)S 2766(if)S 2824(the)S 2919(texture)S 3108(i)S 586 3030(sed)U 690(many)S 848(times,)S 1018(as)S 1092(part)S 1210(of)S 1284(a)S 1335(periodic)S 1557(pattern,)S 1764(or)S 1838(appearing)S 2100(on)S 2184(several)S 2379(objects)S 2574(or)S 2647(in)S 2717(several)S 2911(frames)S 3098(of)S 556 3195(F)U 556 3102(animati)U 738(on,)S 833(the)S 927(setup)S 1074(cost)S 1191(can)S 1295(be)S 1372(amortize)S 1584(d)S 1634(over)S 1761(each)S 1892(use.)S 589 3195(igure)U 737(5)S 791(illustrate)S 1003(s)S 1050(several)S 1245(of)S 1319(these)S 1467(texture)S 1659(\256lters)S 1820(on)S 1904(a)S 1955(checkerboa)S 2230(rd)S 2304(in)S 2374(perspective)S 2649(,)S 2687(which)S 2857(is)S 2920(an)S 3000(excel-)S 3128 3267(-)U 556 3339(p)U 556 3267(lent)U 669(test)S 775(of)S 847(a)S 896(texture)S 1086(\256lter,)S 1237(since)S 1383(it)S 1439(has)S 1541(a)S 1589(range)S 1744(of)S 1815(frequencie)S 2070(s)S 2114(at)S 2179(high)S 2307(contrast.)S 2554(Note)S 2692(that)S 2804(trilinea)S 2976(r)S 3017(inter)S 586 3339(olation)U 789(on)S 884(a)S 945(pyramid)S 1180(blurs)S 1334(excessively)S 1646(parallel)S 1862(to)S 1943(the)S 2051(horizon)S 2269(but)S 2380(that)S 2505(integrate)S 2717(d)S 2781(arrays)S 2962(do)S 3056(not.)S 556 3483(t)U 556 3411(Second)U 757(order)S 908(repeate)S 1083(d)S 1137(integrati)S 1339(on)S 1423(does)S 1557(just)S 1668(as)S 1742(well)S 1870(as)S 1944(EWA)S 2105(for)S 2199(vertical)S 2381(ly)S 2452(oriented)S 2673(texture)S 2864(ellipses)S 3068(\(on)S 573 3483(he)U 667(left)S 785(of)S 872(the)S 983(images\),)S 1226(but)S 1340(there)S 1498(is)S 1574(a)S 1637(striking)S 1857(difference)S 2138(between)S 2375(gaussian)S 2618(EWA)S 2791(and)S 2914(the)S 3024(other)S 3 F 556 3699(F)U 1 F 556 3555(pre\256ltering)U 844(methods)S 1068(for)S 1158(ellipses)S 1359(at)S 1423(45)S 1503(degrees)S 1707(\(on)S 1807(the)S 1901(right)S 2035(of)S 2105(the)S 2199(images\).)S 3 F 593 3699(ourier)U 774(Series)S 1 F 556 3792(A)U (n)R 650(alternat)S 832(ive)S 927(to)S 995(texture)S 1184(space)S 1338(\256ltering)S 1549(is)S 1609(to)S 1676(transform)S 1930(the)S 2024(texture)S 2212(to)S 2279(frequency)S 2540(space)S 2694(and)S 2801(low)S 2911(pass)S 3034(\256lter)S 556 3936(t)U 556 3864(its)U 636(spectrum.)S 915(This)S 1045(is)S 1108(most)S 1248(convenient)S 1536(when)S 1689(the)S 1786(texture)S 1977(is)S 2040(represented)S 2341(by)S 2424(a)S 2474(Fourier)S 2673(series)S 2832(rather)S 2995(than)S 3121(a)S 573 3936(exture)U 746(array.)S 927(Norton,)S 1134(Rockwood,)S 1430(and)S 1538(Skolmoski)S 1816(explore)S 2018(this)S 2126(approach)S 2368(for)S 2459(\257ight)S 2607(simulator)S 2856(applicat)S 3048(ions)S 556 4080(F)U 556 4008(and)U 674(propose)S 895(a)S 953(simple)S 1144(technique)S 1409(for)S 1509(clamping)S 1764(high)S 1901(frequency)S 2172(terms)S 2336([Nor82].)S 2594(Gardner)S 2821(employs)S 3055(3-D)S 589 4080(ourier)U 758(series)S 920(as)S 995(a)S 1047(transparency)S 1380(texture)S 1573(function,)S 1814(with)S 1946(which)S 2118(he)S 2199(generate)S 2404(s)S 2451(surprisingly)S 2762(convincing)S 3054(pic-)S 556 4245(P)U 556 4152(tures)U 693(of)S 763(trees)S 897(and)S 1004(clouds)S 1181([Gar85].)S 589 4245(erlin's)U 787(``Image)S 1022(Synthesizer'')S 1387(uses)S 1534(band)S 1695(limite)S 1837(d)S 1911(pseudo-random)S 2329(functions)S 2597(as)S 2691(texture)S 2903(primitive)S 3125(s)S 16 4710(-)U 556 4317([Per85a].)U 824(Creating)S 1058(textures)S 1275(in)S 1348(this)S 1461(way)S 1587(eases)S 1740(transitions)S 2017(from)S 2159(macroscopic)S 2489(to)S 2561(microscopic)S 2881(views)S 3046(of)S 3121(a)S 36 4710(-)U 3259(--)S EP %%Page: ? 11 BP 1 F 60 Z 556 438(s)U 1782 246(-)U 1822(11)S 1902(-)S 579 438(urface;)U 769(in)S 838(the)S 934(macroscopic)S 1261(range)S 1417(the)S 1513(surface)S 1709(charact)S 1884(eristics)S 2077(are)S 2173(built)S 2306(into)S 2422(the)S 2518(scattering)S 2774(statistics)S 3003(of)S 3074(the)S 3128 510(-)U 556 582(c)U 556 510(illumina)U 758(tion)S 873(model,)S 1059(in)S 1126(the)S 1220(intermedi)S 1452(ate)S 1543(range)S 1697(they)S 1821(are)S 1915(modeled)S 2143(using)S 2293(bump)S 2450(mapping,)S 2696(and)S 2803(in)S 2870(the)S 2964(micros)S 583 582(opic)U 709(range)S 865(the)S 961(surface)S 1156(is)S 1217(explicit)S 1420(geometry)S 1669([Per84],)S 1885([Kaj85].)S 2128(Each)S 2270(term)S 2402(in)S 2470(the)S 2565(texture)S 2754(series)S 2912(can)S 3017(make)S 3 F 556 798(F)U 1 F 556 654(the)U 650(transition)S 898(independentl)S 1210(y)S 1260(at)S 1324(a)S 1371(scale)S 1512(appropriate)S 1807(to)S 1874(its)S 1951(frequency)S 2212(range.)S 3 F 593 798(iltering)U 801(Recommendations)S 1 F 556 891(T)U (he)R 673(best)S 793(\256ltering)S 1007(algorithm)S 1265(for)S 1358(a)S 1408(given)S 1565(task)S 1685(depends)S 1905(on)S 1988(the)S 2085(texture)S 2276(representat)S 2541(ion)S 2641(in)S 2711(use.)S 2848(When)S 3014(\256lter-)S 556 1035(e)U 556 963(ing)U 656(a)S 706(texture)S 897(array,)S 1058(the)S 1154(minimal)S 1378(texture)S 1568(\256lter)S 1704(should)S 1886(be)S 1965(trilinea)S 2137(r)S 2179(interpolat)S 2411(ion)S 2510(on)S 2592(a)S 2641(pyramid.)S 2899(This)S 3028(blurs)S 583 1035(xcessively,)U 874(but)S 976(it)S 1035(elimina)S 1217(tes)S 1309(most)S 1451(aliasing)S 1664(and)S 1776(costs)S 1921(little)S 2058(more)S 2207(than)S 2336(point)S 2485(sampling.)S 2766(Next)S 2908(in)S 2980(quality)S 3118 1107(d)U 556 1179(v)U 556 1107(and)U 667(cost)S 788(are)S 886(integrate)S 1098(d)S 1152(arrays)S 1323(of)S 1397(order)S 1548(1)S 1602(\(box)S 1736(\256lter\))S 1893(or)S 1966(order)S 2116(2)S 2169(\(triangle)S 2397(\256lter\).)S 2589(These)S 2756(allow)S 2913(elongate)S 586 1179(ertical)U 765(or)S 842(horizontal)S 1114(areas)S 1265(to)S 1339(be)S 1423(\256ltered)S 1620(much)S 1780(more)S 1930(accurat)S 2105(ely)S 2205(\(resulting)S 2462(in)S 2535(less)S 2651(blurring)S 2871(at)S 2941(horizons)S 3131 1251(t)U 556 1323(4)U 556 1251(and)U 664(silhouettes\))S 963(but)S 1061(blur)S 1179(is)S 1240(still)S 1352(excessive)S 1604(for)S 1695(elongated)S 1951(areas)S 2096(at)S 2161(an)S 2239(angle)S 2390(\(such)S 2540(as)S 2610(an)S 2687(eccent)S 2842(ric)S 2926(ellipse)S 3104(a)S 586 1323(5)U 637(degrees\).)S 897(For)S 1001(near-perfec)S 1276(t)S 1314(quality)S 1503(at)S 1568(a)S 1616(cost)S 1734(far)S 1822(below)S 1990(that)S 2102(of)S 2173(direct)S 2332(convolution,)S 2656(the)S 2751(EWA)S 2909(or)S 2980(similar)S 3131 1395(t)U 556 1467(i)U 556 1395(\256lter)U 692(on)S 774(a)S 823(pyramid)S 1046(is)S 1108(recommende)S 1420(d.)S 1507(Its)S 1589(cost)S 1708(is)S 1770(not)S 1869(strictly)S 2059(bounded)S 2288(like)S 2401(most)S 2540(pre\256ltering)S 2830(methods,)S 3071(bu)S 573 1467(s)U 626(proportional)S 954(to)S 1031(ellipse)S 1219(eccent)S 1374(ricity.)S 1567(The)S 1691(cost)S 1818(of)S 1897(direct)S 2064(convolution,)S 2396(meanwhile,)S 2705(is)S 2774(proportional)S 3101(to)S 3131 1539(l)U 556 1611(t)U 556 1539(ellipse)U 737(area.)S 896(Any)S 1022(of)S 1095(these)S 1242(methods)S 1469(could)S 1626(probably)S 1863(bene\256t)S 2050(from)S 2190(adaptive)S 2418(re\256nement)S 2699(according)S 2960(to)S 3030(loca)S 573 1611(exture)U 744(variance)S 969([Gla86].)S 556 1704(I)U (n)R 633(the)S 734(case)S 865(of)S 942(arbitrary)S 1177(texture)S 1372(functions,)S 1638(which)S 1812(can)S 1923(be)S 2007(much)S 2168(harder)S 2349(to)S 2423(integrate)S 2662(than)S 2792(texture)S 2986(arrays,)S 556 1869(F)U 556 1776(adaptive)U 781(stochastic)S 1039(sampling)S 1280(methods)S 1504(are)S 1598(called)S 1763(for)S 1853([Lee85].)S 589 1869(uture)U 735(research)S 958(on)S 1040(texture)S 1230(\256lters)S 1389(will)S 1505(continue)S 1735(to)S 1804(improve)S 2027(their)S 2160(quality)S 2350(by)S 2432(providing)S 2687(greater)S 2876(\256lter)S 3011(shape)S 3128 1941(r)U 556 2013(h)U 556 1941(control)U 750(while)S 907(retaining)S 1144(low)S 1256(time)S 1386(and)S 1495(memory)S 1718(costs.)S 1895(One)S 2017(would)S 2189(like)S 2302(to)S 2371(\256nd)S 2486(a)S 2535(constant-cost)S 2875(method)S 3078(fo)S 586 2013(igh)U 683(quality)S 871(\256ltering)S 1082(of)S 1152(arbitraril)S 1364(y)S 1414(oriented)S 1632(ellipti)S 1774(cal.)S 556 2322(S)U 3 F 556 2229(SYSTEM)U 822(SUPPORT)S 1122(FOR)S 1269(TEXTURE)S 1578(MAPPING)S 1 F 589 2322(o)U 643(far)S 734(we)S 828(have)S 966(emphasize)S 1221(d)S 1275(those)S 1426(tasks)S 1570(common)S 1805(to)S 1876(all)S 1961(types)S 2112(of)S 2186(texture)S 2378(mapping.)S 2648(We)S 2756(now)S 2883(summarize)S 3131 2394(t)U 556 2466(d)U 556 2394(some)U 711(of)S 789(the)S 891(special)S 1087(provisions)S 1365(that)S 1484(a)S 1539(modeling)S 1795(and)S 1910(rendering)S 2169(system)S 2364(must)S 2508(make)S 2666(in)S 2740(order)S 2894(to)S 2968(suppor)S 586 2466(ifferent)U 793(varietie)S 975(s)S 1027(of)S 1106(texture)S 1303(mapping.)S 1578(We)S 1691(assume)S 1897(that)S 2016(the)S 2118(rendering)S 2377(program)S 2609(is)S 2677(scanning)S 2919(in)S 2994(screen)S 556 2631(T)U 556 2538(space.)U 593 2631(he)U 681(primary)S 903(requirement)S 1195(s)S 1248(of)S 1328(standard)S 1562(texture)S 1760(mapping)S 2001(are)S 2105(texture)S 2303(space)S 2467(coordinates)S 2775(\()S 2 F (u)R 1 F 2835(,)S 2 F (v)R 1 F 2887(\))S 2937(for)S 3037(each)S 3133 2703(.)U 556 2775(I)U 556 2703(screen)U 731(pixel)S 873(plus)S 994(the)S 1089(partial)S 1265(derivative)S 1507(s)S 1550(of)S 2 F 1620(u)S 1 F 1680(and)S 2 F 1787(v)S 1 F 1844(with)S 1971(respect)S 2162(to)S 2229(screen)S 2 F 2403(x)S 1 F 2460(and)S 2 F 2567(y)S 1 F 2624(for)S 2714(good)S 2854(antiali)S 3006(asing)S 576 2775(f)U 622(the)S 722(analytic)S 940(formulas)S 1180(for)S 1276(these)S 1426(partials)S 1630(are)S 1730(not)S 1832(availabl)S 2024(e,)S 2091(they)S 2220(can)S 2329(be)S 2411(approximate)S 2713(d)S 2768(by)S 2853(differencing)S 556 2940(B)U 556 2847(the)U 2 F 650(u)S 1 F 710(and)S 2 F 817(v)S 1 F 874(of)S 944(neighboring)S 1255(pixels.)S 596 2940(ump)U 724(mapping)S 956(requires)S 1170(additional)S 1432(information)S 1737(at)S 1801(each)S 1932(pixel:)S 2090(two)S 2200(vectors)S 2394(tangent)S 2592(to)S 2659(the)S 2753(surface)S 2947(pointing)S 3133 3012(,)U 556 3084(b)U 556 3012(in)U 629(the)S 2 F 729(u)S 1 F 795(and)S 2 F 908(v)S 1 F 971(directions.)S 1270(For)S 1379(facet)S 1523(shaded)S 1716(polygons)S 1962(these)S 2111(tangents)S 2337(are)S 2436(constant)S 2662(across)S 2837(the)S 2936(polygon)S 586 3084(ut)U 662(for)S 761(Phong)S 943(shaded)S 1139(polygons)S 1388(they)S 1521(vary.)S 1692(In)S 1771(order)S 1927(to)S 2003(ensure)S 2189(artifact)S 2361(-free)S 2503(bump)S 2668(mapping)S 2907(on)S 2995(Phong)S 3125 3156(s)U 556 3228(i)U 556 3156(shaded)U 747(polygons,)S 1006(these)S 1154(tangents)S 1379(must)S 1520(be)S 1601(continuous)S 1889(across)S 2062(polygon)S 2282(seams.)S 2487(One)S 2610(way)S 2733(to)S 2803(guarantee)S 3061(thi)S 573 3228(s)U 619(to)S 689(compute)S 919(tangents)S 1142(at)S 1208(all)S 1291(polygon)S 1510(vertices)S 1720(during)S 1899(model)S 2072(preparation)S 2369(and)S 2478(interpolat)S 2710(e)S 2759(them)S 2902(across)S 3074(the)S 556 3393(P)U 556 3300(polygon.)U 808(The)S 922(normal)S 1113(vector)S 1284(can)S 1388(be)S 1465(computed)S 1723(as)S 1793(the)S 1887(cross)S 2030(product)S 2234(of)S 2304(the)S 2398(tangents.)S 589 3393(roper)U 739(antiali)S 891(asing)S 1041(of)S 1113(illumina)S 1315(tion)S 1431(mapping)S 1664(requires)S 1880(some)S 2029(measure)S 2252(of)S 2324(surface)S 2520(curvature)S 2770(in)S 2839(order)S 2988(to)S 3057(cal-)S 3131 3465(l)U 556 3537(v)U 556 3465(culate)U 723(the)S 819(solid)S 958(angle)S 1111(of)S 1183(sky)S 1288(to)S 1356(\256lter.)S 1526(This)S 1654(is)S 1715(usually)S 1910(provided)S 2145(in)S 2213(the)S 2308(form)S 2446(of)S 2517(the)S 2612(partials)S 2811(of)S 2882(the)S 2977(norma)S 586 3537(ector)U 728(with)S 856(respect)S 1048(to)S 1116(screen)S 1291(space.)S 1480(When)S 1644(direct)S 1802(rendering)S 2053(support)S 2253(for)S 2343(illumina)S 2545(tion)S 2659(mapping)S 2890(is)S 2950(unavail-)S 3128 3609(-)U 556 3681(c)U 556 3609(able,)U 696(however,)S 942(tricks)S 1100(can)S 1208(be)S 1289(employed)S 1551(that)S 1666(give)S 1793(a)S 1843(visually)S 2057(accept)S 2212(able)S 2336(approximati)S 2628(on.)S 2746(Rather)S 2930(than)S 3057(cal)S 583 3681(ulate)U 725(the)S 823(exact)S 975(ray)S 1076(direction)S 1315(at)S 1383(each)S 1518(pixel,)S 1678(one)S 1789(can)S 1896(compute)S 2127(the)S 2224(re\257ected)S 2455(or)S 2528(refracte)S 2713(d)S 2766(ray)S 2866(direction)S 3104(at)S 556 3825(u)U 556 3753(polygon)U 782(vertices)S 999(only)S 1134(and)S 1249(interpolat)S 1481(e)S 1536(it,)S 1613(in)S 1688(the)S 1790(form)S 1935(of)S 2 F 2013(u)S 1 F 2081(and)S 2 F 2196(v)S 1 F 2261(texture)S 2457(indices,)S 2671(across)S 2849(the)S 2951(polygon)S 586 3825(sing)U 706(standard)S 930(methods.)S 556 3918(A)U (lthough)R 816(texture)S 1017(maps)S 1177(are)S 1284(usually)S 1491(much)S 1658(more)S 1815(compact)S 2053(than)S 2190(brute)S 2347(force)S 2504(3-D)S 2630(modeling)S 2891(of)S 2974(surface)S 556 4062(r)U 556 3990(details,)U 752(they)S 879(can)S 986(be)S 1066(bulky,)S 1241(especial)S 1436(ly)S 1506(when)S 1659(they)S 1786(represent)S 2030(a)S 2080(high)S 2210(resolution)S 2474(image)S 2645(as)S 2718(opposed)S 2940(to)S 3009(a)S 3058(low)S 576 4062(esolution)U 819(texture)S 1009(pattern)S 1199(that)S 1312(is)S 1374(replicat)S 1556(ed)S 1635(numerous)S 1894(times.)S 2082(Keeping)S 2308(several)S 2501(of)S 2573(these)S 2719(in)S 2788(random)S 2994(access)S 556 4206(a)U 556 4134(memory)U 785(is)S 853(often)S 1005(a)S 1060(burden)S 1255(on)S 1342(the)S 1443(rendering)S 1701(program.)S 1967(This)S 2101(problem)S 2329(is)S 2396(especial)S 2591(ly)S 2665(acute)S 2820(for)S 2917(rendering)S 583 4206(lgorithms)U 843(that)S 963(generate)S 1197(the)S 1300(image)S 1477(in)S 1553(scanline)S 1779(order)S 1934(rather)S 2103(than)S 2235(object)S 2411(order,)S 2581(since)S 2733(a)S 2788(given)S 2950(scanline)S 3121 4278(e)U 16 4710(-)U 556 4278(could)U 718(access)S 900(hundreds)S 1148(of)S 1226(texture)S 1422(maps.)S 1612(Further)S 1817(work)S 1967(is)S 2034(needed)S 2232(on)S 2319(memory)S 2547(manageme)S 2809(nt)S 2883(for)S 2980(textur)S 36 4710(-)U 3259(--)S EP %%Page: ? 12 BP 3 F 60 Z 556 654(S)U 1 F 556 438(map)U 680(access.)S 1782 246(-)U 1822(12)S 1902(-)S 3 F 589 654(UMMARY)U 1 F 556 747(T)U (exture)R 769(mapping)S 1005(has)S 1110(become)S 1323(a)S 1375(widely)S 1564(used)S 1699(technique)S 1959(because)S 2175(of)S 2250(its)S 2332(generalit)S 2544(y)S 2599(and)S 2710(ef\256ciency.)S 3007(It)S 3068(has)S 556 891(h)U 556 819(even)U 707(made)S 875(its)S 969(way)S 1106(into)S 1237(everyday)S 1495(broadcast)S 1763(TV,)S 1895(thanks)S 2089(to)S 2172(new)S 2308(real-tim)S 2500(e)S 2563(video)S 2733(texture)S 2937(mapping)S 586 891(ardware)U 810(such)S 950(as)S 1029(the)S 1132(Ampex)S 2 F 1338(ADO)S 1 F 1490(and)S 1606(Quantel)S 2 F 1826(Mirage)S 1 F (.)R 2067(Rendering)S 2347(systems)S 2566(of)S 2645(the)S 2748(near)S 2881(future)S 3054(will)S 556 1035(a)U 556 963(allow)U 712(any)S 821(conceiva)S 1036(ble)S 1132(surface)S 1328(paramete)S 1550(r)S 1592(to)S 1661(be)S 1740(texture)S 1930(mapped.)S 2178(Despite)S 2384(the)S 2479(recent)S 2648(explosion)S 2903(of)S 2974(diverse)S 583 1035(pplicati)U 765(ons)S 875(for)S 972(texture)S 1166(mapping,)S 1418(a)S 1471(common)S 1708(set)S 1801(of)S 1877(fundamental)S 2205(concepts)S 2442(and)S 2555(algorithms)S 2839(is)S 2905(emerging.)S 556 1179(n)U 556 1107(We)U 667(have)S 808(surveyed)S 1052(a)S 1106(number)S 1317(of)S 1393(these)S 1543(fundamental)S 1845(s:)S 1911(alternat)S 2093(ive)S 2193(techniques)S 2477(for)S 2573(paramete)S 2795(rization,)S 3021(scan-)S 586 1179(ing,)U 701(texture)S 891(representat)S 1156(ion,)S 1270(direct)S 1430(convolution,)S 1755(and)S 1864(pre\256ltering.)S 2189(Further)S 2388(work)S 2533(is)S 2595(needed)S 2788(on)S 2870(quantifying)S 3 F 556 1467(A)U 1 F 556 1251(texture)U 744(\256lter)S 878(quality)S 1066(and)S 1173(collect)S 1335(ing)S 1432(theoretic)S 1644(al)S 1708(and)S 1815(practica)S 2007(l)S 2044(comparisons)S 2368(of)S 2438(various)S 2635(methods.)S 3 F 599 1467(CKNOWLEDGEMENTS)U 1 F 556 1560(M)U (y)R 662(introduction)S 980(to)S 1050(textures)S 1264(came)S 1415(while)S 1571(mapping)S 1804(Aspen's)S 2022(facades)S 2225(for)S 2317(Walter)S 2504(Bender's)S 2 F 2743(Quick)S 2909(and)S 3021(Dirty)S 1 F 3121 1632(e)U 556 1704(G)U 2 F 556 1632(Animation)U 846(System)S 1052(\(QADAS\))S 1 F 1321(at)S 1404(the)S 1517(Massachusetts)S 1903(Institute)S 2140(of)S 2228(Technology's)S 2597(Architecture)S 2937(Machin)S 599 1704(roup;)U 749(we)S 842(learned)S 1043(the)S 1140(hard)S 1270(way)S 1393(that)S 1507(point)S 1653(sampling)S 1896(and)S 2005(linear)S 2 F 2165(u)S 1 F 2205(,)S 2 F (v)R 1 F 2279(aren't)S 2442(good)S 2584(enough.)S 2818(I)S 2860(did)S 2959(most)S 3098(of)S 3128 1776(-)U 556 1848(i)U 556 1776(the)U 652(research)S 874(that)S 986(evolved)S 1198(into)S 1313(this)S 1421(paper)S 1576(while)S 1731(at)S 1796(New)S 1930(York)S 2074(Institute)S 2293(of)S 2364(Technology's)S 2716(Computer)S 2978(Graph)S 573 1848(cs)U 665(Lab,)S 816(where)S 1005(Pat)S 1124(Hanrahan)S 1400(and)S 1529(Mike)S 1698(Chou)S 1870(contributed)S 2187(many)S 2363(ideas)S 2529(and)S 2657(Ned)S 2798(Greene,)S 3028(Jules)S 3131 1920(t)U 556 1992(P)U 556 1920(Bloomenthal)U 868(,)S 909(and)S 1022(Lance)S 1196(Willia)S 1348(ms)S 1444(supplied)S 1674(the)S 1774(cheeseburger)S 2118(incentive)S 2340(s.)S 2424(Thanks)S 2627(also)S 2750(to)S 2823(Rob)S 2949(Cook)S 3104(a)S 589 1992(ixar)U 703(for)S 793(his)S 883(encouragem)S 1178(ent,)S 1287(and)S 1394(to)S 1461(all)S 1542(the)S 1636(good)S 1776(folks)S 1916(at)S 1980(Paci\256c)S 2164(Data)S 2298(Images.)S 556 2301(R)U 3 F 556 2208(REFERENCES)U 1 F 596 2301(ecommende)U 888(d)S 945(reading:)S 1170(Rogers')S 1387(book)S 1534([Rog85])S 1761(is)S 1828(an)S 1912(excelle)S 2084(nt)S 2158(introduction)S 2480(to)S 2554(image)S 2729(synthesis.)S 3011(For)S 3121(a)S 3121 2373(a)U 556 2445(h)U 556 2373(good)U 705(introduction)S 1029(to)S 1105(texture)S 1302(mapping)S 1542(see)S 1648(Blinn)S 1810(and)S 1925(Newell's)S 2170(paper)S 2332([Bli76].)S 2569(Smith)S 2741([Smi83])S 2966(gives)S 586 2445(elpful)U 756(theoretic)S 968(al/intui)S 1140(tive)S 1260(introduction)S 1584(to)S 1660(digital)S 1844(image)S 2020(\256ltering,)S 2254(and)S 2369(Feibush)S 2587(et.)S 2674(al.)S 2761([Fei80])S 2966(go)S 3054(into)S 3131 2517(t)U 556 2589(r)U 556 2517(texture)U 751(\256ltering)S 969(in)S 1043(detail.)S 1240(Two)S 1377(pass)S 1507(methods)S 1738(are)S 1839(described)S 2096(by)S 2182(Catmull)S 2403(and)S 2516(Smith)S 2686([Cat80].)S 2931(The)S 3051(bes)S 576 2589(eference)U 781(s)S 831(on)S 918(bump)S 1082(mapping)S 1320(and)S 1434(illumina)S 1636(tion)S 1757(mapping)S 1995(are)S 2095(by)S 2181(Blinn)S 2341([Bli78a])S 2568(and)S 2681(Miller)S 2858(&)S 2931(Hoffman)S 3118 2661(n)U 556 2733([)U 556 2661([Mil84],)U 784(respective)S 1029(ly.)S 1137(Systems)S 1363(aspects)S 1563(of)S 1639(texture)S 1833(mapping)S 2070(are)S 2170(discussed)S 2426(by)S 2512(Cook)S 2667([Coo84])S 2892(and)S 3004(Perli)S 576 2733(Per85a].)U 556 2898([)U (Aok78])R 796(Masayoshi)S 1079(Aoki,)S 1237(Martin)S 1424(D.)S 1505(Levine,)S 1711(``Computer)S 2015(Generation)S 2306(of)S 2379(Realistic)S 2614(Pictures'',)S 2 F 2885(Computers)S 1 F 556 3063([)U 2 F 796 2970(and)U 906(Graphics)S 1 F (,)R 1164(Vol.)S 1289(3,)S 1354(1978,)S 1509(pp.)S 1604(149-161.)S 576 3063(Bie86])U 796(Eric)S 918(A.)S 997(Bier,)S 1137(Kenneth)S 1362(R.)S 1438(Sloan,)S 1611(Jr.,)S 1704(``Two-Part)S 1991(Texture)S 2199(Mappings'',)S 2 F 2514(IEEE)S 2665(Computer)S 2925(Graphics)S 1 F 556 3228([)U 2 F 796 3135(and)U 906(Applicati)S 1128(ons)S 1 F (,)R 1246(Vol.)S 1371(6,)S 1436(No.)S 1544(9,)S 1609(Sept.)S 1751(1986,)S 1906(pp.)S 2001(40-53.)S 576 3228(Bli76])U 796(James)S 966(F.)S 1037(Blinn,)S 1209(Martin)S 1396(E.)S 1471(Newell,)S 1683(``Texture)S 1934(and)S 2044(Re\257ection)S 2315(in)S 2385(Computer)S 2649(Generated)S 2919(Images'',)S 556 3393([)U 2 F 796 3300(CACM)U 1 F (,)R 998(Vol.)S 1123(19,)S 1218(No.)S 1326(10,)S 1421(Oct.)S 1543(1976,)S 1698(pp.)S 1793(542-547.)S 576 3393(Bli78a])U 796(James)S 972(F.)S 1049(Blinn,)S 1227(``Simulation)S 1561(of)S 1640(Wrinkled)S 1897(Surfaces'',)S 2 F 2188(Computer)S 2456(Graphics)S 1 F (,)R 2722(\(SIGGRAPH)S 3068('78)S 556 3558([)U 796 3465(Proceedings\),)U 1145(Vol.)S 1270(12,)S 1365(No.)S 1473(3,)S 1538(Aug.)S 1676(1978,)S 1831(pp.)S 1926(286-292.)S 576 3558(Bli78b])U 796(James)S 967(F.)S 1039(Blinn,)S 1212(``Computer)S 1517(Display)S 1728(of)S 1802(Curved)S 2003(Surfaces'',)S 2289(PhD)S 2419(thesis,)S 2595(CS)S 2692(Dept.,)S 2862(U.)S 2943(of)S 3016(Utah,)S 556 3723([)U 796 3630(1978.)U 576 3723(Bra80])U 796(Carlo)S 952(Braccini,)S 1194(Giuseppe)S 1442(Marino,)S 1655(``Fast)S 1816(Geometrica)S 2098(l)S 2136(Manipulations)S 2505(of)S 2576(Digital)S 2765(Images'',)S 2 F 3015(Com-)S 1 F 556 3888([)U 2 F 796 3795(puter)U 943(Graphics)S 1186(and)S 1296(Image)S 1466(Processing)S 1 F (,)R 1768(Vol.)S 1893(13,)S 1988(1980,)S 2143(pp.)S 2238(127-141.)S 576 3888(Bur81])U 796(Peter)S 944(J.)S 1006(Burt,)S 1152(``Fast)S 1316(Filter)S 1471(Transforms)S 1771(for)S 1864(Image)S 2038(Processing'',)S 2 F 2376(Computer)S 2639(Graphics)S 2885(and)S 2998(Image)S 1 F 556 4053([)U 2 F 796 3960(Processing)U 1 F (,)R 1098(Vol.)S 1223(16,)S 1318(1981,)S 1473(pp.)S 1568(20-51.)S 576 4053(Car85])U 796(Richard)S 1009(J.)S 1069(Carey,)S 1250(Donald)S 1449(P.)S 1519(Greenberg,)S 1810(``Textures)S 2083(for)S 2174(Realistic)S 2407(Image)S 2579(Synthesis'',)S 2 F 2885(Computers)S 1 F 16 4710(-)U 2 F 796 4125(and)U 906(Graphics)S 1 F (,)R 1164(Vol.)S 1289(9,)S 1354(No.)S 1462(2,)S 1527(1985,)S 1682(pp.)S 1777(125-138.)S 36 4710(-)U 3259(--)S EP %%Page: ? 13 BP 1 F 60 Z 556 438([)U 1782 246(-)U 1822(13)S 1902(-)S 576 438(Cat74])U 796(Ed)S 889(Catmull,)S 2 F 1125(A)S 1188(Subdivision)S 1495(Algorithm)S 1765(for)S 1861(Computer)S 2127(Display)S 2340(of)S 2413(Curved)S 2616(Surfaces)S 1 F (,)R 2864(PhD)S 2996(thesis,)S 556 603([)U 796 510(Dept.)U 948(of)S 1018(CS,)S 1126(U.)S 1204(of)S 1274(Utah,)S 1426(Dec.)S 1558(1974.)S 576 603(Cat80])U 796(Ed)S 885(Catmull,)S 1117(Alvy)S 1258(Ray)S 1376(Smith,)S 1556(``3-D)S 1710(Transformations)S 2129(of)S 2200(Images)S 2395(in)S 2463(Scanline)S 2692(Order'',)S 2 F 2908(Computer)S 1 F 556 768([)U 2 F 796 675(Graphics)U 1 F (,)R 1054(\(SIGGRAPH)S 1392('80)S 1492(Proceedings\),)S 1841(Vol.)S 1966(14,)S 2061(No.)S 2169(3,)S 2234(July)S 2354(1980,)S 2509(pp.)S 2604(279-285.)S 576 768(Coo84])U 796(Robert)S 981(L.)S 1054(Cook,)S 1220(``Shade)S 1428(Trees'',)S 2 F 1638(Computer)S 1899(Graphics)S 1 F (,)R 2158(\(SIGGRAPH)S 2497('84)S 2598(Proceedings\),)S 2948(Vol.)S 3073(18,)S 556 933([)U 796 840(No.)U 904(3,)S 969(July)S 1089(1984,)S 1244(pp.)S 1339(223-231.)S 576 933(Coo86])U 796(Robert)S 991(L.)S 1074(Cook,)S 1250(``Antialiasing)S 1616(by)S 1707(Stochastic)S 1986(Sampling'',)S 2303(to)S 2381(appear,)S 2 F 2588(ACM)S 2745(Transactions)S 3088(on)S 1 F 556 1098([)U 2 F 796 1005(Graphics)U 1 F (,)R 1054(1986.)S 576 1098(Cro77])U 796(Franklin)S 1026(C.)S 1107(Crow,)S 1281(``The)S 1441(Aliasing)S 1671(Problem)S 1901(in)S 1974(Computer-Genera)S 2409(ted)S 2509(Shaded)S 2712(Images'',)S 2 F 2966(CACM)S 1 F (,)R 556 1263([)U 796 1170(Vol.)U 921(20,)S 1016(Nov.)S 1154(1977,)S 1309(pp.)S 1404(799-805.)S 576 1263(Cro84])U 796(Franklin)S 1025(C.)S 1105(Crow,)S 1278(``Summed-Area)S 1694(Tables)S 1880(for)S 1975(Texture)S 2188(Mapping'',)S 2 F 2485(Computer)S 2750(Graphics)S 1 F (,)R 3012(\(SIG-)S 556 1428([)U 796 1335(GRAPH)U 1018('84)S 1118(Proceedings\),)S 1467(Vol.)S 1592(18,)S 1687(No.)S 1795(3,)S 1860(July)S 1980(1984,)S 2135(pp.)S 2230(207-212.)S 576 1428(Dun78])U 796(Willia)S 948(m)S 1017(Dungan,)S 1244(Jr.,)S 1339(Anthony)S 1571(Stenger,)S 1792(George)S 1990(Sutty,)S 2153(``Texture)S 2402(Tile)S 2521(Considerations)S 2903(for)S 2994(Raster)S 3133 1500(,)U 796 1572(p)U 796 1500(Graphics'',)U 2 F 1097(Computer)S 1365(Graphics)S 1 F (,)R 1631(\(SIGGRAPH)S 1977('78)S 2085(Proceedings\),)S 2442(Vol.)S 2575(12,)S 2678(No.)S 2794(3,)S 2867(Aug.)S 3013(1978)S 826 1572(p.)U 891(130-134.)S 556 1665([)U (Fei80])R 796(Eliot)S 938(A.)S 1020(Feibush,)S 1249(Marc)S 1400(Levoy,)S 1593(Robert)S 1781(L.)S 1857(Cook,)S 2026(``Synthetic)S 2318(Texturing)S 2580(Using)S 2747(Digital)S 2939(Filters'',)S 556 1830([)U 2 F 796 1737(Computer)U 1056(Graphics)S 1 F (,)R 1314(\(SIGGRAPH)S 1652('80)S 1752(Proceedings\),)S 2101(Vol.)S 2226(14,)S 2321(No.)S 2429(3,)S 2494(July)S 2614(1980,)S 2769(pp.)S 2864(294-301.)S 576 1830(Fer84])U 796(Leonard)S 1028(A.)S 1117(Ferrari,)S 1327(Jack)S 1465(Sklansky,)S 1731(``A)S 1845(Fast)S 1976(Recursive)S 2248(Algorithm)S 2530(for)S 2630(Binary-Valued)S 3018(Two-)S 796 1974(1)U 796 1902(Dimensional)U 1125(Filters'',)S 2 F 1355(Computer)S 1616(Vision,)S 1805(Graphics,)S 2063(and)S 2173(Image)S 2343(Processing)S 1 F (,)R 2645(Vol.)S 2770(26,)S 2865(No.)S 2973(3,)S 3038(June)S 826 1974(984,)U 951(pp.)S 1046(292-302.)S 556 2067([)U (Fer85])R 796(Leonard)S 1029(A.)S 1119(Ferrari,)S 1330(Jack)S 1469(Sklansky,)S 1736(``A)S 1851(Note)S 2000(on)S 2092(Duhamel)S 2345(Integrals)S 2588(and)S 2706(Running)S 2944(Average)S 556 2232([)U 796 2139(Filters'',)U 2 F 1025(Computer)S 1285(Vision,)S 1474(Graphics,)S 1732(and)S 1842(Image)S 2012(Processing)S 1 F (,)R 2314(Vol.)S 2439(29,)S 2534(Mar.)S 2669(1985,)S 2824(pp.)S 2919(358-360.)S 576 2232(Fer86])U 796(Leonard)S 1018(A.)S 1096(Ferrari,)S 1295(P.)S 1363(V.)S 1441(Sankar,)S 1643(Jack)S 1770(Sklansky,)S 2025(Sidney)S 2212(Leeman,)S 2442(``Ef\256cient)S 2710(Two-Dimensional)S 2 F 796 2376(P)U 1 F 796 2304(Filters)U 979(Using)S 1151(B-Spline)S 1394(Approximations'',)S 1869(to)S 1945(appear,)S 2 F 2149(Computer)S 2417(Vision,)S 2614(Graphics,)S 2880(and)S 2998(Image)S 833 2376(rocessing)U 1 F (.)R 556 2469([)U (Fol82])R 796(James)S 989(D.)S 1093(Foley,)S 1291(Andries)S 1527(van)S 1660(Dam,)S 2 F 1837(Fundamentals)S 2226(of)S 2318(Interactive)S 2625(Computer)S 2910(Graphics)S 1 F (,)R 556 2634([)U 796 2541(Addison-Wesley,)U 1235(Reading,)S 1471(MA,)S 1602(1982.)S 576 2634(Fra85])U 796(Donald)S 995(Fraser,)S 1182(Robert)S 1368(A.)S 1448(Schowengerdt,)S 1828(Ian)S 1926(Briggs,)S 2122(``Recti\256cat)S 2394(ion)S 2492(of)S 2563(Multichannel)S 2906(Images)S 3101(in)S 2 F 3128 2706(-)U 796 2778(i)U 1 F 796 2706(Mass)U 949(Storage)S 1160(Using)S 1330(Image)S 1508(Transposition'',)S 2 F 1921(Computer)S 2187(Vision,)S 2382(Graphics,)S 2646(and)S 2762(Image)S 2938(Process)S 813 2778(ng)U 1 F (,)R 908(Vol.)S 1033(29,)S 1128(No.)S 1236(1,)S 1301(Jan.)S 1416(1985,)S 1571(pp.)S 1666(23-36.)S 556 2871([)U (Gan82])R 796(Michel)S 996(Gangnet,)S 1244(Didier)S 1427(Perny,)S 1611(Philippe)S 1841(Coueignoux,)S 2179(``Perspective)S 2526(Mapping)S 2772(of)S 2851(Planar)S 3034(Tex-)S 2 F 796 3015(C)U 1 F 796 2943(tures'',)U 2 F 994(Eurographics)S 1350('82)S 1 F (,)R 1471(1982,)S 1632(pp.)S 1733(57-71,)S 1914(\(slightly)S 2141(superior)S 2364(to)S 2437(the)S 2537(version)S 2740(that)S 2857(appeared)S 3101(in)S 2 F 836 3015(omputer)U 1056(Graphics)S 1 F (,)R 1314(Vol.)S 1439(16,)S 1534(No.)S 1642(1,)S 1707(May)S 1837(1982\).)S 3118 3108(5)U 556([Gar85])S 796(Geoffrey)S 1039(Y.)S 1123(Gardner,)S 1360(``Visual)S 1582(Simulation)S 1872(of)S 1947(Clouds'',)S 2 F 2197(Computer)S 2462(Graphics)S 1 F (,)R 2725(\(SIGGRAPH)S 3068('8)S 796 3180(Proceedings\),)U 1145(Vol.)S 1270(19,)S 1365(No.)S 1473(3,)S 1538(July)S 1658(1985,)S 1813(pp.)S 1908(297-303.)S 3128 3273(-)U 556([Gla86])S 796(Andrew)S 1017(S.)S 1093(Glassner,)S 1346(``Adaptive)S 1635(Precision)S 1887(in)S 1962(Texture)S 2178(Mapping'',)S 2 F 2478(Computer)S 2746(Graphics)S 1 F (,)R 3012(\(SIG)S 796 3345(GRAPH)U 1018('86)S 1118(Proceedings\),)S 1467(Vol.)S 1592(20,)S 1687(No.)S 1795(4,)S 1860(Aug.)S 1998(1986,)S 2153(pp.)S 2248(297-306.)S 3121 3438(e)U 556([Gor84])S 796(Cindy)S 965(M.)S 1055(Goral,)S 1229(Kenneth)S 1455(E.)S 1529(Torrance,)S 1784(Donald)S 1983(P.)S 2053(Greenberg,)S 2344(Bennett)S 2554(Battail)S 2716(e,)S 2779(``Modeling)S 3074(th)S 796 3510(Interacti)U 998(on)S 1101(of)S 1194(Light)S 1367(Between)S 1620(Diffuse)S 1842(Surfaces'',)S 2 F 2146(Computer)S 2428(Graphics)S 1 F (,)R 2708(\(SIGGRAPH)S 3068('84)S 556 3675([)U 796 3582(Proceedings\),)U 1145(Vol.)S 1270(18,)S 1365(No.)S 1473(3,)S 1538(July)S 1658(1984,)S 1813(pp.)S 1908(213-222.)S 576 3675(Gre86a])U 796(Ned)S 917(Greene,)S 1127(``Environment)S 1503(Mapping)S 1741(and)S 1849(Other)S 2007(Applications)S 2335(of)S 2405(World)S 2579(Projections'',)S 2 F 2925(Graphics)S 1 F 556 3840([)U 2 F 796 3747(Interface)U 1034('86)S 1 F (,)R 1149(May)S 1279(1986,)S 1434(pp.)S 1529(108-114.)S 576 3840(Gre86b])U 796(Ned)S 919(Greene,)S 1131(Paul)S 1261(S.)S 1332(Heckbert,)S 1591(``Creating)S 1862(Raster)S 2039(Omnimax)S 2303(Images)S 2500(from)S 2640(Multiple)S 2870(Perspective)S 2 F 3128 3912(-)U 796 3984(t)U 1 F 796 3912(Views)U 970(Using)S 1134(The)S 1248(Elliptic)S 1427(al)S 1491(Weighted)S 1746(Average)S 1970(Filter'',)S 2 F 2176(IEEE)S 2327(Computer)S 2587(Graphics)S 2830(and)S 2940(Applica)S 813 3984(ions)U 1 F (,)R 948(Vol.)S 1073(6,)S 1138(No.)S 1246(6,)S 1311(June,)S 1456(1986,)S 1611(pp.)S 1706(21-27.)S 556 4077([)U (Hec83])R 796(Paul)S 936(S.)S 1017(Heckbert,)S 1285(``Texture)S 1545(Mapping)S 1794(Polygons)S 2049(in)S 2128(Perspective'',)S 2493(Technica)S 2715(l)S 2764(Memo)S 2953(No.)S 3073(13,)S 16 4710(-)U 796 4149(NYIT)U 959(Computer)S 1220(Graphics)S 1457(Lab,)S 1586(April)S 1733(1983.)S 36 4710(-)U 3259(--)S EP %%Page: ? 14 BP 1 F 60 Z 556 438([)U 1782 246(-)U 1822(14)S 1902(-)S 576 438(Hec86])U 796(Paul)S 927(S.)S 999(Heckbert,)S 1258(``Filtering)S 1529(by)S 1612(Repeate)S 1807(d)S 1860(Integration'',)S 2 F 2203(Computer)S 2466(Graphics)S 1 F (,)R 2727(\(SIGGRAPH)S 3068('86)S 556 603([)U 796 510(Proceedings\),)U 1145(Vol.)S 1270(20,)S 1365(No.)S 1473(4,)S 1538(Aug.)S 1676(1986,)S 1831(pp.)S 1926(317-321.)S 576 603(Hor81])U 796(Berthold)S 1032(K.)S 1115(P.)S 1188(Horn,)S 1351(``Hill)S 1510(Shading)S 1732(and)S 1844(the)S 1942(Re\257ectanc)S 2197(e)S 2248(Map'',)S 2 F 2437(Proc.)S 2593(IEEE)S 1 F (,)R 2763(Vol.)S 2892(69,)S 2991(No.)S 3103(1,)S 556 768([)U 796 675(Jan.)U 911(1981,)S 1066(pp.)S 1161(14-47.)S 576 768(Hou83])U 796(J.)S 856(C.)S 933(Hourcade,)S 1204(A.)S 1284(Nicolas,)S 1505(``Inverse)S 1744(Perspective)S 2044(Mapping)S 2283(in)S 2352(Scanline)S 2582(Order)S 2743(onto)S 2871(Non-Planar)S 556 933([)U 796 840(Quadrilatera)U 1098(ls'',)S 2 F 1213(Eurographics)S 1563('83)S 1 F (,)R 1678(1983,)S 1833(pp.)S 1928(309-319.)S 576 933(Kaj85])U 796(James)S 976(T.)S 1061(Kajiya,)S 1270(``Anisotropic)S 1627(Re\257ection)S 1908(Models'',)S 2 F 2176(Computer)S 2448(Graphics)S 1 F (,)R 2718(\(SIGGRAPH)S 3068('85)S 556 1098([)U 796 1005(Proceedings\),)U 1145(Vol.)S 1270(19,)S 1365(No.)S 1473(3,)S 1538(July)S 1658(1985,)S 1813(pp.)S 1908(15-21.)S 576 1098(Kay79])U 796(Douglas)S 1026(S.)S 1104(Kay,)S 1249(Donald)S 1456(P.)S 1534(Greenberg,)S 1833(``Transparency)S 2230(for)S 2329(Computer)S 2599(Synthesized)S 2919(Images'',)S 556 1263([)U 2 F 796 1170(Computer)U 1056(Graphics)S 1 F (,)R 1314(\(SIGGRAPH)S 1652('79)S 1752(Proceedings\),)S 2101(Vol.)S 2226(13,)S 2321(No.)S 2429(2,)S 2494(Aug.)S 2632(1979,)S 2787(pp.)S 2882(158-164.)S 576 1263(Lee85])U 796(Mark)S 953(E.)S 1031(Lee,)S 1163(Richard)S 1380(A.)S 1464(Redner,)S 1679(Samuel)S 1886(P.)S 1960(Uselton,)S 2188(``Statistica)S 2450(lly)S 2540(Optimized)S 2821(Sampling)S 3078(for)S 3133 1335(,)U 796 1407(J)U 796 1335(Distributed)U 1088(Ray)S 1206(Tracing'',)S 2 F 1470(Computer)S 1730(Graphics)S 1 F (,)R 1988(\(SIGGRAPH)S 2326('85)S 2426(Proceedings\),)S 2775(Vol.)S 2900(19,)S 2995(No.)S 3103(3)S 819 1407(uly)U 916(1985,)S 1071(pp.)S 1166(61-67.)S 556 1500([)U (Mil84])R 796(Gene)S 945(S.)S 1015(Miller,)S 1203(C.)S 1280(Robert)S 1466(Hoffman,)S 1720(``Illuminat)S 1982(ion)S 2081(and)S 2190(Re\257ection)S 2459(Maps:)S 2630(Simulated)S 2896(Objects)S 3101(in)S 2 F 3118 1572(n)U 796 1644(s)U 1 F 796 1572(Simulated)U 1063(and)S 1172(Real)S 1305(Environments'',)S 2 F 1720(SIGGRAPH)S 2032('84)S 2133(Advanced)S 2392(Computer)S 2653(Graphics)S 2897(Animatio)S 819 1644(eminar)U 1009(notes)S 1 F (,)R 1171(July)S 1291(1984.)S 556 1737([)U (Nor82])R 796(Alan)S 936(Norton,)S 1144(Alyn)S 1287(P.)S 1358(Rockwood,)S 1656(Philip)S 1822(T.)S 1896(Skolmoski,)S 2190(``Clamping:)S 2507(A)S 2572(Method)S 2781(of)S 2853(Antialiasing)S 3128 1809(-)U 796 1881(G)U 796 1809(Textured)U 1051(Surfaces)S 1295(by)S 1392(Bandwidth)S 1693(Limiting)S 1942(in)S 2026(Object)S 2224(Space'',)S 2 F 2460(Computer)S 2737(Graphics)S 1 F (,)R 3012(\(SIG)S 839 1881(RAPH)U 1018('82)S 1118(Proceedings\),)S 1467(Vol.)S 1592(16,)S 1687(No.)S 1795(3,)S 1860(July)S 1980(1982,)S 2135(pp.)S 2230(1-8.)S 3118 1974(d)U 556([Opp75])S 796(Alan)S 935(V.)S 1015(Oppenheim,)S 1333(Ronald)S 1529(W.)S 1623(Schafer,)S 2 F 1844(Digital)S 2037(Signal)S 2213(Processing)S 1 F (,)R 2516(Prentice-Hall)S 2838(,)S 2874(Englewoo)S 796 2046(Cliffs,)U 968(NJ,)S 1069(1975.)S 556 2139([)U (Pae86])R 796(Alan)S 944(W.)S 1047(Paeth,)S 1227(``A)S 1341(Fast)S 1472(Algorithm)S 1754(for)S 1854(General)S 2075(Raster)S 2259(Rotation'',)S 2 F 2552(Graphics)S 2805(Interface)S 3053('86)S 1 F (,)R 556 2304([)U 796 2211(May)U 926(1986,)S 1081(pp.)S 1176(77-81.)S 576 2304(Pea85])U 796(Darwyn)S 1023(R.)S 1112(Peachey,)S 1362(``Solid)S 1563(Texturing)S 1835(of)S 1919(Complex)S 2173(Surfaces'',)S 2 F 2468(Computer)S 2741(Graphics)S 1 F (,)R 3012(\(SIG-)S 556 2469([)U 796 2376(GRAPH)U 1018('85)S 1118(Proceedings\),)S 1467(Vol.)S 1592(19,)S 1687(No.)S 1795(3,)S 1860(July)S 1980(1985,)S 2135(pp.)S 2230(279-286.)S 576 2469(Per84])U 796(Ken)S 923(Perlin,)S 1109(``A)S 1219(Uni\256ed)S 1426(Texture/Re)S 1698(\257ectance)S 1940(Model'',)S 2 F 2179(SIGGRAPH)S 2495('84)S 2601(Advanced)S 2865(Image)S 3041(Syn-)S 1 F 556 2634([)U 2 F 796 2541(thesis)U 953(seminar)S 1166(notes)S 1 F (,)R 1328(July)S 1448(1984.)S 576 2634(Per85a])U 796(Ken)S 928(Perlin,)S 1119(``An)S 1264(Image)S 1447(Synthesizer'',)S 2 F 1815(Computer)S 2087(Graphics)S 1 F (,)R 2357(\(SIGGRAPH)S 2707('85)S 2819(Proceedings\),)S 556 2799([)U 796 2706(Vol.)U 921(19,)S 1016(No.)S 1124(3,)S 1189(July)S 1309(1985,)S 1464(pp.)S 1559(287-296.)S 576 2799(Per85b])U 796(Ken)S 926(Perlin,)S 1115(``Course)S 1355(Notes'',)S 2 F 1580(SIGGRAPH)S 1900('85)S 2010(State)S 2161(of)S 2238(the)S 2341(Art)S 2447(in)S 2523(Image)S 2702(Synthesis)S 2955(seminar)S 1 F 556 2964([)U 2 F 796 2871(notes)U 1 F (,)R 958(July)S 1078(1985.)S 576 2964(Rob66])U 796(Lawrence)S 1085(G.)S 1194(Roberts,)S 2 F 1447(Homogeneous)S 1841(Matrix)S 2056(Representation)S 2472(and)S 2613(Manipulation)S 2991(of)S 3088(N-)S 1 F 556 3129([)U 2 F 796 3036(Dimensional)U 1123(Constructs)S 1 F (,)R 1418(MS-1045,)S 1679(Lincoln)S 1887(Lab,)S 2016(Lexington,)S 2299(MA,)S 2430(July)S 2550(1966.)S 576 3129(Rog85])U 796(David)S 977(F.)S 1059(Rogers,)S 2 F 1278(Procedural)S 1586(Elements)S 1841(for)S 1945(Computer)S 2218(Graphics)S 1 F (,)R 2489(McGraw-Hill,)S 2864(New)S 3010(York,)S 556 3294([)U 796 3201(1985.)U 576 3294(Ros84])U 796(A.)S 874(Rosenfeld,)S 2 F 1153(Multiresolution)S 1548(Image)S 1718(Processing)S 2005(and)S 2115(Analysis)S 1 F (,)R 2354(Springer,)S 2596(Berlin,)S 2782(1984.)S 2 F 3133 3387(,)U 1 F 556([Sha82])S 796(Michael)S 1026(Shantz,)S 1237(``Two)S 1419(Pass)S 1557(Warp)S 1723(Algorithm)S 2006(for)S 2108(Hardware)S 2377(Implement)S 2639(ation'',)S 2 F 2846(Proc.)S 3009(SPIE)S 796 3459(Processing)U 1083(and)S 1193(Display)S 1400(of)S 1467(Three)S 1627(Dimensional)S 1954(Data)S 1 F (,)R 2109(Vol.)S 2234(367,)S 2359(1982,)S 2514(pp.)S 2609(160-164.)S 2 F 3128 3552(-)U 1 F 556([Smi80])S 796(Alvy)S 942(Ray)S 1065(Smith,)S 1250(``Incrementa)S 1562(l)S 1605(Rendering)S 1882(of)S 1958(Textures)S 2194(in)S 2266(Perspective'',)S 2 F 2624(SIGGRAPH)S 2939('80)S 3044(Ani)S 796 3624(mation)U 983(Graphics)S 1226(seminar)S 1439(notes)S 1 F (,)R 1601(July)S 1721(1980.)S 556 3717([)U (Smi83])R 796(Alvy)S 946(Ray)S 1073(Smith,)S 1262(``Digital)S 1500(Filtering)S 1738(Tutorial)S 1963(for)S 2063(Computer)S 2334(Graphics'',)S 2636(parts)S 2783(1)S 2843(and)S 2960(2,)S 2 F 3035(SIG-)S 1 F 3128 3789(-)U 796 3861(2)U 2 F 796 3789(GRAPH)U 1016('83)S 1119(Introduction)S 1442(to)S 1511(Computer)S 1773(Animation)S 2046(seminar)S 2261(notes)S 1 F (,)R 2425(July)S 2547(1983,)S 2704(pp.)S 2801(244-261,)S 3038(262)S 826 3861(72.)U 556 3954([)U (Tan75])R 796(S.)S 866(L.)S 940(Tanimoto,)S 1212(Theo)S 1358(Pavlidis,)S 1589(``A)S 1694(Hierarchic)S 1949(al)S 2015(Data)S 2151(Structure)S 2394(for)S 2486(Picture)S 2679(Processing'',)S 2 F 3015(Com-)S 1 F 16 4710(-)U 2 F 796 4026(puter)U 943(Graphics)S 1186(and)S 1296(Image)S 1466(Processing)S 1 F (,)R 1768(Vol.)S 1893(4,)S 1958(No.)S 2066(2,)S 2131(June)S 2261(1975,)S 2416(pp.)S 2511(104-119.)S 36 4710(-)U 3259(--)S EP %%Page: ? 15 BP 1 F 60 Z 556 438([)U 1782 246(-)U 1822(15)S 1902(-)S 576 438(Wei80])U 796(Carl)S 925(F.)S 998(R.)S 1078(Weiman,)S 1323(``Continuous)S 1664(Anti-Aliased)S 1999(Rotation)S 2231(and)S 2342(Zoom)S 2510(of)S 2584(Raster)S 2762(Images'',)S 2 F 3015(Com-)S 1 F 556 603([)U 2 F 796 510(puter)U 943(Graphics)S 1 F (,)R 1201(\(SIGGRAPH)S 1539('80)S 1639(Proceedings\),)S 1988(Vol.)S 2113(14,)S 2208(No.)S 2316(3,)S 2381(July)S 2501(1980,)S 2656(pp.)S 2751(286-293.)S 576 603(Whi81])U 796(Turner)S 986(Whitted,)S 1222(``The)S 1382(Causes)S 1578(of)S 1654(Aliasing)S 1884(in)S 1957(Computer)S 2224(Generated)S 2498(Images'',)S 2 F 2753(SIGGRAPH)S 3068('81)S 1 F 556 768([)U 2 F 796 675(Advanced)U 1054(Image)S 1224(Synthesis)S 1468(seminar)S 1681(notes)S 1 F (,)R 1843(Aug.)S 1981(1981.)S 576 768(Wil83])U 796(Lance)S 976(Willia)S 1128(ms,)S 1244(``Pyramidal)S 1563(Parametric)S 1825(s'',)S 2 F 1934(Computer)S 2205(Graphics)S 1 F (,)R 2474(\(SIGGRAPH)S 2823('83)S 2934(Proceed-)S 16 4704(-)U 796 840(ings\),)U 951(Vol.)S 1076(17,)S 1171(No.)S 1279(3,)S 1344(July)S 1464(1983,)S 1619(pp.)S 1714(1-11.)S 36 4704(-)U 3259(--)S EP %%Trailer pscatsave end restore %%Pages: 15