bugThe FreeType Project - Bugs: bug #49706, bordering algorithm in ftstroke.c

 
 

bug #49706: bordering algorithm in ftstroke.c

Submitted by:  Henry <ftuser>
Submitted on:  Sat 26 Nov 2016 03:15:06 PM UTC  
 
Severity: 3 - NormalItem Group: Incorrect behaviour
Status: InvalidPrivacy: Public
Assigned to: Alexei Podtelezhnikov <podtelez>Open/Closed: Closed
Planned Release: None

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

(Jump to the original submission Jump to the original submission)

Mon 12 Dec 2016 03:25:30 AM UTC, comment #23:

Dear Henry,

I am very sympathetic to the cause. I certainly make sense to use stroke composite glyphs for CJK. I agree that it may be a path to more compact fonts. Let's be realistic though: there is a long path to implement this. I strongly encourage you to start thinking about extending OpenType specifications instead of hacking SVG. Think about it monumentally in terms of new SFNT font type. This is a big project. Draft specifications, get people involved, code FreeType to support it, then create a font.

Also think why nobody else tried this before? Why we do not see stroke CJK fonts already? Still, who knows, maybe, you will be successful.

Alexei Podtelezhnikov <podtelez>
Project MemberIn charge of this item.
Sun 11 Dec 2016 10:41:25 AM UTC, comment #22:

Respected Mr. Werner Lemberg, fortunately, the code can work and almost reach the target, but unfortunately, there's an unnecessary step to produce the glyph, before the last step to render outline into bitmap, there's an extra step to convert the strokes to closed-curves to satisfy the TrueType format, it should can be directly rasterized from the stroke data, more efficient and performance can be big improved, attached the output, please take a look, Sir.

