> But surely a generic tessellation approach could support perfect arbitrary transformations
Yes, but at typical font sizes this generates a lot of tiny triangles (0 to few pixels) which perfoms badly on GPUs.
10,583 karma · joined February 2, 2010
Yes, but at typical font sizes this generates a lot of tiny triangles (0 to few pixels) which perfoms badly on GPUs.
It does give you an anti-aliased value between 0 and 1 that estimates how much of a pixel is being covered.
But this is a linear estimate based on horizontal and vertical distance to the Bezier curve. It does not look correct at long distances, which is why you shouldn't use it for outlines, drop shadows or the other cool things you can do with (M)SDF. A single pixel outline works fine but is not really legible with modern display resolutions (very thin lines).
For finding the minimum distance between a quadratic Bezier curve and a point would require solving a 3rd degree polynomial, where Slug's algorithm gets away with solving a quadratic equation per pixel. This is makes a big performance difference.
At first glance, subdividing the Bezier curves sounds like a bad idea (more Beziers to rasterize) but it opens doors for some parallelism, and most Bezier curves that appear in fonts are monotonic in the first place (so the increase is very modest). This was inspired by this entertaining but not very serious video about font rasterization [0].
The first parallelism optimization is checking against the curve bounding box vs. a rectangular (in uv-space) region of pixels, and this can quickly determine if the Bezier needs to be evaluated in the first place. This can be done per GPU warp.
The second optimization works only for rectilinear transformation (no rotation, skew or perspective). Solving the quadratic equation involves a square root and a division (which alone are >30% of the computation), which can be computed for each row and column of pixels instead of for each pixel (2n instead of n^2).
Both optimizations rely on mathematical invariants of monotonicity, ie. the derivative of the Bezier curve must be non-zero. All Bezier curves can be robustly subdivided into monotonic sections using de Casteljau's algorithm.
My simple benchmarks compare favorably to Slug on the GPU and to "fast" rasterization algorithms on the CPU (which is an order of magnitude faster than "fancy" rasterization algorithms with hinting etc).
Unfortunately there are so many hobby projects and so little time. All I have is messy shaders that draw individual characters and a few benchmarks to see how quickly (and something similar for the CPU). Going from there to a complete text rendering system would be a lot of work. Writing a more detailed article with illustrative code examples is something I'd want to do but haven't gotten around to.
If you want to offer words of encouragement or geek out about rasterization algorithms, I welcome any input.
[0] https://www.youtube.com/watch?v=SO83KQuuZvg Sebastian Lague - Coding Adventures: Rendering text.
I had a quick glance of the code and it seems to use mostly basic arithmetic instructions on fixed width simd vectors using some helper macros like SIMD_MUL(x, y) for _mm_mul_ps, etc. Some explicit simd intrinsics code for stuff like sin.
That would've been pretty easy to write with portable_simd in Rust or the equivalent C/C++ language extensions (or maybe C++26 std::simd).
You'd just use f32x4 (or add a typedef with attribute in C++) and then use x*y instead of SIMD_MUL.
For basic stuff like this, you should get the exact same generated code.
https://clang.llvm.org/docs/LanguageExtensions.html#vectors-...
This I agree with, deploying and running code for the correct cpu is a problem with no established solution.
As for actually writing the code, portable_simd is great. You need to adjust simd width and compiler config for the cpu you deploy to and fill in the blanks with intrinsics. Which is much less work per target than writing it all with raw intrinsics if you are deploying to more than one target.
This is trivial (but not pretty!) to do with something like `#[cfg(target_feature = "avx2")] const SIMD_WIDTH: usize = 8`. You need a few lines of ugly cfg logic to configure this.
A somewhat orthogonal and much more difficult problem is how to select it at runtime. You would either need to have different binaries built with different compiler options, link object files built with different compiler options to same binary, or dynamically link the correct code at runtime.
This is actually one of the (IMO only) cases where intrinsics are more practical: you can use `_mm256_add_ps` from AVX2 intrinsics regardless of whether you've configured your compiler to support AVX2 or not. As long as you check at runtime before calling the code so you don't get illegal instruction exceptions.
I pass in the vector width as a generic parameter like this:
fn do_simd_stuff<const N: usize>(x: Simd<f32, N>) { x.mul_add(x+x, x*x); }
> you run out of registers and spill all over the place
As usual when optimizing SIMD code, you should keep an eye on the generated disassembly and the benchmark results and watch for register pressure and the other usual things.
I'm definitely NOT saying that you always get the best perf by using 2x SIMD width, but in this particular case it was so.
This is much much easier to do with portable_simd than if you'd write the same with intrinsics, you can change the SIMD width without having to rewrite all your code (e.g. changing from SSE `_mm_add_ps` to AVX `_mm256_add_ps` etc).
It's still a partial solution, you still need to drop down to intrinsics for some special instructions every now and then (which is easy), but in my projects this accounts for much less than 1% of the lines of code. Not applicable everywhere of course.
It's definitely a 80% solution where you occasionally need to drop down to intrinsics (at zero runtime perf cost) for CPU specific instructions.
But just having vector types, arithmetic, swizzling, loads and stores will go a long way for basic tasks.
And with generics you can write code that is type and width agnostic. No need to rewrite your code of you want to go from SSE to AVX512, just change from f32x4 to f32x16 (or use generics) and you are done.
This is incorrect, you can use vectors wider than native SIMD width and the compiler will break them down to register size of the target cpu.
In fact it's sometimes better to used wider than native width, in some applications I see 20% better throughput with f32x16 (512 bits) on an AVX2 CPU (256 bits). It is kinda like loop unrolling it.
Claims to such effect has been made in public by reputable persons but they are not very credible nor has any supporting evidence been shown in public.
Drones getting lost due to GNSS jamming is happening.
But intentional misdirection towards a target would require GNSS spoofing capabilities over an impractically large area and that the drones would be susceptible to simple spoofing. They have satellite navigation, inertial navigation, terrain following cameras and listen to ground based radio sources like cell towers and are designed to operate in hostile RF environment. Just sending a fake GPS signal (several of them) won't make the drone divert to a specific target or direction.
I'm not buying the misdirection story until more compelling evidence is made public.
To engage a slow flying drone with cannons from a fighter jet, they have to get really close while flying close to stall speed. They had some success in shooting down drones but the explosion and the debris caused several lost fighters.
Maybe something like a Embraer Super Tucano turboprop fighter with a gunpod could work. But that has very little other use in the battlefield.
All of these provide a similar set of features and you can use normal arithmetic operations (+, -, *, etc) for SIMD vectors. Together with templates/generics you can also write code that can deal with any vector width. These get compiled to LLVM vector types and will generally give you pretty good generated code.
This is a very good way of writing basic SIMD code and has the benefit that your code can be compiled to multiple instruction sets. I've been working on a project that can compile down to SSE2, AVX2, AVX-512 and NEON, with just a change of compiler options. Somewhat surprisingly I get the best performance by using 2x the native vector width (ie. f32x16 = 512 bits on 256 bit AVX2), which is kinda like unrolling the loop once.
There are some caveats, though. You will need to keep an eye on the generated assembly code to make sure you're on the happy path. You will inevitably need to drop down to ISA specific intrinsics every now and then (for that fast reciprocal square root with `__mm_rsqrt_ps` etc).
As an example I needed to do a gather load from an array of fp16's on AVX2, which does not do 16 bit loads. Rust's `Simd::gather_select` takes 64 bit usize as the index but AVX2 doesn't do 64 bit indices. But as long as I did all the index arithmetic in 32 bits and cast to usize at the last second, the compiler did what I wanted. But you need to kinda know what is available in the ISA to stay on the happy path. Not really an issue with arithmetic.
I'm sure that an experienced SIMD programmer can get better performance by writing intrinsics manually (say 5-20% better) but I'm already at 3-6x better than the scalar implementation I started with. And you'd have to write (and benchmark) the code for each ISA separately, meaning that you'd spend at least five times more time with it (and have 5x more code to maintain).
[0] https://gcc.gnu.org/onlinedocs/gcc-4.6.1/gcc/Vector-Extensio... [1] https://doc.rust-lang.org/nightly/std/simd/index.html [2] https://en.cppreference.com/cpp/numeric/simd
We do have gather load instructions in SIMD instruction sets these days (AVX2 and newer), so AoS vs SoA is not nearly as important as it was once.
Scatter stores are also available but only in newer CPUs.
Yes, it is. In SIMD you can do a reduce for a commutative function in O(log N) steps. Sum, product, min, max, all, any, etc.
Although in this case it might be better if you just take the mask (vector of booleans), convert it to a bitmask and check if it is (non-) zero.
If the language provides it, you might also use .all() or .any() for a mask.
I played a few more rounds today. Fun!
I really love ATC games and the "draw it by hand" aspect makes this kinda funny. Maybe I need to try with a real mouse, kinda slow on a trackpad. For a more serious entrant in this genre (with speeds, altitudes and radio navigation), check out Endless ATC on Steam.
I landed some 40 flights and made it near the top of the leaderboard.
The scoreboard is taking too much screen space and occluding the planes, would be better to have scores at the top or bottom.
You plug it into your project and it can be rendered on anything that can push pixels and/or triangles to the screen. Events from windowing system go in, list of triangles comes out.
This is intended to be used with OpenGL, Vulkan, D3D and other graphics environment and used in cases where integrating a "real" GUI toolkit would be more trouble than it's worth.
Other popular libs like Dear Imgui or Egui work the same way.
Like many software rasterizer projects I used Fabian Giesen's software rasterizer blog series [0] as the baseline.
For solid color triangles with depth testing my 10+ year old laptop achieve ~3.2 Gpixels/s fill rate, which is above 80% of the available memory bandwidth (~26 GiB/s at 64 bits per pixel), using memset as the baseline comparison.
I used Rust and std::simd. The code can be compiled for SSE2, NEON, AVX2 or AVX512 by changing compiler parameters. The inner loop uses 16-wide vectors (512 bits) although my computer only has 8-wide AVX2, but the compiler deals with that. I used generics so I can change vector width easily and have multiple vector widths in the same binary for benchmarking. 16-wide is about 10-20% faster than 8-wide. I was excited to see that AVX masked store instructions get used even though I did not explicitly write masked stores in the code. I spent a lot of time reading the disassembly of the generated code and it's very tight.
The performance falls off a cliff (170 Mpixels/s) once I introduce a "shader" in the inner loop because it is not SIMD friendly (one pixel at a time, not 16 pixels). But that is fine, I am intending to use this with visibility buffer style rendering (store integer triangle id's in color buffer) and/or software occlusion culling (depth buffer only). Neither technique need anything more than solid colors and z-buffer.
[0] https://fgiesen.wordpress.com/2013/02/17/optimizing-sw-occlu...
I got myself one earlier this year and it does what it says on the tin. It can also be controlled from a computer via USB serial connection using a text based protocol (albeit poorly documented and a bit buggy). I used some python scripts to program the signal generator and then capture some measurements from the scope to check the frequency responses of some analog electronics circuits for guitar.
There is a small community around, there are a few repos on GitHub for using them and also this very long eevblog thred.
https://www.eevblog.com/forum/testgear/owon-hds-200-handheld...
Can you share some useful sensors? Any good pH sensor that can work for some period of time without manual maintenance (cleaning the probes etc)?
I've built half a dozen similar box guitars, it's such a fun little thing to build.
Do I see a piezo disk under the bridge in the 3rd instrument? Do you use some kind of preamp with it?
I have been recently experimenting with different kinds of piezo pickups [0] and preamp electronics for them. I've figured out a pretty nice JFET based circuit for the preamp and ordered tiny 13x13mm PCBs with tiny SMT components assembled and it works pretty well (but needs a second revision). They mount directly on the volume potentiometer and fit in a small space.
The one thing I haven't figured out yet is grounding the electronics. In a typical electric guitar you ground the electronics by touching the (grounded) strings, but that doesn't work very well (at all) with slide guitar when your left hand has got a bottle neck slide on it (made of glass or ceramic which is an insulator).
Drop a message below if you want to geek out more about home made guitars and/or related electronics. Depending on your location I could also send some preamp PCBs your way.
[0] https://hazeguitars.com/blog/piezo-pickups-evolve (not my site)
For each AABB, you take the morton code of the minimum and maximum and store them in the array.
But for sorting and searching, construct a sort key from the pair of morton codes so that the most significant bits are the common prefix of the two morton codes and the least significant bits are the "level" (length of common prefix in bits).
E.g. for a 3d octree with 64 bit keys, you'd have 1 unused bit, 57 = 19 * 3 bits of morton code prefix and 6 bits of level. A 2d quadtree with 32b keys would have 1 unused bit, 26 = 2 * 13 bits of prefix and 5 bits of level.
You could also store just the sort key, but I've stored both AABB morton codes so that I can reconstruct the quantized AABBs for culling.
When you sort by this key, you'll get a linear octree where the beginning of the array is all the AABBs that overlap the subdivision plane, then everything on the left side of the plane and the rest is right side of the plane. When traversing the tree, you need two searches per node to find the entries belonging to this node and to find the split point between the left and the right side.
Having the "level" in the least significant bits works as a tiebreaker in the sorting to ensure that entries closer to the root of the tree are in the beginning of the array.
A faster and (arguably) simpler way to construct quad/octrees is using morton codes, sorting and searching with flat arrays [0]. It's also probably easier to implement.
The gist of it is that you quantize the coordinates, do bit interleaving to construct morton code and then sort. The sorting is using numerical keys so you can use a radix sort for O(n) complexity which is much faster on a GPU (but on single CPU core a comparison based sort will probably win if the array isn't huge).
Now everything on the top half of the space is in the beginning of the array and the bottom half is in the end of the array (assuming yxyxyxyx morton code bits). Each of those halves is then split left/right and then each level below that alternates between vertical and horizontal splits.
To find the split point in the array, look at the first and last entry of the (sub)array you're looking at, and look for the first differing bit with (first ^ last).leading_zeros(). Then binary search for the first entry where that bit is high.
To traverse the quad/octree, repeat this process with the two halves you found. This can be done without recursion in O(1) memory using a fixed size stack because you know the depth of the "recursion" is at most half the number of bits in the morton code.
If you used radix sorting for building the array, you can avoid the binary search if you store the histograms from the counting phase of the sorting. Storing the whole histogram may be too much, but just a few highest order bits can already help.
Although I've found experimentally that for small (less that 10000 objects) just sorting and searching is faster if the whole array fits in L2 cache. On my 2015 laptop a single core can sort 10k objects with 64 bit keys in 1 millisecond. Traversing the tree for frustum culling is about 5x faster than just going through the entire array because a lot of geometry can be discarded very quickly.
With a good comparison based sort rebuilding the array after some changes is mighty fast because modern sorting algorithms are much faster for "almost sorted" inputs.
For range queries ("Find everything in the region" in the article), you can probably get better performance by using the BIGMIN/LITMAX method [1].
Now here's a brain teaser to delight your Friday: the article and the method I describe above is for storing points/centroids, but often you need to store axis aligned boxes instead (AABB). There is a very clever trick for this that I discovered independently but later found in some research papers. Can you come up with a (very) small change in the algorithm above to extend it to AABBs instead of centroids?
[0] Karras: Maximizing Parallelism in the Construction of BVHs, Octrees, and k-d Trees - https://research.nvidia.com/sites/default/files/pubs/2012-06... [1] https://en.wikipedia.org/wiki/Z-order_curve#Use_with_one-dim...
Vulkan gives all the tools to avoid any "lag spikes" from shader compiling. In fact, causing them is much more difficult than OpenGL where they could happen in surprising places (and only on certain hardware).
The issue is two fold: 1. Some engines produce a lot of shader permutations. Some AAA titles can have 60000 different shaders compiled. 2. Some GPU rasterizer states (such as color blending) are implemented as shader epilogues.
In Vulkan 1.0 almost all of the pipeline state had to be pre-baked into a pipeline state object compiled ahead of time. This lead to a "shader permutation explosion" where different states need different pipelines.
This requires the game engine to either a) compile all the pipeline combinations ahead of time (slow loading time) or b) compile them as needed (lag spikes).
The core issue for this was solved years ago and now most of the pipeline states can be added to the command buffers ("dynamic states"). This solves the permutation explosion. But at the same time it opens the door for issue 2: some states (blending in particular) can cause a state-based recompile (like ye olde OpenGL days) at runtime.
The only solution to the second problem is not to use the dynamic states that trigger recompiling. That's basically only blending as far as I know. You can't even have dynamic blend state on all GPUs.
For maximum developer flexibility there's the shader object extension that allows mixing and matching shaders and pipeline states any way you want. This will cause state based recompiles at unpredictable times but it's an opt-in feature and easy to avoid if lag spikes are not wanted.
tl;dr: shader recompilation is easy to avoid in Vulkan but porting legacy engine code or art content may take you off the happy path.
The dynamic rendering local read feature is for this. You can get tiler gpus working on the happy path without the need for verbose render passes.
But mobile driver support being what it is, it'll take time until it's widespread in consumer devices (which don't get driver updates).
Afaik the extension isn't even finalized yet and they are pre-releasing it to gather feedback.
And you can't use gpuinfo for assessing how widely available something is or isn't. The stats contain reports from old drivers too so the numbers you see are no indication of hardware support.
To assess how widely supported something is, you need to look at gpuinfo, sort by date or driver version and cross reference something like steam hardware survey.
However it looks like it's simpler to change your shaders (if you can) to use the new GLSL/SPIR-V functionality (or Slang) and don't specify the root signature at all (it's complex and verbose).
Descriptor heaps really reduce the amount of setup code needed, with pipeline layouts gone you can drop like third of the code needed to get started.
Similar in magnitude to dynamic rendering.