Programming Contest: BoxifyMe

[Skybuck Flying]

This sort of technology is used for green screen masking of video.
I worked on such code. You should know that long thin polys can
have horrible performance on some graphics hardware.
A bias toward squarish shapes will give better throughput despite
sometimes more boxes to render.

Entry 5 has a bug, in the center left is a large brown box, that
box should have grown down one pixel into the pink box.

It's not really a bug, it's probably an algorithm inefficiency... from the
high number of boxes it can be seen that wasn't ofcourse efficient and I
tried to point that out... meanwhile that algorithm has been made more
efficient and entry6 proves that.

A truly greedy algorithm should have given up some width to steal
half of the blueGreen boxes space. Bias toward most pixels grabbed.
A 2x10 is way better than a 1x12, etc.

Could be a heuristic.. but doubtfull... area doesn't really play a role that
much... sometimes it might be better to make a line to get rid of those
pesky little pixels/boxes which happen to fall on the same line but just one
pixel different... none-the-less area or ratio might still be a nice
heuristic.

You can probably cut the item count of your render list by a third
by including polys. An area greedy algorithm will leave you with
lots of 3 and 6 pixel right triangles, and similar stuff that
explodes into lots of little boxes.

This is a novel idea, for opengl and physics this could make sense.

It's a bit risky though... if the polygon/triangle because to large and it
has a flat angle like so:

.
.............

Then the diagonal that would result from that would describe too many
pixels...

The diagonal would look something like:

-------
-----.......

So it starts to describe non-existing pixels.


But for very small pixels like
.
...

it might work.

Perhaps also something like:
.
..
...
.....


As long as the pixel describe a perfect triangle/diagonal such an idea might
be possible.

So I will consider it when I start the physics testing !

Thanks for this idea, most appreciated !

Bye,
Skybuck.

 

[Skybuck Flying]

It's not really a bug, it's probably an algorithm inefficiency... from the
high number of boxes it can be seen that wasn't ofcourse efficient and I
tried to point that out... meanwhile that algorithm has been made more
efficient and entry6 proves that.

Actually that's not true... I just remembered entry6's algorithm was changed
somewhat... so it's not considered boxy...

So your points about the "boxy" being inefficient is true... and it wasn't
corrected yet.. since entry6 works a bit different...

Perhaps I will consult opengl newsgroup in future about your statement:

"You should know that long thin polys can have horrible performance on some
graphics hardware"

Perhaps you mean very strange cases where edges lie closely to each other ?

Or perhaps long in the sense of bad memory lookups or so... or perhaps just
inefficient hardware... hmmm..

Bye,
Skybuck.

 

[Skybuck Flying]

Maybe floating point issue's...

Perhaps hardware detects that 12 bit or 16 bit or 24 bit is not enough for
floating point numbers to describe the slopes... so then it might change to
64 bit or something which might be slower.

Bye,
Skybuck.

 

[Skybuck Flying]

A new contester has entered the contest !

And what an entry it is !

The new contester rises to the top spot ! And is now in the lead with only
217 boxes !

He goes by the name of "Rob Pratt"

No further details where provided... I would at least like to know what
programming language was used... this is after all a programming contest


The website had been updated to include Rob Pratt's First Entry.

Will he submit more ?!? Time will tell For now he can sit comfortably
on the throne ! LOL.

http://www.skybuck.org/BoxifyMe/

Bye,
Skybuck.

 

[Skybuck Flying]

"

Hi Skybuck,

I didn't see a deadline mentioned. Is there any chance you can make
it after the deadline for the International Corewar Programming
Contest?

http://www.corewar.info/tournament/icpc1

Thanks,

John
"

I think so.. the contest will probably be running for a while !

Maybe even forever... it's like a King of the Hill contest.

The best programmer/algoritm/entry sits on the throne !

Bye,
Skybuck.

 

[Skybuck Flying]

An interesting development has taken place in the competition.

After carefull analysis by looking at the new visualizations I suspect Rob
Pratt of either:

1. Using the input from James Dow Allen to base his own entry/solution on.
or
2. Using the same kind of algorithm and/or software as James Dow Allen.
or
3. It's simply James Dow Allen pretending to be Rob Pratt.

It's very suspicious to say the least... you be the judge...

The visualizations are at the bottom, the CoordinateMap is a dead give away
me thinks ! Rob's has many similarities/patterns as that of James'es.

http://www.skybuck.org/BoxifyMe/

Bye,
Skybuck.

 

[James Dow Allen]

An interesting development has taken place in the competition.

After carefull analysis by looking at the new visualizations I suspect Rob
Pratt of either:

1. Using the input from James Dow Allen to base his own entry/solution on..
or
2. Using the same kind of algorithm and/or software as James Dow Allen.
or
3. It's simply James Dow Allen pretending to be Rob Pratt.

Well, I suppose it's my word against yours, but I'm confident that
neither of us is impersonating the other, and confident Rob
Pratt would agree!

That the solutions would be quite similar surprises me not in
the least: mine was developed in a very straightforward and obvious
way. I *am* surprised that Mr. Pratt has improved on my score
so dramatically and am anxious to see his solution, but ...

I cannot access your BoxifyMe page today. (Does anyone else have
a similar problem?) Skybuck, Please e-mail me Mr. Pratt's
solution if you have time.

Best wishes,
Rob Pratt^H^H^H^H^H^H^H^H^HJames Dow Allen

 

[Skybuck Flying]

An interesting development has taken place in the competition.

After carefull analysis by looking at the new visualizations I suspect Rob
Pratt of either:

