ajeffrey|pto: I got reprojection mostly working, sorta, though there is one magic constant I determined through experimentation that I need to do some trig to be principled about :)

the quality loss is noticeable, but acceptable given the quality loss inherent in lens distortion correction anyway

besides, we can tweak parameters to improve quality

one problem is that I don't know why my initial technique, to move the camera back to unify frusta, didn't work

pcwalton: can we alternate which eye is rendered, and reproject the "off" eye from the previous frame? Might give less distortion than reprojecting from the "on" eye?

Does anyone use reviewable.io for Servo's PRs?

Task "Servo daily: Linux x64: with Rust Nightly. On failure, ping: SimonSapin, nox, emilio" complete with status 'failed'. Inspect: tools.taskcluster.net/tasks/JW0p9pXrRGCEitLMWhcdEQ

it’d been a while

SimonSapin: Don't know if a nightly with the new hashmaps is out yet but it might be worth waiting for it ?

eijebong: good point, that might be it

Yeah all the tests failures are on size_of

I guess the hashmap is a bit bigger in a struct now

standups: rustup + size_of regression investigation servo/servo #23263

standups: filed rust-lang/hashbrown #69

paul: occasionally, though not in a while

Manishearth: should I merge the rigid transform PR now?

or do you want to do some modifications beforehand (I have no complaint)

standups: reading webgl/es 2.0/s3tc specs; reviews.

ooh, will I actually clear off all of the urgent items on my todo list today :o

standups: Got bindgen to generate the magicleap C API bindings. asajeffrey/rust-webvr 900a723

\o/

nical: sure

jdm: re ^ we can either get rid of the use of the deprecated API (and require v0.20.0 of the SDK, and a matching OS version on the device) or suppress the deprecation error, neither sounds great to me.

ajeffrey: we could ifdef, couldn't we?

jdm: blech, yes we could but really???

ajeffrey: let's just suppress the deprecation for now

and kick that can down the road

jdm: OK

pcwalton: my condensation of our last conversation: github.com/bzm3r/pathfinder/blob/pf3-gentle-docs/docs/intro.md

someone asked me a good question though, which i am having trouble answering: "is my understanding correct that, due to accumulating signed areas additively to the alpha texture, pathfinder can't batch multiple separate but overlapping paths in one draw call?"

i believe the answer is: "pathfinder can do this, and in fact, doing this efficiently is what gives pathfinder its claim to fame"

but when i tried to back up my answer, by playing around with a silly model i made in inkscape, i ran into some issues

bzm3r: Pathfinder uses the GPU blender

to accumulate signed areas

so yes, it can

GPU blender, okay, will put that in as a note, and research it further

glBlendFunc()

this is how it accumulates the signed areas

btw this is the same thing that Skia's CCPR does I think

i see, i see

does pathfinder remake tiles as a user changes their "zoom level"?

a tile is 16x16 pixels, these are screen pixels, right?

yes and yes

everything bets blown away and rebuilt from scratch

this might seem inefficient, but there is really no alternative other than tessellation in the 3D case especially

and tessellation has its own problems

right

one could imagine just changing the tile size and resubmitting the commands to GPU without any CPU work, but this gets tricky (1) when the zoom is a subpixel amount; (2) when you want to further subdivide curves

furthermore we're often GPU bound anyway so this wouldn't really help that much

how does signed area coverage work with respect to anti aliasing?

I'm confused as to what you're asking -- signed area coverage is an implementation of antialiasing

pcwalton you're right, the question is confusing because i was confused

an old pathfinder blog post mentions: nothings.org/gamedev/rasterize

pcwalton: why is the bottom edge of the tile the tile size rather than max(from, to)? github.com/pcwalton/pathfinder/blob…/resources/shaders/fill.vs.glsl#L48

raph: because of the fill rule

we fill top to bottom for historical reasons

Got it, thanks.

I get it, but I think explaining it for a general audience would be something :)

so if you have a tile that looks like ◀

then you will have two fills, one on the top that looks like / and one on the bottom that looks like \

the top one will add +1 to everything below it

and the bottom one will add -1 to everything below it

ahhh

the bottom area cancels out to 0 so you end up with the shape of ◀

right

along the edges it'll be fractional positive/negative amounts

to create the antialiasing

