Page MenuHome
Differential D9787

Add Poisson distribution to the Point Scatter geometry node
ClosedPublic
Actions

Authored by Dalai Felinto (dfelinto) on Dec 8 2020, 4:23 PM.

Details

Reviewers
Sebastian Parborg (zeddb)
Jacques Lucke (JacquesLucke)
Maniphest Tasks
T83228: Dithering support for the disk poisson point scattering node
T83230: Tile distribution for the disk poisson for scattering
Summary

Here is the my current work on adding the new Poisson scattering method.
(This should close T83230 and T83228)

I've also added a Seed input so the user can change the random seed if they wish.

There are still some things that needs to be done:

  1. How should proceed with the 3rd party header library I pulled in.

I've only picked out a small subset of this library: https://github.com/cemyuksel/cyCodeBase/
The library is heavily templated so I could see it used in some other parts of blender in the future.

But for the functionality we need for this case, we could easily just write our own code as the algorithm is quite simple.

  1. Fix the doversion code. Older files with connections to the "Density" socket will have this connection lost.

I've tried to figure out how to properly fix this before my vacation started, but couldn't do it within that time frame.

  1. There might be some optimization/multithreading that could be done.

Sadly for the slowest part (the Poisson distribution algorithm), some clever work would have to be done to make it multi threaded.

The two slow parts is the weight assignment to the points and then the point elimination.
From my tests, they have nearly the same execution time.

For the point weight assignment this could easily be multi threaded by just running all points in parallel (the points individual weight does not depend on the other points weight), so we could have a massive speed up here.

The point elimination is a bit trickier though as the point with the highest weight is removed first. Because the point is removed, all points in its vicinity will have to update their weight values. We could probably do some clever multi threading by slicing the point distribution up and eliminating points within those slices. It would probably work the same way as with particle physics sims where you make sure you only calculate solutions in parallel for points that can't influence each other.

Diff Detail

Repository
rB Blender
Branch
geometry-nodes-distribute-points
Build Status
Buildable 11660
Build 11660: arc lint + arc unit

Event Timeline

Sebastian Parborg (zeddb) requested review of this revision.Dec 8 2020, 4:23 PM
Sebastian Parborg (zeddb) created this revision.
Sebastian Parborg (zeddb) edited the summary of this revision. (Show Details)
Sebastian Parborg (zeddb) edited the summary of this revision. (Show Details)Dec 8 2020, 4:27 PM
Dalai Felinto (dfelinto) added a subscriber: Dalai Felinto (dfelinto).Dec 8 2020, 4:35 PM
Dalai Felinto (dfelinto) added inline comments.
source/blender/nodes/geometry/nodes/node_geo_point_distribute.cc
170

Note to self: cleanup comment style.

209

Note to self: Remove TODOs that will have be tackled in real life.

285–295

note to self: replace this with switch

Dalai Felinto (dfelinto) removed a reviewer: Geometry Nodes.Dec 8 2020, 4:35 PM
Dalai Felinto (dfelinto) added a project: Geometry Nodes.
Ray Molenkamp (LazyDodo) added subscribers: Brecht Van Lommel (brecht), Ray Molenkamp (LazyDodo).Dec 8 2020, 4:37 PM

cyCodeBase has

  1. no public releases
  2. no active work being done on it (last commit was 11 months ago)
  3. header only

there's very little reason to add it to SVN, if we chose to adopt this library (it's still unclear to me who would make that call) my preference would be to use /extern to house it cc: @Brecht Van Lommel (brecht)

Brecht Van Lommel (brecht) added a comment.EditedDec 8 2020, 4:51 PM

I don't think we should add a library dependency for this or add it in extern/, but rather port the small amount of code we need.

Sebastian Parborg (zeddb) added a comment.EditedDec 8 2020, 5:31 PM
In D9787#243356, @Brecht Van Lommel (brecht) wrote:

I don't think we should add a library dependency for this or add it in extern/, but rather port the small amount of code we need.

Ok, that is bascially what I have done so far.
One of the things that is missing is that we need a "Max Heap" (we only have min heap atm).
We could simply use the STD cpp heap implementation to do this I think. And then we can get rid of the cyHeap.h file.

Then it will only be one header file. We could perhaps make this into a generic blender help library (BLI_) so it could be used in other parts of blender easily as well.

Dalai Felinto (dfelinto) added a comment.Dec 9 2020, 5:58 PM

@Sebastian Parborg (zeddb) I tried to arc patch this patch but it failed. Which branch you used as a base? Can you arc diff against master?
(or is this the exact content of geometry-nodes-distribute-points branch?)

Dalai Felinto (dfelinto) added a comment.Dec 9 2020, 6:28 PM

I think it is ok to not do doversion in this very particular case.

We do need a better API for this. Because renaming can help for driver and fcurve. But for links we still need to iterate over sockets and what not. I don't think it is worth the effort for this case.

source/blender/makesdna/DNA_node_types.h
1074

Note: remove all the non relevant (style) changes

Sebastian Parborg (zeddb) added a comment.EditedDec 9 2020, 6:57 PM
In D9787#243748, @Dalai Felinto (dfelinto) wrote:

@Sebastian Parborg (zeddb) I tried to arc patch this patch but it failed. Which branch you used as a base? Can you arc diff against master?
(or is this the exact content of geometry-nodes-distribute-points branch?)

