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