New graphics pipeline?

[mbostock]

In September 2014, I started work on a modular geographic projection pipeline that would allow you to compose geometric transformations during rendering. For example:

• Multiple Rotations
• Back-Facing Hemisphere
• Satellite Projection
• Rotating Orthographic

Rather than having a monolithic projection that renders GeoJSON to a context (Canvas or SVG), the new modular rendering pipeline would have three types of objects: sources, transforms, and sinks. A source generates a sequence of geometry calls (e.g., polygonStart, lineStart, point…). A sink receives geometry calls. And a transform is both a source and a sink that transforms the input geometry to some output geometry. A pipeline is thus a source followed by zero or more transforms followed by a sink.

Example sources:

• d3.geoJsonSource(sink) could return a function that takes a GeoJSON object (such as a FeatureCollection), and makes the corresponding sequence of geometry calls on the specified sink.

Example transforms:

• d3.geoRotate(λ, φ, γ, sink) applies spherical rotation.
• d3.geoClipCircle(π / 2, sink) applies spherical clipping around the origin.
• d3.geoClipAntimeridian(sink) applies an antimeridian cut at ±180°.
• d3.geoOrthographic([precision, ]sink) applies an orthographic projection with adaptive sampling.
• d3.geoMatrix(a, b, c, d, e, f, sink) applies a 2D planar affine transformation.
• d3.geoClipExtent(x0, y0, x1, y1, sink) applies 2D axis-aligned bounding box clipping.

Example sinks:

• d3.geoContextSink(context) renders to canvas 2D context.
• d3.geoPathSink() computes an SVG path data string.
• d3.geoSphericalAreaSink() computes spherical area.
• d3.geoPlanarAreaSink() computes planar area.
• d3.geoSphericalLengthSink() computes spherical length.
• d3.geoPlanarLengthSink() computes planar length.
• d3.geoSphericalBoundsSink() computes spherical bounding box.
• d3.geoPlanarBoundsSink() computes planar bounding box.

Open Questions:

1. Where would you convert from degrees to radians? Another transform? Or would all the sinks and transforms that operate on spherical geometry require degrees as input, trading performance for convenience?

2. Is everything immutable? Do you have to rebuild the entire pipeline when anything changes? Will that be slow?

3. Is there a way to avoid massive nested function calls when constructing a pipeline, say using a source.then?

4. Is there a way to make it less verbose? Are we going to continue to provide convenience functionality such as d3.geoArea(feature) in addition to d3.geoSphericalAreaSink? Is there a more concise way to distinguish between objects that operate on planar versus spherical geometry (say using the “geom” rather than “geo” prefix)?

5. How do you retrieve values from sinks (e.g., when computing area)? Maybe there’s a sink.value function that you call after sending it geometry, and transform.value is implemented as a pass-through to the underlying sink?

Some of the work is here:

https://github.com/d3/d3/compare/graphics-pipeline

[monfera]

Re #3, especially that you're using terms such as sources and sinks: for one-off pipeline executions, the promise style may be sufficient. But if the pipeline isn't just for a singular execution, but instead considers updates over time, then an FRP inspired library such as most.js or the even more compact flyd would be a more natural fit. A hacky example for what I mean by updates over time is here, it uses the core of flyd for the data propagation (but the experiment ending up totally not idiomatic D3; wasn't a goal here).

In general, some folks find RxJS, most.js, xstream and similar libraries more natural and composable than promises, and better at error handling. André Staltz and Ben Lesh come to mind.

Some personal notes on the utility of a data flow concept are here.

[Fil]

Maybe add that transforms should offer an .invert() function (by default we could use numerical interpolation, w/o needing an explicit setup).

[ I'm very excited by this as I already have a few real use cases in mind, such as 2D linear transforms (the plane is shown in perspective and support "vertical" bars of data); the "fisheye" projection http://bl.ocks.org/Fil/1b574a4185a04273de47b49591243102 ; the Bertin 1953 projection; and exceptions to clipping (where you clip at an angle but allow a small "ear" of interesting land to get in though it's a bit farther than the clip angle). & unfortunately I have no knowledge about the performance issues. ]

[jrus]

My opinion is that the standard intermediate form for any geographic processing system which wants good performance should be cartesian (x, y, z) coordinates on the domain [–1, 1] × [–1, 1] × [–1, 1]. These make it easy to rotate, clip, build search trees, compute lengths and areas, project onto Gnomonic, orthographic, stereographic, etc. maps, and so on, without dealing with the same kinds of edge cases / singularities you get when working with a latitude/longitude grid, and without needing to constantly evaluate transcendental functions everywhere.

For example, to find the distance between two points on a (assumed spherical) globe, you can find the straight-line distance in Cartesian coordinates d, and then take 2arcsin(d/2) to get the angular distance; depending on the precision required this can be approximated pretty cheaply.

If such coordinates need to be compressed when you don’t want to represent each point as 3 double precision floats somewhere (e.g. if you want to send a giant polyline to a worker thread or save it to a file, and want to minimize I/O), a very computationally cheap and effective representation is to take the stereographic projection onto a plane, and then cut the resolution, e.g. to a pair of half-precision floats. Both the forward and inverse stereographic projections are extremely cheap, requiring only a few multiplications/additions and a single division operation per point.

[mbostock]

@Fil Good point about inverting transforms. If a transform only has a reference to its output sink, then there’s no way for it to encapsulate inversion… Hrm.

@jrus That’s an interesting idea. I would guess it would be harder to reuse much of our existing implementation with that approach, but it might still be worth pursuing.

[mbostock]

I was able to implement multipass clipping using projection.preclip! See the geoPipeline here:

https://observablehq.com/@d3/satellite-explorer

[mrnix]

Hi Mike. @mbostock Huge thanks for d3 and satellite projection especially! I have a weird issue with projection clipping. For some reason it gives an extra sphere shape, when I'm trying to draw geojson. Happens in very unpredictable cases.

For example here is two almost the same projections, it differs in distance parameter only: 2.140612617 vs 2.124627867. On second one I have merged land and ocean, so I can't fill it properly.

1. good

   

2. bad ^{(you can see extra-light land borders)}

   

Spent many hours trying to solve it. I use the example from here https://observablehq.com/@jjhembd/tilting-the-satellite, Tried different extra factors for preclip function, like d3.geoClipCircle(Math.acos(1 / distance) - 0.000001). I tried different numbers from 0.001 ... to ... 0.000000001, but it breaks geoPath for other projection parameters.

Do you have any ideas how it could be fixed? Thank you.

[Fil]

@mrnix please open a new issue with a link to a notebook with the settings that actually fail.