Bounding Box: compute during depsgraph evaluation #92206

New Issue

Sybren A. Stüvel · 2021-10-14T12:01:35+02:00

Sybren A. Stüvel commented

2021-10-14 12:01:35 +02:00

Currently Object::runtime::bb bounding boxes (BBs) are computed on demand. There are a few different code paths that trigger such computation, and not all of them have the same computation (resulting in #91102). This problem be solved by moving the computation of the bounding box to the depsgraph evaluation. This can then be done consistently and in parallel.

This improvement step should also be used to investigate which coordinate space is used for storing the bounding box, and actually documenting that in a comment in the source code.

Related note, not part of this task but could be fleshed out in a subtask:

The current code doesn't take instancing into account; the bounding box of each instance of an object is recomputed from scratch. From what I (@dr.sybren) understood, this is even done sequentially. This could likely be parallellized, and maybe some other smartness could use the BB of the duplicator to compute the BB of the dupli. Not sure how the latter could be done efficiently, though, as BBs are axis-aligned and simply applying a transformation matrix may make it too large/small.

Currently `Object::runtime::bb` bounding boxes (BBs) are computed on demand. There are a few different code paths that trigger such computation, and not all of them have the same computation (resulting in #91102). This problem be solved by moving the computation of the bounding box to the depsgraph evaluation. This can then be done consistently and in parallel. This improvement step should also be used to investigate which coordinate space is used for storing the bounding box, and actually documenting that in a comment in the source code. ------------ Related note, **not part of this task** but could be fleshed out in a subtask: The current code doesn't take instancing into account; the bounding box of each instance of an object is recomputed from scratch. From what I (@dr.sybren) understood, this is even done sequentially. This could likely be parallellized, and maybe some other smartness could use the BB of the duplicator to compute the BB of the dupli. Not sure how the latter could be done efficiently, though, as BBs are axis-aligned and simply applying a transformation matrix may make it too large/small.

Sybren A. Stüvel commented

2021-10-14 12:01:35 +02:00

Changed status from 'Needs Triage' to: 'Confirmed'

Sybren A. Stüvel commented

2021-10-14 12:01:35 +02:00

Added subscriber: @dr.sybren

Sergey Sharybin commented

2021-10-14 12:55:48 +02:00

Added subscribers: @mont29, @Sergey

Sergey Sharybin commented

2021-10-14 12:55:48 +02:00

Bounding Box: compute using depsgraph node

From the title it sounds like you want a new depsgraph node for the boundbox evaluation, but you don;t mention any benefit from the relations point of view. Adding extra nodes has performance impact, so unless there is real need from graph topology point of view we should do bounding box evaluation as an existing geometry and object modifier stack evaluation nodes.

Currently Object::runtime::bb bounding boxes are computed on demand.

There are indeed places where on-demand calculation will be used. However, for mesh objects the bounding box calculation is done in the mesh_build_data() which is where modifier stack is evaluated. So strictly speaking the statement is at least partially not truthful :)

I did not check other object types evaluation, but if they don't calculate bounding box as part of evaluation I do not see issues of following mesh example there as well.

However, if the issues you've listed in the task description do happen for mesh objects it might be an indicative of something else being broken (because, as mentioned, mesh objects seems to calculate their bounding box during depsgraph evaluation).

Furthermore, the current code doesn't take instancing into account; the bounding box of each instance of an object is recomputed, instead of copying the bounding box from their source object (because the BB is only stored on the CoW copy, and not the original).

Instancing does not make much sense in the original domain. If you need instances you should be using evaluated state and you should not go from evaluated domain to original one. So the fact that boundbox is stored in CoW does make sense to me.

At some point we did have a code which was copying bounding box from evaluated object to original one for an active dependency graph (similar to how animated properties are copied). I can not see this code anymore though. Not sure what happened to it. Maybe @mont29 can shed some light?

It's also my hope that this could be more aware of instancing

The dependency graph is not aware of instancing, so not sure how calculating boundbox during graph evaluaiton would make a difference here.

Such that it can use a copy (+ maybe a matrix multiplication) of the source object rather than iterating over all vertices

Calculate vertices boundbox + transform boundbox != transform vertices + calculate boundbox.

> Bounding Box: compute using depsgraph node From the title it sounds like you want a new depsgraph node for the boundbox evaluation, but you don;t mention any benefit from the relations point of view. Adding extra nodes has performance impact, so unless there is real need from graph topology point of view we should do bounding box evaluation as an existing geometry and object modifier stack evaluation nodes. > Currently `Object::runtime::bb` bounding boxes are computed on demand. There are indeed places where on-demand calculation will be used. However, for mesh objects the bounding box calculation is done in the `mesh_build_data()` which is where modifier stack is evaluated. So strictly speaking the statement is at least partially not truthful :) I did not check other object types evaluation, but if they don't calculate bounding box as part of evaluation I do not see issues of following mesh example there as well. However, if the issues you've listed in the task description do happen for mesh objects it might be an indicative of something else being broken (because, as mentioned, mesh objects seems to calculate their bounding box during depsgraph evaluation). > Furthermore, the current code doesn't take instancing into account; the bounding box of each instance of an object is recomputed, instead of copying the bounding box from their source object (because the BB is only stored on the CoW copy, and not the original). Instancing does not make much sense in the original domain. If you need instances you should be using evaluated state and you should not go from evaluated domain to original one. So the fact that boundbox is stored in CoW does make sense to me. At some point we did have a code which was copying bounding box from evaluated object to original one for an active dependency graph (similar to how animated properties are copied). I can not see this code anymore though. Not sure what happened to it. Maybe @mont29 can shed some light? > It's also my hope that this could be more aware of instancing The dependency graph is not aware of instancing, so not sure how calculating boundbox during graph evaluaiton would make a difference here. > Such that it can use a copy (+ maybe a matrix multiplication) of the source object rather than iterating over all vertices Calculate vertices boundbox + transform boundbox != transform vertices + calculate boundbox.

