Difference between revisions of "GSoC-SpriteSheets Gabba"

From The Battle for Wesnoth Wiki
(Artists' workflow)
m (Hide historical instance of "SVN" from mediawiki search to avoid false positives.)
 
(62 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{SoC2010Student}}
+
{{SoC2010Student_2|gabba|SoC Ideas SpriteSheets}}
 +
[[Category:SoC Ideas SpriteSheets]]
  
 
=Description=
 
=Description=
<h3>Gabba - Sprite Sheets</h3>
+
<h4>Gabba - Sprite Sheets</h4>
  
I have a pretty concrete proposal of how I'd implement the idea from http://wiki.wesnoth.org/SoC_Ideas_SpriteSheets
+
I developed an approach to introduce sprite sheets to Wesnoth with minimal hassle for artists, and as little modifications to game code as possible. I support generation of various sizes of optimized sprite sheets, so we can adapt to various platform and memory/disk requirements. My system will rely on a single external tool based on an existing open-source solution.
Details inside!
+
 
 +
''Updated 04/09/2010''
 +
=IRC=
 +
gabba
 +
 
 +
=SoC Application=
 +
[http://socghop.appspot.com/gsoc/student_proposal/review/google/gsoc2010/gabba/t127042311772 Wesnoth Sprite Sheets]
  
 
=About Me=
 
=About Me=
See http://wiki.wesnoth.org/User:Gabba.
+
See [[User:Gabba]].
  
 
=Project=
 
=Project=
 
The general idea of this project is to introduce sprite sheets and their memory, loading time and disk space benefits, while disturbing the workflow of artists as little as possible. They shouldn't need to go through any more hassles than now to keep contributing.
 
The general idea of this project is to introduce sprite sheets and their memory, loading time and disk space benefits, while disturbing the workflow of artists as little as possible. They shouldn't need to go through any more hassles than now to keep contributing.
  
How I'll achieve this is by introducing a distinction between source material (what artists work with) and generated material (what the game engine actually uses). Note that the differences between the two will be small enough that the game engine will still be able to run using source material directly, as if sprite sheets had never been added.
+
How I'll achieve this is by introducing a distinction between source material (human-friendly material artists work with) and generated material (optimized, memory friendly material that the game engine actually uses). The differences between the two will be small enough that the game engine will still be able to run using source material directly, as if sprite sheets had never been added.
 +
 
 +
After discussing sprite sheets at lenght with various wesnoth developers and artists (both [http://forums.wesnoth.org/viewtopic.php?f=2&t=29311&start=0 in this thread] and on IRC), I have concluded that there currently isn't a common opinion on how sprite sheets should be implemented. My source/generated material distinction, in particular, was deemed interesting by some but doesn't gather unanimity. I've therefore revised this proposal to be flexible enough to handle any change in policy that might happen mid-GSoC or later. [[GSoC-SpriteSheets_Gabba#Uniform_grid_sprite_sheets_output| This]] in particular should ensure my proposal stays relevant no matter what.
  
 
==Source material==
 
==Source material==
* Keep individual pngs on svn. Makes it easier for artists. If some artists prefer to work directly with spritesheets, no problem, I'll accept that as input as well, by taking them apart and treating them as a set of individual images.
+
It will be possible to keep '''individual pngs''' on s&shy;&shy;v&shy;&shy;n, to make life easier for artists which prefer working like that.
* Keep WML .cfg files for unit animations as they are now, i.e. have them refer to individual .png files. (Artists can instead use a part of their own sprite sheet through the already implemented [http://wiki.wesnoth.org/ImagePathFunctionWML#Crop_Function ~CROP()] functor.) Makes it easier to create animations and see what are the frames of an animation.
+
* Some artists would prefer to work directly with spritesheets, and the general policy of Wesnoth may end up stating that all artists must work with those (not sure, since up to now I've seen widely varying opinions among devs and artists on the topic). Therefore I will also offer support for what we could call '''"uniform grid" sprite sheets''' such as this one:<br>http://forums.wesnoth.org/download/file.php?id=39338#.png
 +
*Support is in fact already in Wesnoth for this kind of sprite sheet: an artist can put one together manually, which is easy if you're starting a unit from scratch, and use<br>
 +
  my_sprite_sheet.png~CROP(''sprite_sheet_region'')
 +
in WML to refer to individual frames. [[ImagePathFunctionWML#Crop_Function| ~CROP()]] is currently not memory-efficient, but I will fix it as part of my project.
 +
*I'll add support to my sprite-sheet-building tool to generate this kind of sprite sheet (in addition to the optimized ones) from a unit's existing animation frames.
 +
See [[GSoC-SpriteSheets_Gabba#Uniform_grid_sprite_sheets_output| Uniform grid sprite sheets output]] for more details.
 +
 
 +
In the context of my new system, both individual images and uniform grid sprite sheets are the equivalent of "source code", that is, they are what contributors work with since it's handy and "human-friendly". However in the build process I intend to reorganize all frames freely to place them onto optimized sprite sheets, "compiled code" that's only intended to be used by the game engine.
 +
 
 +
* People will keep using the same syntax to define animations within WML .cfg files. See [[GSoC-SpriteSheets_Gabba#Artists.27_workflow| Artist's workflow]] for examples. Once again, those will be the "source code" people work with, and during the build process I'll make copies of these animation files with updated image references to point to the optimized sprite sheets. These generated sprite sheets will be the "compiled" version that the game engine uses.
  
 
==Generated material==
 
==Generated material==
Optimized sprite sheets will be generated as part of the wesnoth build process, and new WML animation files will be produced, which are identical to the source ones, except for image data which now refers to the correct location within sprite sheets. This will be done with a single, highly configurable command-line tool based on the ClanLib texture packer, that gets called from the current build scripts (scons, cmake, autoconf).
+
Optimized sprite sheets will be generated as part of the wesnoth build process, and new WML animation files will be produced, which are identical to the source ones, except for image data which now refers to the correct location within sprite sheets. This will be done with a single, highly configurable command-line tool based on the ClanLib texture packer, that will get called from the current build scripts (scons, cmake, autoconf).
  
 
The new tool will work by following those steps:
 
The new tool will work by following those steps:
Line 28: Line 46:
 
# Extract the list of image locations from those WML files
 
# Extract the list of image locations from those WML files
 
#* If some image locations are actually references (through ~CROP) to part of a hand-made sprite sheet, each individual reference will be treated as an individual image in the following steps
 
#* If some image locations are actually references (through ~CROP) to part of a hand-made sprite sheet, each individual reference will be treated as an individual image in the following steps
# Use the image list to build sprite sheets of the size specified, cramming as many images as possible into each one using a bin-packing algorithm
+
# Use the image list to build sprite sheets of the size specified, cramming as many images as possible into each one using a bin-packing algorithm (by default: the one already implemented in the ClanLib tool)
 
# Output copies of the original WML files, updating the image references to point to the proper location within my sprite sheets.
 
# Output copies of the original WML files, updating the image references to point to the proper location within my sprite sheets.
  
There are several design choices to make here:
+
The tool I'm planning will let the packagers enter sets of directories/files with WML animation descriptions, and out come the corresponding sprite sheets. This will allow testing per-campaign/per-faction/per-unit sprite sheets, or any other grouping we can think of. The most memory-efficient approach will probably to make per-unit sprite sheets (since its frames are usually loaded together in memory).
* do we mix all sprites from official content together? (Best for disk space, but wastes memory as you may load a whole sheet for a single image.)
 
* do we do per-campaign/per-faction sprite sheets? (Probably best for memory, still ok on disk space, and we're forced to do this for non-mainline content)
 
* we should probably allow a mix of both and let the packagers enter a set of directories with WML animation descriptions, and out come the corresponding sprite sheets.
 
  
 
When distributing the game (except in source form), we'd include only spritesheets and the generated .cfg files, not original .png or .cfg files.
 
When distributing the game (except in source form), we'd include only spritesheets and the generated .cfg files, not original .png or .cfg files.
*This said, we could consider doing an "artist distribution" of the game, that includes the unprocessed images and WML files, so they can browse this material in a more friendly format, without having to use svn. I would also give them a better idea of the preferred format in which to submit their work.
+
*This said, we could consider doing an "artist distribution" of the game, that includes the unprocessed images and WML files, so they can browse this material in a more friendly format, without having to use s&shy;&shy;v&shy;&shy;n. I would also give them a better idea of the preferred format in which to submit their work.
  
 
==The tool==
 
==The tool==
As far as generating the sprite sheets themselves, I'll borrow a maximum of code from the program below (licence is BSD) and adapt their GUI for testing and to complement the automated process:
+
To make the sprite sheet generator tool I've been referring to, I'll borrow a maximum of code from this program; ([http://www.clanlib.org/license.html licence] is a very liberal BSD) and add a command-line interface:
  
 
''ClanLib texture packer''
 
''ClanLib texture packer''
 
     http://www.rtsoft.com/forums/showthread.php?t=2518
 
     http://www.rtsoft.com/forums/showthread.php?t=2518
 
     http://www.clanlib.org/beta/index.php/Examples#Screenshots_from_ClanLib-2.0.2FUtilities
 
     http://www.clanlib.org/beta/index.php/Examples#Screenshots_from_ClanLib-2.0.2FUtilities
http://www.clanlib.org/beta/images/b/bd/Example_texturepacker.png
+
 
 +
*Since I only really need the core algorithm of the texture packer and can possibly even dump the GUI, I'm not yet sure whether trying to get my changes integrated into ClanLib is a good idea. After all, having ClanLib as a build dependency wouldn't be very nice for Wesnoth. I'll contact their community at the beginning of May to see what's their interest in making the tool a separate package, and integrating some of my changes.
 +
**I'll consider writing a separate tool that uses their XML output to fill my WML image references if that makes collaboration easier with them.
 
*This program takes .png with transparency as input and output, so no problem there.
 
*This program takes .png with transparency as input and output, so no problem there.
*I'll modify the GUI and especially provide a command-line interface, to allow integration with the build process. Unless there's a very good case for introducing a new dependency, the modified program won't add any new dependencies to Wesnoth or its build process.
+
*I'll modify (or dump) the GUI and especially provide a command-line interface, to allow integration with the build process. Unless there's a very good case for introducing a new dependency, the modified program won't add any new dependencies to Wesnoth or its build process.<br>Planned command line features (syntax will be determined after implementing and testing):
*The program currently outputs XML with info of where individual images ended up in the sprite sheets; I'll adapt this code to output modified WML .cfg files, as explained above.
+
** Defines sets of folders with WML files from which to extract image references and build the sprite sheets: sprites from different sets are not mixed on the same sprite sheets. Those sets can be read from standard input or a text file.
 +
** Possibility of launching multiple jobs to work on independent image sets (how this interacts with the build system options needs to be determined).
 +
** Configurable name generation for the sprite sheet files
 +
** Configurable sprite sheet size, i.e. 512x512, 1024x1024,etc.
 +
** Choose the type of sprite sheet produced: optimized or uniform grid
 +
 
 +
*The program currently outputs XML with info of where individual images ended up in the sprite sheets; I'll adapt this code to output modified WML .cfg files.
  
 
Note: before picking the ClanLib tool as the base for my work, I evaluated the following ones:
 
Note: before picking the ClanLib tool as the base for my work, I evaluated the following ones:
Line 56: Line 79:
 
     http://slick.cokeandcode.com/demos/packer.jnlp
 
     http://slick.cokeandcode.com/demos/packer.jnlp
 
     http://homepage.ntlworld.com/config/imagepacker/
 
     http://homepage.ntlworld.com/config/imagepacker/
 +
===Planned output===
 +
Since the needs of Wesnoth regarding Sprite Sheets are as yet unclear, I intend to provide two types of outputs to meet the two main use cases:
 +
====Optimized sprite sheets output====
 +
As explained in detail above, the main feature of the tool will be the production of optimized sprite sheets where individual frames are placed by the already implemented algorithm, in order to save as much space as possible. Example of what the ClanLib tool can already do:
 +
http://www.clanlib.org/beta/images/b/bd/Example_texturepacker.png
 +
====Uniform grid sprite sheets output====
 +
Taking existing .pngs for one unit, and putting them together on a uniform grid sprite sheet with which an artist can work directly, may be desirable. However this is not trivial, since from what I understood there's zero guarantee that even frames of the same animation will be of the same size.
  
==The algorithm(s)==
+
I will add a feature to the tool that attempts to generate the best uniform grid sprite sheet possible from a set of images you designate; this generation will follow these steps, and any choice involved will be configurable on the commmand line:
Once all the above is done, I'll spend any remaining time trying to improve the placement of images in the sprite sheets, which may seem to be nitpicking but could get crucial for low-memory devices.
+
#Extract image list (for instance, all the frames of the Drake Burner)
''Misc research links about this:''
+
#Detect and sort together all images that are of the same height AND/OR attempt to detect the animation order in the WML file, so that related frames are placed together and in order
    http://en.wikipedia.org/wiki/Bin_packing_problem
+
#Place rows of sorted images on the sprite sheet, leaving a configurable amount of padding between images
    http://code.google.com/p/caparf/
+
#Surround each image with a border of configurable width, to help the artists know where each image stops
    http://scholar.google.com/scholar?q=%22Packing+Rectangular+Pieces+-+A+Heuristic+Approach.%22
+
#Output modified WML referring to the new image locations within sprite sheets
 +
As a reminder, this is an uniform grid sprite sheet:<br>http://forums.wesnoth.org/download/file.php?id=39338#.png
 +
 
 +
Depending on what the Wesnoth policy finally becomes, these sheets and WML files can either be used both by contributors and the game engine directly; or they can be just used by contributors and used by my tool as input to generate optimized sprite sheets during the build process.
 +
 
 +
==Interaction with macros==
 +
 
 +
WML macros are sometimes used to generate a set of image paths; the exact extent of this use has not been measured. With macros involved, automatically replacing the image path to refer to the spreadsheet instead of the individual image is not so easy. There are several solutions to consider here, depending of the volume of WML code that presents this behavior:
 +
* If they are not significantly numerous to pose a performance problem, ignore macro-generated image paths, period.
 +
* Instead of ignoring them, we could manually put the images that would be referenced by the macro in a sprite sheet, and rewrite the macro so it generates a set of sprite sheet locations instead of a set of image names.
 +
* Provide some kind of "redirection", i.e. a system that knows both the original and generated location of images, and can direct the query to the right place. A small modification to the image locator and an automatically generated text file (with original and new locations) in each image folder would be enough.
 +
 
 +
==Caching adjustments==
 +
 
 +
The ~CROP() function (or something equivalent) is an essential part of making sprite sheets work in Wesnoth. However some [http://forums.wesnoth.org/viewtopic.php?f=2&t=29311&p=417828#p417828 new info surfaced], indicating that a spritesheet mechanism built around ~CROP() as it is now would actually cause the caching mechanism to use more memory. Definitely not a good thing, therefore some adjustments to the caching mechanism will be in order. I want the spritesheet to be loaded only once and then referenced as needed, instead of each sub-image being cached individually in addition to the sprite sheet.
 +
 
 +
Code relevent to ~CROP:
 +
* The locator::locator() constructor calls locator::init_index(), that calculates an image hash from the whole image path, including functors. I'll introduce special treatment for the ~CROP functor here, so that it is ignored in the hash generation ''if the image path only contains ~CROP functors''. This will allow crops of the same image to be considered as identical by the caching system. A mix of ~CROP and other functors can't be ignored in the hash, since the result of those operations is potentially too complex to quickly regenerate from the original image.
 +
* In locator::parse_arguments(), the presence of functors sets the SUB_FILE locator type, and stores the various functors in a string. I'll add here a new property to locators to identify if they are an image crop; this property will be returned via locator::cropped().
 +
* In image::get_image, the following checks if the image locator is cached, and then returns the corresponding surface immediately if it's the case:
 +
 
 +
  if(i_locator.in_cache(*imap))
 +
      return i_locator.locate_in_cache(*imap);
 +
 
 +
I'll modify this to get special treatment for crops:
 +
 
 +
  if(i_locator.in_cache(*imap)) {
 +
      if (i_locator.cropped()) {
 +
          // GET THE RIGHT SUB-SURFACE FROM CACHED IMAGE
 +
          // AND USE IT AS BASE FOR THE OPERATIONS IN THE REST OF get_image()
 +
      } else {
 +
          return i_locator.locate_in_cache(*imap);
 +
      }
 +
  }
 +
 
 +
My explorations of the source code suggested that in some circumstances almost all images are scaled, for example to support the zoom function. To cover cases like this, I can arrange for the cache to store the whole scaled sprite sheet, instead of letting it cache individual scaled crops.
  
 
=Artists' workflow=
 
=Artists' workflow=
So, how would implementing this system affect how artists work now? In short: not at all, once they've understood the distinction between source and generated content, as you can see below:
+
So, supposing the source vs generated material distinction is introduced, how would it affect how artists work now? In short: not at all, once they've understood the distinction between source and generated content, as you can see below:
  
 
''Concrete example from the drake glider (Glider.cfg):''
 
''Concrete example from the drake glider (Glider.cfg):''
*What it'll look like on svn (i.e., same as now):
+
*What it'll look like on s&shy;&shy;v&shy;&shy;n or in the potential "artists' distro" (i.e., same as now):
 
   [attack_anim]
 
   [attack_anim]
 
       (...)
 
       (...)
Line 88: Line 153:
 
   [/attack_anim]
 
   [/attack_anim]
  
*What an artist can change it to (in either the svn source or the packaged version she downloaded from the http://www.wesnoth.org/ front page) in order to test a new image:
+
*What an artist can change it to (in '''any''' version of the game, be it s&shy;&shy;v&shy;&shy;n, artists' distro or regular package), in order to test a new image:
 
   [attack_anim]
 
   [attack_anim]
 
       (...)
 
       (...)
Line 106: Line 171:
 
       (...)
 
       (...)
 
   [/attack_anim]
 
   [/attack_anim]
 +
 +
=Possible use for the future OpenGL Wesnoth=
 +
Wesnoth plans to eventually move to OpenGL. What I've heard about OpenGL texture handling is that it doesn't work too well with a myriad of small textures; this was actually the main motivation for the ClanLib folks to develop their texture packer. To quote one of their devs: "This really helps performance, as the ClanLib now can batch all the sprite drawing commands efficiently, as it won't have to change the texture state."
 +
 +
I think it would be beneficial to Wesnoth if I adapted the core algorithm of my sprite-packing tool in such a way that it's easy to eventually integrate into Wesnoth itself. The reason is the numerous modifications such as flipping, scaling and recoloring that are done to images; with OpenGL, caching them tightly packed on large textures would be much more efficient than keeping them separate. Using my adapted ClanLib algorithm, OpenGL Wesnoth could efficiently organise and store in-memory every modified image it generates. Either it would progressively add them to a large OpenGL texture (if feasible), or it would keep the large texture apart and send it to OpenGL when it's full, to replace the corresponding small ones.
 +
 +
=Optional Features=
 +
==The algorithm(s)==
 +
Once all the above is done, I want to improve the placement of images in the sprite sheets, which may seem to be nitpicking but could provide benefits for low-memory devices.
 +
Misc research links:
 +
    http://en.wikipedia.org/wiki/Bin_packing_problem
 +
    http://code.google.com/p/caparf/
 +
    http://scholar.google.com/scholar?q=%22Packing+Rectangular+Pieces+-+A+Heuristic+Approach.%22
 +
 +
If I really, really have extra time to kill and the space benefits seem to be worth it, I'll investigate the possibility of overlapping identical parts of images (such as transparent areas) so I can pack the sprites even closer together. For sprites that have a lot of empty corner space, it could have a measurable effect.
 +
 +
==Improved support for custom sprite sheets==
 +
(Very, very optional.) To help working with handmade sprite sheets without having to use CROP every time, I would like to add a new WML tag that can define several frames at a time, provided the user specifies the rectangular area and the padding. Such frames could be referenced later in the WML animation code through an ID and their sequence number in the sprite sheet.
  
 
=Milestones and Calendar=
 
=Milestones and Calendar=
Before GSoC, poke a bit more inside the code of ClanLib Texture Packer, and continue to evaluate alternate candidates. Do a few spritesheet tests to try and locate problems that could affect this project.
+
 
 
GSoC start according to Google's calendar: May 24
 
GSoC start according to Google's calendar: May 24
* Add a command line interface to the ClanLib app, and test generations of sets of spritesheets of various sizes, using a list of image folders as input. Discuss design issues for the following milestones.
+
* Modify the Wesnoth caching code so that ~CROP actually saves memory with sprite sheets. Benchmark resulting memory savings. Investigate what to do with macros in image paths.
 
**''Deadline: June 7''
 
**''Deadline: June 7''
* Integrate parsing of WML files with animation data to harvest the list of images (and parts of images) to use as input. Adapt the ClanLib app's current interface to my testing needs.
+
* Add a command line interface to the ClanLib app, and test generations of sets of spritesheets of various sizes, using a list of image folders as input. Adapt the ClanLib app's current interface to testing needs.
 
**''Deadline: June 21''
 
**''Deadline: June 21''
* Output updated WML files with the new location of images within spritesheets.
+
* Integrate parsing of WML files with animation data to harvest the list of images (and parts of images) to use as input. Output updated WML files with the new location of images within spritesheets.
 
**''Deadline: July 5''
 
**''Deadline: July 5''
* Start integration of the tool with the Wesnoth build process.
+
* Start integration of the tool with the Wesnoth build process. Expand command line interface.
 
**''Deadline: July 16 (Mid-term evaluation)''
 
**''Deadline: July 16 (Mid-term evaluation)''
* Finish integration with the build process, do final adjustments to UI, do memory benchmarks and resolve caching issues, document stuff
+
* Finish integration with the build process, do final cleanup of modified ClanLib tool, do memory benchmarks, document stuff
 
**''Deadline: August 9''
 
**''Deadline: August 9''
* If things go faster than planned, implement various bin-packing algorithms to try and do even better than the clanlib texture packer. Test them with various spritesheet sizes and various sets of images.
+
* If things go faster than planned, implement as much as possible from Optional Features above.

Latest revision as of 23:21, 20 March 2013


This page is related to Summer of Code 2010
See the list of Summer of Code 2010 Ideas



This is a Summer of Code 2010 student page
Project: SoC Ideas SpriteSheets


Description

Gabba - Sprite Sheets

I developed an approach to introduce sprite sheets to Wesnoth with minimal hassle for artists, and as little modifications to game code as possible. I support generation of various sizes of optimized sprite sheets, so we can adapt to various platform and memory/disk requirements. My system will rely on a single external tool based on an existing open-source solution.

Updated 04/09/2010

IRC

gabba

SoC Application

Wesnoth Sprite Sheets

About Me

See User:Gabba.

Project

The general idea of this project is to introduce sprite sheets and their memory, loading time and disk space benefits, while disturbing the workflow of artists as little as possible. They shouldn't need to go through any more hassles than now to keep contributing.

How I'll achieve this is by introducing a distinction between source material (human-friendly material artists work with) and generated material (optimized, memory friendly material that the game engine actually uses). The differences between the two will be small enough that the game engine will still be able to run using source material directly, as if sprite sheets had never been added.

After discussing sprite sheets at lenght with various wesnoth developers and artists (both in this thread and on IRC), I have concluded that there currently isn't a common opinion on how sprite sheets should be implemented. My source/generated material distinction, in particular, was deemed interesting by some but doesn't gather unanimity. I've therefore revised this proposal to be flexible enough to handle any change in policy that might happen mid-GSoC or later. This in particular should ensure my proposal stays relevant no matter what.

Source material

It will be possible to keep individual pngs on s­­v­­n, to make life easier for artists which prefer working like that.

  • Some artists would prefer to work directly with spritesheets, and the general policy of Wesnoth may end up stating that all artists must work with those (not sure, since up to now I've seen widely varying opinions among devs and artists on the topic). Therefore I will also offer support for what we could call "uniform grid" sprite sheets such as this one:
    file.php?id=39338#.png
  • Support is in fact already in Wesnoth for this kind of sprite sheet: an artist can put one together manually, which is easy if you're starting a unit from scratch, and use
 my_sprite_sheet.png~CROP(sprite_sheet_region)

in WML to refer to individual frames. ~CROP() is currently not memory-efficient, but I will fix it as part of my project.

  • I'll add support to my sprite-sheet-building tool to generate this kind of sprite sheet (in addition to the optimized ones) from a unit's existing animation frames.

See Uniform grid sprite sheets output for more details.

In the context of my new system, both individual images and uniform grid sprite sheets are the equivalent of "source code", that is, they are what contributors work with since it's handy and "human-friendly". However in the build process I intend to reorganize all frames freely to place them onto optimized sprite sheets, "compiled code" that's only intended to be used by the game engine.

  • People will keep using the same syntax to define animations within WML .cfg files. See Artist's workflow for examples. Once again, those will be the "source code" people work with, and during the build process I'll make copies of these animation files with updated image references to point to the optimized sprite sheets. These generated sprite sheets will be the "compiled" version that the game engine uses.

Generated material

Optimized sprite sheets will be generated as part of the wesnoth build process, and new WML animation files will be produced, which are identical to the source ones, except for image data which now refers to the correct location within sprite sheets. This will be done with a single, highly configurable command-line tool based on the ClanLib texture packer, that will get called from the current build scripts (scons, cmake, autoconf).

The new tool will work by following those steps:

  1. Take command line parameters:
    • A number of existing WML (.cfg) animation files as input (could be a whole directory, a set of directories, individual files, whatever)
    • A target sprite sheet size, for instance 512x512 (optimal size probably depends on target platform memory capabilities)
  2. Extract the list of image locations from those WML files
    • If some image locations are actually references (through ~CROP) to part of a hand-made sprite sheet, each individual reference will be treated as an individual image in the following steps
  3. Use the image list to build sprite sheets of the size specified, cramming as many images as possible into each one using a bin-packing algorithm (by default: the one already implemented in the ClanLib tool)
  4. Output copies of the original WML files, updating the image references to point to the proper location within my sprite sheets.

The tool I'm planning will let the packagers enter sets of directories/files with WML animation descriptions, and out come the corresponding sprite sheets. This will allow testing per-campaign/per-faction/per-unit sprite sheets, or any other grouping we can think of. The most memory-efficient approach will probably to make per-unit sprite sheets (since its frames are usually loaded together in memory).

When distributing the game (except in source form), we'd include only spritesheets and the generated .cfg files, not original .png or .cfg files.

  • This said, we could consider doing an "artist distribution" of the game, that includes the unprocessed images and WML files, so they can browse this material in a more friendly format, without having to use s­­v­­n. I would also give them a better idea of the preferred format in which to submit their work.

The tool

To make the sprite sheet generator tool I've been referring to, I'll borrow a maximum of code from this program; (licence is a very liberal BSD) and add a command-line interface:

ClanLib texture packer

   http://www.rtsoft.com/forums/showthread.php?t=2518
   http://www.clanlib.org/beta/index.php/Examples#Screenshots_from_ClanLib-2.0.2FUtilities
  • Since I only really need the core algorithm of the texture packer and can possibly even dump the GUI, I'm not yet sure whether trying to get my changes integrated into ClanLib is a good idea. After all, having ClanLib as a build dependency wouldn't be very nice for Wesnoth. I'll contact their community at the beginning of May to see what's their interest in making the tool a separate package, and integrating some of my changes.
    • I'll consider writing a separate tool that uses their XML output to fill my WML image references if that makes collaboration easier with them.
  • This program takes .png with transparency as input and output, so no problem there.
  • I'll modify (or dump) the GUI and especially provide a command-line interface, to allow integration with the build process. Unless there's a very good case for introducing a new dependency, the modified program won't add any new dependencies to Wesnoth or its build process.
    Planned command line features (syntax will be determined after implementing and testing):
    • Defines sets of folders with WML files from which to extract image references and build the sprite sheets: sprites from different sets are not mixed on the same sprite sheets. Those sets can be read from standard input or a text file.
    • Possibility of launching multiple jobs to work on independent image sets (how this interacts with the build system options needs to be determined).
    • Configurable name generation for the sprite sheet files
    • Configurable sprite sheet size, i.e. 512x512, 1024x1024,etc.
    • Choose the type of sprite sheet produced: optimized or uniform grid
  • The program currently outputs XML with info of where individual images ended up in the sprite sheets; I'll adapt this code to output modified WML .cfg files.

Note: before picking the ClanLib tool as the base for my work, I evaluated the following ones:

   http://spritesheetpacker.codeplex.com/
   http://www.imagemagick.org/script/montage.php
   BlitzBasic ImagePacker
   http://slick.cokeandcode.com/demos/packer.jnlp
   http://homepage.ntlworld.com/config/imagepacker/

Planned output

Since the needs of Wesnoth regarding Sprite Sheets are as yet unclear, I intend to provide two types of outputs to meet the two main use cases:

Optimized sprite sheets output

As explained in detail above, the main feature of the tool will be the production of optimized sprite sheets where individual frames are placed by the already implemented algorithm, in order to save as much space as possible. Example of what the ClanLib tool can already do: Example_texturepacker.png

Uniform grid sprite sheets output

Taking existing .pngs for one unit, and putting them together on a uniform grid sprite sheet with which an artist can work directly, may be desirable. However this is not trivial, since from what I understood there's zero guarantee that even frames of the same animation will be of the same size.

I will add a feature to the tool that attempts to generate the best uniform grid sprite sheet possible from a set of images you designate; this generation will follow these steps, and any choice involved will be configurable on the commmand line:

  1. Extract image list (for instance, all the frames of the Drake Burner)
  2. Detect and sort together all images that are of the same height AND/OR attempt to detect the animation order in the WML file, so that related frames are placed together and in order
  3. Place rows of sorted images on the sprite sheet, leaving a configurable amount of padding between images
  4. Surround each image with a border of configurable width, to help the artists know where each image stops
  5. Output modified WML referring to the new image locations within sprite sheets

As a reminder, this is an uniform grid sprite sheet:
file.php?id=39338#.png

Depending on what the Wesnoth policy finally becomes, these sheets and WML files can either be used both by contributors and the game engine directly; or they can be just used by contributors and used by my tool as input to generate optimized sprite sheets during the build process.

Interaction with macros

WML macros are sometimes used to generate a set of image paths; the exact extent of this use has not been measured. With macros involved, automatically replacing the image path to refer to the spreadsheet instead of the individual image is not so easy. There are several solutions to consider here, depending of the volume of WML code that presents this behavior:

  • If they are not significantly numerous to pose a performance problem, ignore macro-generated image paths, period.
  • Instead of ignoring them, we could manually put the images that would be referenced by the macro in a sprite sheet, and rewrite the macro so it generates a set of sprite sheet locations instead of a set of image names.
  • Provide some kind of "redirection", i.e. a system that knows both the original and generated location of images, and can direct the query to the right place. A small modification to the image locator and an automatically generated text file (with original and new locations) in each image folder would be enough.

Caching adjustments

The ~CROP() function (or something equivalent) is an essential part of making sprite sheets work in Wesnoth. However some new info surfaced, indicating that a spritesheet mechanism built around ~CROP() as it is now would actually cause the caching mechanism to use more memory. Definitely not a good thing, therefore some adjustments to the caching mechanism will be in order. I want the spritesheet to be loaded only once and then referenced as needed, instead of each sub-image being cached individually in addition to the sprite sheet.

Code relevent to ~CROP:

  • The locator::locator() constructor calls locator::init_index(), that calculates an image hash from the whole image path, including functors. I'll introduce special treatment for the ~CROP functor here, so that it is ignored in the hash generation if the image path only contains ~CROP functors. This will allow crops of the same image to be considered as identical by the caching system. A mix of ~CROP and other functors can't be ignored in the hash, since the result of those operations is potentially too complex to quickly regenerate from the original image.
  • In locator::parse_arguments(), the presence of functors sets the SUB_FILE locator type, and stores the various functors in a string. I'll add here a new property to locators to identify if they are an image crop; this property will be returned via locator::cropped().
  • In image::get_image, the following checks if the image locator is cached, and then returns the corresponding surface immediately if it's the case:
 if(i_locator.in_cache(*imap))
     return i_locator.locate_in_cache(*imap);

I'll modify this to get special treatment for crops:

 if(i_locator.in_cache(*imap)) {
     if (i_locator.cropped()) {
         // GET THE RIGHT SUB-SURFACE FROM CACHED IMAGE
         // AND USE IT AS BASE FOR THE OPERATIONS IN THE REST OF get_image()
     } else {
         return i_locator.locate_in_cache(*imap);
     }
 }

My explorations of the source code suggested that in some circumstances almost all images are scaled, for example to support the zoom function. To cover cases like this, I can arrange for the cache to store the whole scaled sprite sheet, instead of letting it cache individual scaled crops.

Artists' workflow

So, supposing the source vs generated material distinction is introduced, how would it affect how artists work now? In short: not at all, once they've understood the distinction between source and generated content, as you can see below:

Concrete example from the drake glider (Glider.cfg):

  • What it'll look like on s­­v­­n or in the potential "artists' distro" (i.e., same as now):
  [attack_anim]
      (...)
       [frame]
           duration=100
           image="units/drakes/glider-kick-1.png"
       [/frame]
      (...)
  [/attack_anim]
  • What it'll look like after processing through my system, and therefore in your packaged copy of the game:
  [attack_anim]
      (...)
       [frame]
           duration=100
           image="units/drakes/drakes_sprite_sheet.png~CROP(0,0,20,20)"
       [/frame]
      (...)
  [/attack_anim]
  • What an artist can change it to (in any version of the game, be it s­­v­­n, artists' distro or regular package), in order to test a new image:
  [attack_anim]
      (...)
       [frame]
           duration=100
           image="units/drakes/My_New_Fancy_Glider_Kick_1.png"
       [/frame]
      (...)
  [/attack_anim]
  • Or she could use this, too, to refer to her own image sheet or strip (this is already possible):
  [attack_anim]
      (...)
       [frame]
           duration=100
           image="MY_OWN_SPRITE_SHEET.png~CROP(10,10,30,30)"
       [/frame]
      (...)
  [/attack_anim]

Possible use for the future OpenGL Wesnoth

Wesnoth plans to eventually move to OpenGL. What I've heard about OpenGL texture handling is that it doesn't work too well with a myriad of small textures; this was actually the main motivation for the ClanLib folks to develop their texture packer. To quote one of their devs: "This really helps performance, as the ClanLib now can batch all the sprite drawing commands efficiently, as it won't have to change the texture state."

I think it would be beneficial to Wesnoth if I adapted the core algorithm of my sprite-packing tool in such a way that it's easy to eventually integrate into Wesnoth itself. The reason is the numerous modifications such as flipping, scaling and recoloring that are done to images; with OpenGL, caching them tightly packed on large textures would be much more efficient than keeping them separate. Using my adapted ClanLib algorithm, OpenGL Wesnoth could efficiently organise and store in-memory every modified image it generates. Either it would progressively add them to a large OpenGL texture (if feasible), or it would keep the large texture apart and send it to OpenGL when it's full, to replace the corresponding small ones.

Optional Features

The algorithm(s)

Once all the above is done, I want to improve the placement of images in the sprite sheets, which may seem to be nitpicking but could provide benefits for low-memory devices. Misc research links:

   http://en.wikipedia.org/wiki/Bin_packing_problem
   http://code.google.com/p/caparf/
   http://scholar.google.com/scholar?q=%22Packing+Rectangular+Pieces+-+A+Heuristic+Approach.%22

If I really, really have extra time to kill and the space benefits seem to be worth it, I'll investigate the possibility of overlapping identical parts of images (such as transparent areas) so I can pack the sprites even closer together. For sprites that have a lot of empty corner space, it could have a measurable effect.

Improved support for custom sprite sheets

(Very, very optional.) To help working with handmade sprite sheets without having to use CROP every time, I would like to add a new WML tag that can define several frames at a time, provided the user specifies the rectangular area and the padding. Such frames could be referenced later in the WML animation code through an ID and their sequence number in the sprite sheet.

Milestones and Calendar

GSoC start according to Google's calendar: May 24

  • Modify the Wesnoth caching code so that ~CROP actually saves memory with sprite sheets. Benchmark resulting memory savings. Investigate what to do with macros in image paths.
    • Deadline: June 7
  • Add a command line interface to the ClanLib app, and test generations of sets of spritesheets of various sizes, using a list of image folders as input. Adapt the ClanLib app's current interface to testing needs.
    • Deadline: June 21
  • Integrate parsing of WML files with animation data to harvest the list of images (and parts of images) to use as input. Output updated WML files with the new location of images within spritesheets.
    • Deadline: July 5
  • Start integration of the tool with the Wesnoth build process. Expand command line interface.
    • Deadline: July 16 (Mid-term evaluation)
  • Finish integration with the build process, do final cleanup of modified ClanLib tool, do memory benchmarks, document stuff
    • Deadline: August 9
  • If things go faster than planned, implement as much as possible from Optional Features above.
This page was last edited on 20 March 2013, at 23:21.