Vector algorithm need to know the correct wording

[hivelaser]

Have a question quick, i remember there was talk before about some vector ... algorithm that is used to optimize the path the scanner has to travel for drawing the laser images we generate. I can not for the heck of it remember what it was called, can someone chip in if they remember? basically makes it easier on the scanners.

I remember bill was talking about it.

[FutureDesign]

It's called the "traveling salesman problem" and there are numerous optimization algorithms for that exact problem. Google TSP to find solutions and code.
Actually, its TSP with a twist as TSP assumes that the salesman has to make a full stop at every waypoint, however with laser (vectors) the problem is a bit more complex as fx. lines that are collinear will make a better choice than a closer match but in opposite direction. Makes sense?

I have written an ilda (or whatever) optimizer implementing one of the TSP algorithms, but at this time, its not open source. However it can be made available as a library. It even optimizes in regards to previous and next frame and acceleration/deacceleration (mechanical inertia) parameters of target scanners.

[hivelaser]

WoW great, thank you for posting this, i will PM you quick to show what i am up too...

[JohnYayas]

There is a difference between TSP and frame optimization in that with TSP only the points are given. In a frame, segments are given and the idea is to connect all segments with the shortest path. The difference being that in case one a "city" is represented as one location. In the laser problem, the item visited actually has two locations (a start and an end). With TSP, none of the paths are defined. In laser images, the lit paths are predefined since they are the cities to be visited. The blanking lines are the ones that can be created. I never fully wrapped my head around how to implement it so I created something on my own.

One interesting thing I found when optimizing paths in real time is that if the order of the segments is changed dramatically or if the laser image is even drawn in the reverse direction then what you see on the wall can look different due to not being able to 100% compensate for modulation delays, physical characteristics of galvos, etc. It's really apparent when approaching the speed limits of the galvos. At slow speeds you might not even see it. This can especially become apparent in animations if the path taken from one frame to the next is different due to optimization.

Anyway, not attempting to throw out any solutions to problems here... just mentioning some observations I have made.

[FutureDesign]

There is a difference between TSP and frame optimization in that with TSP only the points are given.

I have to disagree with you. The problem is in fact TSP and what you are describing as actually a part of the TSP problem (directed graph). A salesman often has prearranged meetings that his route can't divert from. However, the rest of the stops can be taken in random. Transferred to the laser problem, the visible laser paths can be looked at as predetermined routes. The visible paths endpoints can be looked at as the pool of cities that can be visited in random.
If you insist that the problem is not TSP, then please tell that to the implementation that I did using a commonly known TSP algo :-D

In a frame, segments are given and the idea is to connect all segments with the shortest path.

That is not correct. The shortest path is not always the best choice. Actually, it rarely is. Did you read post #2?

One interesting thing I found when optimizing paths in real time is that if the order of the segments is changed dramatically or if the laser image is even drawn in the reverse direction then what you see on the wall can look different due to not being able to 100% compensate for modulation delays, physical characteristics of galvos, etc. It's really apparent when approaching the speed limits of the galvos. At slow speeds you might not even see it. This can especially become apparent in animations if the path taken from one frame to the next is different due to optimization.

I think that you see this kind of behavior after your optimizing because you only optimize in relation to distance between visible path. If you want to improve your optimization algo, then you may want to read up on TSP and weighted graphs.

Now I might as well make my software open source, as the secrets is out :-D

[james]

I think Gary is right. Once you add all the caveats to the TSP so it makes sense for laser display it isn't the TSP anymore.

My code looks at the ends of all the lit segments and threads them together based on not just proximity but also the angles. It calculates how many dwell points it would take one way or another and tries to find the order that produces a frame with the fewest vertices. It also knows how to reverse the stroke of a lit segment so that it can use either end as the start or the end. Some of the parameters it uses are settable and effect the final order of the art. It is even possible to split every lit segment into individual vectors and randomizes them before sorting them and bonding them back together. This means that closed shapes can change their entry and exit points. It also optimizes from the last point of one frame to the first point of the next.

BTW all of this has been in my open source code for many years.

James.

[FutureDesign]

I think Gary is right. Once you add all the caveats to the TSP so it makes sense for laser display it isn't the TSP anymore.

What caveats? Everything that have been discussed in this thread is part of the TSP problem.
Have a look at: http://en.wikipedia.org/wiki/Travell...lesman_problem. Interesting subjects are: Asymmetric TSP, weighted graphs and directed graphs.

This thread reminds me of a funny quote by Mark Twain and he says:
"All you need in this world is ignorance and confidence, and then your success is assured."

[james]

Well, both Gary and I have created a working example of at least some way to do it and apparently neither of us ever looked at the TSP as a guideline. I know I didn't. I just thought about the situation in laser terminology and put it together.

Maybe it does resemble the TSP. Maybe that was never the tricky part.

Success can also be measure by creating something that actually works and people use.

There are all kinds of ignorance in this world. I am confident of that.

James.

[FutureDesign]

Well, both Gary and I have created a working example of at least some way to do it and apparently neither of us ever looked at the TSP as a guideline. I know I didn't. I just thought about the situation in laser terminology and put it together.
Maybe it does resemble the TSP. Maybe that was never the tricky part.

Well, I believe that you both have done wonderful optimization algos. However, I find it ironic that you both argue against TSP even though you obviously don't know the fully extent of TSP. We can call it anything we want and we can implement it in 1000 different ways. But it's difficult to argue against that most computer scientist call it TSP.
Anyway, I think we are wasting our time here... I'm out.

[JohnYayas]

Well, I believe that you both have done wonderful optimization algos. However, I find it ironic that you both argue against TSP even though you obviously don't know the fully extent of TSP. We can call it anything we want and we can implement it in 1000 different ways. But it's difficult to argue against that most computer scientist call it TSP.
Anyway, I think we are wasting our time here... I'm out.

I never argued against TSP. I just said I never got how it applied to vector optimization. If you made it work, then that is great. No need to be insulting.