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