Page MenuHome

Cycles: Adding Hilbert Curve as a tile order for rendering
ClosedPublic

Authored by Lukas Stockner (lukasstockner97) on Mar 8 2015, 10:11 PM.

Details

Summary

This patch adds the option to render tiles in a Hilbert-Curve order.
The original curve implementation is from Wikipedia.
Since the curve is only defined for square power-of-2 regions, the code works as if the image was padded and nonexisting tiles were skipped.

Diff Detail

Repository
rB Blender

Event Timeline

Lukas Stockner (lukasstockner97) retitled this revision from to Cycles: Adding Hilbert Curve as a tile order for rendering.Mar 8 2015, 10:11 PM

Sure we can start adding all sort of weird and wonderful curves to the tile traversing, but what exactly this brings to artists?

IMO, we should follow the different road:

  • Allow some callback to define a ROI from where the bucket of tiles are starting to summon from
  • Add a proper dynamically scheduled tiles, which would preserve locality of the rendering, keeping the render time as fast as possible. That would be like crucial thing to have if we want to have BVH proxies at some point.

I ran some tests, Hilbert is faster than the "Center" method, but not faster than the Top/Bottom approaches. Nevertheless, Hilbert is nicer visually as one of these, so I think this can go in.

Suggestion:

  • Let Hilbert Curve start in the Center, rather than in the bottom left corner, nicer for feedback.
  • Replace current Center algorithm with this (Hilbert).

Thanks @Thomas Dinges (dingto) for tests! But I wouldn't call it "can go in" just yet ;) Simply there are some stuff in the code to be cleaned up first :)

Starting from center should be relatively simple i think and we should consider doing that, yes. The only thing i'm skeptical about is changing default without feedback from even gooseberry team.

Okay, then let's change Hilbert to start in the center, and then get some feedback. :)

Sergey Sharybin (sergey) requested changes to this revision.
Sergey Sharybin (sergey) added inline comments.
intern/cycles/render/tile.cpp
313

This is to be calculated for only TILE_HILBERT it seems, no need to calculate it for all the tile orders.

intern/cycles/render/tile.h
51

Please place comma at the end.

I would like to switch to that style, so adding new enum values doesn't add noise in patches by affecting previous enum line.

