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