Replies: 14 comments 28 replies
-
|
@gsohler in case you have any opinion about this. I don't have much idea about sdf. |
Beta Was this translation helpful? Give feedback.
-
|
So,
Regarding |
Beta Was this translation helpful? Give feedback.
-
|
There is a discussion about mesh quality here: libfive/libfive#284 |
Beta Was this translation helpful? Give feedback.
-
|
Honestly, until we have a bunch of users of SDF complaining about our speed, I'd prefer to have a small, simple code base. Speed is great, but robustness is much more important, and big part of that is code clarity and simplicity. I think your other parallelization ideas sound simpler than trying to figure out a distance bound. |
Beta Was this translation helpful? Give feedback.
-
|
Indeed, I think the simple stuff can get us pretty far away. The major problem is how to get more users, OpenSCAD SDF integration is still in its early stages, and it feels like most people are not using curv/libfive, maybe sdf is a bit too complicated for normal users. |
Beta Was this translation helpful? Give feedback.
-
|
is curv still actively developed? I was following it on discord, and it went silent some time ago. And it was far from complete at that time. |
Beta Was this translation helpful? Give feedback.
-
|
I wish to know as well, I feel like I am navigating abandoned cities when I check various sdf projects: Nice claims, seems working well and quite a lot of stars, but somehow there is not much recent activities and no one is talking about them. |
Beta Was this translation helpful? Give feedback.
-
|
Hi Emmett, i pass whatever distance function to libfive the user provides.
libfive can handle both proper distance functions and just values with a
sign, but proper distance values work better.
Yes, i know curv and i used it a lot in the past and its very good at
evaluating SDF's
However, My vision is to have a tool which can handle SDF and BREP objects
in the same language/program.
This is why i have taken the effort to use libfive in openscad.
Now having the power of python i can even generate SDF equations or CSG
trees programmatically. I am sure there will arise applications for that.
Some time back I learned about the marching cubes algorithm and its a
perfect fit for evaluating SDF's. its bullet proof and very usable for
parallelism.
However, on the other hand it runs in O(n^3) , it sounds like shooting
birds with cannons which is not good enough for me.
My Vision is to establish an Algorithm to evaluate SDF's in O(n^2) only. My
vision is that I enclose the object with a big cube first. Then I
iteratively add points to the mesh and attach them to the object surface
similar like vacuum deep drawing process of plastic parts(mainly packaging).
I am aware that there are many problems with will arise(like separate
objects or holes inside objects) i hope that i find the right algorithm for
that soon)
…On Thu, Sep 21, 2023 at 5:39 PM Emmett Lalish ***@***.***> wrote:
So, 1 assumes you have a proper distance function (rather than just
something that changes sign), which is assuming a lot for an SDF. It would
disallow too many nice functions, including my heart example, I'm pretty
sure.
3 sounds cool, but how complex would it be? Also, if curv already does
such a good job, why not just use it? Does it not guarantee manifoldness (a
common marching cubes problem)?
Regarding 2, 4, and 5, I trust your judgement when it comes to speed.
Certainly SDF is a highly parallelizable problem. I'm also not sure which
approach is faster: evaluating the SDF values twice (once to set up the
data structures, and again to fill in their values), or just once like I do
now where you have to find a way to index into a disorganized array (hence
the hash table).
—
Reply to this email directly, view it on GitHub
<#561 (comment)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/ACCO4MTF2KW4GEEBU7QPHU3X3RNTTANCNFSM6AAAAAA5BXFX7I>
.
You are receiving this because you were mentioned.Message ID:
***@***.***>
|
Beta Was this translation helpful? Give feedback.
-
|
If your grid is d*d*d, you can have a mesh with O(d^3) vertices, e.g. gyroid. I don't think you can find an algorithm that can correctly handle these cases and have a worse case complexity better than O(d^3). Of cause usually users give us better sdfs, so there should be algorithms that are usually faster. |
Beta Was this translation helpful? Give feedback.
-
|
Agreed. Also, the output in number of triangles is worst-case O(d^3), and commonly O(d^2). I like to think of the number of triangles as n, so really we're talking about O(n^(3/2)) vs O(n) for some common cases. That makes me feel like it's not so ridiculous, especially if it's well-parallelized. And I think the reliability is very much worthwhile, as the vacuum drawing approach sounds very difficult to guarantee. |
Beta Was this translation helpful? Give feedback.
-
|
Also, I'd say for this, memory scaling is a bigger problem than compute scaling. Our current algorithm is O(d^3) in compute, but only O(n) in memory. |
Beta Was this translation helpful? Give feedback.
-
|
Hi Emmett,
I am excited to read, that processing time goes commonly to O(d^2) and i
dont understand why this is achieved.
in marching cube algorithm you really have to march all cubes to find out
where is actually void. this results in O(d^3)
where is the hidden shortcut ?
…On Thu, Sep 21, 2023 at 8:26 PM Emmett Lalish ***@***.***> wrote:
Agreed. Also, the output in number of triangles is worst-case O(d^3), and
commonly O(d^2). I like to think of the number of triangles as n, so really
we're talking about O(n^(3/2)) vs O(n) for some common cases. That makes me
feel like it's not *so* ridiculous, especially if it's well-parallelized.
And I think the reliability is very much worthwhile, as the vacuum drawing
approach sounds very difficult to guarantee.
—
Reply to this email directly, view it on GitHub
<#561 (reply in thread)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/ACCO4MSIQV6N7CJHOOILDK3X3SBFZANCNFSM6AAAAAA5BXFX7I>
.
You are receiving this because you were mentioned.Message ID:
***@***.***>
|
Beta Was this translation helpful? Give feedback.
-
|
I think you misread what I said - can you quote the part you're referring to? |
Beta Was this translation helpful? Give feedback.
-
|
Hi Emmett, yes you are right
you stated:
"Agreed. Also, the output in number of triangles is worst-case O(d^3), and
commonly O(d^2). "
correct, but I fear you need to find out in O(d^3) time that the amount of
triangles is O(d^2)
if you know of any O(d^2) algorithm, even if they probably cannot handle
things like gyroids, I'd like to learn about them ...
Guenther
…On Thu, Sep 21, 2023 at 9:09 PM Emmett Lalish ***@***.***> wrote:
I think you misread what I said - can you quote the part you're referring
to?
—
Reply to this email directly, view it on GitHub
<#561 (reply in thread)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/ACCO4MXD2WWISE62GMS5W6LX3SGFRANCNFSM6AAAAAA5BXFX7I>
.
You are receiving this because you were mentioned.Message ID:
***@***.***>
|
Beta Was this translation helpful? Give feedback.
-
|
I managed to reduce the number of atomic operations required, thus minimizing contention and improved the performance of sdf quite a bit. (about 30% improvement in some cases? the code is quite ugly so I am not posting now) However, I found that importing meshes into manifold is pretty slow. For example, when I use size = 60 for GyroidModule (default is 20), ~30% of the time is spent on evaluating sdf, and the remaining 70% is spent on converting Mesh into Manifold. In particular, SplitPinchedVerts and CreateFaces (finding the connected component + other per face operations) took the majority of time in single threaded mode and cannot be parallelized. This is probably a general enough problem that we should open a separate issue for, because it will also impact other mesh import. |
Beta Was this translation helpful? Give feedback.
-
|
In particular I should put this next to my monitor so I can see it whenever I think atomic is free:
|
Beta Was this translation helpful? Give feedback.
-
|
Nice! Yes, that doesn't surprise me too much - I didn't put that much effort into optimizing our constructor. I figured generally there would be more time spent on further operations than on the input, but if it's exceeding the SDF time, that's not great. I bet Connected components is definitely slow - I looked for quite a while for a decent parallel solution, but couldn't find anything for general graphs. The trouble is they mostly scale with the diameter of the graph, which for us is ~O(n^1/2), which is pretty bad. I wonder if we could create faces by hashing their normal vector and origin offset into precision-sized buckets? It would relate disconnected parts of the same plane, but I don't think that's a problem (that's what Boolean ops will do anyway). |
Beta Was this translation helpful? Give feedback.
-
|
Yeah I don't think we can speed up connected components a lot. We can perhaps open an issue to track performance work on constructor later. |
Beta Was this translation helpful? Give feedback.
-
|
I just had an idea: Why bother with Lipschitz constants when what we are caring is just whether or not the function can cross zero at some neighboring points? We can just do a interval value analysis. Say the original SDF is |
Beta Was this translation helpful? Give feedback.
-
|
Not sure if I get your idea. Of course we can shortcut marching Cube
algorithm by using intervals.but if sdf function is below zero in all 8
corners of the interval cube it does not mean that there is nothing
inside.we still might have missed a rising and a falling edge inside.not
sure if we can use intervals without being sure not to miss anything. If
your idea is different, please explain your idea for dummies 😅 I don't
understand these mathbb expressions unfortunately.
…On Tuesday, October 31, 2023, Chun Kit LAM ***@***.***> wrote:
I just had an idea: Why bother with Lipschitz constants when what we are
caring is just whether or not the function can cross zero at some
neighboring points? We can just do a interval value analysis. Say the
original SDF is $f: \mathbb{R}^3 \to \mathbb{R}$, we can reinterpret in
another domain to make it $f': \mathbb{R}^3 \times \mathbb{R}^3 \to
\mathbb{R}\times\mathbb{R}$, in the sense that the input is the bounding
box of the input space, and the result is the min and max (approximation)
of $f$ inside this input. Every operator is interpreted as interval
arithmetic. If the resulting interval does not contain 0, we will just skip
the whole bounding box. Supporting loops may be tricky because it involves
fixed-point calculation, we can just don't provide loop construct :)
—
Reply to this email directly, view it on GitHub
<#561 (comment)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/ACCO4MXYMNAVK4Q2VVRYLJLYCEAABAVCNFSM6AAAAAA5BXFX7KVHI2DSMVQWIX3LMV43SRDJONRXK43TNFXW4Q3PNVWWK3TUHM3TIMZVGY3TO>
.
You are receiving this because you were mentioned.Message ID:
***@***.***>
--
Null
|
Beta Was this translation helpful? Give feedback.
-
|
The interval overaproximates the set of values the function can take. If it crosses zero somewhere within a cube, the interval should include 0. |
Beta Was this translation helpful? Give feedback.
-
|
If you know a way to quickly bound an arbitrary function, then sure, but that sounds hard? Also, what do you mean by loops? |
Beta Was this translation helpful? Give feedback.
-
|
We don't need to bound arbitrary functions, we just need to bound those that are commonly used, like addition, multiplication, trigonometric functions. This is a common technique called abstract interpretation, I can write a demo later. By loops I mean if the sdf contains some for/while loops. These loops make abstract interpretation harder and slower, and it seems that they are rarely used in sdfs. |
Beta Was this translation helpful? Give feedback.
-
|
Just to understand your idea correctly:for your idea to work the equation
must be clearly visible. A hidden equation just providing values for given
inputs will not work, right?
…On Tue, Oct 31, 2023, 16:59 Chun Kit LAM ***@***.***> wrote:
The interval overaproximates the set of values the function can take. If
it crosses zero somewhere within a cube, the interval should include 0.
—
Reply to this email directly, view it on GitHub
<#561 (reply in thread)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/ACCO4MRLVW3K7XDNUSGQXS3YCEN4ZAVCNFSM6AAAAAA5BXFX7KVHI2DSMVQWIX3LMV43SRDJONRXK43TNFXW4Q3PNVWWK3TUHM3TIMZXGAZTS>
.
You are receiving this because you were mentioned.Message ID:
***@***.***>
|
Beta Was this translation helpful? Give feedback.
-
|
Yes. Let me give a 1D example: When this function is evaluated against |
Beta Was this translation helpful? Give feedback.
-
|
Yes I understand now. For 1d you basically do zero value analysis and it
can easily be done symbolically with the equation.
However if you do with 2d the zero values on x depend on the actual value
of y and it starts to be complicated very soon.can you help me to
understand for 2d ?
…On Tuesday, October 31, 2023, Chun Kit LAM ***@***.***> wrote:
Yes. Let me give a 1D example:
f(x) = sin(x) * x
When this function is evaluated against [pi/2, pi], the range of sin(x)
is [0, 1], and the range of x is [pi/2, pi], so the multiplication result
range is [0, pi].
—
Reply to this email directly, view it on GitHub
<#561 (reply in thread)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/ACCO4MTDZ75BZDBTY5VZ3YLYCEQ7HAVCNFSM6AAAAAA5BXFX7KVHI2DSMVQWIX3LMV43SRDJONRXK43TNFXW4Q3PNVWWK3TUHM3TIMZXGMYDC>
.
You are receiving this because you were mentioned.Message ID:
***@***.***>
--
Null
|
Beta Was this translation helpful? Give feedback.
-
|
No, we only work with the intervals without considering their relations, so 2D is similar. Just change the last x in the above example to y, the analysis just works. |
Beta Was this translation helpful? Give feedback.
-
|
Yes understood. Using Intervals you can reduce the sdf analysis outer
bounding box to the touching bound box of meshed object. This might be an
advantage of the size is the meshed object is not known bit usually you set
the size of the outer bounding box quite precise.
But the equation sub-term topic is interesting, I keep it in mind.
…On Tue, Oct 31, 2023, 18:09 Chun Kit LAM ***@***.***> wrote:
No, we only work with the intervals without considering their relations,
so 2D is similar. Just change the last x in the above example to y, the
analysis just works.
—
Reply to this email directly, view it on GitHub
<#561 (reply in thread)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/ACCO4MUA5BBD36YDHN4WLL3YCEWEFAVCNFSM6AAAAAA5BXFX7KVHI2DSMVQWIX3LMV43SRDJONRXK43TNFXW4Q3PNVWWK3TUHM3TIMZXG42TK>
.
You are receiving this because you were mentioned.Message ID:
***@***.***>
|
Beta Was this translation helpful? Give feedback.
-
|
No, setting the outer bounding box is actually not the main advantage of this. The most important thing is that we can skip a lot of evaluations by iteratively refine the search space, like an octree. If there are zero crossings in the current box, we divide the box into 8 and evaluate in parallel, until the boxes are small enough. It is hard to deduce the range of xyz, but given xyz we can usually get good interval of the output (for simple functions). |
Beta Was this translation helpful? Give feedback.
-
|
now i understand!
the equation is not evaluated for a single value, but always for intervals
and there are rules how to transfer the interval from the inputs to the
output.
if the interval spans over 0, it's split into 8 octants, if not, the
interval can be skipped.
So the O(n^3) can really almost turn into o(n^2) and the result will
initially look like
Minecraft items, but this can resolve after smoothening.
I believe this is what's actually implemented in libfive. Everything has
intervals there but I did not understand until now.
…On Tue, Oct 31, 2023 at 6:33 PM Chun Kit LAM ***@***.***> wrote:
No, setting the outer bounding box is actually not the main advantage of
this. The most important thing is that we can skip a lot of evaluations by
iteratively refine the search space, like an octree. If there are zero
crossings in the current box, we divide the box into 8 and evaluate in
parallel, until the boxes are small enough. It is hard to deduce the range
of xyz, but given xyz we can usually get good interval of the output (for
simple functions).
—
Reply to this email directly, view it on GitHub
<#561 (reply in thread)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/ACCO4MXXCQUGYKAIQEZCW4TYCEY7PAVCNFSM6AAAAAA5BXFX7KVHI2DSMVQWIX3LMV43SRDJONRXK43TNFXW4Q3PNVWWK3TUHM3TIMZXHE4TC>
.
You are receiving this because you were mentioned.Message ID:
***@***.***>
|
Beta Was this translation helpful? Give feedback.
-
|
In contrast to marching cubes, my SDF result (sphere here)
does not follow an orthogonal grid, but is amorph ...
[image: image.png]
On Tue, Oct 31, 2023 at 8:21 PM Guenther Sohler ***@***.***>
wrote:
… now i understand!
the equation is not evaluated for a single value, but always for intervals
and there are rules how to transfer the interval from the inputs to the
output.
if the interval spans over 0, it's split into 8 octants, if not, the
interval can be skipped.
So the O(n^3) can really almost turn into o(n^2) and the result will
initially look like
Minecraft items, but this can resolve after smoothening.
I believe this is what's actually implemented in libfive. Everything has
intervals there but I did not understand until now.
On Tue, Oct 31, 2023 at 6:33 PM Chun Kit LAM ***@***.***>
wrote:
> No, setting the outer bounding box is actually not the main advantage of
> this. The most important thing is that we can skip a lot of evaluations by
> iteratively refine the search space, like an octree. If there are zero
> crossings in the current box, we divide the box into 8 and evaluate in
> parallel, until the boxes are small enough. It is hard to deduce the range
> of xyz, but given xyz we can usually get good interval of the output (for
> simple functions).
>
> —
> Reply to this email directly, view it on GitHub
> <#561 (reply in thread)>,
> or unsubscribe
> <https://github.com/notifications/unsubscribe-auth/ACCO4MXXCQUGYKAIQEZCW4TYCEY7PAVCNFSM6AAAAAA5BXFX7KVHI2DSMVQWIX3LMV43SRDJONRXK43TNFXW4Q3PNVWWK3TUHM3TIMZXHE4TC>
> .
> You are receiving this because you were mentioned.Message ID:
> ***@***.***>
>
|
Beta Was this translation helpful? Give feedback.
-
|
we are unable to see your image, we can just see [image: image.png] |
Beta Was this translation helpful? Give feedback.
-
|
Sorry,
i have now published on imgpile
The picture is visible here:
https://imgpile.com/i/GUUJBg
…On Thu, Nov 2, 2023 at 7:50 AM Chun Kit LAM ***@***.***> wrote:
we are unable to see your image, we can just see [image: image.png]
—
Reply to this email directly, view it on GitHub
<#561 (reply in thread)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/ACCO4MXXUMKLKQKQDGW54VDYCM7CDAVCNFSM6AAAAAA5BXFX7KVHI2DSMVQWIX3LMV43SRDJONRXK43TNFXW4Q3PNVWWK3TUHM3TINJTGA3TS>
.
You are receiving this because you were mentioned.Message ID:
***@***.***>
|
Beta Was this translation helpful? Give feedback.
-
It seems that OpenSCAD folks are interested in adding SDF support (via libfive), so I was curious about our SDF performance comparing with libfive and curv (libfive + GPU). It turns out the speed of libfive is roughly similar to us, and curv is a lot faster. So I looked into the code a bit and was thinking if we can do something about the performance.
|sdf(p)| >= r, we skip evaluating points in a radius ofr. Probably not radius but something like an octree. This can probably reduce most of our queries.Beta Was this translation helpful? Give feedback.
All reactions