The Pursuit for Paths
ThreeDee
 |
Seems to be going in that direction. Meanwhile, here's the next step on the tree. now I seriously have to optimize the path drawing function, for it takes longer this way than without scripting! |
|||
| Posted: April 10, 2012 3:37 pm | ||||
xirja
 |
Oh dear, molasses. I was hoping you were on some old machine. As soon as 'BitMap Buffer' and 'Table Memory Limit' are feasible, then matrix math can be used and then no more 'while' function to step through right? | |||
| Posted: April 10, 2012 4:45 pm | ||||
|
ThreeDee
|
Well, yes. But first, I have a different issue to deal with, which is that the script does the full math to calculate the distance of every line segment at each point. If I first check whether the current point is within the bounding box of the path segment (including line weight) and skip those that aren't, I should be able to speed up the process considerably. | |||
| Posted: April 11, 2012 5:56 am | ||||
CFandM
 |
Some Great work ThreeDee..  Stupid things happen to computers for stupid reasons at stupid times! |
|||
| Posted: April 11, 2012 8:39 am | ||||
Sphinx.
 |
ThreeDee... FYI:
http://blog.gludion.com/2009/08/dista...curve.html Btw. I have a 570% faster version of your sine-o-graph running now I will publish when readyNjyldgarkn sample cache! |
|||
| Posted: April 19, 2012 2:21 am | ||||
SpaceRay
 |
WOW! this is really a good optimization and good news. Thanks very much. |
|||
| Posted: April 19, 2012 2:40 am | ||||
Morgantao
 |
