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