It is for a scaling algorithm, and the conversion will be processed several hundreds of times for a single full screen picture. I need to save every millisecond here.

I almost made the scaling algorithm! In fact I even completely implemented pixel replication, but it is awfully slow.
I had an idea though: If I have a list of lines to duplicate, I can simply shift the screen, without shifting anything in, starting at those lines. This will duplicate and render the whole line automatically!

Unfortunately I don't have such an assembly routine, that would do the shifting.
I could either shift the whole screen with xLib and then mask off the modification with may area selection algorithm, which will still require 9 commands + big cleanup.
Or, if some kind assembly programmer could write a routine which can shift any part of the screen in any direction, I could do it with a single library call which will probably be almost instant.

Also, a new idea I had:
When saving a file, you will be able to select fullscreen or not fullscreen (I mean the bottom screen row, which is unavailable in BASIC normally). Just for simplicity, you will always be able to draw on that line, the fullscreen or not setting will only determine whether it is saved.
Or I might just save that line by default and only ask for fullscreen or not when exporting files.

you should also make it so you could export to pictures

The enlarging algorithm is done!
It is relatively fast ()!
I would say currently it takes approximately 2 minutes for a fullscreen picture, at least exactly two minutes at any magnification factor from 2 to 3, which I believe will be the most used.
I am still optimizing it, the runtime could halve I think.
I will post the code today or tomorrow, depending on when I finish optimizing.

Great, I look forward to seeing the code, and perhaps offering any optimizations if I can spot any. It might be interesting to start learning a little bit of assembly at some point as well, because (I assume) this would be an ideal small, integer-based, relatively simple algorithm to transfer to ASM for speed reasons. You'd just need to learn a little bitmath.

Here is the code:


Code:



Code:


I managed to get the runtime down to 1:38 minutes when enlarging by 250%. Still some optimization I can do, as mentioned in the comments, so I suppose to get it down to about 1:30.
It currently only supports fullscreen. Shouldn't be hard to change, though.

Edit:
Optimized, runtime reduced to 56 seconds!
Also it is slightly smaller, but only a few bytes.
Code coming in 1 minute.

I created a probably faster algorithm for scaling up images 200%. This is my code:

Code:

How it works:

Code:

You could modify it for another zoom.
That will look like this:

Awesome work PT_!
I made it work for any magnification factor and it runs 17 seconds for a fullscreen picture.

Code:


But I just noticed this only works fullscreen. I will put the algorithm in the filters section though, it deserves it!

Edit: PT_ also put some code together which made the algorithm work in both directions (shrinking and enlarging). There were some minor problems, though. As soon as I fix everything I will post the code once more!
Also, I think it is possible to use this algorithm for a specific area on the screen. I just need to mask out the scaled part and here we go!
Overall, PT_ did a very good job here, thank you very much for the awesome idea!

Edit2:
I still couldn't solve everything. I noticed the algorithms can't properly scale to every factor.
However, I made a quick draft for a logo:


What do you think?

This was a hard piece of code. Still doesnt work for a factor of x4:


Code:

I solved the enlarging bug with this code:

Code:
Let's start for shrinking...

EDIT: here's the code for shrinking:

Code:
Note that Z > 1 for shrinking, you could change it to 1/Z though.
Now let's combine it into one section.

EDIT2:

Code:

Here is what I got so far:

I erase the bottom and the left rows, so when shrinking, white pixels are shifted in.
However, a weird thing does not work.

Code:


This line doesn't work for some reason, I tried with real(12,0,... and real(12,2,... both gave no result. Seems like something on the screen gets overwritten?

Code:

I made an algorithm to render Bézier Curves!
(More about Bézier Curves on Wikipedia)


Screenies:



Code:

Code:



Explanation:
Takes three points and draws a Bézier Curve between them.
The input "Steps" determines how acurate the curve will be drawn - more steps: Longer calculation time, better and less edged curve, fewer steps: Faster, but worse curve and more edges.
Basically this just says of how many straight lines the curve consists. The more, the shorter they are and the smoother the angles.
I took 20 which makes an absolutely good curve at such a short lenght, probably even 5 would be good enough to notice no difference.

