Discretization

[joeblew99]

Its slow which is to be expected.

Wondering if a Discretization routine can help ? https://en.wikipedia.org/wiki/Discretization

[deadsy]

On the one hand I do like that the SDFs lead themselves to modelling via the continuous equation rather than a piece-wise approximation. E.g. in openscad you have to tell it how many segments you want it to use in a circle/curve - it models things with polygon approximations. On the other hand trying to work out the SDF evaluation using the continuous equation can start to become a bit tedious for complicated things. I tried doing some newton-raphson solvers, and that works, except when it doesn't. Take a look at the bezier curve stuff. I just turned it into a polygon (I suppose that's a form of discretization) and did the SDF on that. That's a very general technique. My SDF evaluation for polygons is correct but is O(n). It should be possible to write a much faster evaluator for 2D polygons, I just haven't worked it out yet. It should also be possible to get speedups by caching evaluation results. E.g extrudes of 2D objects keep on evaluating the same points.

[joeblew99]

i will have a look at the bezier curves you mentioned.

O(n) is indeed nasty. I was planning to scale things out horizontally across the network to see how it works out in terms of data parallelism. As fas as the architecture i have found 3 options and was wondering what you think?

Favourite one: actor pattern - https://github.com/AsynkronIT/protoactor-go An actor per CSG object seems like a very nice fit because a CSG scene has CSG objects in a graph. So one actor per CSG in the graph. Actors are made for this i feel. The Actor / Graph structure lends itself to binding to a retaining mode openGL GUi later too.

2nd fav astranet - https://github.com/zenhotels/astranet This basically take golang routines and spreads them over the network. There are small changes to a typical golang routine to make it work. I like the fact that you can take a library using go routines and get it using the network with little code changes.

Not a good fit maybe. NATS with go kit - https://github.com/moul/chatsvc Requires more changes to standard golang go routines of course. I dont thing that this is a good hammer to crack this nut.

On Tue, Jun 6, 2017 at 4:47 PM Jason Harris notifications@github.com wrote:

On the one hand I do like that the SDFs lead themselves to modelling via the continuous equation rather than a piece-wise approximation. E.g. in openscad you have to tell it how many segments you want it to use in a circle/curve - it models things with polygon approximations. On the other hand trying to work out the SDF evaluation using the continuous equation can start to become a bit tedious for complicated things. I tried doing some newton-raphson solvers, and that works, except when it doesn't. Take a look at the bezier curve stuff. I just turned it into a polygon (I suppose that's a form of discretization) and did the SDF on that. That's a very general technique. My SDF evaluation for polygons is correct but is O(n). It should be possible to write a much faster evaluator for 2D polygons, I just haven't worked it out yet. It should also be possible to get speedups by caching evaluation results. E.g extrudes of 2D objects keep on evaluating the same points.

— You are receiving this because you authored the thread.

Reply to this email directly, view it on GitHub https://github.com/deadsy/sdfx/issues/1#issuecomment-306509409, or mute the thread https://github.com/notifications/unsubscribe-auth/ALcacyukH8OchuCDWRlj6-cZ9cuFRPoBks5sBWZpgaJpZM4NhtJc .

[deadsy]

You essentially end up with a tree data structure consisting of geometric primitives and CSG operations upon those primitives. Then you evaluate that tree at discrete points within a 3D region to sample the object. In so far as the samples are all independent you could parallelize the problems to the Nth degree by throwing processors at points or sub-regions of the 3D space. The code is currently single threaded, and beyond algorithmic improvements, I suppose I'd just go-routinize the sampling for a multi-core gain before I bothered to use multiple machines.

[joeblew99]

SO lets see if i have got this right then:

1. Shared scene data, and throw processors at sub regions with no side effects possible. SO, that means one CSG result will NOT affect another one - everything is independent.

If true then this is very easy to scale out. Once i get clarification i can look into it.

[deadsy]

Right- the SDF evaluations are independent. Enabling this code to make proper use of multi-core is pretty simple. i.e. - look at the layer code in marching.go. If you have N cores just set each of them to working out the SDF values for a 2D layer. As they complete the results can be fed to the marching cubes code.