Sybren A. Stüvel changed title from ~~Bounding Box: compute using depsgraph node~~ to Bounding Box: compute during depsgraph evaluation

2021-10-14 13:53:23 +02:00

Sybren A. Stüvel commented

2021-10-14 13:58:04 +02:00

In #92206#1235501, @Sergey wrote:
From the title it sounds like you want a new depsgraph node for the boundbox evaluation, but you don;t mention any benefit from the relations point of view. Adding extra nodes has performance impact, so unless there is real need from graph topology point of view we should do bounding box evaluation as an existing geometry and object modifier stack evaluation nodes.

I agree, I renamed it to a more simple "during depsgraph evaluation" .

There are indeed places where on-demand calculation will be used. However, for mesh objects the bounding box calculation is done in the mesh_build_data() which is where modifier stack is evaluated. So strictly speaking the statement is at least partially not truthful :)

I did not check other object types evaluation, but if they don't calculate bounding box as part of evaluation I do not see issues of following mesh example there as well.

The problem surfaced in an application where a curve was used as constraint target, so other object types are indeed a problem. If the mesh approach is deemed "sane enough to copy", let's just copy that.

Instancing does not make much sense in the original domain. If you need instances you should be using evaluated state and you should not go from evaluated domain to original one. So the fact that boundbox is stored in CoW does make sense to me.

Same here, I didn't mean to imply that the BB stored in CoW was a problem.

At some point we did have a code which was copying bounding box from evaluated object to original one for an active dependency graph (similar to how animated properties are copied). I can not see this code anymore though. Not sure what happened to it. Maybe @mont29 can shed some light?

It's also my hope that this could be more aware of instancing

The dependency graph is not aware of instancing, so not sure how calculating boundbox during graph evaluaiton would make a difference here.

Maybe the task should be split up into two, then. One for handling bounding boxes during depsgraph evaluation, and the other for instancing improvements. I'll update the task description to just nudge towards the instancing, but clearly focus on getting BB computation into the depsgraph evaluation.

Calculate vertices boundbox + transform boundbox != transform vertices + calculate boundbox.

True.

> In #92206#1235501, @Sergey wrote: > From the title it sounds like you want a new depsgraph node for the boundbox evaluation, but you don;t mention any benefit from the relations point of view. Adding extra nodes has performance impact, so unless there is real need from graph topology point of view we should do bounding box evaluation as an existing geometry and object modifier stack evaluation nodes. I agree, I renamed it to a more simple "during depsgraph evaluation" . > There are indeed places where on-demand calculation will be used. However, for mesh objects the bounding box calculation is done in the `mesh_build_data()` which is where modifier stack is evaluated. So strictly speaking the statement is at least partially not truthful :) > > I did not check other object types evaluation, but if they don't calculate bounding box as part of evaluation I do not see issues of following mesh example there as well. The problem surfaced in an application where a curve was used as constraint target, so other object types are indeed a problem. If the mesh approach is deemed "sane enough to copy", let's just copy that. > Instancing does not make much sense in the original domain. If you need instances you should be using evaluated state and you should not go from evaluated domain to original one. So the fact that boundbox is stored in CoW does make sense to me. Same here, I didn't mean to imply that the BB stored in CoW was a problem. > At some point we did have a code which was copying bounding box from evaluated object to original one for an active dependency graph (similar to how animated properties are copied). I can not see this code anymore though. Not sure what happened to it. Maybe @mont29 can shed some light? > >> It's also my hope that this could be more aware of instancing > > The dependency graph is not aware of instancing, so not sure how calculating boundbox during graph evaluaiton would make a difference here. Maybe the task should be split up into two, then. One for handling bounding boxes during depsgraph evaluation, and the other for instancing improvements. I'll update the task description to just nudge towards the instancing, but clearly focus on getting BB computation into the depsgraph evaluation. > Calculate vertices boundbox + transform boundbox != transform vertices + calculate boundbox. True.

