2 * $Logfile: /Freespace2/code/Graphics/aaline.cpp $
7 * Code to draw antialiased lines
10 * Revision 1.3 2002/05/28 08:52:03 relnev
11 * implemented two assembly stubs.
13 * cleaned up a few warnings.
15 * added a little demo hackery to make it progress a little farther.
17 * Revision 1.2 2002/05/07 03:16:45 theoddone33
18 * The Great Newline Fix
20 * Revision 1.1.1.1 2002/05/03 03:28:09 root
24 * 3 12/02/98 5:47p Dave
25 * Put in interface xstr code. Converted barracks screen to new format.
27 * 2 10/07/98 10:52a Dave
30 * 1 10/07/98 10:48a Dave
32 * 13 5/06/98 5:30p John
33 * Removed unused cfilearchiver. Removed/replaced some unused/little used
34 * graphics functions, namely gradient_h and _v and pixel_sp. Put in new
35 * DirectX header files and libs that fixed the Direct3D alpha blending
38 * 12 3/24/98 4:03p Lawrance
39 * JOHN: Fix up outline drawing code to support different colors
41 * 11 3/10/98 4:18p John
42 * Cleaned up graphics lib. Took out most unused gr functions. Made D3D
43 * & Glide have popups and print screen. Took out all >8bpp software
44 * support. Made Fred zbuffer. Made zbuffer allocate dynamically to
45 * support Fred. Made zbuffering key off of functions rather than one
48 * 10 1/19/98 6:15p John
49 * Fixed all my Optimized Build compiler warnings
51 * 9 11/30/97 4:26p John
52 * Added 32-bpp antialiased line. Took gamma out of alphacolor
55 * 8 11/29/97 2:06p John
56 * added mode 16-bpp support
58 * 7 10/20/97 8:47a John
59 * fixed gr_lock bug in aaline
61 * 6 10/19/97 12:55p John
62 * new code to lock / unlock surfaces for smooth directx integration.
64 * 5 10/14/97 8:08a John
65 * added a bunch more 16 bit support
67 * 4 10/04/97 11:27a John
70 * 3 10/03/97 9:50a John
71 * enabled antialiasing lines in alphacolor set.
73 * 2 10/03/97 9:10a John
74 * added better antialiased line drawer
76 * 1 10/03/97 9:07a John
83 Code for drawing antialiased lines. Taken from some code
84 published in the Journal of Graphic Tools at www.acm.org/jgt
86 Here is the README that came with the source code:
88 Sample code to draw antialiased lines as described in the Journal of
89 Graphic Tools article High Quality Hardware Line Antialiasing by
90 Scott R. Nelson of Sun Microsystems.
92 The code is written in C and designed to run on any machine with the
93 addition of a proper "display" module. Currently, display modules
94 exist for Macintosh, Unix, and Wintel machines. Thanks to Sanjay Gupta
95 (sanjay.gupta@eng.sun.com) for the Unix X11 display code and Chris
96 Babcock (babcock@rtp.idt.com) for the Windows code.
98 This code is not 100% bug free and is definitely not optimized for
99 performance. It does, however, illustrate all of the points made in
110 #include "grinternal.h"
113 // Convert from floating-point to internal fixed-point formats
114 #define ONE_XY (long int) 0x00100000
115 #define FIX_XY_SHIFT (long int) 20
116 #define ONEHALF_XY (long int) 0x00080000
117 #define ONE_Z (long int) 0x40000000
118 #define ONE_RGB (long int) 0x40000000
119 #define ONE_16 (long int) 0x4000
121 #define FLOAT_TO_FIX_XY(x) ((long int) ((x) * (float) ONE_XY))
123 #define FLOAT_TO_FIX_RGB(x) ((long int) ((x) * (float) ONE_RGB))
124 #define FLOAT_TO_FIX_16(x) ((long int) ((x) * (float) ONE_16))
125 #define FIX_TO_INT_XY(x) ((x) >> FIX_XY_SHIFT)
126 #define FIX_16_TO_FLOAT(x) ((float) (x) / (float) ONE_16)
127 #define FIX_TO_FLOAT_XY(x) ((float) (x) / (float) ONE_XY)
128 #define FIX_TO_FLOAT_RGB(x) ((float) (x) / (float) ONE_RGB)
130 // Get fractional part, next lowest integer part
131 #define FRACT_XY(x) ((x) & (long int) 0x000fffff)
132 #define FLOOR_XY(x) ((x) & (long int) 0xfff00000)
133 #define FIX_XY_TO_INT(x) ((long int) (x) >> (long int) FIX_XY_SHIFT)
135 // Sizes for tables in Draw
136 #define FILTER_WIDTH 0.75 // Line filter width adjustment // .75 // .5 works good with 5.0 gamma
137 #define F_TABLE_SIZE 64 // Filter table size
138 #define SC_TABLE_SIZE 32 // Slope correction table size
139 #define SRT_INT 5 // Sqrt table index integer bits
140 #define SRT_FRACT 4 // ...fraction bits
141 #define SR_INT 3 // Square root result integer bits
142 #define SR_FRACT 5 // ...fraction bits
143 #define SR_TABLE_SIZE (1 << (SRT_INT + SRT_FRACT))
144 #define INV_FILTER 47
146 #define EP_MASK (long int) 0x000f0000u // AA line end-point filter mask
147 #define EP_SHIFT 13u // Number of bits to shift end-point
150 typedef long int fix_xy; // S11.20
152 // One vertex at any of the various stages of the pipeline
154 typedef struct aa_vertex {
158 // All values needed to draw one line
159 typedef struct aa_setup_line {
163 fix_xy vs; // Starting point
165 fix_xy ue; // End (along major axis)
166 fix_xy dvdu; // Delta for minor axis step
171 // Tables that need to be initialized
172 long int slope_corr_table[SC_TABLE_SIZE];
173 long int filter_table[F_TABLE_SIZE];
174 long int sqrt_table[SR_TABLE_SIZE];
176 ubyte new_table[F_TABLE_SIZE*512];
178 int aaline_inited = 0;
180 // Initialize the tables normally found in ROM in the hardware.
181 void aaline_init_tables()
183 int i,j; // Iterative counter
185 double d; // Distance from center of curve
186 double v; // Value to put in table
187 double sr; // The square root value
191 // Build slope correction table. The index into this table
192 // is the truncated 5-bit fraction of the slope used to draw
193 // the line. Round the computed values here to get the closest
194 // fit for all slopes matching an entry.
196 for (i = 0; i < SC_TABLE_SIZE; i++) {
197 // Round and make a fraction
198 m = ((double) i + 0.5) / (float) SC_TABLE_SIZE;
199 v = sqrt(m * m + 1) * 0.707106781; /* (m + 1)^2 / sqrt(2) */
200 slope_corr_table[i] = (long int) (v * 256.0);
203 // Build the Gaussian filter table, round to the middle of the sample region.
204 for (i = 0; i < F_TABLE_SIZE; i++) {
205 d = ((double) i + 0.5) / (float) (F_TABLE_SIZE / 2.0);
206 d = d / FILTER_WIDTH;
207 v = 1.0 / exp(d * d); // Gaussian function
208 filter_table[i] = (long int) (v * 256.0);
211 for ( i=0; i<512; i++ ) {
212 long int corr_slope = i<<8;
213 for (j=0; j<F_TABLE_SIZE; j++ ) {
214 new_table[i*F_TABLE_SIZE+j] = (ubyte)(((corr_slope * filter_table[j]) & 0xf00000) >> (16+4));
215 if (new_table[i*F_TABLE_SIZE+j]==15 ) {
216 // HACK!!! Account for "glass" pixel for hud bitmaps.
217 new_table[i*F_TABLE_SIZE+j] = 14;
223 // Build the square root table for big dots.
224 for (i = 0; i < SR_TABLE_SIZE; i++) {
225 v = (double) ((i << 1) + 1) / (double) (1 << (SRT_FRACT + 1));
227 sqrt_table[i] = (long int) (sr * (double) (1 << SR_FRACT));
235 // Multiply a fixed-point number by a s11.20 fixed-point
236 // number. The actual multiply uses less bits for the
237 // multiplier, since it always represents a fraction
238 // less than 1.0 and less total bits are sufficient.
239 // Some of the steps here are not needed. This was originally
240 // written to simulate exact hardware behavior.
241 long int fix_xy_mult(long int oa, fix_xy ob)
248 __asm__("imul %2 \n\t"
249 "shrd $20, %%edx, %%eax \n\t"
268 // Draw one span of an antialiased line (for horizontal lines).
269 void draw_aa_hspan8(fix_xy x, fix_xy y, long int ep_corr, long int slope)
271 #ifndef HARDWARE_ONLY
272 long int sample_dist; // Distance from line to sample point
273 long int filter_index; // Index into filter table
274 long int i; // Count pixels across span
275 long int index; // Final filter table index
278 sample_dist = (FRACT_XY(y) >> (FIX_XY_SHIFT - 5)) - 16;
280 filter_index = sample_dist + 32;
283 int yi = FIX_XY_TO_INT( y );
284 int xi = FIX_XY_TO_INT( x );
286 if ( xi < gr_screen.clip_left ) return;
287 if ( xi > gr_screen.clip_right ) return;
291 if ( yi < gr_screen.clip_top ) clipped++;
292 if ( yi+3 > gr_screen.clip_bottom ) clipped++;
294 long int corr_slope = (slope * ep_corr) & 0x1ff00;
296 ubyte * lookup = (ubyte *)&Current_alphacolor->table.lookup[0][0];
298 ubyte * filter_lookup = (ubyte *)&new_table[(corr_slope>>8)*F_TABLE_SIZE];
304 for (i = 0; i < 4; i++) {
305 if (filter_index < 0)
306 index = ~filter_index; // Invert when negative
308 index = filter_index;
310 if (index > INV_FILTER) {
312 return; // Not a valid pixel
315 //a = ((corr_slope * filter_table[index]) & 0xf00000) >> (16+4-8);
316 a = filter_lookup[index]<<8;
318 // Should include the alpha value as well...
319 if ( (yi >= gr_screen.clip_top) && (yi <= gr_screen.clip_bottom) ) {
320 dptr = GR_SCREEN_PTR(ubyte,xi, yi);
322 *dptr = lookup[*dptr+a];
332 dptr = GR_SCREEN_PTR(ubyte,xi, yi);
334 for (i = 0; i < 4; i++) {
335 if (filter_index < 0)
336 index = ~filter_index; // Invert when negative
338 index = filter_index;
340 if (index > INV_FILTER) {
342 return; // Not a valid pixel
345 a = filter_lookup[index]<<8;
347 // Should include the alpha value as well...
348 *dptr = lookup[*dptr+a];
350 dptr += gr_screen.rowsize;
363 // Draw one span of an antialiased line (for vertical lines).
365 void draw_aa_vspan8(fix_xy x, fix_xy y, long int ep_corr, long int slope)
367 #ifndef HARDWARE_ONLY
368 long int sample_dist; // Distance from line to sample point
369 long int filter_index; // Index into filter table
370 long int i; // Count pixels across span
371 long int index; // Final filter table index
374 sample_dist = (FRACT_XY(x) >> (FIX_XY_SHIFT - 5)) - 16;
376 filter_index = sample_dist + 32;
378 int yi = FIX_XY_TO_INT( y );
379 int xi = FIX_XY_TO_INT( x );
381 if ( yi < gr_screen.clip_top ) return;
382 if ( yi > gr_screen.clip_bottom ) return;
386 if ( xi < gr_screen.clip_left ) clipped++;
387 if ( xi+3 > gr_screen.clip_right ) clipped++;
389 long int corr_slope = (slope * ep_corr) & 0x1ff00;
391 ubyte * lookup = (ubyte *)&Current_alphacolor->table.lookup[0][0];
393 ubyte * filter_lookup = (ubyte *)&new_table[(corr_slope>>8)*F_TABLE_SIZE];
399 for (i = 0; i < 4; i++) {
400 if (filter_index < 0)
401 index = ~filter_index; // Invert when negative
403 index = filter_index;
405 if (index > INV_FILTER) {
407 return; // Not a valid pixel
410 //a = ((corr_slope * filter_table[index]) & 0xf00000) >> (16+4-8);
411 a = filter_lookup[index]<<8;
414 if ( (xi >= gr_screen.clip_left) && (xi <= gr_screen.clip_right) ) {
415 dptr = GR_SCREEN_PTR(ubyte,xi, yi);
417 *dptr = lookup[*dptr+a];
425 ubyte *dptr = GR_SCREEN_PTR(ubyte,xi, yi);
427 for (i = 0; i < 4; i++) {
428 if (filter_index < 0)
429 index = ~filter_index; // Invert when negative
431 index = filter_index;
433 if (index > INV_FILTER) {
435 return; // Not a valid pixel
438 a = filter_lookup[index]<<8;
440 // Should include the alpha value as well...
443 *dptr = lookup[*dptr+a];
455 void draw_line(aa_setup_line *line)
457 fix_xy x, y; // Start value
458 fix_xy dudu; // Constant 1 or -1 for step
459 fix_xy dx, dy; // Steps in X and Y
460 fix_xy u_off; // Offset to starting sample grid
461 fix_xy us, vs, ue; // Start and end for drawing
462 fix_xy count; // How many pixels to draw
463 long int slope_index; // Index into slope correction table
464 long int slope; // Slope correction value
465 long int ep_corr; // End-point correction value
466 long int scount, ecount; // Start/end count for endpoints
467 long int sf, ef; // Sand and end fractions
468 long int ep_code; // One of 9 endpoint codes
471 if (line->negative) {
485 // Get initial values and count
486 if (line->negative) {
487 u_off = FRACT_XY(line->us) - ONE_XY;
488 us = line->us + ONE_XY;
490 count = FLOOR_XY(us) - FLOOR_XY(ue);
492 u_off = 0 - FRACT_XY(line->us);
494 ue = line->ue + ONE_XY;
495 count = FLOOR_XY(ue) - FLOOR_XY(us);
498 vs = line->vs + fix_xy_mult(line->dvdu, u_off) + ONEHALF_XY;
508 //a = line->as + fix_xy_mult(line->dadu, u_off);
510 // Compute slope correction once per line
511 slope_index = (line->dvdu >> (FIX_XY_SHIFT - 5)) & 0x3fu;
513 if (line->dvdu < 0) {
514 slope_index ^= 0x3fu;
517 if ((slope_index & 0x20u) == 0) {
518 slope = slope_corr_table[slope_index];
520 slope = 0x100; /* True 1.0 */
523 // Set up counters for determining endpoint regions
525 ecount = FIX_TO_INT_XY(count);
527 // Get 4-bit fractions for end-point adjustments
528 sf = (us & EP_MASK) >> EP_SHIFT;
529 ef = (ue & EP_MASK) >> EP_SHIFT;
531 // Interpolate the edges
535 * Compute end-point code (defined as follows):
536 * 0 = 0, 0: short, no boundary crossing
537 * 1 = 0, 1: short line overlap (< 1.0)
538 * 2 = 0, 2: 1st pixel of 1st endpoint
539 * 3 = 1, 0: short line overlap (< 1.0)
540 * 4 = 1, 1: short line overlap (> 1.0)
541 * 5 = 1, 2: 2nd pixel of 1st endpoint
542 * 6 = 2, 0: last of 2nd endpoint
543 * 7 = 2, 1: first of 2nd endpoint
544 * 8 = 2, 2: regular part of line
547 ep_code = ((scount < 2) ? scount : 2) * 3 + ((ecount < 2) ? ecount : 2);
549 if (line->negative) {
551 // Drawing in the negative direction
553 // Compute endpoint information
555 case 0: ep_corr = 0; break;
556 case 1: ep_corr = ((sf - ef) & 0x78) | 4; break;
557 case 2: ep_corr = sf | 4; break;
558 case 3: ep_corr = ((sf - ef) & 0x78) | 4; break;
559 case 4: ep_corr = ((sf - ef) + 0x80) | 4; break;
560 case 5: ep_corr = (sf + 0x80) | 4; break;
561 case 6: ep_corr = (0x78 - ef) | 4; break;
562 case 7: ep_corr = ((0x78 - ef) + 0x80) | 4; break;
563 case 8: ep_corr = 0x100; break;
564 default: ep_corr = 0; break;
568 // Drawing in the positive direction
570 // Compute endpoint information
572 case 0: ep_corr = 0; break;
573 case 1: ep_corr = ((ef - sf) & 0x78) | 4; break;
574 case 2: ep_corr = (0x78 - sf) | 4; break;
575 case 3: ep_corr = ((ef - sf) & 0x78) | 4; break;
576 case 4: ep_corr = ((ef - sf) + 0x80) | 4; break;
577 case 5: ep_corr = ((0x78 - sf) + 0x80) | 4; break;
578 case 6: ep_corr = ef | 4; break;
579 case 7: ep_corr = (ef + 0x80) | 4; break;
580 case 8: ep_corr = 0x100; break;
581 default: ep_corr = 0; break;
586 draw_aa_hspan8(x, y, ep_corr, slope);
588 draw_aa_vspan8(x, y, ep_corr, slope);
603 // Perform the setup operation for a line, then draw it
605 void aaline_setup(aa_vertex *v1, aa_vertex *v2)
607 float dx, dy; // Deltas in X and Y
608 float udx, udy; // Positive version of deltas
609 float one_du; // 1.0 / udx or udy
612 if ( !aaline_inited )
613 aaline_init_tables();
634 line.negative = (dx < 0.0);
635 line.us = FLOAT_TO_FIX_XY(v2->x);
636 line.vs = FLOAT_TO_FIX_XY(v2->y);
637 line.ue = FLOAT_TO_FIX_XY(v1->x);
639 line.dvdu = FLOAT_TO_FIX_XY(dy * one_du);
643 line.negative = (dy < 0.0);
644 line.us = FLOAT_TO_FIX_XY(v2->y);
645 line.vs = FLOAT_TO_FIX_XY(v2->x);
646 line.ue = FLOAT_TO_FIX_XY(v1->y);
648 line.dvdu = FLOAT_TO_FIX_XY(dx * one_du);
651 // Convert colors to fixed-point
652 //line.as = FLOAT_TO_FIX_RGB(v2->a);
654 // Compute delta values for colors
655 //line.dadu = FLOAT_TO_FIX_RGB((v1->a - v2->a) * one_du);
665 void gr8_aaline( vertex *v1, vertex *v2 )
669 if ( !Current_alphacolor ) {
670 gr_line(fl2i(v1->sx),fl2i(v1->sy),fl2i(v2->sx),fl2i(v2->sy));
683 int clipped = 0, swapped = 0;
684 float a1, b1, a2, b2;
685 a1 = (float)gr_screen.clip_left;
686 b1 = (float)gr_screen.clip_top;
687 a2 = (float)gr_screen.clip_right;
688 b2 = (float)gr_screen.clip_bottom;
690 FL_CLIPLINE(aa1.x,aa1.y,aa2.x,aa2.y,a1,b1,a2,b2,return,clipped=1,swapped=1);
693 aaline_setup( &aa1, &aa2 );