Build efficient code from scene description (tree of 3d objects and transformations)

Hello,

i am currently trying to implement a Sphere-Tracing renderer. This is my first Julia project. So i lack on certain aspects like meta programming which is where i need your input.
It uses a cool concept called Signed distance functions. The idea is that you describe the world implicitly by a function which gives the shortest to any object (and if it is inside the -1* the shortest distance to the wall of the object).
My current problem is to find an efficient way to “compile” down a tree of 3d objects to a signed distance function that describes the whole world (or way to compose partials).
I like to give an overview of my attempts so far first. The source code is inline

  • Hand coding This is a circle of radius 50 centered at point (1,1,1)
function scene(Pos::SVector{3}) 
  norm(Pos-SVector{3,Float64}(1.0,1.0,1.0))-50.0
end

Full source of minimal example

  • Functions of functions
function scene_ff(Pos)  
   union(trans(sphere(3.0,spot(SVector{3,Float64}(0,0,0),1.5,Red)),SVector{3,Float64}(0,20,0)),
         plane(SVector{3,Float64}(0.0,0.0,1.0),checkerbox(10,Grey,Black)))(Pos)
end

where i divide in to Sdf and shaders

##Call signature of a shader
(Pos::SVector{3},Normal::SVector{3},Sdf,Step,Inital) -> x::RGB 

## Call signature of a Sdf, rand is necessary hack, please ignore.
(Pos::SVector{3}) -> (distance to Sdf,rand(),Shader of that Sdf) 

which are anonymous functions built by code like:

function union(SDFs...)
   return (Pos::SVector{3}) -> minimum(map(x->x(Pos),SDFs))
end

function trans(Sdf,Vec)
  return (Pos::SVector{3})->(Sdf(Pos-Vec))
end

function plane(Normal::SVector{3},Shader)
  return (Pos::SVector{3}) -> (dot(Pos,Normal),rand(),Shader)
end

function sphere(Radius::Float64,Shader)
  a = rand() #Needed for strict ordering since my lambdas/shaders can't be compared
  return (Pos::SVector{3}) -> return (norm(Pos)-Radius,a,Shader)
end

function unicolor(Color::RGB)
  return (Pos,Normal,Sdf,Step,Inital)->Color
end

function checkerbox(BSize,Shader1,Shader2)
  return (Pos::SVector{3},Normal::SVector{3},Sdf,Step,Inital) -> if xor(mod(Pos[1],2*BSize)>BSize,mod(Pos[2],2*BSize)>BSize,mod(Pos[3],2*BSize)>BSize)   Shader1(Pos,Normal,Sdf,Step,Inital) else Shader2(Pos,Normal,Sdf,Step,Inital) end
end

...

const Red   = unicolor(RGB{Normed{UInt8,8}}(0.8,0.0,0.0))

This approach results in lot’s of allocations and does not lend itself to GPU’s which is my long term goal. But is really flexible
Full source with same scene ToO approach

  • Tree of Objects parsed each time.
const scene = Conjun([
   Transl(SVector{3,Float64}(0,20,0),Sphere(3.0,Spot(SVector{3,Float64}(0,0,0),1.5,Red))), 
   Plane(SVector(0.0,0.0,1.0),Checkbox(10,Grey,Black))
])

with Sdfs working in this manner:

struct Conjun <: Sdf
  Coll::Array{Sdf, 1}
end

function dist(Sdf::Conjun, Position::SVector{3,Float64})
  min(map(x->dist(x,Position),Sdf.Coll)...)
end

function closest(Sdf::Conjun, Position::SVector{3,Float64})
  closest(Sdf.Coll[argmin(map(x->dist(x,Position),Sdf.Coll))],Position)
end

struct Transl <: Sdf
  Off::SVector{3,Float64}
  Vict::Sdf
end

function dist(Sdf::Transl, Position::SVector{3,Float64})
  dist(Sdf.Vict,Position-Sdf.Off)
end

function closest(Sdf::Transl, Position::SVector{3,Float64})
  closest(Sdf.Vict,Position-Sdf.Off)
end

abstract type SSdf <: Sdf end

struct Sphere <: SSdf
   Radius::Float64
   Shadr::Shader
end

function dist(Sph::Sphere, Position::SVector{3,Float64})
   norm(Position)-Sph.Radius
end

function color(Sph::Sphere, Ri::RayInfo)
  shade(Sph.Shadr,Ri)
end

And shader this way:

struct ConstantShader <: Shader
  Color::RGB
end

function shade(Shadr::ConstantShader,Ri::RayInfo)
  Shadr.Color
end

struct Spot <: Shader
  lightPos::SVector{3,Float64}
  brightness::Float64
  Shd1::Shader