Now there are Cubic Bézier Curves!
These are the same, except that there are 2 "Weight Points" instead of one.

Screenies:



Code:

No comments now, sorry. This code works exactly like the one above, just with a bigger amount of lines and points. Check the Wikipedia page on Bézier Curves for more information.

Also note the rendering time gretly increased - and the step rate too. Just because the curves get longer, 50 was more than enough. However, as you see, 25 gives significant quality loss, so something like 30/35/40 should be good.


Edit:
Optimized the code, now I use complex vars instead of lists and [recursiveN] for the loop variable (Thanks for the suggestions, lirtosiast!). Also I moved a little bit of the calculations out of the loop so it got faster.

The cubic and quadratic curves got 0.33 and 0.177 times faster and a little bit smaller.

I think there's an even faster way to compute the Bezier curves that requires <i>no</i> multiplications in the loop. A real*complex multiplication takes 5 ms or so (don't quote me on that though) but an addition can be almost instantaneous. Given that your current method takes about 150 ms per iteration, drawing the Line( cannot be the bottleneck. Therefore, a faster algorithm can speed it up considerably.

There's a method called "forward differencing", which allows you to basically calculate points through iteration of cumSum( on a carefully constructed complex four-element list, taking the last element to be your new point each time. See this page for the details.

cumSum( has only ~5 ms of list-processing overhead, and the actual summing will be very fast compared to multiplications (at the machine code level, adding has a rst instruction, while multiplying doesn't).

(Hmm, it looks like I'll need to use backwards differences instead to use the cumSum( optimization. Forward is still faster than the old way though, if it works.)

Here's my implementation (now it works! runtime ~1.5-2.5s for a 50 point curve):

Code:

Here's a new, even faster algorithm to generate the list of points for the cubic Bezier curve. Input is four points as complex numbers in L1, and output is the list of Bezier points in L2. Will update with the five-point preview version.

Everything is based on backward differences. Call the constructor points P0, P1, P2, and P3. Call the first point of the Bezier curve B₀, and the last B₁, and the Nth point (starting from 0) B_N/(S-1) so there are S points in total. Now, there's a formula for the points B:

(From Wikipedia)

(sorry for using B as one of my variables)

However, computing these directly is too expensive! We'd need to raise t and (1-t) to powers, multiply them by the P points, and add, for *every single point*. Instead, we can figure out a clever formula. Since this is a cubic polynomial in t evaluted at constant points, it has constant fourth differences (Just read the top two sections). These can be found using a little bit of mathematical trickery from the polynomial coefficients.

The A, B, and C are just the coefficients in the simplified form of the formula above (you can get them just by expanding). So the polynomial, when you expand it, is equal to At^3+Bt^2+Ct+P₀.


Code:

Thank you for the code again, it looks really awesome.
Unfortunately, as I use Doors CS, the sum( token is preserved for one of the libraries.
Is there an alternative?

And a note on the project:
It might look like there is not much discussion about this, but actually we are talking a lot in the SAX widget.
If you are interested in reading or participating, you should register at the registration page.

I'm still working on the scaling algorithm, and I'm now working on a new technology; hope it works.

Code:


EDIT: explanation

I've used the code from the website http://tech-algorithm.com/articles/nearest-neighbor-image-scaling/ , the second one. It is only for the horizontal enlarging though. It was 95/Z, now it becomes 95. That

Code:
is for defining the count of lines for shifting, which is executed in the second For-loop.

J is at which line you must shift.

Okay, so a fter (another more) long delay I am back at this project. I am sorry for so many things that came across it...

So, first, lirtosiast, your code seems not to work correctly, and I am sure I typed it correctly. PT_ also confimed this.


It draws a curve, but a wrong one...
I use libraries, so the real( token is preserved. However this can be worked around with imag([var] * i) so I changed this in the code (But this is not the source of error)...

Thanks for your guys help, I wouldn't have brought it to this point without it!

Nik, you quoted the wrong post above, but I confirm that my most recent code didn't work. I forgot to multiply L1(3) by 3 on the first line. It's fixed now.