2 * $Logfile: /Freespace2/code/Graphics/aaline.cpp $
7 * Code to draw antialiased lines
10 * Revision 1.1 2002/05/03 03:28:09 root
14 * 3 12/02/98 5:47p Dave
15 * Put in interface xstr code. Converted barracks screen to new format.
17 * 2 10/07/98 10:52a Dave
20 * 1 10/07/98 10:48a Dave
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
28 * 12 3/24/98 4:03p Lawrance
29 * JOHN: Fix up outline drawing code to support different colors
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
38 * 10 1/19/98 6:15p John
39 * Fixed all my Optimized Build compiler warnings
41 * 9 11/30/97 4:26p John
42 * Added 32-bpp antialiased line. Took gamma out of alphacolor
45 * 8 11/29/97 2:06p John
46 * added mode 16-bpp support
48 * 7 10/20/97 8:47a John
49 * fixed gr_lock bug in aaline
51 * 6 10/19/97 12:55p John
52 * new code to lock / unlock surfaces for smooth directx integration.
54 * 5 10/14/97 8:08a John
55 * added a bunch more 16 bit support
57 * 4 10/04/97 11:27a John
60 * 3 10/03/97 9:50a John
61 * enabled antialiasing lines in alphacolor set.
63 * 2 10/03/97 9:10a John
64 * added better antialiased line drawer
66 * 1 10/03/97 9:07a John
73 Code for drawing antialiased lines. Taken from some code
74 published in the Journal of Graphic Tools at www.acm.org/jgt
76 Here is the README that came with the source code:
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.
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.
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
100 #include "grinternal.h"
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
111 #define FLOAT_TO_FIX_XY(x) ((long int) ((x) * (float) ONE_XY))
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)
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)
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
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
140 typedef long int fix_xy; // S11.20
142 // One vertex at any of the various stages of the pipeline
144 typedef struct aa_vertex {
148 // All values needed to draw one line
149 typedef struct aa_setup_line {
153 fix_xy vs; // Starting point
155 fix_xy ue; // End (along major axis)
156 fix_xy dvdu; // Delta for minor axis step
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];
166 ubyte new_table[F_TABLE_SIZE*512];
168 int aaline_inited = 0;
170 // Initialize the tables normally found in ROM in the hardware.
171 void aaline_init_tables()
173 int i,j; // Iterative counter
175 double d; // Distance from center of curve
176 double v; // Value to put in table
177 double sr; // The square root value
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.
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);
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);
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;
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));
217 sqrt_table[i] = (long int) (sr * (double) (1 << SR_FRACT));
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)
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)
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
261 sample_dist = (FRACT_XY(y) >> (FIX_XY_SHIFT - 5)) - 16;
263 filter_index = sample_dist + 32;
266 int yi = FIX_XY_TO_INT( y );
267 int xi = FIX_XY_TO_INT( x );
269 if ( xi < gr_screen.clip_left ) return;
270 if ( xi > gr_screen.clip_right ) return;
274 if ( yi < gr_screen.clip_top ) clipped++;
275 if ( yi+3 > gr_screen.clip_bottom ) clipped++;
277 long int corr_slope = (slope * ep_corr) & 0x1ff00;
279 ubyte * lookup = (ubyte *)&Current_alphacolor->table.lookup[0][0];
281 ubyte * filter_lookup = (ubyte *)&new_table[(corr_slope>>8)*F_TABLE_SIZE];
287 for (i = 0; i < 4; i++) {
288 if (filter_index < 0)
289 index = ~filter_index; // Invert when negative
291 index = filter_index;
293 if (index > INV_FILTER) {
295 return; // Not a valid pixel
298 //a = ((corr_slope * filter_table[index]) & 0xf00000) >> (16+4-8);
299 a = filter_lookup[index]<<8;
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);
305 *dptr = lookup[*dptr+a];
315 dptr = GR_SCREEN_PTR(ubyte,xi, yi);
317 for (i = 0; i < 4; i++) {
318 if (filter_index < 0)
319 index = ~filter_index; // Invert when negative
321 index = filter_index;
323 if (index > INV_FILTER) {
325 return; // Not a valid pixel
328 a = filter_lookup[index]<<8;
330 // Should include the alpha value as well...
331 *dptr = lookup[*dptr+a];
333 dptr += gr_screen.rowsize;
346 // Draw one span of an antialiased line (for vertical lines).
348 void draw_aa_vspan8(fix_xy x, fix_xy y, long int ep_corr, long int slope)
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
357 sample_dist = (FRACT_XY(x) >> (FIX_XY_SHIFT - 5)) - 16;
359 filter_index = sample_dist + 32;
361 int yi = FIX_XY_TO_INT( y );
362 int xi = FIX_XY_TO_INT( x );
364 if ( yi < gr_screen.clip_top ) return;
365 if ( yi > gr_screen.clip_bottom ) return;
369 if ( xi < gr_screen.clip_left ) clipped++;
370 if ( xi+3 > gr_screen.clip_right ) clipped++;
372 long int corr_slope = (slope * ep_corr) & 0x1ff00;
374 ubyte * lookup = (ubyte *)&Current_alphacolor->table.lookup[0][0];
376 ubyte * filter_lookup = (ubyte *)&new_table[(corr_slope>>8)*F_TABLE_SIZE];
382 for (i = 0; i < 4; i++) {
383 if (filter_index < 0)
384 index = ~filter_index; // Invert when negative
386 index = filter_index;
388 if (index > INV_FILTER) {
390 return; // Not a valid pixel
393 //a = ((corr_slope * filter_table[index]) & 0xf00000) >> (16+4-8);
394 a = filter_lookup[index]<<8;
397 if ( (xi >= gr_screen.clip_left) && (xi <= gr_screen.clip_right) ) {
398 dptr = GR_SCREEN_PTR(ubyte,xi, yi);
400 *dptr = lookup[*dptr+a];
408 ubyte *dptr = GR_SCREEN_PTR(ubyte,xi, yi);
410 for (i = 0; i < 4; i++) {
411 if (filter_index < 0)
412 index = ~filter_index; // Invert when negative
414 index = filter_index;
416 if (index > INV_FILTER) {
418 return; // Not a valid pixel
421 a = filter_lookup[index]<<8;
423 // Should include the alpha value as well...
426 *dptr = lookup[*dptr+a];
438 void draw_line(aa_setup_line *line)
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
454 if (line->negative) {
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;
473 count = FLOOR_XY(us) - FLOOR_XY(ue);
475 u_off = 0 - FRACT_XY(line->us);
477 ue = line->ue + ONE_XY;
478 count = FLOOR_XY(ue) - FLOOR_XY(us);
481 vs = line->vs + fix_xy_mult(line->dvdu, u_off) + ONEHALF_XY;
491 //a = line->as + fix_xy_mult(line->dadu, u_off);
493 // Compute slope correction once per line
494 slope_index = (line->dvdu >> (FIX_XY_SHIFT - 5)) & 0x3fu;
496 if (line->dvdu < 0) {
497 slope_index ^= 0x3fu;
500 if ((slope_index & 0x20u) == 0) {
501 slope = slope_corr_table[slope_index];
503 slope = 0x100; /* True 1.0 */
506 // Set up counters for determining endpoint regions
508 ecount = FIX_TO_INT_XY(count);
510 // Get 4-bit fractions for end-point adjustments
511 sf = (us & EP_MASK) >> EP_SHIFT;
512 ef = (ue & EP_MASK) >> EP_SHIFT;
514 // Interpolate the edges
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
530 ep_code = ((scount < 2) ? scount : 2) * 3 + ((ecount < 2) ? ecount : 2);
532 if (line->negative) {
534 // Drawing in the negative direction
536 // Compute endpoint information
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;
551 // Drawing in the positive direction
553 // Compute endpoint information
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;
569 draw_aa_hspan8(x, y, ep_corr, slope);
571 draw_aa_vspan8(x, y, ep_corr, slope);
586 // Perform the setup operation for a line, then draw it
588 void aaline_setup(aa_vertex *v1, aa_vertex *v2)
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
595 if ( !aaline_inited )
596 aaline_init_tables();
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);
622 line.dvdu = FLOAT_TO_FIX_XY(dy * one_du);
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);
631 line.dvdu = FLOAT_TO_FIX_XY(dx * one_du);
634 // Convert colors to fixed-point
635 //line.as = FLOAT_TO_FIX_RGB(v2->a);
637 // Compute delta values for colors
638 //line.dadu = FLOAT_TO_FIX_RGB((v1->a - v2->a) * one_du);
648 void gr8_aaline( vertex *v1, vertex *v2 )
652 if ( !Current_alphacolor ) {
653 gr_line(fl2i(v1->sx),fl2i(v1->sy),fl2i(v2->sx),fl2i(v2->sy));
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;
673 FL_CLIPLINE(aa1.x,aa1.y,aa2.x,aa2.y,a1,b1,a2,b2,return,clipped=1,swapped=1);
676 aaline_setup( &aa1, &aa2 );