SHARE
TWEET

drawline.c 1.02 by FrozenVoid

a guest Aug 10th, 2013 74 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /* DRAWLINE - Line drawing algorithm.
  2. drawline.c ver1.02 for Digital Mars C by FrozenVoid
  3. see ->fvdrawline function for implementation
  4.  original content licensed under UFIL1.02 http://pastebin.com/L3p9XK3T
  5. portions of file are licensed under other licenses(check source of content)
  6. @..\dmc  -gg -Nc -Jm  -o+all -o-dv %1.c -o%1.exe
  7. */
  8. #include "void.h" //v1.51 http://pastebin.com/qkifnqzq
  9.  
  10.  
  11.  
  12.  
  13. u4 pixels[0xffff]={0};
  14. #define putpixel(x,y,color) px&=0xFFFF;pixels[px++]=x;pixels[px++]=y;pixels[px++]=color; //writes coords+color
  15.  
  16. //Reference code from http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D1%80%D0%B5%D0%B7%D0%B5%D0%BD%D1%85%D1%8D%D0%BC%D0%B0#.D0.A0.D0.B5.D0.B0.D0.BB.D0.B8.D0.B7.D0.B0.D1.86.D0.B8.D1.8F_.D0.BD.D0.B0_C.2B.2B
  17. void refdrawline(int x1, int y1, int x2, int y2,u4 color) {
  18.  
  19.     const int deltaX = abs(x2 - x1);
  20.     const int deltaY = abs(y2 - y1);
  21.     const int signX = x1 < x2 ? 1 : -1;
  22.     const int signY = y1 < y2 ? 1 : -1;
  23.  u4 col=color;u4 px=0;
  24.     //
  25.  
  26.     int error = deltaX - deltaY;
  27.     //
  28.     putpixel(x2,y2,col);
  29.  
  30.     while(x1 != x2 || y1 != y2) {
  31.  
  32.  putpixel(x1,y1,col);
  33.  
  34.         const int error2 = error * 2;
  35.         //
  36.         if(error2 > -deltaY) {
  37.             error -= deltaY;
  38.             x1 += signX;
  39.         }
  40.         if(error2 < deltaX) {
  41.             error += deltaX;
  42.             y1 += signY;
  43.         }
  44.     }
  45.  
  46. }
  47.  
  48. // OPs drawline
  49. //http://dis.4chan.org/read/prog/1375979965/1
  50. v0 opdrawline(s4 x,s4 y,s4 a,s4 b,u4 color){
  51. u4 col=color;u4 px=0;
  52. f4 x0=x;
  53. f4 y0=y;
  54. f4 x1=a;
  55. f4 y1=b;
  56. f4 dx = x1-x0;
  57. f4 dy = y1-y0;
  58. f4 len = _inline_sqrtf(dx*dx+dy*dy);
  59.  dx /= len;
  60. dy /= len;
  61.     for (u4 k=0;k<=len;k++){
  62.  putpixel(floorf((x0)),floorf((y0)),col);
  63.          x0 += dx;
  64.         y0 += dy;
  65.     }
  66.  
  67.  
  68. }
  69. //Union drawline
  70. //http://hbfs.wordpress.com/2009/07/28/faster-than-bresenhams-algorithm/
  71. typedef
  72.   union
  73.    {
  74.     int32_t i;
  75.     struct
  76.      {
  77.       int16_t lo; // endian-specific!
  78.       int16_t hi;
  79.      };
  80.    } fixed_point;
  81. v0 unidrawline(int x1, int y1, int x2, int y2,u4 color){
  82.  int dx=x2-x1;
  83.   int dy=y2-y1;
  84.   int d=2*dy-dx;
  85.   int e=2*dy;
  86.   int ne=2*(dy-dx);
  87.   int x=x1;
  88.   int y=y1;
  89. u4 col=color;u4 px=0;
  90. fixed_point f;
  91.   int32_t m=((int32_t)(y2-y1)<<16)/(x2-x1);
  92.  
  93.   f.i=y1<<16;
  94.   for (x=x1;x<=x2;x++,f.i+=m)
  95.    {
  96.     fixed_point g=f;
  97.     g.i+=32767;
  98.     putpixel(x,g.hi,col);
  99.    }
  100. }
  101. //EFLA-E http://www.edepot.com/linee.html
  102. v0 eflaedrawline(int x, int y, int x2, int y2,u4 color){
  103. u4 px=0;u4 col=color;
  104. bool yLonger=false;
  105.         int shortLen=y2-y;
  106.         int longLen=x2-x;
  107.         if (abs(shortLen)>abs(longLen)) {
  108.                 int swap=shortLen;
  109.                 shortLen=longLen;
  110.                 longLen=swap;                          
  111.                 yLonger=true;
  112.         }
  113.         int decInc;
  114.         if (longLen==0) decInc=0;
  115.         else decInc = (shortLen << 16) / longLen;
  116.  
  117.         if (yLonger) {
  118.                 if (longLen>0) {
  119.                         longLen+=y;
  120.                         for (int j=0x8000+(x<<16);y<=longLen;++y) {
  121.                                 putpixel(j >> 16,y,col);       
  122.                                 j+=decInc;
  123.                         }
  124.                         return;
  125.                 }
  126.                 longLen+=y;
  127.                 for (int j=0x8000+(x<<16);y>=longLen;--y) {
  128.                         putpixel(j >> 16,y,col);       
  129.                         j-=decInc;
  130.                 }
  131.                 return;
  132.         }
  133.  
  134.         if (longLen>0) {
  135.                 longLen+=x;
  136.                 for (int j=0x8000+(y<<16);x<=longLen;++x) {
  137.                         putpixel(x,j >> 16,col);
  138.                         j+=decInc;
  139.                 }
  140.                 return;
  141.         }
  142.         longLen+=x;
  143.         for (int j=0x8000+(y<<16);x>=longLen;--x) {
  144.                 putpixel(x,j >> 16,col);
  145.                 j-=decInc;
  146.         }
  147.  
  148.  
  149.  
  150.  
  151. }
  152. //EFLA-D http://www.edepot.com/lined.html
  153. v0 efladdrawline(int x, int y, int x2, int y2,u4 color){
  154. u4 px=0;u4 col=color;
  155. bool yLonger=false;
  156.         int incrementVal, endVal;
  157.         int shortLen=y2-y;
  158.         int longLen=x2-x;
  159.         if (abs(shortLen)>abs(longLen)) {
  160.                 int swap=shortLen;
  161.                 shortLen=longLen;
  162.                 longLen=swap;
  163.                 yLonger=true;
  164.         }
  165.         endVal=longLen;
  166.         if (longLen<0) {
  167.                 incrementVal=-1;
  168.                 longLen=-longLen;
  169.         } else incrementVal=1;
  170.         int decInc;
  171.         if (longLen==0) decInc=0;
  172.         else decInc = (shortLen << 16) / longLen;
  173.         int j=0;
  174.         if (yLonger) { 
  175.                 for (int i=0;i!=endVal;i+=incrementVal) {
  176.                         putpixel(x+(j >> 16),y+i,col); 
  177.                         j+=decInc;
  178.                 }
  179.         } else {
  180.                 for (int i=0;i!=endVal;i+=incrementVal) {
  181.                         putpixel(x+i,y+(j >> 16),col);
  182.                         j+=decInc;
  183.                 }
  184.         }
  185.  
  186. }
  187. //EFLA-C http://www.edepot.com/linec.html
  188. v0 eflacdrawline(int x, int y, int x2, int y2,u4 color){
  189. u4 px=0;u4 col=color;
  190. bool yLonger=false;
  191.         int incrementVal, endVal;
  192.  
  193.         int shortLen=y2-y;
  194.         int longLen=x2-x;
  195.         if (abs(shortLen)>abs(longLen)) {
  196.                 int swap=shortLen;
  197.                 shortLen=longLen;
  198.                 longLen=swap;
  199.                 yLonger=true;
  200.         }
  201.        
  202.         endVal=longLen;
  203.         if (longLen<0) {
  204.                 incrementVal=-1;
  205.                 longLen=-longLen;
  206.         } else incrementVal=1;
  207.  
  208.         double decInc;
  209.         if (longLen==0) decInc=(double)shortLen;
  210.         else decInc=((double)shortLen/(double)longLen);
  211.         double j=0.0;
  212.         if (yLonger) {
  213.                 for (int i=0;i!=endVal;i+=incrementVal) {
  214.                         putpixel(x+(int)j,y+i,col);
  215.                         j+=decInc;
  216.                 }
  217.         } else {
  218.                 for (int i=0;i!=endVal;i+=incrementVal) {
  219.                         putpixel(x+i,y+(int)j,col);
  220.                         j+=decInc;
  221.                 }
  222.         }
  223.  
  224. }
  225. //EFLA-B http://www.edepot.com/lineb.html
  226. v0 eflabdrawline(int x, int y, int x2, int y2,u4 color){
  227. u4 px=0;u4 col=color;
  228. bool yLonger=false;
  229.         int incrementVal;
  230.         int shortLen=y2-y;
  231.         int longLen=x2-x;
  232.  
  233.         if (abs(shortLen)>abs(longLen)) {
  234.                 int swap=shortLen;
  235.                 shortLen=longLen;
  236.                 longLen=swap;
  237.                 yLonger=true;
  238.         }
  239.  
  240.         if (longLen<0) incrementVal=-1;
  241.         else incrementVal=1;
  242.  
  243.         double multDiff;
  244.         if (longLen==0.0) multDiff=(double)shortLen;
  245.         else multDiff=(double)shortLen/(double)longLen;
  246.         if (yLonger) {
  247.                 for (int i=0;i!=longLen;i+=incrementVal) {
  248.                         putpixel(x+(int)((double)i*multDiff),y+i,col);
  249.                 }
  250.         } else {
  251.                 for (int i=0;i!=longLen;i+=incrementVal) {
  252.                         putpixel(x+i,y+(int)((double)i*multDiff),col);
  253.                 }
  254.         }
  255.  
  256. }
  257. //EFLA-A http://www.edepot.com/linea.html
  258. v0 eflaadrawline(int x, int y, int x2, int y2,u4 color){
  259. u4 px=0;u4 col=color;
  260. bool yLonger=false;
  261.         int incrementVal;
  262.  
  263.         int shortLen=y2-y;
  264.         int longLen=x2-x;
  265.         if (abs(shortLen)>abs(longLen)) {
  266.                 int swap=shortLen;
  267.                 shortLen=longLen;
  268.                 longLen=swap;
  269.                 yLonger=true;
  270.         }
  271.  
  272.         if (longLen<0) incrementVal=-1;
  273.         else incrementVal=1;
  274.  
  275.         double divDiff;
  276.         if (shortLen==0) divDiff=longLen;
  277.         else divDiff=(double)longLen/(double)shortLen;
  278.         if (yLonger) {
  279.                 for (int i=0;i!=longLen;i+=incrementVal) {
  280.                         putpixel(x+(int)((double)i/divDiff),y+i,col);
  281.                 }
  282.         } else {
  283.                 for (int i=0;i!=longLen;i+=incrementVal) {
  284.                         putpixel(x+i,y+(int)((double)i/divDiff),col);
  285.                 }
  286.         }
  287.  
  288. }
  289. //OPT EFLA http://www.simppa.fi/blog/extremely-fast-line-algorithm-as3-optimized/
  290. v0 optefladrawline(int x, int y, int x2, int y2,u4 color){
  291. u4 px=0;u4 col=color;int i;
  292. int shortLen= y2-y;
  293.   int longLen= x2-x;
  294.   bool yLonger;
  295.   if(((shortLen ^ (shortLen >> 31)) - (shortLen >> 31) > (longLen ^ (longLen >> 31)) - (longLen >> 31)))
  296.   {
  297.   shortLen ^= longLen;
  298.   longLen ^= shortLen;
  299.   shortLen ^= longLen;
  300.  
  301.   yLonger= true;
  302.   }
  303.   else
  304.  {
  305.   yLonger = false;
  306.  }
  307.  
  308.   int inc= longLen < 0 ? -1 : 1;
  309.  
  310.   double multDiff= longLen == 0 ? shortLen : shortLen / longLen;
  311.  
  312.   if (yLonger)
  313.   {
  314.     for ( i = 0; i != longLen; i += inc)
  315.     {
  316.       putpixel(x + i*multDiff, y+i, col);
  317.     }
  318.   }
  319.   else
  320.   {
  321.     for (i = 0; i != longLen; i += inc)
  322.     {
  323.       putpixel(x+i, y+i*multDiff, col);
  324.     }
  325.   }
  326.  
  327. }
  328. //peronedrawline http://willperone.net/Code/codeline.php
  329. void peronedrawline(int x1, int y1, int x2, int y2, int color)
  330. {u4 px=0;u4 col=color;
  331.     int cx, cy,
  332.         ix, iy,
  333.         dx, dy,
  334.         ddx= x2-x1, ddy= y2-y1;
  335.      
  336.     if (!ddx) { //vertical line special case
  337.         if (ddy > 0) {
  338.             cy= y1;  
  339.             do {putpixel(x1, cy++, col);}
  340.             while (cy <= y2);
  341.             return;
  342.         } else {
  343.             cy= y2;
  344.             do{ putpixel(x1, cy++, col);}
  345.             while (cy <= y1);
  346.             return;
  347.         }
  348.     }
  349.     if (!ddy) { //horizontal line special case
  350.         if (ddx > 0) {
  351.             cx= x1;
  352.             do{ putpixel(cx, y1, col);}
  353.             while (++cx <= x2);
  354.             return;
  355.         } else {
  356.             cx= x2;
  357.             do{ putpixel(cx, y1, col);}
  358.             while (++cx <= x1);
  359.             return;
  360.         }
  361.     }
  362.     if (ddy < 0) { iy= -1; ddy= -ddy; }//pointing up
  363.             else iy= 1;
  364.     if (ddx < 0) { ix= -1; ddx= -ddx; }//pointing left
  365.             else ix= 1;
  366.     dx= dy= ddx*ddy;
  367.     cy= y1, cx= x1;
  368.     if (ddx < ddy) { // < 45 degrees, a tall line    
  369.         do {
  370.             dx-=ddy;
  371.             do {
  372.                 putpixel(cx, cy, col);
  373.                 cy+=iy, dy-=ddx;
  374.             } while (dy >=dx);
  375.             cx+=ix;
  376.         } while (dx > 0);
  377.     } else { // >= 45 degrees, a wide line
  378.         do {
  379.             dy-=ddx;
  380.             do {
  381.                 putpixel(cx, cy, col);
  382.                 cx+=ix, dx-=ddy;
  383.             } while (dx >=dy);
  384.             cy+=iy;
  385.         } while (dy > 0);
  386.     }
  387. }
  388.  
  389. //Optimized Bresenham algorithm by FrozenVoid
  390. //based on union drawline
  391.  
  392. v0 fvdrawline(u4 x1,u4 y1,u4 x2,u4 y2,u4 color){
  393. u4 px=0;u4 col=color;
  394. int dx=x2-x1;
  395.  int dy=y2-y1;
  396.  int d=2*dy-dx;
  397.  int e=2*dy;
  398.  int ne=2*(dy-dx);
  399. int reg x=x1;
  400. int y=y1;
  401. int reg f=0;
  402.   int32_t reg m=((int32_t)(y2-y1)<<16)/(x2-x1);
  403.  
  404.   f=y1<<16;x=x1;
  405. for (x=x1;x<=x2;x++,f+=m){putpixel(x,((f+32767)>>16),col);}
  406.  
  407.  
  408. }
  409. #define tstart exstart=rdtsc();
  410. #define tend exend=rdtsc();
  411. #define bench(msg) pr("%s cycles spent:%"PRIu64"\n",#msg,exend-exstart);  
  412. #define func(name) tstart;for(h=0;h<10000;h++)name(x1,y1,x2,y2,color);tend;bench(name);
  413. STDSTART //benchmarks
  414. u8 exstart,exend;u4 pixels[0xFFFF]={0};u4 h;
  415. s4 x1=ru2();
  416. s4 x2=ru2();
  417. s4 y1=ru2();
  418. s4 y2=ru2();
  419. u4 color=ru4();
  420. func(refdrawline);
  421. func(opdrawline);
  422. func(eflaedrawline);
  423. func(efladdrawline);
  424. func(eflacdrawline);
  425. func(eflabdrawline);
  426. func(eflaadrawline);
  427. func(optefladrawline);
  428. func(peronedrawline);
  429. func(unidrawline);
  430. func(fvdrawline);
  431. //for use with start/REALTIME drawline.exe
  432. u1 bchar;
  433. pr("Any key+enter to close");;scanf("%c",&bchar);
  434.  
  435.  
  436. STDEND
RAW Paste Data
Top