murrayk@prism.CS.ORST.EDU (05/07/91)
I am currently trying to write some code that will draw a solid-fill triangle on the VGA 640 x 350 screen (I am using this resolution so I can easily write an EGA version also). What the routine needs to do is to take in as input three points (x, y), a color, and a page number (0 or 1) and then as output the routine will draw a filled triangle with the three given points as the vertices. The routine needs to be really fast. I am having some problems as I have not been coding assemply for a long enough amount of time. If anyone has code to do this or is willing to tell me how to do it I would be very (read that extremely VERY) happy. If I do get this code, I will post the program that it is going to be used in, it will probably be a simple demo just to check things out. Thanks a lot for any help you can give me, Keith. ------------------------------ | CHAOS Software | "If I tell ya what I'm doing | 1360 NW VanBuren | today, will you shut up and | Corvallis, OR 97330 | get out of my way?" ------------------------------ -ANTHRAX- Keith Murray (503) 757-2753 "A little man with a big eraser, murrayk@prism.cs.orst.ed changing history..." -MEGADEATH-
wjb@moscom.UUCP (Bill de Beaubien) (05/09/91)
In article <1991May07.025853.7837@lynx.CS.ORST.EDU> murrayk@prism.CS.ORST.EDU writes: > >I am currently trying to write some code that will draw a solid-fill >triangle on the VGA 640 x 350 screen (I am using this resolution so I can >easily write an EGA version also). What the routine needs to do is to >take in as input three points (x, y), a color, and a page number (0 or 1) >and then as output the routine will draw a filled triangle with the three >given points as the vertices. The routine needs to be really fast. I am >having some problems as I have not been coding assemply for a long enough >amount of time. If anyone has code to do this or is willing to tell me >how to do it I would be very (read that extremely VERY) happy. If I do >get this code, I will post the program that it is going to be used in, it >will probably be a simple demo just to check things out. > >Thanks a lot for any help you can give me, Keith. Well, The following code will do most of what you want. The only thing which you specified which it doesn't do is write to either page 0 or page 1. If you want the ability to do this, modify HorizLine and SetPixel10 in hline.asm to take care of paging. I might do this tomorrow (or maybe even later tonight if I can't sleep). Depends on how busy life is for the next few days. In any case, the code's extremely fast. It only works in EGA modes (if you want speed, you sacrifice portability). Basically, it starts at the bottom of the triangle and works its way up drawing horizontal lines between the borders (which it computes ahead of time). It writes complete bytes to the EGA when possible, which speeds it up some. There's a switch in the code which will let you use BIOS calls to do the pixels. This slows things down a lot, so it's probably worthless for what Keith wants, but I left it there for people who want to try it and see how it works, but don't have an EGA. NOTE: The following is a *very* rudimentary shell archive. It does no error checking or anything (our system doesn't seem to have shar, cshar, or bundle or any of those things). The code was written for Microsoft C and Assembler, but should port to other C compilers (and, hopefully, assemblers) with minimal difficulty. Hope you enjoy it... Bill de Beaubien - wjb@moscom.com ------ cut here ------ : # This is a shell archive. cd to an empty directory and feed to sh. cat << 'Zaphod for prez' | sed 's/X\(.*\)X/\1/' > hline.asm X; version 1.0X XX X; This file contains the routines necessary for drawing horizontalX X; lines in EGA video modes. These routines are derived from thoseX X; presented in Richard Wilton's _Programmer's Guide to PC & PS/2 VideoX X; Systems_ (An excellent reference. The best one I've seen thus far,X X; and I have 4.X X;X X; NOTE WELL!!!!!!!!!!!!!!!!!!!!!!!!X X; This code will ONLY work on EGA's (and VGA's in EGA modes, ofX X; course). The price of speed is hardware dependence. For otherX X; cards/modes, similar functions can be written, but this oneX X; most definitely will not work.X XX X; note also: This is set up for the SMALL model. To changeX X; to large model, the EQU's below have to be bumped up by 4,X X; the .MODEL directive has to change, and the PROC NEARS shouldX X; become PROC FARS.X XX X .MODEL SMALLX X .CODEX XX X PUBLIC _HorizLineX X_HorizLine PROC NEARX XX XArgX1 EQU word ptr [bp+4] ; stack frame addressingX XArgX2 EQU word ptr [bp+6]X XArgY EQU word ptr [bp+8]X XArgCol EQU byte ptr [bp+10]X XX X push bp ; preserve caller registersX X mov bp,spX X push siX X push diX XX X; configure the graphics controllerX X mov dx,3CEh ; dx = graphics controller port addressX XX X mov ah,ARGCol ; ah = colourX X xor al,al ; al = set/reset register numberX X out dx,axX XX X mov ax,0F01h ; AH = 1111b (bit plane mask forX X ; enable set/reset regX X out dx,ax ; al = enable set/reset reg #X XX X xor ah,ah ; bits 3 and 4 of AH functionX X mov al,3 ; al = data rotate/func select regX X out dx,axX XX X; force x1 < x2X X mov cx,ArgX2X X sub cx,ArgX1 ; cx = x2 - x1X X jns L01X XX X mov bx,ArgX2 ; swap(&x1, &x2)X X xchg bx,ArgX1X X mov ArgX2,bxX XX X; draw a horizontal lineX XL01: push ds ; preserve DSX X mov ax,ArgYX X mov bx,ArgX1X X call PixelAddr10 ; AH = bit maskX X ; es:bx -> vid bufferX X ; cl = bits to shift leftX X mov di,bx ; es:di->bufferX X mov dh,ah ; dh = unshifted bit mask for left byteX X not dhX X shl dh,cl ; dh = reverse bit mask for first byteX X not dh ; dh = bit mask for first byteX XX X mov cx,ArgX2X X and cl,7X X xor cl,7 ; cl = # of bits to shift leftX X mov dl,0FFh ; dl = unshifted mask for right byteX X shl dl,cl ; dl = bit mask for last byteX XX X; determine byte offset of first and last pixel in lineX X mov ax,ArgX2 ; ax = x2X X mov bx,ArgX1 ; bx = x1X X mov cl,3 ; # bits to shift for pixel->byteX X shr ax,cl ; ax = byte offset of x2X X shr bx,cl ; bx = byte offset of x1X X mov cx,axX X sub cx,bx ; cx = (# bytes in line) - 1X XX X; get graphics controller port address into DXX X mov bx,dx ; bh = mask 1st byte, bl = mask last byteX X mov dx,3CEh ; dx = graphics controller portX X mov al,8 ; al = bit mask reg numberX XX X; make video buffer addressable through DS:DIX X push esX X pop dsX X mov si,di ; DS:SI -> video bufferX XX X; set pixels in leftmost byte of lineX X or bh,bhX X js L43 ; jump if byte-aligned (x1 leftmostX X ; pixel in byte)X X or cx,cxX X jnz L42 ; jump if more than one byte in the lineX XX X and bl,bh ; bl = bit mask for the lineX X jmp short L44X XX XL42: mov ah,bh ; ah = bit mask for 1st byteX X out dx,ax ; update graphics controllerX X movsbX X dec cxX XX X; use a fast 8086 instruction to draw the remainder of the lineX XL43: mov ah,11111111b ; ah = bit maskX X out dx,ax ; update bit mask registerX X rep movsb ; update all pixels in the lineX XX X; set pixels in the rightmost byte of the lineX XL44: mov ah,bl ; ah = bit mask for last byteX X out dx,ax ; update graphics controllerX X movsb ; update bit planesX X pop ds ; restore DSX XX X; restore default graphics controller state and return to callerX X xor ax,ax ; ah = 0, al = 0X X out dx,ax ; restore set/reset registerX XX X inc ax ; ah = 0, al = 1X X out dx,ax ; restore enable set/reset registerX XX X mov al,3 ; ah = 0, al = 3X X out dx,ax ; al = data rotate/func select reg #X XX X mov ax,0FF08h ; ah = 1111111b, al = 8X X out dx,ax ; restore bit mask registerX XX X pop diX X pop siX X mov sp,bpX X pop bpX X retX X_HorizLine ENDPX XX XPixelAddr10 PROC NEARX X mov cl,bl ; cl = low order byte of xX X push dx ; preserve DXX X mov dx,80 ; ax = y * bytes per lineX X mul dxX XX X pop dxX X shr bx,1X X shr bx,1X X shr bx,1 ; bx /= 8X X add bx,ax ; bx = y * bytesperline + x/8X X mov ax,0A000h ; ax = video buffer segmentX X mov es,ax ; es:bx = byte address of pixelX X and cl,7 ; cl = x & 7X X xor cl,7 ; cl = # of bits to shift leftX X mov ah,1 ; ah = unshifted bit maskX X retX XPixelAddr10 ENDPX X ENDX Zaphod for prez cat << 'Zaphod for prez' | sed 's/X\(.*\)X/\1/' > makefile X# version 1.0X XX Xall: triangle.exeX XX Xtriangle.exe: triangle.obj hline.objX X :link /CO triangle hline;X XX Xtriangle.obj: triangle.cX X :cl -c -AS -Od -W3 -Zi triangle.cX XX Xhline.obj: hline.asmX X :masm /W2 /Zi hline;X Zaphod for prez cat << 'Zaphod for prez' | sed 's/X\(.*\)X/\1/' > readme XTriangles 1.0X XX XWell, this is about the fastest triangle filler I could come up with.X XSee the documentation in the triangle function for more info.X XX XAs usual in such things, no warranties. It works for me... if it's usefulX Xfor you, good, I didn't waste a couple hours writing it :-) More fun thanX Xworking anyway, right? :-)X XX XBill de Beaubien wjb@moscom.comX Zaphod for prez cat << 'Zaphod for prez' | sed 's/X\(.*\)X/\1/' > triangle.c X/* version 1.0 */X XX X/*********************************************************************X X * The following code was written by:X X * Bill de Beaubien - wjb@moscom.comX X *X X * Use at your own risk. If you make something useful out of it, I'dX X * appreciate a copy. (not required, however) Aside from that, use itX X * for whatever...X X */X XX X#include <stdio.h> /* used for getchar. remove if you don't use it */X X#include <stdlib.h>X X#include <conio.h> /* used for kbhit. remove if you don't use it */X X#include <dos.h>X XX X/* If you want to use the horizontal line drawing function in this file,X X remove the #if 0 / #endif pair following. The function in here usesX X the BIOS interrupt to do the pixels. It's extremely slow... but it'llX X work in whatever graphics mode you want. */X XX X#if 0X X#define USE_CHLINEX X#endifX XX X/* define a couple of constants for video modes */X X#define VID_TEXT 3 /* normal text mode */X X#define VID_EGA_HIGH 0x10 /* EGA 640x350 16 colour mode */X XX X#define MAX_Y 349 /* max Y pixels */X XX XX Xvoid BresPoints (int x1, int y1, int x2, int y2, int least, int xlist[]);X Xvoid pause (void);X Xvoid SetVideoMode (int mode);X Xvoid Triangle (int x1, int y1, int x2, int y2, int x3, int y3, int color);X XX X#ifdef USE_CHLINEX Xvoid CHorizLine (int x1, int x2, int y, int color);X Xvoid SetPt (int x, int y, int color);X X#elseX Xvoid HorizLine (int x1, int x2, int y, int color);X X#endifX XX Xstatic int xlist1[MAX_Y+1], xlist2[MAX_Y+1];X XX X/*********************************************************************X X * BresPointsX X * This algorithm is based on Bresenham's line drawing algorithm.X X * Basically, it goes along a line and fills an array with eitherX X * the leftmost or rightmost X coordinate for each Y (controlled byX X * the least flag which is passed in). The number of X coordinatesX X * put into the array is the same as the number of different YX X * coordinates in the line. Note that for vertical lines, theX X * array is set to all the same values. For horizontal lines,X X * only 1 element is used.X X *X X * Inputs:X X * x1,y1 endpoint 1 of the lineX X * x2,y2 endpoint 2 of the lineX X * least if true, use the least X coordinate for a given Y.X X * if false, use the greatest X coordinate for a given YX X *X X * Outputs:X X * xlist[] The min or max X coordinate for each Y on the lineX X *X X * This code is based in part on the Bresenham's algorithm presentedX X * in Foley & Van Dam's _Fundamentals of Interactive Computer Graphics,X X * page 435.X X */X XX Xvoid BresPoints (int x1, int y1, int x2, int y2, int least, int xlist[])X X{X X int dx, dy, incr1, incr2, d, x, y, xend, xloop, yend, sign;X XX X dx = abs(x2-x1);X X dy = abs(y2-y1);X X sign = (x2 > x1 && y2 > y1 || x2 < x1 && y2 < y1);X XX X if (dy == 0)X X { /* horizontal line; return min or max x, depending on least */X X if (least)X X xlist[0] = min(x1,x2);X X elseX X xlist[0] = max(x1,x2);X X }X X else if (dx == 0)X X { /* vertical line; return array of all x1's (same as x2's) */X X while (dy)X X xlist[dy--] = x1;X X xlist[0] = x1;X X }X XX X else if (dx >= dy && sign)X X { /* slope between 0 and 1 */X X d = 2 * dy - dx;X X incr1 = 2 * dy;X X incr2 = 2 * (dy - dx);X X xloop = least ? -1 : 0;X XX X if (x1 > x2)X X {X X x = x2;X X y = y2;X X xend = x1;X X }X X elseX X {X X x = x1;X X y = y1;X X xend = x2;X X }X XX X if (!least)X X xlist[xloop] = x;X XX X while (x < xend)X X {X X if (d < 0)X X d+=incr1;X X elseX X {X X y++;X X d+=incr2;X XX X if (least)X X xlist[++xloop] = x;X X elseX X xlist[xloop++] = x+1;X X }X X x++;X X }X X if (least)X X xlist[++xloop] = x;X X elseX X xlist[xloop] = x;X X }X X else if (dy > dx && sign)X X { /* slope between 1 and inf */X X d = 2 * dx - dy;X X incr1 = 2 * dx;X X incr2 = 2 * (dx - dy);X XX X if (y1 > y2)X X {X X y = y2;X X x = x2;X X yend = y1;X X }X X elseX X {X X y = y1;X X x = x1;X X yend = y2;X X }X XX X xloop = 0;X X xlist[xloop++] = x;X XX X while (y < yend)X X {X XX X if (d < 0)X X d+=incr1;X X elseX X {X X x++;X X d+=incr2;X X }X X y++;X X xlist[xloop++] = x;X X }X X }X XX X else if (dy > dx)X X { /* slope between -1 and -inf */X X d = 2 * dx - dy;X X incr1 = 2 * dx;X X incr2 = 2 * (dx - dy);X XX X if (y1 > y2)X X {X X y = y2;X X x = x2;X X yend = y1;X X }X X elseX X {X X y = y1;X X x = x1;X X yend = y2;X X }X XX X xloop = 0;X X xlist[xloop++] = x;X XX X while (y < yend)X X {X XX X if (d < 0)X X d+=incr1;X X elseX X {X X x--;X X d+=incr2;X X }X X y++;X X xlist[xloop++] = x;X X }X X }X XX X else if (dx >= dy)X X { /* slope between 0 and -1 */X X d = 2 * dy - dx;X X incr1 = 2 * dy;X X incr2 = 2 * (dy - dx);X X xloop = least ? dy+1 : dy;X XX X if (x1 > x2)X X {X X x = x2;X X y = y2;X X xend = x1;X X }X X elseX X {X X x = x1;X X y = y1;X X xend = x2;X X }X XX X if (!least)X X xlist[xloop] = x;X XX X while (x < xend)X X {X X if (d < 0)X X d+=incr1;X X elseX X {X X y--;X X d+=incr2;X XX X if (least)X X xlist[--xloop] = x;X X elseX X xlist[xloop--] = x+1;X X }X X x++;X X }X X if (least)X X xlist[--xloop] = x;X X elseX X xlist[xloop] = x;X X }X X}X XX X#ifdef USE_CHLINEX X/*********************************************************************X X * CHorizLineX X * This function draws a horizontal line.X X *X X * Inputs:X X * x1 x coordinate of one end of lineX X * x2 x coordinate of other end of lineX X * y y coordinate of lineX X * color colour of lineX X */X XX Xvoid CHorizLine (int x1, int x2, int y, int color)X X{X X int x;X XX X if (x1 > x2)X X {X X x = x1;X X x1 = x2;X X x2 = x;X X }X XX X for (x=x1; x<=x2; x++)X X SetPt(x,y,color);X X}X XX X/*********************************************************************X X * SetPtX X * This function makes a bios call to write a pixel location.X X * This method is incredibly slow. This being the case, a moreX X * hardware-specific assembly language function is also provided.X X *X X * Inputs:X X * x x coordinate of the pixelX X * y y coordinate of the pixelX X * color colour of the pointX X */X XX Xvoid SetPt (int x, int y, int color)X X{X X union REGS regs;X XX X regs.h.ah = 0x0C; /* service 0x0C, write pixel */X X regs.h.al = (char) color; /* colour of the pixel */X X regs.x.bx = 0; /* page. always set this, just in case. */X X regs.x.cx = x; /* x coordinate */X X regs.x.dx = y; /* y coordinate */X X int86 (0x10, ®s, ®s); /* BIOS video interrupt */X X}X X#endifX XX X/*********************************************************************X X * SetVideoModeX X * This function sets the video mode to the mode passed.X X *X X * Inputs:X X * mode the video mode which you want to useX X */X XX Xvoid SetVideoMode (int mode)X X{X X union REGS regs;X XX X regs.h.ah = 0x0; /* service 0 - set video mode */X X regs.h.al = (char) mode; /* the video mode */X X int86 (0x10, ®s, ®s); /* BIOS video interrupt */X X}X XX X/*********************************************************************X X * TriangleX X * This is the heart of the program. It takes three points, andX X * plots a filled triangle with the points as the corners.X X *X X * Basically, it works like this: It looks at the three points,X X * and sets P1 to be the point with max Y, P3 the point with minX X * Y, and P2 to be the point in between. It then makes 2 listsX X * of X coordinages: 1 for the long leg, and 1 for the combinedX X * shorter legs. These points are set up so that for a givenX X * Y, the array elements have the same index. (y3 has array indexX X * 0, and y1 has array index (y1-y3+1). It then starts at max YX X * and works its way down to 0, drawing horizontal lines betweenX X * the X coordinate pairs for each Y.X X *X X * The only thing not covered in this paragraph is the leastX X * variable. This variable tells BresPoints whether to useX X * the lowest or highest X value for each Y value. (This onlyX X * affects lines where dX > dy, since other lines won't haveX X * multiple X coordinates for the same Y's.) If the line's onX X * the left side of the triangle, least should be set true (non-0).X X * If it's on the right, it should be set to 0.X X *X X * Inputs:X X * x1, y1 corner of triangleX X * x2, y2 corner of triangleX X * x3, y3 corner of triangleX X * color colour of triangleX X */X XX XX Xvoid Triangle (int x1, int y1, int x2, int y2, int x3, int y3, int color)X X{X X int x, y, least, dy;X XX X /* make sure that (x1, y1) is max y */X X if (y2 > y1)X X {X X x = x2;X X x2 = x1;X X x1 = x;X X y = y2;X X y2 = y1;X X y1 = y;X X }X XX X if (y3 > y1)X X {X X x = x3;X X x3 = x1;X X x1 = x;X X y = y3;X X y3 = y1;X X y1 = y;X X }X XX X /* make sure that (x3, y3) is min y */X X if (y2 < y3)X X {X X x = x3;X X x3 = x2;X X x2 = x;X X y = y3;X X y3 = y2;X X y2 = y;X X }X XX X /* least is true if the doubled segment is to the left of the singleX X segment */X XX X least = (x2 < x3);X XX X dy = (y2 - y3);X X BresPoints (x3, y3, x1, y1, least ? 0 : 1, xlist1);X X BresPoints (x3, y3, x2, y2, least, xlist2);X X BresPoints (x2, y2, x1, y1, least, &(xlist2[dy]));X XX X dy = abs(y1 - y3);X XX X for (y = y1; y >= y3; y--, dy--)X X#ifdef USE_CHLINEX X CHorizLine (xlist1[dy], xlist2[dy], y, color);X X#elseX X HorizLine (xlist1[dy], xlist2[dy], y, color);X X#endifX X}X XX X/*********************************************************************X X * pauseX X * This function waits until a key's been pressed, then reads theX X * key. It does leave a cursor on the screen, but c'est la vie.X X * I'll write a better one later :-)X X */X XX Xvoid pause (void)X X{X X while (!kbhit());X X getchar();X X}X XX X/*********************************************************************X X * The following is just a demo. It draws an octogon of 8 trianglesX X */X XX Xvoid main (void)X X{X X int i;X XX X int x[] = {120, 220, 420, 520, 520, 420, 220, 120, 120};X X int y[] = {112, 50, 50, 112, 238, 300, 300, 238, 112};X XX X SetVideoMode (VID_EGA_HIGH);X XX X for (i=0; i<8; i++)X X Triangle (320, 175, x[i], y[i], x[i+1], y[i+1], i+8);X XX X pause();X X SetVideoMode (VID_TEXT);X X}X Zaphod for prez exit 0 -- "Bless me, Father; I ate a lizard." "Was it an abstinence day, and was it artificially prepared?" ------------------------------------------------------------- Bill de Beaubien / wjb@moscom.com