]> icculus.org git repositories - taylor/freespace2.git/blob - src/graphics/aaline.cpp
Initial revision
[taylor/freespace2.git] / src / graphics / aaline.cpp
1 /*
2  * $Logfile: /Freespace2/code/Graphics/aaline.cpp $
3  * $Revision$
4  * $Date$
5  * $Author$
6  *
7  * Code to draw antialiased lines
8  *
9  * $Log$
10  * Revision 1.1  2002/05/03 03:28:09  root
11  * Initial revision
12  *
13  * 
14  * 3     12/02/98 5:47p Dave
15  * Put in interface xstr code. Converted barracks screen to new format.
16  * 
17  * 2     10/07/98 10:52a Dave
18  * Initial checkin.
19  * 
20  * 1     10/07/98 10:48a Dave
21  * 
22  * 13    5/06/98 5:30p John
23  * Removed unused cfilearchiver.  Removed/replaced some unused/little used
24  * graphics functions, namely gradient_h and _v and pixel_sp.   Put in new
25  * DirectX header files and libs that fixed the Direct3D alpha blending
26  * problems.
27  * 
28  * 12    3/24/98 4:03p Lawrance
29  * JOHN: Fix up outline drawing code to support different colors
30  * 
31  * 11    3/10/98 4:18p John
32  * Cleaned up graphics lib.  Took out most unused gr functions.   Made D3D
33  * & Glide have popups and print screen.  Took out all >8bpp software
34  * support.  Made Fred zbuffer.  Made zbuffer allocate dynamically to
35  * support Fred.  Made zbuffering key off of functions rather than one
36  * global variable.
37  * 
38  * 10    1/19/98 6:15p John
39  * Fixed all my Optimized Build compiler warnings
40  * 
41  * 9     11/30/97 4:26p John
42  * Added 32-bpp antialiased line.   Took gamma out of alphacolor
43  * calculation.
44  * 
45  * 8     11/29/97 2:06p John
46  * added mode 16-bpp support
47  * 
48  * 7     10/20/97 8:47a John
49  * fixed gr_lock bug in aaline
50  * 
51  * 6     10/19/97 12:55p John
52  * new code to lock / unlock surfaces for smooth directx integration.
53  * 
54  * 5     10/14/97 8:08a John
55  * added a bunch more 16 bit support
56  * 
57  * 4     10/04/97 11:27a John
58  * took out debug code
59  * 
60  * 3     10/03/97 9:50a John
61  * enabled antialiasing lines in alphacolor set.
62  * 
63  * 2     10/03/97 9:10a John
64  * added better antialiased line drawer
65  * 
66  * 1     10/03/97 9:07a John
67  *
68  * $NoKeywords: $
69  */
70
71 /*
72
73  Code for drawing antialiased lines.  Taken from some code
74  published in the Journal of Graphic Tools at www.acm.org/jgt
75
76  Here is the README that came with the source code:
77
78         Sample code to draw antialiased lines as described in the Journal of
79         Graphic Tools article High Quality Hardware Line Antialiasing by
80         Scott R. Nelson of Sun Microsystems.
81
82         The code is written in C and designed to run on any machine with the
83         addition of a proper "display" module.  Currently, display modules
84         exist for Macintosh, Unix, and Wintel machines.  Thanks to Sanjay Gupta
85         (sanjay.gupta@eng.sun.com) for the Unix X11 display code and Chris
86         Babcock (babcock@rtp.idt.com) for the Windows code.
87
88         This code is not 100% bug free and is definitely not optimized for
89         performance.  It does, however, illustrate all of the points made in
90         the JGT article.
91 */
92
93
94 #include <stdio.h>
95 #include <stdlib.h>
96
97 #include "pstypes.h"
98 #include "2d.h"
99 #include "line.h"
100 #include "grinternal.h"
101 #include "palman.h"
102
103 // Convert from floating-point to internal fixed-point formats
104 #define ONE_XY                  (long int) 0x00100000
105 #define FIX_XY_SHIFT    (long int) 20
106 #define ONEHALF_XY      (long int) 0x00080000
107 #define ONE_Z                   (long int) 0x40000000
108 #define ONE_RGB         (long int) 0x40000000
109 #define ONE_16                  (long int) 0x4000
110
111 #define FLOAT_TO_FIX_XY(x)      ((long int) ((x) * (float) ONE_XY))
112
113 #define FLOAT_TO_FIX_RGB(x)     ((long int) ((x) * (float) ONE_RGB))
114 #define FLOAT_TO_FIX_16(x)      ((long int) ((x) * (float) ONE_16))
115 #define FIX_TO_INT_XY(x)        ((x) >> FIX_XY_SHIFT)
116 #define FIX_16_TO_FLOAT(x)      ((float) (x) / (float) ONE_16)
117 #define FIX_TO_FLOAT_XY(x)      ((float) (x) / (float) ONE_XY)
118 #define FIX_TO_FLOAT_RGB(x)     ((float) (x) / (float) ONE_RGB)
119
120 // Get fractional part, next lowest integer part
121 #define FRACT_XY(x)             ((x) & (long int) 0x000fffff)
122 #define FLOOR_XY(x)             ((x) & (long int) 0xfff00000)
123 #define FIX_XY_TO_INT(x)        ((long int) (x) >> (long int) FIX_XY_SHIFT)
124
125 // Sizes for tables in Draw
126 #define FILTER_WIDTH    0.75            // Line filter width adjustment // .75          // .5 works good with 5.0 gamma
127 #define F_TABLE_SIZE    64                      // Filter table size
128 #define SC_TABLE_SIZE   32              // Slope correction table size
129 #define SRT_INT         5                       // Sqrt table index integer bits
130 #define SRT_FRACT       4                               //   ...fraction bits
131 #define SR_INT          3                               // Square root result integer bits
132 #define SR_FRACT        5                               //   ...fraction bits
133 #define SR_TABLE_SIZE   (1 << (SRT_INT + SRT_FRACT))
134 #define INV_FILTER 47
135
136 #define EP_MASK (long int) 0x000f0000u  // AA line end-point filter mask
137 #define EP_SHIFT        13u                     // Number of bits to shift end-point
138
139
140 typedef long int fix_xy;        // S11.20
141
142 // One vertex at any of the various stages of the pipeline
143
144 typedef struct aa_vertex {
145         float x, y;
146 } aa_vertex;
147
148 // All values needed to draw one line
149 typedef struct aa_setup_line {
150         int x_major;
151         int negative;
152
153         fix_xy vs;                      // Starting point
154         fix_xy us;
155         fix_xy ue;                      // End (along major axis)
156         fix_xy dvdu;            // Delta for minor axis step
157
158 } aa_setup_line;
159
160
161 // Tables that need to be initialized
162 long int slope_corr_table[SC_TABLE_SIZE];
163 long int filter_table[F_TABLE_SIZE];
164 long int sqrt_table[SR_TABLE_SIZE];
165
166 ubyte new_table[F_TABLE_SIZE*512];
167
168 int aaline_inited = 0;
169
170 // Initialize the tables normally found in ROM in the hardware.
171 void aaline_init_tables()
172 {
173         int i,j;                                        // Iterative counter
174         double m;                               // Slope
175         double d;                               // Distance from center of curve
176         double v;                               // Value to put in table
177         double sr;                              //      The square root value
178
179         aaline_inited = 1;
180
181         // Build slope correction table.  The index into this table
182         // is the truncated 5-bit fraction of the slope used to draw
183         // the line.  Round the computed values here to get the closest
184         // fit for all slopes matching an entry.
185
186         for (i = 0; i < SC_TABLE_SIZE; i++) {
187                 // Round and make a fraction
188                 m = ((double) i + 0.5) / (float) SC_TABLE_SIZE;
189                 v = sqrt(m * m + 1) * 0.707106781; /* (m + 1)^2 / sqrt(2) */
190                 slope_corr_table[i] = (long int) (v * 256.0);
191         }
192
193         // Build the Gaussian filter table, round to the middle of the sample region.
194         for (i = 0; i < F_TABLE_SIZE; i++) {
195                 d = ((double) i + 0.5) / (float) (F_TABLE_SIZE / 2.0);
196                 d = d / FILTER_WIDTH;
197                 v = 1.0 / exp(d * d);           // Gaussian function
198                 filter_table[i] = (long int) (v * 256.0);
199         }
200
201         for ( i=0; i<512; i++ ) {
202                 long int corr_slope = i<<8;
203                 for (j=0; j<F_TABLE_SIZE; j++ ) {
204                         new_table[i*F_TABLE_SIZE+j] = (ubyte)(((corr_slope * filter_table[j]) & 0xf00000) >> (16+4));
205                         if (new_table[i*F_TABLE_SIZE+j]==15 )   {
206                                 // HACK!!! Account for "glass" pixel for hud bitmaps.
207                                 new_table[i*F_TABLE_SIZE+j] = 14;
208                         }
209                 }
210         }
211         
212
213         // Build the square root table for big dots.
214         for (i = 0; i < SR_TABLE_SIZE; i++) {
215                 v = (double) ((i << 1) + 1) / (double) (1 << (SRT_FRACT + 1));
216                 sr = sqrt(v);
217                 sqrt_table[i] = (long int) (sr * (double) (1 << SR_FRACT));
218         }
219
220
221 }
222
223
224
225 // Multiply a fixed-point number by a s11.20 fixed-point
226 // number.  The actual multiply uses less bits for the
227 // multiplier, since it always represents a fraction
228 // less than 1.0 and less total bits are sufficient.
229 // Some of the steps here are not needed.  This was originally
230 // written to simulate exact hardware behavior.
231 long int fix_xy_mult(long int oa, fix_xy ob)
232 {
233         int retval;
234
235 #ifdef PLAT_UNIX
236         STUB_FUNCTION;
237 #else
238         _asm {
239                 mov     edx, oa
240                 mov     eax, ob
241                 imul    edx
242                 shrd    eax,edx,20
243                 mov     retval, eax
244         }
245 #endif
246         return retval;
247 }
248
249
250
251 // Draw one span of an antialiased line (for horizontal lines).
252 void draw_aa_hspan8(fix_xy x, fix_xy y, long int ep_corr, long int slope)
253 {
254 #ifndef HARDWARE_ONLY
255         long int sample_dist;           // Distance from line to sample point
256         long int filter_index;          // Index into filter table
257         long int i;                                             // Count pixels across span
258         long int index;                         // Final filter table index
259         int a;                                                  // Alpha
260
261         sample_dist = (FRACT_XY(y) >> (FIX_XY_SHIFT - 5)) - 16;
262         y = y - ONE_XY;
263         filter_index = sample_dist + 32;
264
265
266         int yi = FIX_XY_TO_INT( y );
267         int xi = FIX_XY_TO_INT( x );
268
269         if ( xi < gr_screen.clip_left ) return;
270         if ( xi > gr_screen.clip_right ) return;
271
272         int clipped = 0;
273         
274         if ( yi < gr_screen.clip_top ) clipped++;
275         if ( yi+3 > gr_screen.clip_bottom ) clipped++;
276
277         long int corr_slope = (slope * ep_corr) & 0x1ff00;
278
279         ubyte * lookup = (ubyte *)&Current_alphacolor->table.lookup[0][0];
280
281         ubyte * filter_lookup = (ubyte *)&new_table[(corr_slope>>8)*F_TABLE_SIZE];
282
283
284         if ( clipped )  {
285                 ubyte * dptr;
286                 
287                 for (i = 0; i < 4; i++) {
288                         if (filter_index < 0)
289                                 index = ~filter_index;  // Invert when negative
290                         else
291                                 index = filter_index;
292
293                         if (index > INV_FILTER) {
294                                 Assert( i == 3 );
295                                 return;                 // Not a valid pixel
296                         }
297
298                         //a = ((corr_slope * filter_table[index]) & 0xf00000) >> (16+4-8);
299                         a = filter_lookup[index]<<8;
300
301                         // Should include the alpha value as well...
302                         if ( (yi >= gr_screen.clip_top) && (yi <= gr_screen.clip_bottom) )      {
303                                 dptr = GR_SCREEN_PTR(ubyte,xi, yi);
304
305                                 *dptr = lookup[*dptr+a];
306                         }
307
308                         filter_index -= 32;
309                         //y += ONE_XY;
310                         yi++;
311                 }
312         } else {
313                 ubyte * dptr;
314
315                 dptr = GR_SCREEN_PTR(ubyte,xi, yi);
316         
317                 for (i = 0; i < 4; i++) {
318                         if (filter_index < 0)
319                                 index = ~filter_index;  // Invert when negative
320                         else
321                                 index = filter_index;
322
323                         if (index > INV_FILTER) {
324                                 Assert( i == 3 );
325                                 return;                 // Not a valid pixel
326                         }
327
328                         a = filter_lookup[index]<<8;
329
330                         // Should include the alpha value as well...
331                         *dptr = lookup[*dptr+a];
332
333                         dptr += gr_screen.rowsize;
334
335                         filter_index -= 32;
336                 }
337
338
339         }
340 #else
341         Int3();
342 #endif
343 }
344
345 // draw_aa_vspan
346 // Draw one span of an antialiased line (for vertical lines).
347
348 void draw_aa_vspan8(fix_xy x, fix_xy y, long int ep_corr, long int slope)
349 {
350 #ifndef HARDWARE_ONLY
351         long int sample_dist;           // Distance from line to sample point
352         long int filter_index;          // Index into filter table 
353         long int i;                                             // Count pixels across span
354         long int index;                         // Final filter table index
355         int a;                                                  // Alpha
356
357         sample_dist = (FRACT_XY(x) >> (FIX_XY_SHIFT - 5)) - 16;
358         x = x - ONE_XY;
359         filter_index = sample_dist + 32;
360
361         int yi = FIX_XY_TO_INT( y );
362         int xi = FIX_XY_TO_INT( x );
363
364         if ( yi < gr_screen.clip_top ) return;
365         if ( yi > gr_screen.clip_bottom ) return;
366
367         int clipped = 0;
368         
369         if ( xi < gr_screen.clip_left ) clipped++;
370         if ( xi+3 > gr_screen.clip_right ) clipped++;
371
372         long int corr_slope = (slope * ep_corr) & 0x1ff00;
373
374         ubyte * lookup = (ubyte *)&Current_alphacolor->table.lookup[0][0];
375
376         ubyte * filter_lookup = (ubyte *)&new_table[(corr_slope>>8)*F_TABLE_SIZE];
377
378
379         if ( clipped )  {
380                 ubyte * dptr;
381
382                 for (i = 0; i < 4; i++) {
383                         if (filter_index < 0)
384                                 index = ~filter_index;  // Invert when negative
385                         else
386                                 index = filter_index;
387
388                         if (index > INV_FILTER) {
389                                 Assert( i == 3 );
390                                 return;                 // Not a valid pixel
391                         }
392
393                         //a = ((corr_slope * filter_table[index]) & 0xf00000) >> (16+4-8);
394                         a = filter_lookup[index]<<8;
395
396                         // Draw the pixel
397                         if ( (xi >= gr_screen.clip_left) && (xi <= gr_screen.clip_right) )      {
398                                 dptr = GR_SCREEN_PTR(ubyte,xi, yi);
399
400                                 *dptr = lookup[*dptr+a];
401                         }
402
403                         filter_index -= 32;
404                         xi++;
405                 }
406         } else {
407
408                 ubyte *dptr = GR_SCREEN_PTR(ubyte,xi, yi);
409
410                 for (i = 0; i < 4; i++) {
411                         if (filter_index < 0)
412                                 index = ~filter_index;  // Invert when negative
413                         else
414                                 index = filter_index;
415
416                         if (index > INV_FILTER) {
417                                 Assert( i == 3 );
418                                 return;                 // Not a valid pixel
419                         }
420
421                         a = filter_lookup[index]<<8;
422
423                         // Should include the alpha value as well...
424
425                         // Draw the pixel
426                         *dptr = lookup[*dptr+a];
427
428                         filter_index -= 32;
429                         dptr++;
430                 }
431         }
432 #else
433         Int3();
434 #endif
435 }
436
437
438 void draw_line(aa_setup_line *line)
439 {
440         fix_xy x, y;                                    //  Start value
441         fix_xy dudu;                                    //  Constant 1 or -1 for step
442         fix_xy dx, dy;                                  //  Steps in X and Y
443         fix_xy u_off;                                   //  Offset to starting sample grid
444         fix_xy us, vs, ue;                      //  Start and end for drawing
445         fix_xy count;                                   //  How many pixels to draw
446         long int slope_index;           //  Index into slope correction table
447         long int slope;                         //  Slope correction value
448         long int ep_corr;                               //  End-point correction value
449         long int scount, ecount;        //  Start/end count for endpoints
450         long int sf, ef;                                //  Sand and end fractions
451         long int ep_code;                               //  One of 9 endpoint codes
452
453         // Get directions
454         if (line->negative)     {
455                 dudu = -ONE_XY;
456         } else {
457                 dudu = ONE_XY;
458         }
459
460         if (line->x_major) {
461                 dx = dudu;
462                 dy = line->dvdu;
463         } else {
464                 dx = line->dvdu;
465                 dy = dudu;
466         }
467
468         // Get initial values and count
469         if (line->negative) {
470                 u_off = FRACT_XY(line->us) - ONE_XY;
471                 us = line->us + ONE_XY;
472                 ue = line->ue;
473                 count = FLOOR_XY(us) - FLOOR_XY(ue);
474         } else {
475                 u_off = 0 - FRACT_XY(line->us);
476                 us = line->us;
477                 ue = line->ue + ONE_XY;
478                 count = FLOOR_XY(ue) - FLOOR_XY(us);
479         }
480
481         vs = line->vs + fix_xy_mult(line->dvdu, u_off) + ONEHALF_XY;
482
483         if (line->x_major) {
484                 x = us;
485                 y = vs;
486         } else {
487                 x = vs;
488                 y = us;
489         }
490
491         //a = line->as + fix_xy_mult(line->dadu, u_off);
492
493         // Compute slope correction once per line
494         slope_index = (line->dvdu >> (FIX_XY_SHIFT - 5)) & 0x3fu;
495
496         if (line->dvdu < 0)     {
497                 slope_index ^= 0x3fu;
498         }
499
500         if ((slope_index & 0x20u) == 0) {
501                 slope = slope_corr_table[slope_index];
502         } else {
503                 slope = 0x100;          /* True 1.0 */
504         }
505
506         // Set up counters for determining endpoint regions
507         scount = 0;
508         ecount = FIX_TO_INT_XY(count);
509
510         // Get 4-bit fractions for end-point adjustments
511         sf = (us & EP_MASK) >> EP_SHIFT;
512         ef = (ue & EP_MASK) >> EP_SHIFT;
513
514         // Interpolate the edges
515         while (count >= 0) {
516
517                 /*-
518                 * Compute end-point code (defined as follows):
519                 *  0 =  0, 0: short, no boundary crossing
520                 *  1 =  0, 1: short line overlap (< 1.0)
521                 *  2 =  0, 2: 1st pixel of 1st endpoint
522                 *  3 =  1, 0: short line overlap (< 1.0)
523                 *  4 =  1, 1: short line overlap (> 1.0)
524                 *  5 =  1, 2: 2nd pixel of 1st endpoint
525                 *  6 =  2, 0: last of 2nd endpoint
526                 *  7 =  2, 1: first of 2nd endpoint
527                 *  8 =  2, 2: regular part of line
528                 */
529
530                 ep_code = ((scount < 2) ? scount : 2) * 3 + ((ecount < 2) ? ecount : 2);
531
532                 if (line->negative) {
533
534                         // Drawing in the negative direction
535
536                         // Compute endpoint information
537                         switch (ep_code) {
538                                 case 0: ep_corr = 0;                                                                    break;
539                                 case 1: ep_corr = ((sf - ef) & 0x78) | 4;               break;
540                                 case 2: ep_corr = sf | 4;                                                       break;
541                                 case 3: ep_corr = ((sf - ef) & 0x78) | 4;               break;
542                                 case 4: ep_corr = ((sf - ef) + 0x80) | 4;               break;
543                                 case 5: ep_corr = (sf + 0x80) | 4;                              break;
544                                 case 6: ep_corr = (0x78 - ef) | 4;                              break;
545                                 case 7: ep_corr = ((0x78 - ef) + 0x80) | 4;     break;
546                                 case 8: ep_corr = 0x100;                                                        break;
547                                 default:        ep_corr = 0;                                                            break;  
548                         }
549
550                 } else {
551                         // Drawing in the positive direction
552
553                         // Compute endpoint information
554                         switch (ep_code) {
555                                 case 0: ep_corr = 0;                                                                    break;
556                                 case 1: ep_corr = ((ef - sf) & 0x78) | 4;               break;
557                                 case 2: ep_corr = (0x78 - sf) | 4;                              break;
558                                 case 3: ep_corr = ((ef - sf) & 0x78) | 4;               break;
559                                 case 4: ep_corr = ((ef - sf) + 0x80) | 4;               break;
560                                 case 5: ep_corr = ((0x78 - sf) + 0x80) | 4;     break;
561                                 case 6: ep_corr = ef | 4;                                                       break;
562                                 case 7: ep_corr = (ef + 0x80) | 4;                              break;
563                                 case 8: ep_corr = 0x100;                                                        break;
564                                 default:        ep_corr = 0;                                                            break;  
565                         } 
566                 }
567
568                 if (line->x_major)      {
569                         draw_aa_hspan8(x, y, ep_corr, slope);
570                 } else  {
571                         draw_aa_vspan8(x, y, ep_corr, slope);
572                 }
573
574                 x += dx;
575                 y += dy;
576                 //a += line->dadu;
577
578                 scount++;
579                 ecount--;
580                 count -= ONE_XY;
581         }
582
583 }
584
585
586 // Perform the setup operation for a line, then draw it
587
588 void aaline_setup(aa_vertex *v1, aa_vertex *v2)
589 {
590         float dx, dy;                   // Deltas in X and Y
591         float udx, udy;         // Positive version of deltas
592         float one_du;                   // 1.0 / udx or udy
593         aa_setup_line line;
594
595         if ( !aaline_inited )
596                 aaline_init_tables();
597
598
599         dx = v1->x - v2->x;
600         dy = v1->y - v2->y;
601
602         if (dx < 0.0)   {
603                 udx = -dx;
604         } else  {
605                 udx = dx;
606         }
607
608         if (dy < 0.0)   {
609                 udy = -dy;
610         } else  {
611                 udy = dy;
612         }
613
614         if (udx > udy) {
615                 // X major line
616                 line.x_major = 1;
617                 line.negative = (dx < 0.0);
618                 line.us = FLOAT_TO_FIX_XY(v2->x);
619                 line.vs = FLOAT_TO_FIX_XY(v2->y);
620                 line.ue = FLOAT_TO_FIX_XY(v1->x);
621                 one_du = 1.0f / udx;
622                 line.dvdu = FLOAT_TO_FIX_XY(dy * one_du);
623         } else {
624                 // Y major line
625                 line.x_major = 0;
626                 line.negative = (dy < 0.0);
627                 line.us = FLOAT_TO_FIX_XY(v2->y);
628                 line.vs = FLOAT_TO_FIX_XY(v2->x);
629                 line.ue = FLOAT_TO_FIX_XY(v1->y);
630                 one_du = 1.0f / udy;
631                 line.dvdu = FLOAT_TO_FIX_XY(dx * one_du);
632         }
633
634         // Convert colors to fixed-point
635         //line.as = FLOAT_TO_FIX_RGB(v2->a);
636
637         // Compute delta values for colors
638         //line.dadu = FLOAT_TO_FIX_RGB((v1->a - v2->a) * one_du);
639
640         // Now go draw it
641
642         gr_lock();
643         draw_line(&line);
644         gr_unlock();
645 }
646
647
648 void gr8_aaline( vertex *v1, vertex *v2 )
649 {
650         aa_vertex aa1, aa2;
651
652         if ( !Current_alphacolor ) {
653                 gr_line(fl2i(v1->sx),fl2i(v1->sy),fl2i(v2->sx),fl2i(v2->sy));
654                 return;
655         }
656
657 //      return;
658
659         aa1.x = v1->sx;
660         aa1.y = v1->sy;
661
662         aa2.x = v2->sx;
663         aa2.y = v2->sy;
664
665         {
666                 int clipped = 0, swapped = 0;
667                 float a1, b1, a2, b2;
668                 a1 = (float)gr_screen.clip_left;
669                 b1 = (float)gr_screen.clip_top;
670                 a2 = (float)gr_screen.clip_right;
671                 b2 = (float)gr_screen.clip_bottom;
672
673                 FL_CLIPLINE(aa1.x,aa1.y,aa2.x,aa2.y,a1,b1,a2,b2,return,clipped=1,swapped=1);
674         }
675
676         aaline_setup( &aa1, &aa2 );
677 }