src/livarot/BitLigne.cpp

   1 /*
   2  *  BitLigne.cpp
   3  *  nlivarot
   4  *
   5  *  Created by fred on Wed Jul 23 2003.
   6  *  public domain
   7  *
   8  */
   9
  10 #include "BitLigne.h"
  11
  12 #include <math.h>
  13 #include <cstring>
  14 #include <cstdlib>
  15 #include <string>
  16 #include <cmath>
  17 #include <cstdio>
  18 #include <glib/gmem.h>
  19
  20 BitLigne::BitLigne(int ist,int ien,float iScale)
  21 {
  22   scale=iScale;
  23   invScale=1/iScale;
  24         st=ist;
  25         en=ien;
  26         if ( en <= st ) en=st+1;
  27         stBit=(int)floor(((float)st)*invScale); // round to pixel boundaries in the canvas
  28         enBit=(int)ceil(((float)en)*invScale);
  29         int  nbBit=enBit-stBit;
  30         if ( nbBit&31 ) {
  31                 nbInt=nbBit/32+1;
  32         } else {
  33                 nbInt=nbBit/32;
  34         }
  35   nbInt+=1;
  36         fullB=(uint32_t*)g_malloc(nbInt*sizeof(uint32_t));
  37         partB=(uint32_t*)g_malloc(nbInt*sizeof(uint32_t));
  38
  39         curMin=en;
  40         curMax=st;
  41 }
  42 BitLigne::~BitLigne(void)
  43 {
  44         g_free(fullB);
  45         g_free(partB);
  46 }
  47
  48 void             BitLigne::Reset(void)
  49 {
  50         curMin=en;
  51         curMax=st+1;
  52         memset(fullB,0,nbInt*sizeof(uint32_t));
  53         memset(partB,0,nbInt*sizeof(uint32_t));
  54 }
  55 int              BitLigne::AddBord(float spos,float epos,bool full)
  56 {
  57         if ( spos >= epos ) return 0;
  58
  59   // separation of full and not entirely full bits is a bit useless
  60   // the goal is to obtain a set of bits that are "on the edges" of the polygon, so that their coverage
  61   // will be 1/2 on the average. in practice it's useless for anything but the even-odd fill rule
  62         int   ffBit,lfBit; // first and last bit of the portion of the line that is entirely covered
  63         ffBit=(int)(ceil(invScale*spos));
  64         lfBit=(int)(floor(invScale*epos));
  65         int   fpBit,lpBit; // first and last bit of the portion of the line that is not entirely but partially covered
  66         fpBit=(int)(floor(invScale*spos));
  67         lpBit=(int)(ceil(invScale*epos));
  68
  69   // update curMin and curMax to reflect the start and end pixel that need to be updated on the canvas
  70         if ( floor(spos) < curMin ) curMin=(int)floor(spos);
  71         if ( ceil(epos) > curMax ) curMax=(int)ceil(epos);
  72
  73   // clamp to the line
  74         if ( ffBit < stBit ) ffBit=stBit;
  75         if ( ffBit > enBit ) ffBit=enBit;
  76         if ( lfBit < stBit ) lfBit=stBit;
  77         if ( lfBit > enBit ) lfBit=enBit;
  78         if ( fpBit < stBit ) fpBit=stBit;
  79         if ( fpBit > enBit ) fpBit=enBit;
  80         if ( lpBit < stBit ) lpBit=stBit;
  81         if ( lpBit > enBit ) lpBit=enBit;
  82
  83   // offset to get actual bit position in the array
  84         ffBit-=stBit;
  85         lfBit-=stBit;
  86         fpBit-=stBit;
  87         lpBit-=stBit;
  88
  89   // get the end and start indices of the elements of fullB and partB that will receives coverage
  90         int   ffPos=ffBit>>5;
  91         int   lfPos=lfBit>>5;
  92         int   fpPos=fpBit>>5;
  93         int   lpPos=lpBit>>5;
  94   // get bit numbers in the last and first changed elements of the fullB and partB arrays
  95         int   ffRem=ffBit&31;
  96         int   lfRem=lfBit&31;
  97         int   fpRem=fpBit&31;
  98         int   lpRem=lpBit&31;
  99   // add the coverage
 100   // note that the "full" bits are always a subset of the "not empty" bits, ie of the partial bits
 101   // the function is a bit lame: since there is at most one bit that is partial but not full, or no full bit,
 102   // it does 2 times the optimal amount of work when the coverage is full. but i'm too lazy to change that...
 103         if ( fpPos == lpPos ) { // only one element of the arrays is modified
 104     // compute the vector of changed bits in the element
 105                 uint32_t  add=0xFFFFFFFF;
 106                 if ( lpRem < 32 ) {add>>=32-lpRem;add<<=32-lpRem; }
 107     if ( lpRem <= 0 ) add=0;
 108                 if ( fpRem > 0) {add<<=fpRem;add>>=fpRem;}
 109     // and put it in the line
 110     fullB[fpPos]&=~(add); // partial is exclusive from full, so partial bits are removed from fullB
 111     partB[fpPos]|=add;    // and added to partB
 112     if ( full ) { // if the coverage is full, add the vector of full bits
 113       if ( ffBit <= lfBit ) {
 114         add=0xFFFFFFFF;
 115         if ( lfRem < 32 ) {add>>=32-lfRem;add<<=32-lfRem;}
 116         if ( lfRem <= 0 ) add=0;
 117         if ( ffRem > 0 ) {add<<=ffRem;add>>=ffRem;}
 118         fullB[ffPos]|=add;
 119         partB[ffPos]&=~(add);
 120       }
 121     }
 122         } else {
 123     // first and last elements are differents, so add what appropriate to each
 124                 uint32_t  add=0xFFFFFFFF;
 125                 if ( fpRem > 0 ) {add<<=fpRem;add>>=fpRem;}
 126     fullB[fpPos]&=~(add);
 127     partB[fpPos]|=add;
 128
 129                 add=0xFFFFFFFF;
 130                 if ( lpRem < 32 ) {add>>=32-lpRem;add<<=32-lpRem;}
 131     if ( lpRem <= 0 ) add=0;
 132     fullB[lpPos]&=~(add);
 133     partB[lpPos]|=add;
 134
 135     // and fill what's in between with partial bits
 136     if ( lpPos > fpPos+1 ) memset(fullB+(fpPos+1),0x00,(lpPos-fpPos-1)*sizeof(uint32_t));
 137     if ( lpPos > fpPos+1 ) memset(partB+(fpPos+1),0xFF,(lpPos-fpPos-1)*sizeof(uint32_t));
 138
 139                 if ( full ) { // is the coverage is full, do your magic
 140       if ( ffBit <= lfBit ) {
 141         if ( ffPos == lfPos ) {
 142           add=0xFFFFFFFF;
 143           if ( lfRem < 32 ) {add>>=32-lfRem;add<<=32-lfRem;}
 144           if ( lfRem <= 0 ) add=0;
 145           if ( ffRem > 0 ) {add<<=ffRem;add>>=ffRem;}
 146           fullB[ffPos]|=add;
 147           partB[ffPos]&=~(add);
 148         } else {
 149           add=0xFFFFFFFF;
 150           if ( ffRem > 0 ) {add<<=ffRem;add>>=ffRem;}
 151           fullB[ffPos]|=add;
 152           partB[ffPos]&=~add;
 153
 154           add=0xFFFFFFFF;
 155           if ( lfRem < 32 ) {add>>=32-lfRem;add<<=32-lfRem;}
 156           if ( lfRem <= 0 ) add=0;
 157           fullB[lfPos]|=add;
 158           partB[lfPos]&=~add;
 159
 160           if ( lfPos > ffPos+1 ) memset(fullB+(ffPos+1),0xFF,(lfPos-ffPos-1)*sizeof(uint32_t));
 161           if ( lfPos > ffPos+1 ) memset(partB+(ffPos+1),0x00,(lfPos-ffPos-1)*sizeof(uint32_t));
 162         }
 163       }
 164     }
 165         }
 166         return 0;
 167 }
 168
 169
 170 void             BitLigne::Affiche(void)
 171 {
 172         for (int i=0;i<nbInt;i++) printf(" %.8x",fullB[i]);
 173         printf("\n");
 174         for (int i=0;i<nbInt;i++) printf(" %.8x",partB[i]);
 175         printf("\n\n");
 176 }
 177