Point Optimization

[mikkojay]

I am discovering the significance of optimization when it comes to point order in an ilda frame, i.e. a simple frame might look like crap if your points start and end all over the place.
Has anyone written a conversion algorithm that will
a) optimize points
b) generate appropriate blanking lines
?
Here is a quote from a commercial frame editor's page that mentions what I am talking about:
" Another advanced feature of Anarchy editor is optimisation. Usually, when you draw something, you don't care about how the beam will walk over your image. You begin to worry when your simple image looks poor even on fast scanners. What happens? You simply forgotabout the path of the blanked beam. It's invisible, and you think that scanners can quickly jump from the end of one line to the beginning of another, missing the fact, that your scanners make a lot of hard and sometimes unnecessary work while drawing your image. Anarchy Editor solves this problem in seconds. The optimisation algorithm reorders the points in your image to minimise the path of the beam. It also adds necessary anchor points in the corners depending on the corner angle - more points at sharp angles, and less at obtuse angles - this allows you have good quality images on any system. Just draw what you want in any way, Anarchy Editor will carryout all the dirty work for you to make your image perfect."

Any input would be appreciated. I can see how any frame that is programmatically generated MUST fall though an algorithm like this if you expect the end output to be usable. If I were to write something like this from scratch, I might be in for a series of all-nighters, so I was hoping someone out there might have something to get me started.

Thanks, Mike

[carmangary]

I'm also interested in solving this.

[allthatwhichis]

If a professional program has listed this as a feature, it may be an exspensive question to solve. I'm sure someone here has done it; I for one can barely optimise code itself();

[mikkojay]

Another interesting concept is- what pattern would the scanners prefer?
You would think that starting with 0,0 and growing outwards would make sense. Then there is a raster approach, snaking from left, right, down, repeat.
Then, I have the opportunity to keep points together that comprise polygons- man, this can get pretty detailed-
Hmmm.

[carmangary]

It isn't really a hard problem. Using just brute force vector points can be optimized based on vector distances and angles between vectors. Vector order can be optimized by iterating through all possible combinations and using the order that yields the shortest sum all paths.

If a professional program has listed this as a feature, it may be an exspensive question to solve. I'm sure someone here has done it; I for one can barely optimise code itself();

[mikkojay]

Here is some interesting reading:
http://en.wikipedia.org/wiki/Bresenham's_line_algorithm

[carmangary]

Although I can't think of a useful application of that for laser show software, it is interesting because there have been times that I needed to do that. Especially when I had a TRS-80 and pixels were as large as ladybugs. But, on the other hand, memory was too expensive to be using those kinds of algorithms.

[mixedgas]

OK here it goes , industry standard terms, but not exactly the stadard daffynitions.

Corner point, added to sharpen a corner or other sharp turn , typically 2-3 points added right at the corner.

Anchor point, the scanner is returning from a large jump at the limits of its performance , and my not consistantly land at the same place, adding a few blanked (sometimes not blanked) anchor points at the end of the large jump
guides the scanner in so you dont see random wiggles at the start of the unblanked portion.

Guide point, added to large jumps to keep the scanner on track and control velocity.


Laser software modes VECTOR and Normal or point to point.
(all laser graphics are vector, not raster graphics , but the show industry uses vector for a slightly different meaning then the computer programming types )

Point to point, the software jumps to each data point in the frame with no
smoothing or precomputation, just dump the data to the dacs. Try to update x and Y at the same time though or it looks jagged, the simultainous update is done in hardware.

Vector, the CPU computes in real time lots of small jumps from the raw frame file,making a smoother waveform that can push up scanner performance.
Vector is more expensive and requires better, faster, smarter, hardware.

Although dependant on how you tune your scanners, a general rule is big jumps without guide or anchor points looks bad!

Anarchy resizes the jumps and adds/subtracts points as needed, plus adds corner, anchor and guide points.

Thats the basics, I sure Bill Benner will jump in with more, as Pangolin does both.

BTW< there is no optimatization based on X-Y distance from center, its the jump to jump distances that are important.

Steve Roberts

[mliptack]

Hey Steve,

Thanks for all that information, that really helps out! I have been wanting to get into more drawing of my own frames and that adds a lot of insight.