This is a diff from master to the geometry-nodes-distribute-points, yes.
As you didn't provide any more info than "it doesn't work" you can also try regular git apply. Sometimes arc fails while git apply works.

Sebastian Parborg (zeddb) added inline comments.Dec 9 2020, 6:59 PM
source/blender/makesdna/DNA_node_types.h
1074

These were done automatically by clang format on my end.
But if these changes doesn't happen with a manual make format we should of course just revert it.

Dalai Felinto (dfelinto) updated this revision to Diff 31810.Dec 10 2020, 11:35 AM
  • Remove all versioning code
  • Remove unrelated changes in DNA_node_types.h
  • Cleanup: commits
  • Cleanup: Use switch (this automatically throws a warning when an enum item was neglected)

I still need to savage the library to take only the bits we need.

Harbormaster completed remote builds in B11660: Diff 31810.Dec 10 2020, 11:35 AM
Dalai Felinto (dfelinto) commandeered this revision.Dec 11 2020, 2:05 AM
Dalai Felinto (dfelinto) added a reviewer: Sebastian Parborg (zeddb).

Commandering since I'm rewriting/cleaning it.

My work is in temp-geometry-nodes-distribute-points-cleanup and once finished I can update this Dxxx. The current status is:

  • Tiling
  • Weighting
  • Remove based on weight: Implemented with BLI_heap but it is producing a different result than with cyHeap
  • Progressive (the if progressive part of the code)
Jacques Lucke (JacquesLucke) mentioned this in rB985d673374a4: BLI: add new InplacePriorityQueue data structure.Dec 16 2020, 12:24 PM
Dalai Felinto (dfelinto) updated this revision to Diff 32058.Dec 16 2020, 12:29 PM

Removing all the external dependencies, patch finalized

Harbormaster completed remote builds in B11772: Diff 32058.Dec 16 2020, 12:29 PM
Dalai Felinto (dfelinto) updated this revision to Diff 32059.Dec 16 2020, 12:30 PM
  • Fix for changes in the heap api
Harbormaster completed remote builds in B11773: Diff 32059.Dec 16 2020, 12:30 PM
Jacques Lucke (JacquesLucke) accepted this revision.Dec 16 2020, 1:01 PM
Jacques Lucke (JacquesLucke) added a subscriber: Jacques Lucke (JacquesLucke).

Overall the code seems fine. I tested it, and it produces the intended results. I think there are a few ways in which the code itself can be improved, but I will take care of that in master. I don't see any fundamental flaws in the current code.

There are a couple of // namespace blender::nodes comments in the wrong place.

source/blender/makesrna/intern/rna_nodetree.c
443

inside the domain -> on the surface

448

Same as above.

Also this should probably mention that the points are projected to the surface currently.

source/blender/nodes/geometry/nodes/node_geo_point_distribute.cc
38–39

I think the minimum distance should be smaller by default. Maybe 0.1.

224

Wrong comment style.

This revision is now accepted and ready to land.Dec 16 2020, 1:01 PM
Philipp Oeser (lichtwerk) added a subscriber: Philipp Oeser (lichtwerk).Dec 16 2020, 1:06 PM

Does this support variable radii? Or is this for later? (See "Variable Radii Poisson-Disk Sampling")

Dalai Felinto (dfelinto) updated this revision to Diff 32060.Dec 16 2020, 1:21 PM
Dalai Felinto (dfelinto) marked an inline comment as done.
  • Tweaks from review
Harbormaster completed remote builds in B11774: Diff 32060.Dec 16 2020, 1:21 PM
Dalai Felinto (dfelinto) mentioned this in rBa7628ec22abc: Geometry Nodes: Poisson disk point distribution node/method.Dec 16 2020, 5:14 PM
Dalai Felinto (dfelinto) closed this revision.Dec 16 2020, 6:06 PM

Committed on rBa7628ec22abca8d1aaada75a8227638947168a3a

Dalai Felinto (dfelinto) added a comment.Dec 16 2020, 6:07 PM
In D9787#246163, @Philipp Oeser (lichtwerk) wrote:

Does this support variable radii? Or is this for later? (See "Variable Radii Poisson-Disk Sampling")

I wouldn't know.

Revision Contents
Changeset List

PathSize
source/
blender/
blenlib/
1 line
intern/
19 lines
editors/
space_node/
10 lines
makesdna/
5 lines
makesrna/
intern/
25 lines
nodes/
2 lines
geometry/
nodes/
279 lines
933 lines
193 lines

Diff 31810

View Options

source/blender/blenlib/BLI_kdopbvh.h

Loading...
View Options

source/blender/blenlib/intern/BLI_kdopbvh.c

Loading...
View Options

source/blender/editors/space_node/drawnode.c

Loading...
View Options

source/blender/makesdna/DNA_node_types.h

Loading...
View Options

source/blender/makesrna/intern/rna_nodetree.c

Loading...
View Options

source/blender/nodes/NOD_static_types.h

Loading...
View Options

source/blender/nodes/geometry/nodes/cyHeap.h

Loading...
View Options

source/blender/nodes/geometry/nodes/cySampleElim.hh

Loading...
View Options

source/blender/nodes/geometry/nodes/node_geo_point_distribute.cc

Loading...