end

function shade(Shadr::Spot,Ri::RayInfo)
  shade(Shadr.Shd1,Ri)*min(1,max(0.1,Shadr.brightness*dot(gradient(Ri.tSdf,Ri),normalize(Shadr.lightPos-Ri.Position))))
end

As you see many objects contain references to abstract types. This makes it even slower (although) less allocation heavy than the function of functions approach. It will not work well for GPUs either.

Full source same scene as fof
Problem:
Find a way to compile a scene graph down to a representation with three properties:

  1. It has a signed distance functino which gives you the scene you want (that’s easy) Learn why
  2. It has to tell my which shader to use for which object (this is where the hard coding approach failed badly)
  3. It has to be able to run on GPU

My idea is to built a tree description (from “Objects”) and have it compile down to look up tables and functions. Since that probably works good on GPU. But i am open for better ideas.
The scene after compilation would something like this:

struct Scene
  Objects::SVector  ## Function of the sdf of the different objects in absolute coordinates
  Shaders::SVector  ## Shaders[n_id] belongs to Objects[n_id]
  mapID::Function   ## Gives the id of most appropiate shader at position
  mapObjc::Function ## Gives the id of the closest object from position
  function Scene(Tree::Sdf)
     #magic happens here
  end
end
function dist (S:Scene,Pos)
## Maybe optimizations which not to look at but most likely min of all sfds
end
function color (S:Scene, Pos)::RGB
## does call shader, gives normal in respect to the closest Object and not the total SDF

This approach has several problems too:

  • Can’t run on GPU since mapID functions make scene non isbits (maybe fatal for this approach)
  • Needs magic/macros which converts an SDF tree in to a group of functions and look up tables
  • I do not know how Julia macros work really

I would really appreciate your help/input/ideas.
Sincerely,
freemint

I can’t claim to understand your purpose fully, but from a quick skim one obvious problem is as you say - attaching functions to an a struct means they are not isbits types. But this style isn’t necessary. Instead the mapID and mapObj fieldsd should hold structs representing the method options, like:

struct Plane end
struct Radius end

or whatever you are doing (to nitpick - julia fields and arguments use snake case by convention. Camel case everywhere makes your code hard to understand at a glance, so I don’t really get it!).

Then dispatch on these types using methods of a common function like map_id(::Plane, data) or whatever. Then your struct is all isbits and GPU friendly, and your data is separated from your methods.

A second obvious problem is: you don’t need to reference abstract types in structs, use parametric types instead:

struct Spot{S} <: Shader
  lightPos::SVector{3,Float64}
  brightness::Float64
  shd1::S
end

With type parmeter S instead of Shader. That will compile for a GPU.

I’m also not sure why you need macros. Do as much as you can with structs and multiple dispatch first.

Edit: Ok so you are walking a arbitrary tree of objects. My https://github.com/rafaqz/Flatten.jl package might be interesting for a high performance method of working with arbitrarily nested types using @generated functions (and there are a bunch more unregistered packages of mine that also do this) but only if you can do what you need with normal julia code. It produces great native instructrions but recursive AST generation is hard to think about, so try to avoid @generated functions if you can.

1 Like

@Raf I attempted to implement your guidance here

and came across two problems:

const scene = Conjun((
   Transl(SVector{3,Nm}(0,20,0),Sphere(Nm(3.0),Spot(SVector{3,Nm}(0,0,0),Nm(1.5),Red))),
   Transl(SVector{3,Nm}(12,9,-4),Sphere(Nm(12.0),Spot(SVector{3,Nm}(0,0,0),Nm(1.8),Blue))),
   Transl(SVector{3,Nm}(3,-13,0),Sphere(Nm(9.0),Spot(SVector{3,Nm}(0,0,0),Nm(1.0),Green))),
   Sphere(Nm(1.0),White),
   Transl(SVector{3,Nm}(-20,0,0),Sphere(Nm(0.5),White)),
   Transl(SVector{3,Nm}(-18,0,0),Sphere(Nm(1.0),Red)),
   Plane(SVector{3,Nm}(0.0,0.0,1.0),Checkbox(Nm(10),Grey,Black))
))
  • I did not find a representation of scene that is isbits.

That means that RayInfo is not isbits either.
Also if i enable parametric typing the slot scene goes into the codes gets slower and allocates more.

12.352 s (173535725 allocations: 4.96 GiB) with RayInfo not parametric
14.537 s (213811941 allocations: 7.19 GiB) with Sdf parametric in RayInfo

  • The implementation using structs with parametric typing is significantly slower than the functions of functions approach (x2-3).
    This i think because the scene “tree” is interpreted every time this happens roughly 5234162 times for an 800x800 image.