That sounds like it could be converted into a fine illustration (hint, hint, bzm3r)

raph already working on it! started a bunch of illustrator drawings yesterday

The tricky bits are tile crossings

I don't fully understand that yet.

you mean, path crossings?

the question is how to accumulate it but that's where the GPU's blending hardware comes in

I mean lines that cross tile boundaries, or another way of putting it is shapes that are more than one tile.

I render in a mode where I say "if two fragments overlap the same spot, then add their results" -- glBlendFunc(GL_ONE, GL_ONE) with glBlendEquation(FUNC_ADD)

and since it's a signed floating point framebuffer I'm rendering to, it all just works

pcwalton: nice. That's basically the same as an atomic add, I imagine

But blend hardware is super optimized

raph: yep, except the GPU has special hardwarefor it

on desktop, specialized ALUs that collect the outgoing fragments from the shading units and execute the operation

pcwalton: I'm going to explore my compute idea during a cabin-in-the-woods retreat next week

It's going to be very different from this, very much "pull" while you're doing "push"

pcwalton for path crossings (where there are two paths crossing within one tile), would pathfinder have two alpha tiles associated with that tile? one for each path?

(not to derail this discussion)

(BTW, this is why GPU manufacturers don't want to add more blend modes -- it's because they're literally separate ALUs and they don't want to spend more die area down there)

and each alpha tile would sample from a solid tile that's relevant to a particular path (if the paths had different colours?)

bzm3r: if you have a path with multiple lines, they all accumulate to the same tile

but a line might cross multiple tiles, so that means multiple fill instances

