Category Archives: Computer Science

Ray / Priority R-Tree Intersection

These animations, rendered with Dimension, show the ray / bounding box intersections that occur when rendering a single pixel. The first video shows the regular search, and the second shows the faster case of a cache hit, as described in the previous post. Each ray/box intersection takes up one second in these videos, which aptly illustrates the difference between the cache miss and cache hit cases. For this pixel, the improvement is more than a factor of two. Continue reading Ray / Priority R-Tree Intersection

Fast, Branchless Ray/Bounding Box Intersections

(Update: part 2)

Axis-aligned bounding boxes (AABBs) are universally used to bound finite objects in ray-tracing. Ray/AABB intersections are usually faster to calculate than exact ray/object intersections, and allow the construction of bounding volume hierarchies (BVHs) which reduce the number of objects that need to be considered for each ray. (More on BVHs in a later post.) This means that a ray-tracer spends a lot of its time calculating ray/AABB intersections, and therefore this code ought to be highly optimised. Continue reading Fast, Branchless Ray/Bounding Box Intersections

Fast Binary-Coded Decimal Addition and Subtraction

Binary-Coded Decimal, or BCD, is the most obvious way to encode a positionally-represented decimal number in binary: literally, 1234 becomes 0x1234. The some of the earliest of early computers used this representation, and the SMS protocol still uses it for some ungodly reason. It also has a more sane role as the expanded version of the DPD encoding for IEEE 754-2008 decimal numbers. Continue reading Fast Binary-Coded Decimal Addition and Subtraction

Righteous hack: getting 263 - 1 points in a silly Facebook game

Security through obscurity doesn't work. Every once in a while I like to prove this fact, by getting worldwide high scores on vulnerable leaderboards. The first time I did this was to Area Flat 3 (which was an awesome game when I was in elementary school, and is still pretty fun). Check the all-time top 100 scores for H4X0R (I know, not very original; I was 13, sue me). But that hack was child's play compared to this one. Continue reading Righteous hack: getting 263 - 1 points in a silly Facebook game

Solving Polynomials

A well known (if not by name) theorem is the Abel–Ruffini theorem, which states that there is no algebraic expression for the roots of polynomials with degree higher than 4.

A not-so-well-known fact is that for any polynomial \(P(x)\), it is possible to find (with exact arithmetic) a set of ranges each containing exactly one root of \(P(x)\). One such algorithm is due to James Victor Uspensky in 1948. Continue reading Solving Polynomials