canvas.pathIntersections index out of range

[geniot]

I'm trying to convert a large SVG to PNG:

But I'm getting an exception:

panic: runtime error: index out of range [11] with length 11
goroutine 1 [running]:
github.com/tdewolff/canvas.pathIntersections(0xc044b9a1c8, 0xc044b9a1c8, 0x0, 0x0)
C:/Users/vitaly/go/pkg/mod/github.com/tdewolff/canvas@v0.0.0-20240305210031-9a377e2a1436/path_intersection_util.go:605 +0x34ee

So I found this place in the source code and fixed it somehow. If you could you take a look at my PR, maybe you find it ok and merge it.

Next step: performance, it takes ages to convert this SVG. I'm looking at JSVG (written in Java), it takes a second or two there.

My conversion code:

	file, err := os.Open("score.svg")
	reader := bufio.NewReader(file)
	c, err := canvas.ParseSVG(reader)
	if err != nil {
		panic(err)
	}
	if err := renderers.Write("score.png", c, canvas.DPMM(3.2)); err != nil {
		panic(err)
	}

[tdewolff]

Thanks for the bug report and the proposed PR. Let me take a look at this after the weekend.

[tdewolff]

Could you send me the score.svg file?

I'm wondering if it is slow to parse the SVG, or slow to render the PNG. What final image resolution do you use with JSVG? The rasterizer depends heavily on the final image size, but it is already optimized with ASM so not sure how much can be won there. The SVG parser was put together quickly though, so hopefully that might be the performance issue.

[geniot]

ea

I actually attached the score to the first message. It's the second line.

[tdewolff]

Ah yes, it shows up almost invisible in GitHub because of its width.

The problem is in detecting a line-ellipse intersection that is not found due to a numerical precision error. The problem is that we have a half-circle arc on one path, and the other path is part of that arc, but then goes outwards with a straight line segment. It detects the tangents on the parallel/overlapping arcs, but does not find the same tangent (which should cancel out only together) at the end of the line segment.

EDIT: the problem is in error propagation. The arcs are not exactly overlapping, one has a 6e-13 difference in the ending Y coordinate, this is making its center be 1e-12 off, the radii be 3e-13 off, ending angle be 1e-11 off, which causes the line-ellipse calculation to be off by more than 1e-10 and takes them to be not touching.

[tdewolff]

To explain further, we're trying to find intersections between two paths. In this case, it is the path with itself to eliminate self-intersections caused by stroking. This particular path touches/intersects itself several times, but the problem is the following situation:

One part of the path is a circular arc:

M30.242341004748596 37.609669236818846A0.8700000000000001 0.8700000000000001 0 0 1 28.82999999999447 36.9294

The other part of the path is a linear segment and a circular arc:

M30.23402723090112,37.620459766287226L30.170131507649785,37.66143576791836A0.8700000000002787 0.8700000000002787 0 0 1 28.82999999999447 36.92939999999941

According to the code, the linear segment's end ALMOST touches the circular arc, it is off by 5.7e-4 (that is significant). But is also almost touches its own next path segment (circular arc as well) by the same distance, but two following segments MUST touch at their endpoints, so something is off and is generating a very large error.

My suspicion is that parsing the circular arc representation to a center+angles representation is very prone to numerical error propagation (https://github.com/tdewolff/canvas/blob/master/path_util.go#L65). Will investigate further.

We MUST find all such touching collisions because otherwise further on we can't figure out if two subsequent touching endpoints of a path actually intersect the other path (which may happen when two paths intersect at 90°, but one or both paths have a line segment ending/starting exactly at the intersection point). This is why your PR is almost certainly wrong as it tries to address the issue "too late".

[geniot]

Maybe you are talking about some rendering which is necessary. But I'm comparing the performance with https://github.com/weisJ/jsvg
I just tested. It takes 849 milliseconds to produce the following result:

I don't see any faulty arcs or intersecting segments. It's just what I need.
Well, I guess I'll have to rewrite this in Go myself. I'm going to use it on https://play.octavian.app/

[tdewolff]

I was just adding information to this issue in order to document the bug hunting. The SVG file has no faulty arcs of course, though it is quite suboptimal in describing its shapes, which stretches the numerical stability of the library. I'm expecting to fix this soon.

850 ms for a 42852x539 rasterization is probably right. This library should be in the same ball park. Parsing the SVG takes 30 ms on my machine (fairly slow in my opinion), but the rasterization should take the brunt of the execution time. How long did it take this library to render the SVG (using your PR I suppose) for you?

[geniot]

How long did it take this library to render the SVG (using your PR I suppose) for you?
I couldn't wait till the end :) I tried a small SVG and it took some seconds. Then I tried my long SVG and it took ages and didn't exit. So I just stopped it.

[tdewolff]

I've fixed this issue by disabling ellipses (and flatten them much like Beziérs) in the intersection detection code. This should have no visual effect, but generates flattened paths after Settle and Stroke and all boolean operations.

@geniot The fact that it took so long is because you were trying to create an image of dimension 137126x1728, something my image viewer doesn't even display because it is too big. This is because you were using DPMM(3.2). When using DPMM(1.0) you get the same image size as you posted of 42853x540 pixels. That took me 1.9 seconds to generate, so about twice as slow as JSVG on your computer, but then I don't know what computer you have.

A comparison with other tools:

• convert: 4.7 seconds
• rsvg-convert: can't render an image larger than 32767 pixels (probably they use int16)
• inkscape: crashes, probably asking too much memory?
• svgexport: 3.6 seconds
• cairosvg: image size is too big

So it really is not trivial to render an image that large, I'm actually happy that my library is the fastest out of those well-known tools! Could you please try again and tell me how long it takes to generate the image on your machine with the fix I posted above? If JSVG is really faster I would like to know their "secret".

EDIT: after profiling, of the 1.9 seconds it takes me to generate the image, about 1.3 seconds is spent on generating the PNG file (image/png.filter and compress/flate) which is not something that can be sped up. Only 0.2 seconds is spent on rasterization, wow!

EDIT2: saving the file as BMP (which doesn't use an expensive compression method) takes only 0.3 seconds in total, to parse and render the SVG, which proves my profiling above. Impressive.

[tdewolff]

@geniot Hey Vitaly, I'm still very interested to see how JSVG and this library compare with each other while saving to a PNG image of the same size. If you find time to check that would be great! You could also compare with writing to a BMP file since I suspect that most time is spent on compressing to PNG for both libraries.