1 /* 2 Vector font tool - Gaz Davidson December 2006-2012 3 4 I noticed bitmap fonts were taking massive amounts of video memory at reasonable sizes, 5 so I decided to make a vector font. I always wanted to try converting pixels to triangles... 6 7 And I failed! This is a collection of the ugliest, bloated, most inneficient algorithms 8 i've ever written, but its kinda working so I'm not changing it. 9 */ 10 11 #ifndef __VECTOR_FONT_TOOL_INCLUDED__ 12 #define __VECTOR_FONT_TOOL_INCLUDED__ 13 14 #include "irrlicht.h" 15 #include "CFontTool.h" 16 #include <assert.h> 17 18 using namespace irr; 19 using namespace video; 20 21 struct STriangleList 22 { 23 core::array<core::vector2df> positions; 24 core::array<u16> indexes; 25 26 // for adding one triangle list to another, 27 // these triangles share positions, but dont share triangles 28 STriangleList& operator+=(STriangleList &other) 29 { 30 core::matrix4 m; 31 core::array<s32> map; 32 map.set_used(other.positions.size()); 33 34 for (u32 i=0; i<map.size(); ++i) 35 map[i]=-1; 36 37 for (u32 i=0; i<positions.size(); ++i) 38 for (u32 j=0; j<map.size(); ++j) 39 if ( positions[i] == other.positions[j] ) 40 map[j] = i; 41 42 for (u32 i=0; i<map.size(); ++i) 43 if (map[i] == -1) 44 { 45 positions.push_back(other.positions[i]); 46 map[i] = positions.size()-1; 47 } 48 49 // add triangles 50 for (u32 i=0; i<other.indexes.size(); ++i) 51 indexes.push_back((u32)map[other.indexes[i]]); 52 53 return *this; 54 } 55 56 // functions for building triangles for shapes, 57 // each shape can't have duplicate triangles hasTriangleSTriangleList58 bool hasTriangle(core::vector2df a, core::vector2df b, core::vector2df c) 59 { 60 // make sure the triangle is wound correctly 61 if (core::line2df(a,b).getPointOrientation(c) < 0) 62 { core::vector2df tmp=a; a=b; b=tmp; } 63 64 u32 ia=0xffffffff, ib=0xffffffff, ic=0xffffffff; 65 // Find each vertex 66 for (u32 i=0; i < positions.size() && (ia==(u32)-1||ib==(u32)-1||ic==(u32)-1) ; ++i) 67 { 68 if (positions[i] == a) 69 ia = i; 70 if (positions[i] == b) 71 ib = i; 72 if (positions[i] == c) 73 ic = i; 74 } 75 76 if (ia==0xffffffff) 77 { 78 return false; 79 } 80 if (ib==0xffffffff) 81 { 82 return false; 83 } 84 if (ic==0xffffffff) 85 { 86 return false; 87 } 88 89 for (u32 i=0; i<indexes.size(); i+=3) 90 if ( (indexes[i] == ia && indexes[i+1] == ib && indexes[i+2] == ic) || 91 (indexes[i] == ic && indexes[i+1] == ia && indexes[i+2] == ib) || 92 (indexes[i] == ib && indexes[i+1] == ic && indexes[i+2] == ia) ) 93 return true; 94 95 return false; 96 } 97 addSTriangleList98 void add(core::vector2df a, core::vector2df b, core::vector2df c) 99 { 100 101 // make sure the triangle is wound correctly 102 if (core::line2df(a,b).getPointOrientation(c) < 0) 103 { 104 core::vector2df tmp=a; a=b; b=tmp; 105 } 106 107 u32 ia=0xffffffff, ib=0xffffffff, ic=0xffffffff; 108 // no duplicate vertex positions allowed... 109 for (u32 i=0; i < positions.size() && (ia==-1||ib==-1||ic==-1) ; ++i) 110 { 111 if (positions[i] == a) 112 ia = i; 113 if (positions[i] == b) 114 ib = i; 115 if (positions[i] == c) 116 ic = i; 117 } 118 bool found=true; 119 if (ia==0xffffffff) 120 { 121 ia = positions.size(); 122 positions.push_back(a); 123 found=false; 124 } 125 if (ib==0xffffffff) 126 { 127 ib = positions.size(); 128 positions.push_back(b); 129 found=false; 130 } 131 if (ic==0xffffffff) 132 { 133 ic = positions.size(); 134 positions.push_back(c); 135 found=false; 136 } 137 138 // no duplicate triangles allowed 139 if (found) 140 { 141 found=false; 142 for (u32 i=0; i<indexes.size(); i+=3) 143 { 144 if ( (indexes[i] == ia && indexes[i+1] == ib && indexes[i+2] == ic) || 145 (indexes[i] == ic && indexes[i+1] == ia && indexes[i+2] == ib) || 146 (indexes[i] == ib && indexes[i+1] == ic && indexes[i+2] == ia) ) 147 { 148 found=true; 149 break; 150 } 151 } 152 } 153 154 if (!found) 155 { 156 indexes.push_back(ia); 157 indexes.push_back(ib); 158 indexes.push_back(ic); 159 } 160 } 161 }; 162 163 // finds groups of pixels and triangulates them 164 class CGroupFinder 165 { 166 public: CGroupFinder(bool * memory,s32 w,s32 h,IrrlichtDevice * dev)167 CGroupFinder(bool *memory, s32 w, s32 h, IrrlichtDevice *dev): 168 width(w), height(h), mem(memory), Device(dev) 169 { 170 refbuffer.set_used(w*h); 171 for (u32 i=0; i<refbuffer.size(); ++i) 172 refbuffer[i]=0; 173 // find groups of pixels 174 findGroups(); 175 removeGroups(); 176 177 // triangulate 178 for (u32 i=0; i<groups.size(); ++i) 179 { 180 groups[i].triangulate(); 181 } 182 } 183 184 // contains a clockwise edge line 185 struct SEdge 186 { SEdgeSEdge187 SEdge() : positions() { } 188 189 core::array<core::position2di> positions; 190 isMemberSEdge191 bool isMember(s32 x, s32 y) 192 { 193 for (u32 i=0; i<positions.size(); ++i) 194 if (positions[i].X == x && positions[i].Y == y) 195 return true; 196 return false; 197 } 198 199 // reduces the number of points in the edge 200 void reduce(s32 level=0) 201 { 202 // level 0- remove points on the same line 203 for (u32 i=1; i < positions.size()-1; ++i) 204 { 205 // same point as the last one?! shouldnt happen, dunno why it does :| 206 if (positions[i-1] == positions[i]) 207 { 208 positions.erase(i--); 209 continue; 210 } 211 212 // get headings 213 core::vector2d<f32> h1((f32)(positions[i-1].X - positions[i].X),(f32)(positions[i-1].Y - positions[i].Y)), 214 h2((f32)(positions[i].X - positions[i+1].X),(f32)(positions[i].Y - positions[i+1].Y)); 215 h1.normalize(); 216 h2.normalize(); 217 218 if (h1==h2) // erase the current point 219 positions.erase(i--); 220 } 221 222 // level 1- if point1 points at point3, we can skip point2 223 // level 2+ allow a deviation of level-1 224 225 } 226 227 }; 228 229 // contains an array of lines for triangulation 230 struct SLineList 231 { 232 core::array<core::line2df> lines; SLineListSLineList233 SLineList() : lines() { } addEdgeSLineList234 void addEdge(const SEdge &edge) 235 { 236 // adds lines to the buffer 237 for (u32 i=1; i<edge.positions.size(); ++i) 238 addLine(core::line2df((f32)edge.positions[i-1].X, (f32)edge.positions[i-1].Y, 239 (f32)edge.positions[i].X, (f32)edge.positions[i].Y )); 240 } addLineSLineList241 void addLine( const core::line2df &line ) 242 { 243 // no dupes! 244 if (!hasLine(line)) 245 lines.push_back(line); 246 } hasLineSLineList247 bool hasLine( const core::line2df &line ) 248 { 249 for (u32 i=0; i<lines.size(); ++i) 250 if (line == lines[i] || (line.start == lines[i].end && line.end == lines[i].start) ) 251 return true; 252 return false; 253 } 254 crossesWithSLineList255 bool crossesWith( core::line2df l, core::vector2df p) 256 { 257 // inside checks only work with clockwise triangles 258 if (l.getPointOrientation(p) < 0) 259 { core::vector2df tmp=l.start; l.start=l.end; l.end=tmp; } 260 261 // make the 3 triangle edges 262 core::line2df &la=l, lb(l.end,p), lc(p,l.start); 263 264 // test every line in the list 265 for (u32 i=0; i<lines.size(); ++i) 266 { 267 core::line2df &l2 = lines[i]; 268 269 // the triangle isn't allowed to enclose any points 270 // triangles are clockwise, so if to the right of all 3 lines, it's enclosed 271 if (la.getPointOrientation(l2.start) > 0 && 272 lb.getPointOrientation(l2.start) > 0 && 273 lc.getPointOrientation(l2.start) > 0) 274 return true; 275 //if (la.getPointOrientation(l2.start) < 0 && 276 // lb.getPointOrientation(l2.start) < 0 && 277 // lc.getPointOrientation(l2.start) < 0) 278 // return true; 279 280 core::vector2df out; 281 //if (la.intersectWith(l2,out)) 282 // if (out != la.start && out != la.end && 283 // out != l2.start && out != l2.end) 284 // return true; 285 if (lb.intersectWith(l2,out)) 286 if (!out.equals(lb.start) && !out.equals(lb.end) && 287 !out.equals(l2.start) && !out.equals(l2.end)) 288 return true; 289 if (lc.intersectWith(l2,out)) 290 if (!out.equals(lc.start) && !out.equals(lc.end) && 291 !out.equals(l2.start) && !out.equals(l2.end)) 292 return true; 293 294 // my shit intersection code only works with lines in certain directions :( 295 if (l2.intersectWith(lb,out)) 296 if (!out.equals(lb.start) && !out.equals(lb.end) && 297 !out.equals(l2.start) && !out.equals(l2.end)) 298 return true; 299 if (l2.intersectWith(lc,out)) 300 if (!out.equals(lc.start) && !out.equals(lc.end) && 301 !out.equals(l2.start) && !out.equals(l2.end)) 302 return true; 303 304 305 if (lb.isPointOnLine(l2.start) && l2.start != lb.start && l2.start != lb.end) 306 return true; 307 if (lc.isPointOnLine(l2.start) && l2.start != lc.start && l2.start != lc.end) 308 return true; 309 310 } 311 return false; 312 } 313 }; 314 315 // an area of adjacent pixels 316 struct SPixelGroup 317 { SPixelGroupSPixelGroup318 SPixelGroup(IrrlichtDevice *device) : triangles(), pixelWidth(0), pixelHeight(0), 319 Device(device) {} 320 321 core::array<core::position2di> pixels; 322 core::array<SEdge> edges; 323 STriangleList triangles; 324 core::array<SLineList> ll; 325 core::array<bool> isMemberCache; 326 s32 pixelWidth; 327 s32 pixelHeight; 328 IrrlichtDevice *Device; 329 triangulateSPixelGroup330 void triangulate() 331 { 332 333 // find edges in this group 334 makeEdges(); 335 336 // triangulate the group 337 makeTriangles(); 338 339 } 340 drawTriangleSPixelGroup341 void drawTriangle( core::line2df line, core::vector2df point) 342 { 343 //const u32 endt = Device->getTimer()->getTime() + t; 344 f32 scale = 5; 345 346 347 //while(Device->getTimer()->getTime() < endt ) 348 //{ 349 Device->run(); 350 Device->getVideoDriver()->beginScene(true,true,video::SColor(0,0,0,0)); 351 for (u32 v=0;v<ll.size(); ++v) 352 for (u32 h=0;h<ll[v].lines.size(); ++h) 353 { 354 core::line2df ¤tline = ll[v].lines[h]; 355 core::position2di st = core::position2di((s32)(currentline.start.X*scale)+50, (s32)(currentline.start.Y*scale)+50); 356 core::position2di en = core::position2di((s32)(currentline.end.X*scale)+50, (s32)(currentline.end.Y*scale)+50); 357 358 Device->getVideoDriver()->draw2DLine(st,en, SColor(255,255,255,255)); 359 } 360 // draw this triangle 361 const core::position2di st((s32)(line.start.X*scale)+50, (s32)(line.start.Y*scale)+50); 362 const core::position2di en((s32)(line.end.X*scale)+50, (s32)(line.end.Y*scale)+50); 363 const core::position2di p((s32)(point.X*scale)+50, (s32)(point.Y*scale)+50); 364 Device->getVideoDriver()->draw2DLine(st,en, SColor(255,255,0,0)); 365 Device->getVideoDriver()->draw2DLine(en,p, SColor(255,0,255,0)); 366 Device->getVideoDriver()->draw2DLine(p,st, SColor(255,0,0,255)); 367 368 Device->getVideoDriver()->endScene(); 369 //} 370 } 371 makeTrianglesSPixelGroup372 void makeTriangles() 373 { 374 // make lines from edges, because they're easier to deal with 375 ll.clear(); 376 for (u32 i=0; i < edges.size(); ++i) 377 { 378 SLineList l; 379 l.addEdge(edges[i]); 380 ll.push_back(l); 381 } 382 // add an extra one for inside edges 383 SLineList innerlines; 384 ll.push_back(innerlines); 385 386 // loop through each edge and make triangles 387 for (u32 i=0; i<ll.size(); ++i) 388 { 389 // loop through each line in the edge 390 for (u32 cl=0; cl<ll[i].lines.size(); ++cl) 391 { 392 393 core::line2df ¤tLine = ll[i].lines[cl]; 394 f32 bestScore = -10.0f; 395 s32 bestEdge = -1; 396 s32 bestPoint = -1; 397 // find the best scoring point to join to this line 398 for (u32 k=0; k<ll.size(); ++k) 399 for (u32 j=0; j< ll[k].lines.size(); ++j) 400 { 401 f32 score = 0.0f; 402 core::vector2df point(ll[k].lines[j].start.X, 403 ll[k].lines[j].start.Y); 404 core::line2df line1(point,currentLine.start); 405 core::line2df line2(currentLine.end,point); 406 407 // can't be part of the current line 408 if (point == currentLine.start || point == currentLine.end) 409 continue; 410 411 // must be to the right hand side (triangles are wound clockwise) 412 // unless its part of the inside... 413 f32 side1 = currentLine.getPointOrientation(point); 414 f32 side2 = core::line2df(point,currentLine.start).getPointOrientation(currentLine.end); 415 f32 side3 = core::line2df(currentLine.end,point).getPointOrientation(currentLine.start); 416 if (i<ll.size()-1) 417 if (side1 <= 0 || side2 <= 0 || side3 <=0) 418 continue; 419 420 // can't already have this triangle 421 if (triangles.hasTriangle(currentLine.start,currentLine.end,point)) 422 continue; 423 424 // must not cross any other lines or enclose any points 425 bool itCrossed = false; 426 for (u32 v=0; v<ll.size(); ++v) 427 if (ll[v].crossesWith(currentLine, point)) 428 { 429 itCrossed = true; 430 break; 431 } 432 if (itCrossed) 433 continue; 434 435 436 // so, we like this triangle, but how much? 437 // is it better than all the others? 438 439 // we prefer points from other edges, unless its on the inside 440 if (k==i && i != ll.size()-1) 441 score = 1; 442 else 443 score = 2; 444 445 // we prefer evenly shaped triangles 446 447 // we prefer triangles with a large area 448 449 // do we like this one more than the others? 450 if (score>bestScore) 451 { 452 bestScore = score; 453 bestEdge = k; 454 bestPoint = j; 455 } 456 } 457 // hopefully we found one 458 if (bestEdge >= 0 && bestPoint >= 0 && bestScore >= 0.0f) 459 { 460 //assert(bestEdge >= 0 && bestPoint >= 0); 461 //assert(bestScore >= 0.0f); 462 463 core::vector2df point(ll[bestEdge].lines[bestPoint].start.X, ll[bestEdge].lines[bestPoint].start.Y); 464 465 // add it to the triangles list 466 triangles.add(currentLine.start, currentLine.end, point); 467 468 // add inner lines to the line buffer, but only if they arent in others 469 470 core::line2df la(point,currentLine.start); 471 core::line2df lb(currentLine.end,point); 472 473 bool found = false; 474 for (u32 lineno=0;lineno<ll.size()-1; ++lineno) 475 if (ll[lineno].hasLine(la)) 476 { found=true; break; } 477 if (!found) 478 ll[ll.size()-1].addLine(la); 479 480 for (u32 lineno=0;lineno<ll.size()-1; ++lineno) 481 if (ll[lineno].hasLine(lb)) 482 { found=true; break; } 483 if (!found) 484 ll[ll.size()-1].addLine(lb); 485 486 //drawTriangle(currentLine, point); 487 488 } 489 490 } 491 } 492 } 493 494 // finds the edges makeEdgesSPixelGroup495 void makeEdges() 496 { 497 498 // speed it up 499 refreshIsMemberCache(); 500 501 // clear the edges 502 edges.clear(); 503 504 // loop through each pixel 505 for (u32 i=0; i < pixels.size(); ++i) 506 { 507 core::position2di &p = pixels[i]; 508 s32 &x=p.X, &y=p.Y; 509 bool ul = isMember(p.X-1,p.Y-1); 510 bool u = isMember(p.X,p.Y-1); 511 bool ur = isMember(p.X+1,p.Y-1); 512 bool l = isMember(p.X-1,p.Y); 513 bool r = isMember(p.X+1,p.Y); 514 bool bl = isMember(p.X-1,p.Y+1); 515 bool b = isMember(p.X,p.Y+1); 516 bool br = isMember(p.X+1,p.Y+1); 517 518 // walls already added? 519 bool top=u, bottom=b, left=l, right=r; 520 521 if (!(ul | u | ur | l | r | bl | b | br)) 522 { 523 // lone square 524 SEdge a; 525 a.positions.push_back( core::position2di(x,y)); 526 a.positions.push_back( core::position2di(x+1,y)); 527 a.positions.push_back( core::position2di(x+1,y+1)); 528 a.positions.push_back( core::position2di(x,y+1)); 529 a.positions.push_back( core::position2di(x,y)); 530 edges.push_back(a); 531 top=bottom=left=right=true; 532 } 533 else 534 { 535 if (!(ul|u|l) && (b&r) ) 536 { 537 // upper outer diagonal "/" 538 addToEdges(x,y+1,x+1,y); 539 top=left=true; 540 } else if ( !(u|ur|r) && (b&l) ) 541 { 542 // upper outer diagonal "\" 543 addToEdges(x,y,x+1,y+1); 544 top=right=true; 545 } else if ( !(l|bl|b) && (r&u) ) 546 { 547 // lower outer diagonal "\" 548 addToEdges(x+1,y+1,x,y); 549 left=bottom=true; 550 } else if ( !(r|br|b) && (l&u) ) 551 { 552 // lower outer diagonal "/" 553 addToEdges(x+1,y,x,y+1); 554 right=bottom=true; 555 }/* else if (!(b) && (l&bl) ) 556 { 557 // upper inner diagonal "/" 558 addToEdges(x+1,y+1,x,y+2); 559 //bottom=true; 560 } else if ( !(b) && (r&br) ) 561 { 562 // upper inner diagonal "\" 563 addToEdges(x+1,y+2,x,y+1); 564 //bottom=true; 565 } else if ( !(r) && (b&br) ) 566 { 567 // lower inner diagonal "\" 568 addToEdges(x+1,y,x+2,y+1); 569 //right=true; 570 } else if ( !(l) && (b&bl) ) 571 { 572 // lower inner diagonal "/" 573 addToEdges(x-1,y+1,x,y); 574 //left=true; 575 }*/ 576 577 // add flat edges 578 if (!left /*&& !( (u&ul) || (b&bl)) */) addToEdges(x,y+1,x,y); 579 if (!top /*&& !( (l&ul) || (r&ur)) */) addToEdges(x,y,x+1,y); 580 if (!right /*&& !( (u&ur) || (b&br)) */) addToEdges(x+1,y,x+1,y+1); 581 if (!bottom /*&& !( (l&bl) || (r&br)) */) addToEdges(x+1,y+1,x,y+1); 582 } // lone square 583 } // for 584 585 // reduce the number of points in each edge 586 for (u32 i=0; i<edges.size(); ++i) 587 { 588 edges[i].reduce(1); 589 590 // all edges should have at least 3 points 591 assert(edges[i].positions.size() >= 3); 592 593 // all edges should be closed 594 assert(edges[i].positions[0] == edges[i].positions[edges[i].positions.size()-1] ); 595 } 596 } 597 598 // adds a line to the edges arrays addToEdgesSPixelGroup599 void addToEdges(s32 x1, s32 y1, s32 x2, s32 y2) 600 { 601 bool found=false; 602 // loop through each edge 603 for (u32 i=0; i<edges.size(); ++i) 604 { 605 // if this line starts at the end of an edge 606 if ( edges[i].positions[edges[i].positions.size()-1] == core::position2di(x1,y1)) 607 { 608 // add it to the end 609 edges[i].positions.push_back(core::position2di(x2,y2)); 610 found=true; 611 break; 612 } 613 // if the line ends at the start of the edge 614 if ( edges[i].positions[0]== core::position2di(x2,y2)) 615 { 616 // add it to the front 617 edges[i].positions.push_front(core::position2di(x1,y1)); 618 found=true; 619 break; 620 } 621 } 622 if (!found) 623 { 624 // we make a new edge 625 SEdge n; 626 n.positions.push_back(core::position2di(x1,y1)); 627 n.positions.push_back(core::position2di(x2,y2)); 628 edges.push_back(n); 629 } 630 631 joinEdges(); 632 } 633 joinEdgesSPixelGroup634 void joinEdges() 635 { 636 // touching edges are joined 637 638 for (u32 i=0; i < edges.size(); ++i) 639 for (u32 j=0; j < edges.size(); ++j) 640 { 641 if (i != j && edges[j].positions.size() && edges[i].positions.size()) 642 { 643 if (edges[j].positions[0] == edges[i].positions[edges[i].positions.size()-1]) 644 { 645 for (u32 k=0; k < edges[j].positions.size(); ++k) 646 edges[i].positions.push_back(edges[j].positions[k]); 647 edges[j].positions.clear(); 648 } 649 } 650 } 651 652 // remove empty edges 653 for (u32 i=0; i<edges.size(); ++i) 654 if (edges[i].positions.size() == 0) 655 edges.erase(i--); 656 } 657 658 // tells if this x,y position is a member of this group isMemberSPixelGroup659 bool isMember(s32 x, s32 y) 660 { 661 //for (u32 i=0; i<pixels.size(); ++i) 662 // if (pixels[i].X == x && pixels[i].Y == y) 663 // return true; 664 if (x>pixelWidth || y>pixelHeight || x<0 || y<0) 665 return false; 666 else 667 return isMemberCache[pixelWidth*y + x]; 668 } 669 refreshIsMemberCacheSPixelGroup670 void refreshIsMemberCache() 671 { 672 isMemberCache.clear(); 673 pixelWidth=0; pixelHeight=0; 674 for (u32 i=0; i<pixels.size(); ++i) 675 { 676 if (pixels[i].X>pixelWidth) pixelWidth=pixels[i].X; 677 if (pixels[i].Y>pixelHeight) pixelHeight=pixels[i].Y; 678 } 679 pixelWidth+=2; pixelHeight+=2; 680 isMemberCache.set_used(pixelWidth*pixelHeight+1); 681 for (u32 i=0; i<isMemberCache.size(); ++i) 682 isMemberCache[i] = false; 683 for (u32 i=0; i<pixels.size(); ++i) 684 isMemberCache[pixelWidth*pixels[i].Y + pixels[i].X] = true; 685 } 686 }; 687 688 drawEdges(IrrlichtDevice * device,u32 t,s32 scale)689 void drawEdges(IrrlichtDevice *device, u32 t, s32 scale) 690 { 691 const u32 stt = device->getTimer()->getTime(); 692 const u32 endt = stt + t; 693 694 while(device->getTimer()->getTime() < endt ) 695 { 696 const f32 phase = f32((device->getTimer()->getTime()-stt) % 500) / 500.0f; 697 698 device->run(); 699 device->getVideoDriver()->beginScene(true,true,video::SColor(0,0,0,0)); 700 for (u32 g=0;g<groups.size(); ++g) 701 for (u32 v=0;v<groups[g].edges.size(); ++v) 702 for (u32 p=1;p<groups[g].edges[v].positions.size(); ++p) 703 { 704 core::position2di st = core::position2di(groups[g].edges[v].positions[p-1].X*scale+50, groups[g].edges[v].positions[p-1].Y*scale+50) ; 705 core::position2di en = core::position2di(groups[g].edges[v].positions[p].X*scale+50, groups[g].edges[v].positions[p].Y*scale+50) ; 706 core::position2di ep = en-st; 707 ep = st + core::position2di((s32)(ep.X*phase), (s32)(ep.Y*phase)); 708 device->getVideoDriver()->draw2DLine(st,en); 709 device->getVideoDriver()->draw2DLine(st,ep,video::SColor(255,255,0,0) ); 710 } 711 device->getVideoDriver()->endScene(); 712 } 713 } 714 drawTriangles(IrrlichtDevice * device,u32 t,s32 scale)715 void drawTriangles(IrrlichtDevice *device, u32 t, s32 scale) 716 { 717 const u32 stt = device->getTimer()->getTime(); 718 const u32 endt = stt + t; 719 720 while(device->getTimer()->getTime() < endt ) 721 { 722 const f32 phase = f32((device->getTimer()->getTime()-stt) % 500) / 500.0f; 723 724 device->run(); 725 device->getVideoDriver()->beginScene(true,true,video::SColor(0,0,0,0)); 726 for (u32 g=0;g<groups.size(); ++g) 727 for (u32 v=0;v<groups[g].triangles.indexes.size()*phase; v+=3) 728 { 729 STriangleList &t = groups[g].triangles; 730 core::position2di st((s32)(t.positions[t.indexes[v+0]].X*scale)+50,(s32)(t.positions[t.indexes[v+0]].Y*scale)+50); 731 core::position2di en((s32)(t.positions[t.indexes[v+1]].X*scale)+50,(s32)(t.positions[t.indexes[v+1]].Y*scale)+50); 732 device->getVideoDriver()->draw2DLine(st,en, SColor(255,255,0,0)); 733 st = core::position2di((s32)(t.positions[t.indexes[v+1]].X*scale)+50,(s32)(t.positions[t.indexes[v+1]].Y*scale)+50); 734 en = core::position2di((s32)(t.positions[t.indexes[v+2]].X*scale)+50,(s32)(t.positions[t.indexes[v+2]].Y*scale)+50); 735 device->getVideoDriver()->draw2DLine(st,en, SColor(255,0,255,0)); 736 st = core::position2di((s32)(t.positions[t.indexes[v+2]].X*scale)+50,(s32)(t.positions[t.indexes[v+2]].Y*scale)+50); 737 en = core::position2di((s32)(t.positions[t.indexes[v+0]].X*scale)+50,(s32)(t.positions[t.indexes[v+0]].Y*scale)+50); 738 device->getVideoDriver()->draw2DLine(st,en, SColor(255,0,0,255)); 739 } 740 device->getVideoDriver()->endScene(); 741 } 742 } 743 drawTriLines(IrrlichtDevice * device,u32 t,s32 scale)744 void drawTriLines(IrrlichtDevice *device, u32 t, s32 scale) 745 { 746 const u32 endt = device->getTimer()->getTime() + t; 747 748 while(device->getTimer()->getTime() < endt ) 749 { 750 device->run(); 751 device->getVideoDriver()->beginScene(true,true,video::SColor(0,0,0,0)); 752 for (u32 g=0;g<groups.size(); ++g) 753 for (u32 v=0;v<groups[g].ll.size()-1; ++v) 754 for (u32 h=0;h<groups[g].ll[v].lines.size(); ++h) 755 { 756 core::line2df ¤tline = groups[g].ll[v].lines[h]; 757 const core::position2di st((s32)(currentline.start.X*scale)+50, (s32)(currentline.start.Y*scale)+50); 758 const core::position2di en((s32)(currentline.end.X*scale)+50, (s32)(currentline.end.Y*scale)+50); 759 device->getVideoDriver()->draw2DLine(st,en, SColor(255,255,0,0)); 760 } 761 762 device->getVideoDriver()->endScene(); 763 } 764 } drawTri3D(IrrlichtDevice * device,u32 t)765 void drawTri3D(IrrlichtDevice *device, u32 t) 766 { 767 for (u32 g=0;g<groups.size(); ++g) 768 { 769 STriangleList &t = groups[g].triangles; 770 core::array<S3DVertex> verts; 771 verts.clear(); 772 for(u32 v=0; v< t.positions.size(); ++v) 773 { 774 verts.push_back(S3DVertex( 775 -t.positions[v].X, -t.positions[v].Y, -100, 776 0,0,1,SColor(255,255,255,255),0,0)); 777 } 778 779 device->getVideoDriver()->drawIndexedTriangleList(verts.pointer(),verts.size(),t.indexes.pointer(), t.indexes.size()/3 ); 780 } 781 } 782 783 784 // process all pixels findGroups()785 void findGroups() 786 { 787 for (int y=0; y<height; ++y) 788 for (int x=0; x<width; ++x) 789 processPixel(x,y); 790 791 } 792 793 // remove groups with no pixels removeGroups()794 void removeGroups() 795 { 796 for (u32 i=0; i<groups.size(); ++i) 797 if (groups[i].pixels.size() == 0) 798 groups.erase(i--); 799 800 /*for (s32 y=0; y <height; ++y) 801 { 802 printf("\n"); 803 for (s32 x=0; x <width; ++x) 804 { 805 s32 i; 806 for (i=0; i<groups.size(); ++i) 807 { 808 bool k = groups[i].isMember(x,y); 809 if (k) 810 break; 811 } 812 printf("%d",i); 813 } 814 }*/ 815 816 817 } 818 819 // adds a pixel to its area, merging touching areas processPixel(s32 x,s32 y)820 void processPixel(s32 x, s32 y) 821 { 822 // solid? 823 if (getPixel(x,y)) 824 { 825 s32 g=0, grp=0; 826 827 bool found=false; 828 if (x>0) // look one behind 829 { 830 grp = getRef(x-1,y); 831 if (grp) found=true; 832 } 833 if (y>0) // look above 834 { 835 if (x>0) // top left 836 { 837 g = getRef(x-1,y-1); 838 839 if (g) 840 { 841 if (found) 842 { 843 mergeGroups(grp, g); 844 } 845 else 846 { 847 grp = g; 848 found = true; 849 } 850 } 851 } 852 853 if (x<width-1) // top right 854 { 855 g = getRef(x+1,y-1); 856 857 if (g) 858 { 859 if (found) 860 { 861 mergeGroups(grp, g); 862 } 863 else 864 { 865 grp = g; 866 found = true; 867 } 868 } 869 } 870 871 // top 872 873 g = getRef(x,y-1); 874 875 if (g) 876 { 877 if (found) 878 { 879 mergeGroups(grp, g); 880 } 881 else 882 { 883 grp = g; 884 found = true; 885 } 886 } 887 888 } 889 890 // didn't find a group for this pixel, so we add one 891 if (!found) 892 { 893 SPixelGroup p(Device); 894 p.pixels.push_back(core::position2di(x,y)); 895 groups.push_back(p); 896 groupRefs.push_back(groups.size()); 897 grp=groups.size(); 898 } 899 else 900 { 901 groups[groupRefs[grp-1]-1].pixels.push_back(core::position2di(x,y)); 902 } 903 setRef(x,y,groupRefs[grp-1]); 904 } 905 } 906 getPixel(s32 x,s32 y)907 bool& getPixel(s32 x, s32 y) { return mem[y*width +x]; } getRef(s32 x,s32 y)908 s32& getRef(s32 x, s32 y) { return refbuffer[y*width +x]; } setRef(s32 x,s32 y,s32 g)909 void setRef(s32 x, s32 y, s32 g) { refbuffer[y*width +x] = g; } 910 mergeGroups(s32 g1,s32 g2)911 void mergeGroups(s32 g1, s32 g2) 912 { 913 if (g1==g2) 914 return; 915 // joins two groups together 916 for (u32 i=0; i<groups[g2-1].pixels.size(); ++i) 917 groups[g1-1].pixels.push_back(groups[g2-1].pixels[i]); 918 groups[g2-1].pixels.clear(); 919 groupRefs[g2-1] = g1; 920 } 921 922 s32 width, height; 923 core::array<SPixelGroup> groups; 924 core::array<s32> groupRefs; 925 core::array<s32> refbuffer; 926 bool *mem; 927 IrrlichtDevice *Device; 928 }; 929 930 // creates a simple vector font from a bitmap from the font tool 931 class CVectorFontTool 932 { 933 public: CVectorFontTool(CFontTool * fonttool)934 CVectorFontTool(CFontTool *fonttool) : 935 triangulator(0), FontTool(fonttool), 936 letterHeight(0), letterWidth(0), triangles() 937 { 938 core::map<wchar_t, u32>::Iterator it = FontTool->CharMap.getIterator(); 939 940 while(!it.atEnd()) 941 { 942 CFontTool::SFontArea &fa = FontTool->Areas[(*it).getValue()]; 943 944 if (fa.rectangle.getWidth() > letterWidth) 945 letterWidth = fa.rectangle.getWidth(); 946 if (fa.rectangle.getHeight() > letterHeight) 947 letterHeight = fa.rectangle.getHeight(); 948 949 it++; 950 } 951 952 // number of verts is one more than number of pixels because it's a grid of squares 953 letterWidth++; 954 letterHeight++; 955 956 // create image memory 957 imagedata.set_used(letterWidth*letterHeight); 958 959 // create vertex list, set position etc 960 verts.set_used(letterWidth*letterHeight); 961 for (s32 y=0; y<letterHeight; ++y) 962 { 963 for (s32 x=0; x<letterWidth; ++x) 964 { 965 S3DVertex &v = getVert(x,y); 966 v.Pos = core::vector3df((f32)x,(f32)y,0.0f); 967 v.TCoords.X = (f32)letterWidth / (f32)x; 968 v.TCoords.Y = (f32)letterHeight / (f32)y; 969 v.Normal = core::vector3df(0,0,-1); 970 v.Color = SColor(255,255,255,255); 971 } 972 } 973 // clear index list 974 inds.clear(); 975 976 // create each char in the font... 977 it = FontTool->CharMap.getIterator(); 978 while(!it.atEnd()) 979 { 980 addChar((*it).getKey()); 981 it++; 982 } 983 } 984 ~CVectorFontTool()985 ~CVectorFontTool() 986 { 987 if (triangulator) 988 delete triangulator; 989 } 990 addChar(wchar_t thischar)991 void addChar(wchar_t thischar) 992 { 993 const s32 area = FontTool->CharMap[thischar]; 994 const CFontTool::SFontArea &fa = FontTool->Areas[area]; 995 996 const s32 img = fa.sourceimage; 997 const core::rect<s32>& r = fa.rectangle; 998 999 // init image memory 1000 IImage *image = FontTool->currentImages[img]; 1001 for (u32 i=0; i < imagedata.size(); ++i) 1002 imagedata[i] = false; 1003 for (s32 y=r.UpperLeftCorner.Y; y < r.LowerRightCorner.Y; ++y) 1004 { 1005 for (s32 x=r.UpperLeftCorner.X; x < r.LowerRightCorner.X ; ++x) 1006 if (image->getPixel(x,y).getBlue() > 0) 1007 { 1008 imagedata[letterWidth*(y-r.UpperLeftCorner.Y) +(x-r.UpperLeftCorner.X)] = true; 1009 } 1010 } 1011 1012 // get shape areas 1013 triangulator = new CGroupFinder(imagedata.pointer(), letterWidth, letterHeight, FontTool->Device ); 1014 1015 wprintf(L"Created character '%c' in texture %d\n", thischar, img ); 1016 1017 //floodfill->drawEdges(FontTool->Device, 500, 3); 1018 //floodfill->drawTriangles(FontTool->Device, 500,30); 1019 //floodfill->drawTriLines(FontTool->Device, 200,3); 1020 1021 /* 1022 if (area==32 && map == 0) 1023 { 1024 scene::ISceneManager *smgr = FontTool->Device->getSceneManager(); 1025 smgr->addCameraSceneNodeFPS(); 1026 while(FontTool->Device->run()) 1027 { 1028 //floodfill->drawEdges(FontTool->Device, 100, 30); 1029 FontTool->Device->getVideoDriver()->beginScene(true, true, video::SColor(0,200,200,200)); 1030 smgr->drawAll(); 1031 floodfill->drawTri3D(FontTool->Device, 100); 1032 FontTool->Device->getVideoDriver()->endScene(); 1033 } 1034 }*/ 1035 1036 u32 lastind = triangles.indexes.size(); 1037 1038 // loop through each shape and add it to the current character... 1039 for (u32 i=0; i < triangulator->groups.size(); ++i) 1040 triangles += triangulator->groups[i].triangles; 1041 1042 // add character details 1043 charstarts.push_back(lastind); 1044 charlengths.push_back(triangles.indexes.size() - lastind); 1045 chars.push_back(thischar); 1046 } 1047 saveVectorFont(const c8 * filename,const c8 * formatname)1048 bool saveVectorFont(const c8 *filename, const c8 *formatname) 1049 { 1050 IrrlichtDevice *Device = FontTool->Device; 1051 1052 if (triangles.indexes.size() == 0) 1053 { 1054 Device->getLogger()->log("No vector data to write, aborting."); 1055 return false; 1056 } 1057 1058 core::stringc fn = filename; 1059 1060 if (core::stringc(formatname) == core::stringc("xml")) 1061 { 1062 fn += ".xml"; 1063 io::IXMLWriter *writer = FontTool->Device->getFileSystem()->createXMLWriter(fn.c_str()); 1064 1065 // header and line breaks 1066 writer->writeXMLHeader(); 1067 writer->writeLineBreak(); 1068 1069 // write info header 1070 writer->writeElement(L"font", false, L"type", L"vector"); 1071 writer->writeLineBreak(); 1072 writer->writeLineBreak(); 1073 1074 // write each letter 1075 1076 for (u32 n=0; n<chars.size(); ++n) 1077 { 1078 u32 i = FontTool->CharMap[chars[n]]; 1079 CFontTool::SFontArea &fa = FontTool->Areas[i]; 1080 wchar_t c[2]; 1081 c[0] = chars[n]; 1082 c[1] = L'\0'; 1083 core::stringw area, under, over; 1084 area = core::stringw(fa.rectangle.LowerRightCorner.X- 1085 fa.rectangle.UpperLeftCorner.X); 1086 area += L", "; 1087 area += fa.rectangle.LowerRightCorner.Y- 1088 fa.rectangle.UpperLeftCorner.Y; 1089 1090 1091 core::array<core::stringw> names; 1092 core::array<core::stringw> values; 1093 names.clear(); 1094 values.clear(); 1095 // char 1096 names.push_back(core::stringw(L"c")); 1097 values.push_back(core::stringw(c)); 1098 1099 // width+height 1100 names.push_back(core::stringw(L"wh")); 1101 values.push_back(area); 1102 1103 // start 1104 names.push_back(core::stringw(L"st")); 1105 values.push_back(core::stringw(charstarts[n])); 1106 // length 1107 names.push_back(core::stringw(L"len")); 1108 values.push_back(core::stringw(charlengths[n])); 1109 1110 if (fa.underhang != 0) 1111 { 1112 under = core::stringw(fa.underhang); 1113 names.push_back(core::stringw(L"u")); 1114 values.push_back(under); 1115 } 1116 if (fa.overhang != 0) 1117 { 1118 over = core::stringw(fa.overhang); 1119 names.push_back(core::stringw(L"o")); 1120 values.push_back(over); 1121 } 1122 writer->writeElement(L"c", true, names, values); 1123 1124 writer->writeLineBreak(); 1125 } 1126 1127 // write vertex data 1128 core::stringw data, count; 1129 data = L""; 1130 count = core::stringw(triangles.positions.size()); 1131 for (u32 i=0; i<triangles.positions.size(); ++i) 1132 { 1133 if (i!=0) 1134 data += L", "; 1135 data += (s32)triangles.positions[i].X; 1136 data += L","; 1137 data += (s32)triangles.positions[i].Y; 1138 } 1139 writer->writeElement(L"Vertices", true, L"count", count.c_str(), L"data", data.c_str()); 1140 writer->writeLineBreak(); 1141 1142 // write index list 1143 data = L""; 1144 count = core::stringw(triangles.indexes.size()); 1145 for (u32 i=0; i<triangles.indexes.size(); i+=3) 1146 { 1147 if (i!=0) 1148 data += L", "; 1149 data += triangles.indexes[i+0]; 1150 data += L","; 1151 data += triangles.indexes[i+1], 1152 data += L","; 1153 data += triangles.indexes[i+2]; 1154 } 1155 1156 writer->writeElement(L"Indices", true, L"count", count.c_str(), L"data", data.c_str()); 1157 writer->writeLineBreak(); 1158 1159 writer->writeClosingTag(L"font"); 1160 1161 writer->drop(); 1162 1163 Device->getLogger()->log("Font saved."); 1164 return true; 1165 1166 } 1167 else if (core::stringc(formatname) == core::stringc("bin")) 1168 { 1169 FontTool->Device->getLogger()->log("binary fonts not supported yet, sorry"); 1170 return false; 1171 } 1172 else 1173 { 1174 FontTool->Device->getLogger()->log("unsupported file format, unable to save vector font"); 1175 return false; 1176 } 1177 } 1178 getVert(s32 x,s32 y)1179 S3DVertex& getVert(s32 x, s32 y) { return verts[letterWidth*y +x]; } 1180 1181 core::array<S3DVertex> verts; 1182 core::array<u16> inds; 1183 core::array<bool> imagedata; 1184 1185 core::array<s32> charstarts; // start position of each char 1186 core::array<s32> charlengths; // index count 1187 core::array<wchar_t> chars; // letters 1188 1189 CGroupFinder* triangulator; 1190 CFontTool* FontTool; 1191 1192 s32 letterHeight; 1193 s32 letterWidth; 1194 1195 STriangleList triangles; 1196 }; 1197 1198 #endif // __VECTOR_FONT_TOOL_INCLUDED__ 1199 1200