My long term goal is to compile a scene tree down to an explicit functions which does not allocation similar to my “hard coded” solution in my first post.

The resulting image is currently different due to a bug in spot shader i could no trace down yet. (It has to do that the point from where i light the sphere now moves with the translation)

Is that actually type stable? Are you using @code_warntype? If either the structs or parametric types are slower you are doing something wrong. They will both be compiled away unless you have type instability, and for a GPU parametric types are not optional, you need isbits. Read the performance section of the manual: https://docs.julialang.org/en/v1/manual/performance-tips/index.html.

This might be your type stability problem, tuple could be anything:

struct Conjun <: Sdf
  coll::Tuple
end

So don’t finish profiling until you have clean @code_warntype.

Also as I said already, if you want help you should use snake-case for variables and field names, I can’t read your code fast enough to be worth the effort. Proper spaces after commas and math etc also help other people read your code.

1 Like

@Raf
This is exactly my problem, i have now idea how to make Conjun isbits since it is a collection of N structs of different types. This is what i meant with:

This problem seems inherent to the tree of structures approach and i am unconvinced that i want to perform this “interpret”/“walk” the scene tree on GPU.
Which is why i proposed a structure for a loop-up-table + functions (which has his own problems).
I start to think that i might want to interpret that scene tree as a single type and have a really complicated @generated function which compiles the tree down into a more compute friendly structure with no pointer chasing. But for that i would need to know how to express such a tree of types as parametric type.

The reason i went with Tuple here is that Tuples seemed to behave better when confronted with mixed types than Arrays.

julia> typeof([3,:k])
Array{Any,1}

julia> typeof((3,:k))
Tuple{Int64,Symbol}

But the problem seems to by that maybe the tuples type can be statically inferred but not my Conjun is does not store the type information. I made up some syntax to describe what i think i need:

struct Conjun{T...} 
         coll::Tuple{T}
end

The type of a Tuple being a collection of types, i want to attach the collection of types as parametric type to Conjun but i think this question is best addressed in a new topic.

It turned out i had an type instability when it was fixed when i made the “use this type” Nm(0.001) constant.

Regarding coding conventions. I found the Style Guide useless in that regard. Is there a established coding convention if so where can i learn about it?
Correction: It contains the relevant section here.

Edit: No new code since i am waiting for the conventions how to code so people might actually want to read your code.

This is all you need:

struct Conjun{T} 
         coll::T
end

There is no reason to force it to be a tuple.

In that style guide, arguments and variables are lowercase with underscores when you really need them. ie snake_case. Just like I keep saying. Please read my suggestions, you are making this unnecessarily difficult when I’m putting time into trying to help you. Specifically this bit:

modules and type names use capitalization and camel case: module SparseArrays, struct UnitRange.
functions are lowercase (maximum, convert) and, when readable, with multiple words squashed together (isequal, haskey). When necessary, use underscores as word separators. Underscores are also used to indicate a combination of concepts (remotecall_fetch as a more efficient implementation of fetch(remotecall(…))) or as modifiers.
conciseness is valued, but avoid abbreviation (indexin rather than indxin) as it becomes difficult to remember whether and how particular words are abbreviated.

2 Likes

Way to go!
5.038 s (134868061 allocations: 3.14 GiB) -> 334.679 ms (3097713 allocations: 372.62 MiB)

I find that kind of unfair but that is life. Since i try to follow your suggestions and i appreciate your patience with me.
It is my first project.

Great glad it works.

You were pretty negative about the style guide when it has everything you need for the problem at hand! It hard to help when you reject the best suggestion, and I’m really meant to be working on something else right now, so just saying, next time read more, argue less :slight_smile:

1 Like

I was pretty negative about the Style guide since i did overlook the relevant section. I am sorry. I was a bit rushed in this reply. It indeed contains your recommendations

But i will attempt to use the JuMP conventions from now on since they are more explicit.

1 Like

One of the reasons I created Grassmann.jl is to provide a unified language for geometric algebra in the Julia type system.

julia> using Grassmann; @basis ℝ^3
(⟨+++⟩, v, v₁, v₂, v₃, v₁₂, v₁₃, v₂₃, v₁₂₃)

julia> v1,v2,v3 # vector basis
(v₁, v₂, v₃)

julia> v12,v13,v23 # hyperplane basis
(v₁₂, v₁₃, v₂₃)

Geometric algebra provides a unified language for representing points, lines, planes, spheres, conics, transformations, rotations, and so on, in both affine and projective geometry. The package uses StaticArrays and VectorSpace bits-types to preallocate the Grassmann number types…

It’s a work in progress intended for geometry processing.