-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathK15_ImageAtlas.h
1232 lines (1022 loc) · 40.1 KB
/
K15_ImageAtlas.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/*
K15 Image Atlas v 1.0
Single header public domain library
# Author(s):
Felix Klinge (fklinge dot deck13 dot com)
# Version history
1.0 | 06/17/2016 - Intial release
1.1 | 10/20/2016 - Made the source code C89 (so it can be used by C89 only C compiler)
# What problem is this library trying to solve? (ELI5)
This library can be used to generate a single image that contains
many, smaller images. The library will try to pack the smaller images
as tightly as possible in a performant manner. This newly created
image is often called an 'Atlas'. Hence the name of the library.
# How do I add this library to my project?
This library is a single header library which means that you just have to
#include it into your project. However, you have to add the implementation
of the functions used into *one* of your C/CPP files. To do this you have
to add #define K15_IA_IMPLEMENTATION *before* the #include.
# How does this library work?
This library does implement the 'Skyline Left-Bottom' packing
algorithm. I implemented the algorithm roughly using the paper
'A Skyline-Based Heuristic for the 2D Rectangular Strip Packing Problem'
by Wei Lijun, Andrew Lim and Wenbin Zhu.
To use this library in your project, these are the steps that you should
you follow:
1. You create a new image atlas and specify how many images you want to add
(This is used to determine how much memory needs to be allocated)
Function(s) used:
K15_IACreateAtlas / K15_IACreateAtlasWithCustomMemory
Note: This will trigger an allocation (the only one in this library)
if K15_IACreateAtlas is used. If this is not the desired behavior,
call K15_IACreateAtlasWithCustomMemory with a memory block that is at
least the size of N bytes where N is an integer value returned by
the function K15_IACalculateAtlasMemorySizeInBytes .
2. You start adding images to populate the atlas. The library
will directly place the image at it's respected place according
to the algorithm implemented and will return the position where the
image has been placed to the caller.
Function(s) used:
K15_IAAddImageToAtlas
Note: K15_IAAddImageToAtlas does take a pixel format paramter to later
determine if pixel conversion needs to happen when you want to
get a copy of the image atlas.
3. After you added all the images to the atlas, you can 'bake' the atlas
and get a copy of the pixel data of the finished image atlas.
Function(s) used:
K15_IABakeImageAtlasIntoPixelBuffer
Note: K15_IABakeImageAtlasIntoPixelBuffer does take a pixel format paramater.
Pixel format conversion will happen on the fly if the pixel format
specified differs from that of individual images (that got added
by using K15_IAAddImageToAtlas). Currently, the atlas
will only grow by power of two dimensions.
4. You delete the image atlas to free previously allocated memory during
K15_IACreateAtlas.
Function(s) used:
K15_IAFreeAtlas
Note: If you did no get a copy of the pixel data of the atlas,
the data will be lost after calling this function. You basically
only need to call this function if you created the atlas using
K15_IACreateAtlas and thus triggered a memory allocation.
If memory was allocated by K15_IA_MALLOC during K15_IACreateAtlas,
the memory will be freed using K15_IA_FREE.
# Example Usage
{
const int numImagesToAdd = 256;
//has already been filled
unsigned char* imagesToAdd[numImagesToAdd];
int imagesToAddWidths[numImagesToAdd];
int imagesToAddHeights[numImagesToAdd];
K15_IAImageAtlas atlas = {};
K15_IACreateAtlas(&atlas, numImagesToAdd);
for (int imageIndex = 0;
imageIndex < numImagesToAdd;
++imageIndex)
{
unsigned char* imageData = imagesToAdd[imageIndex];
int imageWidth = imagesToAddWidths[imageIndex];
int imageHeight = imagesToAddHeights[imageIndex];
int imagePosX = 0;
int imagePosY = 0;
K15_IAAddImageToAtlas(&atlas, KIA_PIXEL_FORMAT_R8G8B8, imageData,
imageWidth, imageHeight, &imagePosX, &imagePosY);
//store imagePosX & imagePosY for later use
}
int imagePixelDataSizeInBytes = K15_IACalculateAtlasPixelDataSizeInBytes(&atlas);
void* imagePixelData = malloc(imagePixelDataSizeInBytes);
int width = 0;
int height = 0;
K15_IABakeImageAtlasIntoPixelBuffer(&atlas, KIA_PIXEL_FORMAT_R8G8B8, imagePixelData,
&width, &height);
//imagePixelData can be used in combination with imagePosX & imagePosY to
//identify individual images within the atlas.
//free memory
K15_IAFreeAtlas(&atlas);
}
# Hints
- If you've got a large amount of images you want to add to an atlas,
try increasing the amount of wasted spaces rectangles that are getting
tracked (place '#define K15_IA_MAX_WASTED_SPACE_RECTS N' before
including this header - where N is the amount of wasted space rectangles
to track. Default is 512).
- Best results can be achieved if the images are sorted prior to adding
them to the atlas.
- Currently, the library only produces atlases whose width and height
are power of two.
# TODO
- Merge wasted space areas
- Allow to create non power of two atlases
- Add border per image (really necessary?)
- Enable automatic mip map creation (really necessary?)
# License:
This software is in the public domain. Where that dedication is not
recognized, you are granted a perpetual, irrevocable license to copy
and modify this file however you want.
*/
#ifndef _K15_ImageAtlas_h_
#define _K15_ImageAtlas_h_
#ifndef K15_IA_STATIC
# define kia_def static
#else
# define kia_def extern
#endif //K15_IA_STATIC
typedef signed int kia_s32;
typedef unsigned int kia_u32;
typedef unsigned short kia_u16;
typedef unsigned char kia_u8;
typedef unsigned char kia_b8;
typedef unsigned char kia_byte;
enum _K15_IAAtlasFlags
{
KIA_EXTERNAL_MEMORY_FLAG = 0x01, //<! Memory was provided by the user (K15_IACreateAtlasWithCustomMemory)
KIA_FORCE_POWER_OF_TWO_DIMENSION = 0x02 //<! Currently used by default
};
typedef enum _K15_IAPixelFormat
{
KIA_PIXEL_FORMAT_R8 = 1,
KIA_PIXEL_FORMAT_R8A8 = 2,
KIA_PIXEL_FORMAT_R8G8B8 = 3,
KIA_PIXEL_FORMAT_R8G8B8A8 = 4
} K15_IAPixelFormat;
typedef enum _K15_AtlasResults
{
K15_IA_RESULT_SUCCESS = 0, //<! Everything went fine
K15_IA_RESULT_OUT_OF_MEMORY = 1, //<! Out of memory
K15_IA_RESULT_OUT_OF_RANGE = 2, //<! Out of range (passed wrong index)
K15_IA_RESULT_INVALID_ARGUMENTS = 3, //<! Invalid arguments (nullptr, etc)
K15_IA_RESULT_TOO_FEW_SKYLINES = 4, //<! K15_IA_MAX_SKYLINES is too small for your atlas
K15_IA_RESULT_ATLAS_TOO_SMALL = 5, //<! Only used internally
K15_IA_RESULT_ATLAS_TOO_LARGE = 6 //<! The atlas has grown too large (Specified by K15_IA_DIMENSION_THRESHOLD)
} kia_result;
struct _K15_IARect;
struct _K15_IAImageNode;
struct _K15_IASkyline;
typedef struct _K15_IARect K15_IARect;
typedef struct _K15_IAImageNode K15_IAImageNode;
typedef struct _K15_IASkyline K15_IASkyline;
typedef struct _K15_ImageAtlas
{
K15_IASkyline* skylines; //<! Skylines used to place a new image
K15_IAImageNode* imageNodes; //<! Image nodes added to the atlas
K15_IARect* wastedSpaceRects; //<! We keep track of wasted space to fill it eventually
kia_u32 width; //<! Width of the atlas
kia_u32 height; //<! Height of the atlas
kia_u32 numSkylines; //<! Number of skylines in the skylines array
kia_u32 numWastedSpaceRects; //<! Number of rects in the wastedSpaceRects array
kia_u32 numImageNodes; //<! Number of image nodes in the imageNodes array
kia_u32 numMaxImageNodes; //<! Maximum number of images supported for the atlas
kia_u8 flags; //<! See K15_IAAtlasFlags enum
} K15_ImageAtlas;
//Create a new atlas which is able to store and process p_NumImages of images.
//Note: Triggers an allocation by using K15_IA_MALLOC.
// Returns one of the following results:
// - K15_IA_RESULT_INVALID_ARGUMENTS (p_OutImageAtlas is NULL or p_Components is invalid)
// - K15_IA_RESULT_OUT_OF_MEMORY
// - K15_IA_RESULT_SUCCESS
kia_def kia_result K15_IACreateAtlas(K15_ImageAtlas* p_OutImageAtlas, kia_u32 p_NumImages);
//Create a new atlas which is able to store and process p_NumImages of images.
//Note: Returns one of the following results:
// - K15_IA_RESULT_INVALID_ARGUMENTS (p_OutImageAtlas is NULL or p_Components is invalid)
// - K15_IA_RESULT_SUCCESS
kia_def kia_result K15_IACreateAtlasWithCustomMemory(K15_ImageAtlas* p_OutImageAtlas, kia_u32 p_NumImages,
void* p_AtlasMemory);
//Calculates the amount of memory needed (in bytes) to store an image atlas which
//is able to store p_NumImages of images.
kia_def kia_u32 K15_IACalculateAtlasMemorySizeInBytes(kia_u32 p_NumImages);
//Calculate the amount of memory needed (in bytes) to store the baked image atlas
//pixel data in a specific pixel format.
kia_def kia_u32 K15_IACalculateAtlasPixelDataSizeInBytes(K15_ImageAtlas* p_ImageAtlas, K15_IAPixelFormat p_PixelFormat);
//Free a previously created atlas (K15_IACreateAtlas). Deallocates all memory associated with
//an image atlas.
//Note: You don't necessarly need to call this function if you used your own memory using
// K15_IACreateAtlasWithCustomMemory.
kia_def void K15_IAFreeAtlas(K15_ImageAtlas* p_ImageAtlas);
//Add an image to a specific atlas using a specific pixel format.
//This will trigger the algorithm to find the best possible position for the image.
//The position found will be returned to the caller using the p_OutX and p_OutY parameters.
//Note: Returns one of the following results:
// - K15_IA_RESULT_INVALID_ARGUMENTS (p_ImageAtlas is NULL, p_PixelData is NULL or
// p_PixelDataWith and/or p_PixelDataHeight are invalid or
// p_OutX and/or p_OutY are NULL)
// - K15_IA_RESULT_ATLAS_TOO_SMALL
// - K15_IA_RESULT_TOO_FEW_SKYLINES
// - K15_IA_RESULT_OUT_OF_RANGE (Trying to add more images than specified
// in K15_IACreateAtlas / K15_IACreateAtlasWithCustomMemory)
// - K15_IA_RESULT_SUCCESS
kia_def kia_result K15_IAAddImageToAtlas(K15_ImageAtlas* p_ImageAtlas, K15_IAPixelFormat p_PixelFormat,
void* p_PixelData, kia_u32 p_PixelDataWidth, kia_u32 p_PixelDataHeight,
int* p_OutX, int* p_OutY);
//Compose the images in the atlas into a given pixel data buffer using a specific pixel format.
//The width and height of the resulting pixel buffer will be returned to the caller using the
//p_OutWidth and p_OutHeight parameters (can be NULL).
//Note: If there's a mismatch between the pixel format specified (p_PixelFormat) and the
// pixel format of individual images (specified in K15_IAAddImageToAtlas), pixel
// conversion will happen on the fly to match the pixel format specified.
kia_def void K15_IABakeImageAtlasIntoPixelBuffer(K15_ImageAtlas* p_ImageAtlas, K15_IAPixelFormat p_PixelFormat,
void* p_DestinationPixelDataBuffer, int* p_OutWidth, int* p_OutHeight);
#ifdef K15_IA_IMPLEMENTATION
#define K15_IA_TRUE 1
#define K15_IA_FALSE 0
#ifndef K15_IA_MAX_SKYLINES
# define K15_IA_MAX_SKYLINES 128
#endif //K15_IA_MAX_SKYLINES
#ifndef K15_IA_MAX_WASTED_SPACE_RECTS
# define K15_IA_MAX_WASTED_SPACE_RECTS 512
#endif //K15_IA_MAX_WASTED_SPACE_RECTS
#ifndef K15_IA_DIMENSION_THRESHOLD
# define K15_IA_DIMENSION_THRESHOLD 8192
#endif //K15_IA_DIMENSION_THRESHOLD
#ifndef K15_IA_DEFAULT_MIN_ATLAS_DIMENSION
# define K15_IA_DEFAULT_MIN_ATLAS_DIMENSION 16
#endif //K15_IA_DEFAULT_MIN_ATLAS_DIMENSION
#if K15_IA_DEFAULT_MIN_ATLAS_DIMENSION <= 8
# error "'K15_IA_DEFAULT_MIN_ATLAS_DIMENSION' needs to be at least 8"
#endif
#if K15_IA_DIMENSION_THRESHOLD <= 0
# error "'K15_IA_DIMENSION_THRESHOLD' can not be negative or zero"
#endif
#if K15_IA_DEFAULT_MIN_ATLAS_DIMENSION > K15_IA_DIMENSION_THRESHOLD
# error "'K15_IA_DEFAULT_MIN_ATLAS_DIMENSION' is greater than 'K15_IA_DIMENSION_THRESHOLD'"
#endif
#ifndef K15_IA_MALLOC
# include <stdlib.h>
# define K15_IA_MALLOC malloc
# define K15_IA_FREE free
#endif //K15_IA_MALLOC
#ifndef K15_IA_MEMCPY
# include <string.h>
# define K15_IA_MEMCPY memcpy
#endif //K15_IA_MEMCPY
#ifndef K15_IA_MEMSET
# include <string.h>
# define K15_IA_MEMSET memset
#endif //K15_IA_MEMSET
#ifndef K15_IA_MEMMOVE
# include <string.h>
# define K15_IA_MEMMOVE memmove
#endif //K15_IA_MEMMOVE
#ifndef K15_IA_QSORT
# include <search.h>
# define K15_IA_QSORT qsort
#endif //K15_IA_QSORT
#ifndef K15_IA_MIN
# define K15_IA_MIN(a,b) ((a) < (b) ? (a) : (b))
#endif //K15_IA_MIN
#ifndef K15_IA_MAX
# define K15_IA_MAX(a,b) ((a) > (b) ? (a) : (b))
#endif //K15_IA_MAX
#ifndef kia_internal
# define kia_internal static
#endif //kia_internal
typedef struct _K15_IARect
{
kia_u16 posX;
kia_u16 posY;
kia_u16 width;
kia_u16 height;
} K15_IARect;
typedef struct _K15_IAImageNode
{
K15_IAPixelFormat pixelDataFormat;
K15_IARect rect;
kia_byte* pixelData;
} K15_IAImageNode;
typedef struct _K15_IASkyline
{
kia_u16 baseLinePosX;
kia_u16 baseLinePosY;
kia_u32 baseLineWidth;
} K15_IASkyline;
/*********************************************************************************/
kia_internal int K15_IASortSkylineByXPos(const void* p_SkylineA, const void* p_SkylineB)
{
K15_IASkyline* skylineA = (K15_IASkyline*)p_SkylineA;
K15_IASkyline* skylineB = (K15_IASkyline*)p_SkylineB;
return skylineA->baseLinePosX - skylineB->baseLinePosX;
}
/*********************************************************************************/
/*********************************************************************************/
kia_internal void K15_IAConvertPixel(kia_u8* p_SourcePixel, kia_u8* p_DestinationPixel,
K15_IAPixelFormat p_SourcePixelFormat, K15_IAPixelFormat p_DestinationPixelFormat)
{
if (p_SourcePixelFormat == KIA_PIXEL_FORMAT_R8)
{
kia_s32 colorIndex = 0;
for (colorIndex = 0;
colorIndex < p_DestinationPixelFormat;
++colorIndex)
{
p_DestinationPixel[colorIndex] = *p_SourcePixel;
}
}
else if (p_SourcePixelFormat == KIA_PIXEL_FORMAT_R8A8)
{
kia_u8 sourcePixel = (kia_u8)((float)p_SourcePixel[0] * (float)((p_SourcePixel[1]) / 255));
if (p_DestinationPixelFormat == KIA_PIXEL_FORMAT_R8)
p_DestinationPixel[0] = sourcePixel;
else if (p_DestinationPixelFormat == KIA_PIXEL_FORMAT_R8G8B8)
{
p_DestinationPixel[0] = sourcePixel;
p_DestinationPixel[1] = sourcePixel;
p_DestinationPixel[2] = sourcePixel;
}
else if (p_DestinationPixelFormat == KIA_PIXEL_FORMAT_R8G8B8A8)
{
p_DestinationPixel[0] = p_SourcePixel[0];
p_DestinationPixel[1] = p_SourcePixel[0];
p_DestinationPixel[2] = p_SourcePixel[0];
p_DestinationPixel[3] = p_SourcePixel[1];
}
}
else if (p_SourcePixelFormat == KIA_PIXEL_FORMAT_R8G8B8)
{
kia_u8 greyscale = (kia_u8)((float)(p_SourcePixel[0]) * 0.21f +
(float)(p_SourcePixel[1]) * 0.72f +
(float)(p_SourcePixel[2]) * 0.07f);
if (p_DestinationPixelFormat == KIA_PIXEL_FORMAT_R8)
p_DestinationPixel[0] = greyscale;
else if (p_DestinationPixelFormat == KIA_PIXEL_FORMAT_R8A8)
{
p_DestinationPixel[0] = greyscale;
p_DestinationPixel[1] = 255;
}
else if (p_DestinationPixelFormat == KIA_PIXEL_FORMAT_R8G8B8A8)
{
p_DestinationPixel[0] = p_SourcePixel[0];
p_DestinationPixel[1] = p_SourcePixel[1];
p_DestinationPixel[2] = p_SourcePixel[2];
p_DestinationPixel[3] = 255;
}
}
else if (p_SourcePixelFormat == KIA_PIXEL_FORMAT_R8G8B8A8)
{
float greyscale = (float)(p_SourcePixel[0]) * 0.21f +
(float)(p_SourcePixel[1]) * 0.72f +
(float)(p_SourcePixel[2]) * 0.07f;
float alpha = (float)(p_SourcePixel[3] / 255.f);
float greyscaleWithAlpha = greyscale * alpha;
if (p_DestinationPixelFormat == KIA_PIXEL_FORMAT_R8)
p_DestinationPixel[0] = (kia_u8)(greyscaleWithAlpha + 0.5f);
else if (p_DestinationPixelFormat == KIA_PIXEL_FORMAT_R8A8)
{
p_DestinationPixel[0] = (kia_u8)(greyscale + 0.5f);
p_DestinationPixel[1] = p_SourcePixel[3];
}
else if (p_DestinationPixelFormat == KIA_PIXEL_FORMAT_R8G8B8)
{
p_DestinationPixel[0] = (kia_u8)((float)(p_SourcePixel[0]) * alpha);
p_DestinationPixel[1] = (kia_u8)((float)(p_SourcePixel[1]) * alpha);
p_DestinationPixel[2] = (kia_u8)((float)(p_SourcePixel[2]) * alpha);
}
}
}
/*********************************************************************************/
kia_internal kia_result K15_IAConvertPixelData(kia_byte* p_DestinationPixelData, kia_byte* p_SourcePixelData,
K15_IAPixelFormat p_DestinationPixelFormat, K15_IAPixelFormat p_SourcePixelFormat,
kia_u32 p_PixelDataStride)
{
kia_u32 sourcePixelIndex = 0;
kia_u32 destinationPixelIndex = 0;
kia_u32 pixelIndex = 0;
if (!p_SourcePixelData || !p_DestinationPixelData || p_PixelDataStride == 0)
{
return K15_IA_RESULT_INVALID_ARGUMENTS;
}
//convert pixel by pixel
for (pixelIndex = 0;
pixelIndex < p_PixelDataStride;
++pixelIndex)
{
sourcePixelIndex = pixelIndex * p_SourcePixelFormat;
destinationPixelIndex = pixelIndex * p_DestinationPixelFormat;
K15_IAConvertPixel(p_SourcePixelData + sourcePixelIndex,
p_DestinationPixelData + destinationPixelIndex,
p_SourcePixelFormat, p_DestinationPixelFormat);
}
return K15_IA_RESULT_SUCCESS;
}
/*********************************************************************************/
kia_internal kia_u32 K15_IARemoveSkylineByIndex(K15_IASkyline* p_Skylines, kia_u32 p_NumSkylines,
kia_u32 p_SkylineIndex)
{
kia_u32 numSkylines = p_NumSkylines;
kia_u32 numSkylinesToMove = 0;
if (p_SkylineIndex + 1 < numSkylines)
{
numSkylinesToMove = numSkylines - p_SkylineIndex;
K15_IA_MEMMOVE(p_Skylines + p_SkylineIndex, p_Skylines + p_SkylineIndex + 1,
numSkylinesToMove * sizeof(K15_IASkyline));
}
return --numSkylines;
}
/*********************************************************************************/
kia_internal kia_u32 K15_IAAddWastedSpaceRect(K15_IARect* p_WastedSpaceRects, kia_u32 p_NumWastedSpaceRects,
kia_u32 p_PosX, kia_u32 p_PosY, kia_u32 p_Width, kia_u32 p_Height)
{
if (p_NumWastedSpaceRects == K15_IA_MAX_WASTED_SPACE_RECTS)
return p_NumWastedSpaceRects;
p_WastedSpaceRects[p_NumWastedSpaceRects].posX = p_PosX;
p_WastedSpaceRects[p_NumWastedSpaceRects].posY = p_PosY;
p_WastedSpaceRects[p_NumWastedSpaceRects].width = p_Width;
p_WastedSpaceRects[p_NumWastedSpaceRects].height = p_Height;
return p_NumWastedSpaceRects + 1;
}
/*********************************************************************************/
kia_internal void K15_IAFindWastedSpaceAndRemoveObscuredSkylines(K15_IASkyline* p_Skylines,
kia_u32* p_NumSkylinesOutIn, K15_IARect* p_WastedSpaceRects, kia_u32* p_NumWastedSpaceRectsOutIn,
kia_u32 p_PosX, kia_u32 p_PosY, kia_u32 p_Width)
{
kia_u32 baseLinePosX = 0;
kia_u32 baseLinePosY = 0;
kia_u32 baseLineWidth = 0;
kia_u32 rightPos = p_PosX + p_Width;
kia_u32 baseLineRightPos = 0;
kia_u32 numSkylines = *p_NumSkylinesOutIn;
kia_u32 numWastedSpaceRects = *p_NumWastedSpaceRectsOutIn;
kia_u32 skylineIndex = 0;
K15_IASkyline* skyline = 0;
for (skylineIndex = 0;
skylineIndex < numSkylines;
++skylineIndex)
{
skyline = p_Skylines + skylineIndex;
baseLinePosX = skyline->baseLinePosX;
baseLinePosY = skyline->baseLinePosY;
baseLineWidth = skyline->baseLineWidth;
if (p_PosX < baseLinePosX && rightPos > baseLinePosX && p_PosY >= baseLinePosY)
{
//Split if we 'reach' into another skyline
//check first if the current skyline is fully obscured
baseLineRightPos = baseLinePosX + baseLineWidth;
if (rightPos < baseLineRightPos)
{
numWastedSpaceRects = K15_IAAddWastedSpaceRect(p_WastedSpaceRects, numWastedSpaceRects,
baseLinePosX, baseLinePosY, rightPos - baseLinePosX, p_PosY - baseLinePosY);
skyline->baseLineWidth = baseLineRightPos - rightPos;
skyline->baseLinePosX = rightPos;
continue;
}
numSkylines = K15_IARemoveSkylineByIndex(p_Skylines, numSkylines, skylineIndex);
numWastedSpaceRects = K15_IAAddWastedSpaceRect(p_WastedSpaceRects, numWastedSpaceRects,
baseLinePosX, baseLinePosY, baseLineWidth, p_PosY - baseLinePosY);
--skylineIndex;
}
}
*p_NumSkylinesOutIn = numSkylines;
*p_NumWastedSpaceRectsOutIn = numWastedSpaceRects;
}
/*********************************************************************************/
kia_internal kia_u32 K15_IAMergeSkylines(K15_IASkyline* p_Skylines, kia_u32 p_NumSkylines)
{
K15_IASkyline* skyline = 0;
K15_IASkyline* previousSkyline = 0;
kia_u32 baselineY = 0;
kia_u32 previousBaseLineY = 0;
kia_u32 skylineIndex = 1;
kia_u32 numSkylines = p_NumSkylines;
if (numSkylines > 1)
{
for (skylineIndex = 1;
skylineIndex < numSkylines;
++skylineIndex)
{
skyline = p_Skylines + skylineIndex;
previousSkyline = p_Skylines + skylineIndex - 1;
if (skyline->baseLinePosY == previousSkyline->baseLinePosY)
{
previousSkyline->baseLineWidth += skyline->baseLineWidth;
numSkylines = K15_IARemoveSkylineByIndex(p_Skylines, numSkylines, skylineIndex);
--skylineIndex;
}
}
}
return numSkylines;
}
/*********************************************************************************/
kia_internal kia_result K15_IATryToInsertSkyline(K15_ImageAtlas* p_ImageAtlas, kia_u32 p_BaseLineY,
kia_u32 p_BaseLineX, kia_u32 p_BaseLineWidth)
{
K15_IASkyline* skylines = p_ImageAtlas->skylines;
K15_IASkyline* newSkyline = 0;
K15_IARect* wastedSpaceRects = p_ImageAtlas->wastedSpaceRects;
kia_u32 numSkylines = p_ImageAtlas->numSkylines;
kia_u32 numWastedSpaceRects = p_ImageAtlas->numWastedSpaceRects;
if (numSkylines == K15_IA_MAX_SKYLINES)
return K15_IA_RESULT_TOO_FEW_SKYLINES;
newSkyline = skylines + numSkylines++;
newSkyline->baseLinePosX = p_BaseLineX;
newSkyline->baseLinePosY = p_BaseLineY;
newSkyline->baseLineWidth = p_BaseLineWidth;
//Sort by x position
K15_IA_QSORT(skylines, numSkylines, sizeof(K15_IASkyline), K15_IASortSkylineByXPos);
//try to merge neighbor skylines with the same baseline (y pos)
p_ImageAtlas->numSkylines = K15_IAMergeSkylines(skylines, numSkylines);
return K15_IA_RESULT_SUCCESS;
}
/*********************************************************************************/
kia_internal kia_result K15_IATryToGrowAtlasSize(K15_ImageAtlas* p_ImageAtlas)
{
kia_u32 width = p_ImageAtlas->width;
kia_u32 height = p_ImageAtlas->height;
kia_u32 numSkylines = p_ImageAtlas->numSkylines;
kia_u32 widthExtend = 0;
kia_u32 skylineIndex = 0;
kia_u32 oldWidth = width;
kia_b8 foundSkyline = K15_IA_FALSE;
K15_IASkyline* skylines = p_ImageAtlas->skylines;
K15_IASkyline* skyline = 0;
if (width > height)
height = height << 1;
else
width = width << 1;
if (width > K15_IA_DIMENSION_THRESHOLD || height > K15_IA_DIMENSION_THRESHOLD)
return K15_IA_RESULT_ATLAS_TOO_SMALL;
widthExtend = width - oldWidth;
p_ImageAtlas->width = width;
p_ImageAtlas->height = height;
//find skylines with pos == 0 (at the very bottom and extend their width)
for (skylineIndex = 0;
skylineIndex < numSkylines;
++skylineIndex)
{
skyline = skylines + skylineIndex;
if (skyline->baseLinePosY == 0)
{
skyline->baseLineWidth += widthExtend;
foundSkyline = K15_IA_TRUE;
}
}
if (!foundSkyline)
K15_IATryToInsertSkyline(p_ImageAtlas, 0, oldWidth, widthExtend);
return K15_IA_RESULT_SUCCESS;
}
/*********************************************************************************/
kia_internal kia_result K15_IATryToGrowAtlasSizeToFit(K15_ImageAtlas* p_ImageAtlas,
kia_u32 p_MinWidth, kia_u32 p_MinHeight)
{
kia_u32 width = p_ImageAtlas->width;
kia_u32 height = p_ImageAtlas->height;
if (height >= p_MinHeight &&
width >= p_MinWidth)
{
return K15_IA_RESULT_SUCCESS;
}
while (height < p_MinHeight || width < p_MinWidth)
{
kia_result result = K15_IATryToGrowAtlasSize(p_ImageAtlas);
if (result != K15_IA_RESULT_SUCCESS)
return result;
width = p_ImageAtlas->width;
height = p_ImageAtlas->height;
}
return K15_IA_RESULT_SUCCESS;
}
/*********************************************************************************/
kia_u32 K15_IACalculatePlacementHeuristic(kia_u32 p_BaseLinePosX, kia_u32 p_BaseLinePosY, kia_u32 p_NodeWidth,
kia_u32 p_NodeHeight, K15_IASkyline* p_Skylines, kia_u32 p_NumSkylines)
{
kia_u32 heuristic = 0;
kia_u32 skylineIndex = 0;
K15_IASkyline* skyline = 0;
for (skylineIndex = 0;
skylineIndex < p_NumSkylines;
++skylineIndex)
{
skyline = p_Skylines + skylineIndex;
if (skyline->baseLinePosX >= skyline->baseLinePosX && skyline->baseLinePosX < p_BaseLinePosX + p_NodeWidth)
{
kia_u32 right = K15_IA_MIN(skyline->baseLinePosX + skyline->baseLineWidth, p_BaseLinePosX + p_NodeWidth);
kia_u32 left = K15_IA_MAX(skyline->baseLinePosX, p_BaseLinePosX);
kia_u32 width = right - left;
kia_u32 height = p_BaseLinePosY - skyline->baseLinePosY;
heuristic += width * height;
}
}
return heuristic;
}
/*********************************************************************************/
kia_internal kia_u32 K15_IARemoveOrTrimWastedSpaceRect(K15_IARect* p_WastedSpaceRects,
kia_u32 p_NumWastedSpaceRects, kia_u32 p_Index, kia_u32 p_Width, kia_u32 p_Height)
{
K15_IARect* wastedSpaceRect = p_WastedSpaceRects + p_Index;
if (wastedSpaceRect->width == p_Width &&
wastedSpaceRect->height > p_Height)
{
wastedSpaceRect->posY += p_Height;
wastedSpaceRect->height -= p_Height;
}
else if (wastedSpaceRect->height == p_Height &&
wastedSpaceRect->width > p_Width)
{
wastedSpaceRect->posX += p_Width;
wastedSpaceRect->width -= p_Width;
}
else
{
kia_u32 rectWidth = wastedSpaceRect->width;
kia_u32 rectHeight = wastedSpaceRect->height;
kia_u32 restHeight = wastedSpaceRect->height - p_Height;
kia_u32 restWidth = wastedSpaceRect->width - p_Width;
kia_u32 posLowerX = wastedSpaceRect->posX;
kia_u32 posLowerY = wastedSpaceRect->posY + p_Height;
kia_u32 posRightX = wastedSpaceRect->posX + p_Width;
kia_u32 posRightY = wastedSpaceRect->posY;
if (p_NumWastedSpaceRects > 1)
{
//Remove
kia_u32 numElementsToShift = p_NumWastedSpaceRects - p_Index;
K15_IA_MEMMOVE(p_WastedSpaceRects + p_Index, p_WastedSpaceRects + p_Index + 1,
sizeof(K15_IARect) * numElementsToShift);
}
--p_NumWastedSpaceRects;
if (restWidth != 0 && restHeight != 0)
{
if (restWidth > restHeight)
{
p_NumWastedSpaceRects = K15_IAAddWastedSpaceRect(p_WastedSpaceRects, p_NumWastedSpaceRects, posRightX, posRightY, restWidth, rectHeight);
p_NumWastedSpaceRects = K15_IAAddWastedSpaceRect(p_WastedSpaceRects, p_NumWastedSpaceRects, posLowerX, posLowerY, p_Width, restHeight);
}
else
{
p_NumWastedSpaceRects = K15_IAAddWastedSpaceRect(p_WastedSpaceRects, p_NumWastedSpaceRects, posLowerX, posLowerY, rectWidth, restHeight);
p_NumWastedSpaceRects = K15_IAAddWastedSpaceRect(p_WastedSpaceRects, p_NumWastedSpaceRects, posRightX, posRightY, restWidth, p_Height);
}
}
}
return p_NumWastedSpaceRects;
}
/*********************************************************************************/
kia_internal kia_b8 K15_IATryToFitInWastedSpace(K15_IARect* p_WastedSpaceRects, kia_u32* p_NumWastedSpaceRectsInOut,
K15_IAImageNode* p_NodeToInsert)
{
kia_u32 wastedRectWidth = 0;
kia_u32 wastedRectHeight = 0;
kia_u32 nodeWidth = p_NodeToInsert->rect.width;
kia_u32 nodeHeight = p_NodeToInsert->rect.height;
kia_u32 numWastedSpaceRects = *p_NumWastedSpaceRectsInOut;
kia_u32 heuristic = 0;
kia_u32 bestHeuristic = ~0;
kia_u32 bestFitIndex = ~0;
kia_u32 rectIndex = 0;
K15_IARect* wastedSpaceRect = 0;
for (rectIndex = 0;
rectIndex < numWastedSpaceRects;
++rectIndex)
{
wastedSpaceRect = p_WastedSpaceRects + rectIndex;
wastedRectWidth = wastedSpaceRect->width;
wastedRectHeight = wastedSpaceRect->height;
if (wastedRectWidth >= nodeWidth &&
wastedRectHeight >= nodeHeight)
{
heuristic = wastedRectWidth * wastedRectHeight;
if (heuristic < bestHeuristic)
{
bestHeuristic = heuristic;
bestFitIndex = rectIndex;
}
//we can't get better than this
if (bestHeuristic == 0)
break;
}
}
if (bestFitIndex != ~0)
{
//copy position
wastedSpaceRect = p_WastedSpaceRects + bestFitIndex;
p_NodeToInsert->rect.posX = wastedSpaceRect->posX;
p_NodeToInsert->rect.posY = wastedSpaceRect->posY;
numWastedSpaceRects = K15_IARemoveOrTrimWastedSpaceRect(p_WastedSpaceRects,
numWastedSpaceRects, bestFitIndex, nodeWidth, nodeHeight);
}
*p_NumWastedSpaceRectsInOut = numWastedSpaceRects;
return (bestFitIndex != ~0);
}
/*********************************************************************************/
kia_internal kia_b8 K15_IACheckCollision(K15_IASkyline* p_Skylines, kia_u32 p_NumSkylines, kia_u32 p_BaseLinePosY,
kia_u32 p_BaseLinePosX, kia_u32 p_Width)
{
kia_u32 baseLinePosRight = p_BaseLinePosX + p_Width;
kia_u32 skylineIndex = 0;
K15_IASkyline* skyline = 0;
kia_b8 collision = K15_IA_FALSE;
for (skylineIndex = 0;
skylineIndex < p_NumSkylines;
++skylineIndex)
{
skyline = p_Skylines + skylineIndex;
if (skyline->baseLinePosX > baseLinePosRight)
break;
if (skyline->baseLinePosY > p_BaseLinePosY)
{
collision = K15_IA_TRUE;
break;
}
}
return collision;
}
/*********************************************************************************/
kia_internal kia_result K15_IAAddImageToAtlasSkyline(K15_ImageAtlas* p_ImageAtlas, K15_IAImageNode* p_NodeToInsert,
int* p_OutX, int* p_OutY)
{
kia_result result = K15_IA_RESULT_ATLAS_TOO_SMALL;
kia_u32 numSkylines = p_ImageAtlas->numSkylines;
kia_u32 numImageNodes = p_ImageAtlas->numImageNodes;
kia_u32 numWastedSpaceRects = p_ImageAtlas->numWastedSpaceRects;
kia_u32 height = p_ImageAtlas->height;
kia_u32 width = p_ImageAtlas->width;
kia_u32 lowerPixelSpace = 0;
kia_u32 nodeWidth = p_NodeToInsert->rect.width;
kia_u32 nodeHeight = p_NodeToInsert->rect.height;
kia_u32 baseLinePosY = 0;
kia_u32 baseLinePosX = 0;
kia_u32 baseLineWidth = 0;
kia_u32 heuristic = 0;
kia_u32 bestHeuristic = ~0;
kia_u32 bestFitIndex = ~0;
kia_u32 skylineIndex = 0;
kia_u32 numSkylinesLeft = 0;
K15_IASkyline* skyline = 0;
K15_IASkyline* skylines = p_ImageAtlas->skylines;
K15_IASkyline* nextSkyline = 0;
K15_IAImageNode* imageNodes = p_ImageAtlas->imageNodes;
K15_IARect* wastedSpaceRects = p_ImageAtlas->wastedSpaceRects;
kia_b8 fitsInWastedSpace = K15_IATryToFitInWastedSpace(wastedSpaceRects,
&p_ImageAtlas->numWastedSpaceRects, p_NodeToInsert);
kia_b8 nodeCollides = K15_IA_FALSE;
if (!fitsInWastedSpace)
{
for (skylineIndex = 0;
skylineIndex < numSkylines;
++skylineIndex)
{
skyline = skylines + skylineIndex;
baseLinePosY = skyline->baseLinePosY;
baseLinePosX = skyline->baseLinePosX;
baseLineWidth = skyline->baseLineWidth;
lowerPixelSpace = height - baseLinePosY;
nodeCollides = K15_IA_FALSE;
//check if image fits vertically and does not go out of the atlas if placed
//on this skyline
if (lowerPixelSpace >= nodeHeight &&
baseLinePosX + nodeWidth <= width)
{
//we need additional checks if the image is wider than the current skyline
if (baseLineWidth < nodeWidth)
{
//due to the nature of the algorithm we just need to check the next skylines.
//if they're vertically smaller than the current skyline, we can safely place
//the image at this position. However, this would introduce wasted space
//(which we track)
//No need to check. If this would be the last skyline (and we therefore would
//access out of bounds here), we would never end in this code as the node
//would exceed the atlas width.
nextSkyline = skyline + 1;
numSkylinesLeft = (numSkylines - skylineIndex - 1);
nodeCollides = K15_IACheckCollision(nextSkyline, numSkylinesLeft,
baseLinePosY, baseLinePosX, nodeWidth);
}
if (!nodeCollides)
{
//node potentially fits. Calculate and save heuristic
heuristic = K15_IACalculatePlacementHeuristic(baseLinePosX, baseLinePosY,
nodeWidth, nodeHeight, skylines, numSkylines);
if (heuristic < bestHeuristic)
{
bestHeuristic = heuristic;
bestFitIndex = skylineIndex;
}
//we can't get better than this
if (bestHeuristic == 0)
break;
}
}
}
if (bestFitIndex != ~0)
{
skyline = skylines + bestFitIndex;
p_NodeToInsert->rect.posX = skyline->baseLinePosX;
p_NodeToInsert->rect.posY = skyline->baseLinePosY;
if (skyline->baseLineWidth > p_NodeToInsert->rect.width)
{
skyline->baseLinePosX += p_NodeToInsert->rect.width;
skyline->baseLineWidth -= p_NodeToInsert->rect.width;
}
else
{
p_ImageAtlas->numSkylines = K15_IARemoveSkylineByIndex(skylines, numSkylines,
bestFitIndex);
}
result = K15_IATryToInsertSkyline(p_ImageAtlas, p_NodeToInsert->rect.posY + p_NodeToInsert->rect.height,
p_NodeToInsert->rect.posX, p_NodeToInsert->rect.width);
numSkylines = p_ImageAtlas->numSkylines;
}
}
else
{
result = K15_IA_RESULT_SUCCESS;
}
if (result == K15_IA_RESULT_SUCCESS)
{
if (p_OutX)
*p_OutX = p_NodeToInsert->rect.posX;
if (p_OutY)
*p_OutY = p_NodeToInsert->rect.posY;
//remove/trim any skylines that would be obscured by the new skyline
K15_IAFindWastedSpaceAndRemoveObscuredSkylines(skylines, &numSkylines,
wastedSpaceRects, &p_ImageAtlas->numWastedSpaceRects,
p_NodeToInsert->rect.posX, p_NodeToInsert->rect.posY,
p_NodeToInsert->rect.width);
p_ImageAtlas->numSkylines = numSkylines;
}
return result;
}
/*********************************************************************************/