And I hate to piggy back but I am using LA Studio from pangolin with the FB3 and am having issues when I use the program DRAW3D. When I use the circle tool to make an ellipse for some reason the circle draws back over itself. Let me elaborate further:
The circle I draw will have about 1/4 overlapping itself then it creates a retrace to the original starting point. Of course I have blanking so, the retrace line isn't visible but the 1/4 of the circle that is drawn twice as much is quite a bit brighter. I have tried deleting the double amount of points but I end up with one brighter point. Does anyone know how I can fix this? Is there a software update I haven't received?

-Max

OK here it goes , industry standard terms, but not exactly the stadard daffynitions.

Corner point, added to sharpen a corner or other sharp turn , typically 2-3 points added right at the corner.

Anchor point, the scanner is returning from a large jump at the limits of its performance , and my not consistantly land at the same place, adding a few blanked (sometimes not blanked) anchor points at the end of the large jump
guides the scanner in so you dont see random wiggles at the start of the unblanked portion.

Guide point, added to large jumps to keep the scanner on track and control velocity.


Laser software modes VECTOR and Normal or point to point.
(all laser graphics are vector, not raster graphics , but the show industry uses vector for a slightly different meaning then the computer programming types )

Point to point, the software jumps to each data point in the frame with no
smoothing or precomputation, just dump the data to the dacs. Try to update x and Y at the same time though or it looks jagged, the simultainous update is done in hardware.

Vector, the CPU computes in real time lots of small jumps from the raw frame file,making a smoother waveform that can push up scanner performance.
Vector is more expensive and requires better, faster, smarter, hardware.

Although dependant on how you tune your scanners, a general rule is big jumps without guide or anchor points looks bad!

Anarchy resizes the jumps and adds/subtracts points as needed, plus adds corner, anchor and guide points.

Thats the basics, I sure Bill Benner will jump in with more, as Pangolin does both.

BTW< there is no optimatization based on X-Y distance from center, its the jump to jump distances that are important.

Steve Roberts

[The_Doctor]

Points can be confusing, some systems make them regular in time, in which placement in a frame easily defines how they affect the speed of travel. I prefer that approach, as it's also the easiest to convert to sound card output which can allow for what Steve describes as vector output. It's actually possible to do that, and add a linear interpolator to a point by point scheme to produce a very smooth vector output. Quite easy to code as well. The interpolator is the thing that demands heavy number crunching hardware, especially if it's advanced enough to go beyond linear with user specified step size, and becomes able to optimise curves to handle accelerations to favour a better image rendering, based on the angles and distances it's being asked to draw lines to. It might be possible to implement everything but that in an interpreted language except that interpolator and its output stream to the scan driver via sound card or other DAC.

Another curiosity is that no matter how sharp the corners, the WideMove scanners will ideally have all dwell points of equal duration. I use 9 consecutive samples which equaltes to a heavier pause than Steve mentioned, assuming he's talking of a regular point rate (as opposed to variable). I'd use less for guiding curves, but there's no doubt that when I want a sharp vertex the image renders better if ALL sharp vertices have equal pauses. Could be different for other scanners though.

We really do need a programming subforum, this thread belongs there already.


EDIT:
Never really addressed the question... So, point optimisation in the sense of basic tracking for efficient coverage of a frame is not actually that trivial. It's mathematically intractable, which in this case is another way of saying computers can't do in ten years what we can see easily in a couple of minutes. It relates to the 'travelling salesman' problem, though in practise it's probably much easier to solve, as many parts of the route are predefined by visible draws. A similar thing is done in programs that use vector output to draw circuit board tracks on a plotter, but be aware that some, even the expensive professional tool GerbTool do this badly. That same program does a better task of drill tool movements, but that idea might not help you, I suspect their plotter output is based on that same idea, and what works for arbitrary points does NOT work well for points on already defined lines, unless you plan for that, so even if you find some opensource code you might have to adapt it extensively by adding more.

Far easier to figure out for yourself, do it long enough to establish some good habits, then code those to automate stuff. I'd never try to code an AI, I'd only code the regular stuff I found useful, but tiresome due to repetition. Computers are better at that, and if you learn good habits they'll still appear smart.