2 * $Logfile: /Freespace2/code/Graphics/aaline.cpp $
7 * Code to draw antialiased lines
10 * Revision 1.4 2002/06/09 03:16:04 relnev
13 * removed unneeded asm, old sdl 2d setup.
15 * fixed crash caused by opengl_get_region.
17 * Revision 1.3 2002/05/28 08:52:03 relnev
18 * implemented two assembly stubs.
20 * cleaned up a few warnings.
22 * added a little demo hackery to make it progress a little farther.
24 * Revision 1.2 2002/05/07 03:16:45 theoddone33
25 * The Great Newline Fix
27 * Revision 1.1.1.1 2002/05/03 03:28:09 root
31 * 3 12/02/98 5:47p Dave
32 * Put in interface xstr code. Converted barracks screen to new format.
34 * 2 10/07/98 10:52a Dave
37 * 1 10/07/98 10:48a Dave
39 * 13 5/06/98 5:30p John
40 * Removed unused cfilearchiver. Removed/replaced some unused/little used
41 * graphics functions, namely gradient_h and _v and pixel_sp. Put in new
42 * DirectX header files and libs that fixed the Direct3D alpha blending
45 * 12 3/24/98 4:03p Lawrance
46 * JOHN: Fix up outline drawing code to support different colors
48 * 11 3/10/98 4:18p John
49 * Cleaned up graphics lib. Took out most unused gr functions. Made D3D
50 * & Glide have popups and print screen. Took out all >8bpp software
51 * support. Made Fred zbuffer. Made zbuffer allocate dynamically to
52 * support Fred. Made zbuffering key off of functions rather than one
55 * 10 1/19/98 6:15p John
56 * Fixed all my Optimized Build compiler warnings
58 * 9 11/30/97 4:26p John
59 * Added 32-bpp antialiased line. Took gamma out of alphacolor
62 * 8 11/29/97 2:06p John
63 * added mode 16-bpp support
65 * 7 10/20/97 8:47a John
66 * fixed gr_lock bug in aaline
68 * 6 10/19/97 12:55p John
69 * new code to lock / unlock surfaces for smooth directx integration.
71 * 5 10/14/97 8:08a John
72 * added a bunch more 16 bit support
74 * 4 10/04/97 11:27a John
77 * 3 10/03/97 9:50a John
78 * enabled antialiasing lines in alphacolor set.
80 * 2 10/03/97 9:10a John
81 * added better antialiased line drawer
83 * 1 10/03/97 9:07a John
90 Code for drawing antialiased lines. Taken from some code
91 published in the Journal of Graphic Tools at www.acm.org/jgt
93 Here is the README that came with the source code:
95 Sample code to draw antialiased lines as described in the Journal of
96 Graphic Tools article High Quality Hardware Line Antialiasing by
97 Scott R. Nelson of Sun Microsystems.
99 The code is written in C and designed to run on any machine with the
100 addition of a proper "display" module. Currently, display modules
101 exist for Macintosh, Unix, and Wintel machines. Thanks to Sanjay Gupta
102 (sanjay.gupta@eng.sun.com) for the Unix X11 display code and Chris
103 Babcock (babcock@rtp.idt.com) for the Windows code.
105 This code is not 100% bug free and is definitely not optimized for
106 performance. It does, however, illustrate all of the points made in
117 #include "grinternal.h"
120 // Convert from floating-point to internal fixed-point formats
121 #define ONE_XY (long int) 0x00100000
122 #define FIX_XY_SHIFT (long int) 20
123 #define ONEHALF_XY (long int) 0x00080000
124 #define ONE_Z (long int) 0x40000000
125 #define ONE_RGB (long int) 0x40000000
126 #define ONE_16 (long int) 0x4000
128 #define FLOAT_TO_FIX_XY(x) ((long int) ((x) * (float) ONE_XY))
130 #define FLOAT_TO_FIX_RGB(x) ((long int) ((x) * (float) ONE_RGB))
131 #define FLOAT_TO_FIX_16(x) ((long int) ((x) * (float) ONE_16))
132 #define FIX_TO_INT_XY(x) ((x) >> FIX_XY_SHIFT)
133 #define FIX_16_TO_FLOAT(x) ((float) (x) / (float) ONE_16)
134 #define FIX_TO_FLOAT_XY(x) ((float) (x) / (float) ONE_XY)
135 #define FIX_TO_FLOAT_RGB(x) ((float) (x) / (float) ONE_RGB)
137 // Get fractional part, next lowest integer part
138 #define FRACT_XY(x) ((x) & (long int) 0x000fffff)
139 #define FLOOR_XY(x) ((x) & (long int) 0xfff00000)
140 #define FIX_XY_TO_INT(x) ((long int) (x) >> (long int) FIX_XY_SHIFT)
142 // Sizes for tables in Draw
143 #define FILTER_WIDTH 0.75 // Line filter width adjustment // .75 // .5 works good with 5.0 gamma
144 #define F_TABLE_SIZE 64 // Filter table size
145 #define SC_TABLE_SIZE 32 // Slope correction table size
146 #define SRT_INT 5 // Sqrt table index integer bits
147 #define SRT_FRACT 4 // ...fraction bits
148 #define SR_INT 3 // Square root result integer bits
149 #define SR_FRACT 5 // ...fraction bits
150 #define SR_TABLE_SIZE (1 << (SRT_INT + SRT_FRACT))
151 #define INV_FILTER 47
153 #define EP_MASK (long int) 0x000f0000u // AA line end-point filter mask
154 #define EP_SHIFT 13u // Number of bits to shift end-point
157 typedef long int fix_xy; // S11.20
159 // One vertex at any of the various stages of the pipeline
161 typedef struct aa_vertex {
165 // All values needed to draw one line
166 typedef struct aa_setup_line {
170 fix_xy vs; // Starting point
172 fix_xy ue; // End (along major axis)
173 fix_xy dvdu; // Delta for minor axis step
178 // Tables that need to be initialized
179 long int slope_corr_table[SC_TABLE_SIZE];
180 long int filter_table[F_TABLE_SIZE];
181 long int sqrt_table[SR_TABLE_SIZE];
183 ubyte new_table[F_TABLE_SIZE*512];
185 int aaline_inited = 0;
187 // Initialize the tables normally found in ROM in the hardware.
188 void aaline_init_tables()
190 int i,j; // Iterative counter
192 double d; // Distance from center of curve
193 double v; // Value to put in table
194 double sr; // The square root value
198 // Build slope correction table. The index into this table
199 // is the truncated 5-bit fraction of the slope used to draw
200 // the line. Round the computed values here to get the closest
201 // fit for all slopes matching an entry.
203 for (i = 0; i < SC_TABLE_SIZE; i++) {
204 // Round and make a fraction
205 m = ((double) i + 0.5) / (float) SC_TABLE_SIZE;
206 v = sqrt(m * m + 1) * 0.707106781; /* (m + 1)^2 / sqrt(2) */
207 slope_corr_table[i] = (long int) (v * 256.0);
210 // Build the Gaussian filter table, round to the middle of the sample region.
211 for (i = 0; i < F_TABLE_SIZE; i++) {
212 d = ((double) i + 0.5) / (float) (F_TABLE_SIZE / 2.0);
213 d = d / FILTER_WIDTH;
214 v = 1.0 / exp(d * d); // Gaussian function
215 filter_table[i] = (long int) (v * 256.0);
218 for ( i=0; i<512; i++ ) {
219 long int corr_slope = i<<8;
220 for (j=0; j<F_TABLE_SIZE; j++ ) {
221 new_table[i*F_TABLE_SIZE+j] = (ubyte)(((corr_slope * filter_table[j]) & 0xf00000) >> (16+4));
222 if (new_table[i*F_TABLE_SIZE+j]==15 ) {
223 // HACK!!! Account for "glass" pixel for hud bitmaps.
224 new_table[i*F_TABLE_SIZE+j] = 14;
230 // Build the square root table for big dots.
231 for (i = 0; i < SR_TABLE_SIZE; i++) {
232 v = (double) ((i << 1) + 1) / (double) (1 << (SRT_FRACT + 1));
234 sqrt_table[i] = (long int) (sr * (double) (1 << SR_FRACT));
242 // Multiply a fixed-point number by a s11.20 fixed-point
243 // number. The actual multiply uses less bits for the
244 // multiplier, since it always represents a fraction
245 // less than 1.0 and less total bits are sufficient.
246 // Some of the steps here are not needed. This was originally
247 // written to simulate exact hardware behavior.
248 long int fix_xy_mult(long int oa, fix_xy ob)
271 // Draw one span of an antialiased line (for horizontal lines).
272 void draw_aa_hspan8(fix_xy x, fix_xy y, long int ep_corr, long int slope)
274 #ifndef HARDWARE_ONLY
275 long int sample_dist; // Distance from line to sample point
276 long int filter_index; // Index into filter table
277 long int i; // Count pixels across span
278 long int index; // Final filter table index
281 sample_dist = (FRACT_XY(y) >> (FIX_XY_SHIFT - 5)) - 16;
283 filter_index = sample_dist + 32;
286 int yi = FIX_XY_TO_INT( y );
287 int xi = FIX_XY_TO_INT( x );
289 if ( xi < gr_screen.clip_left ) return;
290 if ( xi > gr_screen.clip_right ) return;
294 if ( yi < gr_screen.clip_top ) clipped++;
295 if ( yi+3 > gr_screen.clip_bottom ) clipped++;
297 long int corr_slope = (slope * ep_corr) & 0x1ff00;
299 ubyte * lookup = (ubyte *)&Current_alphacolor->table.lookup[0][0];
301 ubyte * filter_lookup = (ubyte *)&new_table[(corr_slope>>8)*F_TABLE_SIZE];
307 for (i = 0; i < 4; i++) {
308 if (filter_index < 0)
309 index = ~filter_index; // Invert when negative
311 index = filter_index;
313 if (index > INV_FILTER) {
315 return; // Not a valid pixel
318 //a = ((corr_slope * filter_table[index]) & 0xf00000) >> (16+4-8);
319 a = filter_lookup[index]<<8;
321 // Should include the alpha value as well...
322 if ( (yi >= gr_screen.clip_top) && (yi <= gr_screen.clip_bottom) ) {
323 dptr = GR_SCREEN_PTR(ubyte,xi, yi);
325 *dptr = lookup[*dptr+a];
335 dptr = GR_SCREEN_PTR(ubyte,xi, yi);
337 for (i = 0; i < 4; i++) {
338 if (filter_index < 0)
339 index = ~filter_index; // Invert when negative
341 index = filter_index;
343 if (index > INV_FILTER) {
345 return; // Not a valid pixel
348 a = filter_lookup[index]<<8;
350 // Should include the alpha value as well...
351 *dptr = lookup[*dptr+a];
353 dptr += gr_screen.rowsize;
366 // Draw one span of an antialiased line (for vertical lines).
368 void draw_aa_vspan8(fix_xy x, fix_xy y, long int ep_corr, long int slope)
370 #ifndef HARDWARE_ONLY
371 long int sample_dist; // Distance from line to sample point
372 long int filter_index; // Index into filter table
373 long int i; // Count pixels across span
374 long int index; // Final filter table index
377 sample_dist = (FRACT_XY(x) >> (FIX_XY_SHIFT - 5)) - 16;
379 filter_index = sample_dist + 32;
381 int yi = FIX_XY_TO_INT( y );
382 int xi = FIX_XY_TO_INT( x );
384 if ( yi < gr_screen.clip_top ) return;
385 if ( yi > gr_screen.clip_bottom ) return;
389 if ( xi < gr_screen.clip_left ) clipped++;
390 if ( xi+3 > gr_screen.clip_right ) clipped++;
392 long int corr_slope = (slope * ep_corr) & 0x1ff00;
394 ubyte * lookup = (ubyte *)&Current_alphacolor->table.lookup[0][0];
396 ubyte * filter_lookup = (ubyte *)&new_table[(corr_slope>>8)*F_TABLE_SIZE];
402 for (i = 0; i < 4; i++) {
403 if (filter_index < 0)
404 index = ~filter_index; // Invert when negative
406 index = filter_index;
408 if (index > INV_FILTER) {
410 return; // Not a valid pixel
413 //a = ((corr_slope * filter_table[index]) & 0xf00000) >> (16+4-8);
414 a = filter_lookup[index]<<8;
417 if ( (xi >= gr_screen.clip_left) && (xi <= gr_screen.clip_right) ) {
418 dptr = GR_SCREEN_PTR(ubyte,xi, yi);
420 *dptr = lookup[*dptr+a];
428 ubyte *dptr = GR_SCREEN_PTR(ubyte,xi, yi);
430 for (i = 0; i < 4; i++) {
431 if (filter_index < 0)
432 index = ~filter_index; // Invert when negative
434 index = filter_index;
436 if (index > INV_FILTER) {
438 return; // Not a valid pixel
441 a = filter_lookup[index]<<8;
443 // Should include the alpha value as well...
446 *dptr = lookup[*dptr+a];
458 void draw_line(aa_setup_line *line)
460 fix_xy x, y; // Start value
461 fix_xy dudu; // Constant 1 or -1 for step
462 fix_xy dx, dy; // Steps in X and Y
463 fix_xy u_off; // Offset to starting sample grid
464 fix_xy us, vs, ue; // Start and end for drawing
465 fix_xy count; // How many pixels to draw
466 long int slope_index; // Index into slope correction table
467 long int slope; // Slope correction value
468 long int ep_corr; // End-point correction value
469 long int scount, ecount; // Start/end count for endpoints
470 long int sf, ef; // Sand and end fractions
471 long int ep_code; // One of 9 endpoint codes
474 if (line->negative) {
488 // Get initial values and count
489 if (line->negative) {
490 u_off = FRACT_XY(line->us) - ONE_XY;
491 us = line->us + ONE_XY;
493 count = FLOOR_XY(us) - FLOOR_XY(ue);
495 u_off = 0 - FRACT_XY(line->us);
497 ue = line->ue + ONE_XY;
498 count = FLOOR_XY(ue) - FLOOR_XY(us);
501 vs = line->vs + fix_xy_mult(line->dvdu, u_off) + ONEHALF_XY;
511 //a = line->as + fix_xy_mult(line->dadu, u_off);
513 // Compute slope correction once per line
514 slope_index = (line->dvdu >> (FIX_XY_SHIFT - 5)) & 0x3fu;
516 if (line->dvdu < 0) {
517 slope_index ^= 0x3fu;
520 if ((slope_index & 0x20u) == 0) {
521 slope = slope_corr_table[slope_index];
523 slope = 0x100; /* True 1.0 */
526 // Set up counters for determining endpoint regions
528 ecount = FIX_TO_INT_XY(count);
530 // Get 4-bit fractions for end-point adjustments
531 sf = (us & EP_MASK) >> EP_SHIFT;
532 ef = (ue & EP_MASK) >> EP_SHIFT;
534 // Interpolate the edges
538 * Compute end-point code (defined as follows):
539 * 0 = 0, 0: short, no boundary crossing
540 * 1 = 0, 1: short line overlap (< 1.0)
541 * 2 = 0, 2: 1st pixel of 1st endpoint
542 * 3 = 1, 0: short line overlap (< 1.0)
543 * 4 = 1, 1: short line overlap (> 1.0)
544 * 5 = 1, 2: 2nd pixel of 1st endpoint
545 * 6 = 2, 0: last of 2nd endpoint
546 * 7 = 2, 1: first of 2nd endpoint
547 * 8 = 2, 2: regular part of line
550 ep_code = ((scount < 2) ? scount : 2) * 3 + ((ecount < 2) ? ecount : 2);
552 if (line->negative) {
554 // Drawing in the negative direction
556 // Compute endpoint information
558 case 0: ep_corr = 0; break;
559 case 1: ep_corr = ((sf - ef) & 0x78) | 4; break;
560 case 2: ep_corr = sf | 4; break;
561 case 3: ep_corr = ((sf - ef) & 0x78) | 4; break;
562 case 4: ep_corr = ((sf - ef) + 0x80) | 4; break;
563 case 5: ep_corr = (sf + 0x80) | 4; break;
564 case 6: ep_corr = (0x78 - ef) | 4; break;
565 case 7: ep_corr = ((0x78 - ef) + 0x80) | 4; break;
566 case 8: ep_corr = 0x100; break;
567 default: ep_corr = 0; break;
571 // Drawing in the positive direction
573 // Compute endpoint information
575 case 0: ep_corr = 0; break;
576 case 1: ep_corr = ((ef - sf) & 0x78) | 4; break;
577 case 2: ep_corr = (0x78 - sf) | 4; break;
578 case 3: ep_corr = ((ef - sf) & 0x78) | 4; break;
579 case 4: ep_corr = ((ef - sf) + 0x80) | 4; break;
580 case 5: ep_corr = ((0x78 - sf) + 0x80) | 4; break;
581 case 6: ep_corr = ef | 4; break;
582 case 7: ep_corr = (ef + 0x80) | 4; break;
583 case 8: ep_corr = 0x100; break;
584 default: ep_corr = 0; break;
589 draw_aa_hspan8(x, y, ep_corr, slope);
591 draw_aa_vspan8(x, y, ep_corr, slope);
606 // Perform the setup operation for a line, then draw it
608 void aaline_setup(aa_vertex *v1, aa_vertex *v2)
610 float dx, dy; // Deltas in X and Y
611 float udx, udy; // Positive version of deltas
612 float one_du; // 1.0 / udx or udy
615 if ( !aaline_inited )
616 aaline_init_tables();
637 line.negative = (dx < 0.0);
638 line.us = FLOAT_TO_FIX_XY(v2->x);
639 line.vs = FLOAT_TO_FIX_XY(v2->y);
640 line.ue = FLOAT_TO_FIX_XY(v1->x);
642 line.dvdu = FLOAT_TO_FIX_XY(dy * one_du);
646 line.negative = (dy < 0.0);
647 line.us = FLOAT_TO_FIX_XY(v2->y);
648 line.vs = FLOAT_TO_FIX_XY(v2->x);
649 line.ue = FLOAT_TO_FIX_XY(v1->y);
651 line.dvdu = FLOAT_TO_FIX_XY(dx * one_du);
654 // Convert colors to fixed-point
655 //line.as = FLOAT_TO_FIX_RGB(v2->a);
657 // Compute delta values for colors
658 //line.dadu = FLOAT_TO_FIX_RGB((v1->a - v2->a) * one_du);
668 void gr8_aaline( vertex *v1, vertex *v2 )
672 if ( !Current_alphacolor ) {
673 gr_line(fl2i(v1->sx),fl2i(v1->sy),fl2i(v2->sx),fl2i(v2->sy));
686 int clipped = 0, swapped = 0;
687 float a1, b1, a2, b2;
688 a1 = (float)gr_screen.clip_left;
689 b1 = (float)gr_screen.clip_top;
690 a2 = (float)gr_screen.clip_right;
691 b2 = (float)gr_screen.clip_bottom;
693 FL_CLIPLINE(aa1.x,aa1.y,aa2.x,aa2.y,a1,b1,a2,b2,return,clipped=1,swapped=1);
696 aaline_setup( &aa1, &aa2 );