2 * Copyright (C) Volition, Inc. 1999. All rights reserved.
4 * All source code herein is the property of Volition, Inc. You may not sell
5 * or otherwise commercially exploit the source or things you created based on
10 * $Logfile: /Freespace2/code/Graphics/aaline.cpp $
15 * Code to draw antialiased lines
18 * Revision 1.5 2002/06/09 04:41:17 relnev
19 * added copyright header
21 * Revision 1.4 2002/06/09 03:16:04 relnev
24 * removed unneeded asm, old sdl 2d setup.
26 * fixed crash caused by opengl_get_region.
28 * Revision 1.3 2002/05/28 08:52:03 relnev
29 * implemented two assembly stubs.
31 * cleaned up a few warnings.
33 * added a little demo hackery to make it progress a little farther.
35 * Revision 1.2 2002/05/07 03:16:45 theoddone33
36 * The Great Newline Fix
38 * Revision 1.1.1.1 2002/05/03 03:28:09 root
42 * 3 12/02/98 5:47p Dave
43 * Put in interface xstr code. Converted barracks screen to new format.
45 * 2 10/07/98 10:52a Dave
48 * 1 10/07/98 10:48a Dave
50 * 13 5/06/98 5:30p John
51 * Removed unused cfilearchiver. Removed/replaced some unused/little used
52 * graphics functions, namely gradient_h and _v and pixel_sp. Put in new
53 * DirectX header files and libs that fixed the Direct3D alpha blending
56 * 12 3/24/98 4:03p Lawrance
57 * JOHN: Fix up outline drawing code to support different colors
59 * 11 3/10/98 4:18p John
60 * Cleaned up graphics lib. Took out most unused gr functions. Made D3D
61 * & Glide have popups and print screen. Took out all >8bpp software
62 * support. Made Fred zbuffer. Made zbuffer allocate dynamically to
63 * support Fred. Made zbuffering key off of functions rather than one
66 * 10 1/19/98 6:15p John
67 * Fixed all my Optimized Build compiler warnings
69 * 9 11/30/97 4:26p John
70 * Added 32-bpp antialiased line. Took gamma out of alphacolor
73 * 8 11/29/97 2:06p John
74 * added mode 16-bpp support
76 * 7 10/20/97 8:47a John
77 * fixed gr_lock bug in aaline
79 * 6 10/19/97 12:55p John
80 * new code to lock / unlock surfaces for smooth directx integration.
82 * 5 10/14/97 8:08a John
83 * added a bunch more 16 bit support
85 * 4 10/04/97 11:27a John
88 * 3 10/03/97 9:50a John
89 * enabled antialiasing lines in alphacolor set.
91 * 2 10/03/97 9:10a John
92 * added better antialiased line drawer
94 * 1 10/03/97 9:07a John
101 Code for drawing antialiased lines. Taken from some code
102 published in the Journal of Graphic Tools at www.acm.org/jgt
104 Here is the README that came with the source code:
106 Sample code to draw antialiased lines as described in the Journal of
107 Graphic Tools article High Quality Hardware Line Antialiasing by
108 Scott R. Nelson of Sun Microsystems.
110 The code is written in C and designed to run on any machine with the
111 addition of a proper "display" module. Currently, display modules
112 exist for Macintosh, Unix, and Wintel machines. Thanks to Sanjay Gupta
113 (sanjay.gupta@eng.sun.com) for the Unix X11 display code and Chris
114 Babcock (babcock@rtp.idt.com) for the Windows code.
116 This code is not 100% bug free and is definitely not optimized for
117 performance. It does, however, illustrate all of the points made in
128 #include "grinternal.h"
131 // Convert from floating-point to internal fixed-point formats
132 #define ONE_XY (long int) 0x00100000
133 #define FIX_XY_SHIFT (long int) 20
134 #define ONEHALF_XY (long int) 0x00080000
135 #define ONE_Z (long int) 0x40000000
136 #define ONE_RGB (long int) 0x40000000
137 #define ONE_16 (long int) 0x4000
139 #define FLOAT_TO_FIX_XY(x) ((long int) ((x) * (float) ONE_XY))
141 #define FLOAT_TO_FIX_RGB(x) ((long int) ((x) * (float) ONE_RGB))
142 #define FLOAT_TO_FIX_16(x) ((long int) ((x) * (float) ONE_16))
143 #define FIX_TO_INT_XY(x) ((x) >> FIX_XY_SHIFT)
144 #define FIX_16_TO_FLOAT(x) ((float) (x) / (float) ONE_16)
145 #define FIX_TO_FLOAT_XY(x) ((float) (x) / (float) ONE_XY)
146 #define FIX_TO_FLOAT_RGB(x) ((float) (x) / (float) ONE_RGB)
148 // Get fractional part, next lowest integer part
149 #define FRACT_XY(x) ((x) & (long int) 0x000fffff)
150 #define FLOOR_XY(x) ((x) & (long int) 0xfff00000)
151 #define FIX_XY_TO_INT(x) ((long int) (x) >> (long int) FIX_XY_SHIFT)
153 // Sizes for tables in Draw
154 #define FILTER_WIDTH 0.75 // Line filter width adjustment // .75 // .5 works good with 5.0 gamma
155 #define F_TABLE_SIZE 64 // Filter table size
156 #define SC_TABLE_SIZE 32 // Slope correction table size
157 #define SRT_INT 5 // Sqrt table index integer bits
158 #define SRT_FRACT 4 // ...fraction bits
159 #define SR_INT 3 // Square root result integer bits
160 #define SR_FRACT 5 // ...fraction bits
161 #define SR_TABLE_SIZE (1 << (SRT_INT + SRT_FRACT))
162 #define INV_FILTER 47
164 #define EP_MASK (long int) 0x000f0000u // AA line end-point filter mask
165 #define EP_SHIFT 13u // Number of bits to shift end-point
168 typedef long int fix_xy; // S11.20
170 // One vertex at any of the various stages of the pipeline
172 typedef struct aa_vertex {
176 // All values needed to draw one line
177 typedef struct aa_setup_line {
181 fix_xy vs; // Starting point
183 fix_xy ue; // End (along major axis)
184 fix_xy dvdu; // Delta for minor axis step
189 // Tables that need to be initialized
190 long int slope_corr_table[SC_TABLE_SIZE];
191 long int filter_table[F_TABLE_SIZE];
192 long int sqrt_table[SR_TABLE_SIZE];
194 ubyte new_table[F_TABLE_SIZE*512];
196 int aaline_inited = 0;
198 // Initialize the tables normally found in ROM in the hardware.
199 void aaline_init_tables()
201 int i,j; // Iterative counter
203 double d; // Distance from center of curve
204 double v; // Value to put in table
205 double sr; // The square root value
209 // Build slope correction table. The index into this table
210 // is the truncated 5-bit fraction of the slope used to draw
211 // the line. Round the computed values here to get the closest
212 // fit for all slopes matching an entry.
214 for (i = 0; i < SC_TABLE_SIZE; i++) {
215 // Round and make a fraction
216 m = ((double) i + 0.5) / (float) SC_TABLE_SIZE;
217 v = sqrt(m * m + 1) * 0.707106781; /* (m + 1)^2 / sqrt(2) */
218 slope_corr_table[i] = (long int) (v * 256.0);
221 // Build the Gaussian filter table, round to the middle of the sample region.
222 for (i = 0; i < F_TABLE_SIZE; i++) {
223 d = ((double) i + 0.5) / (float) (F_TABLE_SIZE / 2.0);
224 d = d / FILTER_WIDTH;
225 v = 1.0 / exp(d * d); // Gaussian function
226 filter_table[i] = (long int) (v * 256.0);
229 for ( i=0; i<512; i++ ) {
230 long int corr_slope = i<<8;
231 for (j=0; j<F_TABLE_SIZE; j++ ) {
232 new_table[i*F_TABLE_SIZE+j] = (ubyte)(((corr_slope * filter_table[j]) & 0xf00000) >> (16+4));
233 if (new_table[i*F_TABLE_SIZE+j]==15 ) {
234 // HACK!!! Account for "glass" pixel for hud bitmaps.
235 new_table[i*F_TABLE_SIZE+j] = 14;
241 // Build the square root table for big dots.
242 for (i = 0; i < SR_TABLE_SIZE; i++) {
243 v = (double) ((i << 1) + 1) / (double) (1 << (SRT_FRACT + 1));
245 sqrt_table[i] = (long int) (sr * (double) (1 << SR_FRACT));
253 // Multiply a fixed-point number by a s11.20 fixed-point
254 // number. The actual multiply uses less bits for the
255 // multiplier, since it always represents a fraction
256 // less than 1.0 and less total bits are sufficient.
257 // Some of the steps here are not needed. This was originally
258 // written to simulate exact hardware behavior.
259 long int fix_xy_mult(long int oa, fix_xy ob)
282 // Draw one span of an antialiased line (for horizontal lines).
283 void draw_aa_hspan8(fix_xy x, fix_xy y, long int ep_corr, long int slope)
285 #ifndef HARDWARE_ONLY
286 long int sample_dist; // Distance from line to sample point
287 long int filter_index; // Index into filter table
288 long int i; // Count pixels across span
289 long int index; // Final filter table index
292 sample_dist = (FRACT_XY(y) >> (FIX_XY_SHIFT - 5)) - 16;
294 filter_index = sample_dist + 32;
297 int yi = FIX_XY_TO_INT( y );
298 int xi = FIX_XY_TO_INT( x );
300 if ( xi < gr_screen.clip_left ) return;
301 if ( xi > gr_screen.clip_right ) return;
305 if ( yi < gr_screen.clip_top ) clipped++;
306 if ( yi+3 > gr_screen.clip_bottom ) clipped++;
308 long int corr_slope = (slope * ep_corr) & 0x1ff00;
310 ubyte * lookup = (ubyte *)&Current_alphacolor->table.lookup[0][0];
312 ubyte * filter_lookup = (ubyte *)&new_table[(corr_slope>>8)*F_TABLE_SIZE];
318 for (i = 0; i < 4; i++) {
319 if (filter_index < 0)
320 index = ~filter_index; // Invert when negative
322 index = filter_index;
324 if (index > INV_FILTER) {
326 return; // Not a valid pixel
329 //a = ((corr_slope * filter_table[index]) & 0xf00000) >> (16+4-8);
330 a = filter_lookup[index]<<8;
332 // Should include the alpha value as well...
333 if ( (yi >= gr_screen.clip_top) && (yi <= gr_screen.clip_bottom) ) {
334 dptr = GR_SCREEN_PTR(ubyte,xi, yi);
336 *dptr = lookup[*dptr+a];
346 dptr = GR_SCREEN_PTR(ubyte,xi, yi);
348 for (i = 0; i < 4; i++) {
349 if (filter_index < 0)
350 index = ~filter_index; // Invert when negative
352 index = filter_index;
354 if (index > INV_FILTER) {
356 return; // Not a valid pixel
359 a = filter_lookup[index]<<8;
361 // Should include the alpha value as well...
362 *dptr = lookup[*dptr+a];
364 dptr += gr_screen.rowsize;
377 // Draw one span of an antialiased line (for vertical lines).
379 void draw_aa_vspan8(fix_xy x, fix_xy y, long int ep_corr, long int slope)
381 #ifndef HARDWARE_ONLY
382 long int sample_dist; // Distance from line to sample point
383 long int filter_index; // Index into filter table
384 long int i; // Count pixels across span
385 long int index; // Final filter table index
388 sample_dist = (FRACT_XY(x) >> (FIX_XY_SHIFT - 5)) - 16;
390 filter_index = sample_dist + 32;
392 int yi = FIX_XY_TO_INT( y );
393 int xi = FIX_XY_TO_INT( x );
395 if ( yi < gr_screen.clip_top ) return;
396 if ( yi > gr_screen.clip_bottom ) return;
400 if ( xi < gr_screen.clip_left ) clipped++;
401 if ( xi+3 > gr_screen.clip_right ) clipped++;
403 long int corr_slope = (slope * ep_corr) & 0x1ff00;
405 ubyte * lookup = (ubyte *)&Current_alphacolor->table.lookup[0][0];
407 ubyte * filter_lookup = (ubyte *)&new_table[(corr_slope>>8)*F_TABLE_SIZE];
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 = ((corr_slope * filter_table[index]) & 0xf00000) >> (16+4-8);
425 a = filter_lookup[index]<<8;
428 if ( (xi >= gr_screen.clip_left) && (xi <= gr_screen.clip_right) ) {
429 dptr = GR_SCREEN_PTR(ubyte,xi, yi);
431 *dptr = lookup[*dptr+a];
439 ubyte *dptr = GR_SCREEN_PTR(ubyte,xi, yi);
441 for (i = 0; i < 4; i++) {
442 if (filter_index < 0)
443 index = ~filter_index; // Invert when negative
445 index = filter_index;
447 if (index > INV_FILTER) {
449 return; // Not a valid pixel
452 a = filter_lookup[index]<<8;
454 // Should include the alpha value as well...
457 *dptr = lookup[*dptr+a];
469 void draw_line(aa_setup_line *line)
471 fix_xy x, y; // Start value
472 fix_xy dudu; // Constant 1 or -1 for step
473 fix_xy dx, dy; // Steps in X and Y
474 fix_xy u_off; // Offset to starting sample grid
475 fix_xy us, vs, ue; // Start and end for drawing
476 fix_xy count; // How many pixels to draw
477 long int slope_index; // Index into slope correction table
478 long int slope; // Slope correction value
479 long int ep_corr; // End-point correction value
480 long int scount, ecount; // Start/end count for endpoints
481 long int sf, ef; // Sand and end fractions
482 long int ep_code; // One of 9 endpoint codes
485 if (line->negative) {
499 // Get initial values and count
500 if (line->negative) {
501 u_off = FRACT_XY(line->us) - ONE_XY;
502 us = line->us + ONE_XY;
504 count = FLOOR_XY(us) - FLOOR_XY(ue);
506 u_off = 0 - FRACT_XY(line->us);
508 ue = line->ue + ONE_XY;
509 count = FLOOR_XY(ue) - FLOOR_XY(us);
512 vs = line->vs + fix_xy_mult(line->dvdu, u_off) + ONEHALF_XY;
522 //a = line->as + fix_xy_mult(line->dadu, u_off);
524 // Compute slope correction once per line
525 slope_index = (line->dvdu >> (FIX_XY_SHIFT - 5)) & 0x3fu;
527 if (line->dvdu < 0) {
528 slope_index ^= 0x3fu;
531 if ((slope_index & 0x20u) == 0) {
532 slope = slope_corr_table[slope_index];
534 slope = 0x100; /* True 1.0 */
537 // Set up counters for determining endpoint regions
539 ecount = FIX_TO_INT_XY(count);
541 // Get 4-bit fractions for end-point adjustments
542 sf = (us & EP_MASK) >> EP_SHIFT;
543 ef = (ue & EP_MASK) >> EP_SHIFT;
545 // Interpolate the edges
549 * Compute end-point code (defined as follows):
550 * 0 = 0, 0: short, no boundary crossing
551 * 1 = 0, 1: short line overlap (< 1.0)
552 * 2 = 0, 2: 1st pixel of 1st endpoint
553 * 3 = 1, 0: short line overlap (< 1.0)
554 * 4 = 1, 1: short line overlap (> 1.0)
555 * 5 = 1, 2: 2nd pixel of 1st endpoint
556 * 6 = 2, 0: last of 2nd endpoint
557 * 7 = 2, 1: first of 2nd endpoint
558 * 8 = 2, 2: regular part of line
561 ep_code = ((scount < 2) ? scount : 2) * 3 + ((ecount < 2) ? ecount : 2);
563 if (line->negative) {
565 // Drawing in the negative direction
567 // Compute endpoint information
569 case 0: ep_corr = 0; break;
570 case 1: ep_corr = ((sf - ef) & 0x78) | 4; break;
571 case 2: ep_corr = sf | 4; break;
572 case 3: ep_corr = ((sf - ef) & 0x78) | 4; break;
573 case 4: ep_corr = ((sf - ef) + 0x80) | 4; break;
574 case 5: ep_corr = (sf + 0x80) | 4; break;
575 case 6: ep_corr = (0x78 - ef) | 4; break;
576 case 7: ep_corr = ((0x78 - ef) + 0x80) | 4; break;
577 case 8: ep_corr = 0x100; break;
578 default: ep_corr = 0; break;
582 // Drawing in the positive direction
584 // Compute endpoint information
586 case 0: ep_corr = 0; break;
587 case 1: ep_corr = ((ef - sf) & 0x78) | 4; break;
588 case 2: ep_corr = (0x78 - sf) | 4; break;
589 case 3: ep_corr = ((ef - sf) & 0x78) | 4; break;
590 case 4: ep_corr = ((ef - sf) + 0x80) | 4; break;
591 case 5: ep_corr = ((0x78 - sf) + 0x80) | 4; break;
592 case 6: ep_corr = ef | 4; break;
593 case 7: ep_corr = (ef + 0x80) | 4; break;
594 case 8: ep_corr = 0x100; break;
595 default: ep_corr = 0; break;
600 draw_aa_hspan8(x, y, ep_corr, slope);
602 draw_aa_vspan8(x, y, ep_corr, slope);
617 // Perform the setup operation for a line, then draw it
619 void aaline_setup(aa_vertex *v1, aa_vertex *v2)
621 float dx, dy; // Deltas in X and Y
622 float udx, udy; // Positive version of deltas
623 float one_du; // 1.0 / udx or udy
626 if ( !aaline_inited )
627 aaline_init_tables();
648 line.negative = (dx < 0.0);
649 line.us = FLOAT_TO_FIX_XY(v2->x);
650 line.vs = FLOAT_TO_FIX_XY(v2->y);
651 line.ue = FLOAT_TO_FIX_XY(v1->x);
653 line.dvdu = FLOAT_TO_FIX_XY(dy * one_du);
657 line.negative = (dy < 0.0);
658 line.us = FLOAT_TO_FIX_XY(v2->y);
659 line.vs = FLOAT_TO_FIX_XY(v2->x);
660 line.ue = FLOAT_TO_FIX_XY(v1->y);
662 line.dvdu = FLOAT_TO_FIX_XY(dx * one_du);
665 // Convert colors to fixed-point
666 //line.as = FLOAT_TO_FIX_RGB(v2->a);
668 // Compute delta values for colors
669 //line.dadu = FLOAT_TO_FIX_RGB((v1->a - v2->a) * one_du);
679 void gr8_aaline( vertex *v1, vertex *v2 )
683 if ( !Current_alphacolor ) {
684 gr_line(fl2i(v1->sx),fl2i(v1->sy),fl2i(v2->sx),fl2i(v2->sy));
697 int clipped = 0, swapped = 0;
698 float a1, b1, a2, b2;
699 a1 = (float)gr_screen.clip_left;
700 b1 = (float)gr_screen.clip_top;
701 a2 = (float)gr_screen.clip_right;
702 b2 = (float)gr_screen.clip_bottom;
704 FL_CLIPLINE(aa1.x,aa1.y,aa2.x,aa2.y,a1,b1,a2,b2,return,clipped=1,swapped=1);
707 aaline_setup( &aa1, &aa2 );