Panda3D
 All Classes Functions Variables Enumerations
clip.cxx
00001 #include "zgl.h"
00002 #include <limits.h>
00003 
00004 /* fill triangle profile */
00005 /* #define PROFILE */
00006 
00007 #define CLIP_XMIN   (1<<0)
00008 #define CLIP_XMAX   (1<<1)
00009 #define CLIP_YMIN   (1<<2)
00010 #define CLIP_YMAX   (1<<3)
00011 #define CLIP_ZMIN   (1<<4)
00012 #define CLIP_ZMAX   (1<<5)
00013 
00014 void gl_transform_to_viewport(GLContext *c,GLVertex *v)
00015 {
00016   PN_stdfloat winv;
00017 
00018   /* coordinates */
00019   winv = 1.0f / v->pc.v[3];
00020   v->zp.x= (int) ( v->pc.v[0] * winv * c->viewport.scale.v[0] 
00021                    + c->viewport.trans.v[0] );
00022   v->zp.y= (int) ( v->pc.v[1] * winv * c->viewport.scale.v[1] 
00023                    + c->viewport.trans.v[1] );
00024   v->zp.z= (int) ( v->pc.v[2] * winv * c->viewport.scale.v[2] 
00025                    + c->viewport.trans.v[2] );
00026 
00027   // Add the z-bias, if any.  Be careful not to overflow the int.
00028   int z = v->zp.z + (c->zbias << (ZB_POINT_Z_FRAC_BITS + 4));
00029   if (z < v->zp.z && c->zbias > 0) {
00030     v->zp.z = INT_MAX;
00031   } else if (z > v->zp.z && c->zbias < 0) {
00032     v->zp.z = -INT_MAX;
00033   } else {
00034     v->zp.z = z;
00035   }
00036 
00037   /* color */
00038   v->zp.r=(int)(v->color.v[0] * (ZB_POINT_RED_MAX - ZB_POINT_RED_MIN) 
00039                 + ZB_POINT_RED_MIN);
00040   v->zp.g=(int)(v->color.v[1] * (ZB_POINT_GREEN_MAX - ZB_POINT_GREEN_MIN) 
00041                 + ZB_POINT_GREEN_MIN);
00042   v->zp.b=(int)(v->color.v[2] * (ZB_POINT_BLUE_MAX - ZB_POINT_BLUE_MIN) 
00043                 + ZB_POINT_BLUE_MIN);
00044   v->zp.a=(int)(v->color.v[3] * (ZB_POINT_ALPHA_MAX - ZB_POINT_ALPHA_MIN) 
00045                 + ZB_POINT_ALPHA_MIN);
00046   
00047   /* texture */
00048   if (c->num_textures_enabled >= 1) {
00049     static const int si = 0;
00050     v->zp.s = (int)(v->tex_coord[si].v[0] * c->current_textures[si]->s_max); 
00051     v->zp.t = (int)(v->tex_coord[si].v[1] * c->current_textures[si]->t_max);
00052   }
00053   if (c->num_textures_enabled >= 2) {
00054     static const int si = 1;
00055     v->zp.sa = (int)(v->tex_coord[si].v[0] * c->current_textures[si]->s_max); 
00056     v->zp.ta = (int)(v->tex_coord[si].v[1] * c->current_textures[si]->t_max);
00057   }
00058   if (c->num_textures_enabled >= 3) {
00059     static const int si = 2;
00060     v->zp.sb = (int)(v->tex_coord[si].v[0] * c->current_textures[si]->s_max); 
00061     v->zp.tb = (int)(v->tex_coord[si].v[1] * c->current_textures[si]->t_max);
00062   }
00063 }
00064 
00065 
00066 /* point */
00067 
00068 void gl_draw_point(GLContext *c,GLVertex *p0)
00069 {
00070   if (p0->clip_code == 0) {
00071     ZB_plot(c->zb,&p0->zp);
00072   }
00073 }
00074 
00075 /* line */
00076 
00077 static inline void interpolate(GLVertex *q,GLVertex *p0,GLVertex *p1,PN_stdfloat t)
00078 {
00079   q->pc.v[0]=p0->pc.v[0]+(p1->pc.v[0]-p0->pc.v[0])*t;
00080   q->pc.v[1]=p0->pc.v[1]+(p1->pc.v[1]-p0->pc.v[1])*t;
00081   q->pc.v[2]=p0->pc.v[2]+(p1->pc.v[2]-p0->pc.v[2])*t;
00082   q->pc.v[3]=p0->pc.v[3]+(p1->pc.v[3]-p0->pc.v[3])*t;
00083 
00084   q->color.v[0]=p0->color.v[0] + (p1->color.v[0]-p0->color.v[0])*t;
00085   q->color.v[1]=p0->color.v[1] + (p1->color.v[1]-p0->color.v[1])*t;
00086   q->color.v[2]=p0->color.v[2] + (p1->color.v[2]-p0->color.v[2])*t;
00087   q->color.v[3]=p0->color.v[3] + (p1->color.v[3]-p0->color.v[3])*t;
00088 }
00089 
00090 /*
00091  * Line Clipping 
00092  */
00093 
00094 /* Line Clipping algorithm from 'Computer Graphics', Principles and
00095    Practice */
00096 static inline int ClipLine1(PN_stdfloat denom,PN_stdfloat num,PN_stdfloat *tmin,PN_stdfloat *tmax)
00097 {
00098   PN_stdfloat t;
00099 
00100   if (denom>0) {
00101     t=num/denom;
00102     if (t>*tmax) return 0;
00103     if (t>*tmin) *tmin=t;
00104   } else if (denom<0) {
00105     t=num/denom;
00106     if (t<*tmin) return 0;
00107     if (t<*tmax) *tmax=t;
00108   } else if (num>0) return 0;
00109   return 1;
00110 }
00111 
00112 void gl_draw_line(GLContext *c,GLVertex *p1,GLVertex *p2)
00113 {
00114   PN_stdfloat dx,dy,dz,dw,x1,y1,z1,w1;
00115   PN_stdfloat tmin,tmax;
00116   GLVertex q1,q2;
00117   int cc1,cc2;
00118   
00119   cc1=p1->clip_code;
00120   cc2=p2->clip_code;
00121 
00122   if ( (cc1 | cc2) == 0) {
00123     if (c->depth_test)
00124       ZB_line_z(c->zb,&p1->zp,&p2->zp);
00125     else
00126       ZB_line(c->zb,&p1->zp,&p2->zp);
00127   } else if ( (cc1&cc2) != 0 ) {
00128     return;
00129   } else {
00130     dx=p2->pc.v[0]-p1->pc.v[0];
00131     dy=p2->pc.v[1]-p1->pc.v[1];
00132     dz=p2->pc.v[2]-p1->pc.v[2];
00133     dw=p2->pc.v[3]-p1->pc.v[3];
00134     x1=p1->pc.v[0];
00135     y1=p1->pc.v[1];
00136     z1=p1->pc.v[2];
00137     w1=p1->pc.v[3];
00138     
00139     tmin=0;
00140     tmax=1;
00141     if (ClipLine1(dx+dw,-x1-w1,&tmin,&tmax) &&
00142         ClipLine1(-dx+dw,x1-w1,&tmin,&tmax) &&
00143         ClipLine1(dy+dw,-y1-w1,&tmin,&tmax) &&
00144         ClipLine1(-dy+dw,y1-w1,&tmin,&tmax) &&
00145         ClipLine1(dz+dw,-z1-w1,&tmin,&tmax) && 
00146         ClipLine1(-dz+dw,z1-w1,&tmin,&tmax)) {
00147 
00148       interpolate(&q1,p1,p2,tmin);
00149       interpolate(&q2,p1,p2,tmax);
00150       gl_transform_to_viewport(c,&q1);
00151       gl_transform_to_viewport(c,&q2);
00152 
00153       if (c->depth_test)
00154           ZB_line_z(c->zb,&q1.zp,&q2.zp);
00155       else
00156           ZB_line(c->zb,&q1.zp,&q2.zp);
00157     }
00158   }
00159 }
00160 
00161 
00162 /* triangle */
00163 
00164 /*
00165  * Clipping
00166  */
00167 
00168 /* We clip the segment [a,b] against the 6 planes of the normal volume.
00169  * We compute the point 'c' of intersection and the value of the parameter 't'
00170  * of the intersection if x=a+t(b-a). 
00171  */
00172 
00173 #define clip_func(name, sign, dir, dir1, dir2) \
00174 static PN_stdfloat name(V4 *c, V4 *a, V4 *b) \
00175 {\
00176   PN_stdfloat t,den;\
00177   PN_stdfloat d[4];\
00178   d[0] = (b->v[0] - a->v[0]);\
00179   d[1] = (b->v[1] - a->v[1]);\
00180   d[2] = (b->v[2] - a->v[2]);\
00181   d[3] = (b->v[3] - a->v[3]);\
00182   den = -(sign d[dir]) + d[3];\
00183   if (den == 0) t=0;\
00184   else t = ( sign a->v[dir] - a->v[3]) / den;\
00185   c->v[dir1] = a->v[dir1] + t * d[dir1];\
00186   c->v[dir2] = a->v[dir2] + t * d[dir2];\
00187   c->v[3] = a->v[3] + t * d[3];\
00188   c->v[dir] = sign c->v[3];\
00189   return t;\
00190 }
00191 
00192 
00193 clip_func(clip_xmin, -, 0, 1, 2)
00194 
00195 clip_func(clip_xmax, +, 0, 1, 2)
00196 
00197 clip_func(clip_ymin, -, 1, 0, 2)
00198 
00199 clip_func(clip_ymax, +, 1, 0, 2)
00200 
00201 clip_func(clip_zmin, -, 2, 0, 1)
00202 
00203 clip_func(clip_zmax, +, 2, 0, 1)
00204 
00205 
00206 PN_stdfloat (*clip_proc[6])(V4 *,V4 *,V4 *)=  {
00207     clip_xmin,clip_xmax,
00208     clip_ymin,clip_ymax,
00209     clip_zmin,clip_zmax
00210 };
00211 
00212 static inline void updateTmp(GLContext *c,
00213                  GLVertex *q,GLVertex *p0,GLVertex *p1,PN_stdfloat t)
00214 {
00215   if (c->smooth_shade_model) {
00216     q->color.v[0]=p0->color.v[0] + (p1->color.v[0]-p0->color.v[0])*t;
00217     q->color.v[1]=p0->color.v[1] + (p1->color.v[1]-p0->color.v[1])*t;
00218     q->color.v[2]=p0->color.v[2] + (p1->color.v[2]-p0->color.v[2])*t;
00219     q->color.v[3]=p0->color.v[3] + (p1->color.v[3]-p0->color.v[3])*t;
00220   } else {
00221     q->color.v[0]=p0->color.v[0];
00222     q->color.v[1]=p0->color.v[1];
00223     q->color.v[2]=p0->color.v[2];
00224     q->color.v[3]=p0->color.v[3];
00225   }
00226 
00227   for (int si = 0; si < c->num_textures_enabled; ++si) {
00228     q->tex_coord[si].v[0]=p0->tex_coord[si].v[0] + (p1->tex_coord[si].v[0]-p0->tex_coord[si].v[0])*t;
00229     q->tex_coord[si].v[1]=p0->tex_coord[si].v[1] + (p1->tex_coord[si].v[1]-p0->tex_coord[si].v[1])*t;
00230   }
00231 
00232   q->clip_code=gl_clipcode(q->pc.v[0],q->pc.v[1],q->pc.v[2],q->pc.v[3]);
00233   if (q->clip_code==0) {
00234     gl_transform_to_viewport(c,q);
00235   }
00236 }
00237 
00238 static void gl_draw_triangle_clip(GLContext *c,
00239                                   GLVertex *p0,GLVertex *p1,GLVertex *p2,int clip_bit);
00240 
00241 void gl_draw_triangle(GLContext *c,
00242                       GLVertex *p0,GLVertex *p1,GLVertex *p2)
00243 {
00244   int co,c_and,cc[3],front;
00245   PN_stdfloat norm;
00246   
00247   cc[0]=p0->clip_code;
00248   cc[1]=p1->clip_code;
00249   cc[2]=p2->clip_code;
00250   
00251   co=cc[0] | cc[1] | cc[2];
00252 
00253   /* we handle the non clipped case here to go faster */
00254   if (co==0) {
00255     
00256       norm=(PN_stdfloat)(p1->zp.x-p0->zp.x)*(PN_stdfloat)(p2->zp.y-p0->zp.y)-
00257         (PN_stdfloat)(p2->zp.x-p0->zp.x)*(PN_stdfloat)(p1->zp.y-p0->zp.y);
00258       
00259       if (norm == 0) return;
00260 
00261       front = norm < 0.0;
00262   
00263       /* back face culling */
00264       if (c->cull_face_enabled) {
00265         /* most used case first */
00266         if (c->cull_clockwise) {
00267           if (front == 0) return;
00268           c->draw_triangle_front(c,p0,p1,p2);
00269         } else {
00270           if (front != 0) return;
00271           c->draw_triangle_back(c,p0,p1,p2);
00272         }
00273       } else {
00274         /* no culling */
00275         if (front) {
00276           c->draw_triangle_front(c,p0,p1,p2);
00277         } else {
00278           c->draw_triangle_back(c,p0,p1,p2);
00279         }
00280       }
00281   } else {
00282     c_and=cc[0] & cc[1] & cc[2];
00283     if (c_and==0) {
00284       gl_draw_triangle_clip(c,p0,p1,p2,0);
00285     }
00286   }
00287 }
00288 
00289 static void gl_draw_triangle_clip(GLContext *c,
00290                                   GLVertex *p0,GLVertex *p1,GLVertex *p2,int clip_bit)
00291 {
00292   int co,c_and,co1,cc[3],edge_flag_tmp,clip_mask;
00293   GLVertex tmp1,tmp2,*q[3];
00294   PN_stdfloat tt;
00295 
00296   cc[0]=p0->clip_code;
00297   cc[1]=p1->clip_code;
00298   cc[2]=p2->clip_code;
00299   
00300   co=cc[0] | cc[1] | cc[2];
00301   if (co == 0) {
00302     gl_draw_triangle(c,p0,p1,p2);
00303   } else {
00304     c_and=cc[0] & cc[1] & cc[2];
00305     /* the triangle is completely outside */
00306     if (c_and!=0) return;
00307 
00308     /* find the next direction to clip */
00309     while (clip_bit < 6 && (co & (1 << clip_bit)) == 0)  {
00310       clip_bit++;
00311     }
00312 
00313     /* this test can be true only in case of rounding errors */
00314     if (clip_bit == 6) {
00315 #if 0
00316       printf("Error:\n");
00317       printf("%f %f %f %f\n",p0->pc.v[0],p0->pc.v[1],p0->pc.v[2],p0->pc.v[3]);
00318       printf("%f %f %f %f\n",p1->pc.v[0],p1->pc.v[1],p1->pc.v[2],p1->pc.v[3]);
00319       printf("%f %f %f %f\n",p2->pc.v[0],p2->pc.v[1],p2->pc.v[2],p2->pc.v[3]);
00320 #endif
00321       return;
00322     }
00323   
00324     clip_mask = 1 << clip_bit;
00325     co1=(cc[0] ^ cc[1] ^ cc[2]) & clip_mask;
00326     
00327     if (co1)  { 
00328       /* one point outside */
00329 
00330       if (cc[0] & clip_mask) { q[0]=p0; q[1]=p1; q[2]=p2; }
00331       else if (cc[1] & clip_mask) { q[0]=p1; q[1]=p2; q[2]=p0; }
00332       else { q[0]=p2; q[1]=p0; q[2]=p1; }
00333       
00334       tt=clip_proc[clip_bit](&tmp1.pc,&q[0]->pc,&q[1]->pc);
00335       updateTmp(c,&tmp1,q[0],q[1],tt);
00336 
00337       tt=clip_proc[clip_bit](&tmp2.pc,&q[0]->pc,&q[2]->pc);
00338       updateTmp(c,&tmp2,q[0],q[2],tt);
00339 
00340       tmp1.edge_flag=q[0]->edge_flag;
00341       edge_flag_tmp=q[2]->edge_flag;
00342       q[2]->edge_flag=0;
00343       gl_draw_triangle_clip(c,&tmp1,q[1],q[2],clip_bit+1);
00344 
00345       tmp2.edge_flag=1;
00346       tmp1.edge_flag=0;
00347       q[2]->edge_flag=edge_flag_tmp;
00348       gl_draw_triangle_clip(c,&tmp2,&tmp1,q[2],clip_bit+1);
00349     } else {
00350       /* two points outside */
00351 
00352       if ((cc[0] & clip_mask)==0) { q[0]=p0; q[1]=p1; q[2]=p2; }
00353       else if ((cc[1] & clip_mask)==0) { q[0]=p1; q[1]=p2; q[2]=p0; } 
00354       else { q[0]=p2; q[1]=p0; q[2]=p1; }
00355       
00356       tt=clip_proc[clip_bit](&tmp1.pc,&q[0]->pc,&q[1]->pc);
00357       updateTmp(c,&tmp1,q[0],q[1],tt);
00358 
00359       tt=clip_proc[clip_bit](&tmp2.pc,&q[0]->pc,&q[2]->pc);
00360       updateTmp(c,&tmp2,q[0],q[2],tt);
00361       
00362       tmp1.edge_flag=1;
00363       tmp2.edge_flag=q[2]->edge_flag;
00364       gl_draw_triangle_clip(c,q[0],&tmp1,&tmp2,clip_bit+1);
00365     }
00366   }
00367 }
00368 
00369 
00370 #ifdef PROFILE
00371 int count_triangles,count_triangles_textured,count_pixels;
00372 #endif
00373 
00374 void gl_draw_triangle_fill(GLContext *c,
00375                            GLVertex *p0,GLVertex *p1,GLVertex *p2)
00376 {
00377 #ifdef PROFILE
00378   {
00379     int norm;
00380     assert(p0->zp.x >= 0 && p0->zp.x < c->zb->xsize);
00381     assert(p0->zp.y >= 0 && p0->zp.y < c->zb->ysize);
00382     assert(p1->zp.x >= 0 && p1->zp.x < c->zb->xsize);
00383     assert(p1->zp.y >= 0 && p1->zp.y < c->zb->ysize);
00384     assert(p2->zp.x >= 0 && p2->zp.x < c->zb->xsize);
00385     assert(p2->zp.y >= 0 && p2->zp.y < c->zb->ysize);
00386     
00387     norm=(p1->zp.x-p0->zp.x)*(p2->zp.y-p0->zp.y)-
00388       (p2->zp.x-p0->zp.x)*(p1->zp.y-p0->zp.y);
00389     count_pixels+=abs(norm)/2;
00390     count_triangles++;
00391   }
00392 #endif
00393     
00394 #ifdef PROFILE
00395   if (c->num_textures_enabled != 0) {
00396     count_triangles_textured++;
00397   }
00398 #endif
00399 
00400   (*c->zb_fill_tri)(c->zb,&p0->zp,&p1->zp,&p2->zp);
00401 }
00402 
00403 /* Render a clipped triangle in line mode */  
00404 
00405 void gl_draw_triangle_line(GLContext *c,
00406                            GLVertex *p0,GLVertex *p1,GLVertex *p2)
00407 {
00408     if (c->depth_test) {
00409         if (p0->edge_flag) ZB_line_z(c->zb,&p0->zp,&p1->zp);
00410         if (p1->edge_flag) ZB_line_z(c->zb,&p1->zp,&p2->zp);
00411         if (p2->edge_flag) ZB_line_z(c->zb,&p2->zp,&p0->zp);
00412     } else {
00413         if (p0->edge_flag) ZB_line(c->zb,&p0->zp,&p1->zp);
00414         if (p1->edge_flag) ZB_line(c->zb,&p1->zp,&p2->zp);
00415         if (p2->edge_flag) ZB_line(c->zb,&p2->zp,&p0->zp);
00416     }
00417 }
00418 
00419 
00420 
00421 /* Render a clipped triangle in point mode */
00422 void gl_draw_triangle_point(GLContext *c,
00423                             GLVertex *p0,GLVertex *p1,GLVertex *p2)
00424 {
00425   if (p0->edge_flag) ZB_plot(c->zb,&p0->zp);
00426   if (p1->edge_flag) ZB_plot(c->zb,&p1->zp);
00427   if (p2->edge_flag) ZB_plot(c->zb,&p2->zp);
00428 }
00429 
00430 
00431 
00432 
 All Classes Functions Variables Enumerations