November 2020 - Inkscape Devel

snapping to lines &co.
by NASA Jeff 15 Nov '20

15 Nov '20

I've just been hand tracing a jpg image someone asked me to turn into a drawing. Here are my notes on the process: When moving points they need to be able to snap to points on the curve of lines of other shapes, maybe controlled by being in the same group. Smoothing worked quite well, it would be nice if there were some option to do it to the contours of an image either, Fitting when smoothing, Snapping curves to to an underlying image when editing a curve over an image, could be controlled by layers and opacity etc.. Another feature that would be nice is to snap one part of a path to another part of a path, breaking segments where necessasasary. So say you have two hand drawn paths, where some segments of one are close to or partly overlap the some of the segments of the other path. An option to fit the two segment sets of the path that are close to each other would be nice. I expect I can prototype some of this.

1 0

oh, i didn't send this and answered my own question.
by NASA Jeff 14 Nov '20

14 Nov '20

Does anyone know OTT how filling is performed? Is it just the standard, sort the vertices and walk the inside edges down either side of the vertex a line at a time? I can probably tell by making some shapes that don't fill in a uniform manner when you do that and see who inkscape fills them. I've got a good collection of path segment functions together now for prototyping, and found the first SVG feature implemented on the GPU, or at least in OpenCL, filters. So, that's a positive. I'll think I'll keep on working on the extension before doing any experimentation but I think I've to go a good outline of things to test to see how they fair in terms of rendering performance and enough SVG features down that I should be able to do a bit more than just a point line test. I looked up Bézier length calculations again, and they are basically an approximation using lookup tables. Wikipedia said you could calculate them definitely using a partial integral when I looked a while back but it seems it was incorrect and I'm back where I started in high school calculating the sum of the magnitude of the segments.

3 2

so that would mean.
by NASA Jeff 13 Nov '20

13 Nov '20

When I do a bucket fill I store the result as a collection of lines going from one inside edge to the other than enumerate the list to redraw the lines. Something like gimp would typically trace the extremities to produce a selection outline and fill a bit mask in the same way as I would bucket fill. To create a selection. I don't think a GPU would handle the outline trace at-all well, but most fill patterns and styles are quite possible using shaders, or tilled textures. (I just did a search and came across an OpenCL implementation of filters) https://bugs.webkit.org/show_bug.cgi?id=70099 I don't know what licence the code uses but it's a good example of what's achievable. Oh, I see now, there's fill rule evenodd and fill rule nonzero, so i was almost right.. That's a lot of experimentation, hopeful we should be able to identify what SVG elements or parts of elements can be calculated or rendered at high performance and which ones require a more traditional approach. Even then performance could possibly be improved manually vectorizing if GCC doesn't for a good job. (I expect you have to structure your code in a way that's friendly to GCC's algorithms) and switching to scaled integers over floats which are higher performance and give you more control over the (I've forgotten the word), basically the number of bits you've got to play with to maintain a desired rounding error. Integers having higher performance is certainly the case for older generation CPUs where that bit of performance may be really noticeable to the end user who may not have an acceleration viable GPU.

1 0

i think i've got it.
by NASA Jeff 13 Nov '20

13 Nov '20

It looks like as I described, sorting the vertices and walking the inside edges. Except overlapping boundaries seem to follow a z-order based on the order in which the vertex appears on the path. So, it's basically a bucket fill with some level of z-order based on vertex creation order.

1 0

memory requirements and GPU CPU performance on older systems.
by NASA Jeff 13 Nov '20

13 Nov '20

