Annotation of OpenXM_contrib/gnuplot/hidden3d.c, Revision 1.1.1.3
1.1 maekawa 1: #ifndef lint
1.1.1.3 ! ohara 2: static char *RCSid = "$Id: hidden3d.c,v 1.13.2.6 2002/03/11 12:27:57 broeker Exp $";
1.1 maekawa 3: #endif
4:
5: /* GNUPLOT - hidden3d.c */
6:
7: /*[
8: * Copyright 1986 - 1993, 1998 Thomas Williams, Colin Kelley
9: *
10: * Permission to use, copy, and distribute this software and its
11: * documentation for any purpose with or without fee is hereby granted,
12: * provided that the above copyright notice appear in all copies and
13: * that both that copyright notice and this permission notice appear
14: * in supporting documentation.
15: *
16: * Permission to modify the software is granted, but not the right to
17: * distribute the complete modified source code. Modifications are to
18: * be distributed as patches to the released version. Permission to
19: * distribute binaries produced by compiling modified sources is granted,
20: * provided you
21: * 1. distribute the corresponding source modifications from the
22: * released version in the form of a patch file along with the binaries,
23: * 2. add special version identification to distinguish your version
24: * in addition to the base release version number,
25: * 3. provide your name and address as the primary contact for the
26: * support of your modified version, and
27: * 4. retain our contact information in regard to use of the base
28: * software.
29: * Permission to distribute the released version of the source code along
30: * with corresponding source modifications in the form of a patch file is
31: * granted with same provisions 2 through 4 for binary distributions.
32: *
33: * This software is provided "as is" without express or implied warranty
34: * to the extent permitted by applicable law.
35: ]*/
36:
37:
38: /*
39: * 19 September 1992 Lawrence Crowl (crowl@cs.orst.edu)
40: * Added user-specified bases for log scaling.
41: *
42: * 'someone' contributed a complete rewrite of the hidden line
43: * stuff, for about beta 173 or so, called 'newhide.tgz'
44: *
45: * 1995-1997 Hans-Bernhard Br"oker (Broeker@physik.rwth-aachen.de)
46: * Speedup, cleanup and several modification to integrate
47: * 'newhide' with 3.6 betas ~188 (start of work) up to 273.
48: * As of beta 290, this is 'officially' in gnuplot.
49: *
50: */
51:
52: #include "plot.h"
53: #include "setshow.h"
54:
55: /* TODO (HBB's notes, just in case you're interested):
56: * + fix all the problems I annotated by a 'FIXME' comment
57: * + Find out which value EPSILON should have, and why
58: * + Ask gnuplot-beta for a suitable way of concentrating
59: * all those 'VERYSMALL', 'EPSILON', and other numbers
60: * into one, consistent scheme, possibly based on
61: * <float.h>. E.g., I'd say that for most applications,
62: * the best 'epsilon' is either DBL_EPS or its square root.
63: * + redo all the profiling, esp. to find out if TEST_GRIDCHECK = 1
64: * actually gains some speed, and if it is worth the memory
65: * spent to store the bit masks
66: * -> seems not improve speed at all, at least for my standard
67: * test case (mandd.gpl) it even slows it down by ~ 10%
68: * + Evaluate the speed/memory comparison for storing vertex
69: * indices instead of (double) floating point constants
70: * to store {x|y}{min|max}
71: * + remove those of my comments that are now pointless
72: * + indent all that code
73: * + try to really understand that 'hl_buffer' stuff...
74: * + get rid of hardcoded things like sizeof(short) == 4,
75: * those 0x7fff terms and all that.
76: * + restructure the hl_buffer storing method to make it more efficient
77: * + Try to cut the speed decrease of this code rel. to the old hidden
78: * hidden line removal. (For 'mandd.gpl', it costs an overall
79: * factor of 9 compared with my older versions of gnuplot!)
80: */
81:
82: /*************************/
83: /* Configuration section */
84: /*************************/
85:
86: /* HBB: if this module is compiled with TEST_GRIDCHECK = 1 defined,
87: * it will store the information about {x|y}{min|max} in an
88: * other (additional!) form: a bit mask, with each bit representing
89: * one horizontal or vertical strip of the screen. The bits
90: * for strips a polygon spans are set to one. This allows to
91: * test for xy_overlap simply by comparing bit patterns.
92: */
93: #ifndef TEST_GRIDCHECK
94: #define TEST_GRIDCHECK 0
95: #endif
96:
97: /* HBB 961124; If you don't want the color-distinction between the
98: * 'top' and 'bottom' sides of the surface, like I do, then just compile
99: * with -DBACKSIDE_LINETYPE_OFFSET = 0. */
100: #ifndef BACKSIDE_LINETYPE_OFFSET
101: #define BACKSIDE_LINETYPE_OFFSET 1
102: #endif
103:
104: /* HBB 961127: defining FOUR_TRIANGLES = 1 will separate each quadrangle
105: * of data points into *four* triangles, by introducing an additional
106: * point at the mean of the four corners. Status: experimental
107: */
108: #ifndef FOUR_TRIANGLES
109: #define FOUR_TRIANGLES 0
110: #endif
111:
112: /* HBB 970322: I removed the SENTINEL flag and its implementation
113: * completely. Its speed improvement wasn't that great, and it never
114: * fully worked anyway, so that shouldn't make much of a difference at
115: * all. */
116:
117: /* HBB 961212: this #define lets you choose if the diagonals that
118: * divide each original quadrangle in two triangles will be drawn
119: * visible or not: do draw them, define it to be 7L, otherwise let be
120: * 3L (for the FOUR_TRIANGLES method, the values are 7L and 1L) */
121: /* drd : default to 3, for back-compatibility with 3.5 */
122: #ifndef TRIANGLE_LINESDRAWN_PATTERN
123: #define TRIANGLE_LINESDRAWN_PATTERN 3L
124: #endif
125:
126: /* HBB 970131: with HANDLE_UNDEFINED_POINTS = 1, let's try to handle
127: * UNDEFINED data points in the input we're given by the rest of
128: * gnuplot. We do that by marking these points by giving them z = -2
129: * (which normally never happens), and then refusing to build any
130: * polygon if one of its vertices has this mark. Thus, there's now a
131: * hole in the generated surface. */
132: /* HBB 970322: some of this code is now hardwired (in
133: * PREPARE_POLYGON), so HANDLE_UNDEFINED_POINTS = 0 might have stopped
134: * to be a useful setting. I doubt anyone will miss it, anyway. */
135: /* drd : 2 means undefined only. 1 means outrange treated as undefined */
136: #ifndef HANDLE_UNDEFINED_POINTS
137: #define HANDLE_UNDEFINED_POINTS 1
138: #endif
139: /* Symbolic value for 'do not handle Undefined Points specially' */
140: #define UNHANDLED (UNDEFINED+1)
141:
142: /* HBB 970322: If both subtriangles of a quad were cancelled, try if
143: * using the other diagonal is better. This only makes a difference if
144: * exactly one vertex of the quad is unusable, and that one is on the
145: * first tried diagonal. In such a case, the border of the hole in the
146: * surface will be less rough than with the previous method. To
147: * disable this, #define SHOW_ALTERNATIVE_DIAGONAL as 0 */
148: #ifndef SHOW_ALTERNATIVE_DIAGONAL
149: #define SHOW_ALTERNATIVE_DIAGONAL 1
150: #endif
151:
152: /* HBB 9790522: If the two triangles in a quad are both drawn, and
153: * they show different sides to the user (the quad is 'bent over'),
154: * then it often looks more sensible to draw the diagonal visibly to
155: * avoid other parts of the scene being obscured by what the user
156: * can't see. To disable, #define HANDLE_BENTOVER_QUADRANGLES 0 */
157: #ifndef HANDLE_BENTOVER_QUADRANGLES
158: #define HANDLE_BENTOVER_QUADRANGLES 1
159: #endif
160:
161: /* HBB 970618: The code of split_polygon_by_plane used to make a
162: * separate decision about what should happen to points that are 'in'
163: * the splitting plane (within EPSILON accuracy, i.e.), based on the
164: * orientation of the splitting plane. I had disabled that code for I
165: * assumed it might be the cause of some of the buggyness. I'm not yet
166: * fully convinced on wether that assumption holds or not, so it's now
167: * choosable. OLD_SPLIT_PLANE == 1 will enable it. Some older comments
168: * from the source:*/
169: /* HBB 970325: re-inserted this from older versions. Finally, someone
170: * came up with a test case where it is actually needed :-( */
171: /* HBB 970427: seems to have been an incorrect analysis of that error.
172: * the problematic plot works without this as well. */
173: #ifndef OLD_SPLIT_INPLANE
174: #define OLD_SPLIT_INPLANE 1
175: #endif
176:
177: /* HBB 970618: this way, new edges introduced by splitting a polygon
178: * by the plane of another one will be made visible. Not too useful on
179: * production output, but can help in debugging. */
180: #ifndef SHOW_SPLITTING_EDGES
181: #define SHOW_SPLITTING_EDGES 0
182: #endif
183:
184: /********************************/
185: /* END of configuration section */
186: /********************************/
187:
188:
189:
190: /* Variables to hold configurable values. This is meant to prepare for
191: * making these settable by the user via 'set hidden [option]...' */
192:
193: int hiddenBacksideLinetypeOffset = BACKSIDE_LINETYPE_OFFSET;
194: long hiddenTriangleLinesdrawnPattern = TRIANGLE_LINESDRAWN_PATTERN;
195: int hiddenHandleUndefinedPoints = HANDLE_UNDEFINED_POINTS;
196: int hiddenShowAlternativeDiagonal = SHOW_ALTERNATIVE_DIAGONAL;
197: int hiddenHandleBentoverQuadrangles = HANDLE_BENTOVER_QUADRANGLES;
198:
199: /* The functions to map from user 3D space into normalized -1..1 */
200: #define map_x3d(x) ((x-min_array[FIRST_X_AXIS])*xscale3d-1.0)
201: #define map_y3d(y) ((y-min_array[FIRST_Y_AXIS])*yscale3d-1.0)
1.1.1.2 maekawa 202: #define map_z3d(z) ((z-floor_z)*zscale3d-1.0)
1.1 maekawa 203:
204: extern int suppressMove;
205: extern int xright, xleft, ybot, ytop;
206: extern int xmiddle, ymiddle, xscaler, yscaler;
207: extern double min_array[], max_array[];
208: extern int auto_array[], log_array[];
209: extern double base_array[], log_base_array[];
210: extern double xscale3d, yscale3d, zscale3d;
1.1.1.2 maekawa 211: extern double floor_z;
1.1 maekawa 212:
213: extern int hidden_no_update, hidden_active;
214: extern int hidden_line_type_above, hidden_line_type_below;
215:
216: extern double trans_mat[4][4];
217:
218:
219: #ifdef HAVE_STRINGIZE
220: /* ANSI preprocessor concatenation */
221: # define CONCAT(x,y) x##y
222: # define CONCAT3(x,y,z) x##y##z
223: #else
224: /* K&R preprocessor concatenation */
225: # define CONCAT(x,y) x/**/y
226: # define CONCAT3(x,y,z) x/**/y/**/z
227: #endif
228:
229: /* Bitmap of the screen. The array for each x value is malloc-ed as needed */
230: /* HBB 961111: started parametrisation of type t_pnt, to prepare change from
231: * short to normal ints in **pnt. The other changes aren't always annotated,
232: * so watch out! */
233: typedef unsigned short int t_pnt;
234: #define PNT_BITS (CHAR_BIT*sizeof(t_pnt))
235: /* caution! ANSI-dependant ! ? */
236: #define PNT_MAX USHRT_MAX
237: typedef t_pnt *tp_pnt;
238: static tp_pnt *pnt;
239:
240: /* Testroutine for the bitmap */
241: /* HBB 961110: fixed slight problem indicated by lclint:
242: * calling IS_UNSET with pnt == 0 (possible?) */
243: /* HBB 961111: changed for new t_pnt, let compiler take care of optimisation
244: * `%' -> `&' */
245: /* HBB 961124: switched semantics: as this was *always* called as !IS_SET(),
246: * it's better to check for *unset* bits right away: */
247: #define IS_UNSET(X,Y) ((!pnt || pnt[X] == 0) ? 1 : !(((pnt[X])[(Y)/PNT_BITS] >> ((Y)%PNT_BITS)) & 0x01))
248:
249: /* Amount of space we need for one vertical row of bitmap,
250: and byte offset of first used element */
251: static unsigned long y_malloc;
252:
253: /* These numbers are chosen as dividers into the bitmap. */
254: static int xfact, yfact;
255: #define XREDUCE(X) ((X)/xfact)
256: #define YREDUCE(Y) ((Y)/yfact)
257:
258: /* These variables are only used for drawing the individual polygons
259: that make up the 3d figure. After each polygon is drawn, the
260: information is copied to the bitmap: xmin_hl, ymin_hl are used to
261: keep track of the range of x values. The arrays ymin_hl[],
262: ymax_hl[] are used to keep track of the minimum and maximum y
263: values used for each X value. */
264:
265: /* HBB 961124: new macro, to avoid a wordsize-depence */
266: #define HL_EXTENT_X_MAX UINT_MAX /* caution! ANSI-only !? */
267: static unsigned int xmin_hl, xmax_hl;
268:
269: /* HBB: parametrized type of hl_buffer elements, to allow easier
270: changing later on: */
271: #define HL_EXTENT_Y_MAX SHRT_MAX /* caution! ANSI-only !? */
272: typedef short int t_hl_extent_y;
273: static t_hl_extent_y *ymin_hl, *ymax_hl;
274:
275:
276: /* hl_buffer is a buffer which is needed to draw polygons with very small
277: angles correct:
278:
279: One polygon may be split during the sorting algorithmus into
280: several polygons. Before drawing a part of a polygon, I save in
281: this buffer all lines of the polygon, which will not yet be drawn.
282: If then the actual part draws a virtual line (a invisible line,
283: which splits the polygon into 2 parts), it draws the line visible
284: in those points, which are set in the buffer.
285:
286: The layout of the buffer:
287: hl_buffer[i] stands for the i'th column of the bitmap.
288: Each column is splitted into pairs of points (a,b).
289: Each pair describes a cross of one line with the column. */
290:
1.1.1.3 ! ohara 291: /* HBB 20000608: finally, someone found a serious bug in this code :-(
! 292: * whenever the Cross_store array has to be reallocated, all the
! 293: * pointers in hl_buffer, and the next pointers in struct Cross become
! 294: * invalid. Use indices instead of pointers. */
! 295:
1.1 maekawa 296: struct Cross {
297: int a, b;
1.1.1.3 ! ohara 298: unsigned int next; /* (unsigned int) -1 means: no next */
! 299: /* HBB 20000608: was struct Cross GPHUGE *next;*/
1.1 maekawa 300: };
301:
1.1.1.3 ! ohara 302: #if 0 /* HBB 20000608 */
1.1 maekawa 303: static struct Cross GPHUGE *GPHUGE * hl_buffer;
1.1.1.3 ! ohara 304: #else
! 305: static unsigned int GPHUGE * hl_buffer;
! 306: #endif
1.1 maekawa 307:
308: /* HBB 980303: added a global array of Cross structures, to save lots
309: * of gp_alloc() calls (3 millions in a run through all.dem!) */
310:
311: #define CROSS_STORE_INCREASE 500 /* number of Cross'es to alloc at a time */
312: static struct Cross *Cross_store = 0;
1.1.1.3 ! ohara 313: static unsigned int last_Cross_store = 0, free_Cross_store = 0;
1.1 maekawa 314:
315: struct Vertex {
316: coordval x, y, z;
317: int style;
318: };
319:
320: /* HBB 971114: two new macros, to properly hide the machinery that
321: *implements flagging of vertices as 'undefined' (or 'out of range',
322: *handled equally). Thanks to Lars Hecking for pointing this out */
323: #define FLAG_VERTEX_AS_UNDEFINED(v) \
324: do { (v).z = -2.0; } while (0)
325: #define VERTEX_IS_UNDEFINED(v) ((v).z == -2.0)
326:
327: /* These values serve as flags to detect loops of polygons obscuring
328: * each other in in_front() */
329: typedef enum {
330: is_untested = 0, is_tested, is_in_loop, is_moved_or_split
331: } t_poly_tested;
332:
333: /* Strings for printing out values of type t_poly_tested: */
334: static const char *string_poly_tested[] =
335: {
336: "is_untested",
337: "is_tested",
338: "is_in_loop",
339: "is_moved_or_split"
340: };
341:
342: struct Polygon {
343: int n; /* amount of vertices */
344: long *vertex; /* The vertices (indices on vlist) */
345: long line; /* i'th bit shows, if the i'th line should be drawn */
346: coordval xmin, xmax, ymin, ymax, zmin, zmax;
347: /* min/max in all three directions */
348: struct lp_style_type *lp; /* pointer to l/p properties */
349: int style; /* The style of the lines */
350: long next; /* index of next polygon in z-sorted list */
351: long next_frag; /* next fragment of same polygon... */
352: int id; /* Which polygons belong together? */
353: t_poly_tested tested; /* To determine a loop during the sorting algorithm */
354: /* HBB 980317: on the 16 bit PC platforms, the struct size must
355: * be a power of two, so it exactly fits into a 64KB segment. First
356: * we'll add the TEST_GRIDCHECK fields, regardless wether that
357: * feature was activated or not. */
358: #if TEST_GRIDCHECK || defined(DOS16) || defined(WIN16)
359: unsigned int xextent, yextent;
360: #endif
361: /* HBB 980317: the remaining bit of padding. */
362: #if defined(DOS16) || defined(WIN16) || defined(WIN32)
363: char dummies[8];
364: #endif
365: };
366:
367: typedef enum { /* result type for polygon_plane_intersection() */
368: infront, inside, behind, intersects
369: } t_poly_plane_intersect;
370:
371: static struct Vertex GPHUGE *vlist; /* The vertices */
372: static struct Polygon GPHUGE *plist; /* The polygons */
373: static long nvert, npoly; /* amount of vertices and polygons */
374: static long pfree, vert_free; /* index on the first free entries */
375:
376: static long pfirst; /* Index on the first polygon */
377:
378: /* macros for (somewhat) safer handling of the dynamic array of
379: * polygons, 'plist[]' */
380: #define EXTEND_PLIST() \
381: plist = (struct Polygon GPHUGE *) gp_realloc(plist, \
382: (unsigned long)sizeof(struct Polygon)*(npoly += 10L), "hidden plist")
383:
384: #define CHECK_PLIST() if (pfree >= npoly) EXTEND_PLIST()
385: #define CHECK_PLIST_2() if (pfree+1 >= npoly) EXTEND_PLIST()
386: #define CHECK_PLIST_EXTRA(extra) if (pfree >= npoly) { EXTEND_PLIST() ; extra; }
387:
388:
389: /* precision of calculations in normalized space: */
390: #define EPSILON 1e-5 /* HBB: was 1.0E-5 */
391: #define SIGNOF(X) ( ((X)<-EPSILON) ? -1: ((X)>EPSILON) )
392:
393: /* Some inexact relations: == , > , >= */
394: #define EQ(X,Y) (fabs( (X) - (Y) ) < EPSILON) /* X == Y */
395: #define GR(X,Y) ((X) > (Y) + EPSILON) /* X > Y */
396: #define GE(X,Y) ((X) >= (Y) - EPSILON) /* X >= Y */
397:
398: /* Test, if two vertices are near each other */
399: #define V_EQUAL(a,b) ( GE(0.0, fabs((a)->x - (b)->x) + \
400: fabs((a)->y - (b)->y) + fabs((a)->z - (b)->z)) )
401:
402: #define SETBIT(a,i,set) a= (set) ? (a) | (1L<<(i)) : (a) & ~(1L<<(i))
403: #define GETBIT(a,i) (((a)>>(i))&1L)
404:
405: #define UINT_BITS (CHAR_BIT*sizeof(unsigned int))
406: #define USHRT_BITS (CHAR_BIT*sizeof(unsigned short))
407:
408:
409: static void print_polygon __PROTO((struct Polygon GPHUGE * p, const char *pname));
410:
411: /* HBB: new routine, to help debug 'Logic errors', mainly */
412: static void print_polygon(p, pname)
413: struct Polygon GPHUGE *p;
414: const char *pname;
415: {
416: struct Vertex GPHUGE *v;
417: int i;
418:
419: fprintf(stderr, "#%s:(ind %d) n:%d, id:%d, next:%ld, tested:%s\n",
420: pname, (int) (p - plist), p->n, p->id, p->next,
421: string_poly_tested[(int) (p->tested)]);
422: fprintf(stderr, "#zmin:%g, zmax:%g\n", p->zmin, p->zmax);
423: for (i = 0; i < p->n; i++, v++) {
424: v = vlist + p->vertex[i];
425: fprintf(stderr, "%g %g %g \t%ld\n", v->x, v->y, v->z, p->vertex[i]);
426: }
427: /*repeat first vertex, so the line gets closed: */
428: v = vlist + p->vertex[0];
429: fprintf(stderr, "%g %g %g \t%ld\n", v->x, v->y, v->z, p->vertex[0]);
430: /*two blank lines, as a multimesh separator: */
431: fputs("\n\n", stderr);
432: }
433:
434: /* Gets Minimum 'C' value of polygon, C is x, y, or z: */
435: #define GET_MIN(p, C, min) do { \
436: int i; \
437: long *v = p->vertex; \
438: \
439: min = vlist[*v++].C; \
440: for (i = 1; i< p->n; i++, v++) \
441: if (vlist[*v].C < min) \
442: min = vlist[*v].C; \
443: } while (0)
444:
445: /* Gets Maximum 'C' value of polygon, C is x, y, or z: */
446: #define GET_MAX(p, C, max) do { \
447: int i; \
448: long *v = p->vertex; \
449: \
450: max = vlist[*v++].C; \
451: for (i = 1; i< p->n; i++, v++) \
452: if (vlist[*v].C > max) \
453: max = vlist[*v].C; \
454: } while (0)
455:
456: /* Prototypes for internal functions of this module. */
457: static void map3d_xyz __PROTO((double x, double y, double z,
458: struct Vertex GPHUGE * v));
459: static int reduce_polygon __PROTO((int *n, long **v, long *line, int nmin));
460: static void build_polygon __PROTO((struct Polygon GPHUGE * p, int n,
461: long *v, long line, int style, struct lp_style_type * lp,
462: long next, long next_frag, int id, t_poly_tested tested));
463: static GP_INLINE int maybe_build_polygon __PROTO((struct Polygon GPHUGE * p,
464: int n, long *v, long line, int style, struct lp_style_type * lp,
465: long next, long next_frag, int id, t_poly_tested tested));
466: static void init_polygons __PROTO((struct surface_points * plots, int pcount));
1.1.1.3 ! ohara 467: int compare_by_zmax __PROTO((SORTFUNC_ARGS p1, SORTFUNC_ARGS p2));
1.1 maekawa 468: static void sort_by_zmax __PROTO((void));
469: static int obscured __PROTO((struct Polygon GPHUGE * p));
470: static GP_INLINE int xy_overlap __PROTO((struct Polygon GPHUGE * a, struct Polygon GPHUGE * b));
471: static void get_plane __PROTO((struct Polygon GPHUGE * p, double *a, double *b,
472: double *c, double *d));
473: static t_poly_plane_intersect polygon_plane_intersection __PROTO((struct Polygon GPHUGE * p, double a, double b, double c, double d));
474: static int intersect __PROTO((struct Vertex GPHUGE * v1,
475: struct Vertex GPHUGE * v2, struct Vertex GPHUGE * v3, struct Vertex GPHUGE * v4));
476: static int v_intersect __PROTO((struct Vertex GPHUGE * v1,
477: struct Vertex GPHUGE * v2, struct Vertex GPHUGE * v3, struct Vertex GPHUGE * v4));
478: static int intersect_polygon __PROTO((struct Vertex GPHUGE * v1, struct Vertex GPHUGE * v2, struct Polygon GPHUGE * p));
479: static int full_xy_overlap __PROTO((struct Polygon GPHUGE * a, struct Polygon GPHUGE * b));
480: static long build_new_vertex __PROTO((long V1, long V2, double w));
481: static long split_polygon_by_plane __PROTO((long P, double a, double b,
482: double c, double d, TBOOLEAN f));
483: static int in_front __PROTO((long Last, long Test));
484:
485: /* HBB 980303: new, for the new back-buffer for *Cross structures: */
1.1.1.3 ! ohara 486: static GP_INLINE unsigned int get_Cross_from_store __PROTO((void));
1.1 maekawa 487: static GP_INLINE void init_Cross_store __PROTO((void));
488:
489: static GP_INLINE TBOOLEAN hl_buffer_set __PROTO((int xv, int yv));
490: static GP_INLINE void update_hl_buffer_column __PROTO((int xv, int ya, int yv));
491: static void draw_clip_line_buffer __PROTO((int x1, int y1, int x2, int y2));
492: static void draw_clip_line_update __PROTO((int x1, int y1, int x2, int y2,
493: int virtual));
494: static GP_INLINE void clip_vector_h __PROTO((int x, int y));
495: static GP_INLINE void clip_vector_virtual __PROTO((int x, int y));
496: static GP_INLINE void clip_vector_buffer __PROTO((int x, int y));
497: static void draw __PROTO((struct Polygon GPHUGE * p));
498:
499:
500: /* Set the options for hidden3d. To be called from set.c, when the
501: * user has begun a command with 'set hidden3d', to parse the rest of
502: * that command */
503: void set_hidden3doptions()
504: {
505: struct value t;
506:
507: c_token++;
508:
509: if (END_OF_COMMAND) {
510: return;
511: }
512: if (almost_equals(c_token, "def$aults")) {
513: /* reset all parameters to defaults */
514: hiddenBacksideLinetypeOffset = BACKSIDE_LINETYPE_OFFSET;
515: hiddenTriangleLinesdrawnPattern = TRIANGLE_LINESDRAWN_PATTERN;
516: hiddenHandleUndefinedPoints = HANDLE_UNDEFINED_POINTS;
517: hiddenShowAlternativeDiagonal = SHOW_ALTERNATIVE_DIAGONAL;
518: hiddenHandleBentoverQuadrangles = HANDLE_BENTOVER_QUADRANGLES;
519: c_token++;
520: if (!END_OF_COMMAND)
521: int_error("No further options allowed after 'defaults'", c_token);
522: return;
523: }
524: if (almost_equals(c_token, "off$set")) {
525: c_token++;
526: hiddenBacksideLinetypeOffset = (int) real(const_express(&t));
527: } else if (almost_equals(c_token, "nooff$set")) {
528: c_token++;
529: hiddenBacksideLinetypeOffset = 0;
530: }
531: if (END_OF_COMMAND) {
532: return;
533: }
534: if (almost_equals(c_token, "tri$anglepattern")) {
535: c_token++;
536: hiddenTriangleLinesdrawnPattern = (int) real(const_express(&t));
537: }
538: if (END_OF_COMMAND) {
539: return;
540: }
541: if (almost_equals(c_token, "undef$ined")) {
542: int tmp;
543:
544: c_token++;
545: tmp = (int) real(const_express(&t));
546: if (tmp <= 0 || tmp > UNHANDLED)
547: tmp = UNHANDLED;
548: hiddenHandleUndefinedPoints = tmp;
549: } else if (almost_equals(c_token, "nound$efined")) {
550: c_token++;
551: hiddenHandleUndefinedPoints = UNHANDLED;
552: }
553: if (END_OF_COMMAND) {
554: return;
555: }
556: if (almost_equals(c_token, "alt$diagonal")) {
557: c_token++;
558: hiddenShowAlternativeDiagonal = 1;
559: } else if (almost_equals(c_token, "noalt$diagonal")) {
560: c_token++;
561: hiddenShowAlternativeDiagonal = 0;
562: }
563: if (END_OF_COMMAND) {
564: return;
565: }
566: if (almost_equals(c_token, "bent$over")) {
567: c_token++;
568: hiddenHandleBentoverQuadrangles = 1;
569: } else if (almost_equals(c_token, "nobent$over")) {
570: c_token++;
571: hiddenHandleBentoverQuadrangles = 0;
572: }
573: if (!END_OF_COMMAND) {
574: int_error("No such option to hidden3d (or wrong order)", c_token);
575: }
576: }
577:
578: /* HBB 970619: new routine for displaying the option settings */
579: void show_hidden3doptions()
580: {
581: fprintf(stderr,"\
582: \t Back side of surfaces has linestyle offset of %d\n\
583: \t Bit-Mask of Lines to draw in each triangle is %ld\n\
584: \t %d: ",
585: hiddenBacksideLinetypeOffset, hiddenTriangleLinesdrawnPattern,
586: hiddenHandleUndefinedPoints);
587:
588: switch (hiddenHandleUndefinedPoints) {
589: case OUTRANGE:
590: fputs("Outranged and undefined datapoints are omitted from the surface.\n", stderr);
591: break;
592: case UNDEFINED:
593: fputs("Only undefined datapoints are omitted from the surface.\n", stderr);
594: break;
595: case UNHANDLED:
596: fputs("Will not check for undefined datapoints (may cause crashes).\n", stderr);
597: break;
598: default:
599: fputs("This value is illegal!!!\n", stderr);
600: break;
601: }
602: fprintf(stderr,"\
603: \t Will %suse other diagonal if it gives a less jaggy outline\n\
604: \t Will %sdraw diagonal visibly if quadrangle is 'bent over'\n",
605: hiddenShowAlternativeDiagonal ? "" : "not ",
606: hiddenHandleBentoverQuadrangles ? "" : "not ");
607: }
608:
609: /* HBB 971117: new function. */
610: /* Implements proper 'save'ing of the new hidden3d options... */
611: void save_hidden3doptions(fp)
612: FILE *fp;
613: {
614: if (!hidden3d) {
615: fputs("set nohidden3d\n", fp);
616: return;
617: }
618: fprintf(fp, "set hidden3d offset %d trianglepattern %ld undefined %d %saltdiagonal %sbentover\n",
619: hiddenBacksideLinetypeOffset,
620: hiddenTriangleLinesdrawnPattern,
621: hiddenHandleUndefinedPoints,
622: hiddenShowAlternativeDiagonal ? "" : "no",
623: hiddenHandleBentoverQuadrangles ? "" : "no");
624: }
625:
626: /* Initialize the necessary steps for hidden line removal and
627: initialize global variables. */
628: void init_hidden_line_removal()
629: {
630: int i;
631:
632: /* Check for some necessary conditions to be set elsewhere: */
633: /* HandleUndefinedPoints mechanism depends on these: */
634: assert(OUTRANGE == 1);
635: assert(UNDEFINED == 2);
636: /* '3' makes the test easier in the critical section */
637: if (hiddenHandleUndefinedPoints < OUTRANGE)
638: hiddenHandleUndefinedPoints = UNHANDLED;
639:
640: /* We want to keep the bitmap size less than 2048x2048, so we choose
641: * integer dividers for the x and y coordinates to keep the x and y
642: * ranges less than 2048. In practice, the x and y sizes for the bitmap
643: * will be somewhere between 1024 and 2048, except in cases where the
644: * coordinates ranges for the device are already less than 1024.
645: * We do this mainly to control the size of the bitmap, but it also
646: * speeds up the computation. We maintain separate dividers for
647: * x and y.
648: */
649: xfact = (xright - xleft) / 1024;
650: yfact = (ytop - ybot) / 1024;
651: if (xfact == 0)
652: xfact = 1;
653: if (yfact == 0)
654: yfact = 1;
655: if (pnt == 0) {
656: i = XREDUCE(xright) - XREDUCE(xleft) + 1;
1.1.1.3 ! ohara 657: pnt = (tp_pnt *) gp_alloc(i * sizeof(tp_pnt), "hidden pnt");
1.1 maekawa 658: while (--i >= 0)
659: pnt[i] = (tp_pnt) 0;
660: }
661: }
662:
663: /* Reset the hidden line data to a fresh start. */
664: void reset_hidden_line_removal()
665: {
666: int i;
667: if (pnt) {
668: for (i = 0; i <= XREDUCE(xright) - XREDUCE(xleft); i++) {
669: if (pnt[i]) {
670: free(pnt[i]);
671: pnt[i] = 0;
672: };
673: };
674: };
675: }
676:
677:
678: /* Terminates the hidden line removal process. */
679: /* Free any memory allocated by init_hidden_line_removal above. */
680: void term_hidden_line_removal()
681: {
682: if (pnt) {
683: int j;
684: for (j = 0; j <= XREDUCE(xright) - XREDUCE(xleft); j++) {
685: if (pnt[j]) {
686: free(pnt[j]);
687: pnt[j] = 0;
688: };
689: };
690: free(pnt);
691: pnt = 0;
692: };
693: if (ymin_hl)
694: free(ymin_hl), ymin_hl = 0;
695: if (ymax_hl)
696: free(ymax_hl), ymax_hl = 0;
697: }
698:
699:
700: /* Maps from normalized space to terminal coordinates */
701: #define TERMCOORD(v,x,y) x = ((int)((v)->x * xscaler)) + xmiddle, \
702: y = ((int)((v)->y * yscaler)) + ymiddle;
703:
704:
705: static void map3d_xyz(x, y, z, v)
706: double x, y, z; /* user coordinates */
707: struct Vertex GPHUGE *v; /* the point in normalized space */
708: {
709: int i, j;
710: double V[4], Res[4], /* Homogeneous coords. vectors. */
711: w = trans_mat[3][3];
712: /* Normalize object space to -1..1 */
713: V[0] = map_x3d(x);
714: V[1] = map_y3d(y);
715: V[2] = map_z3d(z);
716: V[3] = 1.0;
717: Res[0] = 0; /*HBB 961110: lclint wanted this... Why? */
718: for (i = 0; i < 3; i++) {
719: Res[i] = trans_mat[3][i]; /* Initiate it with the weight factor. */
720: for (j = 0; j < 3; j++)
721: Res[i] += V[j] * trans_mat[j][i];
722: }
723: for (i = 0; i < 3; i++)
724: w += V[i] * trans_mat[i][3];
725: if (w == 0)
726: w = 1.0e-5;
727: v->x = Res[0] / w;
728: v->y = Res[1] / w;
729: v->z = Res[2] / w;
730: }
731:
732:
733: /* remove unnecessary Vertices from a polygon: */
734: static int reduce_polygon(n, v, line, nmin)
735: int *n; /* number of vertices */
736: long **v; /* the vertices */
737: long *line; /* information which line should be drawn */
738: int nmin; /* if the number reduces under nmin, forget polygon */
739: /* Return value 1: the reduced polygon has still more or equal
740: vertices than nmin.
741: Return value 0: the polygon was trivial; memory is given free */
742: {
743: int less, i;
744: long *w = *v;
745: for (less = 0, i = 0; i < *n - 1; i++) {
746: if (V_EQUAL(vlist + w[i], vlist + w[i + 1])
747: /* HBB 970321: try to remove an endless loop bug (part1/2) */
748: && ((w[i] == w[i + 1])
749: || !GETBIT(*line, i)
750: || GETBIT(*line, i + 1)
751: || ((i > 0) ? GETBIT(*line, i - 1) : GETBIT(*line, *n - 1))))
752: less++;
753: else if (less) {
754: w[i - less] = w[i];
755: SETBIT(*line, i - less, GETBIT(*line, i));
756: }
757: }
758: if (i - less > 0
759: && V_EQUAL(vlist + w[i], vlist + w[0])
760: /* HBB 970321: try to remove an endless loop bug (part2/2) */
761: && (w[i] == w[0]
762: || !GETBIT(*line, i)
763: || GETBIT(*line, i - 1)
764: || GETBIT(*line, 0)))
765: less++;
766: else if (less) {
767: w[i - less] = w[i];
768: SETBIT(*line, i - less, GETBIT(*line, i));
769: }
770: *n -= less;
771: if (*n < nmin) {
772: free(w);
773: *v = 0; /* HBB 980213: signal that v(==w) is free()d */
774: return 0;
775: }
776: if (less) {
777: w = (long *) gp_realloc(w, (unsigned long) sizeof(long) * (*n),
778: "hidden red_poly");
779: *v = w;
780: for (; less > 0; less--)
781: SETBIT(*line, *n + less - 1, 0);
782: }
783: return 1;
784: }
785:
786: /* Write polygon in plist */
787: /*
788: * HBB: changed this to precalculate {x|y}{min|max}
789: */
790: static void build_polygon(p, n, v, line, style, lp, next, next_frag, id, tested)
791: struct Polygon GPHUGE *p; /* this should point at a free entry in plist */
792: int n; /* number of vertices */
793: long *v; /* array of indices on the vertices (in vlist) */
794: long line; /* information, which line should be drawn */
795: int style; /* color of the lines */
796: struct lp_style_type *lp; /* pointer to line/point properties */
797: long next; /* next polygon in the list */
798: long next_frag; /* next fragment of same polygon */
799: int id; /* Which polygons belong together? */
800: t_poly_tested tested; /* Is polygon already on the right place of list? */
801: {
802: int i;
803: struct Vertex vert;
804:
805: if (p >= plist + npoly)
806: fputs("uh oh !\n", stderr);
807:
808: CHECK_POINTER(plist, p);
809:
810: p->n = n;
811: p->vertex = v;
812: p->line = line;
813: p->lp = lp; /* line and point properties */
814: p->style = style;
815: CHECK_POINTER(vlist, (vlist + v[0]));
816: vert = vlist[v[0]];
817: p->xmin = p->xmax = vert.x;
818: p->ymin = p->ymax = vert.y;
819: p->zmin = p->zmax = vert.z;
820: for (i = 1; i < n; i++) {
821: CHECK_POINTER(vlist, (vlist + v[i]));
822: vert = vlist[v[i]];
823: if (vert.x < p->xmin)
824: p->xmin = vert.x;
825: else if (vert.x > p->xmax)
826: p->xmax = vert.x;
827: if (vert.y < p->ymin)
828: p->ymin = vert.y;
829: else if (vert.y > p->ymax)
830: p->ymax = vert.y;
831: if (vert.z < p->zmin)
832: p->zmin = vert.z;
833: else if (vert.z > p->zmax)
834: p->zmax = vert.z;
835: }
836:
837: #if TEST_GRIDCHECK
838: /* FIXME: this should probably use a table of bit-patterns instead... */
839: p->xextent = (~(~0U << (unsigned int) ((p->xmax + 1.0) / 2.0 * UINT_BITS + 1.0)))
840: & (~0U << (unsigned int) ((p->xmin + 1.0) / 2.0 * UINT_BITS));
841: p->yextent = (~(~0U << (unsigned int) ((p->ymax + 1.0) / 2.0 * UINT_BITS + 1.0)))
842: & (~0U << (unsigned int) ((p->ymin + 1.0) / 2.0 * UINT_BITS));
843: #endif
844:
845: p->next = next;
846: p->next_frag = next_frag; /* HBB 961201: link fragments, to speed up draw() q-loop */
847: p->id = id;
848: p->tested = tested;
849: }
850:
851:
852: /* get the amount of curves in a plot */
853: #define GETNCRV(NCRV) do {\
854: if(this_plot->plot_type == FUNC3D) \
855: for(icrvs = this_plot->iso_crvs,NCRV = 0; \
856: icrvs;icrvs = icrvs->next,NCRV++); \
857: else if(this_plot->plot_type == DATA3D) \
858: NCRV = this_plot->num_iso_read; \
859: else { \
860: graph_error("Plot type is neither function nor data"); \
861: return; /* stops a gcc -Wunitialised warning */ \
862: } \
863: } while (0)
864:
865: /* Do we see the top or bottom of the polygon, or is it 'on edge'? */
866: #define GET_SIDE(vlst,csign) do { \
867: double c = vlist[vlst[0]].x * (vlist[vlst[1]].y - vlist[vlst[2]].y) + \
868: vlist[vlst[1]].x * (vlist[vlst[2]].y - vlist[vlst[0]].y) + \
869: vlist[vlst[2]].x * (vlist[vlst[0]].y - vlist[vlst[1]].y); \
870: csign = SIGNOF (c); \
871: } while (0)
872:
873: /* HBB 970131: new function, to allow handling of undefined datapoints
874: * by leaving out the corresponding polygons from the list.
875: * Return Value: 1 if polygon was built, 0 otherwise */
876: static GP_INLINE int maybe_build_polygon(p, n, v, line, style, lp,
877: next, next_frag, id, tested)
878: struct Polygon GPHUGE *p;
879: struct lp_style_type *lp;
880: int n, style, id;
881: t_poly_tested tested;
882: long *v, line, next, next_frag;
883: {
884: int i;
885:
886: assert(v);
887:
888: if (hiddenHandleUndefinedPoints != UNHANDLED)
889: for (i = 0; i < n; i++)
890: if (VERTEX_IS_UNDEFINED(vlist[v[i]])) {
891: free(v); /* HBB 980213: free mem... */
892: v = 0;
893: return 0; /* *don't* build the polygon! */
894: }
895: build_polygon(p, n, v, line, style, lp, next, next_frag, id, tested);
896: return 1;
897: }
898:
899: /* HBB 970322: new macro, invented because code like this occured several
900: * times inside init_polygons, esp. after I added the option to choose the
901: * other diagonal to divide a quad when necessary */
902: /* HBB 980213: Here and below in init_polygons, added code to properly
903: * free any allocated vertex lists ('v' here), or avoid allocating
904: * them in the first place. Thanks to Stefan Schroepfer for reporting
905: * the leak. */
906: #define PREPARE_POLYGON(n,v,i0,i1,i2,line,c,border,i_chk,ncrv_chk,style) do {\
907: (n) = 3; \
908: if (VERTEX_IS_UNDEFINED(vlist[vert_free + (i0)])\
909: || VERTEX_IS_UNDEFINED(vlist[vert_free + (i1)]) \
910: || VERTEX_IS_UNDEFINED(vlist[vert_free + (i2)])) { \
911: /* These values avoid any further action on this polygon */\
912: (v) = 0; /* flag this as undefined */ \
913: (c) = (border) = 0; \
914: } else {\
1.1.1.3 ! ohara 915: (v) = (long *) gp_alloc (sizeof (long) * (n), "hidden PREPARE_POLYGON"); \
1.1 maekawa 916: (v)[0] = vert_free + (i0);\
917: (v)[1] = vert_free + (i1);\
918: (v)[2] = vert_free + (i2);\
919: (line) = hiddenTriangleLinesdrawnPattern;\
920: GET_SIDE((v),(c));\
921: /* Is this polygon at the border of the surface? */\
922: (border) = (i == (i_chk) || ncrv == (ncrv_chk));\
923: }\
924: (style) = ((c) >= 0) ? above : below;\
925: } while (0)
926:
927: static void init_polygons(plots, pcount)
928: struct surface_points *plots;
929: int pcount;
930: /* Initialize vlist, plist */
931: {
932: long int i;
933: struct surface_points *this_plot;
934: int surface;
935: long int ncrv, ncrv1;
936: struct iso_curve *icrvs;
937: int row_offset;
938: int id;
939: int n1, n2; /* number of vertices of a Polygon */
940: long *v1, *v2; /* the Vertices */
941: long line1, line2; /* which lines should be drawn */
942: int above = -1, below, style1, style2; /* the line color */
943: struct lp_style_type *lp; /* pointer to line and point properties */
944: int c1, c2; /* do we see the front or the back */
945: TBOOLEAN border1, border2; /* is it at the border of the surface */
946:
947: /* allocate memory for polylist and nodelist */
948: nvert = npoly = 0;
949: for (this_plot = plots, surface = 0;
950: surface < pcount;
951: this_plot = this_plot->next_sp, surface++) {
952: GETNCRV(ncrv);
953: switch (this_plot->plot_style) {
954: case LINESPOINTS:
955: case STEPS: /* handle as LINES */
956: case FSTEPS:
957: case HISTEPS:
958: case LINES:
959: #if FOUR_TRIANGLES
960: nvert += ncrv * (2 * this_plot->iso_crvs->p_count - 1);
961: #else
962: nvert += ncrv * (this_plot->iso_crvs->p_count);
963: #endif
964: npoly += 2 * (ncrv - 1) * (this_plot->iso_crvs->p_count - 1);
965: break;
966: case DOTS:
967: case XERRORBARS: /* handle as POINTSTYLE */
968: case YERRORBARS:
969: case XYERRORBARS:
970: case BOXXYERROR:
971: case BOXERROR:
972: case CANDLESTICKS: /* HBB: these as well */
973: case FINANCEBARS:
974: case VECTOR:
975: case POINTSTYLE:
976: nvert += ncrv * (this_plot->iso_crvs->p_count);
977: npoly += (ncrv - 1) * (this_plot->iso_crvs->p_count - 1);
978: break;
979: case BOXES: /* handle as IMPULSES */
980: case IMPULSES:
981: nvert += 2 * ncrv * (this_plot->iso_crvs->p_count);
982: npoly += (ncrv - 1) * (this_plot->iso_crvs->p_count - 1);
983: break;
984: }
985: }
986: vlist = (struct Vertex GPHUGE *)
1.1.1.3 ! ohara 987: gp_alloc(sizeof(struct Vertex) * nvert, "hidden vlist");
1.1 maekawa 988: plist = (struct Polygon GPHUGE *)
1.1.1.3 ! ohara 989: gp_alloc(sizeof(struct Polygon) * npoly, "hidden plist");
1.1 maekawa 990:
991: /* initialize vlist: */
992: for (vert_free = 0, this_plot = plots, surface = 0;
993: surface < pcount;
994: this_plot = this_plot->next_sp, surface++) {
995: switch (this_plot->plot_style) {
996: case LINESPOINTS:
997: case BOXERROR: /* handle as POINTSTYLE */
998: case BOXXYERROR:
999: case XERRORBARS:
1000: case YERRORBARS:
1001: case XYERRORBARS:
1002: case CANDLESTICKS: /* HBB: these as well */
1003: case FINANCEBARS:
1004: case VECTOR:
1005: case POINTSTYLE:
1006: above = this_plot->lp_properties.p_type;
1007: break;
1008: case STEPS: /* handle as LINES */
1009: case FSTEPS:
1010: case HISTEPS:
1011: case LINES:
1012: case DOTS:
1013: case BOXES: /* handle as IMPULSES */
1014: case IMPULSES:
1015: above = -1;
1016: break;
1017: }
1018: GETNCRV(ncrv1);
1019: for (ncrv = 0, icrvs = this_plot->iso_crvs;
1020: ncrv < ncrv1 && icrvs;
1021: ncrv++, icrvs = icrvs->next) {
1022: struct coordinate GPHUGE *points = icrvs->points;
1023:
1024: for (i = 0; i < icrvs->p_count; i++) {
1025: /* As long as the point types keep OUTRANGE == 1 and
1026: * UNDEFINED == 2, we can just compare
1027: * hiddenHandleUndefinedPoints to the type of the point. To
1028: * simplify this, let UNHANDLED := UNDEFINED+1 mean 'do not
1029: * handle undefined or outranged points at all' (dangerous
1030: * option, that is...) */
1031: if (points[i].type >= hiddenHandleUndefinedPoints) {
1032: /* mark this vertex as a bad one */
1033: FLAG_VERTEX_AS_UNDEFINED(vlist[vert_free++]);
1034: continue;
1035: }
1036: map3d_xyz(points[i].x, points[i].y, points[i].z, vlist + vert_free);
1037: vlist[vert_free++].style = above;
1038: if (this_plot->plot_style == IMPULSES
1039: || this_plot->plot_style == BOXES) {
1040: map3d_xyz(points[i].x, points[i].y, min_array[FIRST_Z_AXIS], vlist + vert_free);
1041: vlist[vert_free++].style = above;
1042: }
1043: #if FOUR_TRIANGLES
1044: /* FIXME: handle other styles as well! */
1045: if (this_plot->plot_style == LINES &&
1046: i < icrvs->p_count - 1)
1047: vert_free++; /* keep one entry free for quad-center */
1048: #endif
1049: }
1050: }
1051: }
1052:
1053: /* initialize plist: */
1054: id = 0;
1055: for (pfree = vert_free = 0, this_plot = plots, surface = 0;
1056: surface < pcount;
1057: this_plot = this_plot->next_sp, surface++) {
1058: row_offset = this_plot->iso_crvs->p_count;
1059: lp = &(this_plot->lp_properties);
1060: above = this_plot->lp_properties.l_type;
1061: below = this_plot->lp_properties.l_type + hiddenBacksideLinetypeOffset;
1062: GETNCRV(ncrv1);
1063: for (ncrv = 0, icrvs = this_plot->iso_crvs;
1064: ncrv < ncrv1 && icrvs;
1065: ncrv++, icrvs = icrvs->next)
1066: for (i = 0; i < icrvs->p_count; i++)
1067: switch (this_plot->plot_style) {
1068: case LINESPOINTS:
1069: case STEPS: /* handle as LINES */
1070: case FSTEPS:
1071: case HISTEPS:
1072: case LINES:
1073: if (i < icrvs->p_count - 1 && ncrv < ncrv1 - 1) {
1074: #if FOUR_TRIANGLES
1075: long *v3, *v4;
1076: int n3, n4;
1077: long line3, line4;
1078: int c3, c4, style3, style4;
1079: TBOOLEAN border3, border4, inc_id = FALSE;
1080:
1081: /* Build medium vertex: */
1082: vlist[vert_free + 1].x =
1083: (vlist[vert_free].x + vlist[vert_free + 2 * row_offset - 1].x +
1084: vlist[vert_free + 2].x + vlist[vert_free + 2 * row_offset + 1].x
1085: ) / 4;
1086: vlist[vert_free + 1].y =
1087: (vlist[vert_free].y + vlist[vert_free + 2 * row_offset - 1].y +
1088: vlist[vert_free + 2].y + vlist[vert_free + 2 * row_offset + 1].y
1089: ) / 4;
1090: vlist[vert_free + 1].z =
1091: (vlist[vert_free].z + vlist[vert_free + 2 * row_offset - 1].z +
1092: vlist[vert_free + 2].z + vlist[vert_free + 2 * row_offset + 1].z
1093: ) / 4;
1094: vlist[vert_free + 1].style = above;
1095:
1096: PREPARE_POLYGON(n1, v1, 2, 0, 1, line1, c1,
1097: border1, 0, -1, style1);
1098: /* !!FIXME!! special casing (see the older code) still needs to be
1099: * implemented! */
1100: if ((c1 || border1)
1101: && reduce_polygon(&n1, &v1, &line1, 3)) {
1102: CHECK_PLIST();
1103: pfree += maybe_build_polygon(plist + pfree, n1, v1, line1,
1104: style1, lp, -1L, -1L, id++,
1105: is_untested);
1106: inc_id = TRUE;
1107: }
1108: PREPARE_POLYGON(n2, v2, 0, 2 * row_offset - 1, 1, line2, c2,
1109: border2, -1, 0, style2);
1110: if ((c2 || border2)
1111: && reduce_polygon(&n2, &v2, &line2, 3)) {
1112: CHECK_PLIST();
1113: pfree += maybe_build_polygon(plist + pfree, n2, v2, line2,
1114: style2, lp, -1L, -1L, id++,
1115: is_untested);
1116: inc_id = TRUE;
1117: }
1118: PREPARE_POLYGON(n3, v3, 2 * row_offset - 1, 2 * row_offset + 1, 1,
1119: line3, c3, border3, icrvs->p_count - 2, -1,
1120: style3);
1121: if ((c3 || border3)
1122: && reduce_polygon(&n3, &v3, &line3, 3)) {
1123: CHECK_PLIST();
1124: pfree += maybe_build_polygon(plist + pfree, n3, v3, line3,
1125: style3, lp, -1L, -1L, id++,
1126: is_untested);
1127: inc_id = TRUE;
1128: }
1129: PREPARE_POLYGON(n4, v4, 2 * row_offset + 1, 0, 1, line4, c4,
1130: border4, -1, ncrv1 - 2, style4);
1131: if ((c4 || border4)
1132: && reduce_polygon(&n4, &v4, &line4, 3)) {
1133: CHECK_PLIST();
1134: pfree += maybe_build_polygon(plist + pfree, n4, v4, line4,
1135: style4, lp, -1L, -1L, id++,
1136: is_untested);
1137: inc_id = TRUE;
1138: }
1139: /*if (inc_id)
1140: id++; */
1141: vert_free++;
1142:
1143: #else /* FOUR_TRIANGLES */
1144:
1145: PREPARE_POLYGON(n1, v1, row_offset, 0, 1, line1, c1,
1146: border1, 0, 0, style1);
1147: PREPARE_POLYGON(n2, v2, 1, row_offset + 1, row_offset, line2,
1148: c2, border2, icrvs->p_count - 2, ncrv1 - 2,
1149: style2);
1150:
1151: /* if this makes at least one of the two triangles
1152: * visible, use the other diagonal here */
1153: if (hiddenShowAlternativeDiagonal
1154: && !(v1) /* HBB 980213: only try this in the case of */
1155: &&!(v2) /* undefined vertices -> *missing* trigs */
1156: ) {
1157: if (VERTEX_IS_UNDEFINED(vlist[vert_free + 1])) {
1158: PREPARE_POLYGON(n1, v1, row_offset + 1, row_offset, 0,
1159: line1, c1, border1, 0, ncrv1 - 2,
1160: style1);
1161: } else if (VERTEX_IS_UNDEFINED(vlist[vert_free + row_offset])) {
1162: PREPARE_POLYGON(n1, v1, 0, 1, row_offset + 1, line1,
1163: c1, border1, icrvs->p_count - 2, 0,
1164: style1);
1165: }
1166: }
1167: /* HBB 970323: if visible sides of the two triangles
1168: * differs, make diagonal visible! */
1169: /* HBB 970428: FIXME: should this be changed to only
1170: * activate *one* of the triangles' diagonals? If so, how
1171: * to find out the right one? Maybe the one with its
1172: * normal closer to the z direction? */
1173: if (hiddenHandleBentoverQuadrangles
1174: && (c1 * c2) < 0
1175: ) {
1176: SETBIT(line1, n1 - 1, 1);
1177: SETBIT(line2, n2 - 1, 1);
1178: }
1179: if ((c1 || border1)
1180: && reduce_polygon(&n1, &v1, &line1, 3)) {
1181: if ((c2 || border2)
1182: && reduce_polygon(&n2, &v2, &line2, 3)) {
1183: /* These two will need special handling, to
1184: * ensure the links from one to the other
1185: * are only set up when *both* polygons are
1186: * valid */
1187: int r1, r2; /* temp. results */
1188:
1189: CHECK_PLIST_2();
1190: r1 = maybe_build_polygon(plist + pfree, n1, v1,
1191: line1, style1, lp, -1L,
1192: -1L, id, is_untested);
1193: r2 = maybe_build_polygon(plist + pfree + r1, n2, v2,
1194: line2, style2, lp, -1L,
1195: -1L, id++, is_untested);
1196: if (r1 && r2) {
1197: plist[pfree].next_frag = pfree + 1;
1198: plist[pfree + 1].next_frag = pfree;
1199: }
1200: pfree += r1 + r2;
1201: } else { /* P1 was ok, but P2 wasn't */
1202: /* HBB 980213: P2 is invisible, so free its vertex list: */
1203: if (v2) {
1204: free(v2);
1205: v2 = 0;
1206: }
1207: /* HBB 970323: if other polygon wasn't drawn, draw this polygon's
1208: * diagonal visibly (not only if it was 'on edge'). */
1209: /*if (c2 || border2) */
1210: SETBIT(line1, n1 - 1, 1);
1211: CHECK_PLIST();
1212: pfree += maybe_build_polygon(plist + pfree, n1, v1, line1,
1213: style1, lp, -1L, -1L, id++,
1214: is_untested);
1215: }
1216: } else { /* P1 was not ok */
1217: /* HBB 980213: P1 is invisible, so free its vertex list: */
1218: if (v1) {
1219: free(v1);
1220: v1 = 0;
1221: }
1222: /* HBB 970323: if other polygon wasn't drawn, draw this polygon's
1223: * diagonal visibly (not only if it was 'on edge'). */
1224: /*if (c1 || border1) */
1225: SETBIT(line2, n2 - 1, 1);
1226: /* HBB 970522: yet another problem triggered by the handling of
1227: * undefined points: if !(c2||border2), we mustn't try to reduce
1228: * triangle 2. */
1229: if (0
1230: || (1
1231: && (c2 || border2)
1232: && reduce_polygon(&n2, &v2, &line2, 2))
1233: || (1
1234: /* HBB 980213: reduce_... above might have zeroed v... */
1235: && (v2)
1236: && (c1 || border1))) {
1237: CHECK_PLIST();
1238: pfree += maybe_build_polygon(plist + pfree, n2, v2, line2,
1239: style2, lp, -1L, -1L, id++,
1240: is_untested);
1241: } else {
1242: /* HBB 980213: sigh... both P1 and P2 were invisible, but
1243: * at least one of them was a not undefined.. */
1244: if (v1)
1245: free(v1);
1246: if (v2)
1247: free(v2);
1248: }
1249: }
1250: #endif /* else: FOUR_TRIANGLES */
1251: }
1252: vert_free++;
1253: break;
1254: case DOTS:
1.1.1.3 ! ohara 1255: v1 = (long *) gp_alloc(sizeof(long) * 1,
1.1 maekawa 1256: "hidden v1 for dots");
1257: v1[0] = vert_free++;
1258: CHECK_PLIST();
1259: pfree += maybe_build_polygon(plist + pfree, 1, v1, 1L, above,
1260: lp, -1L, -1L, id++, is_untested);
1261: break;
1262: case BOXERROR: /* handle as POINTSTYLE */
1263: case BOXXYERROR:
1264: case XERRORBARS: /* handle as POINTSTYLE */
1265: case YERRORBARS:
1266: case XYERRORBARS:
1267: case CANDLESTICKS: /* HBB: these as well */
1268: case FINANCEBARS:
1269: case POINTSTYLE:
1270: case VECTOR:
1.1.1.3 ! ohara 1271: v1 = (long *) gp_alloc(sizeof(long) * 1,
1.1 maekawa 1272: "hidden v1 for point");
1273: v1[0] = vert_free++;
1274: CHECK_PLIST();
1275: pfree += maybe_build_polygon(plist + pfree, 1, v1, 0L, above,
1276: lp, -1L, -1L, id++, is_untested);
1277: break;
1278: case BOXES: /* handle as IMPULSES */
1279: case IMPULSES:
1280: n1 = 2;
1.1.1.3 ! ohara 1281: v1 = (long *) gp_alloc(sizeof(long) * n1,
1.1 maekawa 1282: "hidden v1 for impulse");
1283: v1[0] = vert_free++;
1284: v1[1] = vert_free++;
1285: line1 = 2L;
1286: (void) reduce_polygon(&n1, &v1, &line1, 1);
1287: CHECK_PLIST();
1288: pfree += maybe_build_polygon(plist + pfree, n1, v1, line1, above,
1289: lp, -1L, -1L, id++, is_untested);
1290: break;
1291: }
1292: }
1293: }
1294:
1.1.1.3 ! ohara 1295: int compare_by_zmax(p1, p2)
! 1296: SORTFUNC_ARGS p1;
! 1297: SORTFUNC_ARGS p2;
1.1 maekawa 1298: {
1.1.1.3 ! ohara 1299: return (SIGNOF(plist[*(const long *) p2].zmax
! 1300: - plist[*(const long *) p1].zmax));
1.1 maekawa 1301: }
1302:
1303: static void sort_by_zmax()
1304: /* and build the list (return_value = start of list) */
1305: {
1306: long *sortarray, i;
1307: struct Polygon GPHUGE *this;
1.1.1.3 ! ohara 1308: sortarray = (long *) gp_alloc(sizeof(long) * pfree, "hidden sortarray");
1.1 maekawa 1309: for (i = 0; i < pfree; i++)
1310: sortarray[i] = i;
1311: qsort(sortarray, (size_t) pfree, sizeof(long), compare_by_zmax);
1312: this = plist + sortarray[0];
1313: for (i = 1; i < pfree; i++) {
1314: this->next = sortarray[i];
1315: this = plist + sortarray[i];
1316: }
1317: this->next = -1L;
1318: pfirst = sortarray[0];
1319: free(sortarray);
1320: }
1321:
1322:
1323: /* HBB: try if converting this code to unsigned int (from signed shorts)
1324: * fixes any of the remaining bugs. In the same motion, remove
1325: * hardcoded sizeof(short) = 2 (09.10.1996) */
1326:
1327: #define LASTBITS (USHRT_BITS -1) /* ????? */
1328: static int obscured(p)
1329: /* is p obscured by already drawn polygons? (only a simple minimax-test) */
1330: struct Polygon GPHUGE *p;
1331: {
1332: int l_xmin, l_xmax, l_ymin, l_ymax; /* HBB 961110: avoid shadowing external names */
1333: t_pnt mask1, mask2;
1334: long indx1, indx2, k, m;
1335: tp_pnt cpnt;
1336: /* build the minimax-box */
1337: l_xmin = (p->xmin * xscaler) + xmiddle;
1338: l_xmax = (p->xmax * xscaler) + xmiddle;
1339: l_ymin = (p->ymin * yscaler) + ymiddle;
1340: l_ymax = (p->ymax * yscaler) + ymiddle;
1341: if (l_xmin < xleft)
1342: l_xmin = xleft;
1343: if (l_xmax > xright)
1344: l_xmax = xright;
1345: if (l_ymin < ybot)
1346: l_ymin = ybot;
1347: if (l_ymax > ytop)
1348: l_ymax = ytop;
1349: if (l_xmin > l_xmax || l_ymin > l_ymax)
1350: return 1; /* not viewable */
1351: l_ymin = YREDUCE(l_ymin) - YREDUCE(ybot);
1352: l_ymax = YREDUCE(l_ymax) - YREDUCE(ybot);
1353: l_xmin = XREDUCE(l_xmin) - XREDUCE(xleft);
1354: l_xmax = XREDUCE(l_xmax) - XREDUCE(xleft);
1355: /* Now check bitmap */
1356: indx1 = l_ymin / PNT_BITS;
1357: indx2 = l_ymax / PNT_BITS;
1358: mask1 = PNT_MAX << (((unsigned) l_ymin) % PNT_BITS);
1359: mask2 = PNT_MAX >> ((~((unsigned) l_ymax)) % PNT_BITS);
1360: /* HBB: lclint wanted this: */
1361: assert(pnt != 0);
1362: for (m = l_xmin; m <= l_xmax; m++) {
1363: if (pnt[m] == 0)
1364: return 0; /* not obscured */
1365: cpnt = pnt[m] + indx1;
1366: if (indx1 == indx2) {
1367: if (~(*cpnt) & mask1 & mask2)
1368: return 0;
1369: } else {
1370: if (~(*cpnt++) & mask1)
1371: return 0;
1372: for (k = indx1 + 1; k < indx2; k++)
1373: if ((*cpnt++) != PNT_MAX)
1374: return 0;
1375: if (~(*cpnt++) & mask2)
1376: return 0;
1377: }
1378: }
1379: return 1;
1380: }
1381:
1382:
1383: void draw_line_hidden(x1, y1, x2, y2)
1384: unsigned int x1, y1, x2, y2;
1385: {
1386: register struct termentry *t = term;
1387: TBOOLEAN flag;
1388: register int xv, yv, errx, erry, err;
1389: register unsigned int xvr, yvr;
1390: int unsigned xve, yve;
1391: register int dy, nstep = 0, dyr;
1392: int i;
1393:
1394: if (x1 > x2) {
1395: xvr = x2;
1396: yvr = y2;
1397: xve = x1;
1398: yve = y1;
1399: } else {
1400: xvr = x1;
1401: yvr = y1;
1402: xve = x2;
1403: yve = y2;
1404: };
1405: errx = XREDUCE(xve) - XREDUCE(xvr);
1406: erry = YREDUCE(yve) - YREDUCE(yvr);
1407: dy = (erry > 0 ? 1 : -1);
1408: dyr = dy * yfact;
1409: switch (dy) {
1410: case 1:
1411: nstep = errx + erry;
1412: errx = -errx;
1413: break;
1414: case -1:
1415: nstep = errx - erry;
1416: errx = -errx;
1417: erry = -erry;
1418: break;
1419: };
1420: err = errx + erry;
1421: errx <<= 1;
1422: erry <<= 1;
1423: xv = XREDUCE(xvr) - XREDUCE(xleft);
1424: yv = YREDUCE(yvr) - YREDUCE(ybot);
1425: (*t->move) (xvr, yvr);
1426: flag = !IS_UNSET(xv, yv);
1427: if (!hidden_no_update) { /* Check first point */
1428: assert(ymax_hl != 0);
1429: assert(ymin_hl != 0);
1430: if (xv < xmin_hl)
1431: xmin_hl = xv;
1432: if (xv > xmax_hl)
1433: xmax_hl = xv;
1434: if (yv > ymax_hl[xv])
1435: ymax_hl[xv] = yv;
1436: if (yv < ymin_hl[xv])
1437: ymin_hl[xv] = yv;
1438: };
1439: for (i = 0; i < nstep; i++) {
1440: if (err < 0) {
1441: xv++;
1442: xvr += xfact;
1443: err += erry;
1444: } else {
1445: yv += dy;
1446: yvr += dyr;
1447: err += errx;
1448: };
1449: if (IS_UNSET(xv, yv)) {
1450: if (flag) {
1451: (*t->move) (xvr, yvr);
1452: flag = FALSE;
1453: };
1454: } else {
1455: if (!flag) {
1456: (*t->vector) (xvr, yvr);
1457: flag = TRUE;
1458: };
1459: };
1460: if (!hidden_no_update) {
1461: /* HBB 961110: lclint wanted these: */
1462: assert(ymax_hl != 0);
1463: assert(ymin_hl != 0);
1464: if (xv < xmin_hl)
1465: xmin_hl = xv;
1466: if (xv > xmax_hl)
1467: xmax_hl = xv;
1468: if (yv > ymax_hl[xv])
1469: ymax_hl[xv] = yv;
1470: if (yv < ymin_hl[xv])
1471: ymin_hl[xv] = yv;
1472: };
1473: };
1474: if (!flag)
1475: (*t->vector) (xve, yve);
1476: return;
1477: }
1478:
1479:
1480: static GP_INLINE int xy_overlap(a, b)
1481: /* Do a and b overlap in x or y (minimax test) */
1482: struct Polygon GPHUGE *a, GPHUGE * b;
1483: {
1484: #if TEST_GRIDCHECK
1485: /* First, check by comparing the extent bit patterns: */
1486: if (!((a->xextent & b->xextent) && (a->yextent & b->yextent)))
1487: return 0;
1488: #endif
1489: return ((int) (GE(b->xmax, a->xmin) && GE(a->xmax, b->xmin)
1490: && GE(b->ymax, a->ymin) && GE(a->ymax, b->ymin)));
1491: }
1492:
1493:
1494: static void get_plane(p, a, b, c, d)
1495: struct Polygon GPHUGE *p;
1496: double *a, *b, *c, *d;
1497: {
1498: int i;
1499: struct Vertex GPHUGE *v1, GPHUGE * v2;
1500: double x, y, z, s;
1501: if (p->n == 1) {
1502: *a = 0.0;
1503: *b = 0.0;
1504: *c = 1.0;
1505: *d = -vlist[p->vertex[0]].z;
1506: return;
1507: }
1508: v1 = vlist + p->vertex[p->n - 1];
1509: v2 = vlist + p->vertex[0];
1510: *a = (v1->y - v2->y) * (v1->z + v2->z);
1511: *b = (v1->z - v2->z) * (v1->x + v2->x);
1512: *c = (v1->x - v2->x) * (v1->y + v2->y);
1513: for (i = 0; i < p->n - 1; i++) {
1514: v1 = vlist + p->vertex[i];
1515: v2 = vlist + p->vertex[i + 1];
1516: *a += (v1->y - v2->y) * (v1->z + v2->z);
1517: *b += (v1->z - v2->z) * (v1->x + v2->x);
1518: *c += (v1->x - v2->x) * (v1->y + v2->y);
1519: }
1520: s = sqrt(*a * *a + *b * *b + *c * *c);
1521: if (GE(0.0, s)) { /* => s==0 => the vertices are in one line */
1522: v1 = vlist + p->vertex[0];
1523: for (i = 1; i < p->n; i++) {
1524: v2 = vlist + p->vertex[i];
1525: if (!V_EQUAL(v1, v2))
1526: break;
1527: }
1528: /* (x,y,z) is l.u. from <v1, v2> */
1529: x = v1->x;
1530: y = v1->y;
1531: z = v1->z;
1532: if (EQ(y, v2->y))
1533: y += 1.0;
1534: else
1535: x += 1.0;
1536: /* build a vector that is orthogonal to the line of the polygon */
1537: *a = v1->y * (v2->z - z) + v2->y * (z - v1->z) + y * (v1->z - v2->z);
1538: *b = v1->z * (v2->x - x) + v2->z * (x - v1->x) + z * (v1->x - v2->x);
1539: *c = v1->x * (v2->y - y) + v2->x * (y - v1->y) + x * (v1->y - v2->y);
1540: s = sqrt(*a * *a + *b * *b + *c * *c);
1541: }
1542: if (*c < 0.0) /* ensure that normalized c is > 0 */
1543: s *= -1.0; /* The exact relation, because c can be very small */
1544: *a /= s;
1545: *b /= s;
1546: *c /= s;
1547: *d = -*a * v1->x - *b * v1->y - *c * v1->z;
1548: return;
1549: }
1550:
1551:
1552: static t_poly_plane_intersect
1553: polygon_plane_intersection(p, a, b, c, d)
1554: struct Polygon GPHUGE *p;
1555: double a, b, c, d;
1556: {
1557: int i, sign, max_sign, min_sign;
1558: struct Vertex GPHUGE *v;
1559:
1560: CHECK_POINTER(plist, p);
1561:
1562: v = vlist + p->vertex[0];
1563: max_sign = min_sign = SIGNOF(a * v->x + b * v->y + c * v->z + d);
1564: for (i = 1; i < p->n; i++) {
1565: v = vlist + p->vertex[i];
1566: sign = SIGNOF(a * v->x + b * v->y + c * v->z + d);
1567: if (sign > max_sign)
1568: max_sign = sign;
1569: else if (sign < min_sign)
1570: min_sign = sign;
1571: }
1572:
1573: /* Yes, this is a bit tricky, but it's simpler for the computer... */
1574: if (min_sign == -1) {
1575: if (max_sign == 1)
1576: return (intersects);
1577: else
1578: return behind;
1579: } else {
1580: if ((max_sign == 0) && (min_sign == 0))
1581: return (inside);
1582: else
1583: return infront;
1584: }
1585: }
1586:
1587:
1588: /* full xy-overlap test (support routines first) */
1589:
1590: /* What do negative return values mean?
1591: It is allowed, that the 2 polygons touch themselves in one point.
1592: There are 2 possibilities of this case:
1593: (A) A vertex of the one polygon is on an edge of the other
1594: (B) The two polygons have a vertex together.
1595: In case (A) the algorithm finds 2 edges, wich touches an edge of the
1596: other polygon. In case (B) the algorithm finds four pairs of edges.
1597: I handle both cases with negative return values:
1598: Case (A) returns -2, and case (B) returns -1.
1599: So I can say, if the sum of negative return values goes greater than 4
1600: (absolutly), there must be more than one touch point. So the
1601: polygons must overlap. */
1602:
1603: /* some variables, for keeping track of minima and maxima across
1604: * all these routines */
1605:
1606: static double m1x, M1x, m1y, M1y, m2x, M2x, m2y, M2y;
1607:
1608: #define MINIMAX (GE(M2x,m1x) && GE(M1x,m2x) && GE(M2y,m1y) && GE(M1y,m2y))
1609:
1610:
1611: /* Does the edge [v1,v2] intersect edge [v3, v4] ?
1612: * This is for non-vertical [v1,v2]
1613: */
1614: static int intersect(v1, v2, v3, v4)
1615: struct Vertex GPHUGE *v1, GPHUGE * v2, GPHUGE * v3, GPHUGE * v4;
1616: {
1617: double m1, m2, t1, t2, x, y, minx, maxx;
1618:
1619: m1 = (v2->y - v1->y) / (v2->x - v1->x);
1620: t1 = v1->y - m1 * v1->x;
1621:
1622: /* if [v3,v4] vertical: */
1623: if (EQ(v3->x, v4->x)) {
1624: y = v3->x * m1 + t1;
1625: if (GR(m2x, m1x) && GR(M1x, m2x)) {
1626: if (GR(y, m2y) && GR(M2y, y))
1627: return 1;
1628: if (EQ(y, m2y) || EQ(y, M2y))
1629: return -2;
1630: return 0;
1631: }
1632: /* m2x == m1x || m2x == M1x */
1633: if (GR(y, m2y) && GR(M2y, y))
1634: return -2;
1635: if (EQ(y, m2y) || EQ(y, M2y))
1636: return -1;
1637: return 0;
1638: }
1639: /* [v3,v4] not vertical */
1640: m2 = (v4->y - v3->y) / (v4->x - v3->x);
1641: t2 = v3->y - m2 * v3->x;
1642: if (!SIGNOF(m1 - m2)) { /* if edges are parallel: */
1643: x = m1 * v3->x + t1 - v3->y;
1644: if (!EQ(m1 * v3->x + t1 - v3->y, 0.0))
1645: return 0;
1646: if (GR(M2x, m1x) && GR(M1x, m2x))
1647: return 1;
1648: return -1; /* the edges have a common vertex */
1649: }
1650: x = (t2 - t1) / (m1 - m2);
1651: minx = GPMAX(m1x, m2x);
1652: maxx = GPMIN(M1x, M2x);
1653: if (GR(x, minx) && GR(maxx, x))
1654: return 1;
1655: if (GR(minx, x) || GR(x, maxx))
1656: return 0;
1657: if ((EQ(x, m1x) || EQ(x, M1x)) && (EQ(x, m1x) || EQ(x, M1x)))
1658: return -1;
1659: return -2;
1660: }
1661:
1662: /* Does the edge [v1,v2] intersect edge [v3, v4] ?
1663: * This is for vertical [v1,v2]
1664: */
1665: static int v_intersect(v1, v2, v3, v4)
1666: struct Vertex GPHUGE *v1, GPHUGE * v2, GPHUGE * v3, GPHUGE * v4;
1667: {
1668: double y;
1669:
1670: /* HBB 971115: to silence picky compilers, use v2 at least once, in
1671: * a dummy expression (caution, may be ANSI-C specific because of
1672: * the use of 'void'...) */
1673: (void) v2;
1674:
1675: /* if [v3,v4] is vertical, too: */
1676: /* already known: rectangles do overlap, because MINIMAX was true */
1677: if (EQ(v3->x, v4->x))
1678: return (GR(M2y, m1y) && GR(M1y, m2y)) ? 1 : -1;
1679:
1680: /* [v3,v4] not vertical */
1681: y = v3->y + (v1->x - v3->x) * (v4->y - v3->y) / (v4->x - v3->x);
1682: if (GR(m1x, m2x) && GR(M2x, m1x)) {
1683: if (GR(y, m1y) && GR(M1y, y))
1684: return 1;
1685: if (EQ(y, m1y) || EQ(y, M1y))
1686: return -2;
1687: return 0;
1688: }
1689: /* m1x == m2x || m1x == M2x */
1690: if (GR(y, m1y) && GR(M1y, y))
1691: return -2;
1692: if (EQ(y, m1y) || EQ(y, M1y))
1693: return -1;
1694: return 0;
1695: }
1696:
1697: #define UPD_MINMAX(v1,v2,npar) do { \
1698: if (v1->x< v2->x) \
1699: CONCAT3(m,npar,x) = v1->x, CONCAT3(M,npar,x) = v2->x; \
1700: else \
1701: CONCAT3(m,npar,x) = v2->x, CONCAT3(M,npar,x) = v1->x; \
1702: if (v1->y< v2->y) \
1703: CONCAT3(m,npar,y) = v1->y, CONCAT3(M,npar,y) = v2->y; \
1704: else \
1705: CONCAT3(m,npar,y) = v2->y, CONCAT3(M,npar,y) = v1->y; \
1706: } while (0)
1707:
1708: /* does the edge [v1,v2] intersect polygon p? */
1709: static int intersect_polygon(v1, v2, p)
1710: struct Vertex GPHUGE *v1, GPHUGE * v2;
1711: struct Polygon GPHUGE *p;
1712: {
1713: struct Vertex GPHUGE *v3, GPHUGE * v4;
1714: int i, s, t = 0;
1715: int (*which_intersect) __PROTO((struct Vertex GPHUGE * v1,
1716: struct Vertex GPHUGE * v2,
1717: struct Vertex GPHUGE * v3,
1718: struct Vertex GPHUGE * v4))
1719: = intersect;
1720:
1721: /* Is [v1,v2] vertical? If, use v_intersect() */
1722: if (EQ(v1->x, v2->x))
1723: which_intersect = v_intersect;
1724:
1725: UPD_MINMAX(v1,v2,1);
1726:
1727: /* test first edge of polygon p */
1728: v3 = vlist + p->vertex[p->n - 1];
1729: v4 = vlist + p->vertex[0];
1730: UPD_MINMAX(v3,v4,2);
1731:
1732:
1733: if (MINIMAX) {
1734: s = (*which_intersect) (v1, v2, v3, v4);
1735: if (s == 1 || (s < 0 && (t += s) < -4))
1736: return 1;
1737: }
1738: /* and the other edges... */
1739: for (i = 0; i < p->n - 1; i++) {
1740: v3 = vlist + p->vertex[i];
1741: v4 = vlist + p->vertex[i + 1];
1742: UPD_MINMAX(v3,v4,2);
1743: if (!MINIMAX)
1744: continue;
1745: s = (*which_intersect) (v1, v2, v3, v4);
1746: if (s == 1 || (s < 0 && (t += s) < -4))
1747: return 1;
1748: }
1749: return t;
1750: }
1751:
1752: /* OK, now here comes the 'real' polygon intersection routine:
1753: * Do a and b overlap in x or y (full test):
1754: * Do edges intersect, do the polygons touch in two points,
1755: * or is a vertex of one polygon inside the other polygon? */
1756:
1757: static int full_xy_overlap(a, b)
1758: struct Polygon GPHUGE *a, GPHUGE * b;
1759: {
1760: struct Vertex GPHUGE *v1, GPHUGE * v2, v;
1761: int i, s, t = 0;
1762:
1763: if (a->n < 2 || b->n < 2)
1764: return 0;
1765: v1 = vlist + a->vertex[a->n - 1];
1766: v2 = vlist + a->vertex[0];
1767: s = intersect_polygon(v1, v2, b);
1768: if (s == 1 || (s < 0 && (t += s) < -4))
1769: return 1;
1770: for (i = 0; i < a->n - 1; i++) {
1771: v1 = vlist + a->vertex[i];
1772: v2 = vlist + a->vertex[i + 1];
1773: s = intersect_polygon(v1, v2, b);
1774: if (s == 1 || (s < 0 && (t += s) < -4))
1775: return 1;
1776: }
1777: /* No edges intersect. Is one polygon inside the other? */
1778: /* The inner polygon has the greater minx */
1779: if (a->xmin < b->xmin) {
1780: struct Polygon GPHUGE *temp = a;
1781: a = b;
1782: b = temp;
1783: }
1784: /* Now, a is the inner polygon */
1785: for (i = 0; i < a->n; i++) {
1786: v1 = vlist + a->vertex[i];
1787: /* HBB: lclint seems to have found a problem here: v wasn't
1788: * fully defined when passed to intersect_polygon() */
1789: v = *v1;
1790: v.x = -1.1;
1791: s = intersect_polygon(v1, &v, b);
1792: if (s == 0)
1793: return 0; /* a is outside polygon b */
1794: v.x = 1.1;
1795: if (s == 1) {
1796: s = intersect_polygon(v1, &v, b);
1797: if (s == 0)
1798: return 0;
1799: if (s == 1)
1800: return 1;
1801: } else if (intersect_polygon(v1, &v, b) == 0)
1802: return 0;
1803: }
1804: #if 1
1805: /* 970614: don't bother, just presume that they do overlap: */
1806: return 1;
1807: #else /* !1 */
1808: print_polygon(a, "a");
1809: print_polygon(b, "b");
1810: graph_error("Logic Error in full_xy_overlap");
1811: return -1; /* HBB: shut up gcc -Wall */
1812: #endif /* !1 */
1813: }
1814:
1815:
1816: /* Helper routine for split_polygon_by_plane */
1817: static long build_new_vertex(V1, V2, w)
1818: long V1, V2; /* the vertices, between which a new vertex is demanded */
1819: double w; /* information about where between V1 and V2 it should be */
1820: {
1821: long V;
1822: struct Vertex GPHUGE *v, GPHUGE * v1, GPHUGE * v2;
1823:
1824: if (EQ(w, 0.0))
1825: return V1;
1826: if (EQ(w, 1.0))
1827: return V2;
1828:
1829: /* We need a new Vertex */
1830: if (vert_free == nvert) /* Extend vlist, if necessary */
1831: vlist = (struct Vertex GPHUGE *)
1832: gp_realloc(vlist, (unsigned long) sizeof(struct Vertex) * (nvert += 10L), "hidden vlist");
1833: V = vert_free++;
1834: v = vlist + V;
1835: v1 = vlist + V1;
1836: v2 = vlist + V2;
1837:
1838: v->x = (v2->x - v1->x) * w + v1->x;
1839: v->y = (v2->y - v1->y) * w + v1->y;
1840: v->z = (v2->z - v1->z) * w + v1->z;
1841: v->style = -1;
1842:
1843: /* 970610: additional checks, to prevent adding unnecessary vertices */
1844: if (V_EQUAL(v, v1)) {
1845: vert_free--;
1846: return V1;
1847: }
1848: if (V_EQUAL(v, v2)) {
1849: vert_free--;
1850: return V2;
1851: }
1852: return V;
1853: }
1854:
1855:
1856: /* Splits polygon p by the plane represented by its equation
1857: * coeffecients a to d.
1858: * return-value: part of the polygon, that is in front/back of plane
1859: * (Distinction necessary to ensure the ordering of polygons in
1860: * the plist stays intact)
1861: * Caution: plist and vlist can change their location!!!
1862: * If a point is in plane, it comes to the behind - part
1863: * (HBB: that may well have changed, as I cut at the 'in plane'
1864: * mechanisms heavily)
1865: */
1866:
1867: static long split_polygon_by_plane(P, a, b, c, d, f)
1868: long P; /* Polygon as index on plist */
1869: double a, b, c, d;
1870: TBOOLEAN f; /* return value = Front(1) or Back(0) */
1871: {
1872: int i, j;
1873: struct Polygon GPHUGE *p = plist + P;
1874: struct Vertex GPHUGE *v;
1875: int snew, stest;
1876: int in_plane; /* what is about points in plane? */
1877: int cross1, cross2; /* first vertices, after p crossed the plane */
1878: double a1 = 0.0, b1, a2 = 0.0, b2; /* parameters of the crosses */
1879: long Front; /* the new Polygon */
1880: int n1, n2;
1881: long *v1, *v2;
1882: long line1, line2;
1883: long next_frag_temp;
1884:
1885:
1886: CHECK_POINTER(plist, p);
1887:
1888: in_plane = (EQ(c, 0.0) && f) ? 1 : -1;
1889: /* first vertex */
1890: v = vlist + p->vertex[0];
1891:
1892: CHECK_POINTER(vlist, v);
1893:
1894: b1 = a * v->x + b * v->y + c * v->z + d;
1895: stest = SIGNOF(b1);
1896: #if OLD_SPLIT_INPLANE
1897: if (!stest)
1898: stest = in_plane;
1899: #endif
1900:
1901: /* find first vertex that is on the other side of the plane */
1902: for (cross1 = 1, snew = stest; snew == stest && cross1 < p->n; cross1++) {
1903: a1 = b1;
1904: v = vlist + p->vertex[cross1];
1905: CHECK_POINTER(vlist, v);
1906: b1 = a * v->x + b * v->y + c * v->z + d;
1907: snew = SIGNOF(b1);
1908: #if OLD_SPLIT_INPLANE
1909: if (!snew)
1910: snew = in_plane;
1911: #endif
1912: }
1913:
1914: if (snew == stest) {
1915: /*HBB: this is possibly not an error in split_polygon, it's just
1916: * not possible to split this polygon by this plane. I.e., the
1917: * error is in the caller! */
1918: fprintf(stderr, "split_poly failed, polygon nr. %ld\n", P);
1919: return (-1); /* return 'unsplittable' */
1920: }
1921: cross1--; /* now, it's the last one on 'this' side */
1922:
1923: /* first vertex that is on the first side again */
1924: for (b2 = b1, cross2 = cross1 + 1;
1925: snew != stest && cross2 < p->n; cross2++) {
1926: a2 = b2;
1927: v = vlist + p->vertex[cross2];
1928: CHECK_POINTER(vlist, v);
1929: b2 = a * v->x + b * v->y + c * v->z + d;
1930: snew = SIGNOF(b2);
1931: #if OLD_SPLIT_INPLANE
1932: if (!snew)
1933: snew = -in_plane;
1934: #endif
1935: }
1936:
1937: if (snew != stest) {
1938: /* only p->vertex[0] is on 'this' side */
1939: a2 = b2;
1940: v = vlist + p->vertex[0];
1941: CHECK_POINTER(vlist, v);
1942: b2 = a * v->x + b * v->y + c * v->z + d;
1943: } else
1944: cross2--; /* now it's the last one on 'the other' side */
1945:
1946: /* We need two new polygons instead of the old one: */
1947: n1 = p->n - cross2 + cross1 + 2;
1948: n2 = cross2 - cross1 + 2;
1.1.1.3 ! ohara 1949: v1 = (long *) gp_alloc(sizeof(long) * n1, "hidden v1 for two new poly");
! 1950: v2 = (long *) gp_alloc(sizeof(long) * n2, "hidden v2 for two new poly");
1.1 maekawa 1951: #if SHOW_SPLITTING_EDGES
1952: line1 = 1L << (n1 - 1);
1953: line2 = 1L << (n2 - 1);
1954: #else
1955: line1 = line2 = 0L;
1956: #endif
1957: v1[0] = v2[n2 - 1] =
1958: build_new_vertex(p->vertex[cross2 - 1],
1959: p->vertex[(cross2 < p->n) ? cross2 : 0], a2 / (a2 - b2));
1960: v2[0] = v1[n1 - 1] =
1961: build_new_vertex(p->vertex[cross1 - 1],
1962: p->vertex[cross1], a1 / (a1 - b1));
1963:
1964: /* Copy visibility from split edges to their fragments: */
1965: if (p->line & (1 << (cross1 - 1))) {
1966: line1 |= 1L << (n1 - 2);
1967: line2 |= 1L;
1968: }
1969: if (p->line & (1L << (cross2 - 1))) {
1970: line1 |= 1L;
1971: line2 |= 1L << (n2 - 2);
1972: }
1973: /* Copy the old line patterns and vertex listings into new places */
1974: /* p->vertex[cross2...p->n-1] --> v1[1...] */
1975: for (i = cross2, j = 1; i < p->n;) {
1976: if (p->line & (1L << i))
1977: line1 |= 1L << j;
1978: v1[j++] = p->vertex[i++];
1979: }
1980: /* p->vertex[0...cross1-1] --> v1[...n1-2] */
1981: for (i = 0; i < cross1 - 1;) {
1982: if (p->line & (1L << i))
1983: line1 |= 1L << j;
1984: v1[j++] = p->vertex[i++];
1985: }
1986: v1[j++] = p->vertex[i++];
1987:
1988: /* p->vertex[cross1...cross2-1] -> v2[1...n2-2] */
1989: for (j = 1; i < cross2 - 1;) {
1990: if (p->line & (1L << i))
1991: line2 |= 1L << j;
1992: v2[j++] = p->vertex[i++];
1993: }
1994: v2[j++] = p->vertex[i];
1995:
1996: /* old vertex list isn't needed any more: */
1997: free(p->vertex);
1998: p->vertex = 0;
1999:
2000: if (!reduce_polygon(&n1, &v1, &line1, 1) ||
2001: !reduce_polygon(&n2, &v2, &line2, 1))
2002: graph_error("Logic Error 2 in split_polygon");
2003:
2004: /* Build the 2 new polygons : we are reusing one + making one new */
2005: CHECK_PLIST_EXTRA(p = plist + P);
2006: Front = pfree++;
2007:
2008: if ((next_frag_temp = p->next_frag) < 0)
2009: next_frag_temp = P; /* First split of this polygon at all */
2010:
2011: /* HBB 961110: lclint said == shouldn't be used on Boolean's */
2012: if ((f && (stest < 0)) || ((!f) && !(stest < 0))) {
2013: build_polygon(plist + P, n1, v1, line1, p->style, p->lp,
2014: p->next, Front, p->id, p->tested);
2015: build_polygon(plist + Front, n2, v2, line2, p->style, p->lp,
2016: -1, next_frag_temp, p->id, is_moved_or_split);
2017: } else {
2018: build_polygon(plist + P, n2, v2, line2, p->style, p->lp,
2019: p->next, Front, p->id, p->tested);
2020: build_polygon(plist + Front, n1, v1, line1, p->style, p->lp,
2021: -1, next_frag_temp, p->id, is_moved_or_split);
2022: }
2023: return Front;
2024: }
2025:
2026: /* HBB: these pieces of code are found repeatedly in in_front(), so
2027: * I put them into macros
2028: * Note: can't use the 'do {...} while (0)' method for
2029: * these: 'continue' wouldn't work any more.
2030: */
2031: #define PUT_P_IN_FRONT_TEST(new_tested) {\
2032: plist[Plast].next = p->next; \
2033: p->next = Test; \
2034: p->tested = new_tested; \
2035: if (Insert >= 0) \
2036: plist[Insert].next = P; \
2037: else \
2038: pfirst = P; \
2039: Insert = P; \
2040: P = Plast; \
2041: p = plist + P; \
2042: continue; \
2043: }
2044:
2045: #define SPLIT_TEST_BY_P {\
2046: long Back = split_polygon_by_plane (Test, pa, pb, pc, pd, 0); \
2047: if (Back >0) { \
2048: p = plist + P; \
2049: test = plist + Test; /* plist can change */ \
2050: plist[Back].next = p->next; \
2051: p->next = Back; \
2052: P = Back; \
2053: p = plist + P; \
2054: zmin = test->zmin; /* the new z-value */ \
2055: } else { \
2056: fprintf(stderr, "Failed to split test (%ld) by p (%ld)\n", Test, P); \
2057: graph_error("Error in hidden line removal: couldn't split..."); \
2058: } \
2059: continue; \
2060: }
2061:
2062: #define SPLIT_P_BY_TEST {\
2063: long Front = split_polygon_by_plane (P, ta, tb, tc, td, 1);\
2064: if (Front >0) {\
2065: p = plist + P;\
2066: test = plist + Test; /* plist can change */\
2067: plist[Front].next = Test;\
2068: if (Insert >= 0)\
2069: plist[Insert].next = Front;\
2070: else\
2071: pfirst = Front;\
2072: Insert = Front;\
2073: } else {\
2074: fprintf(stderr, "Failed to split p (%ld) by test(%ld), relations are %d, %d\n", P, Test, p_rel_tplane, t_rel_pplane);\
2075: print_polygon(test, "test");\
2076: print_polygon(p, "p");\
2077: fputc('\n', stderr);\
2078: }\
2079: continue; /* FIXME: should we continue nevertheless? */\
2080: }
2081:
2082:
2083: /* Is Test in front of the other polygons?
2084: * If not, polygons which are in front of test come between
2085: * Last and Test (I.e. to the 'front' of the plist)
2086: */
2087: static int in_front(Last, Test)
2088: long Last, Test;
2089: {
2090: struct Polygon GPHUGE *test = plist + Test, GPHUGE * p;
2091: long Insert, P, Plast;
2092: double zmin, /* minimum z-value of Test */
2093: ta, tb, tc, td, /* the plane of Test */
2094: pa, pb, pc, pd; /* the plane of a polygon */
2095: t_poly_plane_intersect p_rel_tplane, t_rel_pplane;
2096: int loop = (test->tested == is_in_loop);
2097:
2098: CHECK_POINTER(plist, test);
2099:
2100: /* Maybe this should only done at the end of this routine... */
2101: /* test->tested = is_tested; */
2102:
2103: Insert = Last;
2104:
2105: /* minimal z-value of Test */
2106: zmin = test->zmin;
2107:
2108: /* The plane of the polygon Test */
2109: get_plane(test, &ta, &tb, &tc, &td);
2110:
2111: /* Compare Test with the following polygons, which overlap in z value */
2112: for (Plast = Test, p = test;
2113: ((P = p->next) >= 0) && (((p = plist + P)->zmax > zmin) || (p->tested != 0));
2114: Plast = P) {
2115: CHECK_POINTER(plist, p);
2116:
2117: if (!xy_overlap(test, p))
2118: continue;
2119:
2120: if (p->zmax <= zmin)
2121: continue;
2122:
2123: p_rel_tplane = polygon_plane_intersection(p, ta, tb, tc, td);
2124: if ((p_rel_tplane == behind) || (p_rel_tplane == inside))
2125: continue;
2126:
2127: get_plane(p, &pa, &pb, &pc, &pd);
2128: t_rel_pplane = polygon_plane_intersection(test, pa, pb, pc, pd);
2129: if ((t_rel_pplane == infront) || (t_rel_pplane == inside))
2130: continue;
2131:
2132: if (!full_xy_overlap(test, p))
2133: continue;
2134:
2135: #if 1
2136: /* HBB 971115: try new approach developed directly from Foley et
2137: * al.'s original description */
2138: /* OK, at this point, a total of 16 cases is left to be handled,
2139: * as 4 variables are important, each with two possible values:
2140: * t_rel_pplane may be 'behind' or 'intersects', p_rel_tplane may
2141: * be 'infront' or 'intersects', 'test' may be (seem to be) part
2142: * of a loop or not ('loop'), and p may have been considered
2143: * already or not (p->tested =?= is_tested). */
2144: /* See if splitting wherever possible is a good idea: */
2145: if (p_rel_tplane == intersects) {
2146: p->tested = is_moved_or_split;
2147: SPLIT_P_BY_TEST;
2148: } else if (t_rel_pplane == intersects) {
2149: test->tested = is_moved_or_split;
2150: SPLIT_TEST_BY_P;
2151: } else {
1.1.1.3 ! ohara 2152: if (loop && (p->tested == is_in_loop)) {
! 2153: /* Ouch, seems like we're in trouble, really: no way to
! 2154: * split one of them, and we're in a loop, so we can't
! 2155: * move p to the front of the list, without risking an
! 2156: * endless loop. Well, let's just output the darn thing,
! 2157: * then, no matter what. :-( */
! 2158: #if DEBUG /* normally off */
1.1 maekawa 2159: fprintf(stderr, "\
2160: #Failed: In loop, without intersections.\n\
2161: #Relations are %d, %d\n",
2162: p_rel_tplane, t_rel_pplane);
2163: print_polygon(test, "test");
2164: print_polygon(p, "p");
1.1.1.3 ! ohara 2165: #endif
1.1 maekawa 2166: continue; /* Keep quiet, maybe no-one will notice (;-) */
2167: } else {
2168: PUT_P_IN_FRONT_TEST(is_in_loop);
2169: }
2170: }
2171: #else
2172: /* p obscures test (at least, this *might* be happening */
2173: if (loop) {
2174: /* if P isn't interesting for the loop, put P in front of Test */
2175: if ((p->tested != is_tested)
2176: || (p_rel_tplane == infront)
2177: || (t_rel_pplane == behind)) /* HBB 970325: was infront (!?) */
2178: PUT_P_IN_FRONT_TEST(is_moved_or_split);
2179:
2180: /* else, split either test or p */
2181: if (t_rel_pplane == intersects)
2182: SPLIT_TEST_BY_P;
2183: if (p_rel_tplane == intersects)
2184: SPLIT_P_BY_TEST;
2185:
2186: /* HBB: if we ever come through here, something went severely wrong */
2187: fprintf(stderr, "Failed: polygon %ld vs. %ld, relations are %d, %d\n", P, Test, p_rel_tplane, t_rel_pplane);
2188: print_polygon(test, "test");
2189: print_polygon(p, "p");
2190: fputc('\n', stderr);
2191: graph_error("Couldn't resolve a polygon overlapping pb. Go tell HBB...");
2192: }
2193: /* No loop: if it makes sense, put P in front of Test */
2194: if ((p->tested != is_tested)
2195: && ((t_rel_pplane == behind)
2196: || (p_rel_tplane == infront)))
2197: PUT_P_IN_FRONT_TEST(is_moved_or_split);
2198:
2199: /* If possible, split P */
2200: if ((p->tested != is_tested) || (p_rel_tplane == intersects))
2201: SPLIT_P_BY_TEST;
2202:
2203: /* if possible, split Test */
2204: if (t_rel_pplane == intersects)
2205: SPLIT_TEST_BY_P;
2206:
2207: /* else, we have a loop: mark P as loop and put it in front of Test */
2208: PUT_P_IN_FRONT_TEST(is_in_loop); /* -2: p is in a loop */
2209: #endif
2210: }
2211: if (Insert == Last)
2212: test->tested = is_tested;
2213: return (int) (Insert == Last);
2214: }
2215:
2216:
2217: /* Drawing the polygons */
2218:
2219: /* HBB 980303: new functions to handle Cross back-buffer (saves
2220: * gp_alloc()'s) */
2221:
2222: static GP_INLINE void init_Cross_store()
2223: {
2224: assert(!Cross_store && !last_Cross_store);
2225: last_Cross_store = CROSS_STORE_INCREASE;
2226: free_Cross_store = 0;
2227: Cross_store = (struct Cross *)
1.1.1.3 ! ohara 2228: gp_alloc(last_Cross_store * sizeof(struct Cross), "hidden cross store");
1.1 maekawa 2229: }
2230:
1.1.1.3 ! ohara 2231: static GP_INLINE unsigned int
! 2232: get_Cross_from_store()
1.1 maekawa 2233: {
2234: while (last_Cross_store <= free_Cross_store) {
2235: last_Cross_store += CROSS_STORE_INCREASE;
2236: Cross_store = (struct Cross *)
2237: gp_realloc(Cross_store,
2238: (unsigned long) last_Cross_store * sizeof(struct Cross),
2239: "hidden cross store");
2240: }
1.1.1.3 ! ohara 2241: return free_Cross_store++;
1.1 maekawa 2242: }
2243:
2244: static GP_INLINE TBOOLEAN
2245: hl_buffer_set(xv, yv)
2246: int xv, yv;
2247: {
1.1.1.3 ! ohara 2248: unsigned int c;
! 2249:
1.1 maekawa 2250: /*HBB 961110: lclint wanted this: */
2251: assert(hl_buffer != 0);
1.1.1.3 ! ohara 2252: for (c = hl_buffer[xv];
! 2253: c < last_Cross_store;
! 2254: c = Cross_store[c].next)
! 2255: if (Cross_store[c].a <= yv && Cross_store[c].b >= yv) {
1.1 maekawa 2256: return TRUE;
2257: }
2258: return FALSE;
2259: }
2260:
2261: /* HBB 961201: new var's, to speed up free()ing hl_buffer later */
2262: static int hl_buff_xmin, hl_buff_xmax;
2263:
2264: /* HBB 961124: new routine. All this occured twice in
2265: * draw_clip_line_buffer */
2266: /* Store a line crossing the x interval around xv between y = ya and
2267: * y = yb in the hl_buffer */
2268: static GP_INLINE void update_hl_buffer_column(xv, ya, yb)
1.1.1.3 ! ohara 2269: int xv, ya, yb;
1.1 maekawa 2270: {
1.1.1.3 ! ohara 2271: unsigned int cross, cross2;
! 2272: TBOOLEAN still_in_hl_buffer = TRUE;
1.1 maekawa 2273:
2274: /* First, ensure that ya <= yb */
2275: if (ya > yb) {
2276: int y_temp = yb;
2277: yb = ya;
2278: ya = y_temp;
2279: }
2280: /* loop over all previous crossings at this x-value */
1.1.1.3 ! ohara 2281: for (cross = hl_buffer[xv], still_in_hl_buffer = TRUE;
! 2282: 1;
! 2283: cross = Cross_store[cross].next, still_in_hl_buffer = FALSE
! 2284: ) {
! 2285: if (cross > last_Cross_store) {
1.1 maekawa 2286: /* first or new highest crossing at this x-value */
2287:
2288: /* HBB 980303: new method to allocate Cross structures */
1.1.1.3 ! ohara 2289: cross = get_Cross_from_store();
! 2290: if (still_in_hl_buffer)
! 2291: hl_buffer[xv] = cross;
! 2292: Cross_store[cross].a = ya;
! 2293: Cross_store[cross].b = yb;
! 2294: Cross_store[cross].next = (unsigned int) -1;
1.1 maekawa 2295: /* HBB 961201: keep track of x-range of hl_buffer, to
2296: * speedup free()ing it */
2297: if (xv < hl_buff_xmin)
2298: hl_buff_xmin = xv;
2299: if (xv > hl_buff_xmax)
2300: hl_buff_xmax = xv;
2301: break;
2302: }
1.1.1.3 ! ohara 2303: if (yb < Cross_store[cross].a - 1) {
1.1 maekawa 2304: /* crossing below 'cross', create new entry before 'cross' */
1.1.1.3 ! ohara 2305: cross2 = cross;
1.1 maekawa 2306: /* HBB 980303: new method to allocate Cross structures */
1.1.1.3 ! ohara 2307: cross = get_Cross_from_store();
! 2308: if (still_in_hl_buffer)
! 2309: hl_buffer[xv] = cross;
! 2310: Cross_store[cross].a = ya;
! 2311: Cross_store[cross].b = yb;
! 2312: Cross_store[cross].next = cross2;
1.1 maekawa 2313: break;
1.1.1.3 ! ohara 2314: } else if (ya <= Cross_store[cross].b + 1) {
1.1 maekawa 2315: /* crossing overlaps or covers 'cross' */
1.1.1.3 ! ohara 2316: if (ya < Cross_store[cross].a)
! 2317: Cross_store[cross].a = ya;
! 2318: if (yb > Cross_store[cross].b) {
! 2319: if (Cross_store[cross].next < last_Cross_store
! 2320: && Cross_store[Cross_store[cross].next].a <= yb
! 2321: ) {
1.1 maekawa 2322: /* crossing spans all the way up to 'cross->next' so
2323: * unite them */
1.1.1.3 ! ohara 2324: cross2 = Cross_store[cross].next;
! 2325: Cross_store[cross].b = Cross_store[cross2].b;
! 2326: Cross_store[cross].next = Cross_store[cross2].next;
1.1 maekawa 2327: } else
1.1.1.3 ! ohara 2328: Cross_store[cross].b = yb;
1.1 maekawa 2329: }
2330: break;
2331: }
2332: }
2333: return;
2334: }
2335:
2336:
2337: static void draw_clip_line_buffer(x1, y1, x2, y2)
2338: int x1, y1, x2, y2;
2339: /* Draw a line in the hl_buffer */
2340: {
2341: register int xv, yv, errx, erry, err;
2342: register int dy, nstep;
2343: register int ya;
2344: int i;
2345:
2346: if (!clip_line(&x1, &y1, &x2, &y2)) {
2347: /*printf("dcl_buffer: clipped away!\n"); */
2348: return;
2349: }
2350: if (x1 > x2) {
2351: errx = XREDUCE(x1) - XREDUCE(x2);
2352: erry = YREDUCE(y1) - YREDUCE(y2);
2353: xv = XREDUCE(x2) - XREDUCE(xleft);
2354: yv = YREDUCE(y2) - YREDUCE(ybot);
2355: } else {
2356: errx = XREDUCE(x2) - XREDUCE(x1);
2357: erry = YREDUCE(y2) - YREDUCE(y1);
2358: xv = XREDUCE(x1) - XREDUCE(xleft);
2359: yv = YREDUCE(y1) - YREDUCE(ybot);
2360: }
2361: if (erry > 0)
2362: dy = 1;
2363: else {
2364: dy = -1;
2365: erry = -erry;
2366: }
2367: nstep = errx + erry;
2368: err = -errx + erry;
2369: errx <<= 1;
2370: erry <<= 1;
2371: ya = yv;
2372:
2373: for (i = 0; i < nstep; i++) {
2374: if (err < 0) {
2375: update_hl_buffer_column(xv, ya, yv);
2376: xv++;
2377: ya = yv;
2378: err += erry;
2379: } else {
2380: yv += dy;
2381: err -= errx;
2382: }
2383: }
2384: (void) update_hl_buffer_column(xv, ya, yv);
2385: return;
2386: }
2387:
2388:
2389: /* HBB 961124: improve similarity of this routine with
2390: * draw_clip_line_buffer ()
2391: *
2392: * HBB 961124: changed from 'virtual' to 'do_draw', for clarity (this
2393: * also affects the routines calling this one, so beware!
2394: *
2395: * HBB 961124: introduced checking code, to search for the 'holes in
2396: * the surface' bug
2397: *
2398: * Draw a line into the bitmap (**cpnt), and optionally also to the
2399: * terminal
2400: */
2401: static void draw_clip_line_update(x1, y1, x2, y2, do_draw)
2402: int x1, y1, x2, y2;
2403: TBOOLEAN do_draw;
2404: {
2405: /* HBB 961110: made 'flag' a boolean variable, which needs some
2406: * other changes below as well
2407: *
2408: * HBB 970508: renamed 'flag' to 'is_drawn' (reverting its meaning).
2409: * Should be clearer now
2410: */
2411: TBOOLEAN is_drawn;
2412: register struct termentry *t = term;
2413: register int xv, yv, errx, erry, err;
2414: register int xvr, yvr;
2415: int xve, yve;
2416: register int dy, nstep = 0, dyr;
2417: int i;
2418: if (!clip_line(&x1, &y1, &x2, &y2)) {
2419: /*printf("dcl_update: clipped away!\n"); */
2420: return;
2421: }
2422: if (x1 > x2) {
2423: xvr = x2;
2424: yvr = y2;
2425: xve = x1;
2426: yve = y1;
2427: } else {
2428: xvr = x1;
2429: yvr = y1;
2430: xve = x2;
2431: yve = y2;
2432: }
2433: errx = XREDUCE(xve) - XREDUCE(xvr);
2434: erry = YREDUCE(yve) - YREDUCE(yvr);
2435: if (erry > 0)
2436: dy = 1;
2437: else {
2438: dy = -1;
2439: erry = -erry;
2440: }
2441: dyr = dy * yfact;
2442: nstep = errx + erry;
2443: err = -errx + erry;
2444: errx <<= 1;
2445: erry <<= 1;
2446: xv = XREDUCE(xvr) - XREDUCE(xleft);
2447: yv = YREDUCE(yvr) - YREDUCE(ybot);
2448: (*t->move) ((unsigned int) xvr, (unsigned int) yvr);
2449:
2450: is_drawn = (IS_UNSET(xv, yv) && (do_draw || hl_buffer_set(xv, yv)));
2451:
2452: /* HBB 961110: lclint wanted these: */
2453: assert(ymin_hl != 0);
2454: assert(ymax_hl != 0);
2455: /* Check first point in hl-buffer */
2456: if (xv < xmin_hl)
2457: xmin_hl = xv;
2458: if (xv > xmax_hl)
2459: xmax_hl = xv;
2460: if (yv < ymin_hl[xv])
2461: ymin_hl[xv] = yv;
2462: if (yv > ymax_hl[xv])
2463: ymax_hl[xv] = yv;
2464: for (i = 0; i < nstep; i++) {
2465: /* 970722: new variables */
2466: unsigned int xvr_temp = xvr, yvr_temp = yvr;
2467: if (err < 0) {
2468: xv++;
2469: xvr += xfact;
2470: err += erry;
2471: } else {
2472: yv += dy;
2473: yvr += dyr;
2474: err -= errx;
2475: }
2476: if (IS_UNSET(xv, yv) && (do_draw || hl_buffer_set(xv, yv))) {
2477: if (!is_drawn) {
2478: /* 970722: If this line was meant to be drawn, originally,
2479: * and it was just the bitmap that stopped it, then draw
2480: * it a bit longer (i.e.: start one pixel earlier
2481: */
2482: if (do_draw)
2483: (*t->move) ((unsigned int) xvr_temp, (unsigned int) yvr_temp);
2484: else
2485: (*t->move) ((unsigned int) xvr, (unsigned int) yvr);
2486: is_drawn = TRUE;
2487: }
2488: } else {
2489: if (is_drawn) {
2490: /* 970722: If this line is only drawn because hl_buffer_set()
2491: * was true, then don't extend to the new position (where it
2492: * isn't true any more). Draw the line one pixel shorter,
2493: * instead:
2494: */
2495: if (do_draw)
2496: (*t->vector) ((unsigned int) xvr, (unsigned int) yvr);
2497: else {
2498: (*t->vector) ((unsigned int) xvr_temp, (unsigned int) yvr_temp);
2499: (*t->move) ((unsigned int) xvr, (unsigned int) yvr);
2500: }
2501: is_drawn = FALSE;
2502: }
2503: }
2504: if (xv < xmin_hl)
2505: xmin_hl = xv;
2506: if (xv > xmax_hl)
2507: xmax_hl = xv;
2508: if (yv < ymin_hl[xv])
2509: ymin_hl[xv] = yv;
2510: if (yv > ymax_hl[xv])
2511: ymax_hl[xv] = yv;
2512: }
2513: if (is_drawn)
2514: (*t->vector) ((unsigned int) xvr, (unsigned int) yvr);
2515: return;
2516: }
2517:
2518: #define DRAW_VERTEX(v, x, y) do { \
2519: if ((v)->style >= 0 && \
2520: !clip_point(x,y) && \
2521: IS_UNSET(XREDUCE(x)-XREDUCE(xleft),YREDUCE(y)-YREDUCE(ybot))) \
2522: (*t->point)(x,y, v->style); \
2523: (v)->style = -1; \
2524: } while (0)
2525:
2526: /* Two routines to emulate move/vector sequence using line drawing routine. */
2527: static unsigned int move_pos_x, move_pos_y;
2528:
2529: void clip_move(x, y)
2530: unsigned int x, y;
2531: {
2532: move_pos_x = x;
2533: move_pos_y = y;
2534: }
2535:
2536: void clip_vector(x, y)
2537: unsigned int x, y;
2538: {
2539: draw_clip_line(move_pos_x, move_pos_y, x, y);
2540: move_pos_x = x;
2541: move_pos_y = y;
2542: }
2543:
2544: static GP_INLINE void clip_vector_h(x, y)
2545: int x, y;
2546: /* Draw a line on terminal and update bitmap */
2547: {
2548: draw_clip_line_update(move_pos_x, move_pos_y, x, y, TRUE);
2549: move_pos_x = x;
2550: move_pos_y = y;
2551: }
2552:
2553:
2554: static GP_INLINE void clip_vector_virtual(x, y)
2555: int x, y;
2556: /* update bitmap, do not really draw the line */
2557: {
2558: draw_clip_line_update(move_pos_x, move_pos_y, x, y, FALSE);
2559: move_pos_x = x;
2560: move_pos_y = y;
2561: }
2562:
2563: static GP_INLINE void clip_vector_buffer(x, y)
2564: /* draw a line in the hl_buffer */
2565: int x, y;
2566: {
2567: draw_clip_line_buffer(move_pos_x, move_pos_y, x, y);
2568: move_pos_x = x;
2569: move_pos_y = y;
2570: }
2571:
2572: static void draw(p)
2573: struct Polygon GPHUGE *p;
2574: {
2575: struct Vertex GPHUGE *v;
2576: struct Polygon GPHUGE *q;
2577: long Q;
2578: int i;
2579: int x, y; /* point in terminal coordinates */
2580: register struct termentry *t = term;
2581: t_pnt mask1, mask2;
2582: long int indx1, indx2, k;
2583: tp_pnt cpnt;
2584:
2585: xmin_hl = HL_EXTENT_X_MAX; /* HBB 961124: parametrized this value */
2586: xmax_hl = 0;
2587:
2588: /* HBB 961201: store initial values for range of hl_buffer: */
2589: hl_buff_xmin = XREDUCE(xright) - XREDUCE(xleft);
2590: hl_buff_xmax = 0;
2591:
2592: /* Write the lines of all polygons with the same id as p in the hl_buffer */
2593: /* HBB 961201: use next_frag pointers to loop over fragments: */
2594: for (q = p; (Q = q->next_frag) >= 0 && (q = plist + Q) != p;) {
2595: if (q->id != p->id)
2596: continue;
2597:
2598: /* draw the lines of q into hl_buffer: */
2599: v = vlist + q->vertex[0];
2600: TERMCOORD(v, x, y);
2601: clip_move(x, y);
2602: for (i = 1; i < q->n; i++) {
2603: v = vlist + q->vertex[i];
2604: TERMCOORD(v, x, y);
2605: if (q->line & (1L << (i - 1)))
2606: clip_vector_buffer(x, y);
2607: else
2608: clip_move(x, y);
2609: }
2610: if (q->line & (1L << (i - 1))) {
2611: v = vlist + q->vertex[0];
2612: TERMCOORD(v, x, y);
2613: clip_vector_buffer(x, y);
2614: }
2615: }
2616:
2617:
2618: /* first, set the line and point styles: */
2619: {
2620: struct lp_style_type lp;
2621:
2622: lp = *(p->lp);
2623: lp.l_type = p->style;
2624: term_apply_lp_properties(&(lp));
2625: }
2626:
2627: /*print_polygon (p, "drawing"); */
2628:
2629: /* draw the lines of p */
2630: v = vlist + p->vertex[0];
2631: TERMCOORD(v, x, y);
2632: clip_move(x, y);
2633: DRAW_VERTEX(v, x, y);
2634: for (i = 1; i < p->n; i++) {
2635: v = vlist + p->vertex[i];
2636: TERMCOORD(v, x, y);
2637: if (p->line & (1L << (i - 1)))
2638: clip_vector_h(x, y);
2639: else
2640: clip_vector_virtual(x, y);
2641: DRAW_VERTEX(v, x, y);
2642: }
2643: TERMCOORD(vlist + p->vertex[0], x, y);
2644: if (p->line & (1L << (i - 1)))
2645: clip_vector_h(x, y);
2646: else
2647: clip_vector_virtual(x, y);
2648:
2649:
2650: /* reset the hl_buffer */
2651: /*HBB 961110: lclint wanted this: */
2652: assert(hl_buffer);
2653: for (i = hl_buff_xmin; i <= hl_buff_xmax; i++) {
2654: /* HBB 980303: one part was removed here. It isn't needed any more,
2655: * with the global store for Cross structs. */
1.1.1.3 ! ohara 2656: hl_buffer[i] = (unsigned int) -1;
1.1 maekawa 2657: }
2658: /* HBB 980303: instead, set back the free pointer of the Cross store: */
2659: free_Cross_store = 0;
2660:
2661: /* now mark the area as being filled in the bitmap. */
2662: /* HBB 971115: Yes, I do know that xmin_hl is unsigned, and the
2663: * first test is thus useless. But I'd like to keep it anyway ;-) */
2664: if (xmin_hl < 0 || xmax_hl > XREDUCE(xright) - XREDUCE(xleft))
2665: graph_error("Logic error #3 in hidden line");
2666: /* HBB 961110: lclint wanted these: */
2667: assert(ymin_hl != 0);
2668: assert(ymax_hl != 0);
2669: assert(pnt != 0);
2670: if (xmin_hl < xmax_hl)
2671: for (i = xmin_hl; i <= xmax_hl; i++) {
2672: if (ymin_hl[i] == HL_EXTENT_Y_MAX)
2673: graph_error("Logic error #2 in hidden line");
2674: if (pnt[i] == 0) {
1.1.1.3 ! ohara 2675: pnt[i] = (t_pnt *) gp_alloc(y_malloc, "hidden ymalloc");
1.1 maekawa 2676: memset(pnt[i], 0, (size_t) y_malloc);
2677: }
2678: if (ymin_hl[i] < 0 || ymax_hl[i] > YREDUCE(ytop) - YREDUCE(ybot))
2679: graph_error("Logic error #1 in hidden line");
2680: /* HBB 970508: this shift was wordsize dependent
2681: * I think I fixed that
2682: */
2683: indx1 = ymin_hl[i] / PNT_BITS;
2684: indx2 = ymax_hl[i] / PNT_BITS;
2685: mask1 = PNT_MAX << (((unsigned) ymin_hl[i]) % PNT_BITS);
2686: mask2 = PNT_MAX >> ((~((unsigned) ymax_hl[i])) % PNT_BITS);
2687: cpnt = pnt[i] + indx1;
2688: if (indx1 == indx2)
2689: *cpnt |= (mask1 & mask2);
2690: else {
2691: *cpnt++ |= mask1;
2692: for (k = indx1 + 1; k < indx2; k++)
2693: *cpnt++ = PNT_MAX;
2694: *cpnt |= mask2;
2695: }
2696: ymin_hl[i] = HL_EXTENT_Y_MAX;
2697: ymax_hl[i] = 0;
2698: }
2699: }
2700:
2701:
2702: void plot3d_hidden(plots, pcount)
2703: struct surface_points *plots;
2704: int pcount;
2705: {
2706: long Last, This;
2707: long i;
2708:
2709: #if defined(DOS16) || defined(WIN16)
2710: /* HBB 980309: Ensure that Polygon Structs exactly fit a 64K segment. The
2711: * problem this prevents is that even with 'huge pointers', a single
2712: * struct may not cross a 64K boundary: it will wrap around to the
2713: * beginning of that 64K segment. Someone ought to complain about
2714: * this nuisance, somewhere... :-( */
2715: assert(0 == (0x1 << 16) % (sizeof(struct Polygon)));
2716: #endif
2717:
2718: /* Initialize global variables */
2719: y_malloc = (2 + (YREDUCE(ytop) >> 4) - (YREDUCE(ybot) >> 4)) * sizeof(t_pnt);
2720: /* ymin_hl, ymax_hl: */
2721: i = sizeof(t_hl_extent_y) * (XREDUCE(xright) - XREDUCE(xleft) + 1);
1.1.1.3 ! ohara 2722: ymin_hl = (t_hl_extent_y *) gp_alloc(i, "hidden ymin_hl");
! 2723: ymax_hl = (t_hl_extent_y *) gp_alloc(i, "hidden ymax_hl");
1.1 maekawa 2724: for (i = (XREDUCE(xright) - XREDUCE(xleft)); i >= 0; i--) {
2725: ymin_hl[i] = HL_EXTENT_Y_MAX;
2726: ymax_hl[i] = 0;
2727: }
2728: /* hl_buffer: */
2729: /* HBB 980303 new: initialize the global store for Cross structs: */
2730: init_Cross_store();
2731: i = XREDUCE(xright) - XREDUCE(xleft) + 1;
1.1.1.3 ! ohara 2732: hl_buffer = (unsigned int GPHUGE *)
! 2733: gp_alloc(i * sizeof(unsigned int), "hidden hl_buffer");
1.1 maekawa 2734: while (--i >= 0)
1.1.1.3 ! ohara 2735: hl_buffer[i] = (unsigned int) -1;
1.1 maekawa 2736:
2737: init_polygons(plots, pcount);
2738:
2739: /* HBB 970326: if no polygons survived the cutting away of undefined
2740: * and/or outranged vertices, bail out with a warning message.
2741: * Without this, sort_by_zmax gets a SegFault */
2742: if (!pfree) {
2743: /* HBB 980701: new code to deallocate all the structures allocated up
2744: * to this point. Should fix the core dump reported by
2745: * Stefan A. Deutscher today */
2746: if (ymin_hl) {
2747: free(ymin_hl);
2748: ymin_hl = 0;
2749: }
2750: if (ymax_hl) {
2751: free(ymax_hl);
2752: ymax_hl = 0;
2753: }
2754: if (hl_buffer) {
2755: free(hl_buffer);
2756: hl_buffer = 0;
2757: }
2758: if (Cross_store) {
2759: free(Cross_store);
2760: Cross_store = 0;
2761: last_Cross_store = 0;
2762: }
2763: graph_error("*All* polygons undefined or out of range, thus no plot.");
2764: }
2765: sort_by_zmax();
2766:
2767: /* sort the polygons and draw them in one loop */
2768: Last = -1L;
2769: This = pfirst;
2770: /* Search first polygon, that can be drawn */
2771: while (Last == -1L && This >= 0L) {
2772: This = pfirst;
2773: if (obscured(plist + This)) {
2774: Last = This;
2775: continue;
2776: }
2777: if (plist[This].tested != is_tested && !in_front(Last, This))
2778: continue;
2779: draw(plist + This);
2780: Last = This;
2781: }
2782: /* Draw the other polygons */
2783: for (This = plist[Last].next; This >= 0L; This = plist[Last].next) {
2784: if (obscured(plist + This)) {
2785: Last = This;
2786: continue;
2787: }
2788: if (plist[This].tested != is_tested && !in_front(Last, This))
2789: continue;
2790: draw(plist + This);
2791: Last = This;
2792: }
2793:
2794: /* Free memory */
2795: if (plist) {
2796: for (This = 0L; This < pfree; This++)
2797: free(plist[This].vertex);
2798: free(plist);
2799: plist = 0;
2800: }
2801: if (vlist) {
2802: free(vlist);
2803: vlist = 0;
2804: }
2805: if (ymin_hl) {
2806: free(ymin_hl);
2807: ymin_hl = 0;
2808: }
2809: if (ymax_hl) {
2810: free(ymax_hl);
2811: ymax_hl = 0;
2812: }
2813: if (hl_buffer) {
2814: free(hl_buffer);
2815: hl_buffer = 0;
2816: }
2817: if (Cross_store) {
2818: free(Cross_store);
2819: Cross_store = 0;
2820: last_Cross_store = 0;
2821: }
2822: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to hidden3d.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib / gnuplot