Sergey Sharybin commented

2021-10-14 16:47:17 +02:00

If the mesh approach is deemed "sane enough to copy", let's just copy that.

I think the mesh approach is the way to go.
It will also solve possible issues that Object::runtime.:bb means different things depending on the object type.

Maybe the task should be split up into two

Think it will be the best. The boundbox evaluation during depsgraph evaluation should be a straightforward easy change (ignoring the reality where things are always less easy than they sound! ;) The optimization for instancing is a whole another story, and would need more careful look into.

> If the mesh approach is deemed "sane enough to copy", let's just copy that. I think the mesh approach is the way to go. It will also solve possible issues that `Object::runtime.:bb` means different things depending on the object type. > Maybe the task should be split up into two Think it will be the best. The boundbox evaluation during depsgraph evaluation should be a straightforward easy change (ignoring the reality where things are always less easy than they sound! ;) The optimization for instancing is a whole another story, and would need more careful look into.

Hans Goudey commented

2021-11-29 16:12:56 +01:00

Added subscriber: @HooglyBoogly

Hans Goudey commented

2021-11-29 16:12:56 +01:00

The mesh approach of ignoring all the dirty tag complexity, etc. is nice, since the bound box will be used anyway. However, I don't think BKE_object_boundbox_calc_from_mesh is doing the right thing, since it is using just a mesh rather than the evaluated geometry set.
I think it would be more correct to use BKE_object_boundbox_calc_from_evaluated_geometry everywhere we calculate the bounding box for a newly evaluated object.

The mesh approach of ignoring all the dirty tag complexity, etc. is nice, since the bound box will be used anyway. However, I don't think `BKE_object_boundbox_calc_from_mesh` is doing the right thing, since it is using just a mesh rather than the evaluated geometry set. I think it would be more correct to use `BKE_object_boundbox_calc_from_evaluated_geometry` everywhere we calculate the bounding box for a newly evaluated object.

Hans Goudey commented

2021-12-16 20:22:10 +01:00

In #92206#1235501, @Sergey wrote:
At some point we did have a code which was copying bounding box from evaluated object to original one for an active dependency graph (similar to how animated properties are copied). I can not see this code anymore though. Not sure what happened to it.

@Sergey I think what you're thinking about is still there: object_sync_boundbox_to_original

I've been interested in refactoring this area for a while, since the inconsistencies are quite bad sometimes, and the performance penalties from storing the bounding box on objects instead of data is becoming a problem for geometry nodes.
I spent some time investigating what that would look like, and made a "draft" patch here: D13598: Refactor: Clarify object bounding boxes, cache bounds in data (WIP)

Regarding the specific goal of this patch, it seems like the calculation is usually (almost always) triggered during depsgraph evaluation already anyway.

> In #92206#1235501, @Sergey wrote: > At some point we did have a code which was copying bounding box from evaluated object to original one for an active dependency graph (similar to how animated properties are copied). I can not see this code anymore though. Not sure what happened to it. @Sergey I think what you're thinking about is still there: `object_sync_boundbox_to_original` I've been interested in refactoring this area for a while, since the inconsistencies are quite bad sometimes, and the performance penalties from storing the bounding box on objects instead of data is becoming a problem for geometry nodes. I spent some time investigating what that would look like, and made a "draft" patch here: [D13598: Refactor: Clarify object bounding boxes, cache bounds in data (WIP)](https://archive.blender.org/developer/D13598) Regarding the specific goal of this patch, it seems like the calculation is usually (almost always) triggered during depsgraph evaluation already anyway.

Brecht Van Lommel commented

2022-02-28 17:32:46 +01:00

Added subscriber: @brecht

Brecht Van Lommel commented

2022-02-28 17:32:46 +01:00

Too late for 3.1 I imagine, moving to next release.

Satish Goda commented

2022-04-12 20:28:16 +02:00

Added subscriber: @satishgoda1

Philipp Oeser removed the

Download

What's New

Blender Studio

Manual

Developers Blog

Documentation

Benchmark

Blender Conference

Development Fund

One-time Donations

Bounding Box: compute during depsgraph evaluation #92206