Science, Faculty of
Computer Science, Department of
DSpace
UBCV
Gu, Floria Ziting
Master of Science - MSc
University of British Columbia
Atlas packing is a key step in many computer graphics applications. Packing algorithms seek to arrange a set of charts within a fixed-size atlas with as little downscaling as possible. Many packing applications such as content creation tools, dynamic atlas generation for video games, and texture space shading require on-the-fly interactive atlas packing. Unfortunately, while many methods have been developed for generating tight high-quality packings, they are designed for offline settings and have running times two or more orders of magnitude greater than what is required for interactive performance. While real-time GPU packing methods exist, they significantly downscale packed charts compared to offline methods. We introduce a GPU packing method that targets interactive speeds, provides packing quality approaching that of offline methods, and supports flexible user control over the tradeoff between performance and quality. We observe that current real-time packing methods leave large gaps between charts and often produce asymmetric, or poorly balanced, packings. These artifacts dramatically degrade packing quality. Our Tight And Balanced method eliminates these artifacts while retaining Interactive performance. TABI generates tight packings by compacting empty space between irregularly shaped charts both horizontally and vertically, using two approximations of chart shape that support efficient parallel processing. We balance packing outputs by automatically adjusting atlas row widths and orientations to accommodate varying chart heights. We show that our method significantly reduces chart downscaling compared to existing interactive methods while remaining orders of magnitude faster than offline alternatives.
TABI: Tight and Balanced Interactive Atlas PackingbyFloria Ziting GuB.Sc., University of British Columbia, 2023A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFMaster of ScienceinTHE FACULTY OF GRADUATE AND POSTDOCTORAL STUDIES(Computer Science)The University of British Columbia(Vancouver)October 2025© Floria Ziting Gu, 2025The following individuals certify that they have read, and recommend to the Faculty of Graduate and Post-doctoral Studies for acceptance, the thesis entitled:TABI: Tight and Balanced Interactive Atlas Packingsubmitted by Floria Ziting Gu in partial fulfillment of the requirements for the degree of Master of Sciencein Computer Science.Examining Committee:Alla Sheffer, Professor, Computer Science, UBCSupervisorPeter Yichen Chen, Assistant Professor, Computer Science, UBCSupervisory Committee MemberiiAbstractAtlas packing is a key step in many computer graphics applications. Packing algorithms seek to arrangea set of charts within a fixed-size atlas with as little downscaling as possible. Many packing applicationssuch as content creation tools, dynamic atlas generation for video games, and texture space shading requireon-the-fly interactive atlas packing. Unfortunately, while many methods have been developed for generatingtight high-quality packings, they are designed for offline settings and have running times two or more ordersof magnitude greater than what is required for interactive performance. While real-time GPU packingmethods exist, they significantly downscale packed charts compared to offline methods. We introduce aGPU packing method that targets interactive speeds, provides packing quality approaching that of offlinemethods, and supports flexible user control over the tradeoff between performance and quality. We observethat current real-time packing methods leave large gaps between charts and often produce asymmetric, orpoorly balanced, packings. These artifacts dramatically degrade packing quality. Our Tight And Balancedmethod eliminates these artifacts while retaining Interactive performance. TABI generates tight packingsby compacting empty space between irregularly shaped charts both horizontally and vertically, using twoapproximations of chart shape that support efficient parallel processing. We balance packing outputs byautomatically adjusting atlas row widths and orientations to accommodate varying chart heights. We showthat our method significantly reduces chart downscaling compared to existing interactive methods whileremaining orders of magnitude faster than offline alternatives.iiiLay SummaryAtlas packing algorithms aim to fit a set of irregular shapes into a fixed-size rectangular container with mini-mal downscaling. In many computer graphics applications, atlas packing is a key step and must be performedat interactive speeds (â¤ 15 milliseconds). Though many methods have been developed for generating tight,high-quality packings, their runtimes are two or more orders of magnitude too slow for interactive settings,while existing interactive methods dramatically increase downscaling of the input shapes in comparison.We introduce a novel interactive GPU packing algorithm that provides packing quality approaching that ofnon-interactive methods. We observe that existing interactive methods leave large gaps between shapes andoften produce asymmetric, or poorly balanced, packings, and design our method to eliminate these artifacts.We show that our method significantly reduces shape downscaling compared to existing interactive methodswhile remaining orders of magnitude faster than non-interactive alternatives.ivPrefaceThe work presented in this thesis is the result of a collaboration between me (Floria Gu), Nicholas Vining,and Alla Sheffer. All algorithms and experiments were implemented and conducted by me under the su-pervision of Alla Sheffer and Nicholas Vining, who also assisted with editing this manuscript and providedguidance throughout the project. Suzuran Takikawa assisted with the creation of Figure 3.1. No GenerativeArtificial Intelligence tools were used in the development or writing of this thesis. At the time of writing,the method described in this work has been submitted for publication.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiv1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Objective and Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Fold-and-Push Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.1 Chameleon and FastAtlas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.2 FastAtlas and Chameleon Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.1 Improving Packing Tightness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.1.1 Chart Proxies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.1.2 Compacting Horizontal Gaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.1.3 Compacting Vertical Gaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.2 Balanced Folding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123.3 Algorithm Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.4 Performance Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 Results and Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16vi5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25A Supporting Materials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28A.1 Implementation Details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28A.2 Additional Evaluation Details. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35A.3 Additional Gallery. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35A.4 Additional Ablations and Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40viiList of TablesTable 4.1 Runtime comparison of our method against offline (Xatlas [40]) and interactive (FastAt-las [37], GPU Chameleon [16]) alternatives across our full dataset. The last 3 columnsshow the average ratios between alternatives and our runtimes. Our method is two or-ders of magnitude faster than the fastest offline alternative (Xatlas random), and thoughslower than FastAtlas and Chameleon, it remains interactive. . . . . . . . . . . . . . . . 16Table 4.2 Stretch comparison of our method against Xatlas [40] and interactive alternatives (Fas-tAtlas [37] and Chameleon [16]) across our dataset. Our outputs have significantly lowerstretch than those produced by interactive alternatives. The last two columns show theamount by which our method closes the stretch gap between interactive alternatives andthe best method per-input. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19Table 4.3 Ablating our full method against using only balanced folding or only tightening acrossour dataset (left: average packing time in milliseconds, right: average L2 stretch). Byoptimizing both tightness and balance we achieve the best stretch. . . . . . . . . . . . . . 21Table 4.4 Ablating topt on inputs with 1,000 charts or more (left: average packing time in millisec-onds, right: average L2 stretch between packed and input charts). Increasing topt reducespacking time, but increases stretch. Our method (topt = 0% for inputs with up to 10,000charts and topt = 1% otherwise), minimally increases stretch compared to topt = 0% whileachieving interactive runtimes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22Table A.1 Detailed runtime breakdown for each step of our method, averaged across all datasetsand atlas sizes (all times in milliseconds). Left to right: AABB and OBB computation,local AABB computation, chart sorting by AABB height, boundary refinement for localAABBs and chart orientation computation, horizontal compacting distance computation,balanced folding and pushing for all candidate scale factors, and total packing time (sumof all previous columns). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40viiiTable A.2 Runtime comparison of our method against both prior offline packing methods (Xat-las [40]) and alternatives capable of interactive performance (FastAtlas [37], our GPUimplementation of Chameleon [16]) on UV charts at full and half atlas sizes. The last3 columns show the average ratios between the runtime of alternatives and that of ourmethod. Our method is orders of magnitude faster than prior offline methods, and thoughslower than FastAtlas and Chameleon on average, it remains interactive. . . . . . . . . . 41Table A.3 Runtime comparison of our method against both prior offline packing methods (Xatlas[40]) and alternatives capable of interactive performance (FastAtlas [37], our GPU imple-mentation of Chameleon [16]) on texture-space shading charts at 1K and 2K atlas sizes.The last 3 columns show the average ratios between the runtime of alternatives and thatof our method. Our method is orders of magnitude faster than prior offline methods, andthough slower than FastAtlas and Chameleon on average, it remains interactive. . . . . . 41Table A.4 Packing scale comparison of our method against both prior offline packing methods (Xat-las [40]) and alternatives capable of interactive performance (FastAtlas [37], our GPU im-plementation of Chameleon [16]) on UV charts at full and half atlas sizes. Our methodconsistently outperforms interactive alternatives in terms of packing scale (average L2stretch between packed and input charts). The last two columns show the amount bywhich our method closes the stretch gap between interactive alternatives and the bestmethod per-input. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42Table A.5 Packing scale comparison of our method against both prior offline packing methods (Xat-las [40]) and alternatives capable of interactive performance (FastAtlas [37], our GPUimplementation of Chameleon [16]) on texture-space shading charts at 1K and 2K atlassizes. Our method consistently outperforms interactive alternatives in terms of packingscale (average L2 stretch between packed and input charts). The last two columns showthe amount by which our method closes the stretch gap between interactive alternativesand the best method per-frame. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42Table A.6 Quantitative comparison of our method against our balance component only and ourtightness component only on UV charts at full and half atlas sizes (left: average packingtime in milliseconds, right: average L2 stretch between packed and input charts). Our fullmethod, which combines both components, achieves the best packing scale. . . . . . . . 42Table A.7 Quantitative comparison of our method against our balance component only and ourtightness component only on texture-space shading charts at 1K and 2K atlas sizes (left:average packing time in milliseconds, right: average L2 stretch between packed and inputcharts). Our full method, which combines both components, achieves the best packingscale. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43ixTable A.8 Quantitative evaluation of different values of topt on texture-space shading frames withmore than 1,000 charts at 1K and 2K atlas sizes (left: average packing time in millisec-onds, right: average L2 stretch between packed and input charts). Higher values of toptreduce packing time, but increase stretch. Our method, which sets topt = 0% for in-puts with up to 10,000 charts and topt = 1% otherwise, achieves similar packing scale totopt = 0% while retaining interactive average runtimes. . . . . . . . . . . . . . . . . . . . 43Table A.9 Quantitative comparisons of our method with different numbers of local AABBs: 2,5, and our full method (10) averaged across all datasets and atlas sizes (left: averagepacking time in milliseconds, right: average L2 stretch between packed and input charts).Packing scale improves and the packing time increases with the number of local AABBs,providing a means to control the performance-quality tradeoff. . . . . . . . . . . . . . . 43Table A.10 Quantitative comparisons of our method with different numbers of local AABBs: 2, 5,and our full method (10) on UV charts at full and half atlas sizes (left: average packingtime in milliseconds, right: average L2 stretch between packed and input charts). Pack-ing scale improves and the packing time increases with the number of local AABBs,providing a means to control the performance-quality tradeoff. . . . . . . . . . . . . . . 44Table A.11 Quantitative comparisons of our method with different numbers of local AABBs: 2, 5,and our full method (10) on texture-space shading charts at 1K and 2K atlas sizes (left:average packing time in milliseconds, right: average L2 stretch between packed and inputcharts). Packing scale improves and the packing time increases with the number of localAABBs, providing a means to control the performance-quality tradeoff. . . . . . . . . . . 44xList of FiguresFigure 1.1 Offline packing methods, such as Xatlas [40] (a,b), generate tight, high-quality pack-ings, only minimally downscaling input charts. However, their runtimes are orders ofmagnitude higher than the threshold for interactive performance. Interactive packingmethods such as FastAtlas [37] (c) and GPU Chameleon [16] (d) generate packingswhich leave empty spaces between and underneath charts, requiring significantly largerchart downscaling to fit the charts into fixed size atlases. Our TABI packing algorithm(e) explicitly targets both tightness and balance, and achieves packing scale (as mea-sured by L2 stretch) nearly comparable to offline packing methods within an interactiveruntime budget. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2Figure 1.2 Atlas packing scale directly impacts visual quality in downstream applications. On thereference frame shown in (a), texture-space shaded renders generated using FastAtlas(c) exhibit significant blur as reflected in the FLIP error and error maps (black lowerror; pink to yellow high). This is caused by low packing scale, as measured by theL2 stretch. Renders generated using our method (d) more faithfully preserve the detailsof the frieze and closely approach the quality of renders generated using Xatlas (b), anoffline packing method. All methods use a 1K Ã 1K atlas. . . . . . . . . . . . . . . . . 3Figure 1.3 The GPU UVPackMaster packer [7] outputs have severe inter-chart overlaps on evenrelatively simple (a) inputs (overlap size measured as number of texels covered by twoor more charts). Our outputs are overlap-free and our method is 60 times faster. . . . . . 5Figure 2.1 FastAtlas (left) and GPU Chameleon (right) outputs on the input shown in Fig. 3.1.Both methods operate on chart bounding boxes. FastAtlas folds rows using a prefix-sum based relaxation which causes them to initially overflow, and alternates one left-starting row with two right-starting rows (a); it must further downscale charts prior topushing up in order to fit rows in the atlas (b). Chameleon folds rows sequentially andalternates between one left-starting row and one right-starting row (c), then pushes rowsup (d). Both methods generate packings with low tightness (note the large horizontaland vertical gaps between charts) and balance (note empty space in bottom right inChameleonâs output). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8xiFigure 3.1 TABI overview. (a) Charts placed in descending height order. They are then more tightlypacked horizontally using per-chart proxy shapes (Sec 3.1.2). We compute a target chartscale by evaluating a discrete range of possibilities in parallel. For each candidate scale,charts are scaled and folded into rows using balanced folding (Sec. 3.2). Charts are thentightly pushed up, one row at a time, using per-chart proxies (Sec. 3.1.3). Finally, wechoose the largest scale that does not overflow the atlas. . . . . . . . . . . . . . . . . . 10Figure 3.2 Imbalanced packings are caused by a failure to equalize accumulated chart heights onthe two sides of the packing. Simply alternating rows (left) immediately produces anunbalanced packing. Optimally selecting row directions to equalize height distribution(center) improves balance, but may still lead to wasted space. Our knee-based solution(right) handles large within-row changes in chart height, resulting in an efficient andbalanced packing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13Figure 4.1 Representative comparisons of our outputs against prior offline (Xatlas [40]) and inter-active (FastAtlas [37], Chameleon [16]) alternatives on chart sets originating from UVunwrapping. We achieve L2 stretch approaching that of offline methods, significantlyoutperforming FastAtlas and Chameleon, while maintaining interactive runtimes twoorders of magnitude faster than the offline methods. . . . . . . . . . . . . . . . . . . . . 17Figure 4.2 Representative comparisons of our outputs against prior offline (Xatlas [40]) and in-teractive (FastAtlas [37], Chameleon [16]) alternatives on TSS sourced inputs. Ourmethod achieves L2 stretch approaching that of offline methods, outperforming FastAt-las and Chameleon, while maintaining interactive runtimes several orders of magnitudefaster than those of offline alternatives. . . . . . . . . . . . . . . . . . . . . . . . . . . . 18Figure 4.3 Plot of stretch versus packing time (averages across our dataset) of our method com-pared to prior interactive and offline alternatives for different chart set sizes. In everysize interval, our method (green) shows a significant decrease in stretch relative to priorinteractive methods and remains at least 2 orders of magnitude faster than the closestoffline alternative. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20Figure 4.4 Applying only balanced folding (Sec 3.2) (a) leaves empty space within chartsâ bound-ing boxes, while using only tightening (Sec 3.1) (b) results in an imbalanced packingwith significant unused space in the bottom right. Our full method (c) combines bothcomponents to achieve the best stretch. . . . . . . . . . . . . . . . . . . . . . . . . . . 21Figure 4.5 Ablation of different values of topt on an extremely large input. Higher values (c,d)provide greater performance improvements at the cost of higher stretch. A value of0% (e), i.e. no prefix sum folding, yields the best packing scale but requires a muchlonger runtime. Our chosen setting (topt = 1%, f) significantly improves runtime withminiscule increase in stretch. At all values of topt TABI produces better quality atlasesthan prior interactive alternatives (a, b). . . . . . . . . . . . . . . . . . . . . . . . . . . 22xiiFigure 5.1 (a,b) Chameleon (a) and our TABI (b) packings on the input where TABI performsworst relative to Chameleon across our dataset (even in this worst case, the differencein stretch is minor). (c,d) A representative example of inputs where Tetris type methods(c) outperform TABI (d) by placing small charts into interior voids. . . . . . . . . . . . 24Figure A.1 Our extended GPU pushing algorithm. We define two functions for each chart, TopEdgeand BottomEdge, which are computed by rounding the top and bottom boundaries ofour chart shape proxies (a). In the first pass, each chart computes its vertical offset byreading all frontline texels it covers and comparing them to its TopEdge (b). Once chartvertical offsets are finalized, each chart updates the frontline with its BottomEdge (c). . . 29Figure A.2 Our parallel algorithm for computing the knee position from the frontline. Here a left-to-right row is illustrated; the right-to-left case is symmetric. We maintain the currentleft edge (inclusive) and right edge (exclusive) of the knee chart, and query the frontlineheight at the right edge (a). We find the closest intersection of the corresponding hor-izontal line with the knee chart by processing each frontline texel in the knee chart inparallel (b). Finally, we update the knee position and right edge of the knee chart usingthe location of the intersection (c). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31Figure A.3 The commercial GPU-based packer UVPackMaster outputs packings with severe over-laps (a). Overlap size is measured as the number of texels covered by two or morecharts at the same time. In addition, it fails to satisfy gutter requirements, measured bythe number of texels covered by two or more charts when rendered with 1 pixel gutterdilation. Our method (b) is overlap-free and over 20,000 times faster. . . . . . . . . . . 36Figure A.4 Additional comparisons of our outputs against prior offline (Xatlas [40]) and interac-tive (FastAtlas [37], Chameleon [16]) alternatives on chart sets originating from UVunwrapping. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36Figure A.5 Additional comparisons of our outputs against prior offline (Xatlas [40]) and interac-tive (FastAtlas [37], Chameleon [16]) alternatives on chart sets originating from UVunwrapping. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37Figure A.6 Additional comparisons of our outputs against prior offline (Xatlas [40]) and interac-tive (FastAtlas [37], Chameleon [16]) alternatives on chart sets originating from UVunwrapping. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38Figure A.7 Additional comparisons of our outputs against prior offline (Xatlas [40]) and interactive(FastAtlas [37], Chameleon [16]) alternatives on texture-space shading chart sets [37].For TSS data, charts are not pre-rotated to their tight bounding boxes. . . . . . . . . . . 39xiiiAcknowledgmentsI would like to thank my supervisor, Alla Sheffer, for her guidance and for everything I have learned fromher throughout this project. I am also grateful to Nicholas Vining for his help and technical insights, withoutwhich this project would not have been possible. Thanks to Suzuran Takikawa for help with figures and toall my labmates for their generosity in lending me their machines for experiments at odd hours. Finally, Iwould like to thank my parents for their support in every way.This research was funded by an NSERC CGS-M scholarship.xivChapter 1Introduction1.1 MotivationComputer graphics applications routinely use 2D atlases to store surface signals, such as albedo or normalmaps. This process involves cutting surfaces into charts, parameterizing these charts in 2D, and finally pack-ing the 2D charts into an atlas. Our work focuses on this final packing stage. Packing methods typically aimto pack a set of parameterized 2D charts, whose dimensions are determined by the resolution of the storedsignal, into a fixed size atlas. While this process, in contrast to packing problems in other domains (Sec. 1.3),often requires scaling the charts down to fit them into the atlas, packing methods seek to minimize down-scaling to preserve the input signal as accurately as possible (Fig. 1.2). For many applications, packing mustbe computed at interactive rates (under 15 milliseconds when targeting 60 FPS) as the set of charts changesdynamically over time. We propose a new packing algorithm which achieves interactive performance whiledrastically reducing the amount of downscaling compared to prior interactive alternatives.Computing optimal packings (ones that require the smallest amount of downscaling) is known to beNP-hard [24]. Existing methods use a range of heuristics to balance runtime against downscaling (Sec. 1.3).Some downscaling may be unavoidable, for instance if the area of the charts exceeds the area of the atlas;but intuitively, avoidable downscaling strongly and inversely correlates to the amount of space in the packedatlas that is not occupied by charts, as less âwastedâ area reflects less unnecessary downscaling.Offline packing methods (Sec. 1.3) produce atlases with relatively little wasted space, but at the costof long run times; for example, the industry standard Xatlas packing library [40], using its faster ârandomâsetting, requires nearly 500 milliseconds to pack the input in Fig. 1.1b (214 charts), and requires 2.5 secondsor more to pack the input in Fig 4.2b (1,572 charts). Interactive performance requires speeds which are atleast two orders of magnitude faster than this. Methods that achieve such performance [27, 37] do so bytaking advantage of GPU parallelism. Their performance improvement comes at the expense of a dramaticincrease in downscaling (Fig 1.1c, measured using the L2 stretch of the mapping from the downscaledatlased charts to their input counterparts [30, 37]; a stretch of 1 is ideal, indicating zero downscaling, whileincreased stretch reflects more downscaling).1(b) Xatlas (random)stretch: 1.06runtime: 466.9 ms(c) FastAtlasstretch: 1.40runtime: 0.6 ms(d) Chameleon (GPU)stretch: 1.42runtime: 0.7 ms(e) Oursstretch: 1.09runtime: 2.0 ms(a) Xatlas (brute force)stretch: 1.00runtime: 4,792.4 msFigure 1.1: Offline packing methods, such as Xatlas [40] (a,b), generate tight, high-quality packings,only minimally downscaling input charts. However, their runtimes are orders of magnitude higherthan the threshold for interactive performance. Interactive packing methods such as FastAtlas[37] (c) and GPU Chameleon [16] (d) generate packings which leave empty spaces betweenand underneath charts, requiring significantly larger chart downscaling to fit the charts into fixedsize atlases. Our TABI packing algorithm (e) explicitly targets both tightness and balance, andachieves packing scale (as measured by L2 stretch) nearly comparable to offline packing methodswithin an interactive runtime budget.1.2 Objective and OutlineOur GPU-based packing algorithm is 464 times faster on average than the best offline alternative, whiledramatically reducing stretch compared to prior interactive alternatives (Fig 1.1e). We achieve this reductionin stretch by identifying and addressing the two primary sources of wasted space in the best performinginteractive method, FastAtlas [37]: lack of tightness and imbalance (Sec 2.2). FastAtlas, and the Chameleon[16] method that inspired it (Fig 1.1d), pack the bounding rectangles of input charts, leaving the spacebetween charts and their bounding boxes wasted. Additionally, these methods also often generate height-imbalanced packings that leave large areas at the bottom of the atlas unoccupied by any charts (see theempty spaces on the bottom right of the atlases in Fig 1.1cd). Jointly, these two factors lead to significantlylarger chart downscaling compared to offline alternatives. Our Tight And Balanced Interactive (TABI)method reduces downscaling by decreasing the amount of space wasted around each chart, and by betterbalancing atlas chart placement (Sec 3, Fig 1.1e). TABI produces tighter packings at interactive speeds byemploying approximations of chart shape that can be efficiently used to compact empty space between chartsboth horizontally and vertically (Sec 3.1). We improve balance by dynamically adjusting atlas row widthsand directions to account for height differences between charts (Sec 3.2). Our method takes advantage ofGPU parallelism wherever possible, and permits users to adjust the performance/quality trade-off for theirneeds. It supports fixed width gutters [11], necessary for mipmapping, seam management, and higher-orderfiltering; and can be used both in settings where charts can be freely rotated to minimize downscaling andin those where only multiple-of-90â¦ rotations are allowed.We validate the performance of our method by applying it to 8,386 differently sourced chart sets, packingeach set at two different target atlas sizes (Sec 4). We test both chart sets originating from UV-unwrapped3D models (455 inputs), and texture-space shading chart sets produced by [37] (7,931 inputs); the latterincludes inputs with tens of thousands of charts (the largest containing 44,389 charts), all robustly handled2(c) FastAtlasstretch: 2.97FLIP: 0.165runtime: 0.6 ms(b) Xatlas (brute force)stretch: 2.04FLIP: 0.122runtime: 9480.9 ms(d) Oursstretch: 2.15FLIP: 0.128runtime: 2.5 ms(a) GroundTruthForwardrenderingFLIP Error Map FLIP Error MapFLIP Error MapFigure 1.2: Atlas packing scale directly impacts visual quality in downstream applications. On thereference frame shown in (a), texture-space shaded renders generated using FastAtlas (c) exhibitsignificant blur as reflected in the FLIP error and error maps (black low error; pink to yellowhigh). This is caused by low packing scale, as measured by the L2 stretch. Renders generatedusing our method (d) more faithfully preserve the details of the frieze and closely approach thequality of renders generated using Xatlas (b), an offline packing method. All methods use a 1KÃ 1K atlas.by our method. We compare our runtimes and stretch against interactive packing alternatives as well asthe industry-standard Xatlas library [40], a highly optimized implementation of the standard Tetris offlinepacking algorithm [19]. Relative to the best prior interactive method, TABI narrows the gap in atlas stretch,compared to offline methods, by 48% on average. While TABI is slower than methods like FastAtlas, itremains interactive (average runtime 5.11ms, runtime for atlases with over 10,000 charts 10.79ms). TABIruntimes are 464 times faster on average than those of the fastest offline alternative.31.3 Related WorkAtlas Generation. Atlas generation for storing surface signals, such as textures or normal maps, is a well-researched problem [34]. Atlassing typically consists of three steps, the first two of which are sometimesintertwined [20, 35]: segmenting input surfaces into charts [17, 42]; parameterizing these charts into 2D[19, 33]; and finally, packing the parameterized 2D charts into an atlas [16, 19]. Our work focuses on thefinal packing step of this process, and makes no assumptions about the source, size, shape or count of 2Dcharts in each input.Atlas Packing. Packing 2D charts into atlases as tightly as possible is a well-researched NP-hard prob-lem; see [12] for a recent survey. Traditional packing algorithms seek near-optimal solutions and solve forexact polygon placement using tools such as the no-fit polygon [4], then run heuristic search algorithmsto evaluate many different placement orders. These methods are computationally infeasible for computergraphics applications [39], where typical inputs can consist of hundreds or thousands of arbitrarily-shapedcharts.Algorithms for practical graphics applications typically first sort charts in decreasing order of size, thenplace them into the atlas one at a time. Chameleon[16] approximates charts by their bounding rectangles,folds them into in rows, places rows into the atlas in alternating directions, and pushes each row up againstthe row above it (Fig 2.1b). Chameleon can be parallelized and is amenable to GPU implementation ([37],Sec. 2.1), allowing for interactive performance.The âTetrisâ packing method of [19] and its extensions [28, 31, 42] represent both the charts and the cur-rent packing as rasterized images, and search for valid (non-overlapping) positions and orientations withinthe rasterized atlas. The best candidate position for each chart is selected according to a heuristic scorefunction such as wasted space [19, 31, 42] or distance to the bottom-left corner [41]. Xatlas [40] is a highlyoptimized implementation of Tetris packing that is widely used in industry; it supports both a slower âbruteforceâ packing (Fig 1.1a) and a faster pseudo-randomized ârandomâ one (Fig 1.1b) which differ in the num-ber of candidate positions tested for each chart. While much slower than CPU or GPU Chameleon, thesemethods require significantly less downscaling and are widely used for applications where runtime is a lesserconcern (e.g. static input chart sets for which packing can be precomputed once). Tetris packing methodsare inherently sequential; each inserted chartâs location depends on the final locations of all prior charts,and thus they are not amenable to parallelization [37]. We aim for interactive runtimes orders of magnitudefaster than those of Xatlas, while approaching its output quality (Fig 1.1e, Sec. 4).Learning-Based Packing. Recent works have explored learning-based approaches to packing [10, 38,39], and have shown packing efficiency improvements (lower stretch) over Tetris packing approaches. [10]train a reinforcement learning policy to predict the insertion order of charts into the atlas, while [39] learnto predict both chart order and approximate chart location and orientation. [38] propose to learn packing byexample by modeling the output distribution of a âteacherâ packing algorithm. However, these methods areeven slower than Tetris-type approaches, making them unsuitable for interactive applications. For instance,[39] requires several minutes to pack their largest chart set (784 charts).Fixed Size Atlases and Gutters. Most atlassing applications target a fixed atlas size; however, mostparameterization methods operate in a continuous space. During the packing step, the charts they produce4(b) Ours (overlap texels: 0;overlap texels incl. gutters: 0;runtime: 1 ms)(a) UVPackMaster (overlap texels: 11,975;overlap texels incl. gutters: 12,036;runtime: 83 ms)44 chartsFigure 1.3: The GPU UVPackMaster packer [7] outputs have severe inter-chart overlaps on even rel-atively simple (a) inputs (overlap size measured as number of texels covered by two or morecharts). Our outputs are overlap-free and our method is 60 times faster.must be scaled to fit the target atlas. A naive approach would be to compute either a continuous-spacepacking or a very high-resolution raster one, then scale the packed atlas to fit into the fixed size target atlas.When using a texture atlas, however, most applications use bilinear or other sampling strategies that requirethe charts in the atlas to have fixed width (1px or more) empty gutters around them [29] (i.e. a distancebetween charts of 2px or more). Uniformly scaling an existing packing cannot guarantee that each chart hasthe required gutters around it, as scaling and rounding may produce inter-chart gaps narrower than doublethe gutter width. Scaling can also cause charts to overlap when two previously disjoint chart boundarypoints are quantized to the same location. Strictly avoiding overlaps and preserving gutters requires scalingcharts by a pre-determined factor first, then packing the scaled charts in a raster space whose dimensionsmatch the target atlas size. However, using an unnecessarily low scale factor is undesirable as it may reducethe quality of the signal stored. Practical atlassing methods [28, 31, 37] therefore search for the scalingfactor that minimizes downscaling by packing atlases with different factors and selecting the largest one thatproduces a valid output. We adopt this framework for evaluating both our method and alternative algorithms.We enforce 1px gutters for both our and alternative methods in all experiments.Parallel GPU Packing Methods. UVPackMaster [7] is a closed-source commercial GPU-based packer.While not interactive, it often improves both runtime and stretch versus Xatlas. Unfortunately, it is notrobust, and fails to terminate on 4% of inputs in our dataset (including some of the largest ones). Worse,it introduces significant inter-chart overlaps on 7.5% of inputs (Fig. 1.3a). Finally, while its interface al-lows gutter specification, in our experiments their outputs did not satisfy gutter requirements on over 90%of inputs. TABI robustly processes all inputs in our extensive dataset (Sec 4) and strictly satisfies gutterspecifications.5Several packing strategies achieve real-time performance by leveraging GPU parallelism. Some [14, 15,26] make strict assumptions on the shape of the charts being packed (e.g. individual triangles or rectangularpatches), making them unsuitable for our setting. Recent methods [27, 37] support general chart shapes byoperating on the bounding boxes of the input charts. [27] rounds boxes to power-of-two sizes and packs themusing a superblock-based scheme. FastAtlas [37] significantly outperforms [27] in terms of packing quality.It parallelizes the fold-and-push packing strategy of Chameleon [16] and adapts it to the GPU, with onekey modification: a prefix sum-based relaxation of the previously sequential folding step that significantlyspeeds up computation by allowing greater parallelism at the cost of increased downscaling (Fig. 2.1a).While fast, the stretch introduced by FastAtlas is significantly worse than that of offline alternatives.TABI follows this overall fold-and-push framework [16, 37] but makes major modifications that signifi-cantly reduce stretch (Fig 1.1, 1.2, Sec 4) while retaining interactive performance.Interactive Packing Applications. Interactive packing methods are useful for many applications in digitalcontent creation and real-time rendering. These include surface painting [6, 16], procedural texturing [5, 8],light mapping [1, 25], virtual texturing systems [3], shadow mapping [9], and texture space shading (TSS)[2]. Both [27] and [37] specifically target TSS as the application domain. For digital content creationapplications, the main goal of interactive packing is to provide artists with immediate feedback. When thisis not possible, it is often necessary to resort to offline packing at the cost of artist productivity [36].General Packing Applications. Shape packing into containers is also relevant to applications outside ofcomputer graphics, such as logistics and manufacturing. Unlike atlas packing, which operates on 2D charts,algorithms targeting these applications often pack 3D shapes and may consider physical realizability of thepacking placement in addition to non-overlap constraints [13, 23, 43]. 2D packing methods designed forthese settings (e.g. [21]) share similarities with atlas packing algorithms but do not allow downscaling, asinput shapes correspond to physical parts to be cut out of sheets or panels. Therefore, they can be viewed assolving a subproblem of atlas packing, which searches for the optimal scale factor in addition to the positionand orientation. Our interactive method supports downscaling when required to fit charts in the atlas, andcan also pack at a fixed scale by adjusting the search range.6Chapter 2Fold-and-Push FrameworkAchieving interactive packing performance on typical atlases requires a parallel, GPU based method. Wetherefore develop our TABI packing algorithm by extending the fold-and-push framework [16, 37] (Fig 2.1).This parallelizable framework has been adapted to the GPU and outperforms prior parallel methods in termsof quality; it is thus a natural starting point for our method. Before proceeding to describe our method webriefly review packing methods that operate by folding and pushing charts (Fig. 2.1, Sec 2.1) and analysetheir shortcomings (Sec 2.2).2.1 Chameleon and FastAtlasThe Chameleon packing algorithm operates on chartsâ bounding boxes. Boxes are rotated by 90â¦ if neces-sary so that they are taller than they are wide, and then sorted in decreasing height order to ensure that larger,and hence harder-to-pack charts, are packed first. Charts are packed into the atlas in two steps - folding andpushing. In the folding step, sorted boxes are divided into rows which fit in the atlas width. Rows are thenplaced into the atlas from top to bottom, alternating between left-to-right and right-to-left directions, to tryto prevent tall charts from bunching on one side of the atlas. In the pushing step, the boxes in each row arepushed up as far as possible against previous rows.Vining et al. [37] adapt the packing strategy of Chameleon (Fig 2.1, right) to the GPU by parallelizingeach step, and leveraging GPU parallelism to search for the optimal downscaling factor: folding and pushingare simultaneously performed over a range of candidate discrete scale factors S, and the largest S wherepacking succeeds without overflowing the atlas is chosen. They then introduce FastAtlas, an even fastermethod (Fig 2.1, left). Unlike Chameleon, FastAtlas alternates between one left-to-right row and two right-to-left rows as a domain-specific heuristic targeting texture-space shading. FastAtlas parallelizes the foldingstep via approximation using a parallel prefix sum. After prefix-sum folding, the final chart in each rowmay overflow the atlas width, and all charts must undergo an intermediate scaling-down to bring rows backwithin the atlas width. This intermediate downscaling negatively impacts achieved packing scale, both onits own (Fig. 2.1b) and because it requires FastAtlas to maintain additional horizontal space between chartscompared to Chameleon in order to avoid gutter overlaps after downscaling.7S = 24/64S = 25/64FastAtlasoutput:S = 24/64stretch:3.27(a) Folded (b) Scaled & PushedS = 24/64S = 25/64Chameleon (GPU)(c) Folded (d) Pushedoutput:S = 24/64stretch:3.05Figure 2.1: FastAtlas (left) and GPU Chameleon (right) outputs on the input shown in Fig. 3.1. Bothmethods operate on chart bounding boxes. FastAtlas folds rows using a prefix-sum based re-laxation which causes them to initially overflow, and alternates one left-starting row with tworight-starting rows (a); it must further downscale charts prior to pushing up in order to fit rows inthe atlas (b). Chameleon folds rows sequentially and alternates between one left-starting row andone right-starting row (c), then pushes rows up (d). Both methods generate packings with lowtightness (note the large horizontal and vertical gaps between charts) and balance (note emptyspace in bottom right in Chameleonâs output).2.2 FastAtlas and Chameleon ChallengesWhile interactive, current fold-and-push methods produce notably lower quality at-lases than Tetris-based approaches, suggesting room for improvement. Analysingthe outputs of fold-and-push approaches we observe that this sub-par performanceis driven by two major sources of wasted space. First, since these methods are de-signed to operate on the bounding boxes of the charts, they waste the space betweenthe charts and their bounding boxes (pointed to by arrows in inset); leading to un-desirable horizontal and vertical gaps between packed charts. We refer to this property as lack of tightness.Second, packings generated by fold-and-push methods are often imbalanced: charts on one side of the pack-ing often reach the bottom of the atlas much earlier than those on the other, leaving a significant portion ofthe atlas unoccupied below the âshorterâ side (highlighted by orange ellipse in inset).These observations motivate our packing strategy that reduces wasted space by improving both atlastightness and balance while maintaining interactive performance.8Chapter 3AlgorithmOur method follows the general fold-and-push framework that balances quality against speed. We improveatlas quality by addressing the tightness (Sec 3.1) and imbalance (Sec 3.2) challenges identified above. Weuse Chameleon-like row by row packing for smaller chart sets (Sec 3.1-Sec.3.3); and use a combinationof row-by-row and prefix-sum based parallel packing for larger chart-sets (Sec 3.4). This hybrid approachallows maintaining interactive performance across all inputs. Our input consists of a set of 2D charts to bepacked, and the fixed dimensions of the atlas. We assume that charts are provided as polygonal meshes withcoordinates defined in texel space (i.e. in the same units as the atlas dimensions). Our algorithm outputs per-chart scales and rigid transformations (translation, rotation, and/or reflection) that arrange the charts insidethe atlas with no overlaps between the charts or their gutters. See supplementary for method pseudocode,parameter values, and details.3.1 Improving Packing TightnessImproving packing tightness requires compacting horizontal gaps between charts during the folding step,and vertical gaps during the pushing step. Since the axis-aligned bounding boxes are already tightlypacked, our tightening employs tighter chart bounding shapes that can be computed and evaluated effi-ciently (Sec. 3.1.1). We use these proxies to compact individual horizontal gaps in parallel for all charts(Fig 3.1b) and use a similarly parallel approach to close vertical gaps during pushing (Fig 3.1d).3.1.1 Chart ProxiesEvaluating gaps directly between polygonal charts is too expensive for our runtime budget. Raster-spacecomputation (a` la Tetris packing) would require rasterizing and storing charts at every candidate scale factorwhich in turn would necessitate a prohibitive amount of texture memory. We avoid both pitfalls by byoperating on tight bounding proxies of chart shapes. We employ two such proxies in our method.Our first proxy is computed by dividing the chart into intervals of equalwidth along each of the x and y axes, then computing local AABBs for theâsliceâ of the chart inside each interval; this can be efficiently done in parallelper-chart by having each vertex and edge independently assign itself to one or9(a) Ordered Array of AABBsScale 1:NMultiscale Parallel Folding & Pushing(e) Pick Best Across All Scales(b) Horizontal Tightening (c) Balanced Folding(d) TightPushingScale 56/64Scale 33/64Tightened Array of ChartsScale 61/64Figure 3.1: TABI overview. (a) Charts placed in descending height order. They are then more tightlypacked horizontally using per-chart proxy shapes (Sec 3.1.2). We compute a target chart scale byevaluating a discrete range of possibilities in parallel. For each candidate scale, charts are scaledand folded into rows using balanced folding (Sec. 3.2). Charts are then tightly pushed up, onerow at a time, using per-chart proxies (Sec. 3.1.3). Finally, we choose the largest scale that doesnot overflow the atlas.more intervals along each axis. The local AABBs along the x-axis effectively form a piecewise constantapproximation of the chartâs top and bottom boundaries, and those along the y-axis do the same for the leftand right boundaries. After computing both sets of local AABBs, we then merge them to further refine ourapproximation of the four boundaries for each chart (see inset example, with 2 AABBs per axis). The localAABB proxies capture concavities and void spaces [21] in charts. The more local AABBs are allocated, thebetter this approximation, enabling a tradeoff between quality and performance.We augment the local AABBs by using a second proxy - the oriented bounding boxes(OBBs) for each charts (inset). While finding an exact OBB is too expensive for our interactivebudget, we can obtain an approximate OBB by testing a fixed set of rotations in parallel andselecting the one that results in the minimal area box.Optimizing Chart Orientations. The amount of horizontal and vertical compacting that can be achievedbetween two chart proxies depends on the relative orientation (i.e. horizontal or vertical reflection) of theunderlying charts. It would be prohibitively expensive to globally optimize the orientations of all pairsof charts, since each chartâs choice of orientation affects both its neighbours. Instead, we independentlyreflectverti-callyTop < bottom area? Left < right area?reflecthorizo-ntallyNoNocompute favorable chart orientations, designed toallow for maximal compatibility between theirproxies. Recalling that charts are lined up from leftto right prior to folding the line, we aim to maxi-mize empty area along the bottom of the chart, tomaximize how far the next row can move up in thepushing step; and along the right of the chart, to maximize how far the next chart can move horizontallytoward this one. We use our local AABB proxy, which captures the shape of chartsâ boundaries well, to10determine whether reflection is necessary to satisfy these criteria. We observe that the area between theseboundaries and the edges of the chartâs enclosing AABB approximates the empty area along the four sidesof the chart. Thus, we first compute the approximate empty area on the top and bottom of the chart, andreflect the chart vertically if necessary to move the greater empty area to the bottom. We then consider theempty area on the left and right in a similar fashion to determine whether to reflect the chart horizontally.3.1.2 Compacting Horizontal GapsThe original folding step operates on a line of charts whose AABBs are side-by-side (aligned at the top;Fig. 3.1, top row). This line is guaranteed to be overlap-free, but is not tight. Starting from these ini-tial positions, we can compact the horizontal gaps within the line by using our proxies and moving eachpair of adjacent charts closer together by the maximum distance possible before they would intersect (Fig.3.1b.). This compacting distance can be calculated for each pair of charts in parallel. We use both proxiesin tandem to achieve the best packing results by computing compactingdistances from both proxies (indicated by arrows in the inset), and usingthe larger of the two compacting distances. To compute the compactingdistance between a pair of local AABB proxies, we iterate over the firstchartâs right boundary and the second chartâs left boundary and take theminimum distance between the piecewise constant values. We apply theSeparating Axis Theorem [32] to find the horizontal distance between theOBBs.3.1.3 Compacting Vertical GapsOur proxies also allow us to compact vertical gaps between rows during the pushing step (Fig. 3.1d). Atthis point, charts have known horizontal locations in the atlas, but their vertical locations are still unknown.Like FastAtlas, our parallelized pushing method operates using an advancing frontline â an array storingan entry for each column of texels in the atlas, representing the packing height at that point. In FastAtlas,this frontline is updated one row at a time; each box in the first row writes its height to the frontline, andsubsequent rows then set their vertical offset to the smallest value that prevents them from overwritingthe frontline and write that value plus their height to the frontline texels they cover. We observe that thisfrontline does not require charts to be represented by AABBs. Accordingly, we can test whichever of the topboundaries of the proxies most tightly bounds the chart to find a tight vertical placement against the existingfrontline. In practice, for each x coordinate, this is whichever of the two proxies has the largest y coordinatealong its top edge. We then write the tightest fitting bottom boundary of the two proxies into the frontlineafter each update (whichever of the two proxies has the smallest y coordinate for each x coordinate on thebottom edge.)Pushing all charts up independently, however, can introduce inter-chart overlaps (inset, left). This isbecause the horizontal compacting distances we computed are only exact if chart pairs remain in their initialrelative positions (i.e. are aligned at the top); if one chart moves up after horizontal compacting, theymay now intersect (inset, middle). In some cases, one chart in the pair can still move up freely without11Before pushing After pushing After correctionrisk of intersecting the other; in other cases, neither chart canmove up freely without potential intersection. When com-pacting charts horizontally we identify all adjacent chart pairswhere moving one chart up relative to the other can triggerintersection and record which chartâs movement can triggerintersection. This depends on which proxy provided the finalcompacting distance and thus the final non-overlapping posi-tions; if the local AABB proxy was used, one or both charts can potentially trigger intersection if movedup, while if the OBB proxy was used, at most one chart in each pair can. During the pushing stage we firstallow all charts in a row to push all the way to the frontline. For each chart whose movement can triggerintersection, we check if it moved up relative to the neighbor it can potentially intersect, and move it downto match the neighborâs vertical position. We repeat this process until all such chart pairs are verticallyaligned.3.2 Balanced FoldingWe propose a novel folding method designed to avoid imbalance. We observe that imbalance in the outputsof our baseline methods occurs due to their use of static row alternation rules that fail to equalize accumu-lated chart heights on the two sides of the packing (Fig. 3.2a). We further observe that in many input chartsets, whether artist-created or algorithmically generated, the height of consecutive charts in our sorted linemay differ dramatically (see first and second charts in Fig. 3.2a); such rows introduce significant imbal-ance between the accumulated heights on the left and right. Our first observation suggests that producingbalanced packing, at a minimum, requires dynamically selecting whether chart rows are packed right-to-leftor left-to-right at each row (Fig. 3.2b). However, when chart heights are highly non-uniform within a row,even optimal selection of row directions may be insufficient to balance the packing (Fig. 3.2b). Generatingbalanced packings therefore requires both a more robust strategy for selecting row directions, and a way tohandle rows of highly non-uniform height, ones containing sharp jumps in chart height. We refer to thesesharp jumps in chart height as knees.Our key insight is that when these knees are present, folding the subsequent row(s) at the full atlaswidth independent of direction is sub-optimal as it will simply further increase the height on both sidesof the packing, preserving the imbalance. Instead, we exploit the fact that knees create deep indentations,or concavities, in the frontline, ones that can be effectively filled by shorter rows. Our method detectsthese knee concavities and folds subsequent rows at concavity width, effectively re-balancing the packingby filling the indentation with shorter rows, before continuing (Fig. 3.2c).Knee Concavity Computation. We define a height difference between consecutive charts in a rows as aknee if this difference is sufficiently large in both absolute terms and relative to the height of the taller chart.We restrict each row to have at most one knee, and if multiple are present, operate on the one with the largestheight difference. The concavity-facing edge of the taller chartâs AABB provides a conservative estimateof the concavityâs width (right edge if row is left-to-right, left edge if row is right-to-left). We refine thisestimate by drawing a horizontal line at the height of the frontline texel adjacent to the current knee position,12(a) Simple alternatingrows (stretch: 1.52)(b) Only optimizing rowdirections (stretch: 1.39)(c) Our knee boundedrows (stretch: 1.21)Figure 3.2: Imbalanced packings are caused by a failure to equalize accumulated chart heights on thetwo sides of the packing. Simply alternating rows (left) immediately produces an unbalancedpacking. Optimally selecting row directions to equalize height distribution (center) improvesbalance, but may still lead to wasted space. Our knee-based solution (right) handles large within-row changes in chart height, resulting in an efficient and balanced packing.and updating the knee position to its closest intersection with the frontline. This process is implemented inparallel using atomic operations.Placing Rows. Since rows are pushed up sequentially, we delay the choice of a rowâs direction, foldingwidth, and other per-row options until after all previous rows have been folded and pushed. This enables ourmethod to read the current state of the packing and make the locally optimal decision, avoiding the pitfallsof prior static approaches.Fold at atlas widthLeft-to-rightFold at atlas widthRight-to-leftFold at kneeLeft-to-rightFold at kneeRight-to-leftWe consider the following placement configurations for each row.First, the row may be placed left-to-right or right-to-left. Second, the rowmay be folded at the atlas width or at the position of a knee in a previousrow (if it exists, and all rows between the knee and current row were alsofolded into the knee concavity). Lastly, we also consider folding eachrow with and without horizontal compacting. While the core benefit ofhorizontal compacting is its ability to fit more charts into each row, if itdoes not achieve this goal for a particular row, disabling it may be a betterchoice to enable charts to push up freely without interlock and leave morespace between charts for future rows to push up into. In total, we consider8 possible configurations if a previous knee exists, and 4 otherwise. Dueto chartsâ irregular shapes, it is challenging to predict which configurationwill yield the best outcome after folding and pushing. Instead, we directlyevaluate folding and pushing for each potential configuration. We thenuse the following process to select the âbestâ configuration among them.First, we compare pairs of configurations that differ only by whether horizontal compacting is enabled;13if horizontal compacting increases the number of charts that can be folded into the row, we discard the otherconfiguration. If a valid previous knee exists, we compare the remaining configurations in two separategroups. We observe that packing fails when any point on the frontline exceeds the atlas height after pushing;in other words, the smaller the maximum height of the frontline, the further the packing is from failure. Forall configurations that are folded at the atlas width, we compute the maximum height over the entire frontlineand choose the configuration that minimizes this value. For configurations folded at a knee position, we onlycompare the maximal heights inside the knee as the remaining texel heights are identical. We finally comparethe best âkneeâ configuration to the best ânon-kneeâ configuration using the maximum height over the wholefrontline. Intuitively, folding at the knee permits fewer charts to fit in the current row, but is desirable if itimproves packing balance. We therefore accept the best âkneeâ configuration if its maximum height is atleast marginally smaller than the best ânon-kneeâ configuration.3.3 Algorithm SummaryWe can now summarize our TABI packing algorithm as follows. The initial steps of our algorithm followChameleon: we compute the AABBs of all charts, rotate the boxes to be taller than they are wide, and sortcharts by AABB height. This is followed by two parallel passes which compute our shape approximationsfor each chart and determine each chartâs orientation. We then compute horizontal compacting distancesbetween each pair of adjacent charts in parallel. We simultaneously scale and pack charts at a range ofdiscrete scale factors, and return the largest scale and packing that succeed. Packing proceeds row byrow; each row evaluates folding and pushing for different placement configurations based on our kneefolding strategy, and commits the best result based on the remaining height below the frontline. Our packingprocedure can be implemented as a single GPU kernel with one work group per scale factor in order to takeadvantage of barrier synchronization within a work group (refer to Algorithms 3 and 4 for pseudocode).We implement all steps of our method using OpenGL compute shaders for ease of integration with theexisting pipeline of [37]. However, our algorithm does not depend on any OpenGL-specific features orvendor-specific hardware, and can be realized in other environments such as Vulkan or CUDA.143.4 Performance OptimizationFolding and pushing one row at a time is the primary runtime bottleneck of our method as input size in-creases. We observe that the initial rows, consisting of the largest charts, typically have the greatest impacton packing quality, and are likely to have the most knees. Furthermore, the amount of downscaling caused byusing prefix-sum decreases as chart size gets smaller. Thus the benefits of sequential folding diminish oncechart size becomes sufficiently small relative to atlas size. Therefore, for large chart sets (Fig 4.5), whereby definition, many charts are tiny, the runtime cost of sequential folding outweighs its benefit in termsof quality. We therefore transition between our high-quality sequential folding, and a modified version ofprefix sum folding which can fold all charts in a single parallel pass.We sequentially fold and push the first N rows, dynamically selecting the best placement for each.Then, we fold all remaining charts in parallel using an extension of the prefix sum approximation proposedby FastAtlas. Specifically, we apply our horizontal compacting to the prefix-sum input as follows. Weinitialize element i of the prefix sum array to the AABB width of chart i minus the horizontal distance tochart i+ 1; in other words, we now compute the prefix sum of the horizontal offsets between charts. Afterintermediate downscaling of the prefix sum-folded rows, we insert them into the atlas using the same fixeddirection alternation as FastAtlas and push them up. Unlike FastAtlas, in this hybrid method, the scaling(product of S and intermediate scale) may slightly differ between the first N and the remaining rows. Thus,we compute the average scaling factor weighted by chart area for each candidate scale factor S, and choosethe one that maximizes this value without overflowing the atlas. We allow N to vary per input by switchingto prefix sum folding when no more knees are detected and the height of the tallest chart in the row decreasesbelow a threshold topt , set to 1% of atlas height. Past this point, charts are small enough for intermediatedownscaling to be negligible and the outcome of pushing is very similar regardless of row direction chosen.In practice, small charts often account for a significant fraction of large input chart sets, and our optimizationenables us to process these charts much more quickly with negligible impact on packing scale.15Chapter 4Results and ValidationWe evaluate our method by packing 8,386 chart sets into square atlases of two different sizes each, for atotal of 16,772 atlases. Our input chart sets include two different types of data, reflecting the typical settingswhere interactive atlassing would be used: charts generated via UV unwrapping of 3D models (sourced from[18, 22, 39]), and texture-space shading (TSS) charts generated from camera paths through complex scenes[37]. Our chart sets range in size from 2 to 44,389 charts (30% have under 1,000 charts, 50% have 1,000to 5,000 charts, 10% have 5,000 to 10,000 charts, and 10% have over 10,000 charts). Figs. 1.1, 3.1, 4.1-4.5show representative examples of atlases generated by our method and include atlases containing between20 and 32,818 charts, Figs. 3.1 and 4.5 respectively. Runtime and packing quality statistics are reported inTab. 4.1, Tab. 4.2, and Fig. 4.3.Experimental Setup. Our experimental settings reflect typical atlas generation scenarios in computer graph-ics where atlas sizes are square powers of 2 (due to support for mipmapping) and are similar to those of thestate of the art methods in this space [37, 40]. We pack our UV-unwrapped charts (referred to as UV chartsbelow) at two atlas sizes: the âfullâ size, which corresponds to the size of the original texture (manuallypacked by artists), and half of this full size. For the dataset of [39], which does not have associated textures,we define the input chart size by scaling the original [0,1] UV coordinates to a 1KÃ1K range, and use theseMean packing time (ms) â Packing time ratioXatlas Cham- Xatlas Fast- Cham-Xatlas (brute Fast- eleon (random) Atlas eleon# charts # inputs (random) force) Atlas (GPU) Ours to ours to ours to oursâ¤ 100 1,726 633.51 25,189.01 0.62 0.60 1.22 492.70 0.54 0.52101-500 2,338 1,324.42 70,520.82 0.67 0.84 2.13 613.45 0.33 0.40501-1,000 1,640 1,749.25 66,288.21 0.70 1.39 3.58 475.74 0.20 0.391,001-5,000 8,508 2,131.15 78,392.68 0.85 2.76 5.31 402.57 0.16 0.515,001-10,000 814 3,475.95 80,130.26 1.45 8.34 10.68 323.28 0.14 0.77> 10,000 1,746 6,298.64 72,350.89 1.69 18.12 10.79 589.70 0.16 1.66All 16,772 2,326.34 70,091.95 0.90 4.01 5.11 464.03 0.23 0.62Table 4.1: Runtime comparison of our method against offline (Xatlas [40]) and interactive (FastAtlas[37], GPU Chameleon [16]) alternatives across our full dataset. The last 3 columns show theaverage ratios between alternatives and our runtimes. Our method is two orders of magnitudefaster than the fastest offline alternative (Xatlas random), and though slower than FastAtlas andChameleon, it remains interactive.16220 charts, full size (1K) atlas76 charts, full size (1K) atlas81 charts, half size (512) atlasstretch: 2.14runtime: 0.6 ms(m) FastAtlasstretch: 2.13runtime: 0.6 ms(n) Chameleon (GPU)stretch: 1.83runtime: 1.4 ms(o) Oursstretch: 1.28runtime: 0.6 ms(c) FastAtlasstretch: 1.12runtime: 0.7 ms(d) Chameleon (GPU)stretch: 1.00runtime: 1.7 ms(e) Oursstretch: 1.81runtime: 354.2 ms(l) Xatlas (random)stretch: 1.00runtime: 768.8 ms(b) Xatlas (random)stretch: 1.00runtime: 450.1 ms(g) Xatlas (random)stretch: 1.81runtime: 1,782.8 ms(k) Xatlas (brute force)stretch: 1.00runtime: 3,384.4 ms(a) Xatlas (brute force)stretch: 1.00runtime: 3,686.5 ms(f) Xatlas (brute force)stretch: 1.27runtime: 0.6 ms(h) FastAtlasstretch: 1.33runtime: 0.6 ms(i) Chameleon (GPU)stretch: 1.00runtime: 1.6 ms(j) OursFigure 4.1: Representative comparisons of our outputs against prior offline (Xatlas [40]) and interac-tive (FastAtlas [37], Chameleon [16]) alternatives on chart sets originating from UV unwrapping.We achieve L2 stretch approaching that of offline methods, significantly outperforming FastAtlasand Chameleon, while maintaining interactive runtimes two orders of magnitude faster than theoffline methods.17stretch: 1.00runtime: 2,489.7 ms(b) Xatlas (random)(g) Xatlas (random)stretch: 2.36runtime: 593.9 ms(l) Xatlas (random)stretch: 1.16runtime: 1,792.9 msstretch: 1.33runtime: 0.8 msstretch: 1.25runtime: 2.3 ms(c) FastAtlas (d) Chameleon (GPU) (e) Oursstretch: 1.00runtime: 39,431.4 msstretch: 1.03runtime: 6.4 ms1,572 charts, 2K atlas(h) FastAtlas (i) Chameleon (GPU) (j) Oursstretch: 2.80runtime: 0.7 msstretch: 2.62runtime: 0.9 msstretch: 2.36runtime: 2.3 ms360 charts, 1K atlas(m) FastAtlas (n) Chameleon (GPU) (o) Oursstretch: 1.48runtime: 0.7 msstretch: 1.41runtime: 1.7 ms(a) Xatlas (brute force)(f) Xatlas (brute force)stretch: 2.41runtime: 3,610.8 ms(k) Xatlas (brute force)stretch: 1.12runtime: 94,860.9 msstretch: 1.17runtime: 4.4 ms1,093 charts, 2K atlasFigure 4.2: Representative comparisons of our outputs against prior offline (Xatlas [40]) and interac-tive (FastAtlas [37], Chameleon [16]) alternatives on TSS sourced inputs. Our method achievesL2 stretch approaching that of offline methods, outperforming FastAtlas and Chameleon, whilemaintaining interactive runtimes several orders of magnitude faster than those of offline alterna-tives.18Mean stretch â Stretch improvementXatlas Cham- vs.Xatlas (brute eleon vs. Cham-# charts # inputs (random) force) FastAtlas (GPU) Ours FastAtlas eleonâ¤ 100 1,726 1.65 1.62 1.83 1.78 1.70 53% 43%101-500 2,338 1.70 1.67 2.12 2.03 1.88 53% 41%501-1,000 1,640 1.76 1.72 2.42 2.38 2.01 56% 52%1,001-5,000 8,508 1.76 1.76 2.52 2.48 2.12 50% 48%5,001-10,000 814 2.00 2.42 3.07 2.93 2.48 53% 47%> 10,000 1,746 3.10 4.10 3.99 3.68 3.14 62% 55%All 16,772 1.89 2.00 2.57 2.48 2.16 53% 48%Table 4.2: Stretch comparison of our method against Xatlas [40] and interactive alternatives (FastAtlas[37] and Chameleon [16]) across our dataset. Our outputs have significantly lower stretch thanthose produced by interactive alternatives. The last two columns show the amount by which ourmethod closes the stretch gap between interactive alternatives and the best method per-input.dimensions as the âfullâ size; we then set half size to 512Ã512. The input size of our TSS charts is basedon a 1920Ã 1080 screen resolution [37]; we pack these charts at two different atlas sizes, 1KÃ 1K and2KÃ2K. These sizes reflect real-life settings where downscaling may often be unavoidable, making pack-ing non-trivial. We pre-rotate the UV charts to align their tight bounding boxes with the major axes priorto packing, a common optimization that improves packing quality. For TSS applications, rotating charts byangles which are not multiples of 90â¦ changes the sampling patterns of the chart content, which negativelyimpacts rendering quality and increases visual error; thus, we do not pre-rotate TSS data. We configureTABI to leave 1-pixel gutters around charts to render borders for bilinear sampling, and no spacing alongthe 4 edges of the atlas, where âclampedâ texture sampling avoids the need for gutters. To find the bestdownscaling factor, we follow FastAtlas and test 64 scales ranging from 164 to6464 = 1 (see Figs 2.1, 3.1).See supplementary for additional details.Robustness. TABI successfully generated atlases on all the inputs tested and strictly satisfies the specifiedgutter sizes. As noted in Sec 1.3, and further detailed in the supplementary, this is not the case for alternativessuch as UVPackMaster [7].Measuring Downscaling. Similar to [37], we evaluate the quality of generated packings by computingthe L2 stretch [30] between the triangles in the packed and input charts. The L2 stretch reflects the av-erage amount that charts were downscaled during packing. A stretch of 1 corresponds to the ideal zero-downscaling case, where all charts are packed successfully at exactly their input sizes; increased downscal-ing results in higher stretch. Tab 4.2 reports the average stretch across all TABI outputs.Runtime. TABI takes 5.1 milliseconds on average to pack the inputs tested (Tab 4.1). Our average run-times remain under 11 milliseconds even for atlases with over 10,000 charts, enabling interactive (60 fps)performance. Only 1% of our inputs require over 15 milliseconds to pack. Runtimes range from under amillisecond for smaller atlases, to 24 milliseconds on our most time consuming input. In addition to chartset size, the factors that impact packing time include the number of rows in the output atlas and the numberof knees. Roughly 60% of the time is spent folding and pushing charts, 20% is spent computing the tight19Figure 4.3: Plot of stretch versus packing time (averages across our dataset) of our method comparedto prior interactive and offline alternatives for different chart set sizes. In every size interval, ourmethod (green) shows a significant decrease in stretch relative to prior interactive methods andremains at least 2 orders of magnitude faster than the closest offline alternative.approximations (Sec 3.1.1), and the rest is split roughly evenly between other parts of the method. All timescomputed on an AMD Ryzen 7 1800X CPU (32 GB RAM) and an NVIDIA GeForce RTX 4090.Comparisons. We compare our method both against existing packing methods capable of interactive per-formance, and against existing methods for offline packing. The latter can be seen as a reference baselineand a proxy for the best possibly achievable packing stretch. We compare to FastAtlas [37], the currentstate-of-the-art in real-time atlassing. We also compare to our GPU implementation of Chameleon [16],whose packing approach inspired the parallelized FastAtlas variation (Fig 2.1). We use Xatlas [40], anindustry-standard implementation of the Tetris packing algorithm (Section 1.3) as our offline baseline. Weinclude two variants of Xatlas; Xatlas ârandomâ is the libraryâs default setting and optimizes the searchfor candidate chart positions using randomization, while Xatlas âbrute forceâ is intended to be slower butproduce the best possible results (in our experiments the âbrute forceâ method does indeed outperform theârandomâ on smaller chart sets, but seems to perform less well on larger ones). We use the same experimentsettings described above for all methods we compare against (pre-rotate UV charts to align tight boxes withaxes and use the same gutter settings as for TABI; allow all methods to rotate/reflect charts by multiples of90â¦ only, etc). For a fair comparison, all methods search over the same set of 64 discrete scale factors to findthe maximum scale at which packing succeeds. Since Xatlas does not provide built-in support for searchingfor the optimal downscaling factor, we follow prior work [28] and run a binary search over the 64 scales.As Tab. 4.1 shows, the Xatlas brute force method takes 43 seconds on average to atlas the inputs inour dataset; the most time consuming input takes it 32 minutes to atlas. Xatlas random takes 2 secondson average to generate atlases across our input set, which is much too slow for the applications we target;20(a) Balanced onlystretch: 3.30runtime: 1.3 ms(b) Tight only stretch: 3.29runtime: 2.8 ms(c) Oursstretch: 2.82runtime: 3.6 msFigure 4.4: Applying only balanced folding (Sec 3.2) (a) leaves empty space within chartsâ boundingboxes, while using only tightening (Sec 3.1) (b) results in an imbalanced packing with significantunused space in the bottom right. Our full method (c) combines both components to achieve thebest stretch.Mean packing time (ms) â Mean stretch âBalanced Tight Balanced Tight# charts # inputs only only Ours only only Oursâ¤ 100 1,726 0.66 0.96 1.22 1.74 1.72 1.70101-500 2,338 0.92 1.55 2.13 1.97 1.92 1.88501-1,000 1,640 1.26 2.59 3.58 2.19 2.17 2.011,001-5,000 8,508 2.05 3.96 5.31 2.31 2.24 2.125,001-10,000 814 5.02 7.93 10.68 2.70 2.63 2.48> 10,000 1,746 3.48 8.61 10.79 3.46 3.33 3.14All 16,772 1.97 3.86 5.11 2.33 2.27 2.16Table 4.3: Ablating our full method against using only balanced folding or only tightening across ourdataset (left: average packing time in milliseconds, right: average L2 stretch). By optimizing bothtightness and balance we achieve the best stretch.TABI is almost 500 times faster. While slower than FastAtlas and Chameleon, it remains interactive andproduces dramatically lower stretch packings across the inputs tested, narrowing the gap between interactiveand offline methods by approximately 50% on average.Ablations. We ablate our key algorithmic choices. Tab. 4.3 and Fig 4.4 validate our focus on improvingtightness and balance as key factors in improving stretch compared to FastAtlas and Chameleon. Tighteningthe atlases via horizontal and vertical compacting reduces average stretch from 2.48 (Chameleon) to 2.33;while improving balance without tightening reduces it to 2.27. TABI combines both components and de-creases the average to 2.16 (as a reference, the baseline Xatlas random average stretch is 1.89). This ablationsuggests that the two components have roughly similar impact on the output quality.We ablate our runtime optimization strategy (Sec 3.4) in Tab. 4.4, Fig. 4.5. We observed that for atlaseswith 1,000 or fewer charts, switching to the prefix sum folding strategy for small charts increases, rather thandecreases, runtime (due to the overhead of dispatching the additional prefix-sum shaders). Our experiments2132,818 charts, 2K atlas(a) FastAtlasstretch: 2.57runtime: 1.99 ms(b) Chameleon (GPU)stretch: 2.50runtime: 32.96 ms(c) topt = 5%stretch: 2.17runtime: 12.97 ms(d) topt = 2%stretch: 2.15runtime: 14.18 ms(f) Ours (topt = 1%)stretch: 2.101runtime: 14.90 ms(e) topt = 0%stretch: 2.099runtime: 34.96 msFigure 4.5: Ablation of different values of topt on an extremely large input. Higher values (c,d) providegreater performance improvements at the cost of higher stretch. A value of 0% (e), i.e. no prefixsum folding, yields the best packing scale but requires a much longer runtime. Our chosen setting(topt = 1%, f) significantly improves runtime with miniscule increase in stretch. At all values oftopt TABI produces better quality atlases than prior interactive alternatives (a, b).Mean packing time (ms) â Mean stretch âtopt topt topt topt topt topt topt topt# charts # inputs = 5% = 2% = 1% = 0% Ours = 5% = 2% = 1% = 0% Ours1,001-5,000 8,508 4.62 4.62 4.70 5.31 5.31 2.14 2.13 2.13 2.12 2.125,001-10,000 814 6.28 6.41 6.92 10.68 10.68 2.54 2.52 2.51 2.48 2.48> 10,000 1,746 9.31 9.72 10.79 20.60 10.79 3.20 3.17 3.14 3.01 3.14All 11,068 5.48 5.56 5.82 8.12 6.57 2.34 2.33 2.32 2.29 2.31Table 4.4: Ablating topt on inputs with 1,000 charts or more (left: average packing time in milliseconds,right: average L2 stretch between packed and input charts). Increasing topt reduces packing time,but increases stretch. Our method (topt = 0% for inputs with up to 10,000 charts and topt = 1% oth-erwise), minimally increases stretch compared to topt = 0% while achieving interactive runtimes.thus focus on atlases with over 1,000 charts. For these atlases, using the prefix sum folding strategy inSec 3.4 substantially decreases runtime, with larger values of topt leading to larger speed-up. Notably,even with no runtime optimization, our method takes 8.12 milliseconds on average on large (¿1,000 charts)atlases; though absent optimization performance is not interactive for atlases with over 10,000 charts, itremains two orders of magnitude faster than Xatlas. As expected, the earlier we switch from our method toprefix-sum folding, the more the stretch increases. Even with topt = 5%, however, our stretch is significantlylower than that of FastAtlas and Chameleon. Notably, the stretch of our unoptimized method (topt = 0%)is better than that of the offline Xatlas method (3.01 vs 3.1) â suggesting that for extra large inputs ourmethod may be a better overall alternative (faster and better). These ablations validate our strategy of onlyusing optimization for atlases with over 10,000 charts and using a small topt = 1% value as a way to achieveinteractive performance with minimal increase in stretch. See supplementary for additional comparisonsand ablations.22Chapter 5ConclusionWe introduce TABI, a new interactive texture atlas packing method that significantly improves on the perfor-mance of previous work. Our tight and balanced packings significantly reduce downscaling by decreasingwasted space around each chart and by better balancing chart placement within the atlas. Compared toprevious interactive methods, TABI reduces the gap in atlas stretch compared to offline atlases by 48% onaverage, making it suitable for a wide range of interactive applications where runtime is critical.Limitations and Future Work. TABI produces higher stretch atlases than Chameleon on only 2% ofinputs (and higher stretch atlases than FastAtlas on only 0.5% of inputs). Most of these are due to the inher-ently heuristic nature of our method; worst example shown in Fig 5.1ab. TABI performs worst compared tooffline methods on inputs where even the tight approximations we use only loosely approximate the chartshape, see e.g. Fig 5.1cd. An interesting area of future work is to find a way to pack charts into interiorvoids at interactive speed.23(a) Chameleon (GPU) stretch: 2.67(b) Oursstretch: 2.80(c) Xatlas (random)stretch: 2.05(d) Oursstretch: 2.13Figure 5.1: (a,b) Chameleon (a) and our TABI (b) packings on the input where TABI performs worstrelative to Chameleon across our dataset (even in this worst case, the difference in stretch isminor). (c,d) A representative example of inputs where Tetris type methods (c) outperform TABI(d) by placing small charts into interior voids.24Bibliography[1] J. Arvo et al. Backward ray tracing. In Proc. ACM SIGGRAPH 86 Courses, pages 259â263. â page 6[2] D. Baker and S. Hill. Rock-solid shading. SIGGRAPH Advances in Real-Time Rendering, 2012. âpage 6[3] S. Barrett. Sparse virtual texture memory. In Game Developerâs Conference, 2008. â page 6[4] J. A. Bennell and X. Song. A comprehensive and robust procedure for obtaining the nofit polygonusing minkowski sums. Computers & Operations Research, 35(1):267â281, 2008. â page 4[5] N. A. Carr and J. C. Hart. Meshed atlases for real-time procedural solid texturing. ACM Trans.Graph., 21(2):106â131, 2002. â page 6[6] N. A. Carr and J. C. Hart. Painting detail. In Proc. SIGGRAPH, page 845â852, 2004. â page 6[7] L. CzyzË. Uvpackmaster, 2025. URL https://uvpackmaster.com/. Version 3.4.1. â pages xi, 5, 19[8] D. DeBry, H. Goffin, C. Hecker, O. Quigley, S. Shodhan, and A. Willmott. Player-driven proceduraltexturing. In ACM SIGGRAPH 2007 sketches, pages 81âes. 2007. â page 6[9] H. Doghramachi. Tile-based omnidirectional shadows. In GPU Pro 360 Guide to Shadows, pages193â216. AK Peters/CRC Press, 2018. â page 6[10] J. Fang, Y. Rao, X. Zhao, and B. Du. A hybrid reinforcement learning algorithm for 2d irregularpacking problems. Mathematics, 11(2), 2023. â page 4[11] F. Gonza´lez and G. Patow. Continuity mapping for multi-chart textures. In ACM SIGGRAPH Asia2009 papers, pages 1â8. 2009. â page 2[12] B. Guo, Y. Zhang, J. Hu, J. Li, F. Wu, Q. Peng, and Q. Zhang. Two-dimensional irregular packingproblems: A review. Frontiers in Mechanical Engineering, Volume 8 - 2022, 2022. â page 4[13] F. Gzara, S. Elhedhli, and B. C. Yildiz. The pallet loading problem: Three-dimensional bin packingwith practical constraints. European Journal of Operational Research, 287(3):1062â1074, 2020. âpage 6[14] J. Hladky, H.-P. Seidel, and M. Steinberger. Tessellated shading streaming. Computer GraphicsForum, 38(4):171â182, 2019. â page 6[15] J. Hladky, H.-P. Seidel, and M. Steinberger. Snakebinning: Efficient temporally coherent trianglepacking for shading streaming. Computer Graphics Forum, 40(2):475â488, 2021. â page 6[16] T. Igarashi and D. Cosgrove. Adaptive unwrapping for interactive texture painting. In Proc. I3D,pages 209â216, 2001. â pages viii, ix, xi, xii, xiii, 2, 4, 6, 7, 16, 17, 18, 19, 20, 36, 37, 38, 39, 41, 4225[17] D. Julius, V. Kraevoy, and A. Sheffer. D-charts: Quasi-developable mesh segmentation. In ComputerGraphics Forum, volume 24, pages 581â590, 2005. â page 4[18] J. Knodt and X. Gao. Texture size reduction through symmetric overlap and texture carving. ACMTrans. Graph., 44(1), 2025. â pages 16, 35[19] B. Le´vy, S. Petitjean, N. Ray, and J. Maillot. Least squares conformal maps for automatic textureatlas generation. ACM Trans. Graph., 21(3):362â371, 2002. â pages 3, 4[20] M. Li, D. M. Kaufman, V. G. Kim, J. Solomon, and A. Sheffer. Optcuts: Joint optimization of surfacecuts and parameterization. ACM Trans. Graph, 37(6), 2018. â page 4[21] M. Limper, N. Vining, and A. Sheffer. Boxcutter: Atlas refinement for efficient packing via voidelimination. ACM Trans. Graph, 37(4), 2018. â pages 6, 10[22] S. Liu, Z. Ferguson, A. Jacobson, and Y. I. Gingold. Seamless: seam erasure and seam-awaredecoupling of shape from mesh resolution. ACM Trans. Graph., 36(6), 2017. â pages 16, 35[23] Y. Ma, Z. Chen, W. Hu, and W. Wang. Packing Irregular Objects in 3D Space via HybridOptimization. Computer Graphics Forum, 2018. â page 6[24] V. J. Milenkovic. Rotational polygon containment and minimum enclosure using only robust 2dconstructions. Computational Geometry, 13(1):3â19, 1999. â page 1[25] J. Mitchell, G. McTaggart, and C. Green. Shading in valveâs source engine. In SIGGRAPH Courses,page 129â142, 2006. â page 6[26] J. H. Mueller, P. Voglreiter, M. Dokter, T. Neff, M. Makar, M. Steinberger, and D. Schmalstieg.Shading atlas streaming. ACM Trans. Graph., 37(6), 2018. â page 6[27] T. Neff, J. H. Mueller, M. Steinberger, and D. Schmalstieg. Meshlets and how to shade them: A studyon texture-space shading. Computer Graphics Forum, 41(2):277â287, 2022. â pages 1, 6, 35[28] T. No¨ll and D. Stricker. Efficient packing of arbitrary shaped charts for automatic texture atlasgeneration. Computer Graphics Forum, 30(4):1309â1317, 2011. â pages 4, 5, 20[29] B. Purnomo, J. Cohen, and S. Kumar. Seamless texture atlases. In Proc. Symp. Geometry Processing,page 65â74, 2004. â page 5[30] P. V. Sander, J. Snyder, S. J. Gortler, and H. Hoppe. Texture mapping progressive meshes. In Proc.SIGGRAPH, pages 409â416, 2001. â pages 1, 19[31] P. V. Sander, Z. J. Wood, S. J. Gortler, J. Snyder, and H. Hoppe. Multi-chart geometry images. InProc. SGP 2003, pages 146â155, 2003. â pages 4, 5[32] P. Schneider and D. H. Eberly. Geometric tools for computer graphics. Elsevier, 2002. â page 11[33] A. Sheffer, B. Le´vy, M. Mogilnitsky, and A. Bogomyakov. Abf++: fast and robust angle basedflattening. ACM Trans. Graph, 24(2):311â330, 2005. â page 4[34] A. Sheffer, E. Praun, K. Rose, et al. Mesh parameterization methods and their applications.Foundations and Trends® in Computer Graphics and Vision, 2(2):105â171, 2007. â page 4[35] O. Sorkine, D. Cohen-Or, R. Goldenthal, and D. Lischinski. Bounded-distortion piecewise meshparameterization. In Proc. IEEE Visualization, pages 355â362, 2002. â page 426[36] T. Sousa. Fast as hell: Idtech 8 global illumination. In Proc. Advances in Realtime Rendering, 2025.â page 6[37] N. Vining, Z. Majercik, F. Gu, T. Takikawa, T. Trusty, P. Lalonde, M. McGuire, and A. Sheffer.Fastatlas: Real-time compact atlases for texture space shading. Computer Graphics Forum, 44(2):e70010, 2025. â pagesviii, ix, xi, xii, xiii, 1, 2, 4, 5, 6, 7, 14, 16, 17, 18, 19, 20, 35, 36, 37, 38, 39, 41, 42[38] T. Xue, M. Wu, L. Lu, H. Wang, H. Dong, and B. Chen. Learning gradient fields for scalable andgeneralizable irregular packing. In SIGGRAPH Asia 2023 Conference Papers, 2023. â page 4[39] Z. Yang, Z. Pan, M. Li, K. Wu, and X. Gao. Learning based 2d irregular shape packing. ACM Trans.Graph., 42(6), 2023. â pages 4, 16, 35[40] J. Young. xatlas, 2025. URL https://github.com/jpcy/xatlas. â pagesviii, ix, xi, xii, xiii, 1, 2, 3, 4, 16, 17, 18, 19, 20, 36, 37, 38, 39, 41, 42[41] E. Zhang, K. Mischaikow, and G. Turk. Feature-based surface parameterization and texture mapping.ACM Trans. Graph., 24(1):1â27, 2005. â page 4[42] K. Zhou, J. Synder, B. Guo, and H.-Y. Shum. Iso-charts: stretch-driven mesh parameterization usingspectral analysis. In Proc. SGP 2004, pages 45â54, 2004. â page 4[43] Q. Zhuang, Z. Chen, K. He, J. Cao, and W. Wang. Dynamics simulation-based packing of irregular3d objects. Comput. Graph., 123(C), Oct. 2024. â page 627Appendix ASupporting MaterialsA.1 Implementation DetailsWe provide details of our implementation of the TABI packing algorithm below.Computing Oriented Bounding Boxes. To construct our OBB proxy, we test a fixed set of rotations andselect the one that results in the minimal area box. We test 8 evenly spaced rotations in the interval [0, 7Ï16 ],which we find provides a sufficient balance between accuracy and speed; testing rotations beyond Ï2 isunnecessary because charts are rotated to be at least as tall as they are wide.Computing Chart Orientations. We determine whether to reflect a chart horizontally using the follow-ing procedure. If the left empty area is significantly greater than the right empty area, which we defineas a difference greater than 10% of the chartâs AABB area between the left and right area, we reflectthe chart horizontally to move the greater empty area to the right. However, if the left and right areasBottom left <bottom right area?reflecthorizo-ntallyNoare not significantly different (e.g. if the chart is perfectly di-agonal, such as inset example), we try to maximize the emptyarea in the bottom right corner by comparing the portion of thebottom area located to the left of the chartâs midline (âbottomleft areaâ, blue area in inset) against the area to the right (âbot-tom right areaâ, orange area in inset). If the bottom left areais greater than the bottom right area, we also reflect the charthorizontally.Detecting Interlocking Charts. In order to eliminate potential overlaps during pushing, we mark in thehorizontal compacting step which (if any) charts in each pair may trigger intersection if moved up relativeto the other. First, if the horizontal compacting distance is zero, neither chart is restricted from moving up.28yy â frontline - TopEdge(i)(b) Compute chart y-offsetTopEdge(i)BottomEdge(i)i = 0 1 2 3(a) Chart to pushfrontline â y + BottomEdge(i)(c) Update frontlineFigure A.1: Our extended GPU pushing algorithm. We define two functions for each chart, TopEdgeand BottomEdge, which are computed by rounding the top and bottom boundaries of our chartshape proxies (a). In the first pass, each chart computes its vertical offset by reading all frontlinetexels it covers and comparing them to its TopEdge (b). Once chart vertical offsets are finalized,each chart updates the frontline with its BottomEdge (c).If the local AABB proxy was used, one or both charts can poten-tially trigger intersection if moved up (red arrows with X in inset).We can determine if this is the case independently for each chart: achart can move up without potential intersection (green arrows withcheckmark in inset) if no rectangular segment formed by its piece-wise constant boundary is âbelowâ a segment of the other chartâs boundary (violations indicated by dashedvertical arrows in inset).If the OBB proxy was used, only one chart in each pair can potentiallytrigger intersection if moved up. We detect these cases by comparing they-positions of the rightmost corner of the left OBB and the leftmost cornerof the right OBB (circled in inset); whichever corner is lower correspondsto the chart whose upward movement may trigger intersection.Parallel Pushing Algorithm. We provide full algorithmic details of our parallel pushing method below. Alltexels in the frontline are initialized with a height of zero, corresponding to the top of the atlas. We assumeeach chart defines two functions TopEdge(i) and BottomEdge(i), whose input i is a integer texel index within[0,chartWidth) and whose output is an integer offset from the top of the chart in [0,chartHeight]. We processeach texel in each chart independently; thus, the total number of processed texels is the sum of AABB widthsof all charts in the row. First, each chart is pushed up to the existing frontline by setting its vertical offset tothe maximum of (frontlineâ TopEdge(i)) across all texels that it covers horizontally. We then run Algorithm1 to eliminate all potential overlaps (refer to the previous section for the definition of CannotMoveAbove).29Algorithm 1: Correcting chart vertical offsets after pushingInput: array of per-chart offsets for the current scale factorfunction CorrectYOffsets(offsets)doviolationDetected â 0;for each pair of charts (c,c+1) do in parallel/* offset is 0 at the top of the atlas, and increasesgoing downward */if CannotMoveAbove(c, c+1) and offsets[c].y ¡ offsets[c+1].y thenatomicCompSwap(violationDetected, 0, 1);atomicMax(offsets[c].y, offsets[c+1].y);endif CannotMoveAbove(c+1, c) and offsets[c+1].y ¡ offsets[c].y thenatomicCompSwap(violationDetected, 0, 1);atomicMax(offsets[c+1].y, offsets[c].y);endendwhile violationDetected;endOnce all chartsâ vertical offsets are finalized, each frontline texel that a chart covers horizontally is updatedwith the chartâs vertical offset plus BottomEdge(i); each frontline texel receives the maximum value acrossall charts that cover it. The process for one chart is illustrated in Fig. A.1.We employ our two chart shape proxies to compute accurate values of TopEdge and BottomEdge at eachtexel. For our local AABB proxy, we define TopEdge(i) as the topmost y position among the interval(s) inthe piecewise constant top boundary that overlap texel i horizontally; we define BottomEdge similarly. Forour OBB proxy, we define TopEdge(i) as the topmost y position reached by the one or two âtopâ edges ofthe OBB within texel i; we define BottomEdge similarly. To strictly enforce chart separation and gutterrequirements, TopEdge is rounded up to the nearest integer coordinate, while BottomEdge is rounded down.We evaluate TopEdge and BottomEdge using both proxies and use the result per-texel that provides thetightest bound on the chart shape; this corresponds to the larger y coordinate for TopEdge and the smaller ycoordinate for BottomEdge.Pseudocode for our full packing procedure is provided in Algorithms 3 and 4.Knee Detection Parameters. We categorize the height difference between two consecutive charts as a kneeif this difference is at least 10 percent of the atlas height and at least 20% of the height of the taller chart,which we find to produce reasonable results in practice. Because we consider knees a product of a rowâsshape and not necessarily its size, we use chartsâ original, unscaled heights in this comparison.Updating Knee Location. Pseudocode for updating the location of the knee in the atlas is provided inAlgorithm 2, and we illustrate the procedure in Fig A.2.30(a) Read height next tocurrent kneeknee.chartRightEdgeknee.chartLeftEdgecurrHeight(c) Update kneepositionknee.chartRightEdgeknee.chartLeftEdge(b) Compare to texelsin knee chart> > < <<Figure A.2: Our parallel algorithm for computing the knee position from the frontline. Here a left-to-right row is illustrated; the right-to-left case is symmetric. We maintain the current left edge(inclusive) and right edge (exclusive) of the knee chart, and query the frontline height at the rightedge (a). We find the closest intersection of the corresponding horizontal line with the knee chartby processing each frontline texel in the knee chart in parallel (b). Finally, we update the kneeposition and right edge of the knee chart using the location of the intersection (c).31Algorithm 2: Refining the knee location using the frontlinefunction UpdateKneeLocation(knee)if knee.leftToRight thencurrKneeLocation â knee.chartRightEdge;currHeight â frontLine[currKneeLocation];newKneeLocation â knee.chartLeftEdge - 1;for each texel x in [knee.chartLeftEdge, knee.chartRightEdge) do in parallelif frontLine[x] ¿= currHeight thenatomicMax(newKneeLocation, x);endendknee.chartRightEdge â newKneeLocation + 1;elsecurrKneeLocation â knee.chartLeftEdge - 1;currHeight â frontLine[currKneeLocation];newKneeLocation â knee.chartRightEdge;for each texel x in [knee.chartLeftEdge, knee.chartRightEdge) do in parallelif frontLine[x] ¿= currHeight thenatomicMin(newKneeLocation, x);endendknee.chartLeftEdge â newKneeLocation;endend32Algorithm 3: Folding charts into a rowInput: index of first chart in row; folding width; whether to enable horizontal compacting;per-chart offsets for the current scale factorOutput: index of last chart in rowfunction FoldRow(rowStart, foldingWidth, enableHC, offsets)c â rowStart;currLeftEdge â 0;while c ¡ numCharts donextLeftEdge â currLeftEdge + GetChartWidth(c);if nextLeftEdge ¿ foldingWidth thenreturn câ1;endoffsets[c].x â currLeftEdge;if enableHC thencurrLeftEdge â nextLeftEdge - compactingDistance[c+1];elsecurrLeftEdge â nextLeftEdge;endc â c+1;endreturn numCharts â1;end33Algorithm 4: Full packing computation for one scale factorOutput: True if packing succeeded; false otherwiserowStart â 0, overflow â false, kneeData â NULL;/* while more rows can be formed */while rowStart ¡ numCharts â§ ¬overflow doif kneeData Ì¸= NULL thenUpdateKneeLocation(kneeData);endfor each configuration j = (rowDirection, foldingWidth, enableHC) do/* folding step */rowEnd[ j] â FoldRow(rowStart, foldingWidth, enableHC, localOffsets[ j]);if rowDirection is right-to-left thenReflect charts and chart x offsets;end/* pushing step */Copy frontLine to localFrontLine[ j];for each chart c, texel i in chart do in parallelx â localOffsets[ j][c].x + i;atomicMax(localOffsets[ j][c].y, localFrontLine[ j][x] - TopEdge(c, i));endCorrectYOffsets(localOffsets[ j]);for each chart c, texel i in chart do in parallelx â localOffsets[ j][c].x + i;atomicMax(localFrontLine[ j][x], localOffsets[ j][c].y + BottomEdge(c, i));end/* compute score */for each texel x in atlasWidth do in parallelatomicMax(score[ j], localFrontLine[ j][x]);endif configuration folded at knee thenfor each texel x between atlas edge and knee location do in parallelatomicMax(scoreKnee[ j], localFrontLine[ j][x]);endendend/* commit the best configuration */Set j to best configuration;if best configuration not folded at knee then/* check if this row contains a knee; if so, save its data */kneeData â FindKnee(rowStart, rowEnd[ j]);endCopy localFrontLine[ j] to frontLine;Copy localOffsets[ j][rowStart..rowEnd[ j]] to offsets[rowStart..rowEnd[ j]];overflow â score[ j] > atlasHeight;rowStart â rowEnd[ j] + 1;endreturn ¬overflow;34A.2 Additional Evaluation Details.Data Set Sources. We assemble our dataset of UV-unwrapped chart sets from the datasets of [22], [18],and [39], and our dataset of TSS chart sets from that of [37]. We exclude inputs with only 1 chart, which canbe packed trivially, from both datasets. For UV chart sets with associated textures, we obtain chartsâ inputcoordinates in texel space, and thus their target size, by scaling the original UV coordinates in [0,1] by thedimensions of the texture. Furthermore, we determine the âfullâ atlas dimensions (which should be squareand a power of two) by taking the maximum side length in case of non-square textures and rounding downto a power of two.We note that for TSS applications, where charts are often the result of clipping and projecting scenegeometry into screen space, we are not aware of a clipping-free approximation of the OBB or of localAABBs akin to the conservative estimator used for AABBs in [37]. We therefore clip our TSS charts to theview frustum before passing them as input to any packing method. However, software clipping is alreadyrequired by some TSS algorithms (e.g., [27]); in this case, there will be no additional cost to clipping.UVPackMaster Evaluation Details. We configure UVPackMaster with the same packing settings used toevaluate all other methods: we set the pixelMargin parameter to 2 pixels to reflect our target of 2pixelsâ distance between charts, enable reflection and multiple-of-90â¦ rotations, and enable pre-rotation totight bounding boxes for UV charts only. Since UVPackMaster does not support searching for an optimaldownscaling factor (which is at most 1), we run a binary search over the 64 scale factors in the same way asfor Xatlas.On certain inputs containing complex chart topology, we find that UVPackMaster hangs indefinitelyduring the âtopology analysisâ step and does not terminate. All other methods, including ours, handle suchinputs robustly. We detect these hangs by setting a timeout of 15 minutes; 639 of the 16,772 atlases we pack(4%) exceed this timeout.We set the precision parameter to 2000 in order to eliminate chart overlap warnings raised byUVPackMaster at lower precision values. Nevertheless, even with these settings, UVPackMaster produces1,202 atlases with severe overlaps for which no warnings are issued (7.5% of inputs that terminate). Fig.A.3 shows an additional example of a UVPackMaster output with such overlaps.A.3 Additional Gallery.Figs. A.5-A.7 provide additional examples of atlases packed by our method compared to prior offline andinteractive alternatives for both UV-unwrapped and texture-space shading charts.35(a) UVPackMaster (overlap texels: 75,467;overlap texels incl. gutters: 149,276;runtime: 326,283 ms)(b) Ours (overlap texels: 0;overlap texels incl. gutters: 0;runtime: 15 ms)33,299chartsFigure A.3: The commercial GPU-based packer UVPackMaster outputs packings with severe overlaps(a). Overlap size is measured as the number of texels covered by two or more charts at the sametime. In addition, it fails to satisfy gutter requirements, measured by the number of texels coveredby two or more charts when rendered with 1 pixel gutter dilation. Our method (b) is overlap-freeand over 20,000 times faster.200 charts, full size (1K) atlasstretch: 1.68runtime: 0.6 msFastAtlasstretch: 1.68runtime: 0.7 msChameleon (GPU)stretch: 1.33runtime: 2.4 msOursstretch: 1.32runtime: 669.8 msXatlas (random)stretch: 1.29runtime: 13,925.7 msXatlas (brute force)Figure A.4: Additional comparisons of our outputs against prior offline (Xatlas [40]) and interactive(FastAtlas [37], Chameleon [16]) alternatives on chart sets originating from UV unwrapping.3640 charts, full size (1K) atlas37 charts, full size (1K) atlas42 charts, half size (512) atlas46 charts, half size (512) atlasstretch: 3.10runtime: 0.6 msFastAtlasstretch: 3.05runtime: 0.6 msChameleon (GPU)stretch: 2.67runtime: 1.2 msOursstretch: 1.54runtime: 0.6 msFastAtlasstretch: 1.56runtime: 0.6 msChameleon (GPU)stretch: 1.28runtime: 1.3 msOursstretch: 1.61runtime: 0.6 msFastAtlasstretch: 1.33runtime: 0.6 msChameleon (GPU)stretch: 1.21runtime: 1.3 msOursstretch: 1.23runtime: 408.9 msXatlas (random)stretch: 1.23runtime: 384.5 msXatlas (random)stretch: 2.65runtime: 170.9 msXatlas (random)stretch: 2.55runtime: 156.8 msXatlas (random)stretch: 2.65runtime: 997.4 msXatlas (brute force)stretch: 1.23runtime: 5,870.1 msXatlas (brute force)stretch: 1.20runtime: 6,266.7 msXatlas (brute force)stretch: 2.44runtime: 642.4 msXatlas (brute force)stretch: 3.00runtime: 0.6 msFastAtlasstretch: 3.05runtime: 0.6 msChameleon (GPU)stretch: 2.46runtime: 1.2 msOursFigure A.5: Additional comparisons of our outputs against prior offline (Xatlas [40]) and interactive(FastAtlas [37], Chameleon [16]) alternatives on chart sets originating from UV unwrapping.3769 charts, full size (1K) atlas393 charts, half size (512) atlas60 charts, half size (512) atlas89 charts, half size (512) atlasstretch: 2.39runtime: 0.6 msFastAtlasstretch: 2.37runtime: 0.6 msChameleon (GPU)stretch: 2.00runtime: 1.3 msOursstretch: 2.40runtime: 0.6 msFastAtlasstretch: 2.46runtime: 0.6 msChameleon (GPU)stretch: 2.00runtime: 1.4 msOursstretch: 2.63runtime: 0.6 msFastAtlasstretch: 2.56runtime: 0.9 msChameleon (GPU)stretch: 1.88runtime: 2.5 msOursstretch: 1.90runtime: 226.8 msXatlas (random)stretch: 2.05runtime: 214.2 msXatlas (random)stretch: 1.95runtime: 424.9 msXatlas (random)stretch: 1.18runtime: 343.0 msXatlas (random)stretch: 1.82runtime: 788.6 msXatlas (brute force)stretch: 1.99runtime: 729.6 msXatlas (brute force)stretch: 1.84runtime: 3,359.2 msXatlas (brute force)stretch: 1.10runtime: 4,007.8 msXatlas (brute force)stretch: 1.47runtime: 0.6 msFastAtlasstretch: 1.49runtime: 0.6 msChameleon (GPU)stretch: 1.14runtime: 1.3 msOursFigure A.6: Additional comparisons of our outputs against prior offline (Xatlas [40]) and interactive(FastAtlas [37], Chameleon [16]) alternatives on chart sets originating from UV unwrapping.38827 charts, 2K atlasstretch: 1.82runtime: 0.7 msstretch: 1.72runtime: 1.6 msstretch: 1.38runtime: 4.6 msFastAtlas Chameleon (GPU) Ours2,691 charts, 1K atlasstretch: 2.92runtime: 0.7 msstretch: 2.94runtime: 2.6 msstretch: 2.27runtime: 5.9 msFastAtlas Chameleon (GPU) Oursstretch: 1.28runtime: 2,740.3 msXatlas (random)stretch: 2.12runtime: 954.1 msXatlas (random)stretch: 1.33runtime: 3,373.6 msXatlas (random)stretch: 1.28runtime: 113,087.8 msXatlas (brute force)stretch: 2.12runtime: 4,397.4 msXatlas (brute force)stretch: 1.36runtime: 78,293.7 msXatlas (brute force)908 charts, 2K atlasstretch: 1.97runtime: 0.7 msFastAtlasstretch: 1.95runtime: 1.8 msChameleon (GPU)stretch: 1.45runtime: 4.4 msOursXatlas (random)stretch: 2.19runtime: 644.0 msChameleon (GPU)stretch: 2.68runtime: 0.9 msOursstretch: 2.22runtime: 2.2 msFastAtlasstretch: 2.66runtime: 0.7 ms366 charts, 1K atlasXatlas (brute force)stretch: 2.10runtime: 10,152.0 msFigure A.7: Additional comparisons of our outputs against prior offline (Xatlas [40]) and interactive(FastAtlas [37], Chameleon [16]) alternatives on texture-space shading chart sets [37]. For TSSdata, charts are not pre-rotated to their tight bounding boxes.39LocalAABBAABB/ Local Refine & HorizontalOBB AABB AABB Chart Distance Fold & Total# charts # inputs Comp. Comp. Sort Orient. Comp. Push Packingâ¤ 100 1,726 0.04 0.04 0.42 0.20 0.09 0.42 1.22101-500 2,338 0.06 0.10 0.43 0.40 0.18 0.95 2.13501-1,000 1,640 0.08 0.17 0.43 0.88 0.32 1.70 3.581,001-5,000 8,508 0.10 0.29 0.50 1.16 0.44 2.83 5.315,001-10,000 814 0.23 0.65 0.53 1.20 0.52 7.54 10.68> 10,000 1,746 0.34 1.24 0.46 1.73 0.64 6.38 10.79All 16,772 0.12 0.34 0.47 0.99 0.38 2.81 5.11Table A.1: Detailed runtime breakdown for each step of our method, averaged across all datasets andatlas sizes (all times in milliseconds). Left to right: AABB and OBB computation, local AABBcomputation, chart sorting by AABB height, boundary refinement for local AABBs and chart ori-entation computation, horizontal compacting distance computation, balanced folding and pushingfor all candidate scale factors, and total packing time (sum of all previous columns).A.4 Additional Ablations and StatisticsRuntime Breakdown. Table A.1 reports the contribution of each step of our method to our overall runtime.As expected, folding and pushing across all candidate scale factors using our balanced strategy and verticalcompacting (Alg. 4) occupies much of this time (approximately 60%). Computing our chart shape proxiescomprises approximately a further 20%.Additional Statistics. We provide detailed statistics for our experiments broken down by chart set source(UV charts, where charts are per-rotated to their tight boxes for all methods, and TSS charts, where they arenot) and atlas size. Tables A.2, A.3, A.4, and A.5 provide per-dataset and atlas size breakdowns of runtimeand stretch for our method and alternatives. Tables A.6 and A.7 show the effect of isolating our tightnessimprovement or balance improvement components compared to our full method, broken down along thesame lines. Since only 6 UV chart sets contain more than 500 charts, we do not create separate buckets forchart counts greater than 500 in our UV chart tables. Table A.8 shows the effect of our optimization strategyand topt parameter on texture-space shading inputs with more than 1,000 charts, broken down by atlas size.Note that since only 2 UV chart sets exceed the 1,000-chart threshold, we are unable to include a similarbreakdown for UV inputs.Local AABB Count Ablation. We ablate the impact of the number of local AABBs by comparing theruntime and stretch of our method with 2 and 5 local AABBs per axis to our chosen value of 10 (Tab. A.9).As expected, the fewer local AABBs we allocate, the lower the runtime but the more the stretch increases.Tables A.10 and A.11 provide detailed breakdowns by dataset and atlas size.40Mean packing time (ms) â Packing time ratioXatlas Cham- Xatlas Fast- Cham-Xatlas (brute Fast- eleon (random) Atlas eleon# charts # inputs (random) force) Atlas (GPU) Ours to ours to ours to oursHalf Sizeâ¤ 100 364 183.68 2,118.82 0.61 0.59 1.12 156.19 0.55 0.53> 100 91 483.84 9,603.26 0.65 0.83 1.74 255.79 0.39 0.48All 455 243.71 3,615.71 0.62 0.64 1.25 176.11 0.52 0.52Full Sizeâ¤ 100 364 471.92 18,911.39 0.61 0.58 1.20 379.91 0.52 0.49> 100 91 966.28 46,617.56 0.64 0.79 1.90 468.66 0.35 0.42All 455 570.79 24,452.62 0.61 0.62 1.34 397.66 0.48 0.48Table A.2: Runtime comparison of our method against both prior offline packing methods (Xatlas[40]) and alternatives capable of interactive performance (FastAtlas [37], our GPU implementa-tion of Chameleon [16]) on UV charts at full and half atlas sizes. The last 3 columns show theaverage ratios between the runtime of alternatives and that of our method. Our method is ordersof magnitude faster than prior offline methods, and though slower than FastAtlas and Chameleonon average, it remains interactive.Mean packing time (ms) â Packing time ratioXatlas Cham- Xatlas Fast- Cham-Xatlas (brute Fast- eleon (random) Atlas eleon# charts # frames (random) force) Atlas (GPU) Ours to ours to ours to ours1Kâ¤ 100 499 441.63 6,502.50 0.63 0.61 1.18 372.11 0.57 0.56101-500 1,084 723.66 10,928.50 0.66 0.83 1.99 372.48 0.35 0.42501-1,000 816 969.13 10,219.32 0.69 1.28 3.33 292.27 0.21 0.391,001-5,000 4,252 1,262.79 12,124.44 0.83 2.43 4.99 257.28 0.17 0.485,001-10,000 407 2,671.16 23,592.42 1.42 7.36 10.04 265.25 0.14 0.73> 10,000 873 5,675.60 51,512.06 1.64 16.34 9.85 577.87 0.17 1.63All 7,931 1,665.23 16,335.32 0.90 3.76 4.96 319.55 0.22 0.612Kâ¤ 100 499 1,271.39 65,283.53 0.64 0.61 1.36 941.02 0.52 0.50101-500 1,084 2,021.61 136,571.84 0.68 0.86 2.33 893.23 0.30 0.38501-1,000 816 2,538.68 122,868.79 0.72 1.51 3.85 660.95 0.19 0.391,001-5,000 4,252 3,000.36 144,730.90 0.87 3.09 5.63 547.93 0.16 0.545,001-10,000 407 4,280.75 136,668.11 1.48 9.31 11.32 381.30 0.13 0.82> 10,000 873 6,921.68 93,189.72 1.73 19.91 11.73 601.53 0.15 1.69All 7,931 3,207.64 130,280.62 0.94 4.64 5.69 628.83 0.20 0.64Table A.3: Runtime comparison of our method against both prior offline packing methods (Xatlas [40])and alternatives capable of interactive performance (FastAtlas [37], our GPU implementation ofChameleon [16]) on texture-space shading charts at 1K and 2K atlas sizes. The last 3 columnsshow the average ratios between the runtime of alternatives and that of our method. Our methodis orders of magnitude faster than prior offline methods, and though slower than FastAtlas andChameleon on average, it remains interactive.41Mean stretch â Stretch improvementXatlas Cham- vs.Xatlas (brute eleon vs. Cham-# charts # inputs (random) force) FastAtlas (GPU) Ours FastAtlas eleonHalf Sizeâ¤ 100 364 2.58 2.51 2.81 2.71 2.60 60% 43%> 100 91 2.44 2.38 2.78 2.68 2.51 65% 50%All 455 2.55 2.49 2.80 2.70 2.58 61% 44%Full Sizeâ¤ 100 364 1.26 1.23 1.38 1.33 1.27 62% 51%> 100 91 1.19 1.16 1.35 1.31 1.24 64% 46%All 455 1.25 1.22 1.37 1.32 1.26 62% 50%Table A.4: Packing scale comparison of our method against both prior offline packing methods (Xatlas[40]) and alternatives capable of interactive performance (FastAtlas [37], our GPU implementa-tion of Chameleon [16]) on UV charts at full and half atlas sizes. Our method consistently outper-forms interactive alternatives in terms of packing scale (average L2 stretch between packed andinput charts). The last two columns show the amount by which our method closes the stretch gapbetween interactive alternatives and the best method per-input.Mean stretch â Stretch improvementXatlas Cham- vs.Xatlas (brute eleon vs. Cham-# charts # frames (random) force) FastAtlas (GPU) Ours FastAtlas eleon1Kâ¤ 100 499 1.89 1.85 2.16 2.13 2.01 36% 33%101-500 1,084 2.25 2.21 2.85 2.72 2.51 51% 40%501-1,000 816 2.36 2.32 3.28 3.21 2.71 56% 52%1,001-5,000 4,252 2.36 2.37 3.42 3.35 2.87 51% 48%5,001-10,000 407 2.76 3.49 4.28 4.04 3.40 58% 50%> 10,000 873 4.76 6.15 5.79 5.26 4.47 76% 68%All 7,931 2.60 2.78 3.56 3.42 2.95 54% 49%2Kâ¤ 100 499 1.02 1.02 1.12 1.09 1.05 57% 48%101-500 1,084 1.12 1.11 1.40 1.34 1.24 54% 41%501-1,000 816 1.16 1.13 1.58 1.55 1.32 55% 53%1,001-5,000 4,252 1.15 1.14 1.62 1.61 1.38 49% 48%5,001-10,000 407 1.23 1.34 1.86 1.82 1.56 47% 44%> 10,000 873 1.45 2.06 2.18 2.11 1.81 49% 43%All 7,931 1.18 1.24 1.63 1.60 1.39 51% 47%Table A.5: Packing scale comparison of our method against both prior offline packing methods (Xatlas[40]) and alternatives capable of interactive performance (FastAtlas [37], our GPU implementa-tion of Chameleon [16]) on texture-space shading charts at 1K and 2K atlas sizes. Our methodconsistently outperforms interactive alternatives in terms of packing scale (average L2 stretch be-tween packed and input charts). The last two columns show the amount by which our methodcloses the stretch gap between interactive alternatives and the best method per-frame.Mean packing time (ms) â Mean stretch âBalanced Tight Balanced Tight# charts # inputs only only Ours only only OursHalf Sizeâ¤ 100 364 0.62 0.91 1.12 2.65 2.65 2.60> 100 91 0.81 1.29 1.74 2.57 2.59 2.51All 455 0.65 0.98 1.25 2.64 2.64 2.58Full Sizeâ¤ 100 364 0.63 0.93 1.20 1.30 1.30 1.27> 100 91 0.85 1.34 1.90 1.26 1.27 1.24All 455 0.67 1.01 1.34 1.29 1.29 1.26Table A.6: Quantitative comparison of our method against our balance component only and our tight-ness component only on UV charts at full and half atlas sizes (left: average packing time inmilliseconds, right: average L2 stretch between packed and input charts). Our full method, whichcombines both components, achieves the best packing scale.42Mean packing time (ms) â Mean stretch âBalanced Tight Balanced Tight# charts # frames only only Ours only only Ours1Kâ¤ 100 499 0.68 0.97 1.18 2.07 2.03 2.01101-500 1,084 0.89 1.54 1.99 2.64 2.57 2.51501-1,000 816 1.20 2.56 3.33 2.95 2.93 2.711,001-5,000 4,252 1.96 3.92 4.99 3.11 3.03 2.875,001-10,000 407 4.86 7.81 10.04 3.71 3.61 3.40> 10,000 873 3.27 8.19 9.85 4.95 4.75 4.47All 7,931 1.95 3.94 4.96 3.20 3.11 2.952Kâ¤ 100 499 0.71 0.99 1.36 1.07 1.05 1.05101-500 1,084 0.97 1.60 2.33 1.31 1.27 1.24501-1,000 816 1.33 2.63 3.85 1.44 1.42 1.321,001-5,000 4,252 2.14 4.01 5.63 1.50 1.46 1.385,001-10,000 407 5.17 8.04 11.32 1.70 1.65 1.56> 10,000 873 3.70 9.02 11.73 1.97 1.92 1.81All 7,931 2.13 4.11 5.69 1.50 1.46 1.39Table A.7: Quantitative comparison of our method against our balance component only and our tight-ness component only on texture-space shading charts at 1K and 2K atlas sizes (left: averagepacking time in milliseconds, right: average L2 stretch between packed and input charts). Our fullmethod, which combines both components, achieves the best packing scale.Mean packing time (ms) â Mean stretch âtopt topt topt topt topt topt topt topt# charts # frames = 5% = 2% = 1% = 0% Ours = 5% = 2% = 1% = 0% Ours1K1,001-5,000 4,252 4.26 4.27 4.34 4.99 4.99 2.89 2.88 2.88 2.87 2.875,001-10,000 407 5.69 5.82 6.28 10.04 10.04 3.50 3.47 3.46 3.40 3.40> 10,000 873 8.45 8.82 9.85 19.48 9.85 4.56 4.52 4.47 4.24 4.47All 5,532 5.02 5.10 5.35 7.65 6.13 3.20 3.18 3.17 3.12 3.162K1,001-5,000 4,252 4.99 4.98 5.06 5.63 5.63 1.39 1.38 1.38 1.38 1.385,001-10,000 407 6.87 6.99 7.56 11.32 11.32 1.58 1.57 1.57 1.56 1.56> 10,000 873 10.18 10.62 11.73 21.72 11.73 1.84 1.82 1.81 1.78 1.81All 5,532 5.94 6.02 6.30 8.59 7.01 1.47 1.47 1.46 1.46 1.46Table A.8: Quantitative evaluation of different values of topt on texture-space shading frames withmore than 1,000 charts at 1K and 2K atlas sizes (left: average packing time in milliseconds,right: average L2 stretch between packed and input charts). Higher values of topt reduce packingtime, but increase stretch. Our method, which sets topt = 0% for inputs with up to 10,000 chartsand topt = 1% otherwise, achieves similar packing scale to topt = 0% while retaining interactiveaverage runtimes.Mean packing time (ms) â Mean stretch âOurs Ours Ours Ours# charts # inputs (2 boxes) (5 boxes) Ours (2 boxes) (5 boxes) Oursâ¤ 100 1,726 0.80 0.93 1.22 1.71 1.70 1.70101-500 2,338 1.16 1.45 2.13 1.93 1.90 1.88501-1,000 1,640 1.70 2.29 3.58 2.10 2.04 2.011,001-5,000 8,508 2.71 3.49 5.31 2.20 2.15 2.125,001-10,000 814 6.34 7.71 10.68 2.56 2.50 2.48> 10,000 1,746 5.08 6.64 10.79 3.22 3.18 3.14All 16,772 2.62 3.36 5.11 2.23 2.18 2.16Table A.9: Quantitative comparisons of our method with different numbers of local AABBs: 2, 5, andour full method (10) averaged across all datasets and atlas sizes (left: average packing time inmilliseconds, right: average L2 stretch between packed and input charts). Packing scale improvesand the packing time increases with the number of local AABBs, providing a means to controlthe performance-quality tradeoff.43Mean packing time (ms) â Mean stretch âOurs Ours Ours Ours# charts # inputs (2 boxes) (5 boxes) Ours (2 boxes) (5 boxes) OursHalf Sizeâ¤ 100 364 0.74 0.86 1.12 2.62 2.60 2.60> 100 91 1.00 1.23 1.74 2.54 2.53 2.51All 455 0.79 0.93 1.25 2.60 2.59 2.58Full Sizeâ¤ 100 364 0.77 0.91 1.20 1.28 1.28 1.27> 100 91 1.07 1.33 1.90 1.25 1.24 1.24All 455 0.83 1.00 1.34 1.28 1.27 1.26Table A.10: Quantitative comparisons of our method with different numbers of local AABBs: 2, 5,and our full method (10) on UV charts at full and half atlas sizes (left: average packing time inmilliseconds, right: average L2 stretch between packed and input charts). Packing scale improvesand the packing time increases with the number of local AABBs, providing a means to controlthe performance-quality tradeoff.Mean packing time (ms) â Mean stretch âOurs Ours Ours Ours# charts # frames (2 boxes) (5 boxes) Ours (2 boxes) (5 boxes) Ours1Kâ¤ 100 499 0.80 0.92 1.18 2.03 2.01 2.01101-500 1,084 1.10 1.36 1.99 2.58 2.53 2.51501-1,000 816 1.59 2.11 3.33 2.83 2.75 2.711,001-5,000 4,252 2.56 3.28 4.99 2.97 2.90 2.875,001-10,000 407 6.07 7.31 10.04 3.50 3.43 3.40> 10,000 873 4.65 6.00 9.85 4.57 4.51 4.47All 7,931 2.56 3.26 4.96 3.05 2.99 2.952Kâ¤ 100 499 0.86 1.01 1.36 1.05 1.05 1.05101-500 1,084 1.25 1.57 2.33 1.28 1.25 1.24501-1,000 816 1.82 2.47 3.85 1.38 1.34 1.321,001-5,000 4,252 2.85 3.70 5.63 1.43 1.40 1.385,001-10,000 407 6.60 8.10 11.32 1.61 1.57 1.56> 10,000 873 5.51 7.28 11.73 1.88 1.84 1.81All 7,931 2.89 3.74 5.69 1.44 1.41 1.39Table A.11: Quantitative comparisons of our method with different numbers of local AABBs: 2, 5,and our full method (10) on texture-space shading charts at 1K and 2K atlas sizes (left: averagepacking time in milliseconds, right: average L2 stretch between packed and input charts). Pack-ing scale improves and the packing time increases with the number of local AABBs, providinga means to control the performance-quality tradeoff.44
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Sheffer, Alla
TABI : tight and balanced interactive atlas packing
Text