MB2_TexturePacker.cs 38 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952
  1. using UnityEngine;
  2. using System.Collections;
  3. using System.Collections.Generic;
  4. using System;
  5. using System.IO;
  6. namespace DigitalOpus.MB.Core{
  7. // uses this algorithm http://blackpawn.com/texts/lightmaps/
  8. [System.Serializable]
  9. public struct AtlasPadding
  10. {
  11. public int topBottom;
  12. public int leftRight;
  13. public AtlasPadding(int p)
  14. {
  15. topBottom = p;
  16. leftRight = p;
  17. }
  18. public AtlasPadding(int px, int py)
  19. {
  20. topBottom = py;
  21. leftRight = px;
  22. }
  23. }
  24. [System.Serializable]
  25. public class AtlasPackingResult
  26. {
  27. public int atlasX;
  28. public int atlasY;
  29. public int usedW;
  30. public int usedH;
  31. public Rect[] rects;
  32. public AtlasPadding[] padding;
  33. public int[] srcImgIdxs;
  34. public object data;
  35. public AtlasPackingResult(AtlasPadding[] pds)
  36. {
  37. padding = pds;
  38. }
  39. public void CalcUsedWidthAndHeight()
  40. {
  41. Debug.Assert(rects != null);
  42. float maxW = 0;
  43. float maxH = 0;
  44. float paddingX = 0;
  45. float paddingY = 0;
  46. for (int i = 0; i < rects.Length; i++)
  47. {
  48. paddingX += padding[i].leftRight * 2f;
  49. paddingY += padding[i].topBottom * 2f;
  50. maxW = Mathf.Max(maxW, rects[i].x + rects[i].width);
  51. maxH = Mathf.Max(maxH, rects[i].y + rects[i].height);
  52. }
  53. usedW = Mathf.CeilToInt(maxW * atlasX + paddingX);
  54. usedH = Mathf.CeilToInt(maxH * atlasY + paddingY);
  55. if (usedW > atlasX) usedW = atlasX;
  56. if (usedH > atlasY) usedH = atlasY;
  57. }
  58. public override string ToString()
  59. {
  60. return string.Format("numRects: {0}, atlasX: {1} atlasY: {2} usedW: {3} usedH: {4}", rects.Length, atlasX, atlasY, usedW, usedH);
  61. }
  62. }
  63. public abstract class MB2_TexturePacker
  64. {
  65. public MB2_LogLevel LOG_LEVEL = MB2_LogLevel.info;
  66. internal const int MAX_RECURSION_DEPTH = 10;
  67. internal enum NodeType
  68. {
  69. Container,
  70. maxDim,
  71. regular
  72. }
  73. internal class PixRect
  74. {
  75. public int x;
  76. public int y;
  77. public int w;
  78. public int h;
  79. public PixRect() { }
  80. public PixRect(int xx, int yy, int ww, int hh)
  81. {
  82. x = xx;
  83. y = yy;
  84. w = ww;
  85. h = hh;
  86. }
  87. public override string ToString()
  88. {
  89. return String.Format("x={0},y={1},w={2},h={3}", x, y, w, h);
  90. }
  91. }
  92. internal class Image
  93. {
  94. public int imgId;
  95. public int w;
  96. public int h;
  97. public int x;
  98. public int y;
  99. public Image(int id, int tw, int th, AtlasPadding padding, int minImageSizeX, int minImageSizeY)
  100. {
  101. imgId = id;
  102. w = Mathf.Max(tw + padding.leftRight * 2, minImageSizeX);
  103. h = Mathf.Max(th + padding.topBottom * 2, minImageSizeY);
  104. }
  105. public Image(Image im)
  106. {
  107. imgId = im.imgId;
  108. w = im.w;
  109. h = im.h;
  110. x = im.x;
  111. y = im.y;
  112. }
  113. }
  114. internal class ImgIDComparer : IComparer<Image>
  115. {
  116. public int Compare(Image x, Image y)
  117. {
  118. if (x.imgId > y.imgId)
  119. return 1;
  120. if (x.imgId == y.imgId)
  121. return 0;
  122. return -1;
  123. }
  124. }
  125. internal class ImageHeightComparer : IComparer<Image>
  126. {
  127. public int Compare(Image x, Image y)
  128. {
  129. if (x.h > y.h)
  130. return -1;
  131. if (x.h == y.h)
  132. return 0;
  133. return 1;
  134. }
  135. }
  136. internal class ImageWidthComparer : IComparer<Image>
  137. {
  138. public int Compare(Image x, Image y)
  139. {
  140. if (x.w > y.w)
  141. return -1;
  142. if (x.w == y.w)
  143. return 0;
  144. return 1;
  145. }
  146. }
  147. internal class ImageAreaComparer : IComparer<Image>
  148. {
  149. public int Compare(Image x, Image y)
  150. {
  151. int ax = x.w * x.h;
  152. int ay = y.w * y.h;
  153. if (ax > ay)
  154. return -1;
  155. if (ax == ay)
  156. return 0;
  157. return 1;
  158. }
  159. }
  160. public bool atlasMustBePowerOfTwo = true;
  161. public static int RoundToNearestPositivePowerOfTwo(int x)
  162. {
  163. int p = (int)Mathf.Pow(2, Mathf.RoundToInt(Mathf.Log(x) / Mathf.Log(2)));
  164. if (p == 0 || p == 1) p = 2;
  165. return p;
  166. }
  167. public static int CeilToNearestPowerOfTwo(int x)
  168. {
  169. int p = (int)Mathf.Pow(2, Mathf.Ceil(Mathf.Log(x) / Mathf.Log(2)));
  170. if (p == 0 || p == 1) p = 2;
  171. return p;
  172. }
  173. public abstract AtlasPackingResult[] GetRects(List<Vector2> imgWidthHeights, int maxDimensionX, int maxDimensionY, int padding);
  174. public abstract AtlasPackingResult[] GetRects(List<Vector2> imgWidthHeights, List<AtlasPadding> paddings, int maxDimensionX, int maxDimensionY, bool doMultiAtlas);
  175. /*
  176. Packed rects may exceed atlas size and require scaling
  177. When scaling want pixel perfect fit in atlas. Corners of rects should exactly align with pixel grid
  178. Padding should be subtracted from pixel perfect rect to create pixel perfect square
  179. TODO this doesn't handle each rectangle having different padding
  180. */
  181. internal bool ScaleAtlasToFitMaxDim(Vector2 rootWH, List<Image> images, int maxDimensionX, int maxDimensionY, AtlasPadding padding, int minImageSizeX, int minImageSizeY, int masterImageSizeX, int masterImageSizeY,
  182. ref int outW, ref int outH, out float padX, out float padY, out int newMinSizeX, out int newMinSizeY)
  183. {
  184. newMinSizeX = minImageSizeX;
  185. newMinSizeY = minImageSizeY;
  186. bool redoPacking = false;
  187. // the atlas may be packed larger than the maxDimension. If so then the atlas needs to be scaled down to fit
  188. padX = (float)padding.leftRight / (float)outW; //padding needs to be pixel perfect in size
  189. if (rootWH.x > maxDimensionX)
  190. {
  191. padX = (float)padding.leftRight / (float)maxDimensionX;
  192. float scaleFactor = (float)maxDimensionX / (float)rootWH.x;
  193. if (LOG_LEVEL >= MB2_LogLevel.warn) Debug.LogWarning("Packing exceeded atlas width shrinking to " + scaleFactor);
  194. for (int i = 0; i < images.Count; i++)
  195. {
  196. Image im = images[i];
  197. if (im.w * scaleFactor < masterImageSizeX)
  198. { //check if small images will be rounded too small. If so need to redo packing forcing a larger min size
  199. if (LOG_LEVEL >= MB2_LogLevel.debug) Debug.Log("Small images are being scaled to zero. Will need to redo packing with larger minTexSizeX.");
  200. redoPacking = true;
  201. newMinSizeX = Mathf.CeilToInt(minImageSizeX / scaleFactor);
  202. }
  203. int right = (int)((im.x + im.w) * scaleFactor);
  204. im.x = (int)(scaleFactor * im.x);
  205. im.w = right - im.x;
  206. }
  207. outW = maxDimensionX;
  208. }
  209. padY = (float)padding.topBottom / (float)outH;
  210. if (rootWH.y > maxDimensionY)
  211. {
  212. //float minSizeY = ((float)minImageSizeY + 1) / maxDimension;
  213. padY = (float)padding.topBottom / (float)maxDimensionY;
  214. float scaleFactor = (float)maxDimensionY / (float)rootWH.y;
  215. if (LOG_LEVEL >= MB2_LogLevel.warn) Debug.LogWarning("Packing exceeded atlas height shrinking to " + scaleFactor);
  216. for (int i = 0; i < images.Count; i++)
  217. {
  218. Image im = images[i];
  219. if (im.h * scaleFactor < masterImageSizeY)
  220. { //check if small images will be rounded too small. If so need to redo packing forcing a larger min size
  221. if (LOG_LEVEL >= MB2_LogLevel.debug) Debug.Log("Small images are being scaled to zero. Will need to redo packing with larger minTexSizeY.");
  222. redoPacking = true;
  223. newMinSizeY = Mathf.CeilToInt(minImageSizeY / scaleFactor);
  224. }
  225. int bottom = (int)((im.y + im.h) * scaleFactor);
  226. im.y = (int)(scaleFactor * im.y);
  227. im.h = bottom - im.y;
  228. }
  229. outH = maxDimensionY;
  230. }
  231. return redoPacking;
  232. }
  233. //normalize atlases so that that rects are 0 to 1
  234. public void normalizeRects(AtlasPackingResult rr, AtlasPadding padding)
  235. {
  236. for (int i = 0; i < rr.rects.Length; i++)
  237. {
  238. rr.rects[i].x = (rr.rects[i].x + padding.leftRight) / rr.atlasX;
  239. rr.rects[i].y = (rr.rects[i].y + padding.topBottom) / rr.atlasY;
  240. rr.rects[i].width = (rr.rects[i].width - padding.leftRight * 2) / rr.atlasX;
  241. rr.rects[i].height = (rr.rects[i].height - padding.topBottom * 2) / rr.atlasY;
  242. }
  243. }
  244. }
  245. public class MB2_TexturePackerRegular : MB2_TexturePacker {
  246. class ProbeResult{
  247. public int w;
  248. public int h;
  249. public int outW;
  250. public int outH;
  251. public Node root;
  252. public bool largerOrEqualToMaxDim;
  253. public float efficiency;
  254. public float squareness;
  255. //these are for the multiAtlasPacker
  256. public float totalAtlasArea;
  257. public int numAtlases;
  258. public void Set(int ww, int hh, int outw, int outh, Node r, bool fits, float e, float sq){
  259. w = ww;
  260. h = hh;
  261. outW = outw;
  262. outH = outh;
  263. root = r;
  264. largerOrEqualToMaxDim = fits;
  265. efficiency = e;
  266. squareness = sq;
  267. }
  268. public float GetScore(bool doPowerOfTwoScore){
  269. float fitsScore = largerOrEqualToMaxDim ? 1f : 0f;
  270. if (doPowerOfTwoScore){
  271. return fitsScore * 2f + efficiency;
  272. } else {
  273. return squareness + 2 * efficiency + fitsScore;
  274. }
  275. }
  276. public void PrintTree()
  277. {
  278. printTree(root, " ");
  279. }
  280. }
  281. internal class Node {
  282. internal NodeType isFullAtlas; //is this node a full atlas used for scaling to fit
  283. internal Node[] child = new Node[2];
  284. internal PixRect r;
  285. internal Image img;
  286. ProbeResult bestRoot;
  287. internal Node(NodeType rootType)
  288. {
  289. isFullAtlas = rootType;
  290. }
  291. private bool isLeaf(){
  292. if (child[0] == null || child[1] == null){
  293. return true;
  294. }
  295. return false;
  296. }
  297. internal Node Insert(Image im, bool handed){
  298. int a,b;
  299. if (handed){
  300. a = 0;
  301. b = 1;
  302. } else {
  303. a = 1;
  304. b = 0;
  305. }
  306. if (!isLeaf()){
  307. //try insert into first child
  308. Node newNode = child[a].Insert(im,handed);
  309. if (newNode != null)
  310. return newNode;
  311. //no room insert into second
  312. return child[b].Insert(im,handed);
  313. } else {
  314. //(if there's already a img here, return)
  315. if (img != null)
  316. return null;
  317. //(if space too small, return)
  318. if (r.w < im.w || r.h < im.h)
  319. return null;
  320. //(if space just right, accept)
  321. if (r.w == im.w && r.h == im.h){
  322. img = im;
  323. return this;
  324. }
  325. //(otherwise, gotta split this node and create some kids)
  326. child[a] = new Node(NodeType.regular);
  327. child[b] = new Node(NodeType.regular);
  328. //(decide which way to split)
  329. int dw = r.w - im.w;
  330. int dh = r.h - im.h;
  331. if (dw > dh){
  332. child[a].r = new PixRect(r.x, r.y, im.w, r.h);
  333. child[b].r = new PixRect(r.x + im.w, r.y, r.w - im.w, r.h);
  334. } else {
  335. child[a].r = new PixRect(r.x, r.y, r.w, im.h);
  336. child[b].r = new PixRect(r.x, r.y+ im.h, r.w, r.h - im.h);
  337. }
  338. return child[a].Insert(im,handed);
  339. }
  340. }
  341. }
  342. ProbeResult bestRoot;
  343. public int atlasY;
  344. static void printTree(Node r, string spc){
  345. Debug.Log(spc + "Nd img=" + (r.img != null) + " r=" + r.r);
  346. if (r.child[0] != null)
  347. printTree(r.child[0], spc + " ");
  348. if (r.child[1] != null)
  349. printTree(r.child[1], spc + " ");
  350. }
  351. static void flattenTree(Node r, List<Image> putHere){
  352. if (r.img != null){
  353. r.img.x = r.r.x;
  354. r.img.y = r.r.y;
  355. putHere.Add(r.img);
  356. }
  357. if (r.child[0] != null)
  358. flattenTree(r.child[0], putHere);
  359. if (r.child[1] != null)
  360. flattenTree(r.child[1], putHere);
  361. }
  362. static void drawGizmosNode(Node r){
  363. Vector3 extents = new Vector3(r.r.w, r.r.h, 0);
  364. Vector3 pos = new Vector3(r.r.x + extents.x/2, -r.r.y - extents.y/2, 0f);
  365. Gizmos.color = Color.yellow;
  366. Gizmos.DrawWireCube(pos,extents);
  367. if (r.img != null){
  368. Gizmos.color = new Color(UnityEngine.Random.value, UnityEngine.Random.value, UnityEngine.Random.value);
  369. extents = new Vector3(r.img.w, r.img.h, 0);
  370. pos = new Vector3(r.r.x + extents.x / 2, -r.r.y - extents.y / 2, 0f);
  371. Gizmos.DrawCube(pos,extents);
  372. }
  373. if (r.child[0] != null){
  374. Gizmos.color = Color.red;
  375. drawGizmosNode(r.child[0]);
  376. }
  377. if (r.child[1] != null){
  378. Gizmos.color = Color.green;
  379. drawGizmosNode(r.child[1]);
  380. }
  381. }
  382. static Texture2D createFilledTex(Color c, int w, int h){
  383. Texture2D t = new Texture2D(w,h);
  384. for (int i = 0; i < w; i++){
  385. for (int j = 0; j < h; j++){
  386. t.SetPixel(i,j,c);
  387. }
  388. }
  389. t.Apply();
  390. return t;
  391. }
  392. public void DrawGizmos(){
  393. if (bestRoot != null)
  394. {
  395. drawGizmosNode(bestRoot.root);
  396. Gizmos.color = Color.yellow;
  397. Vector3 extents = new Vector3(bestRoot.outW, -bestRoot.outH, 0);
  398. Vector3 pos = new Vector3(extents.x / 2, extents.y / 2, 0f);
  399. Gizmos.DrawWireCube(pos, extents);
  400. }
  401. }
  402. bool ProbeSingleAtlas(Image[] imgsToAdd, int idealAtlasW, int idealAtlasH, float imgArea, int maxAtlasDimX, int maxAtlasDimY, ProbeResult pr){
  403. Node root = new Node(NodeType.maxDim);
  404. root.r = new PixRect(0,0,idealAtlasW,idealAtlasH);
  405. //Debug.Assert(maxAtlasDim >= 1);
  406. for (int i = 0; i < imgsToAdd.Length; i++){
  407. Node n = root.Insert(imgsToAdd[i],false);
  408. if (n == null){
  409. return false;
  410. } else if (i == imgsToAdd.Length -1){
  411. int usedW = 0;
  412. int usedH = 0;
  413. GetExtent(root,ref usedW, ref usedH);
  414. float efficiency,squareness;
  415. bool fitsInMaxDim;
  416. int atlasW = usedW;
  417. int atlasH = usedH;
  418. if (atlasMustBePowerOfTwo){
  419. atlasW = Mathf.Min (CeilToNearestPowerOfTwo(usedW), maxAtlasDimX);
  420. atlasH = Mathf.Min (CeilToNearestPowerOfTwo(usedH), maxAtlasDimY);
  421. if (atlasH < atlasW / 2) atlasH = atlasW / 2;
  422. if (atlasW < atlasH / 2) atlasW = atlasH / 2;
  423. fitsInMaxDim = usedW <= maxAtlasDimX && usedH <= maxAtlasDimY;
  424. float scaleW = Mathf.Max (1f,((float)usedW)/ maxAtlasDimX);
  425. float scaleH = Mathf.Max (1f,((float)usedH)/ maxAtlasDimY);
  426. float atlasArea = atlasW * scaleW * atlasH * scaleH; //area if we scaled it up to something large enough to contain images
  427. efficiency = 1f - (atlasArea - imgArea) / atlasArea;
  428. squareness = 1f; //don't care about squareness in power of two case
  429. } else {
  430. efficiency = 1f - (usedW * usedH - imgArea) / (usedW * usedH);
  431. if (usedW < usedH) squareness = (float) usedW / (float) usedH;
  432. else squareness = (float) usedH / (float) usedW;
  433. fitsInMaxDim = usedW <= maxAtlasDimX && usedH <= maxAtlasDimY;
  434. }
  435. pr.Set(usedW,usedH,atlasW,atlasH,root,fitsInMaxDim,efficiency,squareness);
  436. if (LOG_LEVEL >= MB2_LogLevel.debug) MB2_Log.LogDebug("Probe success efficiency w=" + usedW + " h=" + usedH + " e=" + efficiency + " sq=" + squareness + " fits=" + fitsInMaxDim);
  437. return true;
  438. }
  439. }
  440. Debug.LogError("Should never get here.");
  441. return false;
  442. }
  443. bool ProbeMultiAtlas(Image[] imgsToAdd, int idealAtlasW, int idealAtlasH, float imgArea, int maxAtlasDimX, int maxAtlasDimY, ProbeResult pr)
  444. {
  445. int numAtlases = 0;
  446. Node root = new Node(NodeType.maxDim);
  447. root.r = new PixRect(0, 0, idealAtlasW, idealAtlasH);
  448. for (int i = 0; i < imgsToAdd.Length; i++)
  449. {
  450. Node n = root.Insert(imgsToAdd[i], false);
  451. if (n == null)
  452. {
  453. if (imgsToAdd[i].x > idealAtlasW && imgsToAdd[i].y > idealAtlasH)
  454. {
  455. return false;
  456. } else
  457. {
  458. // create a new root node wider than previous atlas
  459. Node newRoot = new Node(NodeType.Container);
  460. newRoot.r = new PixRect(0, 0, root.r.w + idealAtlasW, idealAtlasH);
  461. // create a new right child
  462. Node newRight = new Node(NodeType.maxDim);
  463. newRight.r = new PixRect(root.r.w, 0, idealAtlasW, idealAtlasH);
  464. newRoot.child[1] = newRight;
  465. // insert root as a new left child
  466. newRoot.child[0] = root;
  467. root = newRoot;
  468. n = root.Insert(imgsToAdd[i], false);
  469. numAtlases++;
  470. }
  471. }
  472. }
  473. pr.numAtlases = numAtlases;
  474. pr.root = root;
  475. //todo atlas may not be maxDim * maxDim. Do some checking to see what actual needed sizes are and update pr.totalArea
  476. pr.totalAtlasArea = numAtlases * maxAtlasDimX * maxAtlasDimY;
  477. if (LOG_LEVEL >= MB2_LogLevel.debug) MB2_Log.LogDebug("Probe success efficiency numAtlases=" + numAtlases + " totalArea=" + pr.totalAtlasArea);
  478. return true;
  479. }
  480. internal void GetExtent(Node r, ref int x, ref int y)
  481. {
  482. if (r.img != null)
  483. {
  484. if (r.r.x + r.img.w > x)
  485. {
  486. x = r.r.x + r.img.w;
  487. }
  488. if (r.r.y + r.img.h > y) y = r.r.y + r.img.h;
  489. }
  490. if (r.child[0] != null)
  491. GetExtent(r.child[0], ref x, ref y);
  492. if (r.child[1] != null)
  493. GetExtent(r.child[1], ref x, ref y);
  494. }
  495. int StepWidthHeight(int oldVal, int step, int maxDim){
  496. if (atlasMustBePowerOfTwo && oldVal < maxDim){
  497. return oldVal * 2;
  498. } else {
  499. int newVal = oldVal + step;
  500. if (newVal > maxDim && oldVal < maxDim) newVal = maxDim;
  501. return newVal;
  502. }
  503. }
  504. public override AtlasPackingResult[] GetRects(List<Vector2> imgWidthHeights, int maxDimensionX, int maxDimensionY, int atPadding)
  505. {
  506. List<AtlasPadding> padding = new List<AtlasPadding>();
  507. for (int i = 0; i < imgWidthHeights.Count; i++)
  508. {
  509. AtlasPadding p = new AtlasPadding();
  510. p.leftRight = p.topBottom = atPadding;
  511. padding.Add(p);
  512. }
  513. return GetRects(imgWidthHeights, padding, maxDimensionX, maxDimensionY, false);
  514. }
  515. public override AtlasPackingResult[] GetRects(List<Vector2> imgWidthHeights, List<AtlasPadding> paddings, int maxDimensionX, int maxDimensionY, bool doMultiAtlas){
  516. Debug.Assert(imgWidthHeights.Count == paddings.Count, imgWidthHeights.Count + " " + paddings.Count);
  517. int maxPaddingX = 0;
  518. int maxPaddingY = 0;
  519. for (int i = 0; i < paddings.Count; i++)
  520. {
  521. maxPaddingX = Mathf.Max(maxPaddingX, paddings[i].leftRight);
  522. maxPaddingY = Mathf.Max(maxPaddingY, paddings[i].topBottom);
  523. }
  524. if (doMultiAtlas)
  525. {
  526. return _GetRectsMultiAtlas(imgWidthHeights, paddings, maxDimensionX, maxDimensionY, 2 + maxPaddingX * 2, 2 + maxPaddingY * 2, 2 + maxPaddingX * 2, 2 + maxPaddingY * 2);
  527. }
  528. else
  529. {
  530. AtlasPackingResult apr = _GetRectsSingleAtlas(imgWidthHeights, paddings, maxDimensionX, maxDimensionY, 2 + maxPaddingX * 2, 2 + maxPaddingY * 2, 2 + maxPaddingX * 2, 2 + maxPaddingY * 2, 0);
  531. if (apr == null)
  532. {
  533. return null;
  534. } else
  535. {
  536. return new AtlasPackingResult[] { apr };
  537. }
  538. }
  539. }
  540. //------------------ Algorithm for fitting everything into one atlas and scaling down
  541. //
  542. // for images being added calc area, maxW, maxH. A perfectly packed atlas will match area exactly. atlas must be at least maxH and maxW in size.
  543. // Sort images from big to small using either height, width or area comparer
  544. // Explore space to find a resonably efficient packing. Grow the atlas gradually until a fit is found
  545. // Scale atlas to fit
  546. //
  547. AtlasPackingResult _GetRectsSingleAtlas(List<Vector2> imgWidthHeights, List<AtlasPadding> paddings, int maxDimensionX, int maxDimensionY, int minImageSizeX, int minImageSizeY, int masterImageSizeX, int masterImageSizeY, int recursionDepth){
  548. if (LOG_LEVEL >= MB2_LogLevel.debug) Debug.Log (String.Format("_GetRects numImages={0}, maxDimension={1}, minImageSizeX={2}, minImageSizeY={3}, masterImageSizeX={4}, masterImageSizeY={5}, recursionDepth={6}",
  549. imgWidthHeights.Count, maxDimensionX, minImageSizeX, minImageSizeY, masterImageSizeX, masterImageSizeY, recursionDepth));
  550. if (recursionDepth > MAX_RECURSION_DEPTH) {
  551. if (LOG_LEVEL >= MB2_LogLevel.error) Debug.LogError("Maximum recursion depth reached. The baked atlas is likely not very good. " +
  552. " This happens when the packed atlases exceeds the maximum" +
  553. " atlas size in one or both dimensions so that the atlas needs to be downscaled AND there are some very thin or very small images (only-a-few-pixels)." +
  554. " these very thin images can 'vanish' completely when the atlas is downscaled.\n\n" +
  555. " Try one or more of the following: using multiple atlases, increase the maximum atlas size, don't use 'force-power-of-two', remove the source materials that are are using very small/thin textures.");
  556. //return null;
  557. }
  558. float area = 0;
  559. int maxW = 0;
  560. int maxH = 0;
  561. Image[] imgsToAdd = new Image[imgWidthHeights.Count];
  562. for (int i = 0; i < imgsToAdd.Length; i++){
  563. int iw = (int)imgWidthHeights[i].x;
  564. int ih = (int)imgWidthHeights[i].y;
  565. Image im = imgsToAdd[i] = new Image(i, iw, ih, paddings[i], minImageSizeX, minImageSizeY);
  566. area += im.w * im.h;
  567. maxW = Mathf.Max(maxW, im.w);
  568. maxH = Mathf.Max(maxH, im.h);
  569. }
  570. if ((float)maxH/(float)maxW > 2){
  571. if (LOG_LEVEL >= MB2_LogLevel.debug) MB2_Log.LogDebug("Using height Comparer");
  572. Array.Sort(imgsToAdd,new ImageHeightComparer());
  573. }
  574. else if ((float)maxH/(float)maxW < .5){
  575. if (LOG_LEVEL >= MB2_LogLevel.debug) MB2_Log.LogDebug("Using width Comparer");
  576. Array.Sort(imgsToAdd,new ImageWidthComparer());
  577. }
  578. else{
  579. if (LOG_LEVEL >= MB2_LogLevel.debug) MB2_Log.LogDebug("Using area Comparer");
  580. Array.Sort(imgsToAdd,new ImageAreaComparer());
  581. }
  582. //explore the space to find a resonably efficient packing
  583. int sqrtArea = (int) Mathf.Sqrt(area);
  584. int idealAtlasW;
  585. int idealAtlasH;
  586. if (atlasMustBePowerOfTwo)
  587. {
  588. idealAtlasW = idealAtlasH = RoundToNearestPositivePowerOfTwo(sqrtArea);
  589. if (maxW > idealAtlasW)
  590. {
  591. idealAtlasW = CeilToNearestPowerOfTwo(idealAtlasW);
  592. }
  593. if (maxH > idealAtlasH)
  594. {
  595. idealAtlasH = CeilToNearestPowerOfTwo(idealAtlasH);
  596. }
  597. }
  598. else
  599. {
  600. idealAtlasW = sqrtArea;
  601. idealAtlasH = sqrtArea;
  602. if (maxW > sqrtArea)
  603. {
  604. idealAtlasW = maxW;
  605. idealAtlasH = Mathf.Max(Mathf.CeilToInt(area / maxW), maxH);
  606. }
  607. if (maxH > sqrtArea)
  608. {
  609. idealAtlasW = Mathf.Max(Mathf.CeilToInt(area / maxH), maxW);
  610. idealAtlasH = maxH;
  611. }
  612. }
  613. if (idealAtlasW == 0) idealAtlasW = 4;
  614. if (idealAtlasH == 0) idealAtlasH = 4;
  615. int stepW = (int)(idealAtlasW * .15f);
  616. int stepH = (int)(idealAtlasH * .15f);
  617. if (stepW == 0) stepW = 1;
  618. if (stepH == 0) stepH = 1;
  619. int numWIterations=2;
  620. int steppedWidth = idealAtlasW;
  621. int steppedHeight = idealAtlasH;
  622. while (numWIterations >= 1 && steppedHeight < sqrtArea * 1000)
  623. {
  624. bool successW = false;
  625. numWIterations = 0;
  626. steppedWidth = idealAtlasW;
  627. while (!successW && steppedWidth < sqrtArea * 1000)
  628. {
  629. ProbeResult pr = new ProbeResult();
  630. if (LOG_LEVEL >= MB2_LogLevel.trace) Debug.Log("Probing h=" + steppedHeight + " w=" + steppedWidth);
  631. if (ProbeSingleAtlas (imgsToAdd, steppedWidth, steppedHeight, area, maxDimensionX, maxDimensionY, pr))
  632. {
  633. successW = true;
  634. if (bestRoot == null) bestRoot = pr;
  635. else if (pr.GetScore(atlasMustBePowerOfTwo) > bestRoot.GetScore(atlasMustBePowerOfTwo)) bestRoot = pr;
  636. }
  637. else
  638. {
  639. numWIterations++;
  640. steppedWidth = StepWidthHeight(steppedWidth, stepW, maxDimensionX);
  641. if (LOG_LEVEL >= MB2_LogLevel.trace) MB2_Log.LogDebug("increasing Width h=" + steppedHeight + " w=" + steppedWidth);
  642. }
  643. }
  644. steppedHeight = StepWidthHeight(steppedHeight, stepH, maxDimensionY);
  645. if (LOG_LEVEL >= MB2_LogLevel.debug) MB2_Log.LogDebug("increasing Height h=" + steppedHeight + " w=" + steppedWidth);
  646. }
  647. if (bestRoot == null)
  648. {
  649. return null;
  650. }
  651. int outW = 0;
  652. int outH = 0;
  653. if (atlasMustBePowerOfTwo){
  654. outW = Mathf.Min (CeilToNearestPowerOfTwo(bestRoot.w), maxDimensionX);
  655. outH = Mathf.Min (CeilToNearestPowerOfTwo(bestRoot.h), maxDimensionY);
  656. if (outH < outW / 2) outH = outW / 2; //smaller dim can't be less than half larger
  657. if (outW < outH / 2) outW = outH / 2;
  658. } else
  659. {
  660. outW = Mathf.Min(bestRoot.w, maxDimensionX);
  661. outH = Mathf.Min(bestRoot.h, maxDimensionY);
  662. }
  663. bestRoot.outW = outW;
  664. bestRoot.outH = outH;
  665. if (LOG_LEVEL >= MB2_LogLevel.debug) Debug.Log("Best fit found: atlasW=" + outW + " atlasH" + outH + " w=" + bestRoot.w + " h=" + bestRoot.h + " efficiency=" + bestRoot.efficiency + " squareness=" + bestRoot.squareness + " fits in max dimension=" + bestRoot.largerOrEqualToMaxDim);
  666. //Debug.Assert(images.Count != imgsToAdd.Length, "Result images not the same lentgh as source"));
  667. //the atlas can be larger than the max dimension scale it if this is the case
  668. //int newMinSizeX = minImageSizeX;
  669. //int newMinSizeY = minImageSizeY;
  670. List<Image> images = new List<Image>();
  671. flattenTree(bestRoot.root, images);
  672. images.Sort(new ImgIDComparer());
  673. // the atlas may be packed larger than the maxDimension. If so then the atlas needs to be scaled down to fit
  674. Vector2 rootWH = new Vector2(bestRoot.w, bestRoot.h);
  675. float padX, padY;
  676. int newMinSizeX, newMinSizeY;
  677. if (!ScaleAtlasToFitMaxDim(rootWH, images, maxDimensionX, maxDimensionY, paddings[0], minImageSizeX, minImageSizeY, masterImageSizeX, masterImageSizeY,
  678. ref outW, ref outH, out padX, out padY, out newMinSizeX, out newMinSizeY) ||
  679. recursionDepth > MAX_RECURSION_DEPTH)
  680. {
  681. AtlasPackingResult res = new AtlasPackingResult(paddings.ToArray());
  682. res.rects = new Rect[images.Count];
  683. res.srcImgIdxs = new int[images.Count];
  684. res.atlasX = outW;
  685. res.atlasY = outH;
  686. res.usedW = -1;
  687. res.usedH = -1;
  688. for (int i = 0; i < images.Count; i++)
  689. {
  690. Image im = images[i];
  691. Rect r = res.rects[i] = new Rect((float)im.x / (float)outW + padX,
  692. (float)im.y / (float)outH + padY,
  693. (float)im.w / (float)outW - padX * 2f,
  694. (float)im.h / (float)outH - padY * 2f);
  695. res.srcImgIdxs[i] = im.imgId;
  696. if (LOG_LEVEL >= MB2_LogLevel.debug) MB2_Log.LogDebug("Image: " + i + " imgID=" + im.imgId + " x=" + r.x * outW +
  697. " y=" + r.y * outH + " w=" + r.width * outW +
  698. " h=" + r.height * outH + " padding=" + (paddings[i].leftRight * 2) + "x" + (paddings[i].topBottom*2));
  699. }
  700. res.CalcUsedWidthAndHeight();
  701. return res;
  702. }
  703. else
  704. {
  705. if (LOG_LEVEL >= MB2_LogLevel.debug) Debug.Log("==================== REDOING PACKING ================");
  706. //root = null;
  707. return _GetRectsSingleAtlas(imgWidthHeights, paddings, maxDimensionX, maxDimensionY, newMinSizeX, newMinSizeY, masterImageSizeX, masterImageSizeY, recursionDepth + 1);
  708. }
  709. //if (LOG_LEVEL >= MB2_LogLevel.debug) MB2_Log.LogDebug(String.Format("Done GetRects atlasW={0} atlasH={1}", bestRoot.w, bestRoot.h));
  710. //return res;
  711. }
  712. //----------------- Algorithm for fitting everything into multiple Atlases
  713. //
  714. // for images being added calc area, maxW, maxH. A perfectly packed atlas will match area exactly. atlas must be at least maxH and maxW in size.
  715. // Sort images from big to small using either height, width or area comparer
  716. //
  717. // If an image is bigger than maxDim, then shrink it to max size on the largest dimension
  718. // distribute images using the new algorithm, should never have to expand the atlas instead create new atlases as needed
  719. // should not need to scale atlases
  720. //
  721. AtlasPackingResult[] _GetRectsMultiAtlas(List<Vector2> imgWidthHeights, List<AtlasPadding> paddings, int maxDimensionPassedX, int maxDimensionPassedY, int minImageSizeX, int minImageSizeY, int masterImageSizeX, int masterImageSizeY)
  722. {
  723. if (LOG_LEVEL >= MB2_LogLevel.debug) Debug.Log(String.Format("_GetRects numImages={0}, maxDimensionX={1}, maxDimensionY={2} minImageSizeX={3}, minImageSizeY={4}, masterImageSizeX={5}, masterImageSizeY={6}",
  724. imgWidthHeights.Count, maxDimensionPassedX, maxDimensionPassedY, minImageSizeX, minImageSizeY, masterImageSizeX, masterImageSizeY));
  725. float area = 0;
  726. int maxW = 0;
  727. int maxH = 0;
  728. Image[] imgsToAdd = new Image[imgWidthHeights.Count];
  729. int maxDimensionX = maxDimensionPassedX;
  730. int maxDimensionY = maxDimensionPassedY;
  731. if (atlasMustBePowerOfTwo)
  732. {
  733. maxDimensionX = RoundToNearestPositivePowerOfTwo(maxDimensionX);
  734. maxDimensionY = RoundToNearestPositivePowerOfTwo(maxDimensionY);
  735. }
  736. for (int i = 0; i < imgsToAdd.Length; i++)
  737. {
  738. int iw = (int)imgWidthHeights[i].x;
  739. int ih = (int)imgWidthHeights[i].y;
  740. //shrink the image so that it fits in maxDimenion if it is larger than maxDimension if atlas exceeds maxDim x maxDim then new alas will be created
  741. iw = Mathf.Min(iw, maxDimensionX - paddings[i].leftRight * 2);
  742. ih = Mathf.Min(ih, maxDimensionY - paddings[i].topBottom * 2);
  743. Image im = imgsToAdd[i] = new Image(i, iw, ih, paddings[i], minImageSizeX, minImageSizeY);
  744. area += im.w * im.h;
  745. maxW = Mathf.Max(maxW, im.w);
  746. maxH = Mathf.Max(maxH, im.h);
  747. }
  748. //explore the space to find a resonably efficient packing
  749. //int sqrtArea = (int)Mathf.Sqrt(area);
  750. int idealAtlasW;
  751. int idealAtlasH;
  752. if (atlasMustBePowerOfTwo)
  753. {
  754. idealAtlasH = RoundToNearestPositivePowerOfTwo(maxDimensionY);
  755. idealAtlasW = RoundToNearestPositivePowerOfTwo(maxDimensionX);
  756. }
  757. else
  758. {
  759. idealAtlasH = maxDimensionY;
  760. idealAtlasW = maxDimensionX;
  761. }
  762. if (idealAtlasW == 0) idealAtlasW = 4;
  763. if (idealAtlasH == 0) idealAtlasH = 4;
  764. ProbeResult pr = new ProbeResult();
  765. Array.Sort(imgsToAdd, new ImageHeightComparer());
  766. if (ProbeMultiAtlas(imgsToAdd, idealAtlasW, idealAtlasH, area, maxDimensionX, maxDimensionY, pr))
  767. {
  768. bestRoot = pr;
  769. }
  770. Array.Sort(imgsToAdd, new ImageWidthComparer());
  771. if (ProbeMultiAtlas(imgsToAdd, idealAtlasW, idealAtlasH, area, maxDimensionX, maxDimensionY, pr))
  772. {
  773. if (pr.totalAtlasArea < bestRoot.totalAtlasArea)
  774. {
  775. bestRoot = pr;
  776. }
  777. }
  778. Array.Sort(imgsToAdd, new ImageAreaComparer());
  779. if (ProbeMultiAtlas(imgsToAdd, idealAtlasW, idealAtlasH, area, maxDimensionX, maxDimensionY, pr))
  780. {
  781. if (pr.totalAtlasArea < bestRoot.totalAtlasArea)
  782. {
  783. bestRoot = pr;
  784. }
  785. }
  786. if (bestRoot == null)
  787. {
  788. return null;
  789. }
  790. if (LOG_LEVEL >= MB2_LogLevel.debug) Debug.Log("Best fit found: w=" + bestRoot.w + " h=" + bestRoot.h + " efficiency=" + bestRoot.efficiency + " squareness=" + bestRoot.squareness + " fits in max dimension=" + bestRoot.largerOrEqualToMaxDim);
  791. //the atlas can be larger than the max dimension scale it if this is the case
  792. //int newMinSizeX = minImageSizeX;
  793. //int newMinSizeY = minImageSizeY;
  794. List<AtlasPackingResult> rs = new List<AtlasPackingResult>();
  795. // find all Nodes that are an individual atlas
  796. List<Node> atlasNodes = new List<Node>();
  797. Stack<Node> stack = new Stack<Node>();
  798. Node node = bestRoot.root;
  799. while (node != null)
  800. {
  801. stack.Push(node);
  802. node = node.child[0];
  803. }
  804. // traverse the tree collecting atlasNodes
  805. while (stack.Count > 0)
  806. {
  807. node = stack.Pop();
  808. if (node.isFullAtlas == NodeType.maxDim) atlasNodes.Add(node);
  809. if (node.child[1] != null)
  810. {
  811. node = node.child[1];
  812. while (node != null)
  813. {
  814. stack.Push(node);
  815. node = node.child[0];
  816. }
  817. }
  818. }
  819. //pack atlases so they all fit
  820. for (int i = 0; i < atlasNodes.Count; i++)
  821. {
  822. List<Image> images = new List<Image>();
  823. flattenTree(atlasNodes[i], images);
  824. Rect[] rss = new Rect[images.Count];
  825. int[] srcImgIdx = new int[images.Count];
  826. for (int j = 0; j < images.Count; j++)
  827. {
  828. rss[j] = (new Rect(images[j].x - atlasNodes[i].r.x, images[j].y, images[j].w, images[j].h));
  829. srcImgIdx[j] = images[j].imgId;
  830. }
  831. AtlasPackingResult res = new AtlasPackingResult(paddings.ToArray());
  832. GetExtent(atlasNodes[i], ref res.usedW, ref res.usedH);
  833. res.usedW -= atlasNodes[i].r.x;
  834. int outW = atlasNodes[i].r.w;
  835. int outH = atlasNodes[i].r.h;
  836. if (atlasMustBePowerOfTwo)
  837. {
  838. outW = Mathf.Min(CeilToNearestPowerOfTwo(res.usedW), atlasNodes[i].r.w);
  839. outH = Mathf.Min(CeilToNearestPowerOfTwo(res.usedH), atlasNodes[i].r.h);
  840. if (outH < outW / 2) outH = outW / 2; //smaller dim can't be less than half larger
  841. if (outW < outH / 2) outW = outH / 2;
  842. } else
  843. {
  844. outW = res.usedW;
  845. outH = res.usedH;
  846. }
  847. res.atlasY = outH;
  848. res.atlasX = outW;
  849. res.rects = rss;
  850. res.srcImgIdxs = srcImgIdx;
  851. res.CalcUsedWidthAndHeight();
  852. rs.Add(res);
  853. normalizeRects(res, paddings[i]);
  854. if (LOG_LEVEL >= MB2_LogLevel.debug) MB2_Log.LogDebug(String.Format("Done GetRects "));
  855. }
  856. return rs.ToArray();
  857. }
  858. }
  859. }