TPainter inflation routines

[David Faught]

I have been studying the classes and methods involved in the inflation
of 2D objects into 3D objects that TPainter (and CCPainter!) uses with
the aim of trying to eventually optimize the code a bit.  I am someday
still going to try the alternative method that I described a while
back too.

In the meantime, I have a couple of simple-minded questions:

1.  To better see what was going on in the Form>>#traceOutlines
method, I inserted a few lines like "outer asMorph openInWorld."  The
morphs that came out were on the order of 2 to 3 times bigger on the
screen than the original appeared in the viewport.  Why is that?

2.  In the Form>>#traceOutline:do: method, in order to find a starting
point for edge tracing, there is a line that finds the smallest
enclosing rectangle for a form followed by a search of the first
returned line of that rectangle for the first non-background pixel.
There is some extra work being done here somewhere because the
smallest enclosing rectangle does not appear to be used anywhere else,
and all that really needs to be searched for is the first upper left
non-background pixel.  The bottom right of the smallest enclosing
rectangle is of no concern here, right?  Am I missing something here?

3.  The literature in this area that I have come across talks about 2
main methods of extracting polygons from an image, edge tracking which
is done here, and marching squares.  Was marching squares ever tried
for TPainter, or is it generally regarded as inferior for some reason?

Thanks for any help you can provide.

[Andreas Raab]

David Faught wrote:
> 1.  To better see what was going on in the Form>>#traceOutlines
> method, I inserted a few lines like "outer asMorph openInWorld."  The
> morphs that came out were on the order of 2 to 3 times bigger on the
> screen than the original appeared in the viewport.  Why is that?

To avoid 1 pixel shapes which are problematic.

> 2.  In the Form>>#traceOutline:do: method, in order to find a starting
> point for edge tracing, there is a line that finds the smallest
> enclosing rectangle for a form followed by a search of the first
> returned line of that rectangle for the first non-background pixel.
> There is some extra work being done here somewhere because the
> smallest enclosing rectangle does not appear to be used anywhere else,
> and all that really needs to be searched for is the first upper left
> non-background pixel.  The bottom right of the smallest enclosing
> rectangle is of no concern here, right?  Am I missing something here?

Your observation is correct. There is no particular need for the right
and bottom border. You could probably do even random sampling to find a
starting point.

> 3.  The literature in this area that I have come across talks about 2
> main methods of extracting polygons from an image, edge tracking which
> is done here, and marching squares.  Was marching squares ever tried
> for TPainter, or is it generally regarded as inferior for some reason?

We never tried marching squares. It would be interesting to see what the
tradeoffs are compared to the current version. If it deals more robustly
with 1px shapes that alone might be worth it. Give it a try!

Cheers,
   - Andreas

[David Faught]

On 9/15/06, Andreas Raab <andreas.raab@...> wrote:
> David Faught wrote:
> > 1.  To better see what was going on in the Form>>#traceOutlines
> > method, I inserted a few lines like "outer asMorph openInWorld."  The
> > morphs that came out were on the order of 2 to 3 times bigger on the
> > screen than the original appeared in the viewport.  Why is that?
>
> To avoid 1 pixel shapes which are problematic.

This must be a problem for the later Subdivision process.  I would
guess that a 1 point polygon should work okay for the image->polygon
extraction.

> > 2.  In the Form>>#traceOutline:do: method, in order to find a starting
> > point for edge tracing, there is a line that finds the smallest
> > enclosing rectangle for a form followed by a search of the first
> > returned line of that rectangle for the first non-background pixel.
> > There is some extra work being done here somewhere because the
> > smallest enclosing rectangle does not appear to be used anywhere else,
> > and all that really needs to be searched for is the first upper left
> > non-background pixel.  The bottom right of the smallest enclosing
> > rectangle is of no concern here, right?  Am I missing something here?
>
> Your observation is correct. There is no particular need for the right
> and bottom border. You could probably do even random sampling to find a
> starting point.

I think that a random sample to find an edge point might be a little
extreme.  However, it also appears to me that later on in the
Form>>#traceOutline:do: method in the actual edge tracking loop, it
might be beneficial to try to find only corners of polygons to reduce
the point count somewhat.  If the search direction is the same as when
the last point was found, then they are in a straight line and this
point only needs to be output if the next point is in a different
direction.  I guess that logic is a little more complex than I
originally thought as the last, current, and next points all need to
be considered.  The extra logic per point might outweigh the savings
in point count.

Thank you for your input.

[Andreas Raab]

David Faught wrote:

> On 9/15/06, Andreas Raab <andreas.raab@...> wrote:
>> David Faught wrote:
>> > 1.  To better see what was going on in the Form>>#traceOutlines
>> > method, I inserted a few lines like "outer asMorph openInWorld."  The
>> > morphs that came out were on the order of 2 to 3 times bigger on the
>> > screen than the original appeared in the viewport.  Why is that?
>>
>> To avoid 1 pixel shapes which are problematic.
>
> This must be a problem for the later Subdivision process.  I would
> guess that a 1 point polygon should work okay for the image->polygon
> extraction.

No, it's an issue in the tracer. If you want to try it simply scribble a
number of overlapping 1px lines and try it out. It'll happen sooner or
later.

Cheers,
   - Andreas