1. Using the input from James Dow Allen to base his own entry/solution on.
or
2. Using the same kind of algorithm and/or software as James Dow Allen.
or
3. It's simply James Dow Allen pretending to be Rob Pratt.

"
Well, I suppose it's my word against yours, but I'm confident that
neither of us is impersonating the other, and confident Rob
Pratt would agree!

That the solutions would be quite similar surprises me not in
the least: mine was developed in a very straightforward and obvious
way. I *am* surprised that Mr. Pratt has improved on my score
so dramatically and am anxious to see his solution, but ...

I cannot access your BoxifyMe page today. (Does anyone else have
a similar problem?) Skybuck, Please e-mail me Mr. Pratt's
solution if you have time.

Best wishes,
Rob Pratt^H^H^H^H^H^H^H^H^HJames Dow Allen
"

I'd much rather have you access my site properly.

I did introduce some "style sheets" maybe that's screwing up your browser ?

What operating system and browser are you using ?

And how much GHZ and Memory do you have ?

Bye,
Skybuck.

 

[Lew]

The best programmer/algoritm/entry sits on the throne !

Not coincidentally, that's where the best programmers come up with the best
algorithms.

 

[James Dow Allen]

I cannot access your BoxifyMe page today.  (Does anyone else have
a similar problem?)  Skybuck, Please e-mail me Mr. Pratt's
solution if you have time.

It seems no one else has reported the problem here.
But would thread participants please confirm if they *can* access
BoxifyMe?

What operating system and browser are you using ?

Windows XP. Both IE and Firefox fail to load, just
"waiting" for a long time.
http://www.skybuck.org/BoxifyMe/BoxifyMe1JamesDowAllenEntry1.txt
also fails to load, though http://www.skybuck.org/ itself
loads promptly.

And how much GHZ and Memory do you have ?

Uhhh ... enough so that if that's the problem
I don't *want* to load your page!

Best ever,
James

 

[Jim Janney]

A draconian layered architecture?! Are we talking about a module that
needs refactoring?

This is not one of the malapropisms on which I'd normally comment, but
this one is funnier than most.

Thanks to the work of Cerebron[1], we can partition dragons into three
distinct categories: the mythical, the chimerical, and the purely
hypothetical...

[1] http://www.urbandictionary.com/define.php?term=Cerebron

 

[James Dow Allen]

I can access it with Netscape 3.04g and also with IE 6.

I can access both now. Whatever problem it was went away.

James

 

[Skybuck Flying]

A new and the most spectacular contender/contester so far:

David Eisenstat has entered the contest.

And it appears he has become the King of the Contest (Round1)

There is very little room to improve on his results/solutions.

He submitted two solutions:

1. An overlapping solution/entry
2. A non-overlapping solution/entry.

Both of them are claimed to be optimal. The optimal overlapping result is
hereby pretty much confirmed (217 boxes). The non-overlapping solution still
needs confirmation though (264 boxes).

It also appears there are different optimal solutions at least for the
overlapping variation of the contest.

Because David has supplied two optimal solutions (one for overlapping and
one for non-overlapping) he has become the new King of the Contest of Round
1.

However David's overlapping solution is considered by me to be slightly
better than that of Rob's overlapping solution. Because David's solution has
less "heat"

Perhaps that is subjective but still. So there is very little room for
improvements. A better heatmap or perhaps other better maps might still
de-crown him.

But for now he seems to be sitting firmly on the King's Throne.

Further entries are still accepted:

1. Solver confirmations.
2. Additional algorithms, these will come in handy for the next round.

I shall now start to think and contemplate on the next round. I already have
idea's for the next round. It will probably be very much fun to look it.

Will the solver crowds still be able to participate or will their solvers
break down in sweat and lag behind ?!?

Only time will tell !

The website has been updated for your enjoyment:

http://www.skybuck.org/BoxifyMe/

Bye,
Skybuck =D

 

[Skybuck Flying]

With fractional ints that poly is legal.
For a NTSC screen (640x448) you would use byte pixel addresses and cut
the screen in four quarters, so no fractions.
For HD (1280x1024) you end up using 16 bit ints, giving 5 bits of fract.
Enough for a 16 to 1 slope or so.

After generating each rect you could then adjust the verts by fractions
to pick up more pixels. This could cut your rect count in half.
(And double your data size, as now you have to describe four points, not
2.)
But here again fewer items means faster rendering, maybe by ~30%.


And
.
..
..
...

And
.
..
..
...

And
.
..
...
..

And maybe this combination of two of the above.
.
..
.
..

I was thinking more about all kinds of triangles with a perfect diagonal...

Like so:

.
...

.
..
....

.
..
...
.....


And any combination of these.

Ofcourse the idea could be expanded to try and see if any set of pixels
describe a bresenham line algorithm... but then if the line is too flat it
might assume the bitmap ment a diagonal... while in reality it are just two
flat surfaces...

So describing a more flat-like diagonal like... might upset any physics
simulations.... or maybe not... I guess it depends on the intention of the
form of the bitmap.

For a ball or any circular/spline like looking bitmap it would make sense...

But I can also imagine cases where it's not round/circular/spline like but
simply two squares right next to each other with 1 pixel height
difference... so maybe it appear as if it were a diagonal might be wrong

So that's why I would limit it to perfect diagonals only with an stepping of
dx/dy = 1

I think in those cases it's pretty clear that it was probably ment as a
diagonal.

For now I am not going to include it in the contest, because it might become
to difficult and I would to move on a bit, but maybe later/in the future I
give this a looksy/try

Bye,
Skybuck.