Register
handmade.network Library

Algorithms

How to do X using Y.

Article

  • Avoiding branchy loops in lexers with FSMs
    ★ 0 0
    aka Some Strategies For Fast Lexical Analysis when Parsing Programming Languages, by Sean Barrett
  • Eli Bendersky: A Recursive Descent Parser with an Infix Operator
    ★ 0 0
    Details how to add a shunting yard parser into a recursive descent parser. Examples in Python.
  • Eli Bendersky: Parsing Expressions by Precedence Climbing
    ★ 0 0
    "It's not necessary to be familiar with the other algorithms for expression parsing in order to understand precedence climbing. In fact, I think that precedence climbing is the simplest of them all. To explain it, I want to first present what the algorithm is trying to achieve. After this, I will explain how it does this, and finally will present a fully functional implementation in Python."
  • Eli Bendersky: Top-Down Operator Precedence Parsing
    ★ 0 0
    "The third article describes a method that combines RD [recursive descent] parsing with a different algorithm for parsing expressions to achieve better results. This method is actually used in the real-world, for example in GCC and Parrot (source). An alternative parsing algorithm was discovered by Vaughan Pratt in 1973. Called Top Down Operator Precedence, it shares some features with the modified RD parser, but promises to simplify the code, as well as provide better performance."
  • Expression Parsing
    ★ 0 0
    Details the Recursive Descent, Shunting Yard and Precedence Climbing parsing algorithms.
  • Point in Polygon Detection Strategies
    ★ 0 0
    Testing whether a point is inside a polygon is a basic operation in computer graphics. Graphics Gems presents an algorithm for testing points against convex polygons (Badouel 1990). This Gem provides algorithms which are from 1.6 to 9 or more times faster for convex polygons. It also presents algorithms for testing non-convex polygons and discusses the advantages and drawbacks of each. Faster, more memory intensive algorithms are also presented, along with an O(log n) algorithm for convex polygons. Code is included for the algorithms discussed.
  • The History of Zip Files
    ★ 0 0
    Describes in depth the history and inner working of the Zip compression format.
  • The Surface Area Heuristic
    ★ 0 0
    Improve ray-tracing performance by building a Bounding Volume Hierarchy using the Surface Area Heuristic as the splitting criterion. "The SAH rewards small nodes with many triangles, while avoiding large nodes with few triangles."
  • Two-stage tables for storing Unicode character properties
    ★ 0 0
    How to efficiently store and access properties of Unicode characters. The technique extends to other problems where sparse or repeating data must be looked up in O(1) time.
  • When Bloom Filters Don't Bloom
    ★ 0 0

Article Series

  • Red Blob Games
    ★ 1 0
    Visual explanations of math and algorithms, using motivating examples from computer games.

Blog

  • Eli Bendersky: A Recursive Descent Parser with an Infix Operator
    ★ 0 0
    Details how to add a shunting yard parser into a recursive descent parser. Examples in Python.
  • Eli Bendersky: Parsing Expressions by Precedence Climbing
    ★ 0 0
    "It's not necessary to be familiar with the other algorithms for expression parsing in order to understand precedence climbing. In fact, I think that precedence climbing is the simplest of them all. To explain it, I want to first present what the algorithm is trying to achieve. After this, I will explain how it does this, and finally will present a fully functional implementation in Python."
  • Eli Bendersky: Top-Down Operator Precedence Parsing
    ★ 0 0
    "The third article describes a method that combines RD [recursive descent] parsing with a different algorithm for parsing expressions to achieve better results. This method is actually used in the real-world, for example in GCC and Parrot (source). An alternative parsing algorithm was discovered by Vaughan Pratt in 1973. Called Top Down Operator Precedence, it shares some features with the modified RD parser, but promises to simplify the code, as well as provide better performance."
  • Markov Chains Explained Visually
    ★ 0 0
    Basic explanation of Markov chains with interactive visualizations.
  • The Surface Area Heuristic
    ★ 0 0
    Improve ray-tracing performance by building a Bounding Volume Hierarchy using the Surface Area Heuristic as the splitting criterion. "The SAH rewards small nodes with many triangles, while avoiding large nodes with few triangles."
  • When Bloom Filters Don't Bloom
    ★ 0 0

Book

  • Algorithms and Data Structures
    ★ 0 0
    Classic text on programming by Niklaus Wirth
  • Fractal Curves
    ★ 0 0
    A complete taxonomy of plane-filling (a.k.a space-filling) curves. E.g. Hilbert curve, Peano curve, Morton curve, etc...

Online Book

  • Fractal Curves
    ★ 0 0
    A complete taxonomy of plane-filling (a.k.a space-filling) curves. E.g. Hilbert curve, Peano curve, Morton curve, etc...

Other