(sorry if I've gotten that wrong, patrick can probably explain better than i can)

two paths with different colors are different tiles of course

raph ah yeah, i'm asking about the two paths with different colours case

they occupy the same "physical tile" (in terms of screen pixels)

but have two different alpha tiles?

right, i think for the purpose of accumulation they're completely separate

bzm3r: they are separate "objects" and so will have completely different tiles allocated

and will eventually be blended during the alpha tile compositing phase

during the fill phase they're considered completely independent

right

the "sampling from a solid tile" is something that happens in alpha tile compositing, not fill, right?

raph if i am understanding correctly, the answer is "yes", right?

a fill just generates the alpha tile

so we never sample from a solid tile

solid tiles only exist as rendering commands

oh true, i wrote this out in the condensation too...

there is a lookup table texture that records the color ("shader") of each object

but that's separate

raph: so, when it comes to tile crossings, there are basically 3 cases to handle

remember that we are doing a top to bottom sweep line

(1) horizontal tile crossings -- i.e. a single line crosses multiple tiles

in that case, we simply have a loop that clips and generates fill commands

let me link the code

it's this function github.com/pcwalton/pathfinder/blob/pf3/renderer/src/gpu_data.rs#L186

I really should move that into tiles.rs

(2) vertical tile crossings -- in that case we clip at the current tile strip lower edge, handle the top part, and push the bottom part onto the active edge list github.com/pcwalton/pathfinder/blob/pf3/renderer/src/tiles.rs#L473

a "tile strip" is a horizontal row of tiles

ok i'm gonna read those

me too

and there is a third case?

(3) is when you have are processing an existing active edge -- and I actually have to page this back into my brain :(

the code is here github.com/pcwalton/pathfinder/blob/pf3/renderer/src/tiles.rs#L117

will look through it!

ty very much, as always, for your time

the basic idea is that you have to handle fill coming through from tiles above

i hope to produce some nice illustrations for you too :)

and there are two cases to consider

(3a) there is fill coming from tiles above that partially, but not fully, spans the horizontal width of this tile

that is github.com/pcwalton/pathfinder/blob/pf3/renderer/src/tiles.rs#L160 and github.com/pcwalton/pathfinder/blob/pf3/renderer/src/tiles.rs#L192

(3b) there is fill that completely spans the horizontal width of this tile, github.com/pcwalton/pathfinder/blob/pf3/renderer/src/tiles.rs#L174

so just to make sure i have this right, if you were rendering a shape that was n tiles wide and 1 tile high, you wouldn't need to worry about active edges

raph: yes

in case (3b) we do not explicitly add a fill operation, but add a constant amount of fill to the tile itself, known as "backdrop"

the reason why we do this is that it makes it easy to identify solid tiles -- they are tiles with backdrop != 0 that have no fill operations attached to them

also, it cuts down on the load on the GPU blender a bit

in that case the backdrop is always an integer winding number?

right.

it's actually an i8

(might need to be expanded in the future)

used to be i16, but then I needed to pack tighter and I made it i8

oh well, could always expand it

sure sure, i don't think it's a big problem in practice

raph: oh, I also figured if it was a problem I could just overflow by adding explicit fill operations and making such tiles not solid

so "solid tile" would mean "tile whose winding number is between [-128,-1] or [1,127]"

which seems fine in practice

btw, you can see why I do this on CPU -- it's quite branchy and furthermore each curve in the path can produce a variable number of outputs (alpha tiles, solid tiles, fills). it is possible to do on GPU, but I'm not certain it will really be a speedup on most hardware

doing transforms and clipping on GPU would be more of an obvious win. unfortunately that happens before tiling, so it would be CPU -> GPU -> CPU -> GPU. still might be worth it, though

even clipping is difficult on GPU, though, because Sutherland-Hodgman clipping creates a varying number of output curves for each input curve

some amount of stream compaction will likely be necessary

yeah, i don't see doing this exact thing on gpu

i do wonder if it might be possible to do something a little more gpu-ish. for example, you could render delta-backdrop, then do cumulative sum to get the actual backdrop

or, and i'm totally just spitballing here, you could do the tile-backdrop calculation in one dimension but not the other

so you do a cumulative sum (font-rs style) in 1/16th the pixels

as opposed to the current backdrop calculation needing to be done for 1/256 the pixels

oh good, there's a servo s3 bucket that I don't have access to

(you can tell I like cumulative sum - it's not necessarily a good idea on gpu unless you have compute, and maybe not even then)

Ok I understand the algorithm. Good stuff.

Lemme see if I understand something (this might be useful for exposition)

Say you have an axis-aligned rectangle

If the whole thing fits within a single tile in height, then only the horizontal edges contribute, the vertical edges could basically be discarded

But if the vertical edges cross tile boundaries, then those crossings generate "active tile fills"

which are essentially equivalent to horizontal lines at the top of the tile strip

(one difference being that if the active tile fill covers a whole tile, it becomes backdrop)

standups: Uploaded the pathfinder magicleap demo to dropbox.com/s/ovxfj3ghwghg7xk/PathfinderDemo.mpk

standups: webxr spec discussions on editor-collab

raph: vertical edges can be completely ignored (they are not, but they contribute zero)

that is, vertical lines

raph: I considered doing prefix sum but decided against it for two reasons

(1) it doesn't really result in that many fewer pixels drawn -- the GPU hardware rasterizer does not know how to rasterize a line with anything other than Bresenham's algorithm (which is not sufficient) and therefore I draw the whole axis aligned bounding box for each line

the only thing that prefix sum would mean in terms of fragment shader invocation is that I wouldn't have to extend the AABB to the bottom of each tile

but I would be paying for that with the actual prefix sum

I did some back of the envelope measurements to test this and found that the gains from only drawing the AABB of each line would not be very large

(2) prefix sum is not realistically implementable without compute shader. I considered various techniques but they were too ugly for words, and they were way too expensive in terms of ROPs

it might be worth revisiting this choice if you had something like CUDA Dynamic Parallelism to be able to launch work groups from within the GPU itself developer.download.nvidia.com/asset…ief_Dynamic_Parallelism_in_CUDA.pdf

but it's probably years before we get this in GL or Vulkan, if we ever get it (it's been 5 years and there has been no interest outside of CUDA)

pcwalton: right, I see the limitations of prefix sum on GPU

raph: the real benefit of prefix sum would be that it allows for greater parallelism during the tiling phase

and to be clear, I'm not advocating prefix sum for the actual device pixels (like font-rs), I'm talking about tile generation

I could envision a fully on-GPU tiling phase that uses compute shader on all curves in parallel to generate fills and allocate alpha tiles

and then uses prefix sum to propagate fill between the tiles and generate solid tiles

in fact I suspect that is how I will want to proceed if and when I have an optional GPU tiling mode

however, I don't really see this as practical without compute shader. it might be doable, but not maintainably :)

Actually I don't think you need prefix sum for that; if all tiles see all curves, then you can just add up the contribution from each curve

so GL3 support demands that I do tiling on CPU, for now.

I'm likely to experiment with this next week

I suspect that will be asymptotically too slow

but I'm happy to be proven wrong

raph: my gut feeling tells me to do this:

allocate one GPU thread per curve

It's very likely what I end up with will be worse than PF3 :)

then for each curve sequentially output fills in the PF3 sense, using atomics to allocate alpha tiles as you go

happily, most curves in complex SVGs (which are, after all, the SVGs that we care about accelerating, since complex SVGs are the slow ones) only have 1 or 2 fills

so there should be quite good parallelism from that

right

essentially write a geometry shader.

in fact, I thought about using geometry shaders and asked Kai from the Chrome team yesterday if we could have them in WebGPU for this -- he said no :)

