Polygonize image using Sverchok

Ribel78 commented 6 years ago

Problem statement

Recently I was playing with ways to create Polygonized image effect in Blender. And decided to automate it using Sverchok. Below I present my node tree and I would love to hear your opinion and even advice for improvement of the speed of the calculations. Currently the calculations use static mesh, but I would like to improve on this too by generating different types of meshing - rectangular, triangular, voronoi pattern etc.

Steps to reproduce

Screenshot:
Download .blend file: SV_UV_2_VCOL - 03(numpy)_01_2018_01_26_11_48.zip

Expected result

I decided to use numpy node at some point to speedup the calculations

Actual result

Despite improvement of the speed replacing lists with numpy arrays it is still slow on large sized images and hi - polygonal mesh.

Sverchok version

SV 0.5.9.6 (b546794)

zeffii commented 6 years ago

Cool. Some remarks before opening it.

Whenever the node tree updates, it tries to update as little as possible. However, when the tree is being told to do a general update, or one of the nodes that's asked to update happens to be at the very "tip/upstream" in the tree, the result is still that anything downstream is recalculated.
The act of obtaining any array / numpy / list from img.pixels is slow. img.pixels[:] is faster, but as you start to increase the pixel count expect the speed of "transfer" from pixels to array/numpy/list to increase non linearly (prove it, don't wait for me).

A workable approach is to forget the notion that this will work in (near) realtime for 'unseen' images (not without custom implementations.. binaries..etc ). Instead if you can cope with this just working on a static image, it is possible to cache the pixel array (in ram.. or on disk..) and remove that hugely CPU intensive step.

It would be awesome if Blender had a function to obtain a numpy array of the pixels, but i'm not aware of any movement toward that.

I know @ly29 has done something similar in the past with nodes
- https://github.com/nortikin/sverchok/issues/831
- https://github.com/nortikin/sverchok/issues/859
I also did the vertexcolor map stuff (but not with automatic polygon mesh creation..)
Another interesting mode might be a dithering mode with a simplification step prior to Delaunay.

Also, consider that there's a massive amount of information being rejected by the cubism effect anyway, and that you could sample every second pixel instead then generate the polygonmesh..

ly29 commented 6 years ago

Yeah. img.pixels is a super bad interface.

Of course image manipulation in python will always suck a bit...

Caching the processed image output is a dramatic speed up definitely worth the extra code.

Ribel78 commented 6 years ago

I attempted to load the scripts of @ly29 but they gave me an error during loading. Also I am not as advanced in Python to understand the scripted nodes completely.

I tried replacing pixels with pixels[:] but the process slowed down drastically (1920x1080 image) pixels is from class bpy_prop_array pixels[:] is a tupple I assume selecting pixels check box in Object ID Selector does the conversion to tuple. But it is not needed as I am pushing the data into numpy array. So the first option is faster

I can accept that this node tree is not animation friendly but if as @zeffii said re-sampling of the image data may improve the speed the user can manipulate the image externally and use it instead of the original.

I would like to ask you to try using different arrangement of nodes to complete the same task. Maybe from that we can squeeze additional speed up?

zeffii commented 6 years ago

but if as @zeffii said re-sampling of the image data may improve the speed the user can manipulate the image externally and use it instead of the original.

like a proxy, yep :/

I would like to ask if you to try use different arrangement of nodes to complete the same task. Maybe from that we can squeeze additional speed up?

I fully intend to, time permitting!

zeffii commented 6 years ago

and yes you are right, the Object ID Selector node does output pixels directly. Shown in this snippet of the UI code

https://github.com/nortikin/sverchok/blob/a553a3436b0ec550f9c1efe7e38cb57dc72497b1/nodes/object_nodes/get_asset_properties.py#L168-L172

but implemented here

https://github.com/nortikin/sverchok/blob/a553a3436b0ec550f9c1efe7e38cb57dc72497b1/nodes/object_nodes/get_asset_properties.py#L202-L210

meaning you can get pixels already directly from there. Also notice my annotation beside the code, pre-empting the need for an output of width/height somehow.

zeffii commented 6 years ago

The best way to get a real grip on these nodes is to use them, and if they do something you don't understand then read their source. There's a chance you will answer your own questions, and at the same time give us reason to return to a node and upgrade it - if it needs boosting.

Ribel78 commented 6 years ago

The best way to get a real grip on these nodes is to use them, and if they do something you don't understand then read their source.

When I click view source button "external" it gives me an error:

Traceback (most recent call last):
  File "\2.79\scripts\addons\sverchok-master\ui\development.py", line 192, in execute
    subprocess.Popen([app_name, fpath])
  File "\2.79\python\lib\subprocess.py", line 676, in __init__
    restore_signals, start_new_session)
  File "\2.79\python\lib\subprocess.py", line 955, in _execute_child
    startupinfo)
OSError: [WinError 87] The parameter is incorrect

location: <unknown location>:-1

zeffii commented 6 years ago

ah, yes you need to configure your external Code viewer..

https://github.com/nortikin/sverchok/issues/1776#issuecomment-328330129

btw, I don't have major issues with your implementation in the .blend , only issues that I could address in the code of certain nodes .

SV_UV_2_VCOL - 03(numpy)_01_MOD_2018_01_26_16_03.zip

zeffii commented 6 years ago

I don't recommend editing the code, until you spend more time reading the rest of the code base .