Paper

  • Bidirectional Path Tracing and Multiple Importance Sampling (2 Minute Papers)
    ★ 0 0
    With a classical unidirectional path tracer, we'll have some scenes where it is difficult to connect to the light source, and therefore many of our computed samples will be wasted. What if we would start not only one light path from the camera, but one also from the light source, and connect the two together? It turns out that we get a much more robust technique that can render a variety of "packed" scenes with lots of occlusions with ease.
  • Matrix row-column sampling for the many-light problem
    ★ 0 0
    Computing global illumination using the many-lights approach is expensive, this algorithm presents a method ("exploration") for reducing the amount of lights to be sampled.
  • Metropolis Light Transport (2 Minute Papers)
    ★ 0 0
    Metropolis Light Transport is a powerful technique that can outperform the convergence speed of Bidirectional Path Tracing on most difficult scenes (what makes a scene difficult is a story on its own). It promises optimal importance sampling "along multiple steps" in the stationary distribution of the Markov chain.
  • Photon Mapping (2 Minute Papers)
    ★ 0 0
    Describes the Photon Mapping solution to light transport.
  • Polygonising a scalar field
    ★ 0 0
    Papers describing methods of creating a polygonal representation of a scalar field (e.g. marching cubes with voxels).
  • Stochastic Lightcuts
    ★ 0 0
    A solution to the global illumination problem by sampling from many lights. Stochastic Lightcuts is an improvement on the earlier Lightcuts algorithm. Presentation at HPG 2019.
  • Stochastic Progressive Photon Mapping (2 Minute Papers)
    ★ 0 0
    Describes improvements to Photon Mapping, called Progressive Photon Mapping, Stochastic Photon Mapping, and their combination.

Repository

  • Doug Crockford - Top Down Operator Precedence (aka Pratt Parsing)
    ★ 0 0
    In this Youtube video, the "top down operator precedence" method of parsing is discussed. In a nutshell, TDOP, also known as "Pratt parsing" is sort of like a combination of precedence climbing parsers and recursive descent parsers. Notably TDOP does not use a grammar, which makes it somewhat unique among other parser techniques. A working example by the author can be found here: https://github.com/douglascrockford/TDOP

Website

  • The Beauty of Bresenham's Algorithm
    ★ 2 0
    This page introduces a compact and efficient implementation of Bresenham's algorithm to plot lines, circles, ellipses and Bézier curves.
  • Fractal Curves
    ★ 0 0
    A complete taxonomy of plane-filling (a.k.a space-filling) curves. E.g. Hilbert curve, Peano curve, Morton curve, etc...

YouTube Series

YouTube Video

  • Advanced Global Illumination Using Photon Mapping
    ★ 0 0
    Photon mapping provides a practical way of efficiently simulating global illumination including interreflections, caustics, color bleeding, participating media and subsurface scattering in scenes with complicated geometry and advanced material models. This class will provide the insight necessary to efficiently implement and use photon mapping to simulate global illumination in complex scenes. The presentation will briefly cover the fundamentals of photon mapping including efficient techniques and datastructures for managing large numbers of rays and photons. In addition, we will describe how to integrate the information from the photon maps in shading algorithms to render global illumination.
  • Bidirectional Path Tracing and Multiple Importance Sampling (2 Minute Papers)
    ★ 0 0
    With a classical unidirectional path tracer, we'll have some scenes where it is difficult to connect to the light source, and therefore many of our computed samples will be wasted. What if we would start not only one light path from the camera, but one also from the light source, and connect the two together? It turns out that we get a much more robust technique that can render a variety of "packed" scenes with lots of occlusions with ease.
  • Doug Crockford - Top Down Operator Precedence (aka Pratt Parsing)
    ★ 0 0
    In this Youtube video, the "top down operator precedence" method of parsing is discussed. In a nutshell, TDOP, also known as "Pratt parsing" is sort of like a combination of precedence climbing parsers and recursive descent parsers. Notably TDOP does not use a grammar, which makes it somewhat unique among other parser techniques. A working example by the author can be found here: https://github.com/douglascrockford/TDOP
  • Matrix row-column sampling for the many-light problem
    ★ 0 0
    Computing global illumination using the many-lights approach is expensive, this algorithm presents a method ("exploration") for reducing the amount of lights to be sampled.
  • Metropolis Light Transport (2 Minute Papers)
    ★ 0 0
    Metropolis Light Transport is a powerful technique that can outperform the convergence speed of Bidirectional Path Tracing on most difficult scenes (what makes a scene difficult is a story on its own). It promises optimal importance sampling "along multiple steps" in the stationary distribution of the Markov chain.
  • Path Tracing and Next Event Estimation (2 Minute Papers)
    ★ 0 0
    A description of Path Tracing, a ray tracing solution to the rendering equation, and one of its traditional optimizations, Next Event Estimation.
  • Photon Mapping (2 Minute Papers)
    ★ 0 0
    Describes the Photon Mapping solution to light transport.
  • Practical Global Illumination with Irradiance Caching
    ★ 0 0
    Lighting usually only changes smoothly over a surface, Irradiance Caching is a classic approach to reduce the computational cost by only computing lighting at points where it changes quickly.
  • Radiosity
    ★ 0 0
    Lecture describing how to solve the radiosity equations used to compuse diffuse global illumination.
  • Ray-Traced Irradiance Fields (Real-Time Light Probe Rendering)
    ★ 0 0
    [...] how to combine glossy reflection ray tracing with diffuse ray-traced irradiance field probes. This creates a complete dynamic global illumination solution that scales across all DXR GPUs and minimizes light leaking without requiring manual per-probe or lightmap work by artists.
  • Stochastic Lightcuts
    ★ 0 0
    A solution to the global illumination problem by sampling from many lights. Stochastic Lightcuts is an improvement on the earlier Lightcuts algorithm. Presentation at HPG 2019.
  • Stochastic Progressive Photon Mapping (2 Minute Papers)
    ★ 0 0
    Describes improvements to Photon Mapping, called Progressive Photon Mapping, Stochastic Photon Mapping, and their combination.