(which I'm fine with)

webgpu is on track to have an ok compute shader?

so having a curve generate fills makes sense, but how do you generate the backdrops (and the "active edge fills" which can be seen as partial backdrop)?

in your current code, this depends on the active edge list being sorted, doing the whole thing in scanline order

standups: some looking at webaudio stuff

raph: yes, Kai demo'd it to me yesterday :)

sweet. And it has stuff like ballot and shuffle?

dunno the specifics

I know I'm limiting myself very much to the future by experimenting with compute

And I should be very clear what my goals are here

no, it's valuable. if you succeed I'll probably seriously consider merging it into PF

given how we're skating right up to the perf edge in VR we need all the help we can get

I'm looking to see if I can do something simple and with smooth performance characteristics

raph: so here's what I was thinking: you first generate fills in compute shader, and then you go to fill them as usual -- and as you fill, you accumulate "outgoing fill" either in a separate buffer or in the bottom row of each tile

or, you could do a separate pass to accumulate outgoing fill, either way

Right, that's what I was talking about with the cumulative sums

then you use a prefix sum between tiles to propagate the fill around

You say prefix sum, I say cumulative sum, let's call the whole thing off

:)

anyway, then you have one "backdrop" per *vertical column* of each tie

tie

tile. stupid macbook pro keyboard.

Yup. I think that would work.

at that point you can allocate solid tiles

I do believe that you will never have to allocate any alpha tiles after initial fill generation as long as you make sure to allocate alpha tiles even if there no actual fills

think vertical lines

they generate zero-size fills

however, you still need to allocate alpha tiles for them because they are partially filled

I believe you're correct

But I'm not sure we're totally on the same page

BTW, the "Massively Parallel Vector Graphics" paper has the same idea, but it calls active edge fills/backdrops "shortcuts"

based on the analogy of Sutherland-Hodgman clipping

I don't like that term but you might see it around

I'm seeing generating those alpha tiles from intersections between vertical lines and tile boundaries

But I thought I heard you say vertical lines don't contribute anything

right, so consider rendering an axis aligned (but not tile aligned) filled rect

the vertical sides need to get alpha tiles allocated

however there will not actually be any fills in them -- or at least if you generate a fill it will be a degenerate fill with zero width and therefore no pixels filled

all of the paint in those tiles will be generated from the prefix sum pass

this is fine, you just need to make sure that they get an alpha tile assigned to them at some point so that you render them

in other words, all of their paint will come from the column backdrops generated during prefix sum

Yeah, this is making sense.

BTW compute shader is perfectly shippable on most devices these days. shipping large-scale desktop software is the exception, not the rule :)

(lucky us)

Just took another scan through the MPVG paper. It seems pretty complex :/

raph: yes, it's very... engineered :)

I'm not 100% convinced by quadtrees, they seem maybe more academic than practical

right

some gfx people proposed similar things to me at the last All Hands

I feel I'd need to see that the benefit is commensurate with the complexity

that said, have you been able to compare pf3 performance against their approach?

I have not

we really need people to do that kind of performance evaluation work

agreed, it would be good

I would like to, it's just as always time

one thing i *do* potentially see as useful from that paper is green's theorem area evaluation of beziers

i think it's not just time, i think there's also a case to be made for unbiased evaluation

yes, that is cool, especially since I think we're more memory bound than ALU bound in the fragment shader

might as well put those cycles to use

that's the sense i get too, anything that reduces the number of primitives is a win, as long as it isn't a ridiculous amount of computation