(file #39197)

Henry <ftuser>
Sun 11 Dec 2016 10:14:17 AM UTC, comment #21:

What you describe (i.e., composite glyphs that need scaling and translation for its element) is called `tricky' within FreeType; a typical example is the very old `mingli.ttf' font (not `mingli.ttc' or `mingliu.ttc', BTW). If you want to get a consistent line thickness, you have to first construct the composite glyph, then stroking the outline.

Given that modern rasterizers allow overlapping contours (mainly because of the introduction of variation fonts in OpenType 1.8), I don't see a problem here.

Anyways, I now wait for your code :-)

Werner LEMBERG <wl>
Project Administrator
Sun 11 Dec 2016 09:44:01 AM UTC, comment #20:

Sir, thank you for your quickly response. Composite different glyph with TrueType outline to form one glyph require to scale the outline and translate it to a suitable position, but the issue is, the scaled outline can't keep the line-width immutable, so all parts of the generated glyph cannot keep coordinate, it will look strange. The attached single-line stroke based on svg file is the source to rasterize, the target is, adapt current FreeType code base to successfully rasterized it with "different line-width" and the output is acceptable. The svg file have three strokes that can be used to make the character ぁ (unicode 0x3041).

(file #39196)

Henry <ftuser>
Sun 11 Dec 2016 07:18:27 AM UTC, comment #19:

Henry, we have no idea how to help you. We won't implement a generalized stroker, since we don't need it (and the stroked format of Winfonts is obsolete since many, many years, so there is no priority at all to add support for it). In other words, it is up to you to proceed.

If you want to contribute code, great! We'll then have a look. But again: we need code to look at that you contribute.

Werner LEMBERG <wl>
Project Administrator
Sun 11 Dec 2016 06:21:07 AM UTC, comment #18:

Respected Sir, really needs your help. Filling contour shapes that construct with unclosed curves is not so difficult, maybe bresenham's algorithm can do such work, so FreeType support stroke-font (or should be accurately called svg-font, glyph built with only single-line strokes) should not so difficult, a C implement on this page: http://members.chello.at/~easyfilter/bresenham.html.

Henry <ftuser>
Thu 08 Dec 2016 03:01:54 PM UTC, comment #17:

Exactly. FreeType supports font formats, rather than ad hoc SVG rasterization hacks. Henry should first choose (preferably) an existing stroke font format rather than reinventing the wheel. Then we can work on FreeType support for that format. I want to save Henry's time. Font is more than just glyphs, there is character maps and the rest.

Alexei Podtelezhnikov <podtelez>
Project MemberIn charge of this item.
Thu 08 Dec 2016 11:02:56 AM UTC, comment #16:

I'm glad to contribute stable code, but sorry, Sir, current code is just for test, the directly rasterize from dynamic generated outline can work, but not mature, product-ready, the algorithm to generate outline with strokes is not so perfect as mentioned in the previous comment, So, the key point is the algorithm, an algorithm that can generate good closed-bezier-path by variable line-width.

Henry <ftuser>
Thu 08 Dec 2016 07:26:50 AM UTC, comment #15:

Henry, please reopen this issue as soon as you have some stable source code that you want to contribute! Integrating it into FreeType might be useful to render stroked WinFNT fonts (which we don't support yet) and maybe other stuff also.

Werner LEMBERG <wl>
Project Administrator
Thu 08 Dec 2016 06:10:10 AM UTC, comment #14:

Respected Mr. Werner Lemberg and Mr. Alexei Podtelezhnikov,
Yes, the existing TrueType font is not a better option, especially CJK font defined with TrueType format, the font file is "too big", from 15MB to 60MB, the size is too large for deep-embedded system, but use stroke-font to generation 60,000 CJK character (Kanji) "on-the-fly" only needs 400KB~500KB! Extreme amazed small size! That's the reason! FreeType can support stroke-font is not only an expectation for me, but also many people, when they need FreeType strong support CAD, CNC etc. Please take care such an requirement, Sir, Please. Today, I use FreeType with OpenGL to display "on-the-fly" generated glyph, the result is not so ideal, the output attached, please take a look, Sir.

(file #39174)

Henry <ftuser>
Wed 07 Dec 2016 09:23:06 PM UTC, comment #13:

Alright. FreeType is a font parser and rasterizer, it was never meant to be a general shape rasterizer although this might be achievable. It sounds like Henry wants to use SVG to define a new font format. This is a long shot, i am not sure why existing TrueType is not an a better option.

I am going to close this bug as invalid because, again, SVG is not a font format supported by FreeType.

Alexei Podtelezhnikov <podtelez>
Project MemberIn charge of this item.
Wed 07 Dec 2016 02:53:26 PM UTC, comment #12:

The correspond SVG file ( 5bf8.svg ) of the #9 rasterized bitmap, you can see some fault there, and the algorithm is not perfect.

(file #39172)

Henry <ftuser>
Wed 07 Dec 2016 04:33:53 AM UTC, comment #11:

No, Sir, not for Hershey font, it's an experience of stroke-font (or vector graph) rasterizing, especially for embedded device, that require small storage, small memory and high performance, such feature seems still missed or only weak supporting in FreeType until today, it really needs your help, Sir. To get the purpose of the project try to implement, please refer the attached another svg file (51a0.svg), if the rasterized bitmap keeping "thin", only single strokes (maybe single pixel strokes ) in the glyph, and display same as the original SVG file, then the work well done, and great thing become more greater, FreeType can support stroke-font now! Even CJK character!

(file #39169)

Henry <ftuser>
Tue 06 Dec 2016 03:46:44 PM UTC, comment #10:

Is this about support for stroked fonts like Hershey? This is missing, and Freetype stroker might be useful.

Alexei Podtelezhnikov <podtelez>
Project MemberIn charge of this item.
Tue 06 Dec 2016 02:16:38 AM UTC, comment #9:

Dear Sir, The implement is not so perfect, some strokes is still "too fat", although the result is almost acceptable, but an enhancement can be added to the rasterizer of FreeType to produce more thin strokes (only single pixel strokes, and can by dynamically adjust width of strokes), it needs your strong help, Sir. When the feature is stable, it can be merged into the main trunk of FreeType, but not now. Please refer the attached screenshot, it's the rasterized bitmap for the previous svg file (小.svg). The outline generation algorithm referred the GPC library and the polygon-offset module of NodeJS. The urls:
http://www.cs.man.ac.uk/~toby/alan/software/
https://github.com/w8r/polygon-offset

In addition, continue the way, the bordering algorithm in ftstroke.c can support arbitrary shapes might be quite useful too.

(file #39156)

Henry <ftuser>
Mon 05 Dec 2016 06:37:26 AM UTC, comment #8:

URL please, in case your project is publicly available!

Having stroking support in FreeType might be quite useful.

Werner LEMBERG <wl>
Project Administrator
Sat 03 Dec 2016 02:42:45 PM UTC, comment #7:

Respected Mr. Alexei Podtelezhnikov, the issue have been resolved today, now FreeType can directly rasterize svg strokes and output extreme thin character. Using the bordering algorithm in ftstroke.c to implement the function is a wrong direction, sorry for bothering you.

Henry <ftuser>
Fri 02 Dec 2016 10:48:33 AM UTC, comment #6:

Respected Sir, the reason to avoid FT_Glyph_Stroke(FT_Glyph *pglyph, ...) is that the parameter FT_Glyph in the function don't directly filled data from font file as normal, but manually filled from svg files, i.e, the call to TT_Load_Simple_Glyph() have been hooked to fetch data from an extra svg file, and the svg file only have single-line strokes (unclosed-bezier-path). The hook function can work well for closed-bezier-path, but can't work for unclosed-bezier-path, including, the path from stroke font, please refer the attached test svg file. In fact, the purpose of this project is try to add stroke-font supporting to FreeType, but it seams not so easy, making outline of strokes is bezier clipping and offsetting algorithm related task, FreeType's bordering algorithm should have implemented it well, but Sir, it needs your help to make the function really working. The following links mentioned something about this topic, please take a look:
http://stackoverflow.com/questions/1109536/an-algorithm-for-inflating-deflating-offsetting-buffering-polygons
http://www.angusj.com/delphi/clipper.php
https://sourceforge.net/projects/vpr

(file #39130)

Henry <ftuser>
Wed 30 Nov 2016 03:15:03 PM UTC, comment #5:

Thank you for your analysis. Not that there is anything wrong in using the low level stroker functions, but I never personally used those. What is your reason to avoid FT_Glyph_Stroke?

Could you please post the images with wrong results? I am not following how to use your test page. Truth be told, our stroker documentation leaves much to be desired.

Alexei Podtelezhnikov <podtelez>
Project MemberIn charge of this item.
Wed 30 Nov 2016 06:32:25 AM UTC, comment #4:

After analysis, it's a memory management related bug, maybe the variable or buffer isn't be correctly initialized, e.g, the num_points used in FT_Outline_New(), if set it to FT_UInt num_points = 100; run the test, sometime return correct data, sometime return wrong data ( very big x, or y), set num_points=2; to a small value, ,FT_Stroker_Export() will always return wrong data. Due to lacking of deep knowledge of FreeType, I still don't know what the point to fix it.

Henry <ftuser>
Mon 28 Nov 2016 09:55:28 AM UTC, comment #3:

the test files attached.

Henry <ftuser>
Mon 28 Nov 2016 09:18:22 AM UTC, comment #2:

Respected Mr. Alexei Podtelezhnikov,
I made a simple test page online, so the output outline data can be view in browser, just put the data in javascript function init(), then you can see the bordered shape. Please refer this link:
http://jsbin.com/vajejanuro
Thank you.

Henry <ftuser>
Sat 26 Nov 2016 06:55:40 PM UTC, comment #1:

Alexei, please have a look.

Werner LEMBERG <wl>
Project Administrator
Sat 26 Nov 2016 03:15:06 PM UTC, original submission:

The bordering algorithm in ftstroke.c can't work as expected with simple strokes. Here is the simple procedure to test the bordering algorithm,
1, define a global variable in freetype.h
extern FT_Library glibrary;
2, define a function named outlineStroker() to make border of strokes.
3, load a truetype font as normal, then hook the function outlineStroker() into TT_Load_Simple_Glyph() in ttgload.c
FT_Outline* outline = &gloader->current.outline;
outlineStroker(outline);
4, FT_Stroker_Export(stroker, outline) should correctly output the bordered outline.

-------------------outlineStroker() added in ttgload.c-------------------------------
static int
outlineStroker(TT_Loader loader,
FT_Outline *outline)
{
FT_Error error = 0;
// Initialize FreeType.
// FT_Library library;
// FT_Init_FreeType(&library);

// FT_Face face;
// Set up a stroker.
FT_Stroker stroker;
FT_Stroker_New(glibrary, &stroker);
int outlineWidth = 1;
FT_Stroker_Set(stroker,
(int)(outlineWidth * 64),
FT_STROKER_LINECAP_ROUND,
FT_STROKER_LINEJOIN_ROUND,
0);

//int ch = 0x51a0;
//face = loader->face;
// if (FT_Get_Glyph(face->glyph, &glyph) == 0)
//error = FT_Load_Char(face, ch, FT_LOAD_RENDER|FT_LOAD_TARGET_MONO);
//error = FT_Load_Char(face, ch, FT_LOAD_NO_SCALE | FT_LOAD_NO_BITMAP);
//if (error) goto Exit;
//FT_Glyph glyph;
//FT_Glyph_StrokeBorder(face->glyph, stroker, 0, 0);
//FT_Stroker_Rewind( stroker );
FT_Vector v_start;
v_start.x = 100; v_start.y = 100;
FT_Bool opened = 1;
error = FT_Stroker_BeginSubPath( stroker, &v_start, opened);
if ( error ) goto Exit;

FT_Vector vec;
vec.x = 200; vec.y = 100;
error = FT_Stroker_LineTo( stroker, &vec );
if ( error ) goto Exit;

//error = FT_Stroker_ConicTo( stroker, &v_control, &vec );
//if ( error ) goto Exit;
//error = FT_Stroker_CubicTo( stroker, &vec1, &vec2, &vec );
//if ( error ) goto Exit;

//FT_Outline outline;
FT_UInt num_points = 100;//2*16;
FT_UInt num_contours = 1;

error = FT_Stroker_EndSubPath(stroker);
if ( error ) goto Exit;
error = FT_Outline_New(glibrary,
num_points,
(FT_Int)num_contours,
outline);
if ( error ) goto Exit;

FT_Stroker_GetCounts(stroker,&num_points, &num_contours );
FT_Stroker_Export(stroker, outline);
outline_dump(loader, outline);

// Clean up afterwards.
FT_Stroker_Done(stroker);

Exit:
return error;

}

-----------------outline_dump() added in ttgload.c-------------------------------
static void
outline_dump(TT_Loader loader,
FT_Outline* outline)
{
int i;
printf("-----------outline dump------------\n");
printf("n_points:%d n_contours:%d->", outline->n_points, outline->n_contours);
for (i = 0; i< outline->n_contours; i++){
printf("%d,", outline->contours[i]);
}
printf("\n---points---\n");
for (i = 0; i< outline->n_points; i++){
FT_Vector* v = &outline->points[i];
printf("{x:%ld,y:%ld},", v->x, v->y);
}
printf("\n----flag---\n");
FT_Byte flag = (FT_Byte)outline->tags;
for (i = 0; i< outline->n_points; i++, flag++){
printf("%d,", *flag);
}
printf("\n");

/* set phantom points */
if (loader){
//pp1=(0,0) pp2=(glph width, 0), pp3 =(0, 850) pp4=(0, -150);
printf("------------------------------\n");
printf("phantom points:(%ld %ld) (%ld %ld) (%ld %ld) (%ld %ld)\n",
loader->pp1.x, loader->pp1.y, loader->pp2.x, loader->pp2.y,
loader->pp3.x, loader->pp3.y, loader->pp4.x, loader->pp4.y);

}
printf("------------------------------\n");
}

-----main.c-------------------------------------------------------------------------
#include <stdio.h>
#include <assert.h>
#include "ft2build.h"
#include FT_FREETYPE_H
#include FT_STROKER_H

FT_Library glibrary;
int main(int argc, char ** argv)
{
int error;
FT_Face face;
FT_Library library;

error = FT_Init_FreeType(&library);
if (error) {
fprintf(stderr, "ft init err %d\n", error);
exit(1);
}

glibrary = library;
error = FT_New_Face(library,font,0, &face);
if (error) {
fprintf(stderr, "new face err %d\n", error);
exit(1);
}
FT_UInt fontSize = 64;
error = FT_Set_Pixel_Sizes(face, 0, fontSize);
if (error) {
fprintf(stderr, "set pixel sizes err %d\n", error);
exit(1);
}

int iChar = 0x4ef0;
error = FT_Load_Char(face, iChar, FT_LOAD_RENDER|FT_LOAD_TARGET_MONO);
if (error) {
fprintf(stderr, "load char err %d\n", error);
exit(1);
}
return 0;
}

------------------------------end of code------------------------------------------

Henry <ftuser>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach File(s):
   
   
Comment:
   

Attached Files
file #39197:  opengl2.png added by ftuser (263KiB - image/png)
file #39196:  3041.svg added by ftuser (2KiB - image/svg+xml)
file #39174:  opengl.png added by ftuser (121KiB - image/png)
file #39172:  5bf8.svg added by ftuser (2KiB - image/svg+xml)
file #39169:  51a0.svg added by ftuser (2KiB - image/svg+xml)
file #39156:  ScreenShot.png added by ftuser (276KiB - image/png)
file #39130:  小.svg added by ftuser (707B - image/svg+xml)
file #39090:  shrink.js added by ftuser (15KiB - application/x-javascript)
file #39091:  shrink.html added by ftuser (2KiB - text/html)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by podtelez (Posted a comment)
  • -unavailable- added by wl (Posted a comment)
  • -unavailable- added by ftuser (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 13 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Sun 11 Dec 2016 10:41:25 AM UTCftuserAttached File-=>Added opengl2.png, #39197
    Sun 11 Dec 2016 09:44:01 AM UTCftuserAttached File-=>Added 3041.svg, #39196
    Thu 08 Dec 2016 06:10:10 AM UTCftuserAttached File-=>Added opengl.png, #39174
    Wed 07 Dec 2016 09:23:06 PM UTCpodtelezStatusNeed Info=>Invalid
      Open/ClosedOpen=>Closed
    Wed 07 Dec 2016 02:53:26 PM UTCftuserAttached File-=>Added 5bf8.svg, #39172
    Wed 07 Dec 2016 04:33:53 AM UTCftuserAttached File-=>Added 51a0.svg, #39169
    Tue 06 Dec 2016 02:16:38 AM UTCftuserAttached File-=>Added ScreenShot.png, #39156
    Mon 05 Dec 2016 06:37:26 AM UTCwlStatusNone=>Need Info
    Fri 02 Dec 2016 10:48:33 AM UTCftuserAttached File-=>Added 小.svg, #39130
    Mon 28 Nov 2016 09:53:12 AM UTCftuserAttached File-=>Added shrink.js, #39090
      Attached File-=>Added shrink.html, #39091
    Sat 26 Nov 2016 06:55:40 PM UTCwlAssigned toNone=>podtelez

    Back to the top


    Powered by Savane 3.1-cleanup1