Iterating Over Binary Trees

Binary trees are great. If you ever have to implement one yourself though, you're probably either using C or you need to look at the documentation for your language's standard library more closely. Even POSIX C has the tsearch family of functions from <search.h>. Continue reading Iterating Over Binary Trees

Collisions

This animation is of one of Dimension's test scenes, physically integrated with collision detection and gravity. Each collision is perfectly elastic. The 1000-sphere scene was integrated and collision-detected 100 times per frame. The integration and rendering took 30 minutes on 12 cores, or 3 hours of CPU time. Continue reading Collisions

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

Priority R-Trees

PR-trees, as used by Dimension, provide a bounding-volume hierarchy with the unique property of bounded query complexity. Combined with intersection caching, they work as a very efficient BVH, comparable to POV-Ray's performance. This is a rendering (using Dimension) of the PR-tree generated for one of its test scenes: Continue reading Priority R-Trees

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 Cubic Polynomials

Although a closed form solution exists for the roots of polynomials of degree ≤ 4, the general formulae for cubics (and quartics) is ugly. Various simplifications can be made; commonly, the cubic $$a_3\,x^3+a_2\,x^2+a_1\,x+a_0$$ is transformed by substituting $$x = t-a_2/3a_3$$, giving Continue reading Solving Cubic Polynomials

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