Page MenuHome
Differential D10402

Fix T84899: Instance ids are not unique.
ClosedPublic
Actions

Authored by Jacques Lucke (JacquesLucke) on Feb 12 2021, 1:36 PM.

Details

Reviewers
Hans Goudey (HooglyBoogly)
Maniphest Tasks
T84899: Large number of instance render wont start, stuck at 1sample, repeating BVH Building
Commits
rB98db4cc6391d: Fix T84899: instance ids are not unique in common cases
Summary

Ids stored in the id attribute cannot be assumed to be unique. While they might be unique in many cases, this is not something that can be guaranteed in general. For some use cases (e.g. generating "stable randomness" on points) uniqueness is not important. To support features like motion blur, unique ids are important though.

This patch implements a simple algorithm that turns non-unique ids into unique ids. Obviously, there are limits to how successful this can be. Here are some requirements I set:

  • Ids that are unique already, must not be changed/
  • If there are id collisions, only ids that collide should be changed.
  • The same input should generate the same output.
  • Handle the cases when all ids are different and when all ids are the same equally well (in expected linear time).
  • Small changes in the input id array should ideally only have a small impact on the output id array.

Diff Detail

Repository
rB Blender
Branch
unique-instance-ids (branched from master)
Build Status
Buildable 12839
Build 12839: arc lint + arc unit

Event Timeline

Jacques Lucke (JacquesLucke) requested review of this revision.Feb 12 2021, 1:36 PM
Jacques Lucke (JacquesLucke) created this revision.
Harbormaster completed remote builds in B12835: Diff 33901.Feb 12 2021, 1:36 PM
Jacques Lucke (JacquesLucke) edited the summary of this revision. (Show Details)Feb 12 2021, 1:45 PM
Jacques Lucke (JacquesLucke) added a task: T84899: Large number of instance render wont start, stuck at 1sample, repeating BVH Building.
Jacques Lucke (JacquesLucke) retitled this revision from Fix T84899: Instance ids are not unique. to Fix T84899: Instance ids are not unique (WIP)..
Jacques Lucke (JacquesLucke) added a subscriber: Hans Goudey (HooglyBoogly).
Jacques Lucke (JacquesLucke) updated this revision to Diff 33904.Feb 12 2021, 1:51 PM
  • cleanup
Harbormaster completed remote builds in B12838: Diff 33904.Feb 12 2021, 1:51 PM
Jacques Lucke (JacquesLucke) updated this revision to Diff 33905.Feb 12 2021, 1:57 PM
  • use set instead of map
Harbormaster completed remote builds in B12839: Diff 33905.Feb 12 2021, 1:57 PM
Jacques Lucke (JacquesLucke) updated this revision to Diff 33920.Feb 12 2021, 4:43 PM
  • use caching and apply to 2.92
Harbormaster completed remote builds in B12850: Diff 33920.Feb 12 2021, 4:43 PM
Jacques Lucke (JacquesLucke) edited the summary of this revision. (Show Details)Feb 12 2021, 4:43 PM
Jacques Lucke (JacquesLucke) added a reviewer: Hans Goudey (HooglyBoogly).
Jacques Lucke (JacquesLucke) retitled this revision from Fix T84899: Instance ids are not unique (WIP). to Fix T84899: Instance ids are not unique..
Hans Goudey (HooglyBoogly) added a comment.Feb 12 2021, 5:05 PM

Didn't test this myself, but I doubt I would end up testing a situation you didn't, and the code looks good. Just a couple questions.

source/blender/blenkernel/intern/geometry_set.cc
609

I guess this is the part that makes it consistent for every run, but I think I'm not understanding this properly.
The original_id will be the same for every collided id. If we seed each collided ID with the same value, won't they reproduce the same sequence of random values. I would expect that to work fine until you have more than 100 collisions, in which case using the same sequence of random values for every collision wouldn't work anymore.

What am I missing?

638

Do we ever expect this cache to be invalidated over the course of drawing? If the "almost unique ids" were generated once at the end of evaluation, the same cache should apply until the next evaluation, right?

That assumes the "almost_unique_ids" will always be used I suppose, and would require moving this to modifier evaluation.

Anyway, some note here addressing that somehow would be nice.

Jacques Lucke (JacquesLucke) added inline comments.Feb 12 2021, 5:17 PM
source/blender/blenkernel/intern/geometry_set.cc
609

You are missing that the random number generator is only seeded once for every original_id, because it is cached in generator_by_original_id.

638

Well, if some node would use this and then change the instances component, this would have to be invalidated.
Currently, the generated ids are indeed never invalidated, I'm just generating them lazily when needed.

Hans Goudey (HooglyBoogly) accepted this revision.Feb 12 2021, 5:24 PM
Hans Goudey (HooglyBoogly) added inline comments.
source/blender/blenkernel/intern/geometry_set.cc
609

Right! Thanks

638

Right, the node changing the Instances would happen before the end of evaluation though. Anyway, I like this method, was just curious about the other approach.

This revision is now accepted and ready to land.Feb 12 2021, 5:24 PM
Closed by commit rB98db4cc6391d: Fix T84899: instance ids are not unique in common cases (authored by Jacques Lucke (JacquesLucke)). · Explain WhyFeb 12 2021, 5:48 PM
This revision was automatically updated to reflect the committed changes.
Jacques Lucke (JacquesLucke) added a commit: rB98db4cc6391d: Fix T84899: instance ids are not unique in common cases.

Revision Contents
Changeset List

PathSize
source/
blender/
blenkernel/
3 lines
intern/
65 lines
8 lines

Diff 33905

View Options

source/blender/blenkernel/BKE_geometry_set.h

Loading...
View Options

source/blender/blenkernel/intern/geometry_set.cc

Loading...
View Options

source/blender/blenkernel/intern/object_dupli.c

Loading...