zeffii commented 6 years ago

ps.. isn't b2.79 Release Alpha released, yet. My blend uses RGBA :)

Ribel78 commented 6 years ago

@zeffi Added Text editor, can view source now. In the official 2.79 I had to remove the parameter for alpha:

-    VC.append([r, g, b, 1.0])
+    VC.append([r, g, b])

and set the Vertex color m3 mode in Properties to RGB, and it works! Also using one Exec Node and without converting data looks prettier!

I am planning to write tutorial on this topic and will include the best Sverchok solution from here.

zeffii commented 6 years ago

maybe @Kosvor2 and @nortikin

Ribel78 commented 6 years ago

@zeffii Is there a way to compare speed (variant 1 vs variant 2)?

variants

I am still convinced that using Object ID Set MK2 for pixels data is faster than checking the option "pixels" in Object ID Selector and converting it to tupple. Using larger images makes the difference obvious - Variant 2 is 3-4 times faster than Variant 1. Another disadvantage of Variant 1 is that you have to replace the Image twice as opposed to once in Variant 2.

enzyme69 commented 6 years ago

Can debug print timing from add-on preferences if not wrong....

Ribel78 commented 6 years ago

@enzyme69 Thanks for pointing that out!

For image 5760x3840, using sverchok.log gives me (excluding debug statements / errors during rewiring)

Variant 1: Approx. 52 s.
Variant 2: Approx. 16 s

zeffii commented 6 years ago

if 2 is faster, then let's look at why. I suspect the slowdown is the fact that two instances of Object ID Selector are doing lookups on bpy.data.images[ ]<.stuff> .

just as a test try using 2 A number nodes to set the width / height of the image instead of using the Object ID Selector. (this means you remove one Object ID Selector) .

zeffii commented 6 years ago

The more that can be done inside a single node, the better. We could even provide a second tickbox for

   [ ] pixels   [ ] as numpy array

When we repeatedly need to use a certain set of nodes to achieve an effect, there's good reason to make a dedicated node (or mode) for the effect. This would be such an instance. None of the active devs would do this kind of stuff using nodes alone.. i think.

zeffii commented 6 years ago

maybe even

[ ] pixels  [ ] numpy   [ ] dims

:) and ticking dims would add width / height socket. Or ..maybe a dedicated node.

portnov commented 6 years ago

Here is a bit more about profiling: #1920, #1933 .

zeffii commented 6 years ago

also: https://blender.stackexchange.com/a/3678/47

Ribel78 commented 6 years ago

In Variant 2 - is replacing pixels with pixels[:] the same as checking 'pixels' in Object ID Selector? The slowing down gets even worse this way.

zeffii commented 6 years ago

is replacing pixels with pixels[:] the same as checking 'pixels' in Object ID Selector?

yep. that's what the code does. well.. almost. If you don't tick pixels it passes [[img]], with pixels ticked it passes [[img.pixels[:]]] . Look again https://github.com/nortikin/sverchok/issues/2090#issuecomment-360817029

it should be faster to use, but ... when is anything "predictable" : ) ?

zeffii commented 6 years ago

the speedup (according to the knowledgable answer on BSE) comes from the readonly reference generated by pixels[:]. I'd need to write a script to test this to remove "sverchok" from the equation. It could be any number of things unless one writes a compact script to do it, you'll not understand it (neither will I )

zeffii commented 6 years ago

" accessing data inside a numpy array is relatively slow if you're trying to just grab it by index. " (reference: http://zwmiller.com/blogs/python_data_structure_speed.html )

zeffii commented 6 years ago

so i might be that pixels[:] without then passing to numpy array is faster. (only one way to be certain)

Ribel78 commented 6 years ago

For the skeptic baby image:

pixels[:] without passing to np.array - 0.482 seconds

pixels[:] passing to np.array - 0.451 seconds

pixels passing to np.array - 0.078 seconds

I think we have a winner.

Ribel78 commented 6 years ago

I have another problem to solve.

If I want to use Delaunay for mesh triangulation or any other planar mesh manipulation I don't find a way to insert UV data in the output object using nodes.

Is it possible to output object containing UV layer?

Blender's UV -> Unwrap operator should be fine for planar UV maps.

zeffii commented 6 years ago

also the code in exec might have varying speed ups if you try a few variations

# current
VC = []
for i in V1[0]:
    r, g, b = V2[0][4*i:4*i+3]
    VC.append([r, g, b, 1.0])
append(VC)

# alias the append
VC = []
collect = VC.append
for i in V1[0]:
    r, g, b = V2[0][4*i:4*i+3]
    collect([r, g, b, 1.0])
append(VC)

# alias the append, do explicit indexing
VC = []
collect = VC.append
for i in V1[0]:
    idx = 4*i
    r, g, b = V2[0][idx], V2[0][idx + 1], V2[0][idx + 2]
    collect([r, g, b, 1.0])
append(VC)

zeffii commented 6 years ago

(sorry, refresh this page. that last snippet must be modified or it won't work)

Ribel78 commented 6 years ago

The first and the third are equal in speed, the second is slower near 2 times.

zeffii commented 6 years ago

i found a bit of a honking broken feature of execnode while experimenting.. fixing that will be my priority.

i think you'll be fine, armed to the teeth with debug/timer tools.

zeffii commented 6 years ago

reopen if you need to

nortikin / sverchok