Path: utzoo!attcan!uunet!mcvax!ukc!dcl-cs!bath63!ma_jns
From: ma_jns@ux63.bath.ac.uk (Spackman)
Newsgroups: comp.graphics
Subject: Re: Floyd-Steinberg Errors:  What do I do with them?
Message-ID: <2811@bath63.ux63.bath.ac.uk>
Date: 19 Jul 88 09:51:59 GMT
References: <6506@well.UUCP> <13172@jumbo.dec.com> <252@versatc.UUCP>
Reply-To: ma_jns@ux63.bath.ac.uk (Spackman)
Organization: University of Bath, England
Lines: 379


   2N     11776: 19 Jul 88 John Spackman   
(Message # 2: 11776 bytes, New)
Via:  uk.ac.bath.maths; 19 Jul 88 10:41 BST
Received: from chroma by mordell.maths.bath.AC.UK id aa29121;
          19 Jul 88 10:35 BST
Date:     Tue, 19 Jul 88 10:33:28 BST
From:     John Spackman <jns@uk.ac.bath.maths>
To:       ma_jns@uk.ac.bath.ux63

               The following shell archive contains various C code for
          mappings  between  Cartesian  and  Peano  co-ordinates.  The
          Peano co-ordinate of a point in a 2^n  side  square  is  the
          position  along the connected, filling Peano curve ( Hilbert
          here ).  The mappings are achieved with  simple  bit  shifts
          for speed, iterating 'n' times for a '2^n' side square.

               I have used this curve to order error propagation (c.g.
          Floyd  Steinberg), passing the whole error incurred by quan-
          tisation at one pixel to the Peano-next pixel.  Other graph-
          ical applications include run-length images ALONG THE CURVE,
          which is comparable to quad encoding.

               The code may be adapted to generate curves in  n-space,
          e.g. 3-space for look up table algorithms.

    John Spackman, Maths Sciences
    University of Bath, Claverton  Down,  Bath,  Avon,  BA2 7AY, England.

#------------- cut here -------------- cut here -----------
#! /bin/sh
# This is a shell archive.  Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file".  To overwrite existing
# files, type "sh file -c".  You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g..  If this archive is complete, you
# will see the following message at the end:
#		"End of archive 1 (of 1)."
# Contents:  peano_routines.h peano_routines.c example.c makefile
# 
# An example showing how to use the mappings is given in "example.c", 
# which you should make with the makfile. For example, try :-
# Level (>0) ? 1                                  'Square of 2^level side
# Direction : Across in [0,1] & From in [0,3] ?   'Direction & Origin of curve
#                                                 'Output ..
# 0 th peano point AT [ X = 0, Y = 0 ]
# 	[ X = 0, Y = 0 ] AT 0 th peano point
# 1 th peano point AT [ X = 1, Y = 0 ]
# 	[ X = 1, Y = 0 ] AT 1 th peano point
# 2 th peano point AT [ X = 1, Y = 1 ]
# 	[ X = 1, Y = 1 ] AT 2 th peano point
# 3 th peano point AT [ X = 0, Y = 1 ]
# ... etc.
if test -f 'peano_routines.h' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'peano_routines.h'\"
else
echo shar: Extracting \"'peano_routines.h'\"
sed "s/^X//" >'peano_routines.h' <<'END_OF_FILE'
Xstruct traverse
X{ 
X  int accross, from;
X};
X
Xstruct record
X{ 
X  int moreton, peano;
X  struct traverse next;
X};
X
Xstruct path
X{ 
X  struct record quad[4];
X};
X
Xstruct curve
X{ 
X  struct path dimension[2];
X};
X
Xtypedef struct traverse TRAVERSE;
Xtypedef struct record RECORD;
Xtypedef struct path PATH;
Xtypedef struct curve CURVE;
END_OF_FILE
fi
if test -f 'peano_routines.c' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'peano_routines.c'\"
else
echo shar: Extracting \"'peano_routines.c'\"
sed "s/^X//" >'peano_routines.c' <<'END_OF_FILE'
X#include "peano_routines.h"
X
Xchar copy_right[] = "\
X        +---+   +---+   +---+   +---+   +---+   +---+   +---+   +---+ \n\
X        |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   | \n\
X        |   +---+   |   |   +---+   |   |   +---+   |   |   +---+   | \n\
X        |           |   |           |   |           |   |           | \n\
X        +---+   +---+   +---+   +---+   +---+   +---+   +---+   +---+ \n\
X            |   |           |   |           |   |           |   |     \n\
X        +---+   +-----------+   +---+   +---+   +-----------+   +---+ \n\
X        |                           |   |                           | \n\
X        |   +-------+   +-------+   |   |   +-------+   +-------+   | \n\
X        |   |       |   |       |   |   |   |       |   |       |   | \n\
X        +---+   +---+   +---+   +---+   +---+   +---+   +---+   +---+ \n\
X                |           |                   |           |         \n\
X        +---+   +---+   +---+   +---+   +---+   +---+   +---+   +---+ \n\
X        |   |       |   |       |   |   |   |       |   |       |   | \n\
X        |   +-------+   +-------+   +---+   +-------+   +-------+   | \n\
X        |                                                           | \n\
X        +---+   +-------+   +-------+   +-------+   +-------+   +---+ \n\
X            |   |       |   |       |   |       |   |       |   |     \n\
X        +---+   +---+   +---+   +---+   +---+   +---+   +---+   +---+ \n\
X        |           |           |           |           |           | \n\
X        |   +---+   |   +---+   +---+   +---+   +---+   |   +---+   | \n\
X        |   |   |   |   |   |       |   |       |   |   |   |   |   | \n\
X        +---+   +---+   |   +-------+   +-------+   |   +---+   +---+ \n\
X                        |                           |                 \n\
X        +---+   +---+   |   +-------+   +-------+   |   +---+   +---+ \n\
X        |   |   |   |   |   |       |   |       |   |   |   |   |   | \n\
X        |   +---+   |   +---+   +---+   +---+   +---+   |   +---+   | \n\
X        |           |           |           |           |           | \n\
X        +---+   +---+   +---+   +---+   +---+   +---+   +---+   +---+ \n\
X            |   |       |   |       |   |       |   |       |   |     \n\
X        >>--+   +-------+   +-------+   +-------+   +-------+   +-->> \n\
X                                                                      \n\
X    ######                                         @1988 John Spackman,   \n\
X     ##  ##                                        The University of Bath,\n\
X     ##  ##   ####    ####    #####    ####        Claverton Down,        \n\
X     #####   ##  ##      ##   ##  ##  ##  ##       Bath,                  \n\
X     ##      ######   #####   ##  ##  ##  ##       Avon,                  \n\
X     ##      ##      ##  ##   ##  ##  ##  ##       BA2 7AY,               \n\
X    ####      ####    ### ##  ##  ##   ####        England.               \n\
X                                                                          \n\
X      ####                                                                \n\
X     ##  ##                                                               \n\
X    ##       ##  ##   ## ###   ##  ##   ####   #####                      \n\
X    ##       ##  ##    ### ##  ##  ##  ##  ## ##                          \n\
X    ##       ##  ##    ##  ##  ##  ##  ######  ####                       \n\
X     ##  ##  ##  ##    ##       ####   ##         ##                      \n\
X      ####    ### ##  ####       ##     ####  #####                       \n\
X\n";
X
Xstatic CURVE pattern;
Xstatic int level, power;
X
Xinit(degree)
Xint degree;
X{   
X  PATH *x = &(pattern.dimension[0]);
X  PATH *y = &(pattern.dimension[1]);
X
X  x->quad[0].moreton = 0;     
X  x->quad[0].peano = 0;
X  x->quad[0].next.accross = 1;
X  x->quad[0].next.from = 0;
X  x->quad[1].moreton = 2;     
X  x->quad[1].peano = 3;
X  x->quad[1].next.accross = 0;
X  x->quad[1].next.from = 0;
X  x->quad[2].moreton = 3;     
X  x->quad[2].peano = 1;
X  x->quad[2].next.accross = 0;
X  x->quad[2].next.from = 0;
X  x->quad[3].moreton = 1;     
X  x->quad[3].peano = 2;
X  x->quad[3].next.accross = 1;
X  x->quad[3].next.from = 3;
X
X  y->quad[0].moreton = 0;     
X  y->quad[0].peano = 0;
X  y->quad[0].next.accross = 0;
X  y->quad[0].next.from = 0;
X  y->quad[1].moreton = 1;     
X  y->quad[1].peano = 1;
X  y->quad[1].next.accross = 1;
X  y->quad[1].next.from = 0;
X  y->quad[2].moreton = 3;     
X  y->quad[2].peano = 3;
X  y->quad[2].next.accross = 1;
X  y->quad[2].next.from = 0;
X  y->quad[3].moreton = 2;     
X  y->quad[3].peano = 2;
X  y->quad[3].next.accross = 0;
X  y->quad[3].next.from = 3;
X
X  level = degree; 
X  power = degree*2;
X
X}
X
Xint from_peano(peano,direction)
Xint peano;
XTRAVERSE direction; /* Position along Peano curve */
X{   
X  int bits = power;
X  int from = direction.from;
X  int peano_quad;
X  int result = 0;
X  RECORD use;
X
X  while (bits)
X  {   
X    bits -= 2;
X    peano_quad = (peano>>bits)&3;
X    use = pattern.dimension[direction.accross].quad[peano_quad];
X    direction = use.next;
X    result |= ((from^use.moreton)<<bits);
X    from ^= direction.from;
X  }
X
X  return result;
X}
X
Xint to_peano(moreton,direction)
Xint moreton;
XTRAVERSE direction; /* Position along Peano curve */
X{   
X  int bits = power;
X  int from = direction.from;
X  int moreton_quad, peano_quad;
X  int result = 0;
X  RECORD use;
X
X  while (bits)
X  {   
X    bits -= 2;
X    moreton_quad = (moreton>>bits)&3;
X    peano_quad =
X        pattern.dimension[direction.accross].quad[from^moreton_quad].peano;
X
X    use = pattern.dimension[direction.accross].quad[peano_quad];
X    direction = use.next;
X    result |= (peano_quad<<bits);
X    from ^= direction.from;
X  }
X
X  return result;
X}
X
Xcoord(moreton,x,y)
Xint moreton;
Xint *x, *y;
X{   
X  int bits = 1;
X  *x = 0; 
X  *y =0;
X
X  while (moreton)
X  {   
X    if (moreton&1) *x |= bits;
X    moreton >>= 1;
X    if (moreton&1) *y |= bits;
X    moreton >>= 1;
X    bits <<= 1;
X  }
X  return;
X}
X
Xint combine(x,y)
Xint x, y;
X{   
X  int result =0;
X  int bits = 1;
X
X  while (x || y)
X  {   
X    if (x&1) result |= bits;
X    x >>=1; 
X    bits <<=1;
X    if (y&1) result |= bits;
X    y >>=1; 
X    bits <<=1;
X  }
X  return result;
X}
END_OF_FILE
fi
if test -f 'example.c' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'example.c'\"
else
echo shar: Extracting \"'example.c'\"
sed "s/^X//" >'example.c' <<'END_OF_FILE'
X#include <stdio.h>
X#include "peano_routines.h"
X
Xextern char copy_right[];
X
Xmain()
X{   
X  TRAVERSE direct;
X  int moreton, peano, x, y;
X  int i, top, level;
X  int entered;
X  
X  printf(copy_right);
X
X  do
X  { do
X    { printf("Level (>0) ? ");
X      entered = scanf("%d", &level);
X      while (getchar()!='\n') continue;
X    }   
X    while (level <=0 || entered<1);
X
X    init(level);
X    top = 1<<(level*2);
X
X    do
X    { printf("Direction : Across in [0,1] & From in [0,3] ? ");
X      entered = scanf("%d%d", &(direct.accross), &(direct.from) );
X      while (getchar()!='\n') continue;
X    }   
X    while (direct.accross  < 0 || direct.accross  > 1 ||
X        direct.from < 0 || direct.from > 3 ||
X        entered<2);
X
X    for (i=0; i<top; i++)
X    { moreton =  from_peano(i,direct);
X      coord(moreton,&x,&y);
X      printf("%d th peano point AT [ X = %d, Y = %d ]\n",i,x,y);
X      moreton = combine(x,y);
X      peano = to_peano(moreton,direct);
X      printf("\t[ X = %d, Y = %d ] AT %d th peano point\n",x,y,peano);
X    }
X
X  } 
X  while (level);
X
X}
END_OF_FILE
fi
if test -f 'makefile' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'makefile'\"
else
echo shar: Extracting \"'makefile'\"
sed "s/^X//" >'makefile' <<'END_OF_FILE'
X# Makefile for peano routines
X
XSDIR= .
XODIR= .
XRDIR= .
XBACKUP_DIR= /tmp
X
X# C Source
X
XSRCS= $(SDIR)/example.c $(SDIR)/peano_routines.c
X
X# Object Code
X
XOBJS= $(ODIR)/example.o $(ODIR)/peano_routines.o
X
X# Runs
X
XRUNS= $(RDIR)/example 
X
X# Executable files to be created
X
Xall: example 
X
X# Compile commands
X
Xexample: example.o peano_routines.o
X	cc -g -o example example.o peano_routines.o
Xexample.o:
X	cc -g -c $(SDIR)/example.c
X
Xpeano_routines.o: peano_routines.h
X	cc -g -c $(SDIR)/peano_routines.c
X
X# Lint command
X
Xlint: $(SRCS)
X	lint $(SRCS)
X
X# Remove unnecessary files
X
Xclean:
X	rm -f $(ODIR)/core $(ODIR)/a.out $(ODIR)/*.o $(SDIR)/*~
END_OF_FILE
fi