Re: Release Objectives

Ok, I'll make a roadmap for the overlap removal algorithm.

On 19-06-14 19:49, Frank Trampe wrote:
> With the right documentation and some advice from you, it may be 
> easier to reimplement some of these things than to reverse engineer 
> the existing code.
>
>
>
> On Thu, Jun 19, 2014 at 12:21 PM, Kristof Bastiaensen 
> <[email protected] <mailto:[email protected]>> wrote:
>
>     On 19-06-14 17:38, [email protected]
>     <mailto:[email protected]> wrote:
>     > On Thu, 19 Jun 2014, Jose Da Silva wrote:
>     >>> I guess a brutal force  way to detect failed remove-overlap
>     operation
>     >>> was to render the outline into bitmap and compare the before/after
>     >>> bitmaps. If the deviation was too big, redo the remove-overlap
>     >>> operation with different setttings.
>     >> Let's avoid that if we can.
>     > I tried to implement that in Tsukurimashou, and it didn't work
>     very well.
>     > I'm not sure what the current state of those tests is - it's
>     been a while
>     > since I've touched them - but the code still exists, can be
>     enabled with
>     > the appropriate configuration options, and I'd encourage interested
>     > parties to get a copy of Tsukurimashou and try it.  Issues 474
>     and 685
>     > made the whole thing more difficult.
>     >
>     >> Then it is a matter of figuring out which curve intersects what
>     curve.
>     >> When you've figured-out which curve crosses which curve, then
>     you use a bit
>     >> of algebra to find the crossover point.
>     > Much can go wrong and we need to handle ALL the special cases
>     properly.
>     >
>     > In particular, if you calculate the intersection point of two spline
>     > segments, because of numeric precision the point you calculate
>     may not
>     > actually be exactly on either segment.
>     >
>     > If you split a segment A into two segments B and C, their end
>     points may
>     > not actually be exactly at the intersection point you intended
>     to use as
>     > the split point.  Then an intersection calculated against B
>     might give you
>     > a point that is in effect a point on C; or an intersection that
>     should be
>     > exactly at the endpoint of B may instead be within the interior
>     of B,
>     > causing you to split B again, recursively, and create a very short
>     > segment.
>     >
>     > If you have two segments that coincide, you have to recognize
>     that - and
>     > there may be cases where two segments *nearly* coincide
>     (because, for
>     > instance, they both represent arcs of the same circle [splines can't
>     > represent circles exactly]) but due to numeric precision and the
>     > inherent limitations of the spline approximation they are not bit
>     > for bit identical.  If you don't use a tolerance and call them
>     coincident
>     > when they're not, then you end up splitting them at all the many
>     points
>     > where they cross, and because the differences between them were
>     at the
>     > limits of your precision anyway, the resulting split-down
>     segments will
>     > flail around due to rounding error and be likely to trigger
>     other bugs.
>     >
>     > It may be a miracle it currently works as well as it does.
>
>     You can use the bezier clipping algorithm to robustly find the
>     intersections
>     between two bezier curves (see
>     http://tom.cs.byu.edu/~557/text/cagd.pdf
>     <http://tom.cs.byu.edu/%7E557/text/cagd.pdf>)
>     This is also used by inkscape and lib2geom.  I have implemented it in
>     my haskell library https://github.com/kuribas/cubicbezier
>
>     The two curves may have an infinite number
>     of overlaping points, if they represent the same polynomial.
>     This will be obviously the case when the two curves have the same
>     control points.
>     It's also possible when they are the same polynomial, but with
>     different
>     control points, but this is very unlikely.
>     This should be checked before calculating overlapping points.
>
>     If you have a design with nearly coincident segments, that may give
>     many control points, but why would anyone use that in a design?
>     The maximum number of points that coincide for two (non-identical)
>     segments is 9, so that shouldn't cause any crashes.
>
>     Kristof
>
>     >> Straight lines should be simpler.
>     > With straight lines you're especially likely to run into issues of
>     > coincident segments.  There are also issues from lines that are
>     meant to
>     > be straight but are not perfectly so.
>     >
>
>
>     ------------------------------------------------------------------------------
>     HPCC Systems Open Source Big Data Platform from LexisNexis Risk
>     Solutions
>     Find What Matters Most in Your Big Data with HPCC Systems
>     Open Source. Fast. Scalable. Simple. Ideal for Dirty Data.
>     Leverages Graph Analysis for Fast Processing & Easy Data Exploration
>     http://p.sf.net/sfu/hpccsystems
>     _______________________________________________
>     Fontforge-devel mailing list
>     [email protected]
>     <mailto:[email protected]>
>     https://lists.sourceforge.net/lists/listinfo/fontforge-devel
>
>
>
>
> ------------------------------------------------------------------------------
> HPCC Systems Open Source Big Data Platform from LexisNexis Risk Solutions
> Find What Matters Most in Your Big Data with HPCC Systems
> Open Source. Fast. Scalable. Simple. Ideal for Dirty Data.
> Leverages Graph Analysis for Fast Processing & Easy Data Exploration
> http://p.sf.net/sfu/hpccsystems
>
>
> _______________________________________________
> Fontforge-devel mailing list
> [email protected]
> https://lists.sourceforge.net/lists/listinfo/fontforge-devel

------------------------------------------------------------------------------
HPCC Systems Open Source Big Data Platform from LexisNexis Risk Solutions
Find What Matters Most in Your Big Data with HPCC Systems
Open Source. Fast. Scalable. Simple. Ideal for Dirty Data.
Leverages Graph Analysis for Fast Processing & Easy Data Exploration
http://p.sf.net/sfu/hpccsystems

_______________________________________________
Fontforge-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/fontforge-devel