Closing up some loose ends.

Even though everything (mostly) works at this point that are still some things I would like to improve.

What is happening in this sequence?  Planes just seem to disappear.  What happened is that plane 6 was seen early by x2 because there is no occlusion and the frustum is large, although this would happen if it was an open space.  Because it was seen so early in x2 by the time the robot is where it is in the pictures plane 6 ran out of storage (1200 iteration I think) and x2 could not compute.  There are two solutions and both of them are used.  The first is to have a rule that a plane has to be seen at least a certain amount of times to be included in an xpoint.  In this case plane 6 was seen just a few times.  The other rule would be to store the "best" previously calculated instance of an xpoint and use it as a backup when this happens.

The two pictures show exactly when plane 6 is seen for a brief instance.  So how to remove it if it has only been seen a few times?  I could restrict adding new planes until they are a minimum amount of time but then this problem happens

After completing the motion model I retested it  with the non motion model test run and I noticed it wouldn't work.  There was one issue with that some keypoints weren't getting generated.  The first time is was a bug with the rltplaneinterval copy constructor.  The other time it was due to plane 6 being added to xpoint 0 when it only had one iteration which is was on the plane with plane 5.  To make it worse plane 5 was used to compute plane 6 xreference.  Since it isn't possible to do keypoints with only one iteration this caused the above failure.  The problem was compounded by the fact that plane 6 is used to link to x0 to x2, and x3.  Half of a solution was to force any linking planes to have at least a certain amount of intervals and this at least somewhat fixed the problem as eventually one xpoint got it right in time (although not x0).

I realized that the problem is that plane 6 should not be considered part of x0, and to do this I would calculate x0 for enough iteration to determine plane 6 is not working out.  Then I would roll back time and note that plane 6 should not be in x0.  I think I have to roll back time rather then adjusting where plane 6 is linked to because other stuff could happen that makes it difficult to predict any future bugs.  Since I'm only rolling back a few iterations it shouldn't be that intensive even though I have to redo the iterations completely.

The other thing I might do is figure out a better way to match planes to intervals.  I'm thinking of picking one plane, then finding the plane with the greatest overlapping interval.  Then finding a plane that attaches to either of the two planes with the next greatest interval etc.  This should maximum the interval size at the expense of processing time.  I haven't decided if I will implement it, I guess if I have the time. (still not going to implement it at this point since it is expensive in terms of processing and the current way is still decent)

Roll back system

So the solution was to have some code when calculating the xpoints that after say 20 iterations make sure a plane is at least calculated over 10 iterations.  If it is not roll back and have the plane not added to the xpoint.  Also if on the second time if the plane is added to a new xpoint and it still does not have 10 iterations don't use the plane.

The roll back system was not that complicated.  Pretty much the "state" is stored as planeobjects inside rltplanes.  To roll back I simply had to change the index of the last added planeobject in the rltplane, and that would roll it back.  Then I had to calculate the interval of the rltplane and make sure it should still exist.  If it shouldn't then remove it.  I had a simular process to removing xpoints and xpointlinks which might not exist in the past. 

 Every iteration when planes are added these planes are stored.  I also store which xpoint is current and planes that don't have the minimum amount of iterations to be added.  A fortunate design decision is that rltplanes even if they are never added are still stored in the master list so it made things easier in terms of not having to make new memory objects and delete them in the roll back system itself.

So after the current state has been rolled back I run foward through time again with the stored inputs for each iteration.  I also place a hint saying that at a certain iteration make sure a plaen does not get added to a certain xpoint or does not get added at all.   

This is a pretty good rule to enforce a minimum amount of planes per xpoint, because the algorithm is sensitive to having xpoints with a small number of iterations as this is prone to errors due to noise.

This picture is the corrected version with plane 6 no longer being added to x2.  Note is is just a coincidence that is both cases plane 6 is the one giving problems!

The above two show that new xpoints are creating when rolling back but why two of them?  Originally the hint simply was make a new xpoint rather then don't add it to a certain xpoint.  I changed the code to have it not being added to certain xpoint and the problem is fixed.

Further Issues

