Taking LINQ to Objects to Extremes: A fully LINQified RayTracer


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

Comments (51)

  1. LINQ als Renderer LINQ hat was…

  2. MSDNArchive says:

    HARD CORE. Very impressive!

  3. You’ve been kicked (a good thing) – Trackback from DotNetKicks.com

  4. neuralocity says:

    Amazing.  This is an eyeopening experience for myself, very interesting.  Thanks!

  5. neuralocity says:

    You should start a LINQ Cookbook site.

  6. MichaelGiagnocavo says:

    Would be cool if let was available in normal expressions and could also define subexpressions… I can’t wait to see what C# 4 will enable.

  7. ASPInsiders says:

    In my new ongoing quest to read source code to be a better developer , I now present the seventh in an

  8. Welcome to the thirty-third edition of Community Convergence. This week we have a new video called Programming

  9. A few weeks back, Soma blogged about an increased investment by the Microsoft Developer Division in the

  10. Luke Hoban is now full time as program manager on F#, and has just posted a short introduction about

  11. Luke Hoban is now full time as program manager on F#, and has just posted a short introduction about

  12. Luke Hoban is now full time as program manager on F#, and has just posted a short introduction about

  13. Through Don Syme&#39;s blog I read about Luke Hoban moving from the C# team at Microsoft to the F# team

  14. Bryan says:

    You are insane.  My hats off to you.

  15. Anonymous says:

    Screenshot? :)

  16. CoqBlog says:

    Je viens de tomber sur ça : Taking LINQ to Objects to Extremes: A fully LINQified RayTracer En clair

  17. LukeH says:

    Anonymous –

    There is a screenshot of the image produced by the raytracer on my previous blog post (linked to above).  Probably more fun though to try it out for yourself :-).  The attached code file can be compiled with the C#3.0 compiler at the command line or imported into a VS 2008 project.

  18. If you look in the PLINQ samples in the December 2007 CTP , you’ll see a parallel implementation of Luke

  19. If you look in the PLINQ samples in the December 2007 CTP , you&#39;ll see a parallel implementation

  20. Dimchansky says:

    LINQRayTracer is slower, than first version of RayTracer. Why?

  21. Often, when you try to find out how to write the correct LINQ query you need, you end up being confused

  22. Often, when you try to find out how to write the correct LINQ query you need, you end up being confused

  23. Consider a simplified version of the parallel implementation of Luke Hoban’s LINQ ray tracer var Xs =

  24. Consider a simplified version of Luke Hoban&#39;s LINQ ray tracer var Xs = Enumerable .Range(1, screenWidth

  25. Ivan says:

    Продолжение беседы про прикладную функциональщину. Попытка реализовать парсер п

  26. LukeH says:

    Dimchansky – Thanks for the comment on the performance difference between the query-based version and the original version.  As you point out, there is a fairly significant performance overhead for the version that uses one giant query.  I should have mentioned this as an additional reason to *not* recommend this extreme kind of code for a typical application.

    The culprit in terms of performance in this case is primarily the many "let" clauses.  These each incur a method call, a delegate invocation and an allocation of a "SelectIterator".  Since many of these are run in tight loops which are hit close to millions of times during a typical run, the additional cost is magnified significantly.

  27. Welcome to the thirty-eighth Community Convergence. These posts are designed to keep you in touch with

  28. Anders says:

    Impressive! Regarding the comments on this article, one should really do something about the crap! But I guess you don’t have the option to delete any of ’em, do you LukeH?

  29. SHArQ says:

    Uhh… Is that thingie what you call a BIG query?

    How about a 40KB-length, seven-level-nested one? :)

  30. Last fall in Barcelona, Spain two PM’s from the C# team gave talks on key parts of the new technology

  31. Vi riporto un link ad un post che potete trovare anche nei link della StartPage di VisualStudio. Sono

  32. works guo says:

    这里是LINQ to XML利用let暂时存放子节点的数据,再从查询let中的数据得到XML中子节点多个属性.

  33. CoryDambach says:

    Do you have a version of the Ray Tracer distributed with the Parallel Extensions CTP where the code has more comments for people without 3D graphics experience?  The organization of the CTP version is superb(in comparison to the single file one), but without XML comments I found navigating it tiresome…  (I know teaching 3d programming was not the purpose of either, but I thought I’d ask.)  I’ve learned quite a bit from it already.

    Also, I haven’t looked at the code for this one, but did you use Parallel Linq in it, the post didn’t seem to imply it.  If not, why didn’t you?

  34. I’m finally getting into the groove with LINQ and lambda expressions, and am over the initial skepticism

  35. ctodx says:

    An interesting question that someone asked of me recently, indicating perhaps that the information from

  36. Niall Connaughton says:

    Pretty cool, fun reading through it all 😛

    I was just wondering about the performance issue raised. I haven’t read the other version of the code so I don’t know if this improvement would be just for this mega-LINQ version or not. But I was looking at the section of the query that works out if an object is in shadow from the light and I think the query could be tweaked a bit.

    Couldn’t you put in a where clause to filter out objects which intersect the ray from the light but are beyond the originally intersected object? Then you could remove the order by and use FirstOrDefault(), saving on intersecting all other objects in the scene once you found a shadow casting object.

    I guess depending on how many objects you have and how much shadow you have this may have varying levels of improvement.

  37. I have ported this raytracer to XQuery!  All the code explained line by line so you can understand what is going on.  It runs with XQSharp.

    More information can be found here:

    http://www.xqsharp.com/xqsharp/samples/raytracer/index.htm

  38. Wow… this is the greatest piece of code written in a LONG time.  You need to get an award or something.

  39. Joshimac says:

    Hi , I am trying to implement the same RayTracer in VB.net.But it is unable to recognize isect variable.

    Can someone plz help.

  40. Joshimac says:

    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))}

  41. Justicle says:

    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

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

  43. Alejandro Piad says:

    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.

  44. YunHarla says:

    mhhh i wonder if this would also work with ObjCs NSArray filters 😀

  45. Ignacio Soler Garcia says:

    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!