1/*********************************************************************** 2 * * 3 * $Id: hpgsimagerop.c 372 2007-01-14 18:16:03Z softadm $ 4 * * 5 * hpgs - HPGl Script, a hpgl/2 interpreter, which uses a Postscript * 6 * API for rendering a scene and thus renders to a variety of * 7 * devices and fileformats. * 8 * * 9 * (C) 2004-2006 ev-i Informationstechnologie GmbH http://www.ev-i.at * 10 * * 11 * Author: Wolfgang Glas * 12 * * 13 * hpgs is free software; you can redistribute it and/or * 14 * modify it under the terms of the GNU Lesser General Public * 15 * License as published by the Free Software Foundation; either * 16 * version 2.1 of the License, or (at your option) any later version. * 17 * * 18 * hpgs is distributed in the hope that it will be useful, * 19 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * 21 * Lesser General Public License for more details. * 22 * * 23 * You should have received a copy of the GNU Lesser General Public * 24 * License along with this library; if not, write to the * 25 * Free Software Foundation, Inc., 59 Temple Place, Suite 330, * 26 * Boston, MA 02111-1307 USA * 27 * * 28 *********************************************************************** 29 * * 30 * The implementation of the ROP3 clip frame extraction from images. * 31 * * 32 ***********************************************************************/ 33 34#include <hpgs.h> 35#include <assert.h> 36#if defined ( __MINGW32__ ) || defined ( _MSC_VER ) 37#include<malloc.h> 38#else 39#include<alloca.h> 40#endif 41 42// #define HPGS_IMAGE_ROP_DEBUG 43 44typedef struct hpgs_img_clip_seg_st hpgs_img_clip_seg; 45 46struct hpgs_img_clip_seg_st 47{ 48 int j; 49 int i_vert; 50}; 51 52typedef struct hpgs_img_clip_line_st hpgs_img_clip_line; 53 54struct hpgs_img_clip_line_st 55{ 56 int i0; 57 int j0; 58 59 int i1; 60 int j1; 61 62 int key; 63 int usage; 64}; 65 66#define MK_LINE_KEY(i,j) ((j)+(img->width+1)*(i)) 67 68static int compare_clip_lines (const void *a, const void *b) 69{ 70 const hpgs_img_clip_line *la = (const hpgs_img_clip_line *)a; 71 const hpgs_img_clip_line *lb = (const hpgs_img_clip_line *)b; 72 73 if (la->key < lb->key) return -1; 74 if (la->key > lb->key) return 1; 75 return 0; 76} 77 78static int grow_clip_lines (hpgs_device *device, 79 hpgs_img_clip_line **clip_lines, 80 size_t *clip_lines_sz) 81{ 82 size_t nsz = *clip_lines_sz*2; 83 hpgs_img_clip_line *ncl=realloc(*clip_lines,nsz*sizeof(hpgs_img_clip_line)); 84 85 if (!ncl) 86 return hpgs_set_error(hpgs_i18n("hpgs_image_rop3_clip: Out of memory growing temporary storage.")); 87 88 *clip_lines = ncl; 89 *clip_lines_sz = nsz; 90 return 0; 91} 92 93/*! 94 Sets a clip frame to the given device, which encloses all regions 95 of the device, which are cover by the image taking into account 96 the given ROP3 transfer function. 97 98 The argument \c data must contain a pointer to a two-dimensional 99 array of raw pixels of the size of the image. This array is filled 100 with pixel values as if the image has been painted to a white 101 destination area using the given ROP3 function. 102 103 Return values: 104 \li 0 The clip frame is empty, no operation has been performed on 105 the output device. 106 107 \li 1 The clip frame is not empty, the clip path has been 108 set to the output device using clipsave/moveto/lineto/clip 109 operations. 110 111 \li 2 The clip frame covers the whole image, no operation has been 112 performed on the output device. 113 114 \li 3 The clip frame is not empty, the visible pixels have all the same color 115 and clip path has been set to the output device using 116 moveto/lineto/setrgbcolor/fill operations. The image does not have to be 117 transferred by subsequent functions, the rgb color of the device has been 118 altered. 119 120 \li -1 An error occured on the output device. 121 122*/ 123int hpgs_image_rop3_clip(hpgs_device *device, 124 hpgs_palette_color *data, 125 const hpgs_image *img, 126 const hpgs_point *ll, const hpgs_point *lr, 127 const hpgs_point *ur, 128 const hpgs_palette_color *p, 129 hpgs_xrop3_func_t xrop3) 130{ 131 // The upper bound for clip_lines_sz is (w+1)*(h+1)*2. 132 // This formula is chosen so, that for w==1 and h==1, 133 // this result is achieved. For larger pictures, we 134 // use 1/8th of the upper bound, which is pretty conservative. 135 // If not doing so, the algorithm easily consumes up to 1GB or more, 136 // which is too much for alloca, too. So this estimation combined 137 // with the usage of malloc should make the code robust. 138 size_t clip_lines_sz = ((img->width+1)*(img->height+1)+31)/4; 139 140 hpgs_img_clip_line *clip_lines = (hpgs_img_clip_line *) 141 malloc(sizeof(hpgs_img_clip_line)*clip_lines_sz); 142 143 hpgs_img_clip_seg *segs0 = (hpgs_img_clip_seg *) 144 hpgs_alloca(sizeof(hpgs_img_clip_seg)*(img->width+1)); 145 146 hpgs_img_clip_seg *segs1 = (hpgs_img_clip_seg *) 147 hpgs_alloca(sizeof(hpgs_img_clip_seg)*(img->width+1)); 148 149 if (!clip_lines || !segs0 || !segs1) 150 return hpgs_set_error(hpgs_i18n("hpgs_image_rop3_clip: Out of memory allocating temporary storage.")); 151 152 int n_clip_lines = 0; 153 int ret = -1; 154 int i_seg0,n_segs0 = 0; 155 int i_seg1,n_segs1 = 0; 156 157 hpgs_point ul; 158 int i,j; 159 160 hpgs_bool all_visible = HPGS_TRUE; 161 hpgs_palette_color *first_visible_pixel = 0; 162 hpgs_bool single_color = HPGS_FALSE; 163 164 ul.x = ll->x + (ur->x - lr->x); 165 ul.y = ll->y + (ur->y - lr->y); 166 167 // first, accumulate lines. 168 for (i=0;i<img->height+1;++i) 169 { 170 // cut the current raster line 171 int t_last = 1; 172 n_segs1 = 0; 173 174 // this is here in order to construct all lines 175 // for the very last grid line 176 if (i<img->height) 177 { 178 for (j=0;j<img->width;++j) 179 { 180 int t; 181 hpgs_paint_color s; 182 unsigned r,g,b; 183 184 hpgs_image_get_pixel(img,j,i,&s,0); 185 186 r = xrop3(s.r,p->r); 187 g = xrop3(s.g,p->g); 188 b = xrop3(s.b,p->b); 189 190 // transparent ? 191 t = (r == 0x00ff && g == 0x00ff && b == 0x00ff); 192 193 if (t != t_last) // last pixel different transparency ? 194 { 195 segs1[n_segs1].j = j; 196 segs1[n_segs1].i_vert = -1; 197 ++n_segs1; 198 } 199 200 t_last = t; 201 202 data->r = (unsigned char)r; 203 data->g = (unsigned char)g; 204 data->b = (unsigned char)b; 205 206 if (!t) 207 { 208 if (!first_visible_pixel) 209 { 210 first_visible_pixel = data; 211 single_color = HPGS_TRUE; 212 } 213 else if (single_color && 214 (first_visible_pixel->r != data->r || 215 first_visible_pixel->g != data->g || 216 first_visible_pixel->b != data->b )) 217 single_color = HPGS_FALSE; 218 } 219 220 ++data; 221 } 222 223 if (n_segs1 != 1 || segs1[0].j > 0) 224 all_visible = HPGS_FALSE; 225 226 // close trailing visible segment. 227 if (t_last == 0) 228 { 229 segs1[n_segs1].j = j; 230 segs1[n_segs1].i_vert = -1; 231 ++n_segs1; 232 } 233 } 234 235 assert(n_segs1 <= (img->width+1)); 236 237#ifdef HPGS_IMAGE_ROP_DEBUG 238 hpgs_log("i=%d: segs1:",i); 239 240 for (j=0;j<n_segs1;++j) 241 hpgs_log("%c%d",j?',':' ',segs1[j].j); 242 hpgs_log("\n"); 243 244 j=n_clip_lines; 245#endif 246 247 // construct lines. 248 i_seg0 = 0; 249 i_seg1 = 0; 250 t_last = -1; 251 252 while (i_seg0 < n_segs0 || i_seg1 < n_segs1) 253 { 254 if (i_seg1 >= n_segs1 || (i_seg0 < n_segs0 && segs0[i_seg0].j < segs1[i_seg1].j)) 255 { 256 // horizontal line. 257 if (t_last >= 0) 258 { 259 clip_lines[n_clip_lines].i0 = i; 260 clip_lines[n_clip_lines].i1 = i; 261 // check for the orientation. 262 if (i_seg0 & 1) 263 { 264 clip_lines[n_clip_lines].j0 = t_last; 265 clip_lines[n_clip_lines].j1 = segs0[i_seg0].j; 266 } 267 else 268 { 269 clip_lines[n_clip_lines].j0 = segs0[i_seg0].j; 270 clip_lines[n_clip_lines].j1 = t_last; 271 } 272 273 if (++n_clip_lines >= clip_lines_sz && 274 grow_clip_lines(device,&clip_lines,&clip_lines_sz)) 275 goto cleanup; 276 277 t_last = -1; 278 } 279 else 280 t_last = segs0[i_seg0].j; 281 282 283 ++i_seg0; 284 } 285 else if (i_seg0 >= n_segs0 || segs1[i_seg1].j < segs0[i_seg0].j) 286 { 287 // horizontal line. 288 if (t_last >= 0) 289 { 290 clip_lines[n_clip_lines].i0 = i; 291 clip_lines[n_clip_lines].i1 = i; 292 // check for the orientation. 293 if (i_seg1 & 1) 294 { 295 clip_lines[n_clip_lines].j0 = segs1[i_seg1].j; 296 clip_lines[n_clip_lines].j1 = t_last; 297 } 298 else 299 { 300 clip_lines[n_clip_lines].j0 = t_last; 301 clip_lines[n_clip_lines].j1 = segs1[i_seg1].j; 302 } 303 if (++n_clip_lines >= clip_lines_sz && 304 grow_clip_lines(device,&clip_lines,&clip_lines_sz)) 305 goto cleanup; 306 t_last = -1; 307 } 308 else 309 t_last = segs1[i_seg1].j; 310 311 // create vertical line. 312 clip_lines[n_clip_lines].j0 = segs1[i_seg1].j; 313 clip_lines[n_clip_lines].j1 = segs1[i_seg1].j; 314 315 // check for the orientation. 316 if (i_seg1 & 1) 317 { 318 clip_lines[n_clip_lines].i0 = i+1; 319 clip_lines[n_clip_lines].i1 = i; 320 } 321 else 322 { 323 clip_lines[n_clip_lines].i0 = i; 324 clip_lines[n_clip_lines].i1 = i+1; 325 } 326 327 segs1[i_seg1].i_vert = n_clip_lines; 328 if (++n_clip_lines >= clip_lines_sz && 329 grow_clip_lines(device,&clip_lines,&clip_lines_sz)) 330 goto cleanup; 331 332 ++i_seg1; 333 } 334 else 335 { 336 assert(segs0[i_seg0].j == segs1[i_seg1].j); 337 338 // horizontal line. 339 if (t_last >= 0) 340 { 341 clip_lines[n_clip_lines].i0 = i; 342 clip_lines[n_clip_lines].i1 = i; 343 // check for the orientation. 344 if (i_seg1 & 1) 345 { 346 clip_lines[n_clip_lines].j0 = segs1[i_seg1].j; 347 clip_lines[n_clip_lines].j1 = t_last; 348 } 349 else 350 { 351 clip_lines[n_clip_lines].j0 = t_last; 352 clip_lines[n_clip_lines].j1 = segs1[i_seg1].j; 353 } 354 355 if (++n_clip_lines >= clip_lines_sz && 356 grow_clip_lines(device,&clip_lines,&clip_lines_sz)) 357 goto cleanup; 358 } 359 360 if ((i_seg0 & 1) == (i_seg1 & 1)) 361 { 362 // extend segment 363 int il = segs0[i_seg0].i_vert; 364 if (i_seg1 & 1) 365 clip_lines[il].i0 = i+1; 366 else 367 clip_lines[il].i1= i+1; 368 369 segs1[i_seg1].i_vert = il; 370 t_last = -1; 371 } 372 else 373 { 374 // create new segment. 375 clip_lines[n_clip_lines].j0 = segs1[i_seg1].j; 376 clip_lines[n_clip_lines].j1 = segs1[i_seg1].j; 377 378 if (i_seg1 & 1) 379 { 380 clip_lines[n_clip_lines].i0 = i+1; 381 clip_lines[n_clip_lines].i1 = i; 382 } 383 else 384 { 385 clip_lines[n_clip_lines].i0 = i; 386 clip_lines[n_clip_lines].i1 = i+1; 387 } 388 389 segs1[i_seg1].i_vert = n_clip_lines; 390 391 if (++n_clip_lines >= clip_lines_sz && 392 grow_clip_lines(device,&clip_lines,&clip_lines_sz)) 393 goto cleanup; 394 395 t_last = segs1[i_seg1].j; 396 } 397 398 ++i_seg0; 399 ++i_seg1; 400 } 401 } 402 403#ifdef HPGS_IMAGE_ROP_DEBUG 404 hpgs_log("i=%d: lines: ",i); 405 406 for (;j<n_clip_lines;++j) 407 hpgs_log("(%d,%d,%d,%d)", 408 clip_lines[j].i0,clip_lines[j].j0, 409 clip_lines[j].i1,clip_lines[j].j1); 410 hpgs_log("\n"); 411#endif 412 assert (t_last == -1); 413 414 // swap clip segment caches 415 { 416 hpgs_img_clip_seg *tmp = segs0; 417 segs0=segs1; 418 segs1=tmp; 419 } 420 n_segs0 = n_segs1; 421 } 422 423#ifdef HPGS_IMAGE_ROP_DEBUG 424 hpgs_log("clip_img: n_clip_lines,all_visible = %d,%d.\n", 425 n_clip_lines,all_visible); 426#endif 427 428 if (n_clip_lines <= 0) { ret = 0; goto cleanup; } 429 if (all_visible && !single_color) { ret = 2; goto cleanup; } 430 431 assert(n_clip_lines <= (img->width+1)*(img->height+1)*2); 432 433 // OK, now create the lookup key of the lines. 434 for (i=0;i<n_clip_lines;++i) 435 { 436 clip_lines[i].key = MK_LINE_KEY(clip_lines[i].i0,clip_lines[i].j0); 437 clip_lines[i].usage = 0; 438 } 439 440 // sort the table 441 qsort(clip_lines,n_clip_lines,sizeof(hpgs_img_clip_line),compare_clip_lines); 442 443 if (!single_color && hpgs_clipsave(device)) goto cleanup; 444 445 // now construct the clip path. 446 for (i = 0;i<n_clip_lines;++i) 447 { 448 hpgs_img_clip_line *line = clip_lines+i; 449 int iline = 0; 450 451 if (line->usage) continue; 452 453 do 454 { 455 hpgs_point p; 456 int key,i0,i1; 457 458 p.x = ul.x + 459 line->j0 * (lr->x - ll->x) / img->width + 460 line->i0 * (lr->x - ur->x) / img->height ; 461 462 p.y = ul.y + 463 line->j0 * (lr->y - ll->y) / img->width + 464 line->i0 * (lr->y - ur->y) / img->height ; 465 466 key = MK_LINE_KEY(line->i1,line->j1); 467 468 if (iline) 469 { 470 if (hpgs_lineto(device,&p)) goto cleanup; 471 } 472 else 473 { 474 if (hpgs_moveto(device,&p)) goto cleanup; 475 } 476 477#ifdef HPGS_IMAGE_ROP_DEBUG 478 hpgs_log("(%d,%d,%d,%d)", 479 line->i0,line->j0, 480 line->i1,line->j1); 481#endif 482 ++iline; 483 line->usage=1; 484 485 // binary search 486 i0 = 0; 487 i1 = n_clip_lines; 488 489 while (i1>i0) 490 { 491 int ii = i0+(i1-i0)/2; 492 493 if (clip_lines[ii].key < key) 494 i0 = ii+1; 495 else 496 i1 = ii; 497 } 498 499 while (clip_lines[i0].usage && 500 i0 < n_clip_lines-1 && 501 clip_lines[i0+1].key == key) 502 ++i0; 503 504 assert(i0 < n_clip_lines && key == clip_lines[i0].key); 505 506 line = clip_lines+i0; 507 508 assert (line); 509 510 if (line->usage && line < clip_lines + n_clip_lines && 511 line[1].key == key) 512 ++line; 513 } 514 while (!line->usage); 515 516 assert (line->i0 == clip_lines[i].i0 && 517 line->j0 == clip_lines[i].j0 ); 518 519#ifdef HPGS_IMAGE_ROP_DEBUG 520 hpgs_log("\n"); 521#endif 522 if (hpgs_closepath(device)) goto cleanup; 523 } 524 525 if (single_color) 526 { 527 hpgs_color c; 528 529 c.r = first_visible_pixel->r / 255.0; 530 c.g = first_visible_pixel->g / 255.0; 531 c.b = first_visible_pixel->b / 255.0; 532 533 if (hpgs_setrgbcolor(device,&c)) goto cleanup; 534 if (hpgs_fill(device,HPGS_FALSE)) goto cleanup; 535 if (hpgs_newpath(device)) goto cleanup; 536 537 ret = 3; 538 } 539 540 else 541 { 542 if (hpgs_clip(device,HPGS_FALSE)) goto cleanup; 543 if (hpgs_newpath(device)) goto cleanup; 544 545 ret = 1; 546 } 547 548 cleanup: 549 if (clip_lines) free(clip_lines); 550 return ret; 551} 552