Lepre Devlog

Lepre is, or will be, a simple 2D graphics library, made in C/C++ and OpenGL. Lepre Source

[liblepre]

Devlog 33 - Sorting

Lately I’ve been a bit busy, but I managed to do some research on sorting.

I wanted to make sure Lepre does not weight on the user with something so basic like sorting. I searched the web for some benchmarks, but I wasn’t lucky.

I’ve found this radix sort implementation http://erik.gorset.no/2011/04/radix-sort-is-faster-than-quicksort.html claiming to be faster than quick sort. So I’ve implemented quicksort, radix sort and insertion sort and I benchmarked them. The results were positive. Luckily Casey Muratori started coding the z sorting too in Handmade Hero, so on the its forums: https://hero.handmadedev.org/forum/code-discussion/1020-day-229-what-about-radix-sort Interestingly faster radix sort that one! Using an auxiliary array improves cache locality and makes radix sort really faster! I implemented that one too and here are the results. (time in ns on the y-axis, number of ordered elements on the x-axis)

Note: below 65336 the algorithms use 16bit unsigned and above they use 32bit ones.

As you can see radix sort without additional memory (radix) is way slower than quick sort iterative (qsi) on the 32bit range. Radix with additional memory (radix_mc) is instead faster than qsi in that range.

But let’s take a look closer in the 16bit range.

Hey, look! Radix is faster than qsi! But still radix_mc is faster. Maybe log scale could help.

So, insertion sort (ins) is actually faster than all of them below a certain threshold. Radix_mc is the faster one, above the ins threshold. So we have a winner!

Note: radix_mc times account for the reordering of the keys, so it is actually faster if you don’t need the keys to be reordered!

A question remains: do the 16bit specialization actually shortens times for radix_mc? For radix it’s clear that it does. Let’s see.

A little bit, above a certain threshold. And yeah, radix has a great benefit from that.

All these data refers to reordering an array of random data, generated with a xorshift128plus. Generally in real life usage you’ll not be adding quads with a random z. What if there are repetitions?

Qsi is the one that benefits more from repetitions. The others are practically the same.

Conclusion

The fastest sorting algorithm for 16bit unsigned values is radix_mc. We can sort 2^16 elements in under a ms. This is pretty good.

It occurs to me that rendering sprites from a 3D world would require to use 32 bit floating point numbers. We could map the z of the sprites in view to the 16bit unsigned domain. It has been done here http://stereopsis.com/radix.html for float32 to u32. So we could use 32 bit values or convert float32 to float16 ( like https://www.mathworks.com/matlabcentral/fileexchange/23173-ieee-754r-half-precision-floating-point-converter )and then to u16. I’ll have to build a test scenario and verify which is the best solution.