intern/cycles/util/util_hilbert.h
17 ↗(On Diff #3706)

Did you consider calling it more generic, like util_curve.h or so? So we can add more curve-specific files here.

Plus the file does not follow the code conventions. And one more thing, functions are to have util_ prefix.

22 ↗(On Diff #3706)

Doesn't it seem generic enough to be a part of util_math?

inline => ccl_device_inline. Same applies to cases below.

33 ↗(On Diff #3706)

Would prefer something more verbose:

/* Hilbert curve calculation functions
 * Based on code from
 *  http://en.wikipedia.org/wiki/Hilbert_curve
 */

Or just no need to bother with links.

41 ↗(On Diff #3706)

You can use swap from util_algorithm.h.

49 ↗(On Diff #3706)

Spaces around operators seems inconsistent.

This revision now requires changes to proceed.Mar 12 2015, 11:43 AM

Just to clarify: What do you mean with "start from center"?
The way I see it, you would have four Hilbert Curves, starting form the center and each one of them going towards one corner of the image. However, in that case the tile coherency is lost again because you work on 4 different parts of the image.
Another idea would be to divide the image into a 3x3 grid and rendering each one, starting from the center, with the Hilbert Curve...

Is this somehow better than existing tile orders? I haven't tested the patch, but from the video on wikipedia it looks quite unpredictable to the untrained artist's eye. Like a snake randomly changing direction.

Would also suggest a more useful tooltip ;)

Edit: Not that I'm against adding cool new features, just wouldn't recommend replacing the current 'Center' unless it's an improvement.

Hi, I'm sorry if it's not the right place to ask something but I've lost Hours of rendertime because of this "feature"

I often cancel a render when I realize I won't meet the deadline, to relaunch it on multiple computer. Having to deal with non rectangular region is a nighmare.

For exemple today I had to create a plane with a mask of the previous render(canceled at 50%).

So please give us top/bottom.

sincerely

Render Settings (Properties Editor) -> Performance Panel -> Tiles. You can set it to Top / Bottom there, we have that feature for almost 2 years.

Thomas Dinges (dingto) edited edge metadata.
Thomas Dinges (dingto) removed rB Blender as the repository for this revision.
Thomas Dinges (dingto) commandeered this revision.
Thomas Dinges (dingto) updated this revision to Diff 5520.
  • Addressing review comments. Imho ready to commit. Not making it default, just as a user choice.

In order to be really useful for artists it have to be somewhat more starting-from-center and probably even become a default strategy.

Otherwise it's just yet another option which is not gonna to be used.

intern/cycles/render/tile.cpp
198

Could also become an util_ function.

I played around a bit and found a way to create a spiral-hilbert-mix that roughly follows a spiral pattern (from the center outwards), but consists of rotated instances of a hilbert curves.
Below is a quick, hacky patch that adds support for it - the main change is that it modifies the code to store the generated tiles in a sorted order. Actually, I think we should do that in any case, since the current tile code is O(n²) (for each fetched tile, it searches the largest tile in the whole list - that might be the reason why 8x8 is sometimes slower than 16x16, but I didn't benchmark yet).

The new pattern is just as fast as bottom-to-top etc. afaics and therefore slightly faster than center. The main problem I can see is that for large tiles it's not really centered anymore, but for smaller tiles it works great.

Tested the hilbert.diff from latest comment, looks good to me visually.

Woops, had unpublished comment. Would be nice if phabricator notifies diff/task author when someone has something unpublished, but that's another story.

This is the order i had in mind indeed. But please:

  • Apply D1684
  • Update the patch against newer master
  • Update this revision for the review, there's some feedback
  • You can also try getting rid of explicit std::swap call by using util_algorithm.h

New diff, now with the new Hilbert Spiral pattern.

Sergey Sharybin (sergey) requested changes to this revision.
Sergey Sharybin (sergey) added inline comments.
intern/cycles/render/tile.cpp
161

This will fail for viewport renders, i.e.

174

Can it be more meaningful name than just a single letter? Same applies to the cases below.

185

Braces around the block.

intern/cycles/util/util_math.h
37

That's not best idea in the world to include algorithm for non-CPU kernels.

1548

Avoid having rather meaningless names.

This revision now requires changes to proceed.Dec 26 2015, 7:58 PM

Okay, review should be addressed.
The assert(!sliced) should be fine now since Bottom-to-Top tile order is now forced for viewport rendering (since it won't be visible anyways).
This was actually standard behaviour for the older TileManager, but since the new one treats viewport and F12-render essentially equal, it needs to be forced somewhere else now.
I did some tests here, usual result was: Hilbert Curve beats Center by ~5 percent, but loses to Bottom-to-top by some fraction of a percent.

intern/cycles/render/tile.cpp
65

d >> 1

69

Braces.

73

d >>= 2

179

Can we have more readable names for the direction? Like,

enum {
  DIRECTION_LEFT,
  DIRECTION_TOP,
};

or something similar?

215

Picky: Prefer not to have quesitons in comments, statements are usually cleaner to follow. Like, "Check whether center of spiral was reached.". Applies to few places here.

222

This doesn't follow code style.

278

Please apply this separately. Can go to master now, but please always use mustage (curly ;) brackets.

Okay, review is addressed.
I originally tried to keep the LOC added due to the Hilbert Spiral down, but it indeed looks nicer now.
Also, I already committed the "Force Bottom-to-Top", so it's no longer needed in here.

Thomas Dinges (dingto) accepted this revision.

Looks good to me and can be commited.

This revision was automatically updated to reflect the committed changes.