Projective GA for ray tracing

[tian]

Hi there! I attended the Siggraph GA talk and I see that this forum is empty, so I hope that ignorant questions are welcome!

I’m interested in geometric algebra for ray tracing, so I thought I’d start a topic for it. As a first prompt: One of the problems for ray tracing is intersection with sharp triangles. When these triangles aren’t axis-aligned, the bounding box for them is much larger than they are, so raycasts will encounters many false positives.

If we use geometric algebra, is there some neat trick we can pull to avoid this? The purpose of AABBs is to define regions of space that can be nested hierarchically that are easy to test for intersection. Since calculating the intersection of two things is done differently in GA, can we use non axis aligned bounding boxes?

[cgunn3]

I can’t suggest any non-axis-aligned bounding boxes. But perhaps it’s useful to describe how I imagine directly ray casting against a triangle (sharp or not) might look like in 3D PGA.

Let the ray be r, a bivector, and the triangle be ABC where A, B, and C are 3-vectors. Precompute the bivector sides a = B v C, b =C v A, c = A v B. Join the ray r with each of these edge lines to obtain the scalars s = r v a, t = r v b, u = r v c. (The join of two lines measures, roughly speaking, the signed distances between the lines measured along their common normal line.) Then r intersects the interior of the triangle exactly when s, t, and u all have the same sign. In that case, this intersection can be calculated as (A v B v C) ^ r where A v B v C is the plane of the triangle. Since the three edges and the plane can be precomputed and stored with the triangle, the cost of doing a hit test reduces to the three joins r v a, etc., each of which is essentially the inner product of two 6-vectors for a total of 18 mults and 15 adds. Of course you can stop after two joins (12 M + 10A) if the signs are already different. To my admittedly ignorant ears it sounds like it might be competitive to checking against a bounding box.

But perhaps you are already using plücker line coordinates in your ray caster and are doing similar operations already without calling it geometric algebra?

[enki]

Hia Tian,

There are no ignorant questions, thank you for your attendance, and to break the ice on the forum !

Jumping right in, formats for points (homogeneous coordinates) and planes (linear equation = normal + offset from origin), are no doubt similar or exactly the formats you are using today, any sufficiently optimized code will be identical or very similar. (especially since the use of plucker coordinates is common for raytracing applications)

The obvious places where the use of PGA should be expected to deliver substantial speedups is a bit higher up in the pipeline, dealing with animations, smooth deformations, computational geometry, physics and kinematics.

That said a lot of the practical options remain unexplored - what exactly the advantages will be of using PGA planes and edge lines explicitely is uncharted - the new strict relation between area and volume provided by this representation may perhaps lead to more interesting acceleration structures.

From your post it sounds almost like you are storing an AABB per triangle ? Have you explored the use of alternate acceleration structures like e.g. k/d trees ?

Steven.