[ I’ve taken the qsi from https://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Quicksort#Iterative_Quicksort ]

The last commit: https://bitbucket.org/theGiallo/liblepre/commits/99aee5b563a4e2dbda472df366b488c2a2bb65cd. (there are other new things, but I’m going to split the devlog in two)

* jumps away *

[liblepre]

Devlog 32 - Pixel perfect

I’ve implemented two functions, that enable the user to add a sprite or an atlas frame with pixel scale of 1:1 and with aligned pixels. These functions are thought for text, e.g. a text overlay over game objects. They could be useful also for games that want to be always “pixel perfect”. Obviously rotation is a nonsense with pixel aligned, but if the camera is rotating maybe the user wants her sprite to be aligned with the world, or maybe with the screen. The user can set this with a parameter, that will rotate the sprite to be aligned with the screen, or set rotation to zero, to be aligned with the world.

Functions declarations:

lepre_bool lepre_add_sprite_px_perfect( Lepre_Draw_Data * draw_data, lepre_u32 batch_id, Lepre_Texture const * texture, Lepre_V2 pos, lepre_bool screen_aligned, Lepre_Rgba_u8 color ); lepre_bool lepre_add_atlas_frame_px_perfect( Lepre_Draw_Data * draw_data, lepre_u32 batch_id, Lepre_Atlas const * atlas, Lepre_V2 pos, lepre_u32 frame_id, lepre_bool screen_aligned, Lepre_Rgba_u8 color );

Functions use, from lepre_test:

lepre_add_sprite_px_perfect( &draw_data, world_batch, &mipmap_trilinear_test_texture, lepre_V2( 0.57f, -3.59f ), lepre_true, lepre_C_colors_u8.white ); lepre_add_atlas_frame_px_perfect( &draw_data, world_batch, &mipmap_trilinear_test_atlas, lepre_V2( -1.57f, -2.59f ), 6, lepre_false, lepre_C_colors_u8.white );

The last commit: https://bitbucket.org/theGiallo/liblepre/commits/0241614a33778b8f01244215982a29c5598511c9.

* jumps away *

P.S.: ICYMI if you view the posts singularly, the code is smaller and colored! In the dashboard it's all big and gray :[

[liblepre]

Devlog 31

I’ve integrated into Lepre the setting of the target framebuffer, with the option to set a custom viewport. It’s in a separate function, because the user should be able to target which framebuffer she wants.

I’ve also addressed the resizing and I’ve made a function the user can call to resize the linear framebuffer, if it’s the case.

It’s all demoed into the lepre_test.

The last commit: https://bitbucket.org/theGiallo/liblepre/commits/ee397683b23381be3570052ee0249f0f4771accf.

* jumps away *

[liblepre]

Devember - Devlog 30

31st day of Devember. The last one.

I’ve done some cleanup, prepped for taking shaders into lepre.h and checked the build file for the test.

It has been a nice Devember. From now on I’ll continue the development, with a more easy schedule.

A note: Lepre is not ready. Its being in development means it can change in any way at any moment, so I don’t want people to use it yet, so I’ve not coded some little things and I’ve never updated the master branch. BUT it’s usable, so if someone wants to give it a try she can. I’ll have to put the license in there. 99% I’ll pick zlib license.

The last commit: https://bitbucket.org/theGiallo/liblepre/commits/42ed90d04c23fc83d40e1cfb587b5056002d4e16.

* jumps away *

[liblepre]

Devember - Devlog 29

30th day of Devember.

The mipmapping process now is correct for each image format and color-space.

The last commit: https://bitbucket.org/theGiallo/liblepre/commits/6e8253290144d8d1c23af9353b87629c4015c12f.

* jumps away *

[liblepre]

Devember - Devlog 28

29th day of Devember. Today no code, but I've done research on downscaling. * jumps away *

[liblepre]

Devember - Devlog 27

28th day of Devember.

I’ve implemented two functions to add a rectangle textured with an atlas frame tiled:

w/ scale: the size of the texture is maintained, and the repeating count varies accordingly;

w/ size: the user needs to specify the size of the rectangle in uv coordinates, so the texturing is fixed.

Result:

Full res image.

The last commit: https://bitbucket.org/theGiallo/liblepre/commits/0e61baebdf0756f7e505901fbb07b7e335beefcd.

* jumps away *

[liblepre]

Devember - Devlog 26

27th day of Devember.

Finally I’ve written the new shader and I’ve adapted the CPU code. I’ve set up a test and tested all the wrapping policies. It seems to work correctly! I’ve not tested the actual wrapping, but it makes no color bleeding with bilinear filtering, so it should be working.

So, what I do?

I’ve changed the UV mapping for atlases to be relative to the wanted frame. So the basic quad [0,1] maps to the whole frame. The user can restrict the area of the sampling, so it can refer to a single frame, without overflowing on the neighbors. The old method to set the UV of the quad is still there, but being relative to a single frame now it enable to fill a quad repeating the frame! Texture filtering methods and wrap policies are specified per quad, so a single texture can be used for tiling and for single frames, or it can be used with linear scaling and with no interpolation. This means more data transferred, but it makes the system so flexible that it’s worth it.

Full res image.

The last commit: https://bitbucket.org/theGiallo/liblepre/commits/5f91f7f50ee2d9770dabf291df9ad9f0d277c0bb.

* jumps away *

[liblepre]

Devember - Devlog 25

26th day of Devember.

I’ve written the new shader that performs texture sampling manually and is able to restrict the sampling area. I’ve not adapted the CPU code to it, so it’s still untested.

The last commit: https://bitbucket.org/theGiallo/liblepre/commits/c72a75ea582d04584c3791e601501c642a39f562.

* jumps away *

[liblepre]

Devember - Devlog 24

25th day of Devember.

Not so much today. I’ve started working on the new shader for color bleeding prevention with atlases.

The last commit: https://bitbucket.org/theGiallo/liblepre/commits/0872c269782ac08e37f5f2a07641222ff2de84ce.

* burps away *

[liblepre]

Devember - Devlog 23

24th day of Devember.

Today more research. Visualizing the problem is always a good thing. i’ve set up a simple comparison between the 4 mipmapping methods and made 4 sprites of a full atlas with scale controlled with the mouse wheel. In this way is possible to see the problem:

Bilinear interpolation on borders takes color from neighbors atlas frames.

As this guy has done I think I will manually implement texture filtering in GLSL so I can sample atlas frames without overflowing into the neighborhood.

The last commit: https://bitbucket.org/theGiallo/liblepre/commits/20a0fe6bbc570c547111705213afe6859189e706.

* jumps away *

[liblepre]

Devember - Devlog 22

23rd day of Devember.

Today no code. I’ve done some research on atlases and mipmapping.

Links:

https://www.gamedev.net/blog/73/entry-1692117-terrain-texturing-explained/

https://gamedev.stackexchange.com/questions/46963/how-to-avoid-texture-bleeding-in-a-texture-atlas

https://www.opengl.org/discussion_boards/showthread.php/172404-Pixel-center-and-top-left-rule-in-OpenGL

* jumps away *

[liblepre]

Devember - Devlog 21

22nd day of Devember.

Today I’ve tested the code of yesterday. A lot of typos and missing things. I was clearly missing my 24″ dual monitor and my mechanical keyboard (I was at university with my 12″ laptop).

Now mipmapping is working. it’s correct only with images of power of 2 sides. Levels are calculated with the simplest method of averaging pixels of level 0 in the area covered by the pixel of the level. Yes, that is linear interpolation. It does not differentiate for different types of encoding.

I have in plan to implement more downscaling algorithms, like cubic or sinc.

Have a picture!

The last commit: https://bitbucket.org/theGiallo/liblepre/commits/5a83476ac712630e7fb073f8e638df1e24c54525.

* jumps away *

[liblepre]

Devember - Devlog 20

21st day of Devember.

I’m still working on mipmapping. I’ve read some code of SOIL as a reference of function style.

I’ve also found the cool article by J. Blow

Oh, the code compiles but is untested.

The last commit: https://bitbucket.org/theGiallo/liblepre/commits/24a8f2e3ddcc8c8ea6d6df23ce35fcf1c34abbf4.

* jumps away *

[liblepre]

Devember - Devlog 19

20th day of Devember.

Today I’ve spent some time on research on mipmapping.

Practically no code.

The last commit: https://bitbucket.org/theGiallo/liblepre/commits/e1375a3c35ee9242e2e29d8f23f9f477ff92b76d.

[liblepre]

Devember - Devlog 18

19th day of Devember.

A bit late today.

Now full window rectangles can be textured and can have a displacement, expressed in percentage of window size.

The last commit: https://bitbucket.org/theGiallo/liblepre/commits/d6c1a2f8e9d096fa8e250f1a23e2459f753d0733.

* yawns away *

[liblepre]

Devember - Devlog 17

18th day of Devember.

 I’ve rewritten the function to add a full window colored rectangle using the camera data. Now it works with camera rotation. I should write one for a textured rectangle. Maybe I could implement one with a camera relative translation. It should be useful for effects like screen-shake.

I’ve implemented the function to add a frame of a texture atlas. As can you see in the image below the linear min/max filters of OpenGL create color bleeding at the edges. I have a TODO for implementing correct mipmapping for atlases.

Now all functions support rotation only around center. It would be useful to support rotation around an arbitrary point.

The last commit: https://bitbucket.org/theGiallo/liblepre/commits/97402a8b2490a86daf88c09c80f1d6f1a500e39c.