Transcript Chart Packing Problem

Chart Packing Heuristic
Xun Shi
208395360
Problem Statement
• Finding the least area to pack all the
texture charts for a 3D models.
2006-11
Extract
texture
Optimal
packing
2
Outline
• Bin packing and its heuristics Algs
• Chart packing Algs
– Non-overlapping bounding rectangle
Heuristic
– Bruno’s Heuristic
– APTAS Heuristic
2006-11
3
Bin packing problem
• Objects of different volumes must be
packed into a finite number of bins with
capacity V in a way that minimizes the
number of bins used.
– NP-hard;
– Several Heuristic Algs;
• Applications: chart packing, linear
packing, packing by weight, etc.
2006-11
4
Heuristic Algs
• First Fit Decreasing (FFD)
– first sort the items by volume, then insert
into the first bin with sufficient space;
• With sorting: 11/9 OPT + 1 bins;
– Without sorting: 17/10 OPT + 2 bins;
– A More efficient Alg: 71/60 OPT + 1 bins;
• Best Fit Decreasing
2006-11
5
Chart Packing Problem
• given a set of polygons, find a nonoverlapping placement of the polygons
that the enclosing rectangle is of
minimum area.
• Tangram
2006-11
6
Chart Packing Problem
• Ancient China
2006-11
7
Chart Packing Problem
• given a set of polygons, find a nonoverlapping placement of the polygons
that the enclosing rectangle is of
minimum area.
• Tangram
2006-11
HOW??
8
ALG 1: Packing by nonoverlapping bounding rectangle
However, due to the arbitrary shapes…
2006-11
9
ALG 2: Bruno’s Heuristic
• Rotate the charts: maximum diameter
of the charts are oriented vertically
• Sort the charts in decreasing order
2006-11
10
ALG 2: Bruno’s Heuristic cont.
• Insert the charts one by one
2006-11
11
ALG 2: Bruno’s Heuristic cont.
• Using horizontal function to
approximate chart position;
• Rely on experience
– Not proved !!
2006-11
12
ALG 2: Bruno’s Heuristic cont.
Save space
2006-11
Waste space
13
APTAS for charts packing
• APTAS: asymptotic polynomial time
approximation scheme
– de la Vega and Leuker, 1980
– For every fixed ε> 0 algorithm outputs a
solution of size (1+ε)OPT + 1 in time
polynomial in n.
2006-11
14
APTAS for charts packing cont.
• Instance: Multiset of real numbers
• Solution: A partition of I into subsets
• Optimal Solution: A solution with a
minimum number of subsets k.
2006-11
15
APTAS for charts packing cont.
• Two constructive reductions
– Reduce BP into Large Set BP[ ], with
the threshold
• Also have Small Set
– Reduce Large Set BP[ ] into BP[ , m],
all
are chosen from a set of at most
m different values
2006-11
16
APTAS for charts packing cont.
• Large Set: BP[ , m] can be solved by
dynamic programming in polynomial of n.
k ≤(1+
) OPT
• Small Set: Greedy insert
2006-11
17
APTAS for charts packing cont.
• Running time: dominated for packing
Large Set
• k≤(1+2 ) OPT + 1 for sufficiently small
( ≤½)
2006-11
18
Reference
•
•
•
•
B. Lévy, S. Petitjean, N. Ray, J. MaillotLeast, “Squares Conformal Maps
for Automatic Texture Atlas Generation”, ACM Press, 2002
P. Sander, J. Snyder, S. Gortler, H. Hoppe, “Texture mapping
progressive meshes” In SIGGRAPH 01 Conf. Proc. 409-416. ACM Press,
2001.
U. Zwick, E. Reshef, “Bin Packing”, course note, 1997/8
del la Vega, G. S. Lueker, “Bin packing can be solved within 1+ε in linear
time”, Combinatiorica, 1(4):349-355, 1981
2006-11
19
THANK YOU VERY MUCH!!
2006-11
20