This problem is one that slipped by.  Why are there so many xpoints?  There was some code missing when adding globally matched planes it would check any xpoint linked one away from the current one but I neglected to check the current one!  After I fixed it (picture to the right) there were 7 less xpoints in the entire run.  This situation happens when linking xpoints it only uses 2 planes to link so some planes are visible but not a member of the current xpoint.  The problem is is sometimes is not a member of the past xpoint either so a new one is created.  The problem is the start is causes by the first 5 planes showing up at the same starting iteration rather then the furthest one appears later.

Reordering system

Below is an interesting thing.  Originally I thought that when two planes are parallel and cannot generate keypoints then that is fine.  The offsets would still be correct.  However if two coplanar planes with one (plane 4) leaving the view and the other (plane 10) entering the view at the exactly the same rate there is the identical problem of the keypoint not being valid but this time the offset is not valid either.  To solve this I had to put in a reordering routine that after a certain iteration it reordered the order of the chaining of the planes to eliminate this error.  The algorithm used first builds a n^2 matrix of all the planes in an xpoint with all the other planes.  If a plane has keypoints it records the interval size.  If it doesn't it records it as not valid.  After the matrix is constructed then the reordering routine does a brute force to figure out the order of maximum interval size.  It iterates through all the planes and goes through every possible route.  I tested it and it eliminates the issue.

The big problem is that I only check for an ordering which there is a one straight path, e.g every plane is on the path.  A problem could arise where rather then a peer to peer we need more of a star configuration in which one plane carries most of the links.  This would require a rejigging of how the xpoint is calculated too.  The other issue is the algorithm to solve this can't check every path, it needs to check every permutation of every path such that 1->2->3 is no longer valid as it could be 1->2,3.  So after selecting the first plane we need to select every permutation of all remaining combinations of planes that have a valid interval to plane 1.  This is well beyond n^2 maybe factorial time, although I suppose if the valid intervals is sparse it probably were not, but I decided to stop development here because it does not add too much to the project.

XReference saving system

A feature I wanted to add for a while is a way to save the best state of an xpoint so that if we run out of plane storage we still have the best information available.  The way this was done is two add extra variables in the xpointreference to have a backup copy which can either be saved from the current and loaded to the current information.  Every time the xpoint is calculated I check to see what is the total current plane size in all the references.  If it is bigger then the backup save the information to backup.  Otherwise load from the backup.  Also load the backup when the xpoint could not calculate.  This happens when there is not an overlapping interval for two planes due to circular array which holds planeobjects.  

Note that it backups reference all together.  I tried to backup individual references but then I realized that the xpoint could change its location which would invalidate the references.  Saving them all together prevents this.  It might be possible to save individual ones but then I would need to save extra information on the other plane of the reference and then reconstruct if there are any differences of plane size from one reference to another.  I do this when linking xpoints anyway but it might not work if we have two intervals where neither has the maximum size plane.  The current way is more in the spirit that an xpoint should contain only planes that are visible together.  

To test this I reduced the planestorage from 1200 iteration to 300.  This sped up the computation quite a bit.  It did work but it led to other problems.


In the left picture when the motion model is done the xpoint selected is 6 not 0.  I think the reason why x0 is not selected has something to do with the code which adds global matches to the current xpoint, as it was not there before.  The reason why plane 1 never extends itself is because it is only linked to x0 (x6 can't take it because it is viewed too late to be a member). and x0 does not have anything else in that interval because plane 2 is getting ignored due to plane 8.

The quickest solution is to merge plane 8 and 2 and then x0 will be recognized as the current xpoint because it contains plane 1,2,3 where x6 only contains 2,3.  The problem is that when there is noise the plane might not merge that well.  

Instead I decided to add some code in when closing a loop, to link plane 8 to x0 not for computation reasons, just so it has a reference when finding the current xpoint.  Since x0 would now have plane 8,2,3 it would have 3 matches to x6 2 so then the planeobjects would get routed to plane 2 not 8 and the problem is solved.  The algorithm simply looks at global matches when there are two similar ones (plane 2,8) put a reference in plane 8 that makes it count towards x0 viewable total.

When I was adding the above features I would have to constantly retest against both simulation to makes sure nothing broke.  Here is video after all the changes.