bugThe FreeType Project - Bugs: bug #37572, ISECT truetype instruction fails...

 
 

bug #37572: ISECT truetype instruction fails to compute valid intersection

Submitted by:  None
Submitted on:  Mon 15 Oct 2012 06:24:37 AM UTC  
 
Severity: 3 - NormalItem Group: Incorrect behaviour
Status: FixedPrivacy: Public
Assigned to: Werner LEMBERG <wl>Open/Closed: Closed
Planned Release: 2.4.11

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)

Sat 20 Oct 2012 05:53:15 AM UTC, comment #6:

The patch looks fine, thanks! However, please add a comment how the formula gets derived. Something like

Let

a = vector(a0, a1)
b = vector(b0, b1) .

Then

dot_product(normal_vector(a), b)
= discriminant
= |a| * |b| * sin(alpha)

dot_product(a, b)
= dotproduct
= |a| * |b| * cos(alpha)

which eventually yields

tan(alpha) = discriminant / dotproduct .

Werner LEMBERG <wl>
Project AdministratorIn charge of this item.
Sat 20 Oct 2012 02:23:13 AM UTC, comment #5:

Do you mind checking the attached patch on top of git tree? I will push it if everything is fine.

(file #26799)

Alexei Podtelezhnikov <podtelez>
Project Member
Fri 19 Oct 2012 08:04:32 AM UTC, comment #4:

Thanks. I rebuilt Freetype and Fontforge from Git sources this evening and confirmed that this does indeed fix the issue in my font.

It's odd that ISECT is so rarely used. I found it convenient for updating stroke intersections and bevel joins. In this case, it was in positioning points in the neck of the numeral 8 at low ppems where I discovered the bug. It may just be that few of us are crazy enough to try to handcraft truetype code.

- aek

Anonymous
Thu 18 Oct 2012 08:57:49 PM UTC, comment #3:

Please do so! I'm aware of the costly calculations. However, ISECT is rarely used: While debugging fonts I've actually never encountered it in the last few years. So I was happy to implement a working solution, even at the cost of some overhead.

Your solution is far more elegant, of course. I know that such mathematical enhancements are you special area of expertise :-)

Werner LEMBERG <wl>
Project AdministratorIn charge of this item.
Thu 18 Oct 2012 05:57:27 PM UTC, comment #2:

This is a cool bug and I agree with the fix idea. However, all costly square roots in length calculations and divisions could be avoided if you threshold tangent instead of sine, which is totally equivalent for tese purposes.

abs(tangent) > epsilon

is the same as

abs(sine) > epsilon * abs(cosine)

is the same as

abs(discriminant) > epsilon * abs(dot_product)

VoilĂ ! I'll prepare a patch if you don't mind.

Alexei Podtelezhnikov <podtelez>
Project Member
Wed 17 Oct 2012 09:35:51 AM UTC, comment #1:

Fixed in git. Thanks for the report, and please test.

Werner LEMBERG <wl>
Project AdministratorIn charge of this item.
Mon 15 Oct 2012 06:24:37 AM UTC, original submission:

Using the ISECT truetype instruction on two lines with the following 26.6 coordinates:

a0 = 160,192 a1 = 192,160
b0 = 160,256 b1 = 192,288

calculates an intersection at 176,224 when the expected intersection point is at 128,224. Working through the code for Ins_ISECT() in ttinterp.cpp, it appears as though the algorithm is incorrectly classifying the two lines as parallel when in fact they are orthogonal.

- aek

Anonymous

 

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

Attach File(s):
   
   
Comment:
   

Attached Files
file #26799:  isect.patch added by podtelez (2KiB - text/x-patch - alternative fix)

 

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)
  •  

    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 5 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Sat 20 Oct 2012 02:23:13 AM UTCpodtelezAttached File-=>Added isect.patch, #26799
    Wed 17 Oct 2012 09:35:51 AM UTCwlStatusNone=>Fixed
      Assigned toNone=>wl
      Open/ClosedOpen=>Closed
      Planned ReleaseNone=>2.4.11

    Back to the top


    Powered by Savane 3.1-cleanup1