[37] | 1 | /* |
---|
| 2 | |
---|
| 3 | Brian Curless |
---|
| 4 | |
---|
| 5 | Computer Graphics Laboratory |
---|
| 6 | Stanford University |
---|
| 7 | |
---|
| 8 | --------------------------------------------------------------------- |
---|
| 9 | |
---|
| 10 | Copyright (1997) The Board of Trustees of the Leland Stanford Junior |
---|
| 11 | University. Except for commercial resale, lease, license or other |
---|
| 12 | commercial transactions, permission is hereby given to use, copy, |
---|
| 13 | modify this software for academic purposes only. No part of this |
---|
| 14 | software or any derivatives thereof may be used in the production of |
---|
| 15 | computer models for resale or for use in a commercial |
---|
| 16 | product. STANFORD MAKES NO REPRESENTATIONS OR WARRANTIES OF ANY KIND |
---|
| 17 | CONCERNING THIS SOFTWARE. No support is implied or provided. |
---|
| 18 | |
---|
| 19 | */ |
---|
| 20 | |
---|
| 21 | |
---|
| 22 | #include <limits.h> |
---|
| 23 | #include <stdio.h> |
---|
| 24 | #include <unistd.h> |
---|
| 25 | #include <assert.h> |
---|
| 26 | |
---|
| 27 | #include "SectionRLE.h" |
---|
| 28 | |
---|
| 29 | SectionRLE::SectionRLE() |
---|
| 30 | { |
---|
| 31 | this->xdim = this->ydim = 0; |
---|
| 32 | this->rleScanline = new SectionScanlineRLE; |
---|
| 33 | this->defaultElement = new SectionElement; |
---|
| 34 | this->defaultElement->density = 0; |
---|
| 35 | this->defaultElement->nx = 0; |
---|
| 36 | this->defaultElement->ny = 0; |
---|
| 37 | this->defaultElement->nz = 0; |
---|
| 38 | this->defaultElement->confidence = 0; |
---|
| 39 | this->defaultElement->valid = FALSE; |
---|
| 40 | this->defaultElement->realData = TRUE; |
---|
| 41 | this->defaultElement->set.ntris = 0; |
---|
| 42 | } |
---|
| 43 | |
---|
| 44 | |
---|
| 45 | SectionRLE::SectionRLE(int xd, int yd, int num) |
---|
| 46 | { |
---|
| 47 | this->init(xd, yd, num); |
---|
| 48 | } |
---|
| 49 | |
---|
| 50 | |
---|
| 51 | void |
---|
| 52 | SectionRLE::init(int xd, int yd, int num) |
---|
| 53 | { |
---|
| 54 | this->xdim = xd; |
---|
| 55 | this->ydim = yd; |
---|
| 56 | |
---|
| 57 | this->rleScanline = new SectionScanlineRLE; |
---|
| 58 | |
---|
| 59 | this->lengthAddr = new RunLength*[this->ydim]; |
---|
| 60 | |
---|
| 61 | this->elementAddr = new SectionElement*[this->ydim]; |
---|
| 62 | |
---|
| 63 | // Lucas optimization init. Set cachedlength to be huge, |
---|
| 64 | // so that it will not be the "right run" for the first |
---|
| 65 | // try, and then will get initialized correctly. |
---|
| 66 | this->cachedX = new RunLength[this->ydim]; |
---|
| 67 | this->cachedLengthAddr = new RunLength*[this->ydim]; |
---|
| 68 | |
---|
| 69 | this->cachedElemAddr = new SectionElement*[this->ydim]; |
---|
| 70 | |
---|
| 71 | // Invalidate the cache |
---|
| 72 | for (int myy = 0; myy < this->ydim; myy++) { |
---|
| 73 | this->cachedX[myy] = USHRT_MAX; |
---|
| 74 | } |
---|
| 75 | |
---|
| 76 | this->lengthChunker = new ChunkAllocator(num); |
---|
| 77 | this->elementChunker = new ChunkAllocator(num); |
---|
| 78 | |
---|
| 79 | this->defaultElement = new SectionElement; |
---|
| 80 | this->defaultElement->density = 0; |
---|
| 81 | this->defaultElement->nx = 0; |
---|
| 82 | this->defaultElement->ny = 0; |
---|
| 83 | this->defaultElement->nz = 0; |
---|
| 84 | this->defaultElement->valid = FALSE; |
---|
| 85 | this->defaultElement->set.ntris = 0; |
---|
| 86 | |
---|
| 87 | this->clear(); |
---|
| 88 | } |
---|
| 89 | |
---|
| 90 | |
---|
| 91 | SectionRLE::~SectionRLE() |
---|
| 92 | { |
---|
| 93 | this->freeSpace(); |
---|
| 94 | } |
---|
| 95 | |
---|
| 96 | |
---|
| 97 | void |
---|
| 98 | SectionRLE::freeSpace() |
---|
| 99 | { |
---|
| 100 | if (this->lengthAddr != NULL) { |
---|
| 101 | delete [] this->lengthAddr; |
---|
| 102 | } |
---|
| 103 | if (this->elementAddr != NULL) { |
---|
| 104 | delete [] this->elementAddr; |
---|
| 105 | } |
---|
| 106 | if (this->defaultElement != NULL) { |
---|
| 107 | delete this->defaultElement; |
---|
| 108 | } |
---|
| 109 | } |
---|
| 110 | |
---|
| 111 | void |
---|
| 112 | SectionRLE::clear() |
---|
| 113 | { |
---|
| 114 | RunLength length, end; |
---|
| 115 | |
---|
| 116 | this->reset(); |
---|
| 117 | |
---|
| 118 | setRunType(&end, SectionRLE::END_OF_RUN); |
---|
| 119 | |
---|
| 120 | length = this->xdim; |
---|
| 121 | setRunType(&length, SectionRLE::CONSTANT_DATA); |
---|
| 122 | |
---|
| 123 | for (int yy = 0; yy < this->ydim; yy++) { |
---|
| 124 | allocNewRun(yy); |
---|
| 125 | putNextLength(length); |
---|
| 126 | putNextElement(defaultElement); |
---|
| 127 | putNextLength(end); |
---|
| 128 | } |
---|
| 129 | } |
---|
| 130 | |
---|
| 131 | |
---|
| 132 | |
---|
| 133 | |
---|
| 134 | void |
---|
| 135 | SectionRLE::setRunType(RunLength *length, int runType) |
---|
| 136 | { |
---|
| 137 | if (runType == SectionRLE::END_OF_RUN) |
---|
| 138 | *length = SectionRLE::END_OF_RUN; |
---|
| 139 | else if (runType == SectionRLE::VARYING_DATA) |
---|
| 140 | *length = *length | SectionRLE::HIGHEST_BIT; |
---|
| 141 | |
---|
| 142 | // else leave it alone |
---|
| 143 | } |
---|
| 144 | |
---|
| 145 | void |
---|
| 146 | SectionRLE::reset() |
---|
| 147 | { |
---|
| 148 | this->lengthChunker->reset(); |
---|
| 149 | this->elementChunker->reset(); |
---|
| 150 | } |
---|
| 151 | |
---|
| 152 | |
---|
| 153 | void |
---|
| 154 | SectionRLE::putNextElement(SectionElement *element) |
---|
| 155 | { |
---|
| 156 | SectionElement *newElem = |
---|
| 157 | (SectionElement *)this->elementChunker->alloc(sizeof(SectionElement)); |
---|
| 158 | newElem->density = element->density; |
---|
| 159 | newElem->nx = element->nx; |
---|
| 160 | newElem->ny = element->ny; |
---|
| 161 | newElem->nz = element->nz; |
---|
| 162 | newElem->confidence = element->confidence; |
---|
| 163 | newElem->valid = element->valid; |
---|
| 164 | newElem->realData = element->realData; |
---|
| 165 | newElem->set.ntris = element->set.ntris; |
---|
| 166 | } |
---|
| 167 | |
---|
| 168 | |
---|
| 169 | void |
---|
| 170 | SectionRLE::putNextLength(RunLength length) |
---|
| 171 | { |
---|
| 172 | RunLength *newLength = |
---|
| 173 | (RunLength *)this->lengthChunker->alloc(sizeof(RunLength)); |
---|
| 174 | *newLength = length; |
---|
| 175 | } |
---|
| 176 | |
---|
| 177 | |
---|
| 178 | |
---|
| 179 | |
---|
| 180 | void |
---|
| 181 | SectionRLE::allocNewRun(int y) |
---|
| 182 | { |
---|
| 183 | // Make room for contiguous runs and point the length and data |
---|
| 184 | // pointers to the next place that length and data will be put |
---|
| 185 | |
---|
| 186 | this->elementChunker->newChunkIfNeeded(sizeof(SectionElement)*(this->xdim+1)); |
---|
| 187 | this->elementAddr[y] = |
---|
| 188 | (SectionElement *)this->elementChunker->currentAddr; |
---|
| 189 | |
---|
| 190 | this->lengthChunker->newChunkIfNeeded(sizeof(RunLength)*(this->xdim+1)); |
---|
| 191 | this->lengthAddr[y] = |
---|
| 192 | (RunLength *)this->lengthChunker->currentAddr; |
---|
| 193 | |
---|
| 194 | setScanline(y); |
---|
| 195 | |
---|
| 196 | // Lucas: Invalidate the cached value |
---|
| 197 | this->cachedX[y] = USHRT_MAX; |
---|
| 198 | } |
---|
| 199 | |
---|
| 200 | |
---|
| 201 | void |
---|
| 202 | SectionRLE::setScanline(int y) |
---|
| 203 | { |
---|
| 204 | currentLength = this->lengthAddr[y]; |
---|
| 205 | currentElem = this->elementAddr[y]; |
---|
| 206 | } |
---|
| 207 | |
---|
| 208 | // Lucas: |
---|
| 209 | // getElement is now an inline function, |
---|
| 210 | // which calls getElementSlow if necessary |
---|
| 211 | // (e.g. it doesn't have the right run in cache...) |
---|
| 212 | |
---|
| 213 | |
---|
| 214 | SectionElement * |
---|
| 215 | SectionRLE::getElementSlow(int xx, int yy) |
---|
| 216 | { |
---|
| 217 | SectionElement *element=NULL; |
---|
| 218 | RunLength *oldCurrentLength; |
---|
| 219 | SectionElement *oldCurrentElem; |
---|
| 220 | |
---|
| 221 | RunLength length; |
---|
| 222 | int runType; |
---|
| 223 | |
---|
| 224 | // Save the old position pointers |
---|
| 225 | oldCurrentLength = currentLength; |
---|
| 226 | oldCurrentElem = currentElem; |
---|
| 227 | |
---|
| 228 | setScanline(yy); |
---|
| 229 | |
---|
| 230 | RunLength currentX = 0; |
---|
| 231 | |
---|
| 232 | // If cached values are less than the desired X, |
---|
| 233 | // use it as a starting point... |
---|
| 234 | if (cachedX[yy] <= xx) { |
---|
| 235 | currentX = cachedX[yy]; |
---|
| 236 | currentLength = cachedLengthAddr[yy]; |
---|
| 237 | currentElem = cachedElemAddr[yy]; |
---|
| 238 | } |
---|
| 239 | |
---|
| 240 | for ( ; currentX <= xx; currentX += length) { |
---|
| 241 | |
---|
| 242 | // Lucas: Save the starting point for this run. |
---|
| 243 | // when loop exits, cache saves last run used. |
---|
| 244 | cachedX[yy] = currentX; |
---|
| 245 | cachedLengthAddr[yy] = currentLength; |
---|
| 246 | cachedElemAddr[yy] = currentElem; |
---|
| 247 | |
---|
| 248 | length = getNextLength(); |
---|
| 249 | runType = getRunType(&length); |
---|
| 250 | |
---|
| 251 | |
---|
| 252 | // Lucas: Be dangerous. You only live once. |
---|
| 253 | // skip the assertion. It's inside a critical loop. |
---|
| 254 | // assert(runType != SectionRLE::END_OF_RUN); |
---|
| 255 | |
---|
| 256 | if (runType == SectionRLE::CONSTANT_DATA) { |
---|
| 257 | element = getNextElement(); |
---|
| 258 | } else { |
---|
| 259 | if (xx < currentX+length) { |
---|
| 260 | currentElem += (xx - currentX); |
---|
| 261 | element = getNextElement(); |
---|
| 262 | } else { |
---|
| 263 | currentElem += length; |
---|
| 264 | } |
---|
| 265 | } |
---|
| 266 | } |
---|
| 267 | |
---|
| 268 | // Restore the old position pointers |
---|
| 269 | currentLength = oldCurrentLength; |
---|
| 270 | currentElem = oldCurrentElem; |
---|
| 271 | |
---|
| 272 | return element; |
---|
| 273 | } |
---|
| 274 | |
---|
| 275 | |
---|
| 276 | void |
---|
| 277 | SectionRLE::copyScanline(SectionScanlineRLE *rleScanline, int y) |
---|
| 278 | { |
---|
| 279 | int i; |
---|
| 280 | RunLength length; |
---|
| 281 | int runType; |
---|
| 282 | SectionElement *element; |
---|
| 283 | |
---|
| 284 | rleScanline->reset(); |
---|
| 285 | allocNewRun(y); |
---|
| 286 | |
---|
| 287 | while (TRUE) { |
---|
| 288 | length = rleScanline->getNextLength(); |
---|
| 289 | putNextLength(length); |
---|
| 290 | |
---|
| 291 | runType = getRunType(&length); |
---|
| 292 | |
---|
| 293 | if (runType == SectionRLE::END_OF_RUN) |
---|
| 294 | break; |
---|
| 295 | |
---|
| 296 | if (runType == SectionRLE::CONSTANT_DATA) { |
---|
| 297 | element = rleScanline->getNextElement(); |
---|
| 298 | putNextElement(element); |
---|
| 299 | } |
---|
| 300 | else { |
---|
| 301 | for (i=0; i<length; i++) { |
---|
| 302 | element = rleScanline->getNextElement(); |
---|
| 303 | putNextElement(element); |
---|
| 304 | } |
---|
| 305 | } |
---|
| 306 | } |
---|
| 307 | } |
---|
| 308 | |
---|
| 309 | |
---|
| 310 | void |
---|
| 311 | SectionRLE::copy(SectionRLE *other) |
---|
| 312 | { |
---|
| 313 | SectionScanlineRLE *rleScanline; |
---|
| 314 | |
---|
| 315 | this->reset(); |
---|
| 316 | |
---|
| 317 | for (int yy = 0; yy < this->ydim; yy++) { |
---|
| 318 | rleScanline = other->getRLEScanline(yy); |
---|
| 319 | this->copyScanline(rleScanline, yy); |
---|
| 320 | } |
---|
| 321 | } |
---|
| 322 | |
---|
| 323 | |
---|
| 324 | SectionScanlineRLE * |
---|
| 325 | SectionRLE::getRLEScanline(int y) |
---|
| 326 | { |
---|
| 327 | setScanline(y); |
---|
| 328 | rleScanline->lengths = currentLength; |
---|
| 329 | rleScanline->elements = currentElem; |
---|
| 330 | rleScanline->reset(); |
---|
| 331 | return rleScanline; |
---|
| 332 | } |
---|
| 333 | |
---|
| 334 | |
---|
| 335 | |
---|
| 336 | |
---|
| 337 | |
---|