src/clip.c

   1 #include "zgl.h"
   2
   3 /* fill triangle profile */
   4 /* #define PROFILE */
   5
   6 #define CLIP_XMIN   (1<<0)
   7 #define CLIP_XMAX   (1<<1)
   8 #define CLIP_YMIN   (1<<2)
   9 #define CLIP_YMAX   (1<<3)
  10 #define CLIP_ZMIN   (1<<4)
  11 #define CLIP_ZMAX   (1<<5)
  12
  13 void gl_transform_to_viewport(GLContext *c,GLVertex *v)
  14 {
  15         float winv;
  16
  17         /* coordinates */
  18         winv=1.0/v->pc.W;
  19         v->zp.x= (int) ( v->pc.X * winv * c->viewport.scale.X
  20                         + c->viewport.trans.X );
  21         v->zp.y= (int) ( v->pc.Y * winv * c->viewport.scale.Y
  22                         + c->viewport.trans.Y );
  23         v->zp.z= (int) ( v->pc.Z * winv * c->viewport.scale.Z
  24                         + c->viewport.trans.Z );
  25         /* color */
  26         if (c->lighting_enabled) {
  27                 v->zp.r=(int)(v->color.v[0] * (ZB_POINT_RED_MAX - ZB_POINT_RED_MIN)
  28                                 + ZB_POINT_RED_MIN);
  29                 v->zp.g=(int)(v->color.v[1] * (ZB_POINT_GREEN_MAX - ZB_POINT_GREEN_MIN)
  30                                 + ZB_POINT_GREEN_MIN);
  31                 v->zp.b=(int)(v->color.v[2] * (ZB_POINT_BLUE_MAX - ZB_POINT_BLUE_MIN)
  32                                 + ZB_POINT_BLUE_MIN);
  33         } else {
  34                 /* no need to convert to integer if no lighting : take current color */
  35                 v->zp.r = c->longcurrent_color[0];
  36                 v->zp.g = c->longcurrent_color[1];
  37                 v->zp.b = c->longcurrent_color[2];
  38         }
  39
  40         /* texture */
  41
  42         if (c->texture_2d_enabled) {
  43                 v->zp.s=(int)(v->tex_coord.X * (ZB_POINT_S_MAX - ZB_POINT_S_MIN)
  44                                 + ZB_POINT_S_MIN);
  45                 v->zp.t=(int)(v->tex_coord.Y * (ZB_POINT_T_MAX - ZB_POINT_T_MIN)
  46                                 + ZB_POINT_T_MIN);
  47         }
  48 }
  49
  50
  51 static void gl_add_select1(GLContext *c,int z1,int z2,int z3)
  52 {
  53         unsigned int min,max;
  54         min=max=z1;
  55         if (z2<min) min=z2;
  56         if (z3<min) min=z3;
  57         if (z2>max) max=z2;
  58         if (z3>max) max=z3;
  59
  60         gl_add_select(c,0xffffffff-min,0xffffffff-max);
  61 }
  62
  63 /* point */
  64
  65 void gl_draw_point(GLContext *c,GLVertex *p0)
  66 {
  67         if (p0->clip_code == 0) {
  68                 if (c->render_mode == GL_SELECT) {
  69                         gl_add_select(c,p0->zp.z,p0->zp.z);
  70                 } else {
  71                         ZB_plot(c->zb,&p0->zp);
  72                 }
  73         }
  74 }
  75
  76 /* line */
  77
  78 static inline void interpolate(GLVertex *q,GLVertex *p0,GLVertex *p1,float t)
  79 {
  80         q->pc.X=p0->pc.X+(p1->pc.X-p0->pc.X)*t;
  81         q->pc.Y=p0->pc.Y+(p1->pc.Y-p0->pc.Y)*t;
  82         q->pc.Z=p0->pc.Z+(p1->pc.Z-p0->pc.Z)*t;
  83         q->pc.W=p0->pc.W+(p1->pc.W-p0->pc.W)*t;
  84
  85         q->color.v[0]=p0->color.v[0] + (p1->color.v[0]-p0->color.v[0])*t;
  86         q->color.v[1]=p0->color.v[1] + (p1->color.v[1]-p0->color.v[1])*t;
  87         q->color.v[2]=p0->color.v[2] + (p1->color.v[2]-p0->color.v[2])*t;
  88 }
  89
  90 /*
  91  * Line Clipping
  92  */
  93
  94 /* Line Clipping algorithm from 'Computer Graphics', Principles and
  95    Practice */
  96 static inline int ClipLine1(float denom,float num,float *tmin,float *tmax)
  97 {
  98         float t;
  99
 100         if (denom>0) {
 101                 t=num/denom;
 102                 if (t>*tmax) return 0;
 103                 if (t>*tmin) *tmin=t;
 104         } else if (denom<0) {
 105                 t=num/denom;
 106                 if (t<*tmin) return 0;
 107                 if (t<*tmax) *tmax=t;
 108         } else if (num>0) return 0;
 109         return 1;
 110 }
 111
 112 void gl_draw_line(GLContext *c,GLVertex *p1,GLVertex *p2)
 113 {
 114         float dx,dy,dz,dw,x1,y1,z1,w1;
 115         float tmin,tmax;
 116         GLVertex q1,q2;
 117         int cc1,cc2;
 118
 119         cc1=p1->clip_code;
 120         cc2=p2->clip_code;
 121
 122         if ( (cc1 | cc2) == 0) {
 123                 if (c->render_mode == GL_SELECT) {
 124                         gl_add_select1(c,p1->zp.z,p2->zp.z,p2->zp.z);
 125                 } else {
 126                         if (c->depth_test)
 127                                 ZB_line_z(c->zb,&p1->zp,&p2->zp);
 128                         else
 129                                 ZB_line(c->zb,&p1->zp,&p2->zp);
 130                 }
 131         } else if ( (cc1&cc2) != 0 ) {
 132                 return;
 133         } else {
 134                 dx=p2->pc.X-p1->pc.X;
 135                 dy=p2->pc.Y-p1->pc.Y;
 136                 dz=p2->pc.Z-p1->pc.Z;
 137                 dw=p2->pc.W-p1->pc.W;
 138                 x1=p1->pc.X;
 139                 y1=p1->pc.Y;
 140                 z1=p1->pc.Z;
 141                 w1=p1->pc.W;
 142
 143                 tmin=0;
 144                 tmax=1;
 145                 if (ClipLine1(dx+dw,-x1-w1,&tmin,&tmax) &&
 146                                 ClipLine1(-dx+dw,x1-w1,&tmin,&tmax) &&
 147                                 ClipLine1(dy+dw,-y1-w1,&tmin,&tmax) &&
 148                                 ClipLine1(-dy+dw,y1-w1,&tmin,&tmax) &&
 149                                 ClipLine1(dz+dw,-z1-w1,&tmin,&tmax) &&
 150                                 ClipLine1(-dz+dw,z1-w1,&tmin,&tmax)) {
 151
 152                         interpolate(&q1,p1,p2,tmin);
 153                         interpolate(&q2,p1,p2,tmax);
 154                         gl_transform_to_viewport(c,&q1);
 155                         gl_transform_to_viewport(c,&q2);
 156
 157                         if (c->depth_test)
 158                                 ZB_line_z(c->zb,&q1.zp,&q2.zp);
 159                         else
 160                                 ZB_line(c->zb,&q1.zp,&q2.zp);
 161                 }
 162         }
 163 }
 164
 165
 166 /* triangle */
 167
 168 /*
 169  * Clipping
 170  */
 171
 172 /* We clip the segment [a,b] against the 6 planes of the normal volume.
 173  * We compute the point 'c' of intersection and the value of the parameter 't'
 174  * of the intersection if x=a+t(b-a).
 175  */
 176
 177 #define clip_func(name,sign,dir,dir1,dir2) \
 178         static float name(V4 *c,V4 *a,V4 *b) \
 179 {\
 180         float t,dX,dY,dZ,dW,den;\
 181         dX = (b->X - a->X);\
 182         dY = (b->Y - a->Y);\
 183         dZ = (b->Z - a->Z);\
 184         dW = (b->W - a->W);\
 185         den = -(sign d ## dir) + dW;\
 186         if (den == 0) t=0;\
 187         else t = ( sign a->dir - a->W) / den;\
 188         c->dir1 = a->dir1 + t * d ## dir1;\
 189         c->dir2 = a->dir2 + t * d ## dir2;\
 190         c->W = a->W + t * dW;\
 191         c->dir = sign c->W;\
 192         return t;\
 193 }
 194
 195
 196 clip_func(clip_xmin,-,X,Y,Z)
 197
 198 clip_func(clip_xmax,+,X,Y,Z)
 199
 200 clip_func(clip_ymin,-,Y,X,Z)
 201
 202 clip_func(clip_ymax,+,Y,X,Z)
 203
 204 clip_func(clip_zmin,-,Z,X,Y)
 205
 206 clip_func(clip_zmax,+,Z,X,Y)
 207
 208
 209         float (*clip_proc[6])(V4 *,V4 *,V4 *)=  {
 210                 clip_xmin,clip_xmax,
 211                 clip_ymin,clip_ymax,
 212                 clip_zmin,clip_zmax
 213         };
 214
 215 static inline void updateTmp(GLContext *c,
 216                 GLVertex *q,GLVertex *p0,GLVertex *p1,float t)
 217 {
 218         if (c->current_shade_model == GL_SMOOTH) {
 219                 q->color.v[0]=p0->color.v[0] + (p1->color.v[0]-p0->color.v[0])*t;
 220                 q->color.v[1]=p0->color.v[1] + (p1->color.v[1]-p0->color.v[1])*t;
 221                 q->color.v[2]=p0->color.v[2] + (p1->color.v[2]-p0->color.v[2])*t;
 222         } else {
 223                 q->color.v[0]=p0->color.v[0];
 224                 q->color.v[1]=p0->color.v[1];
 225                 q->color.v[2]=p0->color.v[2];
 226         }
 227
 228         if (c->texture_2d_enabled) {
 229                 q->tex_coord.X=p0->tex_coord.X + (p1->tex_coord.X-p0->tex_coord.X)*t;
 230                 q->tex_coord.Y=p0->tex_coord.Y + (p1->tex_coord.Y-p0->tex_coord.Y)*t;
 231         }
 232
 233         q->clip_code=gl_clipcode(q->pc.X,q->pc.Y,q->pc.Z,q->pc.W);
 234         if (q->clip_code==0)
 235                 gl_transform_to_viewport(c,q);
 236 }
 237
 238 static void gl_draw_triangle_clip(GLContext *c,
 239                 GLVertex *p0,GLVertex *p1,GLVertex *p2,int clip_bit);
 240
 241 void gl_draw_triangle(GLContext *c,
 242                 GLVertex *p0,GLVertex *p1,GLVertex *p2)
 243 {
 244         int co,c_and,cc[3],front;
 245         float norm;
 246
 247         cc[0]=p0->clip_code;
 248         cc[1]=p1->clip_code;
 249         cc[2]=p2->clip_code;
 250
 251         co=cc[0] | cc[1] | cc[2];
 252
 253         /* we handle the non clipped case here to go faster */
 254         if (co==0) {
 255
 256                 norm=(float)(p1->zp.x-p0->zp.x)*(float)(p2->zp.y-p0->zp.y)-
 257                         (float)(p2->zp.x-p0->zp.x)*(float)(p1->zp.y-p0->zp.y);
 258
 259                 if (norm == 0) return;
 260
 261                 front = norm < 0.0;
 262                 front = front ^ c->current_front_face;
 263
 264                 /* back face culling */
 265                 if (c->cull_face_enabled) {
 266                         /* most used case first */
 267                         if (c->current_cull_face == GL_BACK) {
 268                                 if (front == 0) return;
 269                                 c->draw_triangle_front(c,p0,p1,p2);
 270                         } else if (c->current_cull_face == GL_FRONT) {
 271                                 if (front != 0) return;
 272                                 c->draw_triangle_back(c,p0,p1,p2);
 273                         } else {
 274                                 return;
 275                         }
 276                 } else {
 277                         /* no culling */
 278                         if (front) {
 279                                 c->draw_triangle_front(c,p0,p1,p2);
 280                         } else {
 281                                 c->draw_triangle_back(c,p0,p1,p2);
 282                         }
 283                 }
 284         } else {
 285                 c_and=cc[0] & cc[1] & cc[2];
 286                 if (c_and==0) {
 287                         gl_draw_triangle_clip(c,p0,p1,p2,0);
 288                 }
 289         }
 290 }
 291
 292 static void gl_draw_triangle_clip(GLContext *c,
 293                 GLVertex *p0,GLVertex *p1,GLVertex *p2,int clip_bit)
 294 {
 295         int co,c_and,co1,cc[3],edge_flag_tmp,clip_mask;
 296         GLVertex tmp1,tmp2,*q[3];
 297         float tt;
 298
 299         cc[0]=p0->clip_code;
 300         cc[1]=p1->clip_code;
 301         cc[2]=p2->clip_code;
 302
 303         co=cc[0] | cc[1] | cc[2];
 304         if (co == 0) {
 305                 gl_draw_triangle(c,p0,p1,p2);
 306         } else {
 307                 c_and=cc[0] & cc[1] & cc[2];
 308                 /* the triangle is completely outside */
 309                 if (c_and!=0) return;
 310
 311                 /* find the next direction to clip */
 312                 while (clip_bit < 6 && (co & (1 << clip_bit)) == 0)  {
 313                         clip_bit++;
 314                 }
 315
 316                 /* this test can be true only in case of rounding errors */
 317                 if (clip_bit == 6) {
 318 #if 0
 319                         printf("Error:\n");
 320                         printf("%f %f %f %f\n",p0->pc.X,p0->pc.Y,p0->pc.Z,p0->pc.W);
 321                         printf("%f %f %f %f\n",p1->pc.X,p1->pc.Y,p1->pc.Z,p1->pc.W);
 322                         printf("%f %f %f %f\n",p2->pc.X,p2->pc.Y,p2->pc.Z,p2->pc.W);
 323 #endif
 324                         return;
 325                 }
 326
 327                 clip_mask = 1 << clip_bit;
 328                 co1=(cc[0] ^ cc[1] ^ cc[2]) & clip_mask;
 329
 330                 if (co1)  {
 331                         /* one point outside */
 332
 333                         if (cc[0] & clip_mask) { q[0]=p0; q[1]=p1; q[2]=p2; }
 334                         else if (cc[1] & clip_mask) { q[0]=p1; q[1]=p2; q[2]=p0; }
 335                         else { q[0]=p2; q[1]=p0; q[2]=p1; }
 336
 337                         tt=clip_proc[clip_bit](&tmp1.pc,&q[0]->pc,&q[1]->pc);
 338                         updateTmp(c,&tmp1,q[0],q[1],tt);
 339
 340                         tt=clip_proc[clip_bit](&tmp2.pc,&q[0]->pc,&q[2]->pc);
 341                         updateTmp(c,&tmp2,q[0],q[2],tt);
 342
 343                         tmp1.edge_flag=q[0]->edge_flag;
 344                         edge_flag_tmp=q[2]->edge_flag;
 345                         q[2]->edge_flag=0;
 346                         gl_draw_triangle_clip(c,&tmp1,q[1],q[2],clip_bit+1);
 347
 348                         tmp2.edge_flag=1;
 349                         tmp1.edge_flag=0;
 350                         q[2]->edge_flag=edge_flag_tmp;
 351                         gl_draw_triangle_clip(c,&tmp2,&tmp1,q[2],clip_bit+1);
 352                 } else {
 353                         /* two points outside */
 354
 355                         if ((cc[0] & clip_mask)==0) { q[0]=p0; q[1]=p1; q[2]=p2; }
 356                         else if ((cc[1] & clip_mask)==0) { q[0]=p1; q[1]=p2; q[2]=p0; }
 357                         else { q[0]=p2; q[1]=p0; q[2]=p1; }
 358
 359                         tt=clip_proc[clip_bit](&tmp1.pc,&q[0]->pc,&q[1]->pc);
 360                         updateTmp(c,&tmp1,q[0],q[1],tt);
 361
 362                         tt=clip_proc[clip_bit](&tmp2.pc,&q[0]->pc,&q[2]->pc);
 363                         updateTmp(c,&tmp2,q[0],q[2],tt);
 364
 365                         tmp1.edge_flag=1;
 366                         tmp2.edge_flag=q[2]->edge_flag;
 367                         gl_draw_triangle_clip(c,q[0],&tmp1,&tmp2,clip_bit+1);
 368                 }
 369         }
 370 }
 371
 372
 373 void gl_draw_triangle_select(GLContext *c,
 374                 GLVertex *p0,GLVertex *p1,GLVertex *p2)
 375 {
 376         gl_add_select1(c,p0->zp.z,p1->zp.z,p2->zp.z);
 377 }
 378
 379 #ifdef PROFILE
 380 int count_triangles,count_triangles_textured,count_pixels;
 381 #endif
 382
 383 void gl_draw_triangle_fill(GLContext *c,
 384                 GLVertex *p0,GLVertex *p1,GLVertex *p2)
 385 {
 386 #ifdef PROFILE
 387         {
 388                 int norm;
 389                 assert(p0->zp.x >= 0 && p0->zp.x < c->zb->xsize);
 390                 assert(p0->zp.y >= 0 && p0->zp.y < c->zb->ysize);
 391                 assert(p1->zp.x >= 0 && p1->zp.x < c->zb->xsize);
 392                 assert(p1->zp.y >= 0 && p1->zp.y < c->zb->ysize);
 393                 assert(p2->zp.x >= 0 && p2->zp.x < c->zb->xsize);
 394                 assert(p2->zp.y >= 0 && p2->zp.y < c->zb->ysize);
 395
 396                 norm=(p1->zp.x-p0->zp.x)*(p2->zp.y-p0->zp.y)-
 397                         (p2->zp.x-p0->zp.x)*(p1->zp.y-p0->zp.y);
 398                 count_pixels+=abs(norm)/2;
 399                 count_triangles++;
 400         }
 401 #endif
 402
 403         if (c->texture_2d_enabled) {
 404 #ifdef PROFILE
 405                 count_triangles_textured++;
 406 #endif
 407                 ZB_setTexture(c->zb,c->current_texture->images[0].pixmap);
 408                 ZB_fillTriangleMappingPerspective(c->zb,&p0->zp,&p1->zp,&p2->zp);
 409         } else if (c->current_shade_model == GL_SMOOTH) {
 410                 ZB_fillTriangleSmooth(c->zb,&p0->zp,&p1->zp,&p2->zp);
 411         } else {
 412                 ZB_fillTriangleFlat(c->zb,&p0->zp,&p1->zp,&p2->zp);
 413         }
 414 }
 415
 416 /* Render a clipped triangle in line mode */
 417
 418 void gl_draw_triangle_line(GLContext *c,
 419                 GLVertex *p0,GLVertex *p1,GLVertex *p2)
 420 {
 421         if (c->depth_test) {
 422                 if (p0->edge_flag) ZB_line_z(c->zb,&p0->zp,&p1->zp);
 423                 if (p1->edge_flag) ZB_line_z(c->zb,&p1->zp,&p2->zp);
 424                 if (p2->edge_flag) ZB_line_z(c->zb,&p2->zp,&p0->zp);
 425         } else {
 426                 if (p0->edge_flag) ZB_line(c->zb,&p0->zp,&p1->zp);
 427                 if (p1->edge_flag) ZB_line(c->zb,&p1->zp,&p2->zp);
 428                 if (p2->edge_flag) ZB_line(c->zb,&p2->zp,&p0->zp);
 429         }
 430 }
 431
 432
 433
 434 /* Render a clipped triangle in point mode */
 435 void gl_draw_triangle_point(GLContext *c,
 436                 GLVertex *p0,GLVertex *p1,GLVertex *p2)
 437 {
 438         if (p0->edge_flag) ZB_plot(c->zb,&p0->zp);
 439         if (p1->edge_flag) ZB_plot(c->zb,&p1->zp);
 440         if (p2->edge_flag) ZB_plot(c->zb,&p2->zp);
 441 }
 442
 443
 444
 445