green's theorem itself is pretty simple, it's the crossing tests

note that splitting curves at tile boundaries is a pain

my personal feeling is that quad bez might be the sweet spot

I used to do it before I switched to converting to lines on-the-fly

cubics are really hard

possibly. monotonic quadratic beziers might help

definitely want monotonicity so you don't have to deal with two roots all the time

i have a pretty darn good cubic to quadratic converter in kurbo

a lot of PF3 is the desire to ship something simple so we can build on it later

it's been a couple of years, I feel I should show results

oh yes, i'm also motivated by simplicity

and it's a fairly conservative design that's extensible over time

actually, if you don't mind me bending your ear, i can explain more about where my motivation is coming from right now

sure

i've been following the progress of makepad, and it's quite impressive

long story short, it's a very direct generation of gl instances using imgui techniques, with as much intelligence as possible in the shader

for example, they have one shader for an animated "tab close" icon

performance is impressive, both cpu and gpu are in the 1ms range

(they're doing msdf for text, which is a whole nother discussion)

so basically if this is the future of gui, then i'm wasting my time with piet

i want to explore the question, what if you put the 2d graphics scene graph on the gpu, and evaluate it with compute

raph: so before you jump in, note that Unity is rapidly deprecating their IMGUI in favor of Unity UI, which is traditional

they did the IMGUI experiment, and are having perf problems, and are throwing it out

the jury is still out here

right, there are a lot of intertwined problems

so i want to know whether gpu compute evaluation of a 2d scene graph can be done performantly

and yes, I would like to get Pathfinder to that point, essentially -- putting the 2D graphics scene graph on the GPU and having a full GPU pipeline

if yes, then the druid/piet approach is valid

WebRender more or less does the Makepad approach

if no, that's evidence that you have to design your ui around gpu-friendly primitives to get performance

they have special shaders for borders and whatnot

I wrote some of them, once upon a time :)

rounded rectangles etc?

yeah

they have extremely optimized paths for rounded rects, CSS borders, even dashing and so forth

i'm particularly interested in clipping and opacity

yeah, they have fast paths for that, rounded rect clips in particular are very optimized

in ways that do not work for arbitrary vector clips

sure, easy to believe

so basically I don't feel I have to *do* the whole thing

lots of axis aligned bounding box tricks

you might compare WR perf with Pathfinder on scenes that both can render

but I just want to get a swag on whether it's possible

to get some initial numbers

if so, then i'll push forward with piet and expect pretty good performance on direct2d at least this year

this is easy to do, just save a web page from a browser to PDF, then convert the PDF to SVG and render it

... via Pathfinder

then compare to WebRender rendering the page directly

right'

beware of text though, PF has no glyph caching optimizations

text is kinda the interesting part :)

well, as far as text is concerned, the big question in my mind is whether you want (a) static 2D text, (b) smoothly zoomable 2D text, or (c) 3D text

but the alternative hypothesis is that a 2d api such as piet is a performance bottleneck that will kill performance in the long run

I don't know…I used to be skeptical of traditional 2D APIs but now with PF's experience I'm warming up to them

certainly if you have to do a lot of the work on cpu that is true

let me put it this way

I don't think that the current Web, or desktop UIs, on a flat screen is a particularly good fit for a traditional 2D vector API descended from PostSCript

so i basically want to explore uploading bits of scene graph to the gpu and letting the gpu basically run the whole pipeline

mostly because they involve translating relatively static axis aligned boxes

to accelerate this workload, it's mostly blitting. vector needs are minimal if any

for text, you typically just render to a glyph atlas and then call it a day

however, for game UI, or for UI in VR, that's a whole 'nother ball game

I feel like I understand this part of the space pretty well

game UI is mostly arbitrary vector scenes, often designed in Flash, that are frequently scaled

and VR of course is even more so

so tl;dr I think WebRender/Makepad's approach is probably best for desktop and mobile apps

I think the main part I don't understand well is getting the scene out of the UI logic and onto the GPU

ah, I see what you mean

The other thing I want to explore here is immediate / retained

druid is very old-school retained, in sharp contrast to makepad

well, you are always going to have a step that generates GPU buffers from a CPU-side display list. I don't see a way around it

ah, but i think there *is* something we can do

a CPU-side data structure

