Taking LINQ to Objects to Extremes: A fully LINQified RayTracer

Taking LINQ to Objects to Extremes: A fully LINQified RayTracer

Rate This
  • Comments 51

Not too long ago I blogged about a C# raytracer which took advantage of a lot of C#3.0 language constructs.  However, you may have noticed that it did not actually use LINQ query expressions all that much.  Well, after discussing this with a coworker on the PLINQ team at lunch one day - I was convinced that it should be possible to express the logic of the raytracer in a LINQ to Objects query.  The result is below - a single 60-line LINQ query which captures the complete raytracing algorithm.

[DISCLAIMER:  I am by no means suggesting it's a good idea to write code like this.  Do so only at your own risk!  Just as you *could* write your entire application in one method body, or decide to replace all if statements with virtual method dispatches, doing what I show below is a clear abuse of this language construct.  But it's an interesting example to show that there is a lot of expresiveness available in C#3.0 query expressions.]

One Really Big Query Expression!

var pixelsQuery =
    from y in Enumerable.Range(0, screenHeight)
    let recenterY = -(y - (screenHeight / 2.0)) / (2.0 * screenHeight)
    select from x in Enumerable.Range(0, screenWidth)
           let recenterX = (x - (screenWidth / 2.0)) / (2.0 * screenWidth)
           let point =
               Vector.Norm(Vector.Plus(scene.Camera.Forward,
                                       Vector.Plus(Vector.Times(recenterX, scene.Camera.Right),
                                                   Vector.Times(recenterY, scene.Camera.Up))))
           let ray = new Ray() { Start = scene.Camera.Pos, Dir = point }
           let computeTraceRay = (Func<Func<TraceRayArgs, Color>, Func<TraceRayArgs, Color>>)
            (f => traceRayArgs =>
             (from isect in
                  from thing in traceRayArgs.Scene.Things
                  select thing.Intersect(traceRayArgs.Ray)
              where isect != null
              orderby isect.Dist
              let d = isect.Ray.Dir
              let pos = Vector.Plus(Vector.Times(isect.Dist, isect.Ray.Dir), isect.Ray.Start)
              let normal = isect.Thing.Normal(pos)
              let reflectDir = Vector.Minus(d, Vector.Times(2 * Vector.Dot(normal, d), normal))
              let naturalColors =
                  from light in traceRayArgs.Scene.Lights
                  let ldis = Vector.Minus(light.Pos, pos)
                  let livec = Vector.Norm(ldis)
                  let testRay = new Ray() { Start = pos, Dir = livec }
                  let testIsects = from inter in
                                       from thing in traceRayArgs.Scene.Things
                                       select thing.Intersect(testRay)
                                   where inter != null
                                   orderby inter.Dist
                                   select inter
                  let testIsect = testIsects.FirstOrDefault()
                  let neatIsect = testIsect == null ? 0 : testIsect.Dist
                  let isInShadow = !((neatIsect > Vector.Mag(ldis)) || (neatIsect == 0))
                  where !isInShadow
                  let illum = Vector.Dot(livec, normal)
                  let lcolor = illum > 0 ? Color.Times(illum, light.Color) : Color.Make(0, 0, 0)
                  let specular = Vector.Dot(livec, Vector.Norm(reflectDir))
                  let scolor = specular > 0
                                 ? Color.Times(Math.Pow(specular, isect.Thing.Surface.Roughness),
                                               light.Color)
                                 : Color.Make(0, 0, 0)
                  select Color.Plus(Color.Times(isect.Thing.Surface.Diffuse(pos), lcolor),
                                    Color.Times(isect.Thing.Surface.Specular(pos), scolor))
              let reflectPos = Vector.Plus(pos, Vector.Times(.001, reflectDir))
              let reflectColor = traceRayArgs.Depth >= MaxDepth
                                  ? Color.Make(.5, .5, .5)
                                  : Color.Times(isect.Thing.Surface.Reflect(reflectPos),
                                                f(new TraceRayArgs(new Ray()
                                                {
                                                    Start = reflectPos,
                                                    Dir = reflectDir
                                                },
                                                                   traceRayArgs.Scene,
                                                                   traceRayArgs.Depth + 1)))
              select naturalColors.Aggregate(reflectColor,
                                             (color, natColor) => Color.Plus(color, natColor))
             ).DefaultIfEmpty(Color.Background).First())
           let traceRay = Y(computeTraceRay)
           select new { X = x, Y = y, Color = traceRay(new TraceRayArgs(ray, scene, 0)) };

foreach (var row in pixelsQuery)
    foreach (var pixel in row)
        setPixel(pixel.X, pixel.Y, pixel.Color.ToDrawingColor());
Let Expressions

"let" query clauses allow you to introduce a variable into scope which can be used by the following query clauses.  Similar to local variables in a method body, this gives you a way to avoid evaluating a common expression multiple times by storing it in a variable.  This can be very useful even in much simpler queries.  Of course, in the query above - let is absolutely critical.

Recursion

A raytracer is inhenertly recursive - whenever a ray hits a reflective or transparent surface, new rays have to be cast.  Thus the query that expreses the raytracer needs to be recursive.  But the let clause doesn't support declaring recursive functions.  Not to let that stop us (as it really should!) - we can use the Y combinator to introduce recursion by hand.  Mads wrote a very detailed description of the recursive lambda expressions in C# recently - and the code example above uses my personal implementation of some of the same ideas he describes. 

Expression-based control structures

When you are trying to write things in a single query expression - you don't have the luxury of using any statements.  Since most of the C# control structures are  statement based (if, switch, for, while, etc.) - this can make things a little trickier.  One really valauble expression-based control structure is the ternary operator ( x ? y : z ).  This is used in a couple of places above to provide the necessary branching logic.  The rest of the control structuring is accomplished with LINQ Standard Query Operators - Select, SelectMany, Where, OrderBy, Aggregate and DefaultIfEmpty.  As functional programmers have shown for years, the expressiveness of these very general list processing operations is impressive.

Conclusion

In case you had any doubts - hopefully this convinces you that C#3.0 Query Expressions are really a very expressive language construct.  Of course - this expressiveness is probably best used in more moderation than shown here!

File iconLINQRayTracer.cs

kick it on DotNetKicks.com

Leave a Comment
  • Please add 1 and 8 and type the answer here:
  • Post
  • Posting the VB.net Code:

    Dim pixelsQuery = From y In Enumerable.Range(0, screenHeight) _

                        Let recenterY = -(y - (screenHeight / 2.0)) / (2.0 * screenHeight)

                  Select From x In Enumerable.Range(0, screenWidth) _

                      Let recenterX = (x - (screenWidth / 2.0R)) / (2.0R * screenWidth) _

                      Let point = Vector.Norm(Vector.Plus(scene.Camera.Forward, Vector.Plus(Vector.Times(recenterX, scene.Camera.Right), Vector.Times(recenterY, scene.Camera.Up)))) _

                       Let ray = New Ray() With {.Start = scene.Camera.Pos, .Dir = point} _

                       Let computeTraceRay = DirectCast((Function(f) Function(traceRayArgs) (

                                                                       From isect In _

                                                                       From thing In traceRayArgs.Scene.Things _

                               Select thing.Intersect(traceRayArgs.Ray) Where isect IsNot Nothing Order By isect.Dist

                           Let d = isect.Ray.Dir _

                           Let pos = Vector.Plus(Vector.Times(isect.Dist, isect.Ray.Dir), isect.Ray.Start) _

                           Let normal = isect.Thing.Normal(pos) _

                           Let reflectDir = Vector.Minus(d, Vector.Times(2 * Vector.Dot(normal, d), normal)) _

                          Let naturalColors = From light In traceRayArgs.Scene.Lights _

                               Let ldis = Vector.Minus(light.Pos, pos) _

                               Let livec = Vector.Norm(ldis) _

                               Let testRay = New Ray() _

                             Let testIsects = From inter In From thing In traceRayArgs.Scene.Things _

                                      Select thing.Intersect(testRay) _

                                   Where inter IsNot Nothing _

                                  Order By inter.Dist _

                                   Select inter _

                              Let testIsect = testIsects.FirstOrDefault() _

                              Let neatIsect = If(testIsect Is Nothing, 0, testIsect.Dist) _

                               Let isInShadow = Not ((neatIsect > Vector.Mag(ldis)) OrElse (neatIsect = 0)) _

                              Where Not isInShadow _

                              Let illum = Vector.Dot(livec, normal) _

                              Let lcolor = If(illum > 0, Color.Times(illum, light.Color), Color.Make(0, 0, 0)) _

                               Let specular = Vector.Dot(livec, Vector.Norm(reflectDir)) _

                               Let scolor = If(specular > 0, Color.Times(Math.Pow(specular, isect.Thing.Surface.Roughness), light.Color), Color.Make(0, 0, 0)) _

                               Select Color.Plus(Color.Times(isect.Thing.Surface.Diffuse(pos), lcolor), Color.Times(isect.Thing.Surface.Specular(pos), scolor)) _

                           Let reflectPos = Vector.Plus(pos, Vector.Times(0.001, reflectDir)) _

                           Let reflectColor = If(traceRayArgs.Depth >= MaxDepth, Color.Make(0.5, 0.5, 0.5), Color.Times(isect.Thing.Surface.Reflect(reflectPos), f(New TraceRayArgs(New Ray(), traceRayArgs.Scene, traceRayArgs.Depth + 1)))) _

                           Select naturalColors.Aggregate(reflectColor, Function(color__2, natColor) Color.Plus(color__2, natColor))).DefaultIfEmpty(Color.Background).First()), Func(Of Func(Of TraceRayArgs, Color), Func(Of TraceRayArgs, Color))) _

                      Let traceRay = y(computeTraceRay) _

                      Select New With {.X = x, .Y = y(), .Color = traceRay(New TraceRayArgs(ray, scene, 0))}

  • Crazy awesome. I just did some quick profiling (I know thats not the point), and it seems IEnumerator.MoveNext() is taking most of the time - according to my calculations it's running at 1 millisecond *per call*!

    Here's the cut and past from the profiler (apologies for bad formatting):

    Functions that were called by RayTracer.RayTracer.Render(class RayTracer.Scene)

    Function Name Elapsed Inclusive Time % Elapsed Inclusive Time Number of Calls Elapsed Exclusive Time Application Inclusive Time Application Exclusive Time Elapsed Exclusive Time % Application Inclusive Time % Application Exclusive Time %

    System.Collections.IEnumerator.MoveNext() 97.14 253,791.40 250,275 1,123.30 43,060.49 223.40 0.43 97.25 0.50

  • I imagine there's a bug inside and someone who hasn't written this code must fix it...

  • Amazing... I'm always looking for bizarre ways of bending a language syntax to do this kind of stuff, but your proposal is one of the most impressive I've found.

  • mhhh i wonder if this would also work with ObjCs NSArray filters :D

  • It's a nice thing to see :) One question, do you know what's the performance of the LINQ Raytracer vs the same algorithm coded in the standard way? Thanks for sharing!

Page 4 of 4 (51 items) 1234