15 replies to this topic

[roxtar]

I was trying to implement the midpoint subdivision line clipping algorithm which is a modification of the Cohen Sutherland algorithm.

void lineclip(int x0,int y0,int x1,int y1,int xwmin,int ywmin,int xwmax,int ywmax) {

  outcode code0,code1;

  int midx,midy;

  code0=calcode(x0,y0,xwmin,ywmin,xwmax,ywmax);

  code1=calcode(x1,y1,xwmin,ywmin,xwmax,ywmax);

  if( !(code0 | code1) ) { /*The two points are completely inside the window*/

    line(x0,y0,x1,y1);

    return;

  }

  else if(code0 & code1) /*The two points are completely outside the window.*/

    return ;

  midx=(x0+x1)/2;

  midy=(y0+y1)/2;

  lineclip(midx,midy,x1,y1,xwmin,ywmin,xwmax,ywmax);

  lineclip(x0,y0,midx,midy,xwmin,ywmin,xwmax,ywmax);

}

The calcode routine generates the "code" (same as in Cohen Sutherland algorithm) for the point, which is passed as an argument, against the clipping window boundaries. Unfortunately when I run this routine I get segmentation faults. Can anyone tell me why?
I couldn't find much documentation about this algorithm either in texts or on the net. Any help will be appreciated.

Thanks

[Phaetos]

Hi!

As you don't use pointers in your function I doubt that the function itself is giving the segfault...
I suspect this call :

line(x0,y0,x1,y1)

Maybe this is the point where the segfault occurs? Can you post the source of this function?

Greetings
Stefan

[roxtar]

I don't think that the line routine is the problem. It is a pretty straightforward implementation.

void line(int x0,int y0,int x1,int y1) {

  glBegin(GL_LINES);

  glVertex2i(x0,y0);

  glVertex2i(x1,y1);

  glEnd();

}

The main program looks like this:

int main(int argc,char ** argv) {

    SDL_Event event;

    int x0=10,y0=10,x1=23,y1=32;

    int xwmin=5,ywmin=5,xwmax=18,ywmax=18;

    ginitialize(); /*Initializes openGL and SDL */

    while(1) {

    glClear(GL_COLOR_BUFFER_BIT|GL_DEPTH_BUFFER_BIT);

    glColor3f(1.0,1.0,1.0);

    line(x0,y0,x1,y1);

    glColor3f(1.0,0.0,0.0);

    lineclip(x0,y0,x1,y1,xwmin,ywmin,xwmax,ywmax); /*If I comment out this line the program will run and draw a white line. 

Otherwise it just crashes.*/

    while(SDL_PollEvent(&event)) {

     switch(event.type) {

     case SDL_QUIT:

	  gclose();

	  return 0;	  

     }

   }

   glFlush();

   SDL_GL_SwapBuffers();

  }

}

[Phaetos]

Hi!

What does calcode() return? The line

"(code0 & code1)" is suspicious - maybe it should read "(code0 && code1)" ??

My guess is you run out of stack memory because of too many nested recursions....

Greetings
Stefan

[roxtar]

calcode returns the area code of the point (read the Cohen Sutherland algorithm, you will understand) it is a simple unsigned int. In the "if" statement it is supposed to be a bitwise and (&) and not a logical one (&&). I was also thinking that maybe I'm running out of stack space, but I just wanted to confirm. Does anyone know a non recursive implementation of this?

[zavie]

Message deleted.

[Phaetos]

Hi Zavie!

Roxtar uses the Cohan&Sutherland Algorithm - which returns a bit combination that
explains the position of a point regarding the clipping-window. It consits of 4 bits: 1 for
each scenario: above, beyond, left of and right of. So, when all bits are zero, the point
is exactly IN the window.
And, therefor, if (code0 | code1) is still zero, both points are IN the window and the
line can be drawn completely.

Sorry, roxtar, but I don't have any ideas left why you may get a segfault ... sorry. The only thing left is: Do you determine the bits right? I think it is important that you set the bits with "<=" and ">=" comparisons, so that a point ON a boundary is considered to be in it.... but thats just wild guessing now ;)

Greetings
Stefan

[roxtar]

I would refer both of you to this and this. Look under Cohen Sutherland line clipping.

[.oisyn]

Don't know why your code segfaults (not very evident from the code you posted), but your algorithm looks like a pretty slow one, and can also cause a lot of artifacts since you're not using floating point coordinates. Wouldn't that be a problem?

[roxtar]

I know that the algorithm is inefficient, I'm not actually looking to use it in any *other* program. I am doing this only for theoretical interest and I'm not worried about artifacts. Can anyone run the program in their computer and let me know if they also get a segfault or not.

[Mihail121]

Can you please post the calcode function. I will gladly test it on here.

P.S.

You can send me a private message or contact me on the ICQ (245757495)

[roxtar]

The calcode function:

typedef unsigned int outcode;

enum {TOP=0x8,BOTTOM=0x4,RIGHT=0x2,LEFT=0x1};

unsigned int calcode(int x,int y,int xwmin,int ywmin,int xwmax,int ywmax)

{

 unsigned int code=0;

 if(y>ywmax)

	code|=TOP;

 else if(y<ywmin)

	code|=BOTTOM;

 if(x>xwmax)

	code|=RIGHT;

 else if(x<xwmin)

	code|=LEFT;


 return(code);

}

[.oisyn]

BTW, are you sure it's a segfault? It looks to me like a stack overflow because of a potential infinite recursion. But that's something you can easily check with a debugger.

If the two points are adjacent to eachother, (x0+x1)/2 evaluates to either x0 or x1, depending on the signs of x0 and x1, so you're calling another lineclip with exactly the same parameters over and over again.

[Mihail121]

You my friend are causing a stack overflow because of the infinite recursion of the lineclip function!

edit: .oisyn is correct

[roxtar]

It worked, thank you guys :yes:

void lineclip(int x0,int y0,int x1,int y1,int xwmin,int ywmin,int xwmax,int ywmax) {

  outcode code0,code1;

  int midx,midy;

  if(abs(x0-x1)==1 && abs(y0-y1)==1) /*Adjacent points */

   return;

  code0=calcode(x0,y0,xwmin,ywmin,xwmax,ywmax);

  code1=calcode(x1,y1,xwmin,ywmin,xwmax,ywmax);

  if( !(code0 | code1) ) { /*The two points are completely inside the window*/

    line(x0,y0,x1,y1);

    return;

  }

  else if(code0 & code1) /*The two points are completely outside the window.*/

    return ;

  midx=(x0+x1)/2;

  midy=(y0+y1)/2;

  lineclip(midx,midy,x1,y1,xwmin,ywmin,xwmax,ywmax);

  lineclip(x0,y0,midx,midy,xwmin,ywmin,xwmax,ywmax);

}

[NomadRock]

There are pretty easy ways to remove recursion. I suggest you look at an algorithms book, and you can probably google up some information as well.

The trivial solution is to build your own stack of variables, and the easy solutions are when you have a single recursive call at the beginning or the end of the function. This might be a fun exercise for you considering you are doing this for purely academic purposes.