forked from gnuplot/gnuplot-old
/
hidden3d.c
2826 lines (2559 loc) · 85.6 KB
/
hidden3d.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
#ifndef lint
static char *RCSid = "$Id: hidden3d.c,v 1.1.1.4 1998/06/23 12:38:00 lhecking Exp $";
#endif
/* GNUPLOT - hidden3d.c */
/*[
* Copyright 1986 - 1993, 1998 Thomas Williams, Colin Kelley
*
* Permission to use, copy, and distribute this software and its
* documentation for any purpose with or without fee is hereby granted,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation.
*
* Permission to modify the software is granted, but not the right to
* distribute the complete modified source code. Modifications are to
* be distributed as patches to the released version. Permission to
* distribute binaries produced by compiling modified sources is granted,
* provided you
* 1. distribute the corresponding source modifications from the
* released version in the form of a patch file along with the binaries,
* 2. add special version identification to distinguish your version
* in addition to the base release version number,
* 3. provide your name and address as the primary contact for the
* support of your modified version, and
* 4. retain our contact information in regard to use of the base
* software.
* Permission to distribute the released version of the source code along
* with corresponding source modifications in the form of a patch file is
* granted with same provisions 2 through 4 for binary distributions.
*
* This software is provided "as is" without express or implied warranty
* to the extent permitted by applicable law.
]*/
/*
* 19 September 1992 Lawrence Crowl (crowl@cs.orst.edu)
* Added user-specified bases for log scaling.
*
* 'someone' contributed a complete rewrite of the hidden line
* stuff, for about beta 173 or so, called 'newhide.tgz'
*
* 1995-1997 Hans-Bernhard Br"oker (Broeker@physik.rwth-aachen.de)
* Speedup, cleanup and several modification to integrate
* 'newhide' with 3.6 betas ~188 (start of work) up to 273.
* As of beta 290, this is 'officially' in gnuplot.
*
*/
#include "plot.h"
#include "setshow.h"
/* TODO (HBB's notes, just in case you're interested):
* + fix all the problems I annotated by a 'FIXME' comment
* + Find out which value EPSILON should have, and why
* + Ask gnuplot-beta for a suitable way of concentrating
* all those 'VERYSMALL', 'EPSILON', and other numbers
* into one, consistent scheme, possibly based on
* <float.h>. E.g., I'd say that for most applications,
* the best 'epsilon' is either DBL_EPS or its square root.
* + redo all the profiling, esp. to find out if TEST_GRIDCHECK=1
* actually gains some speed, and if it is worth the memory
* spent to store the bit masks
* -> seems not improve speed at all, at least for my standard
* test case (mandd.gpl) it even slows it down by ~ 10%
* + Evaluate the speed/memory comparison for storing vertex
* indices instead of (double) floating point constants
* to store {x|y}{min|max}
* + remove those of my comments that are now pointless
* + indent all that code
* + try to really understand that 'hl_buffer' stuff...
* + get rid of hardcoded things like sizeof(short)==4,
* those 0x7fff terms and all that.
* + restructure the hl_buffer storing method to make it more efficient
* + Try to cut the speed decrease of this code rel. to the old hidden
* hidden line removal. (For 'mandd.gpl', it costs an overall
* factor of 9 compared with my older versions of gnuplot!)
*/
/*************************/
/* Configuration section */
/*************************/
/* HBB: if this module is compiled with TEST_GRIDCHECK=1 defined,
* it will store the information about {x|y}{min|max} in an
* other (additional!) form: a bit mask, with each bit representing
* one horizontal or vertical strip of the screen. The bits
* for strips a polygon spans are set to one. This allows to
* test for xy_overlap simply by comparing bit patterns.
*/
#ifndef TEST_GRIDCHECK
#define TEST_GRIDCHECK 0
#endif
/* HBB 961124; If you don't want the color-distinction between the
* 'top' and 'bottom' sides of the surface, like I do, then just compile
* with -DBACKSIDE_LINETYPE_OFFSET=0. */
#ifndef BACKSIDE_LINETYPE_OFFSET
#define BACKSIDE_LINETYPE_OFFSET 1
#endif
/* HBB 961127: defining FOUR_TRIANGLES=1 will separate each quadrangle
* of data points into *four* triangles, by introducing an additional
* point at the mean of the four corners. Status: experimental
*/
#ifndef FOUR_TRIANGLES
#define FOUR_TRIANGLES 0
#endif
/* HBB 970322: I removed the SENTINEL flag and its implementation
* completely. Its speed improvement wasn't that great, and it never
* fully worked anyway, so that shouldn't make much of a difference at
* all. */
/* HBB 961212: this #define lets you choose if the diagonals that
* divide each original quadrangle in two triangles will be drawn
* visible or not: do draw them, define it to be 7L, otherwise let be
* 3L (for the FOUR_TRIANGLES method, the values are 7L and 1L) */
/* drd : default to 3, for back-compatibility with 3.5 */
#ifndef TRIANGLE_LINESDRAWN_PATTERN
#define TRIANGLE_LINESDRAWN_PATTERN 3L
#endif
/* HBB 970131: with HANDLE_UNDEFINED_POINTS=1, let's try to handle
* UNDEFINED data points in the input we're given by the rest of
* gnuplot. We do that by marking these points by giving them z=-2
* (which normally never happens), and then refusing to build any
* polygon if one of its vertices has this mark. Thus, there's now a
* hole in the generated surface. */
/* HBB 970322: some of this code is now hardwired (in
* PREPARE_POLYGON), so HANDLE_UNDEFINED_POINTS=0 might have stopped
* to be a useful setting. I doubt anyone will miss it, anyway. */
/* drd : 2 means undefined only. 1 means outrange treated as undefined */
#ifndef HANDLE_UNDEFINED_POINTS
#define HANDLE_UNDEFINED_POINTS 1
#endif
/* Symbolic value for 'do not handle Undefined Points specially' */
#define UNHANDLED (UNDEFINED+1)
/* HBB 970322: If both subtriangles of a quad were cancelled, try if
* using the other diagonal is better. This only makes a difference if
* exactly one vertex of the quad is unusable, and that one is on the
* first tried diagonal. In such a case, the border of the hole in the
* surface will be less rough than with the previous method. To
* disable this, #define SHOW_ALTERNATIVE_DIAGONAL as 0 */
#ifndef SHOW_ALTERNATIVE_DIAGONAL
#define SHOW_ALTERNATIVE_DIAGONAL 1
#endif
/* HBB 9790522: If the two triangles in a quad are both drawn, and
* they show different sides to the user (the quad is 'bent over'),
* then it often looks more sensible to draw the diagonal visibly to
* avoid other parts of the scene being obscured by what the user
* can't see. To disable, #define HANDLE_BENTOVER_QUADRANGLES 0 */
#ifndef HANDLE_BENTOVER_QUADRANGLES
#define HANDLE_BENTOVER_QUADRANGLES 1
#endif
/* HBB 970618: The code of split_polygon_by_plane used to make a
* separate decision about what should happen to points that are 'in'
* the splitting plane (within EPSILON accuracy, i.e.), based on the
* orientation of the splitting plane. I had disabled that code for I
* assumed it might be the cause of some of the buggyness. I'm not yet
* fully convinced on wether that assumption holds or not, so it's now
* choosable. OLD_SPLIT_PLANE==1 will enable it. Some older comments
* from the source:*/
/* HBB 970325: re-inserted this from older versions. Finally, someone
* came up with a test case where it is actually needed :-( */
/* HBB 970427: seems to have been an incorrect analysis of that error.
* the problematic plot works without this as well. */
#ifndef OLD_SPLIT_INPLANE
#define OLD_SPLIT_INPLANE 1
#endif
/* HBB 970618: this way, new edges introduced by splitting a polygon
* by the plane of another one will be made visible. Not too useful on
* production output, but can help in debugging. */
#ifndef SHOW_SPLITTING_EDGES
#define SHOW_SPLITTING_EDGES 0
#endif
/********************************/
/* END of configuration section */
/********************************/
/* Variables to hold configurable values. This is meant to prepare for
* making these settable by the user via 'set hidden [option]...' */
int hiddenBacksideLinetypeOffset = BACKSIDE_LINETYPE_OFFSET;
long hiddenTriangleLinesdrawnPattern = TRIANGLE_LINESDRAWN_PATTERN;
int hiddenHandleUndefinedPoints = HANDLE_UNDEFINED_POINTS;
int hiddenShowAlternativeDiagonal = SHOW_ALTERNATIVE_DIAGONAL;
int hiddenHandleBentoverQuadrangles = HANDLE_BENTOVER_QUADRANGLES;
/* The functions to map from user 3D space into normalized -1..1 */
#define map_x3d(x) ((x-min_array[FIRST_X_AXIS])*xscale3d-1.0)
#define map_y3d(y) ((y-min_array[FIRST_Y_AXIS])*yscale3d-1.0)
#define map_z3d(z) ((z-base_z)*zscale3d-1.0)
extern int suppressMove;
extern int xright, xleft, ybot, ytop;
extern int xmiddle, ymiddle, xscaler, yscaler;
extern double min_array[], max_array[];
extern int auto_array[], log_array[];
extern double base_array[], log_base_array[];
extern double xscale3d, yscale3d, zscale3d;
extern double base_z;
extern int hidden_no_update, hidden_active;
extern int hidden_line_type_above, hidden_line_type_below;
extern double trans_mat[4][4];
#ifdef HAVE_CPP_STRINGIFY
/* ANSI preprocessor concatenation */
# define CONCAT(x,y) x##y
# define CONCAT3(x,y,z) x##y##z
#else
/* K&R preprocessor concatenation */
# define CONCAT(x,y) x/**/y
# define CONCAT3(x,y,z) x/**/y/**/z
#endif
/* Bitmap of the screen. The array for each x value is malloc-ed as needed */
/* HBB 961111: started parametrisation of type t_pnt, to prepare change from
* short to normal ints in **pnt. The other changes aren't always annotated,
* so watch out! */
typedef unsigned short int t_pnt;
#define PNT_BITS (CHAR_BIT*sizeof(t_pnt))
#define PNT_MAX USHRT_MAX /* caution! ANSI-dependant ! ? */
typedef t_pnt *tp_pnt;
static tp_pnt *pnt;
/* Testroutine for the bitmap */
/* HBB 961110: fixed slight problem indicated by lclint:
* calling IS_UNSET with pnt==0 (possible?) */
/* HBB 961111: changed for new t_pnt, let compiler take care of optimisation
* `%' -> `&' */
/* HBB 961124: switched semantics: as this was *always* called as !IS_SET(),
* it's better to check for *unset* bits right away: */
#define IS_UNSET(X,Y) ((!pnt || pnt[X]==0) ? 1 : !(((pnt[X])[(Y)/PNT_BITS] >> ((Y)%PNT_BITS)) & 0x01))
/* Amount of space we need for one vertical row of bitmap,
and byte offset of first used element */
static unsigned long y_malloc;
/* These numbers are chosen as dividers into the bitmap. */
static int xfact, yfact;
#define XREDUCE(X) ((X)/xfact)
#define YREDUCE(Y) ((Y)/yfact)
/* These variables are only used for drawing the individual polygons
that make up the 3d figure. After each polygon is drawn, the
information is copied to the bitmap: xmin_hl, ymin_hl are used to
keep track of the range of x values. The arrays ymin_hl[],
ymax_hl[] are used to keep track of the minimum and maximum y
values used for each X value. */
/* HBB 961124: new macro, to avoid a wordsize-depence */
#define HL_EXTENT_X_MAX UINT_MAX /* caution! ANSI-only !? */
static unsigned int xmin_hl, xmax_hl;
/* HBB: parametrized type of hl_buffer elements, to allow easier
changing later on: */
#define HL_EXTENT_Y_MAX SHRT_MAX /* caution! ANSI-only !? */
typedef short int t_hl_extent_y;
static t_hl_extent_y *ymin_hl, *ymax_hl;
/* hl_buffer is a buffer which is needed to draw polygons with very small
angles correct:
One polygon may be split during the sorting algorithmus into
several polygons. Before drawing a part of a polygon, I save in
this buffer all lines of the polygon, which will not yet be drawn.
If then the actual part draws a virtual line (a invisible line,
which splits the polygon into 2 parts), it draws the line visible
in those points, which are set in the buffer.
The layout of the buffer:
hl_buffer[i] stands for the i'th column of the bitmap.
Each column is splitted into pairs of points (a,b).
Each pair describes a cross of one line with the column. */
struct Cross {
int a, b;
struct Cross GPHUGE *next;
};
static struct Cross GPHUGE * GPHUGE *hl_buffer;
/* HBB 980303: added a global array of Cross structures, to save lots
* of gp_alloc() calls (3 millions in a run through all.dem!) */
#define CROSS_STORE_INCREASE 500 /* number of Cross'es to alloc at a time */
static struct Cross *Cross_store = 0;
static int last_Cross_store=0, free_Cross_store = 0;
struct Vertex {
coordval x, y, z;
int style;
};
/* HBB 971114: two new macros, to properly hide the machinery that
*implements flagging of vertices as 'undefined' (or 'out of range',
*handled equally). Thanks to Lars Hecking for pointing this out */
#define FLAG_VERTEX_AS_UNDEFINED(v) \
do { (v).z = -2.0; } while (0)
#define VERTEX_IS_UNDEFINED(v) ((v).z == -2.0)
/* These values serve as flags to detect loops of polygons obscuring
* each other in in_front() */
typedef enum {
is_untested = 0, is_tested, is_in_loop, is_moved_or_split
} t_poly_tested;
/* Strings for printing out values of type t_poly_tested: */
static const char *string_poly_tested[] = {
"is_untested",
"is_tested",
"is_in_loop",
"is_moved_or_split"
};
struct Polygon {
int n; /* amount of vertices */
long *vertex; /* The vertices (indices on vlist) */
long line; /* i'th bit shows, if the i'th line should be drawn */
coordval xmin, xmax, ymin, ymax, zmin, zmax;
/* min/max in all three directions */
struct lp_style_type *lp; /* pointer to l/p properties */
int style; /* The style of the lines */
long next; /* index of next polygon in z-sorted list */
long next_frag; /* next fragment of same polygon... */
int id; /* Which polygons belong together? */
t_poly_tested tested; /* To determine a loop during the sorting algorithm */
/* HBB 980317: on the 16 bit PC platforms, the struct size must
* be a power of two, so it exactly fits into a 64KB segment. First
* we'll add the TEST_GRIDCHECK fields, regardless wether that
* feature was activated or not. */
#if TEST_GRIDCHECK || defined(DOS16) || defined(WIN16)
unsigned int xextent, yextent;
#endif
/* HBB 980317: the remaining bit of padding. */
#if defined(DOS16) || defined(WIN16)
char dummies[8];
#endif
};
typedef enum { /* result type for polygon_plane_intersection() */
infront, inside, behind, intersects
} t_poly_plane_intersect;
static struct Vertex GPHUGE *vlist; /* The vertices */
static struct Polygon GPHUGE *plist; /* The polygons */
static long nvert, npoly; /* amount of vertices and polygons */
static long pfree, vert_free; /* index on the first free entries */
static long pfirst; /* Index on the first polygon */
/* macros for (somewhat) safer handling of the dynamic array of
* polygons, 'plist[]' */
#define EXTEND_PLIST() \
plist = (struct Polygon GPHUGE *) gp_realloc(plist, \
(unsigned long)sizeof(struct Polygon)*(npoly+=10L), "hidden plist")
#define CHECK_PLIST() if (pfree >= npoly) EXTEND_PLIST()
#define CHECK_PLIST_2() if (pfree+1 >= npoly) EXTEND_PLIST()
#define CHECK_PLIST_EXTRA(extra) if (pfree >= npoly) { EXTEND_PLIST() ; extra; }
/* precision of calculations in normalized space: */
#define EPSILON 1e-5 /* HBB: was 1.0E-5 */
#define SIGNOF(X) ( ((X)<-EPSILON) ? -1: ((X)>EPSILON) )
/* Some inexact relations: == , > , >= */
#define EQ(X,Y) (fabs( (X) - (Y) ) < EPSILON) /* X == Y */
#define GR(X,Y) ((X) > (Y) + EPSILON) /* X > Y */
#define GE(X,Y) ((X) >=(Y) - EPSILON) /* X >= Y */
/* Test, if two vertices are near each other */
#define V_EQUAL(a,b) ( GE(0.0, fabs((a)->x - (b)->x) + \
fabs((a)->y - (b)->y) + fabs((a)->z - (b)->z)) )
#define SETBIT(a,i,set) a= (set) ? (a) | (1L<<(i)) : (a) & ~(1L<<(i))
#define GETBIT(a,i) (((a)>>(i))&1L)
#define UINT_BITS (CHAR_BIT*sizeof(unsigned int))
#define USHRT_BITS (CHAR_BIT*sizeof(unsigned short))
static void print_polygon __PROTO((struct Polygon GPHUGE * p, const char *pname));
/* HBB: new routine, to help debug 'Logic errors', mainly */
static void
print_polygon(p, pname)
struct Polygon GPHUGE * p;
const char *pname;
{
struct Vertex GPHUGE *v;
int i;
fprintf(stderr, "#%s:(ind %d) n:%d, id:%d, next:%ld, tested:%s\n",
pname, (int)(p-plist), p->n, p->id, p->next,
string_poly_tested[(int)(p->tested)]);
fprintf(stderr,"#zmin:%g, zmax:%g\n", p->zmin, p->zmax);
for (i=0; i<p->n; i++, v++) {
v = vlist + p->vertex[i];
fprintf(stderr,"%g %g %g \t%ld\n", v->x, v->y, v->z, p->vertex[i]);
}
/*repeat first vertex, so the line gets closed: */
v = vlist + p->vertex[0];
fprintf(stderr,"%g %g %g \t%ld\n", v->x, v->y, v->z, p->vertex[0]);
/*two blank lines, as a multimesh separator: */
fprintf(stderr,"\n\n");
}
/* Gets Minimum 'C' value of polygon, C is x, y, or z: */
#define GET_MIN(p, C, min) do { \
int i; \
long *v=p->vertex; \
\
min = vlist[*v++].C; \
for (i=1; i< p->n; i++, v++) \
if (vlist[*v].C < min) \
min = vlist[*v].C; \
} while (0)
/* Gets Maximum 'C' value of polygon, C is x, y, or z: */
#define GET_MAX(p, C, max) do { \
int i; \
long *v=p->vertex; \
\
max = vlist[*v++].C; \
for (i=1; i< p->n; i++, v++) \
if (vlist[*v].C > max) \
max = vlist[*v].C; \
} while (0)
/* Prototypes for internal functions of this module. */
static void map3d_xyz __PROTO((double x, double y, double z, struct Vertex GPHUGE *v));
static int reduce_polygon __PROTO((int *n, long **v, long *line, int nmin));
static void build_polygon __PROTO((struct Polygon GPHUGE *p, int n,
long *v, long line, int style, struct lp_style_type *lp,
long next, long next_frag, int id, t_poly_tested tested));
static GP_INLINE int maybe_build_polygon __PROTO((struct Polygon GPHUGE *p, int n,
long *v, long line, int style, struct lp_style_type *lp,
long next, long next_frag, int id, t_poly_tested tested));
static void init_polygons __PROTO((struct surface_points *plots, int pcount));
static int compare_by_zmax __PROTO((const void *p1, const void *p2));
static void sort_by_zmax __PROTO((void));
static int obscured __PROTO((struct Polygon GPHUGE *p));
static GP_INLINE int xy_overlap __PROTO((struct Polygon GPHUGE *a, struct Polygon GPHUGE *b));
static void get_plane __PROTO((struct Polygon GPHUGE *p, double *a, double *b,
double *c, double *d));
static t_poly_plane_intersect polygon_plane_intersection __PROTO((struct Polygon GPHUGE *p, double a,
double b, double c, double d));
static int intersect __PROTO((struct Vertex GPHUGE *v1, struct Vertex GPHUGE *v2,
struct Vertex GPHUGE *v3, struct Vertex GPHUGE *v4));
static int v_intersect __PROTO((struct Vertex GPHUGE *v1, struct Vertex GPHUGE *v2,
struct Vertex GPHUGE *v3, struct Vertex GPHUGE *v4));
static int intersect_polygon __PROTO((struct Vertex GPHUGE *v1, struct Vertex GPHUGE *v2,
struct Polygon GPHUGE *p));
static int full_xy_overlap __PROTO((struct Polygon GPHUGE *a, struct Polygon GPHUGE *b));
static long build_new_vertex __PROTO((long V1, long V2, double w));
static long split_polygon_by_plane __PROTO((long P, double a, double b, double c,
double d, TBOOLEAN f));
static int in_front __PROTO((long Last, long Test));
/* HBB 980303: new, for the new back-buffer for *Cross structures: */
static GP_INLINE struct Cross *get_Cross_from_store __PROTO((void));
static GP_INLINE void init_Cross_store __PROTO((void));
static GP_INLINE TBOOLEAN hl_buffer_set __PROTO((int xv, int yv));
static GP_INLINE void update_hl_buffer_column __PROTO((int xv, int ya, int yv));
static void draw_clip_line_buffer __PROTO((int x1, int y1, int x2, int y2));
static void draw_clip_line_update __PROTO((int x1, int y1, int x2, int y2,
int virtual));
static GP_INLINE void clip_vector_h __PROTO((int x, int y));
static GP_INLINE void clip_vector_virtual __PROTO((int x, int y));
static GP_INLINE void clip_vector_buffer __PROTO((int x, int y));
static void draw __PROTO((struct Polygon GPHUGE *p));
/* Set the options for hidden3d. To be called from set.c, when the
* user has begun a command with 'set hidden3d', to parse the rest of
* that command */
void
set_hidden3doptions()
{
struct value t;
c_token++;
if (END_OF_COMMAND) {
return;
}
if (almost_equals(c_token,"def$aults")) {
/* reset all parameters to defaults */
hiddenBacksideLinetypeOffset = BACKSIDE_LINETYPE_OFFSET;
hiddenTriangleLinesdrawnPattern = TRIANGLE_LINESDRAWN_PATTERN;
hiddenHandleUndefinedPoints = HANDLE_UNDEFINED_POINTS;
hiddenShowAlternativeDiagonal = SHOW_ALTERNATIVE_DIAGONAL;
hiddenHandleBentoverQuadrangles = HANDLE_BENTOVER_QUADRANGLES;
c_token++;
if (!END_OF_COMMAND)
int_error("No further options allowed after 'defaults'", c_token);
return;
}
if (almost_equals(c_token, "off$set")) {
c_token++;
hiddenBacksideLinetypeOffset = (int) real(const_express(&t));
} else if (almost_equals(c_token, "nooff$set")) {
c_token++;
hiddenBacksideLinetypeOffset = 0;
}
if (END_OF_COMMAND) {
return;
}
if (almost_equals(c_token, "tri$anglepattern")) {
c_token++;
hiddenTriangleLinesdrawnPattern = (int) real(const_express(&t));
}
if (END_OF_COMMAND) {
return;
}
if (almost_equals(c_token, "undef$ined")) {
int tmp;
c_token++;
tmp = (int) real(const_express(&t));
if (tmp<=0 || tmp > UNHANDLED)
tmp = UNHANDLED;
hiddenHandleUndefinedPoints = tmp;
} else if (almost_equals(c_token, "nound$efined")) {
c_token++;
hiddenHandleUndefinedPoints = UNHANDLED;
}
if (END_OF_COMMAND) {
return;
}
if (almost_equals(c_token, "alt$diagonal")) {
c_token++;
hiddenShowAlternativeDiagonal = 1;
} else if (almost_equals(c_token, "noalt$diagonal")) {
c_token++;
hiddenShowAlternativeDiagonal = 0;
}
if (END_OF_COMMAND) {
return;
}
if (almost_equals(c_token, "bent$over")) {
c_token++;
hiddenHandleBentoverQuadrangles = 1;
} else if (almost_equals(c_token, "nobent$over")) {
c_token++;
hiddenHandleBentoverQuadrangles = 0;
}
if (!END_OF_COMMAND) {
int_error("No such option to hidden3d (or wrong order)", c_token);
}
}
/* HBB 970619: new routine for displaying the option settings */
void
show_hidden3doptions()
{
fprintf(stderr, "\t Back side of surfaces has linestyle offset of %d\n",
hiddenBacksideLinetypeOffset);
fprintf(stderr, "\t Bit-Mask of Lines to draw in each triangle is %ld\n",
hiddenTriangleLinesdrawnPattern);
fprintf(stderr, "\t %d: ", hiddenHandleUndefinedPoints);
switch (hiddenHandleUndefinedPoints) {
case OUTRANGE:
fprintf(stderr, "Outranged and undefined datapoints are omitted from the surface.\n");
break;
case UNDEFINED:
fputs("Only undefined datapoints are omitted from the surface.\n", stderr);
break;
case UNHANDLED:
fputs("Will not check for undefined datapoints (may cause crashes).\n", stderr);
break;
default:
fputs("This value is illegal!!!\n", stderr);
break;
}
fprintf(stderr, "\t Will %suse other diagonal if it gives a less jaggy outline\n",
hiddenShowAlternativeDiagonal ? "" : "not ");
fprintf(stderr, "\t Will %sdraw diagonal visibly if quadrangle is 'bent over'\n",
hiddenHandleBentoverQuadrangles ? "" : "not ");
}
/* HBB 971117: new function.*/
/* Implements proper 'save'ing of the new hidden3d options... */
void
save_hidden3doptions(fp)
FILE *fp;
{
if (!hidden3d) {
fputs("set nohidden3d\n", fp);
return;
}
fprintf(fp, "set hidden3d offset %d trianglepattern %ld undefined %d %saltdiagonal %sbentover\n",
hiddenBacksideLinetypeOffset,
hiddenTriangleLinesdrawnPattern,
hiddenHandleUndefinedPoints,
hiddenShowAlternativeDiagonal ? "" : "no",
hiddenHandleBentoverQuadrangles ? "" : "no");
}
/* Initialize the necessary steps for hidden line removal and
initialize global variables. */
void
init_hidden_line_removal ()
{
int i;
/* Check for some necessary conditions to be set elsewhere: */
/* HandleUndefinedPoints mechanism depends on these: */
assert(OUTRANGE==1);
assert(UNDEFINED==2);
/* '3' makes the test easier in the critical section */
if (hiddenHandleUndefinedPoints<OUTRANGE)
hiddenHandleUndefinedPoints=UNHANDLED;
/* We want to keep the bitmap size less than 2048x2048, so we choose
* integer dividers for the x and y coordinates to keep the x and y
* ranges less than 2048. In practice, the x and y sizes for the bitmap
* will be somewhere between 1024 and 2048, except in cases where the
* coordinates ranges for the device are already less than 1024.
* We do this mainly to control the size of the bitmap, but it also
* speeds up the computation. We maintain separate dividers for
* x and y.
*/
xfact = (xright - xleft) / 1024;
yfact = (ytop - ybot) / 1024;
if (xfact == 0)
xfact = 1;
if (yfact == 0)
yfact = 1;
if (pnt == 0)
{
i = XREDUCE (xright) - XREDUCE (xleft) + 1;
pnt = (tp_pnt *) gp_alloc (
(unsigned long) (i * sizeof (tp_pnt)), "hidden pnt");
while (--i>=0)
pnt[i] = (tp_pnt) 0;
}
}
/* Reset the hidden line data to a fresh start. */
void
reset_hidden_line_removal ()
{
int i;
if (pnt)
{
for (i = 0; i <= XREDUCE (xright) - XREDUCE (xleft); i++)
{
if (pnt[i])
{
free (pnt[i]);
pnt[i] = 0;
};
};
};
}
/* Terminates the hidden line removal process. */
/* Free any memory allocated by init_hidden_line_removal above. */
void
term_hidden_line_removal ()
{
if (pnt)
{
int j;
for (j = 0; j <= XREDUCE (xright) - XREDUCE (xleft); j++)
{
if (pnt[j])
{
free (pnt[j]);
pnt[j] = 0;
};
};
free (pnt);
pnt = 0;
};
if (ymin_hl)
free (ymin_hl), ymin_hl = 0;
if (ymax_hl)
free (ymax_hl), ymax_hl = 0;
}
/* Maps from normalized space to terminal coordinates */
#define TERMCOORD(v,x,y) x = ((int)((v)->x * xscaler)) + xmiddle, \
y = ((int)((v)->y * yscaler)) + ymiddle;
static void
map3d_xyz (x, y, z, v)
double x, y, z; /* user coordinates */
struct Vertex GPHUGE *v; /* the point in normalized space */
{
int i, j;
double V[4], Res[4], /* Homogeneous coords. vectors. */
w = trans_mat[3][3];
/* Normalize object space to -1..1 */
V[0] = map_x3d (x);
V[1] = map_y3d (y);
V[2] = map_z3d (z);
V[3] = 1.0;
Res[0]=0; /*HBB 961110: lclint wanted this... Why? */
for (i = 0; i < 3; i++)
{
Res[i] = trans_mat[3][i]; /* Initiate it with the weight factor. */
for (j = 0; j < 3; j++)
Res[i] += V[j] * trans_mat[j][i];
}
for (i = 0; i < 3; i++)
w += V[i] * trans_mat[i][3];
if (w == 0)
w = 1.0e-5;
v->x = Res[0] / w;
v->y = Res[1] / w;
v->z = Res[2] / w;
}
/* remove unnecessary Vertices from a polygon: */
static int
reduce_polygon (n, v, line, nmin)
int *n; /* number of vertices */
long **v; /* the vertices */
long *line; /* the information, which line should be drawn */
int nmin; /* if the number reduces under nmin, forget polygon */
/* Return value 1: the reduced polygon has still more or equal
vertices than nmin.
Return value 0: the polygon was trivial; memory is given free */
{
int less, i;
long *w = *v;
for (less = 0, i = 0; i < *n - 1; i++) {
if (V_EQUAL (vlist + w[i], vlist + w[i + 1])
/* HBB 970321: try to remove an endless loop bug (part1/2) */
&& ((w[i] == w[i+1])
|| !GETBIT (*line, i)
|| GETBIT (*line, i + 1)
|| ((i > 0) ? GETBIT (*line, i - 1) : GETBIT (*line, *n - 1))))
less++;
else if (less) {
w[i - less] = w[i];
SETBIT (*line, i - less, GETBIT (*line, i));
}
}
if (i - less > 0
&& V_EQUAL (vlist + w[i], vlist + w[0])
/* HBB 970321: try to remove an endless loop bug (part2/2) */
&& (w[i] == w[0]
|| !GETBIT (*line, i)
|| GETBIT (*line, i - 1)
|| GETBIT (*line, 0)))
less++;
else if (less) {
w[i - less] = w[i];
SETBIT (*line, i - less, GETBIT (*line, i));
}
*n -= less;
if (*n < nmin) {
free (w);
*v = 0; /* HBB 980213: signal that v(==w) is free()d */
return 0;
}
if (less) {
w = (long *) gp_realloc (w, (unsigned long) sizeof (long) * (*n),
"hidden red_poly");
*v = w;
for (; less > 0; less--)
SETBIT (*line, *n + less - 1, 0);
}
return 1;
}
/* Write polygon in plist */
/*
* HBB: changed this to precalculate {x|y}{min|max}
*/
static void
build_polygon (p, n, v, line, style, lp, next, next_frag, id, tested)
struct Polygon GPHUGE *p; /* this should point at a free entry in plist */
int n; /* number of vertices */
long *v; /* array of indices on the vertices (in vlist) */
long line; /* information, which line should be drawn */
int style; /* color of the lines */
struct lp_style_type *lp; /* pointer to line/point properties */
long next; /* next polygon in the list */
long next_frag; /* next fragment of same polygon */
int id; /* Which polygons belong together? */
t_poly_tested tested; /* Is polygon already on the right place of list? */
{
int i;
struct Vertex vert;
if (p >= plist+npoly)
fprintf(stderr, "uh oh !\n");
CHECK_POINTER(plist, p);
p->n = n;
p->vertex = v;
p->line = line;
p->lp = lp; /* line and point properties */
p->style = style;
CHECK_POINTER(vlist, (vlist + v[0]));
vert=vlist[v[0]];
p->xmin = p->xmax = vert.x;
p->ymin = p->ymax = vert.y;
p->zmin = p->zmax = vert.z;
for (i = 1; i < n; i++)
{
CHECK_POINTER(vlist, (vlist + v[i]));
vert=vlist[v[i]];
if (vert.x < p->xmin)
p->xmin=vert.x;
else if (vert.x > p->xmax)
p->xmax=vert.x;
if (vert.y < p->ymin)
p->ymin=vert.y;
else if (vert.y > p->ymax)
p->ymax=vert.y;
if (vert.z < p->zmin)
p->zmin=vert.z;
else if (vert.z > p->zmax)
p->zmax=vert.z;
}
#if TEST_GRIDCHECK
/* FIXME: this should probably use a table of bit-patterns instead...*/
p->xextent = (~ (~0U << (unsigned int)((p->xmax+1.0)/2.0*UINT_BITS+1.0)))
& (~0U << (unsigned int)((p->xmin+1.0)/2.0*UINT_BITS));
p->yextent = (~ (~0U << (unsigned int)((p->ymax+1.0)/2.0*UINT_BITS+1.0)))
& (~0U << (unsigned int)((p->ymin+1.0)/2.0*UINT_BITS));
#endif
p->next = next;
p->next_frag = next_frag; /* HBB 961201: link fragments, to speed up draw() q-loop */
p->id = id;
p->tested = tested;
}
/* get the amount of curves in a plot */
#define GETNCRV(NCRV) do {\
if(this_plot->plot_type==FUNC3D) \
for(icrvs=this_plot->iso_crvs,NCRV=0; \
icrvs;icrvs=icrvs->next,NCRV++); \
else if(this_plot->plot_type == DATA3D) \
NCRV = this_plot->num_iso_read; \
else { \
graph_error("Plot type is neither function nor data"); \
return; /* stops a gcc -Wunitialised warning */ \
} \
} while (0)
/* Do we see the top or bottom of the polygon, or is it 'on edge'? */
#define GET_SIDE(vlst,csign) do { \
double c = vlist[vlst[0]].x * (vlist[vlst[1]].y - vlist[vlst[2]].y) + \
vlist[vlst[1]].x * (vlist[vlst[2]].y - vlist[vlst[0]].y) + \
vlist[vlst[2]].x * (vlist[vlst[0]].y - vlist[vlst[1]].y); \
csign = SIGNOF (c); \
} while (0)
/* HBB 970131: new function, to allow handling of undefined datapoints
* by leaving out the corresponding polygons from the list.
* Return Value: 1 if polygon was built, 0 otherwise */
static GP_INLINE int
maybe_build_polygon (p, n, v, line, style, lp,
next, next_frag, id, tested)
struct Polygon GPHUGE *p;
struct lp_style_type *lp;
int n, style, id;
t_poly_tested tested;
long *v, line, next, next_frag;
{
int i;
assert(v);
if (hiddenHandleUndefinedPoints!=UNHANDLED)
for (i=0; i<n ; i++)
if (VERTEX_IS_UNDEFINED(vlist[v[i]])) {
free(v); /* HBB 980213: free mem... */
v = 0;
return 0; /* *don't* build the polygon! */
}
build_polygon (p, n, v, line, style, lp, next, next_frag, id, tested );
return 1;
}
/* HBB 970322: new macro, invented because code like this occured several
* times inside init_polygons, esp. after I added the option to choose the
* other diagonal to divide a quad when necessary */
/* HBB 980213: Here and below in init_polygons, added code to properly
* free any allocated vertex lists ('v' here), or avoid allocating
* them in the first place. Thanks to Stefan Schroepfer for reporting
* the leak. */
#define PREPARE_POLYGON(n,v,i0,i1,i2,line,c,border,i_chk,ncrv_chk,style) do {\
(n) = 3; \
if (VERTEX_IS_UNDEFINED(vlist[vert_free + (i0)])\
|| VERTEX_IS_UNDEFINED(vlist[vert_free + (i1)]) \
|| VERTEX_IS_UNDEFINED(vlist[vert_free + (i2)])) { \
/* These values avoid any further action on this polygon */\
(v)=0; /* flag this as undefined */ \
(c)=(border)=0; \
} else {\
(v) = (long *) gp_alloc ((unsigned long) sizeof (long) * (n), "hidden PREPARE_POLYGON"); \
(v)[0] = vert_free + (i0);\
(v)[1] = vert_free + (i1);\
(v)[2] = vert_free + (i2);\
(line) = hiddenTriangleLinesdrawnPattern;\
GET_SIDE((v),(c));\
/* Is this polygon at the border of the surface? */\
(border) = (i == (i_chk) || ncrv == (ncrv_chk));\
}\
(style) = ((c) >= 0) ? above : below;\
} while (0)
static void
init_polygons (plots, pcount)
struct surface_points *plots;
int pcount;
/* Initialize vlist, plist */
{
long int i;
struct surface_points *this_plot;
int surface;
long int ncrv, ncrv1;
struct iso_curve *icrvs;
int row_offset;
int id;
int n1, n2; /* number of vertices of a Polygon */
long *v1, *v2; /* the Vertices */
long line1, line2; /* which lines should be drawn */
int above=-1, below, style1, style2; /* the line color */
struct lp_style_type *lp; /* pointer to line and point properties */
int c1, c2; /* do we see the front or the back */
TBOOLEAN border1, border2; /* is it at the border of the surface */
/* allocate memory for polylist and nodelist */
nvert = npoly = 0;
for (this_plot = plots, surface = 0;
surface < pcount;
this_plot = this_plot->next_sp, surface++) {
GETNCRV (ncrv);
switch (this_plot->plot_style) {
case LINESPOINTS:
case STEPS: /* handle as LINES */
case FSTEPS:
case HISTEPS:
case LINES:
#if FOUR_TRIANGLES
nvert += ncrv * (2 * this_plot->iso_crvs->p_count - 1);
#else
nvert += ncrv * (this_plot->iso_crvs->p_count);
#endif
npoly += 2 * (ncrv - 1) * (this_plot->iso_crvs->p_count - 1);
break;
case DOTS:
case XERRORBARS: /* handle as POINTSTYLE */
case YERRORBARS:
case XYERRORBARS:
case BOXXYERROR:
case BOXERROR:
case CANDLESTICKS: /* HBB: these as well */
case FINANCEBARS:
case VECTOR:
case POINTSTYLE:
nvert += ncrv * (this_plot->iso_crvs->p_count);
npoly += (ncrv - 1) * (this_plot->iso_crvs->p_count - 1);
break;
case BOXES: /* handle as IMPULSES */
case IMPULSES:
nvert += 2 * ncrv * (this_plot->iso_crvs->p_count);
npoly += (ncrv - 1) * (this_plot->iso_crvs->p_count - 1);
break;
}
}