MERGE gcompris_7-4 UNTESTED

MERGE gcompris_7-4
UNTESTED

16 files changed, 1138 insertions, 0 deletions

diff --git a/tools/list_missing_sounds.sh b/tools/list_missing_sounds.sh
new file mode 100755
index 0000000..411ea0c
--- /dev/null
+++ b/tools/list_missing_sounds.sh
@@ -0,0 +1,45 @@
+#!/bin/sh
+#
+# Copyright (C) 2006 Jose JORGE
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+#
+#######################################################################
+#
+# This script lists the sounds missing in some locale compared to english
+# It much be run with the list of locale sound you want to compare
+# list_missing_sounds fr en de
+#
+snd_path="boards/sounds/"
+reference="en"
+
+if test "$1" == ""
+then
+  echo "Usage: $0 <locale>"
+  echo "With locale being a locale as found in boards/sounds like fr"
+  echo "Run it in the GCompris root directory"
+  exit 1
+fi
+
+for locale in $@
+do
+  if test -d boards/sounds/$locale; then 
+	  find $snd_path$locale | grep .ogg > ~/tmp/sounds_$locale.lst
+	  find $snd_path$reference | grep .ogg | sed s+/$reference/+/$locale/+ > ~/tmp/sounds_$reference.lst
+	  echo "The sounds avaliable in $reference that miss in $locale are :"
+	  grep -v -f ~/tmp/sounds_$locale.lst ~/tmp/sounds_$reference.lst
+  fi
+done
+rm ~/tmp/sounds_$locale.lst ~/tmp/sounds_$reference.lst
diff --git a/tools/shapegame/HOWTO b/tools/shapegame/HOWTO
new file mode 100644
index 0000000..d2c8bbe
--- /dev/null
+++ b/tools/shapegame/HOWTO
@@ -0,0 +1,114 @@
+#
+#  creating region puzzle for germany
+#
+#
+# 1. got map from wikipedia ->
+#    source/Deutschland_Bundeslaender_1990_thresshold.tif
+# 
+# 2. used gimp to extract individual regions by filling all others with
+#    white and save them as "bayern.png" etc. The size of each
+#    indivudual image must be the same as the full image
+#
+# 3. create the background image by filling the separation lines and 
+#    store it as Deutschland_komplett.png
+# 
+# 4. Now crop away borders and compute the coordiantes for the puzzle
+#    pieces, using pnmcrop from "netpbm" package, and the compute the
+#    target spots with the distance transform, based on the great
+#    algorithm and source code from Pedro F. Felzenszwalb and Daniel
+#    P. Huttenlocher, see http://people.cs.uchicago.edu/~pff/dt/
+# 
+cd ~/gcompris_dev/gcompris/boards/geography/germany_region/source2
+rm -f coordinates.txt
+for i in baden-wuerttemberg.png bayern.png berlin.png brandenburg.png bremen.png hamburg.png hessen.png mecklenburg-vorpommern.png niedersachsen.png nordrhein-westfalen.png rheinland-pfalz.png saarland.png sachsen-anhalt.png sachsen.png schleswig_holstein.png thueringen.png; do
+  echo filename: $i >> coordinates.txt
+  pngtopnm $i |pnmscale 0.8| pnmcrop --white --verbose 2>> coordinates.txt | pnmtopng -transparent white > ../$i
+  echo shape: `pngtopnm ../$i | head -2 | tail -1` >> coordinates.txt 
+  pngtopnm ../$i | ppmtopgm | pgmtopbm -threshold -value 0.9 | pnminvert > binmask.pbm
+  ~/gcompris_dev/gcompris/tool/shapegame/nice_target_spot binmask.pbm target.ppm
+  pnmtopng -transparent white target.ppm > ../target_$i
+done
+
+#
+#  simulate output from pnmcrop for background-image
+#
+
+pngtopnm Deutschland_komplett.png |pnmscale 0.8| pnmtopng -transparent white > ../back.png
+echo filename: back.png >> coordinates.txt 
+echo pnmcrop: cropping 0 rows off the top >> coordinates.txt 
+echo pnmcrop: cropping 0 cols off the left >> coordinates.txt 
+echo shape: `pngtopnm ../back.png | head -2 | tail -1` >> coordinates.txt 
+
+#
+# 5. Now create the xml-file board6_0.xml.in from created
+#   source2/coordinates.txt
+#
+cd ~/gcompris_dev/gcompris/boards/geography/germany_region/source2
+
+cat > realnames.txt <<EOF
+Baden-Württemberg
+Bayern
+Berlin
+Brandenburg
+Bremen
+Hamburg
+Hessen
+Mecklenburg-Vorpommern
+Niedersachsen
+Nordrhein-Westfalen
+Rheinland-Pfalz
+Saarland
+Sachsen-Anhalt
+Sachsen
+Schleswig-Holstein
+Thüringen
+EOF
+
+
+grep "filename:" coordinates.txt | awk '{print $2}' > filenames.txt
+grep "off the left" coordinates.txt | awk '{print $3}' > coords_x.txt
+grep "off the top" coordinates.txt | awk '{print $3}' > coords_y.txt
+grep "shape:" coordinates.txt | awk '{print $2, $3}' > shape.txt
+
+paste filenames.txt coords_x.txt coords_y.txt shape.txt realnames.txt> hurz.txt
+
+echo '<?xml version="1.0" encoding="UTF-8"?>
+<ShapeGame>
+  <Title x="600" y="495" justification="GTK_JUSTIFY_CENTER">
+    <_name>Deutschland Bundesländer</_name>
+  </Title>' > board6_0.xml.in
+
+awk '{ 
+if($1 != "back.png")
+{
+  print "  <Shape name=\"A"NR"\" pixmapfile=\"geography/germany_region/"$1"\" targetfile=\"geography/germany_region/target_"$1"\" x=\""$2+100+$4/2"\" y=\""$3+$5/2"\" zoomx=\"1\" zoomy=\"1\" position=\"0\"><_tooltip>"$6"</_tooltip></Shape>";
+}
+else 
+{
+  print "  <Shape name=\"1\" pixmapfile=\"geography/germany_region/"$1"\" type=\"SHAPE_BACKGROUND\" x=\""$2+100+$4/2"\" y=\""$3+$5/2"\" zoomx=\"1\" zoomy=\"1\" position=\"0\"/>";
+}
+}' < hurz.txt >> board6_0.xml.in
+
+echo '</ShapeGame>' >> board6_0.xml.in
+
+cp -f board6_0.xml.in ../../board6_0.xml.in
+
+
+#
+#  edit gcompris/boards/geography/Makefile.am to include board6_0.xml.in
+#
+
+cd ~/gcompris_dev/gcompris
+intltoolize && automake && autoconf && ./configure --prefix $PWD
+
+cd ~/gcompris_dev/gcompris
+make install
+
+~/gcompris_dev/gcompris/bin/gcompris
+
+
+#
+#  Create the distribution for Bruno
+#
+cd ~/gcompris_dev/
+tar -zcvf germany_regions_2006_01_29.tar.gz gcompris/tool/ gcompris/boards/geography/germany_region/ gcompris/boards/geography/Makefile.am
diff --git a/tools/shapegame/Makefile b/tools/shapegame/Makefile
new file mode 100644
index 0000000..2fcc763
--- /dev/null
+++ b/tools/shapegame/Makefile
@@ -0,0 +1,2 @@
+
+all: nice_target_spot
diff --git a/tools/shapegame/dt/.cvsignore b/tools/shapegame/dt/.cvsignore
new file mode 100644
index 0000000..a33a4d7
--- /dev/null
+++ b/tools/shapegame/dt/.cvsignore
@@ -0,0 +1 @@
+dt
diff --git a/tools/shapegame/dt/Makefile b/tools/shapegame/dt/Makefile
new file mode 100644
index 0000000..91ea042
--- /dev/null
+++ b/tools/shapegame/dt/Makefile
@@ -0,0 +1,23 @@
+INCDIR = -I.
+DBG    = -g
+OPT    = -O3
+CPP    = g++
+CFLAGS = $(DBG) $(OPT) $(INCDIR)
+LINK   = -lm 
+
+.cpp.o:
+	$(CPP) $(CFLAGS) -c $< -o $@
+
+all: dt
+
+dt: dt.cpp 
+	$(CPP) $(CFLAGS) -o dt dt.cpp $(LINK)
+
+clean:
+	/bin/rm -f dt *.o
+
+clean-all: clean
+	/bin/rm -f *~ 
+
+
+
diff --git a/tools/shapegame/dt/README b/tools/shapegame/dt/README
new file mode 100644
index 0000000..ddf45c3
--- /dev/null
+++ b/tools/shapegame/dt/README
@@ -0,0 +1,34 @@
+Implementation of the distance transform algorithm described in:
+
+Distance Transforms of Sampled Functions
+Pedro F. Felzenszwalb and Daniel P. Huttenlocher
+Cornell Computing and Information Science TR2004-1963 
+http://people.cs.uchicago.edu/~pff/dt/
+
+The main program "dt.cpp" computes the standard distance transform of
+a binary image.  The algorithm for computing the transform of a
+sampled function is in "dt.h".
+
+1) Type make to compile "dt".
+
+2) Run "./dt input.pbm output.pgm" to compute the distance transform
+of a binary image.  The input is a binary PBM image and the output is
+a grayscale PGM image.  Note that the actual distance values are
+scaled to fit in the [0-255] grayscale range.
+
+The code in this directory is Copyrighted by Pedro Felzenszwalb and is
+released under GPL:
+
+   Betreff: Re: Gnu public license for your distance transform code?
+   Datum: Sun, 29 Jan 2006 19:20:05 -0600
+   Von: Pedro Felzenszwalb <pff@cs.uchicago.edu>
+   An: Olaf Ronneberger <Olaf@Ronneberger.net>
+   Referenzen: <43DD45AB.1060706@Ronneberger.net>
+
+   Dear Olaf,
+
+   I am glad to hear the code is being used in your software and I am
+   happy to release it under the GPL.
+   Do you need me to send you anything in particular?
+
+   Pedro
diff --git a/tools/shapegame/dt/dt.cpp b/tools/shapegame/dt/dt.cpp
new file mode 100644
index 0000000..214b14d
--- /dev/null
+++ b/tools/shapegame/dt/dt.cpp
@@ -0,0 +1,58 @@
+/* dt - dt.cpp
+ *
+ * Copyright (C) 2006 Pedro Felzenszwalb
+ *
+ *   This program is free software; you can redistribute it and/or modify
+ *   it under the terms of the GNU General Public License as published by
+ *   the Free Software Foundation; either version 2 of the License, or
+ *   (at your option) any later version.
+ *
+ *   This program is distributed in the hope that it will be useful,
+ *   but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *   GNU General Public License for more details.
+ *
+ *   You should have received a copy of the GNU General Public License
+ *   along with this program; if not, write to the Free Software
+ *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+#include <cstdio>
+#include <cstdlib>
+#include <cmath>
+#include "pnmfile.h"
+#include "imconv.h"
+#include "dt.h"
+
+int main(int argc, char **argv) {
+  if (argc != 3) {
+    fprintf(stderr, "usage: %s input(pbm) output(pgm)\n", argv[0]);
+    return 1;
+  }
+
+  char *input_name = argv[1];
+  char *output_name = argv[2];
+
+  // load input
+  image<uchar> *input = loadPBM(input_name);
+
+  // compute dt
+  image<float> *out = dt(input);
+
+  // take square roots
+  for (int y = 0; y < out->height(); y++) {
+    for (int x = 0; x < out->width(); x++) {
+      imRef(out, x, y) = sqrt(imRef(out, x, y));
+    }
+  }
+
+  // convert to grayscale
+  image<uchar> *gray = imageFLOATtoUCHAR(out);
+
+  // save output
+  savePGM(gray, output_name);
+
+  delete input;
+  delete out;
+  delete gray;
+}
diff --git a/tools/shapegame/dt/dt.h b/tools/shapegame/dt/dt.h
new file mode 100644
index 0000000..efe557e
--- /dev/null
+++ b/tools/shapegame/dt/dt.h
@@ -0,0 +1,115 @@
+/* dt - dt.h
+ *
+ * Copyright (C) 2006 Pedro Felzenszwalb
+ *
+ *   This program is free software; you can redistribute it and/or modify
+ *   it under the terms of the GNU General Public License as published by
+ *   the Free Software Foundation; either version 2 of the License, or
+ *   (at your option) any later version.
+ *
+ *   This program is distributed in the hope that it will be useful,
+ *   but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *   GNU General Public License for more details.
+ *
+ *   You should have received a copy of the GNU General Public License
+ *   along with this program; if not, write to the Free Software
+ *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+/* distance transform */
+
+#ifndef DT_H
+#define DT_H
+
+#include <algorithm>
+#include "image.h"
+
+#define INF 1E20
+
+/* dt of 1d function using squared distance */
+static float *dt(float *f, int n) {
+  float *d = new float[n];
+  int *v = new int[n];
+  float *z = new float[n+1];
+  int k = 0;
+  v[0] = 0;
+  z[0] = -INF;
+  z[1] = +INF;
+  for (int q = 1; q <= n-1; q++) {
+    float s  = ((f[q]+square(q))-(f[v[k]]+square(v[k])))/(2*q-2*v[k]);
+    while (s <= z[k]) {
+      k--;
+      s  = ((f[q]+square(q))-(f[v[k]]+square(v[k])))/(2*q-2*v[k]);
+    }
+    k++;
+    v[k] = q;
+    z[k] = s;
+    z[k+1] = +INF;
+  }
+
+  k = 0;
+  for (int q = 0; q <= n-1; q++) {
+    while (z[k+1] < q)
+      k++;
+    d[q] = square(q-v[k]) + f[v[k]];
+  }
+
+  delete [] v;
+  delete [] z;
+  return d;
+}
+
+/* dt of 2d function using squared distance */
+static void dt(image<float> *im) {
+  int width = im->width();
+  int height = im->height();
+  float *f = new float[std::max(width,height)];
+
+  // transform along columns
+  for (int x = 0; x < width; x++) {
+    for (int y = 0; y < height; y++) {
+      f[y] = imRef(im, x, y);
+    }
+    float *d = dt(f, height);
+    for (int y = 0; y < height; y++) {
+      imRef(im, x, y) = d[y];
+    }
+    delete [] d;
+  }
+
+  // transform along rows
+  for (int y = 0; y < height; y++) {
+    for (int x = 0; x < width; x++) {
+      f[x] = imRef(im, x, y);
+    }
+    float *d = dt(f, width);
+    for (int x = 0; x < width; x++) {
+      imRef(im, x, y) = d[x];
+    }
+    delete [] d;
+  }
+
+  delete f;
+}
+
+
+/* dt of binary image using squared distance */
+static image<float> *dt(image<uchar> *im, uchar on = 1) {
+  int width = im->width();
+  int height = im->height();
+
+  image<float> *out = new image<float>(width, height, false);
+  for (int y = 0; y < height; y++) {
+    for (int x = 0; x < width; x++) {
+      if (imRef(im, x, y) == on)
+	imRef(out, x, y) = 0;
+      else
+	imRef(out, x, y) = INF;
+    }
+  }
+
+  dt(out);
+  return out;
+}
+
+#endif
diff --git a/tools/shapegame/dt/image.h b/tools/shapegame/dt/image.h
new file mode 100644
index 0000000..4f385dc
--- /dev/null
+++ b/tools/shapegame/dt/image.h
@@ -0,0 +1,101 @@
+/* dt - image.h
+ *
+ * Copyright (C) 2006 Pedro Felzenszwalb
+ *
+ *   This program is free software; you can redistribute it and/or modify
+ *   it under the terms of the GNU General Public License as published by
+ *   the Free Software Foundation; either version 2 of the License, or
+ *   (at your option) any later version.
+ *
+ *   This program is distributed in the hope that it will be useful,
+ *   but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *   GNU General Public License for more details.
+ *
+ *   You should have received a copy of the GNU General Public License
+ *   along with this program; if not, write to the Free Software
+ *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+/* a simple image class */
+
+#ifndef IMAGE_H
+#define IMAGE_H
+
+#include <cstring>
+
+template <class T>
+class image {
+ public:
+  /* create an image */
+  image(const int width, const int height, const bool init = true);
+
+  /* delete an image */
+  ~image();
+
+  /* init an image */
+  void init(const T &val);
+
+  /* copy an image */
+  image<T> *copy() const;
+  
+  /* get the width of an image. */
+  int width() const { return w; }
+  
+  /* get the height of an image. */
+  int height() const { return h; }
+  
+  /* image data. */
+  T *data;
+  
+  /* row pointers. */
+  T **access;
+  
+ private:
+  int w, h;
+};
+
+/* use imRef to access image data. */
+#define imRef(im, x, y) (im->access[y][x])
+  
+/* use imPtr to get pointer to image data. */
+#define imPtr(im, x, y) &(im->access[y][x])
+
+template <class T>
+image<T>::image(const int width, const int height, const bool init) {
+  w = width;
+  h = height;
+  data = new T[w * h];  // allocate space for image data
+  access = new T*[h];   // allocate space for row pointers
+  
+  // initialize row pointers
+  for (int i = 0; i < h; i++)
+    access[i] = data + (i * w);  
+  
+  if (init)
+    memset(data, 0, w * h * sizeof(T));
+}
+
+template <class T>
+image<T>::~image() {
+  delete [] data; 
+  delete [] access;
+}
+
+template <class T>
+void image<T>::init(const T &val) {
+  T *ptr = imPtr(this, 0, 0);
+  T *end = imPtr(this, w-1, h-1);
+  while (ptr <= end)
+    *ptr++ = val;
+}
+
+
+template <class T>
+image<T> *image<T>::copy() const {
+  image<T> *im = new image<T>(w, h, false);
+  memcpy(im->data, data, w * h * sizeof(T));
+  return im;
+}
+
+#endif
+  
diff --git a/tools/shapegame/dt/imconv.h b/tools/shapegame/dt/imconv.h
new file mode 100644
index 0000000..2ecbd0b
--- /dev/null
+++ b/tools/shapegame/dt/imconv.h
@@ -0,0 +1,177 @@
+/* dt - imconv.h
+ *
+ * Copyright (C) 2006 Pedro Felzenszwalb
+ *
+ *   This program is free software; you can redistribute it and/or modify
+ *   it under the terms of the GNU General Public License as published by
+ *   the Free Software Foundation; either version 2 of the License, or
+ *   (at your option) any later version.
+ *
+ *   This program is distributed in the hope that it will be useful,
+ *   but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *   GNU General Public License for more details.
+ *
+ *   You should have received a copy of the GNU General Public License
+ *   along with this program; if not, write to the Free Software
+ *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+/* image conversion */
+
+#ifndef CONV_H
+#define CONV_H
+
+#include <climits>
+#include "image.h"
+#include "imutil.h"
+#include "misc.h"
+
+#define	RED_WEIGHT	0.299
+#define GREEN_WEIGHT	0.587
+#define BLUE_WEIGHT	0.114
+
+static image<uchar> *imageRGBtoGRAY(image<rgb> *input) {
+  int width = input->width();
+  int height = input->height();
+  image<uchar> *output = new image<uchar>(width, height, false);
+
+  for (int y = 0; y < height; y++) {
+    for (int x = 0; x < width; x++) {
+      imRef(output, x, y) = (uchar)
+	(imRef(input, x, y).r * RED_WEIGHT +
+	 imRef(input, x, y).g * GREEN_WEIGHT +
+	 imRef(input, x, y).b * BLUE_WEIGHT);
+    }
+  }
+  return output;
+}
+
+static image<rgb> *imageGRAYtoRGB(image<uchar> *input) {
+  int width = input->width();
+  int height = input->height();
+  image<rgb> *output = new image<rgb>(width, height, false);
+
+  for (int y = 0; y < height; y++) {
+    for (int x = 0; x < width; x++) {
+      imRef(output, x, y).r = imRef(input, x, y);
+      imRef(output, x, y).g = imRef(input, x, y);
+      imRef(output, x, y).b = imRef(input, x, y);
+    }
+  }
+  return output;  
+}
+
+static image<float> *imageUCHARtoFLOAT(image<uchar> *input) {
+  int width = input->width();
+  int height = input->height();
+  image<float> *output = new image<float>(width, height, false);
+
+  for (int y = 0; y < height; y++) {
+    for (int x = 0; x < width; x++) {
+      imRef(output, x, y) = imRef(input, x, y);
+    }
+  }
+  return output;  
+}
+
+static image<float> *imageINTtoFLOAT(image<int> *input) {
+  int width = input->width();
+  int height = input->height();
+  image<float> *output = new image<float>(width, height, false);
+
+  for (int y = 0; y < height; y++) {
+    for (int x = 0; x < width; x++) {
+      imRef(output, x, y) = imRef(input, x, y);
+    }
+  }
+  return output;  
+}
+
+static image<uchar> *imageFLOATtoUCHAR(image<float> *input, 
+				       float min, float max) {
+  int width = input->width();
+  int height = input->height();
+  image<uchar> *output = new image<uchar>(width, height, false);
+
+  if (max == min)
+    return output;
+
+  float scale = UCHAR_MAX / (max - min);
+  for (int y = 0; y < height; y++) {
+    for (int x = 0; x < width; x++) {
+      uchar val = (uchar)((imRef(input, x, y) - min) * scale);
+      imRef(output, x, y) = bound(val, (uchar)0, (uchar)UCHAR_MAX);
+    }
+  }
+  return output;
+}
+
+static image<uchar> *imageFLOATtoUCHAR(image<float> *input) {
+  float min, max;
+  min_max(input, &min, &max);
+  return imageFLOATtoUCHAR(input, min, max);
+}
+
+static image<long> *imageUCHARtoLONG(image<uchar> *input) {
+  int width = input->width();
+  int height = input->height();
+  image<long> *output = new image<long>(width, height, false);
+
+  for (int y = 0; y < height; y++) {
+    for (int x = 0; x < width; x++) {
+      imRef(output, x, y) = imRef(input, x, y);
+    }
+  }
+  return output;  
+}
+
+static image<uchar> *imageLONGtoUCHAR(image<long> *input, long min, long max) {
+  int width = input->width();
+  int height = input->height();
+  image<uchar> *output = new image<uchar>(width, height, false);
+
+  if (max == min)
+    return output;
+
+  float scale = UCHAR_MAX / (float)(max - min);
+  for (int y = 0; y < height; y++) {
+    for (int x = 0; x < width; x++) {
+      uchar val = (uchar)((imRef(input, x, y) - min) * scale);
+      imRef(output, x, y) = bound(val, (uchar)0, (uchar)UCHAR_MAX);
+    }
+  }
+  return output;
+}
+
+static image<uchar> *imageLONGtoUCHAR(image<long> *input) {
+  long min, max;
+  min_max(input, &min, &max);
+  return imageLONGtoUCHAR(input, min, max);
+}
+
+static image<uchar> *imageSHORTtoUCHAR(image<short> *input, 
+					short min, short max) {
+  int width = input->width();
+  int height = input->height();
+  image<uchar> *output = new image<uchar>(width, height, false);
+
+  if (max == min)
+    return output;
+
+  float scale = UCHAR_MAX / (float)(max - min);
+  for (int y = 0; y < height; y++) {
+    for (int x = 0; x < width; x++) {
+      uchar val = (uchar)((imRef(input, x, y) - min) * scale);
+      imRef(output, x, y) = bound(val, (uchar)0, (uchar)UCHAR_MAX);
+    }
+  }
+  return output;
+}
+
+static image<uchar> *imageSHORTtoUCHAR(image<short> *input) {
+  short min, max;
+  min_max(input, &min, &max);
+  return imageSHORTtoUCHAR(input, min, max);
+}
+
+#endif
diff --git a/tools/shapegame/dt/imutil.h b/tools/shapegame/dt/imutil.h
new file mode 100644
index 0000000..6fcfca9
--- /dev/null
+++ b/tools/shapegame/dt/imutil.h
@@ -0,0 +1,66 @@
+/* dt - imutil.h
+ *
+ * Copyright (C) 2006 Pedro Felzenszwalb
+ *
+ *   This program is free software; you can redistribute it and/or modify
+ *   it under the terms of the GNU General Public License as published by
+ *   the Free Software Foundation; either version 2 of the License, or
+ *   (at your option) any later version.
+ *
+ *   This program is distributed in the hope that it will be useful,
+ *   but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *   GNU General Public License for more details.
+ *
+ *   You should have received a copy of the GNU General Public License
+ *   along with this program; if not, write to the Free Software
+ *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+/* some image utilities */
+
+#ifndef IMUTIL_H
+#define IMUTIL_H
+
+#include "image.h"
+#include "misc.h"
+
+/* compute minimum and maximum value in an image */
+template <class T>
+void min_max(image<T> *im, T *ret_min, T *ret_max) {
+  int width = im->width();
+  int height = im->height();
+  
+  T min = imRef(im, 0, 0);
+  T max = imRef(im, 0, 0);
+  for (int y = 0; y < height; y++) {
+    for (int x = 0; x < width; x++) {
+      T val = imRef(im, x, y);
+      if (min > val)
+	min = val;
+      if (max < val)
+	max = val;
+    }
+  }
+
+  *ret_min = min;
+  *ret_max = max;
+} 
+
+/* threshold image */
+template <class T>
+image<uchar> *threshold(image<T> *src, int t) {
+  int width = src->width();
+  int height = src->height();
+  image<uchar> *dst = new image<uchar>(width, height);
+  
+  for (int y = 0; y < height; y++) {
+    for (int x = 0; x < width; x++) {
+      imRef(dst, x, y) = (imRef(src, x, y) >= t);
+    }
+  }
+
+  return dst;
+}
+
+#endif
+
diff --git a/tools/shapegame/dt/input.pbm b/tools/shapegame/dt/input.pbm
new file mode 100644
index 0000000..7e26ca9
--- /dev/null
+++ b/tools/shapegame/dt/input.pbm
diff --git a/tools/shapegame/dt/misc.h b/tools/shapegame/dt/misc.h
new file mode 100644
index 0000000..b7b2f50
--- /dev/null
+++ b/tools/shapegame/dt/misc.h
@@ -0,0 +1,65 @@
+/* dt - misc.h
+ *
+ * Copyright (C) 2006 Pedro Felzenszwalb
+ *
+ *   This program is free software; you can redistribute it and/or modify
+ *   it under the terms of the GNU General Public License as published by
+ *   the Free Software Foundation; either version 2 of the License, or
+ *   (at your option) any later version.
+ *
+ *   This program is distributed in the hope that it will be useful,
+ *   but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *   GNU General Public License for more details.
+ *
+ *   You should have received a copy of the GNU General Public License
+ *   along with this program; if not, write to the Free Software
+ *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+/* random stuff */
+
+#ifndef MISC_H
+#define MISC_H
+
+#include <cmath>
+
+#ifndef M_PI
+#define M_PI 3.141592653589793
+#endif
+
+typedef unsigned char uchar;
+
+typedef struct { uchar r, g, b; } rgb;
+
+inline bool operator==(const rgb &a, const rgb &b) {
+  return ((a.r == b.r) && (a.g == b.g) && (a.b == b.b));
+}
+
+template <class T>
+inline T abs(const T &x) { return (x > 0 ? x : -x); };
+
+template <class T>
+inline int sign(const T &x) { return (x >= 0 ? 1 : -1); };
+
+template <class T>
+inline T square(const T &x) { return x*x; };
+
+template <class T>
+inline T bound(const T &x, const T &min, const T &max) {
+  return (x < min ? min : (x > max ? max : x));
+}
+
+template <class T>
+inline bool check_bound(const T &x, const T&min, const T &max) {
+  return ((x < min) || (x > max));
+}
+
+inline int vlib_round(float x) { return (int)(x + 0.5F); }
+
+inline int vlib_round(double x) { return (int)(x + 0.5); }
+
+inline double gaussian(double val, double sigma) {
+  return exp(-square(val/sigma)/2)/(sqrt(2*M_PI)*sigma);
+}
+
+#endif
diff --git a/tools/shapegame/dt/pnmfile.h b/tools/shapegame/dt/pnmfile.h
new file mode 100644
index 0000000..eacf1a1
--- /dev/null
+++ b/tools/shapegame/dt/pnmfile.h
@@ -0,0 +1,211 @@
+/* dt - pnmfile.h
+ *
+ * Copyright (C) 2006 Pedro Felzenszwalb
+ *
+ *   This program is free software; you can redistribute it and/or modify
+ *   it under the terms of the GNU General Public License as published by
+ *   the Free Software Foundation; either version 2 of the License, or
+ *   (at your option) any later version.
+ *
+ *   This program is distributed in the hope that it will be useful,
+ *   but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *   GNU General Public License for more details.
+ *
+ *   You should have received a copy of the GNU General Public License
+ *   along with this program; if not, write to the Free Software
+ *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+/* basic image I/O */
+
+#ifndef PNM_FILE_H
+#define PNM_FILE_H
+
+#include <cstdlib>
+#include <climits>
+#include <cstring>
+#include <fstream>
+#include "image.h"
+#include "misc.h"
+
+#define BUF_SIZE 256
+
+class pnm_error { };
+
+static void read_packed(unsigned char *data, int size, std::ifstream &f) {
+  unsigned char c = 0;
+  
+  int bitshift = -1;
+  for (int pos = 0; pos < size; pos++) {
+    if (bitshift == -1) {
+      c = f.get();
+      bitshift = 7;
+    }
+    data[pos] = (c >> bitshift) & 1;
+    bitshift--;
+    }
+}
+
+static void write_packed(unsigned char *data, int size, std::ofstream &f) {
+  unsigned char c = 0;
+  
+  int bitshift = 7;
+  for (int pos = 0; pos < size; pos++) {
+      c = c | (data[pos] << bitshift);
+      bitshift--;
+      if ((bitshift == -1) || (pos == size-1)) {
+	f.put(c);
+	bitshift = 7;
+	c = 0;
+      }
+  }
+}
+
+/* read PNM field, skipping comments */ 
+static void pnm_read(std::ifstream &file, char *buf) {
+  char doc[BUF_SIZE];
+  char c;
+  
+  file >> c;
+  while (c == '#') {
+    file.getline(doc, BUF_SIZE);
+    file >> c;
+  }
+  file.putback(c);
+  
+  file.width(BUF_SIZE);
+  file >> buf;
+  file.ignore();
+}
+
+static image<uchar> *loadPBM(const char *name) {
+  char buf[BUF_SIZE];
+  
+  /* read header */
+  std::ifstream file(name, std::ios::in | std::ios::binary);
+  pnm_read(file, buf);
+  if (strncmp(buf, "P4", 2))
+    throw pnm_error();
+    
+  pnm_read(file, buf);
+  int width = atoi(buf);
+  pnm_read(file, buf);
+  int height = atoi(buf);
+  
+  /* read data */
+  image<uchar> *im = new image<uchar>(width, height);
+  for (int i = 0; i < height; i++)
+    read_packed(imPtr(im, 0, i), width, file);
+  
+  return im;
+}
+
+static void savePBM(image<uchar> *im, const char *name) {
+  int width = im->width();
+  int height = im->height();
+  std::ofstream file(name, std::ios::out | std::ios::binary);
+
+  file << "P4\n" << width << " " << height << "\n";
+  for (int i = 0; i < height; i++)
+    write_packed(imPtr(im, 0, i), width, file);
+}
+
+static image<uchar> *loadPGM(const char *name) {
+  char buf[BUF_SIZE];
+  
+  /* read header */
+  std::ifstream file(name, std::ios::in | std::ios::binary);
+  pnm_read(file, buf);
+  if (strncmp(buf, "P5", 2))
+    throw pnm_error();
+
+  pnm_read(file, buf);
+  int width = atoi(buf);
+  pnm_read(file, buf);
+  int height = atoi(buf);
+
+  pnm_read(file, buf);
+  if (atoi(buf) > UCHAR_MAX)
+    throw pnm_error();
+
+  /* read data */
+  image<uchar> *im = new image<uchar>(width, height);
+  file.read((char *)imPtr(im, 0, 0), width * height * sizeof(uchar));
+
+  return im;
+}
+
+static void savePGM(image<uchar> *im, const char *name) {
+  int width = im->width();
+  int height = im->height();
+  std::ofstream file(name, std::ios::out | std::ios::binary);
+
+  file << "P5\n" << width << " " << height << "\n" << UCHAR_MAX << "\n";
+  file.write((char *)imPtr(im, 0, 0), width * height * sizeof(uchar));
+}
+
+static image<rgb> *loadPPM(const char *name) {
+  char buf[BUF_SIZE], doc[BUF_SIZE];
+  
+  /* read header */
+  std::ifstream file(name, std::ios::in | std::ios::binary);
+  pnm_read(file, buf);
+  if (strncmp(buf, "P6", 2))
+    throw pnm_error();
+
+  pnm_read(file, buf);
+  int width = atoi(buf);
+  pnm_read(file, buf);
+  int height = atoi(buf);
+
+  pnm_read(file, buf);
+  if (atoi(buf) > UCHAR_MAX)
+    throw pnm_error();
+
+  /* read data */
+  image<rgb> *im = new image<rgb>(width, height);
+  file.read((char *)imPtr(im, 0, 0), width * height * sizeof(rgb));
+
+  return im;
+}
+
+static void savePPM(image<rgb> *im, const char *name) {
+  int width = im->width();
+  int height = im->height();
+  std::ofstream file(name, std::ios::out | std::ios::binary);
+
+  file << "P6\n" << width << " " << height << "\n" << UCHAR_MAX << "\n";
+  file.write((char *)imPtr(im, 0, 0), width * height * sizeof(rgb));
+}
+
+template <class T>
+void load_image(image<T> **im, const char *name) {
+  char buf[BUF_SIZE];
+  
+  /* read header */
+  std::ifstream file(name, std::ios::in | std::ios::binary);
+  pnm_read(file, buf);
+  if (strncmp(buf, "VLIB", 9))
+    throw pnm_error();
+
+  pnm_read(file, buf);
+  int width = atoi(buf);
+  pnm_read(file, buf);
+  int height = atoi(buf);
+
+  /* read data */
+  *im = new image<T>(width, height);
+  file.read((char *)imPtr((*im), 0, 0), width * height * sizeof(T));
+}
+
+template <class T>
+void save_image(image<T> *im, const char *name) {
+  int width = im->width();
+  int height = im->height();
+  std::ofstream file(name, std::ios::out | std::ios::binary);
+
+  file << "VLIB\n" << width << " " << height << "\n";
+  file.write((char *)imPtr(im, 0, 0), width * height * sizeof(T));
+}
+
+#endif
diff --git a/tools/shapegame/nice_target_spot.cpp b/tools/shapegame/nice_target_spot.cpp
new file mode 100644
index 0000000..aa3c31d
--- /dev/null
+++ b/tools/shapegame/nice_target_spot.cpp
@@ -0,0 +1,126 @@
+/* gcompris - nice_target_spot.cpp
+ *
+ * Copyright (C) 2006 Olaf Ronneberger
+ *
+ *   This program is free software; you can redistribute it and/or modify
+ *   it under the terms of the GNU General Public License as published by
+ *   the Free Software Foundation; either version 2 of the License, or
+ *   (at your option) any later version.
+ *
+ *   This program is distributed in the hope that it will be useful,
+ *   but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *   GNU General Public License for more details.
+ *
+ *   You should have received a copy of the GNU General Public License
+ *   along with this program; if not, write to the Free Software
+ *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+/**************************************************************************
+**       Title: create nice target spot
+**
+**    create nice target spots for puzzle pieces in gcpomris shapegame
+**    based on distance transform from Pedro F. Felzenszwalb and 
+**    Daniel P. Huttenlocher.
+**
+**************************************************************************/
+
+#include <cstdio>
+#include <cstdlib>
+#include <cmath>
+#include "dt/pnmfile.h"
+#include "dt/imconv.h"
+#include "dt/dt.h"
+
+int main(int argc, char **argv) {
+  if (argc != 3) {
+    fprintf(stderr, "usage: %s input(pbm) output(ppm)\n", argv[0]);
+    return 1;
+  }
+
+  char *input_name = argv[1];
+  char *output_name = argv[2];
+
+  // load input
+  image<uchar> *input = loadPBM(input_name);
+
+  // compute dt
+  image<float> *out = dt(input);
+
+  // take square roots
+  for (int y = 0; y < out->height(); y++) {
+    for (int x = 0; x < out->width(); x++) {
+      imRef(out, x, y) = sqrt(imRef(out, x, y));
+    }
+  }
+
+  // find maximum
+  int xmax = 0;
+  int ymax = 0;
+  float maxValue = 0;
+  for (int y = 0; y < out->height(); y++) {
+    for (int x = 0; x < out->width(); x++) {
+      if( imRef(out, x, y) > maxValue)
+      {
+        xmax = x;
+        ymax = y;
+        maxValue = imRef(out, x, y);
+      }
+    }
+  }
+  
+  // draw circle at max position into new image (not touching the border)
+  image<rgb>* circleimage = new image<rgb>( input->width(), 
+                                            input->height(), false);
+  rgb white;
+  white.r = 255;
+  white.g = 255;
+  white.b = 255;
+  
+  circleimage->init(white);
+
+  float circleRadius = 3.5;
+  float borderThickness = 1;
+  
+  float innerCircleSqrRadius = square(circleRadius);
+  float outerCircleSqrRadius = square(circleRadius+borderThickness);
+  
+  rgb dotColor;
+  dotColor.r = 255;
+  dotColor.g = 0;
+  dotColor.b = 0;
+
+  rgb borderColor;
+  borderColor.r = 0;
+  borderColor.g = 0;
+  borderColor.b = 0;
+  
+
+  for (int y = 0; y < out->height(); y++) {
+    for (int x = 0; x < out->width(); x++) {
+      float currentSqrRadius = square(x - xmax) + square(y - ymax);
+      
+      if( currentSqrRadius <= outerCircleSqrRadius
+          && imRef(out, x, y) > 1)
+      {
+        if( currentSqrRadius <= innerCircleSqrRadius)
+        {
+          imRef( circleimage, x, y) = dotColor;
+        }
+        else
+        {
+          imRef( circleimage, x, y) = borderColor;
+        }
+      }
+    }
+  }
+
+  // save output
+  savePPM(circleimage, output_name);
+
+  delete input;
+  delete out;
+  delete circleimage;
+  
+}
diff --git a/tools/shapegame/test.pbm b/tools/shapegame/test.pbm
new file mode 100644
index 0000000..97a57ea
--- /dev/null
+++ b/tools/shapegame/test.pbm