| Re: [AD] clipping line algorithm |
[ Thread Index |
Date Index
| More lists.liballeg.org/allegro-developers Archives
]
> I have fixed up your version so that it compiles[ you were right, it
> didnt compile as is ;) ]. Performance was vastly improved using vline
> and hline. Clipline now performs almost the same as line when no
> clipping must be performed. Tests show clipline actually performs faster
> than line even when no clipping is performed, I dont know why though.
"clipline" is typically 50% faster with Linux/DGA2 on my machine with actual
clipping, no difference without actual clipping.
> Attached is clipline3 and the main loop I used to benchmark it with.
Thanks for both.
A few nits:
Try to follow Allegro's coding conventions.
> const int TOP = 0x8;
> const int BOTTOM = 0x4;
> const int RIGHT = 0x2;
> const int LEFT = 0x1;
This is a C++ idiom. Use preprocessor symbols instead in Allegro.
> float slope;
> int b;
Both are unused. Compile at least with -Wall with GCC.
> ASSERT( w );
There is no symbol named 'w'. It's 'bmp'.
> /* not sure if this is really necessary.
> * if not, rename the arguements without the
> * leading underscore: _x1 -> x1
> */
> if ( _x1 > _x2 ){
> x1 = _x2;
> x2 = _x1;
> } else {
> x1 = _x1;
> x2 = _x2;
> }
>
> if ( _y1 > _y2 ){
> y1 = _y2;
> y2 = _y1;
> } else {
> y1 = _y1;
> y2 = _y2;
> }
This is both unnecessary and wrong: you can't swap the x-coordinates without
also swapping the y-coordinates.
> } else if ( outcode & BOTTOM ){
> if ( y2 - y1 == 0 )
> x = x1;
> else
> x = x1 + ( x2 - x1 ) * ( ymax - y1 ) / ( y2 - y1 );
> y = ymin;
'ymin', not 'ymax', in the formula.
> } else {
> if ( x2 - x1 == 0 )
> y = y1;
> else
> y = y1 + (y2-y1) * (xmax-x1)/(x2-x1);
> x = xmin;
'xmin', not 'xmax', in the formula.
And note that you use the wrong orientation for the y-axis:
if ( y > ymax ) code |= TOP; else if ( y < ymin ) code |= BOTTOM; \
The TOP of the bitmap is (y < ymin), the BOTTOM is (y > ymax). But this
doesn't affect the algorithm since you can rename TOP into BOTTOM and vice
versa.
I've applied the attached patch to mainline.
--
Eric BotcazouIndex: src/gfx.c
===================================================================
RCS file: /cvsroot/alleg/allegro/src/gfx.c,v
retrieving revision 1.15
diff -p -r1.15 gfx.c
*** src/gfx.c 25 Jun 2003 08:31:40 -0000 1.15
--- src/gfx.c 19 Sep 2003 14:10:09 -0000
***************
*** 16,21 ****
--- 16,23 ----
*
* Bresenham arc routine by Romano Signorelli.
*
+ * Cohen-Sutherland line clipping by Jon Rafkind.
+ *
* See readme.txt for copyright information.
*/
*************** void do_line(BITMAP *bmp, int x1, int y1
*** 681,738 ****
/* _normal_line:
* Draws a line from x1, y1 to x2, y2, using putpixel() to do the work.
*/
void _normal_line(BITMAP *bmp, int x1, int y1, int x2, int y2, int color)
{
! int sx, sy, dx, dy, t;
!
! if (x1 == x2) {
! vline(bmp, x1, y1, y2, color);
! return;
! }
!
! if (y1 == y2) {
! hline(bmp, x1, y1, x2, color);
! return;
! }
!
! /* use a bounding box to check if the line needs clipping */
! if (bmp->clip) {
! sx = x1;
! sy = y1;
! dx = x2;
! dy = y2;
!
! if (sx > dx) {
! t = sx;
! sx = dx;
! dx = t;
! }
! if (sy > dy) {
! t = sy;
! sy = dy;
! dy = t;
! }
! if ((sx >= bmp->cr) || (sy >= bmp->cb) || (dx < bmp->cl) || (dy < bmp->ct))
return;
! if ((sx >= bmp->cl) && (sy >= bmp->ct) && (dx < bmp->cr) && (dy < bmp->cb))
! bmp->clip = FALSE;
!
! t = TRUE;
}
- else
- t= FALSE;
-
- acquire_bitmap(bmp);
-
- do_line(bmp, x1, y1, x2, y2, color, bmp->vtable->putpixel);
! release_bitmap(bmp);
! bmp->clip = t;
}
--- 683,807 ----
/* _normal_line:
* Draws a line from x1, y1 to x2, y2, using putpixel() to do the work.
+ * This is an implementation of the Cohen-Sutherland line clipping algorithm.
+ * Loops over the line until it can be either trivially rejected or trivially
+ * accepted. If it is neither rejected nor accepted, subdivide it into two
+ * segments, one of which can be rejected.
*/
void _normal_line(BITMAP *bmp, int x1, int y1, int x2, int y2, int color)
{
! int code0, code1;
! int outcode;
! int x, y;
! int xmax, xmin, ymax, ymin;
! int done = 0, accept = 0;
! int clip_orig;
! ASSERT(bmp);
!
! if ((clip_orig = bmp->clip) != 0) { /* save clipping state */
! #define TOP 0x8
! #define BOTTOM 0x4
! #define LEFT 0x2
! #define RIGHT 0x1
!
! #define COMPCLIP(code, x, y) \
! { \
! code = 0; \
! if (y < ymin) \
! code |= TOP; \
! else if (y > ymax) \
! code |= BOTTOM; \
! if (x < xmin) \
! code |= LEFT; \
! else if (x > xmax) \
! code |= RIGHT; \
! }
!
! xmin = bmp->cl;
! xmax = bmp->cr-1;
! ymin = bmp->ct;
! ymax = bmp->cb-1;
!
! COMPCLIP(code0, x1, y1);
! COMPCLIP(code1, x2, y2);
!
! do {
!
! if (!(code0 | code1)) {
! /* Trivially accept. */
! accept = done = 1;
! }
! else if (code0 & code1) {
! /* Trivially reject. */
! done = 1;
! }
! else {
! /* Didn't reject or accept, so do some calculations. */
! outcode = code0 ? code0 : code1; /* pick one endpoint */
! if (outcode & TOP) {
! if (y2 == y1)
! x = x1;
! else
! x = x1 + (x2 - x1) * (ymin - y1) / (y2 - y1);
! y = ymin;
! }
! else if (outcode & BOTTOM) {
! if (y2 == y1)
! x = x1;
! else
! x = x1 + (x2 - x1) * (ymax - y1) / (y2 - y1);
! y = ymax;
! }
! else if (outcode & LEFT) {
! if (x2 == x1)
! y = y1;
! else
! y = y1 + (y2 - y1) * (xmin - x1) / (x2 - x1);
! x = xmin;
! }
! else { /* outcode & RIGHT */
! if (x2 == x1)
! y = y1;
! else
! y = y1 + (y2 - y1) * (xmax - x1) / (x2 - x1);
! x = xmax;
! }
!
! if (outcode == code0) {
! x1 = x;
! y1 = y;
! COMPCLIP(code0, x1, y1);
! }
! else {
! x2 = x;
! y2 = y;
! COMPCLIP(code1, x2, y2);
! }
! }
! } while (!done);
! if (!accept)
return;
! /* We have already done the clipping, no need to do it again. */
! bmp->clip = FALSE;
}
! if (x1 == x2) {
! bmp->vtable->vline(bmp, x1, y1, y2, color);
! }
! else if (y1 == y2) {
! bmp->vtable->hline(bmp, x1, y1, x2, color);
! }
! else {
! acquire_bitmap(bmp);
! do_line(bmp, x1, y1, x2, y2, color, bmp->vtable->putpixel);
! release_bitmap(bmp);
! }
! /* Restore original clipping state. */
! bmp->clip = clip_orig;
}