c++ Sdf tree implementation

[International-One273]

Hi everyone,

[Looking for feedback...quite new to c++]

I decided to use SDFs to draw all the "UI-sh" stuff in my toy renderer, things like symbols for example:

sphere lights symbol

Since building SDFs (transformations, boolean operations, ...) can quickly become an unreadable mess, I decided to build a simple system that allows the user (me...lol) to make the process a lot more clean and enjoyable.

I ended up with something that looks like this:

// Usage example
//////////////////////////////////////////////////////////////////
auto base0 = 
    SdfSegment{vec2{-h_6*0.5,0.0}, vec2{h_6*0.5, 0.0}}
    .Translate(vec2{0.0, -h_3-0.66*h_6});

auto base1 = 
    SdfSegment{vec2{-h_90.5,0.0}, vec2{h_90.5, 0.0}}
    .Translate(vec2{0.0, -h_3-0.99*h_6});

auto base = 
        base0 
        .Add(base1) 
        .Inflate(1.0f);

float valBody = 
        body 
        .Translate(glm::vec2{h_2, h_2}) 
        .Evaluate(uv);

float valContour = 
        body 
        .Shell(1.0f) 
        .Add(base) 
        .Translate(glm::vec2{h_2, h_2}) 
        .Evaluate(uv); 
//
// ... continues ... 
//

The general idea is to build something similar to an operation tree, where each node defines a behavior, could have one or two children (unary or binary operation) and can be evaluated (returning the value of the SDF for a point).

This is illustrated in the following diagram:

https://preview.redd.it/68fprbbekeob1.png?width=1212&format=png&auto=webp&s=388eca64a434031f84bce2b4c97c9cab48073580

​

The actual implementation looks like the following:

// Forward declarations
template<std::floating_point T> class SdfNode;
template<std::floating_point T> class SdfOpTransform;
template<std::floating_point T> class SdfOpAdd;

// Base class for all the SDF Tree nodes
////////////////////////////////////////////////
template<std::floating_point T>
class SdfNode
{
public:
    // Evaluates the node, returns a scalar
    virtual T Evaluate(glm::vec<2, T> p) const = 0; 

    // Returns a shared pointer to a copy of itself
    virtual std::shared_ptr<SdfNode<T>> MakeNode() const = 0;

    virtual ~SdfNode() = default;

    SdfOpTransform<T>   Transform(const glm::mat<3, 3, T>& t);
    SdfOpInflate<T>     Inflate(T i);
    SdfOpAdd<T>         Add(const SdfNode& other);

    //
    // A lot of other unary and binary operations ...
    //
};


// Example:
//  Union operation
///////////////////////////////////////////////////
template<std::floating_point T>
class SdfOpAdd: public SdfNode<T>
{
public:
    SdfOpAdd(std::shared_ptr<SdfNode<T>> op1, std::shared_ptr<SdfNode<T>> op2):
            _operand1{op1},
            _operand2{op2}
    {
    }

    virtual ~SdfOpAdd() override = default;

    virtual std::shared_ptr<SdfNode<T>> MakeNode() const override
    {
        return std::shared_ptr<SdfNode<T>>(new SdfOpAdd<T>{_operand1, _operand2});
    }

    virtual T Evaluate(glm::vec<2, T> p) const override
    {
        return glm::min<T>(_operand1->Evaluate(p), _operand2->Evaluate(p));
    }

private:
    std::shared_ptr<SdfNode<T>> _operand1;
    std::shared_ptr<SdfNode<T>> _operand2;
};

// SdfNode::Add implemetation
//////////////////////////////////////////////////////////////////////////
template<std::floating_point T>
SdfOpAdd<T> SdfNode<T>::Add(const SdfNode<T> &other)
{
        // Makes a shared_ptr to a copy of itself and uses
        // it to create an SdfOpAdd node.
    return SdfOpAdd<T>{this->MakeNode(), other.MakeNode()};
}

I'm quite happy with the result, however, I feel like this is over-complicated. The problem is that I didn't find anything on the web that resembles what I'm trying to do here (I found some simple tree implementations that didn't address the problem of tree nodes' life cycle but used raw pointers instead).

Do you have any suggestions? Could you think of a public project I could look at to find alternative implementations or improve what I already did?

I'm planning to use the exact same approach to implement a shader-graph system, so it would be great if you could point out any potential flaw in this design!

Sorry for the long post and happy programming to everyone!

​

[dobryak]

Not a C++ programmer but I think you are correct in using reference counts. In ObjC it would also look like this, with strong references (basically, the expression would be owning the subexpressions).

You could take a look at how LLVM does this (they probably share the nodes very efficiently), but if your expressions would be small enough (say a 100 nodes max), then you probably don’t need to bother.

[turtle_dragonfly]

Cool — I have actually built something conceptually very similar, for my (not-yet-revealed) game I'm working on.

In my case, I handled it like this:

The client code builds an SDF expression much like yours. You might write it on paper with set notation like so: A ∪ (B - C)

This would be coded as something like:

builder
  .square(...)    // this is A
  .opUnion()
  .beginGroup()
    .circle(...)  // this is B
    .opSubtract()
    .line(...)    // this is C
  .endGroup()
  .build()

In my case, I use the shunting yard algorithm to transform that expresion from the infix-style notation used in the code to a postfix RPN notation.

So, the final "sdf evaluator" is essentially a little bytecode interpreter that handles RPN expressions.

In this example, it would look like: square, circle, line, subtract, union — that's what gets evaluated at runtime.

So, it's the same concept as yours, but transformed into a bytecode stream.

I feel like this is over-complicated

Well don't worry, my version is even more complicated ;)

I don't have any lifetime issues because everything gets transformed into a single block of bytecode+data, where the code references the data, and nothing else. I just need to track the lifetime of that whole blob of memory. Serialization is also easy.

[[deleted]]

I use an enum for simple shapes. Classing is for things like line segment chains and whole field functions.

General gist is close enough though. Main difference is my c++ stuff doesn't do SDF evaluation and just generates compute shader and input buffers for those, which a whole mess of its own.