1 /*
2 * Copyright 2013 Jeremie Roy. All rights reserved.
3 * License: https://github.com/bkaradzic/bgfx#license-bsd-2-clause
4 */
5
6 #include "common.h"
7 #include <bgfx/bgfx.h>
8
9 #include <limits.h> // INT_MAX
10 #include <vector>
11
12 #include "cube_atlas.h"
13
14 class RectanglePacker
15 {
16 public:
17 RectanglePacker();
18 RectanglePacker(uint32_t _width, uint32_t _height);
19
20 /// non constructor initialization
21 void init(uint32_t _width, uint32_t _height);
22
23 /// find a suitable position for the given rectangle
24 /// @return true if the rectangle can be added, false otherwise
25 bool addRectangle(uint16_t _width, uint16_t _height, uint16_t& _outX, uint16_t& _outY);
26
27 /// return the used surface in squared unit
getUsedSurface()28 uint32_t getUsedSurface()
29 {
30 return m_usedSpace;
31 }
32
33 /// return the total available surface in squared unit
getTotalSurface()34 uint32_t getTotalSurface()
35 {
36 return m_width * m_height;
37 }
38
39 /// return the usage ratio of the available surface [0:1]
40 float getUsageRatio();
41
42 /// reset to initial state
43 void clear();
44
45 private:
46 int32_t fit(uint32_t _skylineNodeIndex, uint16_t _width, uint16_t _height);
47
48 /// Merges all skyline nodes that are at the same level.
49 void merge();
50
51 struct Node
52 {
NodeRectanglePacker::Node53 Node(int16_t _x, int16_t _y, int16_t _width) : x(_x), y(_y), width(_width)
54 {
55 }
56
57 int16_t x; //< The starting x-coordinate (leftmost).
58 int16_t y; //< The y-coordinate of the skyline level line.
59 int32_t width; //< The line _width. The ending coordinate (inclusive) will be x+width-1.
60 };
61
62
63 uint32_t m_width; //< width (in pixels) of the underlying texture
64 uint32_t m_height; //< height (in pixels) of the underlying texture
65 uint32_t m_usedSpace; //< Surface used in squared pixel
66 std::vector<Node> m_skyline; //< node of the skyline algorithm
67 };
68
RectanglePacker()69 RectanglePacker::RectanglePacker()
70 : m_width(0)
71 , m_height(0)
72 , m_usedSpace(0)
73 {
74 }
75
RectanglePacker(uint32_t _width,uint32_t _height)76 RectanglePacker::RectanglePacker(uint32_t _width, uint32_t _height)
77 : m_width(_width)
78 , m_height(_height)
79 , m_usedSpace(0)
80 {
81 // We want a one pixel border around the whole atlas to avoid any artefact when
82 // sampling texture
83 m_skyline.push_back(Node(1, 1, uint16_t(_width - 2) ) );
84 }
85
init(uint32_t _width,uint32_t _height)86 void RectanglePacker::init(uint32_t _width, uint32_t _height)
87 {
88 BX_CHECK(_width > 2, "_width must be > 2");
89 BX_CHECK(_height > 2, "_height must be > 2");
90 m_width = _width;
91 m_height = _height;
92 m_usedSpace = 0;
93
94 m_skyline.clear();
95 // We want a one pixel border around the whole atlas to avoid any artifact when
96 // sampling texture
97 m_skyline.push_back(Node(1, 1, uint16_t(_width - 2) ) );
98 }
99
addRectangle(uint16_t _width,uint16_t _height,uint16_t & _outX,uint16_t & _outY)100 bool RectanglePacker::addRectangle(uint16_t _width, uint16_t _height, uint16_t& _outX, uint16_t& _outY)
101 {
102 int best_height, best_index;
103 int32_t best_width;
104 Node* node;
105 Node* prev;
106 _outX = 0;
107 _outY = 0;
108
109 best_height = INT_MAX;
110 best_index = -1;
111 best_width = INT_MAX;
112 for (uint16_t ii = 0, num = uint16_t(m_skyline.size() ); ii < num; ++ii)
113 {
114 int32_t yy = fit(ii, _width, _height);
115 if (yy >= 0)
116 {
117 node = &m_skyline[ii];
118 if ( ( (yy + _height) < best_height)
119 || ( ( (yy + _height) == best_height) && (node->width < best_width) ) )
120 {
121 best_height = uint16_t(yy) + _height;
122 best_index = ii;
123 best_width = node->width;
124 _outX = node->x;
125 _outY = uint16_t(yy);
126 }
127 }
128 }
129
130 if (best_index == -1)
131 {
132 return false;
133 }
134
135 Node newNode(_outX, _outY + _height, _width);
136 m_skyline.insert(m_skyline.begin() + best_index, newNode);
137
138 for (uint16_t ii = uint16_t(best_index + 1), num = uint16_t(m_skyline.size() ); ii < num; ++ii)
139 {
140 node = &m_skyline[ii];
141 prev = &m_skyline[ii - 1];
142 if (node->x < (prev->x + prev->width) )
143 {
144 uint16_t shrink = uint16_t(prev->x + prev->width - node->x);
145 node->x += shrink;
146 node->width -= shrink;
147 if (node->width <= 0)
148 {
149 m_skyline.erase(m_skyline.begin() + ii);
150 --ii;
151 --num;
152 }
153 else
154 {
155 break;
156 }
157 }
158 else
159 {
160 break;
161 }
162 }
163
164 merge();
165 m_usedSpace += _width * _height;
166 return true;
167 }
168
getUsageRatio()169 float RectanglePacker::getUsageRatio()
170 {
171 uint32_t total = m_width * m_height;
172 if (total > 0)
173 {
174 return (float)m_usedSpace / (float)total;
175 }
176
177 return 0.0f;
178 }
179
clear()180 void RectanglePacker::clear()
181 {
182 m_skyline.clear();
183 m_usedSpace = 0;
184
185 // We want a one pixel border around the whole atlas to avoid any artefact when
186 // sampling texture
187 m_skyline.push_back(Node(1, 1, uint16_t(m_width - 2) ) );
188 }
189
fit(uint32_t _skylineNodeIndex,uint16_t _width,uint16_t _height)190 int32_t RectanglePacker::fit(uint32_t _skylineNodeIndex, uint16_t _width, uint16_t _height)
191 {
192 int32_t width = _width;
193 int32_t height = _height;
194
195 const Node& baseNode = m_skyline[_skylineNodeIndex];
196
197 int32_t xx = baseNode.x, yy;
198 int32_t widthLeft = width;
199 int32_t ii = _skylineNodeIndex;
200
201 if ( (xx + width) > (int32_t)(m_width - 1) )
202 {
203 return -1;
204 }
205
206 yy = baseNode.y;
207 while (widthLeft > 0)
208 {
209 const Node& node = m_skyline[ii];
210 if (node.y > yy)
211 {
212 yy = node.y;
213 }
214
215 if ( (yy + height) > (int32_t)(m_height - 1) )
216 {
217 return -1;
218 }
219
220 widthLeft -= node.width;
221 ++ii;
222 }
223
224 return yy;
225 }
226
merge()227 void RectanglePacker::merge()
228 {
229 Node* node;
230 Node* next;
231 uint32_t ii;
232
233 for (ii = 0; ii < m_skyline.size() - 1; ++ii)
234 {
235 node = (Node*) &m_skyline[ii];
236 next = (Node*) &m_skyline[ii + 1];
237 if (node->y == next->y)
238 {
239 node->width += next->width;
240 m_skyline.erase(m_skyline.begin() + ii + 1);
241 --ii;
242 }
243 }
244 }
245
246 struct Atlas::PackedLayer
247 {
248 RectanglePacker packer;
249 AtlasRegion faceRegion;
250 };
251
Atlas(uint16_t _textureSize,uint16_t _maxRegionsCount)252 Atlas::Atlas(uint16_t _textureSize, uint16_t _maxRegionsCount)
253 : m_usedLayers(0)
254 , m_usedFaces(0)
255 , m_textureSize(_textureSize)
256 , m_regionCount(0)
257 , m_maxRegionCount(_maxRegionsCount)
258 {
259 BX_CHECK(_textureSize >= 64 && _textureSize <= 4096, "Invalid _textureSize %d.", _textureSize);
260 BX_CHECK(_maxRegionsCount >= 64 && _maxRegionsCount <= 32000, "Invalid _maxRegionsCount %d.", _maxRegionsCount);
261
262 init();
263
264 m_layers = new PackedLayer[24];
265 for (int ii = 0; ii < 24; ++ii)
266 {
267 m_layers[ii].packer.init(_textureSize, _textureSize);
268 }
269
270 m_regions = new AtlasRegion[_maxRegionsCount];
271 m_textureBuffer = new uint8_t[ _textureSize * _textureSize * 6 * 4 ];
272 bx::memSet(m_textureBuffer, 0, _textureSize * _textureSize * 6 * 4);
273
274 m_textureHandle = bgfx::createTextureCube(_textureSize
275 , false
276 , 1
277 , bgfx::TextureFormat::BGRA8
278 );
279 }
280
Atlas(uint16_t _textureSize,const uint8_t * _textureBuffer,uint16_t _regionCount,const uint8_t * _regionBuffer,uint16_t _maxRegionsCount)281 Atlas::Atlas(uint16_t _textureSize, const uint8_t* _textureBuffer, uint16_t _regionCount, const uint8_t* _regionBuffer, uint16_t _maxRegionsCount)
282 : m_usedLayers(24)
283 , m_usedFaces(6)
284 , m_textureSize(_textureSize)
285 , m_regionCount(_regionCount)
286 , m_maxRegionCount(_regionCount < _maxRegionsCount ? _regionCount : _maxRegionsCount)
287 {
288 BX_CHECK(_regionCount <= 64 && _maxRegionsCount <= 4096, "_regionCount %d, _maxRegionsCount %d", _regionCount, _maxRegionsCount);
289
290 init();
291
292 m_regions = new AtlasRegion[_regionCount];
293 m_textureBuffer = new uint8_t[getTextureBufferSize()];
294
295 bx::memCopy(m_regions, _regionBuffer, _regionCount * sizeof(AtlasRegion) );
296 bx::memCopy(m_textureBuffer, _textureBuffer, getTextureBufferSize() );
297
298 m_textureHandle = bgfx::createTextureCube(_textureSize
299 , false
300 , 1
301 , bgfx::TextureFormat::BGRA8
302 , BGFX_SAMPLER_NONE
303 , bgfx::makeRef(m_textureBuffer, getTextureBufferSize() )
304 );
305 }
306
~Atlas()307 Atlas::~Atlas()
308 {
309 bgfx::destroy(m_textureHandle);
310
311 delete [] m_layers;
312 delete [] m_regions;
313 delete [] m_textureBuffer;
314 }
315
init()316 void Atlas::init()
317 {
318 m_texelSize = float(UINT16_MAX) / float(m_textureSize);
319 float texelHalf = m_texelSize/2.0f;
320 switch (bgfx::getRendererType() )
321 {
322 case bgfx::RendererType::Direct3D9:
323 m_texelOffset[0] = 0.0f;
324 m_texelOffset[1] = 0.0f;
325 break;
326
327 case bgfx::RendererType::Direct3D11:
328 case bgfx::RendererType::Direct3D12:
329 m_texelOffset[0] = texelHalf;
330 m_texelOffset[1] = texelHalf;
331 break;
332
333 default:
334 m_texelOffset[0] = texelHalf;
335 m_texelOffset[1] = -texelHalf;
336 break;
337 }
338 }
339
addRegion(uint16_t _width,uint16_t _height,const uint8_t * _bitmapBuffer,AtlasRegion::Type _type,uint16_t outline)340 uint16_t Atlas::addRegion(uint16_t _width, uint16_t _height, const uint8_t* _bitmapBuffer, AtlasRegion::Type _type, uint16_t outline)
341 {
342 if (m_regionCount >= m_maxRegionCount)
343 {
344 return UINT16_MAX;
345 }
346
347 uint16_t xx = 0;
348 uint16_t yy = 0;
349 uint32_t idx = 0;
350 while (idx < m_usedLayers)
351 {
352 if (m_layers[idx].faceRegion.getType() == _type
353 && m_layers[idx].packer.addRectangle(_width + 1, _height + 1, xx, yy) )
354 {
355 break;
356 }
357
358 idx++;
359 }
360
361 if (idx >= m_usedLayers)
362 {
363 if ( (idx + _type) > 24
364 || m_usedFaces >= 6)
365 {
366 return UINT16_MAX;
367 }
368
369 for (int ii = 0; ii < _type; ++ii)
370 {
371 AtlasRegion& region = m_layers[idx + ii].faceRegion;
372 region.x = 0;
373 region.y = 0;
374 region.width = m_textureSize;
375 region.height = m_textureSize;
376 region.setMask(_type, m_usedFaces, ii);
377 }
378
379 m_usedLayers += _type;
380 m_usedFaces++;
381
382 if (!m_layers[idx].packer.addRectangle(_width + 1, _height + 1, xx, yy) )
383 {
384 return UINT16_MAX;
385 }
386 }
387
388 AtlasRegion& region = m_regions[m_regionCount];
389 region.x = xx;
390 region.y = yy;
391 region.width = _width;
392 region.height = _height;
393 region.mask = m_layers[idx].faceRegion.mask;
394
395 updateRegion(region, _bitmapBuffer);
396
397 region.x += outline;
398 region.y += outline;
399 region.width -= (outline * 2);
400 region.height -= (outline * 2);
401
402 return m_regionCount++;
403 }
404
updateRegion(const AtlasRegion & _region,const uint8_t * _bitmapBuffer)405 void Atlas::updateRegion(const AtlasRegion& _region, const uint8_t* _bitmapBuffer)
406 {
407 uint32_t size = _region.width * _region.height * 4;
408 if (0 < size)
409 {
410 const bgfx::Memory* mem = bgfx::alloc(size);
411 bx::memSet(mem->data, 0, mem->size);
412 if (_region.getType() == AtlasRegion::TYPE_BGRA8)
413 {
414 const uint8_t* inLineBuffer = _bitmapBuffer;
415 uint8_t* outLineBuffer = m_textureBuffer + _region.getFaceIndex() * (m_textureSize * m_textureSize * 4) + ( ( (_region.y * m_textureSize) + _region.x) * 4);
416
417 for (int yy = 0; yy < _region.height; ++yy)
418 {
419 bx::memCopy(outLineBuffer, inLineBuffer, _region.width * 4);
420 inLineBuffer += _region.width * 4;
421 outLineBuffer += m_textureSize * 4;
422 }
423
424 bx::memCopy(mem->data, _bitmapBuffer, mem->size);
425 }
426 else
427 {
428 uint32_t layer = _region.getComponentIndex();
429 const uint8_t* inLineBuffer = _bitmapBuffer;
430 uint8_t* outLineBuffer = (m_textureBuffer + _region.getFaceIndex() * (m_textureSize * m_textureSize * 4) + ( ( (_region.y * m_textureSize) + _region.x) * 4) );
431
432 for (int yy = 0; yy < _region.height; ++yy)
433 {
434 for (int xx = 0; xx < _region.width; ++xx)
435 {
436 outLineBuffer[(xx * 4) + layer] = inLineBuffer[xx];
437 }
438
439 bx::memCopy(mem->data + yy * _region.width * 4, outLineBuffer, _region.width * 4);
440 inLineBuffer += _region.width;
441 outLineBuffer += m_textureSize * 4;
442 }
443 }
444
445 bgfx::updateTextureCube(m_textureHandle, 0, (uint8_t)_region.getFaceIndex(), 0, _region.x, _region.y, _region.width, _region.height, mem);
446 }
447 }
448
packFaceLayerUV(uint32_t _idx,uint8_t * _vertexBuffer,uint32_t _offset,uint32_t _stride) const449 void Atlas::packFaceLayerUV(uint32_t _idx, uint8_t* _vertexBuffer, uint32_t _offset, uint32_t _stride) const
450 {
451 packUV(m_layers[_idx].faceRegion, _vertexBuffer, _offset, _stride);
452 }
453
packUV(uint16_t _regionHandle,uint8_t * _vertexBuffer,uint32_t _offset,uint32_t _stride) const454 void Atlas::packUV(uint16_t _regionHandle, uint8_t* _vertexBuffer, uint32_t _offset, uint32_t _stride) const
455 {
456 const AtlasRegion& region = m_regions[_regionHandle];
457 packUV(region, _vertexBuffer, _offset, _stride);
458 }
459
writeUV(uint8_t * _vertexBuffer,int16_t _x,int16_t _y,int16_t _z,int16_t _w)460 static void writeUV(uint8_t* _vertexBuffer, int16_t _x, int16_t _y, int16_t _z, int16_t _w)
461 {
462 uint16_t* xyzw = (uint16_t*)_vertexBuffer;
463 xyzw[0] = _x;
464 xyzw[1] = _y;
465 xyzw[2] = _z;
466 xyzw[3] = _w;
467 }
468
packUV(const AtlasRegion & _region,uint8_t * _vertexBuffer,uint32_t _offset,uint32_t _stride) const469 void Atlas::packUV(const AtlasRegion& _region, uint8_t* _vertexBuffer, uint32_t _offset, uint32_t _stride) const
470 {
471 int16_t x0 = (int16_t)( ( (float)_region.x * m_texelSize + m_texelOffset[0]) - float(INT16_MAX) );
472 int16_t y0 = (int16_t)( ( (float)_region.y * m_texelSize + m_texelOffset[1]) - float(INT16_MAX) );
473 int16_t x1 = (int16_t)( ( ( (float)_region.x + _region.width) * m_texelSize + m_texelOffset[0]) - float(INT16_MAX) );
474 int16_t y1 = (int16_t)( ( ( (float)_region.y + _region.height) * m_texelSize + m_texelOffset[1]) - float(INT16_MAX) );
475 int16_t ww = (int16_t)( (float(INT16_MAX) / 4.0f) * (float)_region.getComponentIndex() );
476
477 _vertexBuffer += _offset;
478 switch (_region.getFaceIndex() )
479 {
480 case 0: // +X
481 x0 = -x0;
482 x1 = -x1;
483 y0 = -y0;
484 y1 = -y1;
485 writeUV(_vertexBuffer, INT16_MAX, y0, x0, ww); _vertexBuffer += _stride;
486 writeUV(_vertexBuffer, INT16_MAX, y1, x0, ww); _vertexBuffer += _stride;
487 writeUV(_vertexBuffer, INT16_MAX, y1, x1, ww); _vertexBuffer += _stride;
488 writeUV(_vertexBuffer, INT16_MAX, y0, x1, ww); _vertexBuffer += _stride;
489 break;
490
491 case 1: // -X
492 y0 = -y0;
493 y1 = -y1;
494 writeUV(_vertexBuffer, INT16_MIN, y0, x0, ww); _vertexBuffer += _stride;
495 writeUV(_vertexBuffer, INT16_MIN, y1, x0, ww); _vertexBuffer += _stride;
496 writeUV(_vertexBuffer, INT16_MIN, y1, x1, ww); _vertexBuffer += _stride;
497 writeUV(_vertexBuffer, INT16_MIN, y0, x1, ww); _vertexBuffer += _stride;
498 break;
499
500 case 2: // +Y
501 writeUV(_vertexBuffer, x0, INT16_MAX, y0, ww); _vertexBuffer += _stride;
502 writeUV(_vertexBuffer, x0, INT16_MAX, y1, ww); _vertexBuffer += _stride;
503 writeUV(_vertexBuffer, x1, INT16_MAX, y1, ww); _vertexBuffer += _stride;
504 writeUV(_vertexBuffer, x1, INT16_MAX, y0, ww); _vertexBuffer += _stride;
505 break;
506
507 case 3: // -Y
508 y0 = -y0;
509 y1 = -y1;
510 writeUV(_vertexBuffer, x0, INT16_MIN, y0, ww); _vertexBuffer += _stride;
511 writeUV(_vertexBuffer, x0, INT16_MIN, y1, ww); _vertexBuffer += _stride;
512 writeUV(_vertexBuffer, x1, INT16_MIN, y1, ww); _vertexBuffer += _stride;
513 writeUV(_vertexBuffer, x1, INT16_MIN, y0, ww); _vertexBuffer += _stride;
514 break;
515
516 case 4: // +Z
517 y0 = -y0;
518 y1 = -y1;
519 writeUV(_vertexBuffer, x0, y0, INT16_MAX, ww); _vertexBuffer += _stride;
520 writeUV(_vertexBuffer, x0, y1, INT16_MAX, ww); _vertexBuffer += _stride;
521 writeUV(_vertexBuffer, x1, y1, INT16_MAX, ww); _vertexBuffer += _stride;
522 writeUV(_vertexBuffer, x1, y0, INT16_MAX, ww); _vertexBuffer += _stride;
523 break;
524
525 case 5: // -Z
526 x0 = -x0;
527 x1 = -x1;
528 y0 = -y0;
529 y1 = -y1;
530 writeUV(_vertexBuffer, x0, y0, INT16_MIN, ww); _vertexBuffer += _stride;
531 writeUV(_vertexBuffer, x0, y1, INT16_MIN, ww); _vertexBuffer += _stride;
532 writeUV(_vertexBuffer, x1, y1, INT16_MIN, ww); _vertexBuffer += _stride;
533 writeUV(_vertexBuffer, x1, y0, INT16_MIN, ww); _vertexBuffer += _stride;
534 break;
535 }
536 }
537