2 * $Logfile: /Freespace2/code/Graphics/aaline.cpp $
7 * Code to draw antialiased lines
10 * Revision 1.2 2002/05/07 03:16:45 theoddone33
11 * The Great Newline Fix
13 * Revision 1.1.1.1 2002/05/03 03:28:09 root
17 * 3 12/02/98 5:47p Dave
18 * Put in interface xstr code. Converted barracks screen to new format.
20 * 2 10/07/98 10:52a Dave
23 * 1 10/07/98 10:48a Dave
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
31 * 12 3/24/98 4:03p Lawrance
32 * JOHN: Fix up outline drawing code to support different colors
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
41 * 10 1/19/98 6:15p John
42 * Fixed all my Optimized Build compiler warnings
44 * 9 11/30/97 4:26p John
45 * Added 32-bpp antialiased line. Took gamma out of alphacolor
48 * 8 11/29/97 2:06p John
49 * added mode 16-bpp support
51 * 7 10/20/97 8:47a John
52 * fixed gr_lock bug in aaline
54 * 6 10/19/97 12:55p John
55 * new code to lock / unlock surfaces for smooth directx integration.
57 * 5 10/14/97 8:08a John
58 * added a bunch more 16 bit support
60 * 4 10/04/97 11:27a John
63 * 3 10/03/97 9:50a John
64 * enabled antialiasing lines in alphacolor set.
66 * 2 10/03/97 9:10a John
67 * added better antialiased line drawer
69 * 1 10/03/97 9:07a John
76 Code for drawing antialiased lines. Taken from some code
77 published in the Journal of Graphic Tools at www.acm.org/jgt
79 Here is the README that came with the source code:
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.
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.
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
103 #include "grinternal.h"
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
114 #define FLOAT_TO_FIX_XY(x) ((long int) ((x) * (float) ONE_XY))
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)
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)
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
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
143 typedef long int fix_xy; // S11.20
145 // One vertex at any of the various stages of the pipeline
147 typedef struct aa_vertex {
151 // All values needed to draw one line
152 typedef struct aa_setup_line {
156 fix_xy vs; // Starting point
158 fix_xy ue; // End (along major axis)
159 fix_xy dvdu; // Delta for minor axis step
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];
169 ubyte new_table[F_TABLE_SIZE*512];
171 int aaline_inited = 0;
173 // Initialize the tables normally found in ROM in the hardware.
174 void aaline_init_tables()
176 int i,j; // Iterative counter
178 double d; // Distance from center of curve
179 double v; // Value to put in table
180 double sr; // The square root value
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.
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);
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);
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;
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));
220 sqrt_table[i] = (long int) (sr * (double) (1 << SR_FRACT));
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)
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)
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
264 sample_dist = (FRACT_XY(y) >> (FIX_XY_SHIFT - 5)) - 16;
266 filter_index = sample_dist + 32;
269 int yi = FIX_XY_TO_INT( y );
270 int xi = FIX_XY_TO_INT( x );
272 if ( xi < gr_screen.clip_left ) return;
273 if ( xi > gr_screen.clip_right ) return;
277 if ( yi < gr_screen.clip_top ) clipped++;
278 if ( yi+3 > gr_screen.clip_bottom ) clipped++;
280 long int corr_slope = (slope * ep_corr) & 0x1ff00;
282 ubyte * lookup = (ubyte *)&Current_alphacolor->table.lookup[0][0];
284 ubyte * filter_lookup = (ubyte *)&new_table[(corr_slope>>8)*F_TABLE_SIZE];
290 for (i = 0; i < 4; i++) {
291 if (filter_index < 0)
292 index = ~filter_index; // Invert when negative
294 index = filter_index;
296 if (index > INV_FILTER) {
298 return; // Not a valid pixel
301 //a = ((corr_slope * filter_table[index]) & 0xf00000) >> (16+4-8);
302 a = filter_lookup[index]<<8;
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);
308 *dptr = lookup[*dptr+a];
318 dptr = GR_SCREEN_PTR(ubyte,xi, yi);
320 for (i = 0; i < 4; i++) {
321 if (filter_index < 0)
322 index = ~filter_index; // Invert when negative
324 index = filter_index;
326 if (index > INV_FILTER) {
328 return; // Not a valid pixel
331 a = filter_lookup[index]<<8;
333 // Should include the alpha value as well...
334 *dptr = lookup[*dptr+a];
336 dptr += gr_screen.rowsize;
349 // Draw one span of an antialiased line (for vertical lines).
351 void draw_aa_vspan8(fix_xy x, fix_xy y, long int ep_corr, long int slope)
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
360 sample_dist = (FRACT_XY(x) >> (FIX_XY_SHIFT - 5)) - 16;
362 filter_index = sample_dist + 32;
364 int yi = FIX_XY_TO_INT( y );
365 int xi = FIX_XY_TO_INT( x );
367 if ( yi < gr_screen.clip_top ) return;
368 if ( yi > gr_screen.clip_bottom ) return;
372 if ( xi < gr_screen.clip_left ) clipped++;
373 if ( xi+3 > gr_screen.clip_right ) clipped++;
375 long int corr_slope = (slope * ep_corr) & 0x1ff00;
377 ubyte * lookup = (ubyte *)&Current_alphacolor->table.lookup[0][0];
379 ubyte * filter_lookup = (ubyte *)&new_table[(corr_slope>>8)*F_TABLE_SIZE];
385 for (i = 0; i < 4; i++) {
386 if (filter_index < 0)
387 index = ~filter_index; // Invert when negative
389 index = filter_index;
391 if (index > INV_FILTER) {
393 return; // Not a valid pixel
396 //a = ((corr_slope * filter_table[index]) & 0xf00000) >> (16+4-8);
397 a = filter_lookup[index]<<8;
400 if ( (xi >= gr_screen.clip_left) && (xi <= gr_screen.clip_right) ) {
401 dptr = GR_SCREEN_PTR(ubyte,xi, yi);
403 *dptr = lookup[*dptr+a];
411 ubyte *dptr = GR_SCREEN_PTR(ubyte,xi, yi);
413 for (i = 0; i < 4; i++) {
414 if (filter_index < 0)
415 index = ~filter_index; // Invert when negative
417 index = filter_index;
419 if (index > INV_FILTER) {
421 return; // Not a valid pixel
424 a = filter_lookup[index]<<8;
426 // Should include the alpha value as well...
429 *dptr = lookup[*dptr+a];
441 void draw_line(aa_setup_line *line)
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
457 if (line->negative) {
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;
476 count = FLOOR_XY(us) - FLOOR_XY(ue);
478 u_off = 0 - FRACT_XY(line->us);
480 ue = line->ue + ONE_XY;
481 count = FLOOR_XY(ue) - FLOOR_XY(us);
484 vs = line->vs + fix_xy_mult(line->dvdu, u_off) + ONEHALF_XY;
494 //a = line->as + fix_xy_mult(line->dadu, u_off);
496 // Compute slope correction once per line
497 slope_index = (line->dvdu >> (FIX_XY_SHIFT - 5)) & 0x3fu;
499 if (line->dvdu < 0) {
500 slope_index ^= 0x3fu;
503 if ((slope_index & 0x20u) == 0) {
504 slope = slope_corr_table[slope_index];
506 slope = 0x100; /* True 1.0 */
509 // Set up counters for determining endpoint regions
511 ecount = FIX_TO_INT_XY(count);
513 // Get 4-bit fractions for end-point adjustments
514 sf = (us & EP_MASK) >> EP_SHIFT;
515 ef = (ue & EP_MASK) >> EP_SHIFT;
517 // Interpolate the edges
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
533 ep_code = ((scount < 2) ? scount : 2) * 3 + ((ecount < 2) ? ecount : 2);
535 if (line->negative) {
537 // Drawing in the negative direction
539 // Compute endpoint information
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;
554 // Drawing in the positive direction
556 // Compute endpoint information
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;
572 draw_aa_hspan8(x, y, ep_corr, slope);
574 draw_aa_vspan8(x, y, ep_corr, slope);
589 // Perform the setup operation for a line, then draw it
591 void aaline_setup(aa_vertex *v1, aa_vertex *v2)
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
598 if ( !aaline_inited )
599 aaline_init_tables();
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);
625 line.dvdu = FLOAT_TO_FIX_XY(dy * one_du);
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);
634 line.dvdu = FLOAT_TO_FIX_XY(dx * one_du);
637 // Convert colors to fixed-point
638 //line.as = FLOAT_TO_FIX_RGB(v2->a);
640 // Compute delta values for colors
641 //line.dadu = FLOAT_TO_FIX_RGB((v1->a - v2->a) * one_du);
651 void gr8_aaline( vertex *v1, vertex *v2 )
655 if ( !Current_alphacolor ) {
656 gr_line(fl2i(v1->sx),fl2i(v1->sy),fl2i(v2->sx),fl2i(v2->sy));
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;
676 FL_CLIPLINE(aa1.x,aa1.y,aa2.x,aa2.y,a1,b1,a2,b2,return,clipped=1,swapped=1);
679 aaline_setup( &aa1, &aa2 );