ResidualVM logo ResidualVM website - Forums - Contact us BuildBot - Doxygen - Wiki curved edge

clip.cpp

Go to the documentation of this file.
00001 /* ResidualVM - A 3D game interpreter
00002  *
00003  * ResidualVM is the legal property of its developers, whose names
00004  * are too numerous to list here. Please refer to the AUTHORS
00005  * file distributed with this source distribution.
00006  *
00007  * This program is free software; you can redistribute it and/or
00008  * modify it under the terms of the GNU General Public License
00009  * as published by the Free Software Foundation; either version 2
00010  * of the License, or (at your option) any later version.
00011  *
00012  * This program is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015  * GNU General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU General Public License
00018  * along with this program; if not, write to the Free Software
00019  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
00020  *
00021  */
00022 
00023 /*
00024  * This file is based on, or a modified version of code from TinyGL (C) 1997-1998 Fabrice Bellard,
00025  * which is licensed under the zlib-license (see LICENSE).
00026  * It also has modifications by the ResidualVM-team, which are covered under the GPLv2 (or later).
00027  */
00028 
00029 #include "graphics/tinygl/zgl.h"
00030 
00031 namespace TinyGL {
00032 
00033 // fill triangle profile
00034 // #define TINYGL_PROFILE
00035 
00036 #define CLIP_XMIN   (1 << 0)
00037 #define CLIP_XMAX   (1 << 1)
00038 #define CLIP_YMIN   (1 << 2)
00039 #define CLIP_YMAX   (1 << 3)
00040 #define CLIP_ZMIN   (1 << 4)
00041 #define CLIP_ZMAX   (1 << 5)
00042 
00043 void gl_transform_to_viewport(GLContext *c, GLVertex *v) {
00044     float winv;
00045 
00046     // coordinates
00047     winv = (float)(1.0 / v->pc.W);
00048     v->zp.x = (int)(v->pc.X * winv * c->viewport.scale.X + c->viewport.trans.X);
00049     v->zp.y = (int)(v->pc.Y * winv * c->viewport.scale.Y + c->viewport.trans.Y);
00050     v->zp.z = (int)(v->pc.Z * winv * c->viewport.scale.Z + c->viewport.trans.Z);
00051     // color
00052     v->zp.r = (int)(v->color.X * ZB_POINT_RED_MAX);
00053     v->zp.g = (int)(v->color.Y * ZB_POINT_GREEN_MAX);
00054     v->zp.b = (int)(v->color.Z * ZB_POINT_BLUE_MAX);
00055     v->zp.a = (int)(v->color.W * ZB_POINT_ALPHA_MAX);
00056 
00057     // texture
00058     if (c->texture_2d_enabled) {
00059         v->zp.s = (int)(v->tex_coord.X * ZB_POINT_ST_MAX);
00060         v->zp.t = (int)(v->tex_coord.Y * ZB_POINT_ST_MAX);
00061     }
00062 }
00063 
00064 static void gl_add_select1(GLContext *c, int z1, int z2, int z3) {
00065     int min, max;
00066 
00067     min = max = z1;
00068     if (z2 < min)
00069         min = z2;
00070     if (z3 < min)
00071         min = z3;
00072     if (z2 > max)
00073         max = z2;
00074     if (z3 > max)
00075         max = z3;
00076 
00077     gl_add_select(c, 0xffffffff - min, 0xffffffff - max);
00078 }
00079 
00080 // point
00081 
00082 void gl_draw_point(GLContext *c, GLVertex *p0) {
00083     if (p0->clip_code == 0) {
00084         if (c->render_mode == TGL_SELECT) {
00085             gl_add_select(c, p0->zp.z, p0->zp.z);
00086         } else {
00087             c->fb->plot(&p0->zp);
00088         }
00089     }
00090 }
00091 
00092 // line
00093 
00094 static inline void interpolate_color(GLContext *c, GLVertex *q, GLVertex *p0, GLVertex *p1, float t) {
00095     if (c->current_shade_model == TGL_SMOOTH)
00096         q->color = p0->color + (p1->color - p0->color) * t;
00097     else
00098         q->color = p0->color;
00099 }
00100 
00101 static inline void interpolate(GLContext *c, GLVertex *q, GLVertex *p0, GLVertex *p1, float t) {
00102     q->pc = p0->pc + (p1->pc - p0->pc) * t;
00103     interpolate_color(c, q, p0, p1, t);
00104 }
00105 
00106 // Line Clipping
00107 
00108 // Line Clipping algorithm from 'Computer Graphics', Principles and
00109 // Practice
00110 static inline int ClipLine1(float denom, float num, float *tmin, float *tmax) {
00111     float t;
00112 
00113     if (denom > 0) {
00114         t = num / denom;
00115         if (t > *tmax)
00116             return 0;
00117         if (t > *tmin)
00118             *tmin = t;
00119     } else if (denom < 0) {
00120         t = num / denom;
00121         if (t < *tmin)
00122             return 0;
00123         if (t < *tmax)
00124             *tmax = t;
00125     } else if (num > 0)
00126         return 0;
00127 
00128     return 1;
00129 }
00130 
00131 void gl_draw_line(GLContext *c, GLVertex *p1, GLVertex *p2) {
00132     float dx, dy, dz, dw, x1, y1, z1, w1;
00133     float tmin, tmax;
00134     GLVertex q1, q2;
00135     int cc1, cc2;
00136 
00137     cc1 = p1->clip_code;
00138     cc2 = p2->clip_code;
00139 
00140     if ((cc1 | cc2) == 0) {
00141         if (c->render_mode == TGL_SELECT) {
00142             gl_add_select1(c, p1->zp.z, p2->zp.z, p2->zp.z);
00143         } else {
00144             if (c->depth_test)
00145                 c->fb->fillLineZ(&p1->zp, &p2->zp);
00146             else
00147                 c->fb->fillLine(&p1->zp, &p2->zp);
00148         }
00149     } else if ((cc1 & cc2) != 0) {
00150         return;
00151     } else {
00152         dx = p2->pc.X - p1->pc.X;
00153         dy = p2->pc.Y - p1->pc.Y;
00154         dz = p2->pc.Z - p1->pc.Z;
00155         dw = p2->pc.W - p1->pc.W;
00156         x1 = p1->pc.X;
00157         y1 = p1->pc.Y;
00158         z1 = p1->pc.Z;
00159         w1 = p1->pc.W;
00160 
00161         tmin = 0;
00162         tmax = 1;
00163         if (ClipLine1(dx + dw, -x1 - w1, &tmin, &tmax) &&
00164                 ClipLine1(-dx + dw, x1 - w1, &tmin, &tmax) &&
00165                 ClipLine1(dy + dw, -y1 - w1, &tmin, &tmax) &&
00166                 ClipLine1(-dy + dw, y1 - w1, &tmin, &tmax) &&
00167                 ClipLine1(dz + dw, -z1 - w1, &tmin, &tmax) &&
00168                 ClipLine1(-dz + dw, z1 - w1, &tmin, &tmax)) {
00169             interpolate(c, &q1, p1, p2, tmin);
00170             interpolate(c, &q2, p1, p2, tmax);
00171             gl_transform_to_viewport(c, &q1);
00172             gl_transform_to_viewport(c, &q2);
00173 
00174             if (c->depth_test)
00175                 c->fb->fillLineZ(&q1.zp, &q2.zp);
00176             else
00177                 c->fb->fillLine(&q1.zp, &q2.zp);
00178         }
00179     }
00180 }
00181 
00182 // triangle
00183 
00184 // Clipping
00185 
00186 // We clip the segment [a,b] against the 6 planes of the normal volume.
00187 // We compute the point 'c' of intersection and the value of the parameter 't'
00188 // of the intersection if x=a+t(b-a).
00189 
00190 #define clip_func(name, sign, dir, dir1, dir2) \
00191 static float name(Vector4 *c, Vector4 *a, Vector4 *b) { \
00192     float t, dX, dY, dZ, dW, den;\
00193     dX = (b->X - a->X); \
00194     dY = (b->Y - a->Y); \
00195     dZ = (b->Z - a->Z); \
00196     dW = (b->W - a->W); \
00197     den = -(sign d ## dir) + dW; \
00198     if (den == 0) \
00199         t = 0; \
00200     else \
00201         t = (sign a->dir - a->W) / den; \
00202     c-> dir1 = (a->dir1 + t * d ## dir1); \
00203     c-> dir2 = (a->dir2 + t * d ## dir2); \
00204     c->W = (a->W + t * dW); \
00205     c-> dir = (sign c->W); \
00206     return t; \
00207 }
00208 
00209 clip_func(clip_xmin, -, X, Y, Z)
00210 clip_func(clip_xmax, +, X, Y, Z)
00211 clip_func(clip_ymin, -, Y, X, Z)
00212 clip_func(clip_ymax, +, Y, X, Z)
00213 clip_func(clip_zmin, -, Z, X, Y)
00214 clip_func(clip_zmax, +, Z, X, Y)
00215 
00216 float(*clip_proc[6])(Vector4 *, Vector4 *, Vector4 *) =  {
00217     clip_xmin, clip_xmax,
00218     clip_ymin, clip_ymax,
00219     clip_zmin, clip_zmax
00220 };
00221 
00222 static inline void updateTmp(GLContext *c, GLVertex *q, GLVertex *p0, GLVertex *p1, float t) {
00223     interpolate_color(c, q, p0, p1, t);
00224 
00225     if (c->texture_2d_enabled) {
00226         // NOTE: This could be implemented with operator overloading,
00227         // but i'm not 100% sure that we can completely disregard Z and W components so I'm leaving it like this for now.
00228         q->tex_coord.X = (p0->tex_coord.X + (p1->tex_coord.X - p0->tex_coord.X) * t);
00229         q->tex_coord.Y = (p0->tex_coord.Y + (p1->tex_coord.Y - p0->tex_coord.Y) * t);
00230     }
00231 
00232     q->clip_code = gl_clipcode(q->pc.X, q->pc.Y, q->pc.Z, q->pc.W);
00233     if (q->clip_code == 0)
00234         gl_transform_to_viewport(c, q);
00235 }
00236 
00237 static void gl_draw_triangle_clip(GLContext *c, GLVertex *p0, GLVertex *p1, GLVertex *p2, int clip_bit);
00238 
00239 void gl_draw_triangle(GLContext *c, GLVertex *p0, GLVertex *p1, GLVertex *p2) {
00240     int co, c_and, cc[3], front;
00241     float norm;
00242 
00243     cc[0] = p0->clip_code;
00244     cc[1] = p1->clip_code;
00245     cc[2] = p2->clip_code;
00246 
00247     co = cc[0] | cc[1] | cc[2];
00248 
00249     // we handle the non clipped case here to go faster
00250     if (co == 0) {
00251         norm = (float)(p1->zp.x - p0->zp.x) * (float)(p2->zp.y - p0->zp.y) -
00252                (float)(p2->zp.x - p0->zp.x) * (float)(p1->zp.y - p0->zp.y);
00253         if (norm == 0)
00254             return;
00255 
00256         front = norm < 0.0;
00257         front = front ^ c->current_front_face;
00258 
00259         // back face culling
00260         if (c->cull_face_enabled) {
00261             // most used case first */
00262             if (c->current_cull_face == TGL_BACK) {
00263                 if (front == 0)
00264                     return;
00265                 c->draw_triangle_front(c, p0, p1, p2);
00266             } else if (c->current_cull_face == TGL_FRONT) {
00267                 if (front != 0)
00268                     return;
00269                 c->draw_triangle_back(c, p0, p1, p2);
00270             } else {
00271                 return;
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, GLVertex *p0, GLVertex *p1, GLVertex *p2, int clip_bit) {
00290     int co, c_and, co1, cc[3], edge_flag_tmp, clip_mask;
00291     GLVertex tmp1, tmp2, *q[3];
00292     float tt;
00293 
00294     cc[0] = p0->clip_code;
00295     cc[1] = p1->clip_code;
00296     cc[2] = p2->clip_code;
00297 
00298     co = cc[0] | cc[1] | cc[2];
00299     if (co == 0) {
00300         gl_draw_triangle(c, p0, p1, p2);
00301     } else {
00302         c_and = cc[0] & cc[1] & cc[2];
00303         // the triangle is completely outside
00304         if (c_and != 0)
00305             return;
00306 
00307         // find the next direction to clip
00308         while (clip_bit < 6 && (co & (1 << clip_bit)) == 0) {
00309             clip_bit++;
00310         }
00311 
00312         // this test can be true only in case of rounding errors
00313         if (clip_bit == 6) {
00314 #if 0
00315             printf("Error:\n");
00316             printf("%f %f %f %f\n", p0->pc.X, p0->pc.Y, p0->pc.Z, p0->pc.W);
00317             printf("%f %f %f %f\n", p1->pc.X, p1->pc.Y, p1->pc.Z, p1->pc.W);
00318             printf("%f %f %f %f\n", p2->pc.X, p2->pc.Y, p2->pc.Z, p2->pc.W);
00319 #endif
00320             return;
00321         }
00322 
00323         clip_mask = 1 << clip_bit;
00324         co1 = (cc[0] ^ cc[1] ^ cc[2]) & clip_mask;
00325 
00326         if (co1)  {
00327             // one point outside
00328             if (cc[0] & clip_mask) {
00329                 q[0] = p0; q[1] = p1; q[2] = p2;
00330             } else if (cc[1] & clip_mask) {
00331                 q[0] = p1; q[1] = p2; q[2] = p0;
00332             } else {
00333                 q[0] = p2; q[1] = p0; q[2] = p1;
00334             }
00335 
00336             tt = clip_proc[clip_bit](&tmp1.pc, &q[0]->pc, &q[1]->pc);
00337             updateTmp(c, &tmp1, q[0], q[1], tt);
00338 
00339             tt = clip_proc[clip_bit](&tmp2.pc, &q[0]->pc, &q[2]->pc);
00340             updateTmp(c, &tmp2, q[0], q[2], tt);
00341 
00342             tmp1.edge_flag = q[0]->edge_flag;
00343             edge_flag_tmp = q[2]->edge_flag;
00344             q[2]->edge_flag = 0;
00345             gl_draw_triangle_clip(c, &tmp1, q[1], q[2], clip_bit + 1);
00346 
00347             tmp2.edge_flag = 1;
00348             tmp1.edge_flag = 0;
00349             q[2]->edge_flag = edge_flag_tmp;
00350             gl_draw_triangle_clip(c, &tmp2, &tmp1, q[2], clip_bit + 1);
00351         } else {
00352             // two points outside
00353             if ((cc[0] & clip_mask) == 0) {
00354                 q[0] = p0; q[1] = p1; q[2] = p2;
00355             } else if ((cc[1] & clip_mask) == 0) {
00356                 q[0] = p1; q[1] = p2; q[2] = p0;
00357             } else {
00358                 q[0] = p2; q[1] = p0; q[2] = p1;
00359             }
00360 
00361             tt = clip_proc[clip_bit](&tmp1.pc, &q[0]->pc, &q[1]->pc);
00362             updateTmp(c, &tmp1, q[0], q[1], tt);
00363 
00364             tt = clip_proc[clip_bit](&tmp2.pc, &q[0]->pc, &q[2]->pc);
00365             updateTmp(c, &tmp2, q[0], q[2], tt);
00366 
00367             tmp1.edge_flag = 1;
00368             tmp2.edge_flag = q[2]->edge_flag;
00369             gl_draw_triangle_clip(c, q[0], &tmp1, &tmp2, clip_bit + 1);
00370         }
00371     }
00372 }
00373 
00374 void gl_draw_triangle_select(GLContext *c, GLVertex *p0, GLVertex *p1, GLVertex *p2) {
00375     gl_add_select1(c, p0->zp.z, p1->zp.z, p2->zp.z);
00376 }
00377 
00378 #ifdef TINYGL_PROFILE
00379 int count_triangles, count_triangles_textured, count_pixels;
00380 #endif
00381 
00382 void gl_draw_triangle_fill(GLContext *c, GLVertex *p0, GLVertex *p1, GLVertex *p2) {
00383 #ifdef TINYGL_PROFILE
00384     {
00385         int norm;
00386         assert(p0->zp.x >= 0 && p0->zp.x < c->fb->xsize);
00387         assert(p0->zp.y >= 0 && p0->zp.y < c->fb->ysize);
00388         assert(p1->zp.x >= 0 && p1->zp.x < c->fb->xsize);
00389         assert(p1->zp.y >= 0 && p1->zp.y < c->fb->ysize);
00390         assert(p2->zp.x >= 0 && p2->zp.x < c->fb->xsize);
00391         assert(p2->zp.y >= 0 && p2->zp.y < c->fb->ysize);
00392 
00393         norm = (p1->zp.x - p0->zp.x) * (p2->zp.y - p0->zp.y) -
00394                 (p2->zp.x - p0->zp.x) * (p1->zp.y - p0->zp.y);
00395         count_pixels += abs(norm) / 2;
00396         count_triangles++;
00397     }
00398 #endif
00399 
00400     if (c->color_mask == 0) {
00401         // FIXME: Accept more than just 0 or 1.
00402         c->fb->fillTriangleDepthOnly(&p0->zp, &p1->zp, &p2->zp);
00403     }
00404     if (c->shadow_mode & 1) {
00405         assert(c->fb->shadow_mask_buf);
00406         c->fb->fillTriangleFlatShadowMask(&p0->zp, &p1->zp, &p2->zp);
00407     } else if (c->shadow_mode & 2) {
00408         assert(c->fb->shadow_mask_buf);
00409         c->fb->fillTriangleFlatShadow(&p0->zp, &p1->zp, &p2->zp);
00410     } else if (c->texture_2d_enabled) {
00411 #ifdef TINYGL_PROFILE
00412         count_triangles_textured++;
00413 #endif
00414         c->fb->setTexture(c->current_texture->images[0].pixmap);
00415         if (c->current_shade_model == TGL_SMOOTH) {
00416             c->fb->fillTriangleTextureMappingPerspectiveSmooth(&p0->zp, &p1->zp, &p2->zp);
00417         } else {
00418             c->fb->fillTriangleTextureMappingPerspectiveFlat(&p0->zp, &p1->zp, &p2->zp);
00419         }
00420     } else if (c->current_shade_model == TGL_SMOOTH) {
00421         c->fb->fillTriangleSmooth(&p0->zp, &p1->zp, &p2->zp);
00422     } else {
00423         c->fb->fillTriangleFlat(&p0->zp, &p1->zp, &p2->zp);
00424     }
00425 }
00426 
00427 // Render a clipped triangle in line mode
00428 
00429 void gl_draw_triangle_line(GLContext *c, GLVertex *p0, GLVertex *p1, GLVertex *p2) {
00430     if (c->depth_test) {
00431         if (p0->edge_flag)
00432             c->fb->fillLineZ(&p0->zp, &p1->zp);
00433         if (p1->edge_flag)
00434             c->fb->fillLineZ(&p1->zp, &p2->zp);
00435         if (p2->edge_flag)
00436             c->fb->fillLineZ(&p2->zp, &p0->zp);
00437     } else {
00438         if (p0->edge_flag)
00439             c->fb->fillLine(&p0->zp, &p1->zp);
00440         if (p1->edge_flag)
00441             c->fb->fillLine(&p1->zp, &p2->zp);
00442         if (p2->edge_flag)
00443             c->fb->fillLine(&p2->zp, &p0->zp);
00444     }
00445 }
00446 
00447 // Render a clipped triangle in point mode
00448 void gl_draw_triangle_point(GLContext *c, GLVertex *p0, GLVertex *p1, GLVertex *p2) {
00449     if (p0->edge_flag)
00450         c->fb->plot(&p0->zp);
00451     if (p1->edge_flag)
00452         c->fb->plot(&p1->zp);
00453     if (p2->edge_flag)
00454         c->fb->plot(&p2->zp);
00455 }
00456 
00457 } // end of namespace TinyGL


Generated on Sat Mar 16 2019 05:01:21 for ResidualVM by doxygen 1.7.1
curved edge   curved edge