one could imagine a GPU data structure that you incrementally update

that may be what you were about to propose :)

which is generally inspired by flutter - basically widgets render into "layers", which are bits of display list

(just caught up to this discussion, ...so much to learn....but pretty cool :) )

clipping and translation are just nodes in the scene graph, so if you want to scroll, just update those, the contents of the scrolled window are retained

the sense i get is that wr tries to do a bunch of this, but makepad is aggressively immediate

the world gets drawn from zero every frame

raph: I mean, that's true for WR too

I don't see how you don't redraw the world from zero every frame

i mean it generates all instances on the cpu and uploads them every frame

That's what WR does too

well, ok, not for scrolling

so any sense of retaining it has is to avoid traversing the dom?

right, scrolling

(dom stands for?)

maybe what i'm talking about is generalizing what wr does for scrolling

document object model, it's the representation of the web content

i see adding scaling and opacity, for pinch-to-zoom and layer fade effects

anyway, you upload a tree root (i'm thinking in immutable style) and then tell the gpu "go" and it does the rest

so very much *unlike* flutter and ios you're not rendering these layers to textures for compositing

so it's entirely possible i'm smoking crack

but i want to build a rough prototype and take it for a spin on real hardware

i don't expect this retained stuff to cover for too many sins, it still has to be fast to build the scene graph

yeah, having a retained GPU data structure sounds doable

that you then render with indirect draw

but there i'm actually not worried, i see this as a fairly thin serialization/packing step over the traditional 2d api

this is what indirect draw was made for -- putting scene graphs on GPU

one thing that i do expect to be done on cpu is bounding boxes

(basically per-tile i want to do a bbox culled traversal of the graph)

i think for text glyphs etc you already have a bbox, i don't see this adding significant cost cpu-side

yeah, you will want to measure the perf of doing things on CPU before deciding to incur the complexity of moving to GPU

yes, i think it's *similar* to indirect draw but very different because my primitives are 2d not 3d

so this is why i'm going all in on compute, rather than trying to map to things that existing 3d pipelines do well

in any case, it feels worth playing with

in the worst case, it won't work but i will have learned a lot :)

pcwalton why is create_vertex_array only ever used by the GroundLineDrawing object in the demo?

bzm3r: because the actual code that does the vector renderer is in renderer/src/gpu/renderer.rs

found it :)

so every fill has to create a vertex array

and we don't really know up front how many fills there are going to be

standups: gamepad liveness digging servo/servo #23269

By my read, there's a vertex array for a *slice* of fills, might be amortized over a fairly large number

correct

raph there can be an indeterminate number of slices of fills too though?

it tries to do MAX_FILLS_PER_BATCH, which is 16000

right

right right right

16384, sorry

over 9000 in any case

heh

my head's hurting a bit

raph: sorry, there are two MAX_FILLS_PER_BATCH, one of which is unused :(

it's 0x1000

err, sorry, 0x4000

yeah, 16384

bzm3r: correct, there are an indeterminate number. we stream batches of 16K fills to the GPU as soon as they are ready.

pcwalton so, opengl "manages" vertex array object creation for you, but in vulkan/gfx-hal, you manage "vertex array object" ("AttributeDescs") --- basically, there's going to be one vertex buffer each for fills, and alpha tiles

the data within each buffer will be refreshed as new batches are created

yes

yeah, then i think i have a good handle on what `create_vertex_array` should do for the gfx-hal backend: it will create an attribute desc, and then these attribute descs will be stored within the Device struct

at "program" (pipeline in gfx-hal land) creation, use the stored attribute descs to fill out necessary info for pipeline creation

bzm3r: you might want to have two buffers, so you can be filling one while the gpu is drawing the other

you have to have barriers etc so you don't start writing into a buffer until the gpu is done consuming it

raph yeah, was reading a bunch about that yesterday

put the relevant resources into the graphics resource dump too

i'm still somewhat far from that point though

for now i was just figuring out what create_vertex_array should do (recall our discussion yesterday? i've changed my mind again, after seeing how renderer.rs uses the device trait)

standups: webaudio validation servo/servo #23270

(so i'll stick as closely as possible to the device trait, and only make small modifications like &mut)

sounds right

yay, reprojection works now with improved quality

and no magic constants, everything is worked out on paper :)