Mah... Less than 600% is not that fast 
Very nice Sphinx. Is the faster filter done only by optimizing the LUA script, or is there anything else? |
|||
| Posted: April 19, 2012 4:20 am | ||||
|
Sphinx.
|
Yes its all in the script. I use several optimization tricks. I will publish later on Njyldgarkn sample cache! |
|||
| Posted: April 19, 2012 4:27 am | ||||
|
Morgantao
|
Actually, if it's all in the script, I won't see the difference...
It's like you'd tell me that now the script is in Cantonese instead of Mandarin |
|||
| Posted: April 19, 2012 4:44 am | ||||
|
SpaceRay
|
Exactly the same for me
BUT I do not care, at least I can use this without knowing how it works. |
|||
| Posted: April 19, 2012 2:39 pm | ||||
|
ThreeDee
|
Hi Sphinx, Filter Optimizer in action! There are definitely many ways of optimizing it, starting from scripting the sine inputs as slider inputs into the script rather than reading the grayscale images. Although I do like visually seeing (in the Editor) the corrspondence between the input and the result. And of course the path drawing function as described earlier. Did you figure out additional ways to optimize it? Yes, I read that article recently -- although not the linked "solution to 3rd degree equation" that was in French -- and was considering the option of using quadratic curves (rather than cubic) for some future auto-bezier type path drawing filters. Did you already manage to script that solution with lua? TD |
|||
| Posted: April 20, 2012 10:41 am | ||||
|
Sphinx.
|
Actually I posted that link before looking into the actionscript implementation. Just a brief look reveals a very expensive implementation - not suitable to run W*H*Points time..
About the optimizations: I still use the map input, but I use the initialization trick to fetch the points needed for the overall rendering. When you have the points, you can do various precalculations also. The initialization trick used to be even more efficient, but changes in the scripting engine made it slower (now it initializes for each block in each thread, not just once). It is still better than fetching all the points for each sample. I then made sure that the use of all these expensive math functions were limited to an absolute minimum. Stuff like math.sqrt inside a loop is something you want to avoid. And the algorithm were simplified a bit.. I applied several other optimization tricks - most described in this article: http://filterforge.com/wiki/index.php...and_Tricks The attached version renders in 32 sec (vs 7 mins 33 sec original) Note that it is WIP - I'm currently working on some sort of z input (or scale input) so the gradient might not be 100% identical to your original Sine-O-Graph One - Sphinxmorphed.ffxml Njyldgarkn sample cache! |
|||
| Posted: April 21, 2012 5:13 am | ||||
|
ThreeDee
|
Geez, this is pretty pro programming -- you've definitely read your lua manuals. I had no idea you could do many of these things with this language.
Apart from the overall neatness of the code, I like how you got the minimum distance and took the square root only at the end. I'll definitely incorporate the improvement into my other attempts along this line. Thanks! TD |
|||
| Posted: April 22, 2012 12:23 pm | ||||
|
ThreeDee
|
Ok, now that I've read the code line by line, I have to admit, I'm not sure I follow it everywhere. As far as I can tell, you are calculating the squared distance first and using it to determine which segment is closest. I'm not sure what you are using the variable "r" for, or the reciprocal of the squared distance for that matter. Is it needed because were in the range of 0 to 1 or more directly in the distance calculation?
At least I can't picture it all in my head. Perhaps I should graph it out. I get that the az is not really used as yet. I imagine you could use it for either z depth of for variable line weight. TD |
|||
| Posted: April 22, 2012 1:52 pm | ||||
|
ThreeDee
|
Now, you're using a rather large table here. I was scared off table usage by the "table memory limit" thread. Is there a safe upper limit to a table size you can recommend? | |||
| Posted: April 22, 2012 2:05 pm | ||||
|
ThreeDee
|
That flash implementation of distance to a quadratic bezier curve is, by the way, wrong -- it doesn't find the closest point, just the closest point that is at 90 degree angle fr om the curve segment, which becomes rapidly apparent when you test it with the included flash app.
For instance, it gives the below solution, wh ere the yellow dot on the curve is supposedly the point on the curve that is closest to the red circled dot.  |
|||
| Posted: April 22, 2012 2:16 pm | ||||
|
xirja
|
Wow, nice to see voronoi here. What the two of you can do with this one, I'm excited! | |||
| Posted: April 22, 2012 3:11 pm | ||||
|
Sphinx.
|
Heh, yeah the downside of the optimization is that the script is a lot harder to read.
Variable r is simply used to determine the segment length: if inside 0..1 range we're between a and b (I think you used a similar approach?). Actually the ramp btwn a and b (the value of r) could be useful as an additional output. About the table: no that one is not big - its only a 1D table with up to 1000 entries. The table size debate is about w*h sized tables :-S I can't say what is the recommended size limit. I'd keep an eye on the memory usage and performance and then as a general rule of thumb: as long as you're dealing with 1D arrays with a few variables per entry, don't worry about the size. The reciprocal variable is simply to avoid expensive divisions inside main inner loops, i.e. use a*(1/x) instead of a/x, where 1/x is precalculated. Btw. check out this script http://forums.codeguru.com/showthread.php?t=194400 I used it as reference implementation, and it is not "ruined" by too many optimizations. About the bezier stuff.. yeah its no good. I'm afraid there is no continuous solution and we need to generate the whole point series and check one by one. Bye bye performance... Njyldgarkn sample cache! |
|||
| Posted: April 23, 2012 2:22 am | ||||
|
ThreeDee
|
Yeah, I know. I can rarely even understand my own scripts coming back to them after a few months. And as to optimization... let's say I have plenty of room for improvement there.
It is definitely good to have a few solutions to compare. Actually it could be a fun and useful optimization challenge to come up with a certain bezier-curve related objective and challenge all resident scripters to come up with the fastest implementation. How about a challenge for the best optimized cubic bezier curve with variable line weight and variable quality setting (flatness value, i.e. number of line segments that make up the curve)? For proper comparison we would also need a reference set of values for the four points, the line weight and quality setting (number of line segments). TD |
|||
| Posted: April 25, 2012 3:31 pm | ||||
|
ThreeDee
|
Here's another thought I woke up with this morning. What if we approximated the bezier curve with arc segments instead of straight lines? It is not much more calculation, but we would get very smooth curves at low quality settings. Even 8 segments would give a very nice result if they were done as arcs instead of lines. |
|||
| Posted: April 26, 2012 2:55 am | ||||
|
ThreeDee
|
In my estimate this would require calculating three lines for each point pair: the normals for the two points (call these A and B) and a line (call it C) that was equidistant from the two points. The center of the circle would have to be on line C, and a good solution for its location would probably be the average of the crossing points of (A and C) and (B and C). What do you think?
The largest deviation from the actual bezier path would be at the sharpest turns which would be somewhat rounded off. |
|||
| Posted: April 26, 2012 3:02 am | ||||
|
Sphinx.
|
Interesting idea - That could greatly limit the number of points needed to inspect.
As you say we would get an infinite number of possible center points on the perpendicular bisector, but with three points from the bezier segment it might be possible. I.e. instead of finding circle center C from A,B, we find circle center D from A,B,C (circumcircle of a triangle, http://local.wasp.uwa.edu.au/~pbourke...clefrom3/). Since the bezier path generation itself can take place in an initialization section, we don't have to worry too much about generating some extra points.. Right now I'm a bit worried about what comes after... i.e. how to get a continuous line rendering from the circle distances Njyldgarkn sample cache! |
|||
| Posted: April 28, 2012 1:49 am | ||||
|
SpaceRay
|
what happened to this ?
Is there any further development and possible examples? I am not personally interest in this myself as I do not understand it and can´t use it, but I think that anyway is interesting and cool to see about this and what can be done |
|||
| Posted: February 15, 2013 2:40 am | ||||
Join Our Community!
Filter Forge has a thriving, vibrant, knowledgeable user community. Feel free to join us and have fun!
15,407 Registered Users
+10 new last day!
112,685 Posts
+20 new last day!
10,109 Topics
+8 new in 7 days!
Recent Forum Posts:
- Batch Rendering Wrapper by SpaceRay
few minutes ago - Beta Gallery by SpaceRay
10 minutes ago - Good News! New FF 4.004 and ENABLES submission of filters to library! by SpaceRay
15 minutes ago - mw_Petri Dishes & Liches by marwyn by Dave S
2 hours ago - FF 4 beta by Apophis
3 hours ago - Flouresecnece Image Merger-Blue Green by uglyboys by TBH-1138
4 hours ago - FF should make an iPhone app! (warning: crazy idea) by joel collins
8 hours ago - Colored Plastic Tiles by Qender by TBH-1138
today - Rendering Manager Bug by CFandM
yesterday - Contest on DeviantArt by Burt
May 22, 2013 - Pseudorandom by ThreeDee
May 22, 2013 - Random Variation by ThreeDee
May 22, 2013
Recent Wiki Edits:
- Indigo_
Ray by Indigo Ray
February 25, 2013 - Optimizing_
Filters_ by Crapadillafor_ Speed
February 22, 2013 - Feature_
Wishlist by Crapadilla
September 19, 2012 - Main_
Page by Crapadilla
September 19, 2012 - Filter_
Construction:_ by CrapadillaFundamental_ Techniques
September 19, 2012
