Skip to main content
GameDev.net gamedev.net
🔒 Locked 🎮 Unity

Fixed-point problem (dist transform)

Started by DWN Jul 25, 2010 at 9:25 AM 2 replies 950+ views
Original Post
DWN
DWN
Okay, normally I wouldn't put up a brief coding problem and request assistance, but I've spent a lot of time on this, and I'm now begging for another set of eyes.

I am trying to convert the following code into int32 (fixed point):

#define INF 0xffff//Distance transform of 1D function using squared distancestatic float *dt(int *f, int n) {  float *d=new float[n];  int *v=new int[n];  int *z=new int[n+1];  int s;  int k=0;  v[0]=0;  z[0]=2048.f*-INF;  z[1]=2048.f*+INF;  for(int q=1;q<n;q++) {    k++;    do {      k--;      s=(2048.f/2.f)*        ( (f[q]+square(q)) - (f[v[k]]+square(v[k])) ) / (q-v[k]);    } while(s<=z[k]);    k++;    v[k]=q;    z[k]=s;    z[k+1]=2048.f*+INF;  }  k=0;  for(int q=0;q<n;q++) {    while (z[k+1] < 2048.f*q) k++;    d[q]=square(q-v[k]) + f[v[k]];//    if (d[q]>10000.f) exit(0); //This exits  }  delete [] v;  delete [] z;  return d;}static image<float> *dt(image<uchar>* in, uchar on=1) {  //Distance transform of binary image using squared distance  int width=in->width();  int height=in->height();  image<float> *im=new image<float>(width, height, false);  for (int y=0;y<height;y++) {    for (int x=0;x<width;x++) {      if (imRef(in,x,y)==on) imRef(im,x,y)=0;      else imRef(im,x,y)=INF;    }  }  //Distance transform of 2D function using squared distance  width=im->width();  height=im->height();  int *f=new int[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;  return im;}



Here is my integer version:

//Distance transform of 1D array using squared distance//Last two arguments must be dimensioned v[size],z[size+1], but do not contain//meaningful data; they exist so arrays need not be allocated repeatedlyvoid agDistanceTransform1D(unsigned short* buff,unsigned short *src,                           unsigned int size,int* v,int* z) {#define AG_DTINFINITY 0xffff  v[0]=0;  z[0]=-AG_DTINFINITY<<11;  z[1]=AG_DTINFINITY<<11;  int a,s,k=0;  for(int q=1;q<size;q++) {    k++;    do {      k--;      //While I would expect this line to be the problem, it doesn't seem to be      s=(((q*q-v[k]*v[k])<<10)+((src[q]-src[v[k]])>>6))/(q-v[k]);    } while(s<=z[k]);    k++;    v[k]=q;    z[k]=s;    z[k+1]=AG_DTINFINITY<<11;  }  k=0;  for(int q=0;q<size;q++) {    while(z[k+1]<(q<<11)) k++;    a=(((q-v[k])*(q-v[k]))<<11)+(src[v[k]]>>5);    a>>=11;    a=(a>AG_DTINFINITY? AG_DTINFINITY : a);//    if (a>4) exit(0); //This does not exit    buff[q]=a;  }}void agFullScreenDistanceTransform(unsigned short* buff) {  for(int y=0;y<AG_HEIGHT;y++) {    for(int x=0;x<AG_WIDTH;x++) {      agSetPixel(buff+y*AG_WIDTH+x,255,255,255);    }  }  agRead(buff+150*AG_WIDTH+250,"dist.bmp",NULL,NULL,1);//  agCircle(buff,320,240,100,255,255,255);  for(int y=0;y<AG_HEIGHT;y++) {    for(int x=0;x<AG_WIDTH;x++) {      if (buff[y*AG_WIDTH+x]) buff[y*AG_WIDTH+x]=0;      else buff[y*AG_WIDTH+x]=AG_DTINFINITY;    }  }  //Distance transform of 2D array using squared distance  unsigned short d[AG_WIDTH],f[AG_WIDTH];  int v[AG_WIDTH],z[AG_WIDTH+1];  //Transform along columns  for(int x=0;x<AG_WIDTH;x++) {    for(int y=0;y<AG_HEIGHT;y++) {      f[y]=buff[y*AG_WIDTH+x];    }    agDistanceTransform1D(d,f,AG_HEIGHT,v,z);    for(int y=0;y<AG_HEIGHT;y++) {      buff[AG_WIDTH*y+x]=d[y];    }  }  //Transform along rows//  for(int y=0;y<AG_HEIGHT;y++) {//    for(int x=0;x<AG_WIDTH;x++) {//      f[x]=buff[y*AG_WIDTH+x];//    }//    agDistanceTransform1D(d,f,AG_WIDTH,v,z);//    for(int x=0;x<AG_WIDTH;x++) {//      buff[AG_WIDTH*y+x]=d[y];//    }//  }  for(int y=0;y<AG_HEIGHT;y++) {    for(int x=0;x<AG_WIDTH;x++) {      commonSetPixel(buff+y*AG_WIDTH+x,buff[y*AG_WIDTH+x]>>8,0,0);    }  }#undef AG_DTINFINITY}


Obviously the output of the second function is a little different. It does not return a value - my intention. The first function, however, is not computing the correct function. The output values are not getting any greater than value 4.
DWN
DWN
YEA! got this working, more or less. I'd like a little more precision, though, in 16 bits.

I'm trying to find HALF-PRECISION (16-BIT) FLOAT CONVERSION ROUTINES online, but haven't found any. :/ Any help? They should be in C (not ASM) for the sake of portability.

Thanks for any help!!
DWN
DWN
BTW, I mean to convert from and to SHORT (16-BIT) INT.
DWN
DWN
Oh yeah, I forgot to mention: all the values are UNSIGNED.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.