Jon's many-language ray tracer

Discussion in 'Java' started by alex goldman, Jun 24, 2005.

  1. alex goldman

    alex goldman Guest

    Regarding Jon's ray tracer, I'll play the devil's advocate:

    When you only have spheres, algebraic types are nice and dandy, but if you
    had a plethora of different objects to render, some of them special cases
    of others, perhaps using OOP and organizing them into a class hierarchy
    would be better?
     
    alex goldman, Jun 24, 2005
    #1
    1. Advertisements

  2. Maybe, but when in need of binary methods you will have to make one or more
    messes - and end up using the visitor pattern which I don't find
    particularly pleasant. What's the functional equivalent to the visitor
    pattern, and to the class hierarchy which is so often used as an example in
    OOP textbooks?

    I only had to do such a thing once, and used ocaml polymorphic variants -
    and I don't remember exactly what my solution looked like, nor if I liked
    my solution or not, but I think it was the visitor pattern implemented as a
    match over polymorphic variants (representing the "extensible" ADT of
    shapes), which would be IMHO the clever brother of the usual thing :)

    What should be the functional way to implement a hierarchy like

    shape
    circle <: shape
    box <: shape

    and the function "intersect" which is specialized in the case (box,box) and
    (circle,circle), but maybe also on (circle,box)?

    What should be the functional way to allow extensibility and successive
    refinement of the intersect function?

    Maybe there are elegant solutions only using ADTs, but maybe one needs
    functors, or polymorphic variants, or type classes, existential types etc.
    Is there anyone willing to propose solutions?

    bye and thanks

    Vincenzo
     
    Vincenzo Ciancia, Jun 24, 2005
    #2
    1. Advertisements

  3. alex goldman

    chris Guest

    Not a ray tracer, but I'm working on a simple scene graph in OCaml for
    OpenGL. To represent visual objects I use polymorphic variants.
    Algebraic types (Variants) in OCaml cannot be extended easily, however
    polymorphic variants do the job nicely.

    The only problem is look up is O(n) in the number of variants if you
    rely on a global rendering "dispatch" function. I assumed that was too
    much of a hit, so each node carries the render function it needs with
    it. This isn't a big space hit as it may sound, because it ends up just
    as aliases to the same functions.

    If I knew how to hash polymorphic variants generically, a table driven
    approach may work and be easily extensible (just add new render
    functions to the table) but am leaving that until later.

    Objects are used for the rendering context and serve a different purpose
    there.


    Chris
     
    chris, Jun 24, 2005
    #3
  4. alex goldman

    alex goldman Guest


    There are a few problems that I see in your post:

    1. We are not discussing functional vs imperative, but algebraic datatypes
    vs inheritance

    2. In the raytracer, "intersect" works on (ray, shape) pairs not (shape,
    shape), so the visitor pattern is irrelevant

    Regardless

    3. Some OOP systems don't need the visitor pattern, because they have
    http://en.wikipedia.org/wiki/Multiple_dispatch

    And also

    4. Abruptly changing "Subject:", while the subject remains the same, is not
    very helpful.

    5. The ray tracer was actively discussed lately in both clf and cljp - Jon
    started the discussion there himself. I'd like to hear what both
    communities have to say about this. Repeating the same arguments separatly
    in different groups is a waste of time. Don't trim the groups list.
     
    alex goldman, Jun 24, 2005
    #4
  5. First of all, I am sorry for my previous post which is off topic on cljp, of
    course I didn't notice the crosspost when replying (I will try to configure
    my newsreader a little better in order to notice crossposts in the future).

    In fact I never used the word "imperative" in my post.

    I am replying to your topic, which seemed to me: "object-oriented approaches
    vs. ADT approaches to problems that arise when writing graphics programs".
    I generalized a bit but used a rather imprecise word: "functional", I meant
    "ADT plus newer but still ADT-related techniques, like polymorphic
    variants, modules, functors, existential ADTs and so on".
    I tried to interpret your intentions and talk about object-oriented
    hierarchies and their equivalent in functional languages. I was wrong it
    seems, as you only want to talk about Jon raytracer - should I be sorry for
    having replied? If so, you should be sorry for having asked in the first
    I know, of course! I unintentionally stated that you _need_ the visitor
    pattern in OOP. But I guess I can state that using C#, C++, Java, Eiffel,
    the O of ocaml and other more or less "mainstream" OO languages, one will
    surely think about using the visitor pattern when in need of binary
    methods.
    Seems like you felt the change of subject as a critique of the one you
    used...

    I changed the subject on purpose, because I was introducing a rather
    interesting (at least, to me) subject which I thought be strictly related
    to your post (hence the reply) but not strictly related with the original
    subject (Jon's raytracer), so I changed the subject hoping that this would
    contribute to the signal-to-noise ratio of a possible search on usenet for
    the topic.

    I see that the subject has much more meaning for readers of cljp than for
    readers of clf due to previous discussions, but pardon me I was not aware
    of those, so I changed the subject as I am used to do when I think it's
    worth - and BTW I think discussing on usenet about what the subject of a
    certain post should be is even less helpful than changing a subject :)
    I actually didn't, so what has this to do with the "few problems" in my
    post? And also, I still think that my post was perfectly in topic with your
    on CLF, I don't see why you're upset with that.

    Again - sorry for this other off topic on both NGs - I think this post will
    clarify the previous one to everybody.

    V.
     
    Vincenzo Ciancia, Jun 24, 2005
    #5
  6. alex goldman

    Jon Harrop Guest

    Wow, I'm famous. ;-)
    Definitely not in my experience. Time for a shameless plug: The latest
    commercial product from my company, Presenta, is a slideshow presentation
    program designed to display technical content including animated slideshow
    points, typeset mathematics and 2D and 3D graphics:

    http://www.ffconsultancy.com/products/presenta

    Presenta is now written entirely in OCaml. Two years ago, it was written
    entirely in C++. The OCaml implementation makes very little use of objects
    (there is a single object type, for a "scene", which was done only to
    circumvent having mutually recursive modules).

    The internals are very complicated (much more complicated than anything I
    did during my PhD in computational physics, for example) and the OCaml
    implementation relies heavily upon variant types and pattern matching to
    get its jobs done. For example, variant types are used to represent:

    1. A whole document.
    2. Typeset mathematics.
    3. Graphics.
    4. The scene graph used for rendering.
    5. Lines and Bezier curves.
    6. Multiresolution paths.
    .... and many other entities.

    In the case of 2D vector graphics, the program uses a particularly
    sophisticated approach to adaptively tesselate geometry in order to render
    only what is necessary for the current frame of animation whilst maximally
    reusing the results of previous computations and also exploiting hardware
    acceleration via OpenGL. This is not easy. Indeed, nobody else has managed
    to do this AFAIK.

    Having translated this from an entirely OO C++ implementation I can
    definitely say that OO is very poorly suited to this application. OCaml's
    variants and pattern matching are not only vastly more succinct, they are
    also much clearer, much more robust and even much faster than the
    equivalent C++. Pattern matching leads to most code updates being localised
    where as OO leads to scattered updates which are not statically checked to
    the same extent by the compiler (C++ or Java).

    Finally, the advantages offered by OCaml don't just lead to 1/2 or 1/3 as
    much code, as my ray tracer might lead you to believe. The code density in
    the current implementation is more than 5x that of the old C++. For larger
    projects, OCaml code is even smaller in proportion. I believe this is due
    to the extra dimension of factoring made possible by higher-order
    functions.
     
    Jon Harrop, Jun 24, 2005
    #6
  7. alex goldman

    Jon Harrop Guest

    When learning a new paradigm, you should not try to translate old solutions
    but, rather, you should try to reimplement old problems. So don't ask what
    the "visitor pattern" looks like in a functional implementation. Find a
    representative example which has been solved using the visitor pattern.
    Forget about the visitor pattern. Then try to solve the same problem in ML.
    type shape = Circle of vec * float | Box of vec * vec
    Simply:

    let intersect s1 s2 = match s1, s2 with
    Circle (c1, r1), Circle (c2, r2) -> ...
    | Circle (c, r), Box (l, u)
    | Box (l, u), Circle (c, r) -> ...
    | Circle (c1, r1), Circle (c2, r2) -> ...
    There are two different ways to extend this problem:

    1. You could add a new shape.

    In ML, you do this:

    type shape =
    Circle of vec * float
    | Box of vec * vec
    | Polygon of vec list

    and the compiler will then tell you exactly where you have pattern matches
    which don't handle Polygon.

    In C++ or Java, you add a new derived class called Polygon:

    class Polygon : public Shape {
    ...
    }

    2. You could add a new function which acts upon shapes.

    In ML, you do this:

    let bound = function
    Circle of (c, r) -> ...
    | Box of (l, u) -> ...

    In C++ or Java, you add a new member function to shape:

    class Shape {
    ...
    virtual Bound bound() const = 0;
    }

    and implementations in every derived class:

    class Circle : public Shape {
    ...
    virtual Bound bound() const {
    ...
    }
    }

    In general, a program has far more functions than types. So the ML approach
    is better because code updates are localised when adding new functions
    (which is more common) than when adding new types (less common). The ML
    also has many other advantages. For example, you have to cut and paste the
    types a lot in C++ and Java but ML infers all of the types.

    Finally, MLs pattern matches are so much more expressive than derived
    classes in C++ and Java (e.g. you can pattern match over strings) that the
    compiler has a much better chance of optimising them. So ML programs are
    typically much faster too.
     
    Jon Harrop, Jun 24, 2005
    #7
  8. alex goldman

    alex goldman Guest

    Aha!

    In an objectless code, your Scene would be a big union of most or all
    renderable stuff. If it's an object instead, then everything that's
    renderable should be its subtype, no?
    My own experience was that simply rewriting an application significantly
    reduces its size, even when I rewrite it in the same language.
     
    alex goldman, Jun 25, 2005
    #8
  9. alex goldman

    Jon Harrop Guest

    No, sorry. :)

    I used an object to weaken the type system. Nothing to do with OO and/or
    subtyping.
    I have ported several applications from OCaml to C++ and the code expanded
    by the same amount, despite being rewritten.
     
    Jon Harrop, Jun 25, 2005
    #9
  10. alex goldman

    alex goldman Guest

    This is telling us something (about the type system), but not enough to have
    a meaningful discussion. Suppose you want to render

    Spheres, ellipsoids, cones, planes, parallelepipeds, prisms, etc.

    There are obviously complex RELATIONS among these, and you might want to
    re-use the code due to these relations instead of just cutting and pasting.

    What would your scene _object_ look like?

    type aux = Sphere of sphere | Ell of ell | Cone of cone | Plane of ...

    class scene = ?
     
    alex goldman, Jun 25, 2005
    #10
  11. alex goldman

    Jon Harrop Guest

    The OCaml type system is deliberately restrictive. Out of 10,000 lines of
    code in my latest project, this restrictiveness is advantageous (by
    eliminating many errors) in all but one place. In this place, I have use an
    object to weaken the type system just enough to let me do what I want.
    Absolutely. Then you factor your code into many functions. Code reuse is
    then achieved by calling one function from many places. For example, if
    you're after brevity, you might replace all sphere code with calls to
    ellipse.

    Your example is be best written in OCaml without using any OO at all.
    My scene _object_ looks nothing like that. It looks like this:

    class scene :
    ?fills:Smoke.Fill.t Store.t ->
    ?styles:Smoke.Style.geometry Store.t ->
    ?geometries:Smoke.ContourGeometry.t Store.t ->
    basic_node -> object ('a)
    method add_fill : Smoke.Fill.t -> Smoke.Fill.t Store.key * 'a
    method add_geometry : Smoke.ContourGeometry.t ->
    Smoke.ContourGeometry.t Store.key * 'a
    method add_style : Smoke.Style.geometry ->
    Smoke.Style.geometry Store.key * 'a
    method append : basic_node -> int * 'a
    method get_bound : Smoke.Bound.t
    method get_bound_of : basic_node -> Smoke.Bound.t
    method bound_of : iterator -> Smoke.Bound.t
    method get_fill : Smoke.Fill.t Store.key -> Smoke.Fill.t
    method get_fills : Smoke.Fill.t Store.t
    method get_geometry : Smoke.ContourGeometry.t Store.key ->
    Smoke.ContourGeometry.t
    method get_geometries : Smoke.ContourGeometry.t Store.t
    method get_root : basic_node
    method get_style : Smoke.Style.geometry Store.key ->
    Smoke.Style.geometry
    method get_styles : Smoke.Style.geometry Store.t
    method push_back : basic_node -> 'a
    method push_front : basic_node -> 'a
    method render : Smoke.RenderData.t -> unit
    method replace_fill : Smoke.Fill.t Store.key -> Smoke.Fill.t -> 'a
    method replace_geometry : Smoke.ContourGeometry.t Store.key ->
    Smoke.ContourGeometry.t -> 'a
    method replace_root : basic_node -> 'a
    method replace_style : Smoke.Style.geometry Store.key ->
    Smoke.Style.geometry -> 'a
    end

    It has nothing to do with shapes, geometries and so forth. It is only to do
    with the way I chose to structure the whole library. Specifically, it pulls
    everything together in a way that can then be used by all of the parts of
    my library independently, without having to know about each other. Thus, it
    evades a big mutual dependency.

    You want to talk about the variant type which implements a scene. I have
    chosen to use a variant type (much better than a class hierarchy):

    type ('leaf, 'loner, 'group) generic_node =
    GenericLeaf of 'leaf
    | GenericLoner of 'loner * ('leaf, 'loner, 'group) generic_node
    | GenericGroup of 'group * ('leaf, 'loner, 'group) generic_node list

    Note that it is both generic and extensible. The functions which act over
    this type are also both polymorphic and extensible. I have several levels
    of progressively more specialised scenes and functions, allowing the user
    to choose how much functionality they want to implement themselves.

    This functionality can actually be achieved (albeit unsafely) in C++ and
    Java but the code required is so convoluted that nobody would ever think to
    write it. In OCaml, the best approach is often the most natural and mose
    concise.
     
    Jon Harrop, Jun 25, 2005
    #11
  12. alex goldman

    alex goldman Guest

    okay, but what if you were using just ML (you actually mentioned earlier you
    were thinking about porting your book and code to SML). Suppose your code
    was in SML from the beginning, nearly 10,000 lines of it. At one point, you
    realize that the type system will not allow you to do what you want - your
    type checker God tells you to get lost. This is the kind of situation I've
    been in with ML (the memories are too painful, and I'm supressing them, so
    don't ask, I don't really want to talk about that ;-)
    I guess I asked the wrong question. What I really wanted to know was what
    its relation to spheres, ellipsoids, cones, planes, parallelepipeds,
    prisms, etc. looks like.

    INRIA folks have a paper about Objects vs not Objects (Modules?). IIRC, the
    basic idea is that objects are good when you have few function, but many
    data types. What I'm saying is that ray tracing seems just like this type
    of application (unless you limit yourself to spheres). There is a couple of
    functions (intersect and ?), but very many data types.

    So when you use an OO design, the code differences between *Objective* Caml
    on the one hand, and Java or C++ on the other hand, will be rather
    superficial.
     
    alex goldman, Jun 25, 2005
    #12
  13. Multiple dispatch just shifts the problems to a different area.

    I.e. if programmer A add a new ray type and programmer B adds a new
    shape type, they can't do that independently. It's just the same mess as
    with the visitor pattern.

    Regards,
    Jo
     
    Joachim Durchholz, Jun 25, 2005
    #13
  14. Why not? It's just a plain recursive function :)
     
    Philippa Cowderoy, Jun 25, 2005
    #14
  15. That should be simple. The visitor pattern is just a hack for
    languages that doesn't have first class functions - a tuple of
    functions implemented as an object. :)

    /L
     
    Lasse Reichstein Nielsen, Jun 25, 2005
    #15
  16. [Delayed but repeated Followup-To; I don't read comp.lang.java.programmer]

    Not quite, a tuple of functions is still a translation of a solution
    rather than the problem.

    It's a hack for extensible classes, i.e. for extending the set of
    functions whose implementation is dispatched at runtime on the type
    of one of arguments.

    It can be used to emulate algebraic types for example (subclasses are
    used for constructors, dispatch is used instead of pattern matching).
    This can be quite inconvenient:
    1. only one layer of constructors is dispatched at a time,
    2. you can't have a default case - you have to specify what to do for
    all constructors separately,
    3. and the body of each match must be moved to a separate method, with
    all local variables passed explicitly to it.

    In addition
    4. it requires a fixed signature of the function, so passing
    additional arguments and returning results is tricky (requires
    packing multiple arguments in "tuples", which Java lacks anyway,
    and casting to overcome static type system).
    5. In Java it makes static exception specifications harmful: a single
    exception specification must be used for all functions dispatched
    that way.
    6. It removes the other axis of extensibility, the one which was easy
    in plain OOP: adding new types to dispatch on.

    Generic functions (like in CLOS and Dylan) solve the problem of adding
    dispatched functions without most of these drawbacks (only 1 and 3
    remain), and as a bonus they provide dispatching on multiple arguments
    at once.
     
    Marcin 'Qrczak' Kowalczyk, Jun 25, 2005
    #16
  17. What do you mean? You can force the visitor implementor to implement a
    default method that can be called with types of shapes.
    No, multiple dispatch has a number of advantages over the visitor
    pattern. See this page for more info:
    http://nice.sourceforge.net/visitor.html

    /Jesper Nordenberg
     
    Jesper Nordenberg, Jun 25, 2005
    #17
  18. That's one of the ways people try to address the problem.

    The base problem is: you have N ray types and M shape types. With any
    kind of multiple dispatch (be it the Visitor pattern or built right into
    the language), that's a matrix of NxM functions (of course, in practice,
    that matrix is filled with relatively few values).

    Now if both programmers add a new type, you have an (N+1)x(M+1) matrix.
    And it's the [N+1][M+1] corner case that gives us all the trouble:
    neither the programmer who's responsible for the N axis nor the
    programmer who's responsible for the M axis will feel responsible for
    that case - in fact neither knows that this new case exists! And if the
    software has an unknown case, there will be nobody who reviews whether
    it's handled correctly.
    Even worse: adding a new type is an important design change, so it's
    quite likely that this new combined case is nontrivially different from
    anything that exists.

    Forcing a default just covers the problem up by making the system
    compile. What's actually needed is the exact opposite: a compiler
    message that informs whoever uses the two extensions together that
    there's a new, unimplemented case in his system.

    Needless to say that this plays havoc with composability: adding two
    independent extensions to the system may break it. In other words,
    multiple dispatch breaks modularity (the ability to compose independent
    libraries without getting adverse interactions).
    For the Javaites among the readers: It also prevents dynamic class
    loading. Well, one could defer the error message until the
    not-provided-for type combination actually turns up and throw an
    exception. You'd get multiple dispatch at the price of slightly
    destabilising the software... which is actually feasible with the right
    overall architecture; see the whitepapers on system stability in Erlang.
    OK, I agree MD solves several problems of Visitor.
    It doesn't solve the non-modularity problem though. And I don't think
    that this is solvable; whatever structure you impose, it will lead to
    unexpected results (read: bug opportunities) in some cases.

    The best way to handle the problem is to decompose the operation on NxM
    types into two: one Nx1, and one 1xM, where the composition will always
    do the right thing, without either Visitor or MD. Unfortunately, it
    seems that this strategy doesn't always work (but I'm not sure that this
    is a fundamental problem - it might be lack of inventiveness that makes
    us fail to see how to decompose NxM operations).

    Regards,
    Jo
     
    Joachim Durchholz, Jun 25, 2005
    #18
  19. Perhaps, but it's not going to go to Nx1 and 1xM - sooner or later that
    amounts to assuming the problem's bilinear. Other structures no doubt
    exist - I'm having some fun exploring extensible parsing for a wiki,
    though that has the advantage of an easy fallback case ("it's not markup,
    so it must be plain text").
     
    Philippa Cowderoy, Jun 26, 2005
    #19
  20. Forcing a default handler is the only solution I can think of in a
    language that supports dynamic class loading. You then have the option
    of throwing an exception in the default handler if you can't/won't
    handle the sub type.
    In some cases having a default handler and special handling of a few
    sub types is what the developer wants. In other cases you want special
    handling of all sub types, but as you note this is impossible to check
    at compile time on platforms that support dynamic class loading
    (unless, like in the visitor pattern, the programmer is forced to
    provide a list of supported sub types for multiple dispatch). Compiler
    support for multiple dispatch could actually give you the option of
    checking that all sub types available at compile time are handled in
    separate methods, which would give some protection against the bugs
    you mention.

    /Jesper Nordenberg
     
    Jesper Nordenberg, Jun 26, 2005
    #20
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.