A full 32bit 4k screen is 31mb There are approximately 70 full 4k screens in 2GB, which is about the memory of an ancient PC or graphics card. My PC performs unbuffered memory writes at 10GB/s according to a benchmark I just ran, and read performance is over 13GB/s That means my PC can write the full 2GB in 1/5 of a second and my PC is currently under a lot of load, I have loads of stuff open. More details including GPU to CPU and CPU to GPU memory performance can be found here: http://www.bealto.com/gpu-benchmarks_mem.html The devices listed are relatively old, a PCI Express V2 16 BUS is listed with a performance of 8GB/s It would take 1/25 of a second to transfer the full 2GB at theoretical maximum performance. That means you could sustain a transfer rate of 201MB at a speed of 40 frames per second, or about 6 and a half full 4k screens or 25 full-HD screens 40 times a second. A modern PCI Express bus can sustain 126 GB/s Having a vector with 32bit x and y coordinates for every pixel of a 4k screen shouldn't pose a performance issue. Old PCI Express 2 systems can achieve that at 120 fps. Masks and stencils won't be the whole screen and even if they were older systems without 4k screens (you need a modern graphics card to be able to operate one) could have roughly 350 full-HD screen stencils before filling up 2GB of RAM. So, the memory requirement of using masks and stencils and then texturing and filtering on the GPU shouldn't be an issue. Well, that's all the theory out of the way, and it certainly seems viable. Just to see if any of it works in practice.

1 0

whilst the user twiddles their fingers.
by NASA Jeff 13 Nov '20

13 Nov '20

Creating masks for filling may be slow, but it could just initially be done for clipped areas and then background areas can be calculated during user idle time, so they can be cashed so that they don't have to be recalculated if something on a layer above them changes.

1 0

worst case scenario
by NASA Jeff 13 Nov '20

13 Nov '20

worst-case scenario is that i have to load everything into bitmaps and do the calculations using shaders using the colour of the bit map for the coefficient values. That's basically what OpenCL does in the background for you, but it should work on machines that don't support OpenCL assuming they can operate on enough bitmaps at once to provide the number of coefficients needed.

1 0

i may do a little experiment sooner rather than later.
by NASA Jeff 13 Nov '20

13 Nov '20

What I'll do for feasibility is create some arrays for triangular strips for every pixel of the screen, perform the basic spline calculations on them combined with normal calculations so the triangular strip has a width in the direction of the normal of either side and see what the performance is like. I have quite a new PC with a fast GPU, my older PC will have a different performance profile I expect.

1 0

more on rendering usin g the GPU.
by NASA Jeff 13 Nov '20

13 Nov '20

it does if it's architectured right, see for instance how the Pathfinder library does it it doesn't if it needs back-and-forth stuff with cpu and gpu involved (anyway, 2am, going to bed) oliverthered 1:37 AM ok, I'll run a test soon of calculating all the line points an entire SVG file in one go to see how that performs. but you're correct, unless there's some way you can work with the line points when rendering an image on the GPU you have to shuttle the calculations between the GPU and CPU to do the drawing. that then leaves the question of how often do you actually have to recalculate all the drawing points. you could calculate the drawing points as a triangular strip maybe. Then it's just one trip to the GPU and back to calculate them and then you change the data type into vertices and send them off to the GPU again to be rendered. you should then be able to manipulate the line directly on the GPU you just can't break it or delete it without having to go from GPU to CPU again. Filling is a lot harder on any kind of scale. Here's one example of SVG filling on the GPU: http://matthieu.besson.pagesperso-orange.fr/2010.01.15/SVG Rendering using OpenGL.html matthieu.besson.pagesperso-orange.fr SVG Rendering using OpenGL line drawing is however fixed filling not dynamic filling, you know the width you don't have to do bounds checking for the fill boundary. and it's still possible to do that on the CPU as a mask and then have the GPU render the fill texture and style etc.. an array of drawing points need be no bigger than a few full screen 32bit depth textures to fill the whole screen with lines. If you can create an array of triangles at point separation using the tangents of the spline you should then be able to use a shader to do all the stroke drawing, feeding it the array of triangles you've calculated. anyhow, i'll have to do some benchmarking, but in theory at least everything apart from creating a mask for filling can be handled by the GPU. So to do all of that you need to know the length of the lines so you can precalculate the size of the array needed to hold the triangular stipes at one pixel spacing..

1 0

looks like opencl should be able to do it.
by NASA Jeff 13 Nov '20

13 Nov '20

So, long as you don't need to increase or change the number of elements in the vectors, basically no memory allocation, it looks like bulk vector operations are easy with OpenCL... here's an example where a vector id added: https://github.com/rsnemmen/OpenCL-examples/tree/master/sum_array But there's a wide variety of other possible functions... I'll have to port the path rendering into OpenCL code and see how well it performs when I give it a vector containing all the path data in an entire SVG file in one go. That should at least performance benchmark it and provide a proof of concept.

1 0