Re[2]: [Gnash-dev] Questions about trapezoids, triangle stripper etc.

[Udo Giacomozzi]

Hello strk,

Monday, September 18, 2006, 10:24:22 AM, you wrote:
s> Udo, good digging!
s> I don't have an answer for your question, so I'd just suggest you
s> try completely skipping the tesselator and see what happen with
s> some of the existing testcases.

Yes, that will be the next step. I think I'll have some time to give
it a try on Tuesday. I'll probably have to override the mash_set
class so that it passes the data directly to the renderer, which then
gives the polygon to the AGG's own tesselator. Once that works
solid fills and solid lines should work too.

Anyway, I now understand the principle behind the tesselator and I
tried to explain it in my notes.


s> In general, it would be nice if you could write down this info
s> in the gnash manual (internals chapter) for future references.

Yes, I digged (still do that) step by step through the code and write
down what I learn from it. I already wrote lots of stuff because I try
to be very detailed. Once done I'll post it here so you guys can
review it in case some parts are wrong.

The most difficult thing is that the code is sparse across lots of
files and even more classes. Sometimes it's hard to follow the logic
of the implementation..


s> In particular, I'm trying to separate the "parser" code from 
s> the "playing" code and I think your digging might help me in this.
s> For example, is the 'line strips' creation done at parse time
s> or at play time ?

Well, I did concentrate on the parsing and rendering code, but not yet
on the playing code. However, I'm quite sure it is done at play time
since it has to deal with transformations, morphing and such. For
example, curves (splines) are converted to lines (a "mesh") starting
in the display() method of the shape. Of course these lines are an
approximation of the original curve and the number of lines used to
reconstruct the curve depends on some factors, like the current size
of the curve. For example when you zoom a sprite (MovieClip) it will
re-calculate the lines to stay below a certain error tolerance. The
mesh is also stored in some sort of cache to minimise these
calculations. Simply speaking, If you double the scale of a sprite the
number of lines building a it's curves will double too.


s> What happen when new lines are added at runtime
s> (we currently don't support the drawing API so it's likely there's
s> no support of dynamic drawing) ?

I've found no code for dynamic drawing. However,
server/parser/shape_character_def.cpp would be the place to look since
it is the starting point for everything that's visible. In theory one
can change the "path", "fill_style" and "line_style" properties of a
"shape_character_def" at any time as long as it's cache
(m_cached_meshes) is cleared. The mesh will be re-generated next time
display() is called.

There may be problems with shapes, however, since the code (especially
the "tesselator") makes some assumptions on the on the way shapes are
defined. AFAIK, shape holes are a problem for the tesselator, but the
Flash IDE already solves them at design time (but I'm not very sure on
this). The AGG renderer probably would have no problems with this, but
I can't tell about the Gnash tesselator. I believe it just would look
wrong at worst.


I'd say it will be difficult to really separate the parsing part from
the playing part because that would mean lots of rewriting. The code
seems very weaved, probably to gain some speed optimizations. For
example, the character shape does everything from reading,
transformation, caching and rendering. However, it does nothing at a
low level. Reading is done by external functions that create a bunch
of classes. Starting from an "edge" the shape is transformed using a
few intermediary classes until everything is simplified to a list of
triangles. To accomplish that lots of other classes here and there,
like the tesselator, are used. In a certain way it actually makes
sense, because the shape_character_def is completely responsible for
it's shape and is probably the best way to control the cache.

Ok, you could extract the parsing part and simply pass the curves to
the class, however I currently see no real benefit from that. If the
only point is to support dynamic drawing it is possible to add a
simpler constructor that does not use any parser and can be used to
add curves later.

Coming back to the renderer, I start to doubt it's really necessary to
rewrite the renderer class. Simply everything is decomposed to
straight lines (polygons and outlines). Looking at the mesh set cache
(see above) I'd say it's probably better than passing the original
curve to the renderer who would probably try to render it too
accurately and would have to recalculate it again and again.

Instead, I'm thinking of allowing the renderer to activate some bypass
mechanism that tells the shape class "hey, I have my own tesselator -
you don't need to do it". That could be probably be extended to even
bypass the cuves-to-line transformation, if the renderer really can do
that better anyway.
Anyway, the mesh cache should remain in the shape class since it
depends too much on it.

Please not I'm still a novice to Gnash and I might be completely wrong
on some parts... ;)


I have a completely different question: Maybe I'm stir up a hornets'
nest but could you explain a bit the story of Gnash? I know that it
has it's origins in GameSWF and AFAIK the project is split because the
original author didn't want to include some of your patches. I'm
asking because I'd like to know how the single parts of Gnash evolved
technically. For example, it seems that no one here apparently knows
anything about the rendering part and most development is focused on
other parts of the project. Perhaps it helps me to understand the
interaction of the code when I know which parts have been developed
"independently". I hope you understand what I mean...

Best wishes,
Udo


s> --strk;

s> On Wed, Sep 13, 2006 at 07:49:08PM +0200, Udo Giacomozzi wrote:
>> Hi again.
>> 
>> Ok, things are getting clearer now. I studied everything and came now
>> to the tesselator part.
>> 
>> AFAIK, curves and lines are loaded into a list of "edges" which then
>> are either passed as "line strips" to the renderer (in the case of an
>> outline) or mangled through the tesselator if it is a filled shape.
>> 
>>   BTW, straight lines seem to be converted to curves where the control
>>   point equals the new anchor point (resulting a straight line on
>>   screen). That explains why simple straight lines are drawn in pieces
>>   of different length. This could be optimized, I'd say...
>> 
>> Back to my question:
>> 
>> The outline mesh is passed to the "tesselator", which seems to
>> generate a list of trapezoids that together form the correct
>> fill for the shape, correct? These trapezoids have parallel upper and
>> lower sides, and probably they perfectly horizontal on the screen.
>> 
>> Ok, these trapezoids are then split to two triangles via the
>> "tri_stripper". I guess this is to support accelerated hardware?
>> Anyway, in the end we probably have a bunch of triangles that form the
>> shape (and are passed to the backend).
>> 
>> Now, we would like to bypass the tesselator completely and let the
>> backend draw the original shape itself (based on straight lines is
>> ok). The reason is that these triangles (the shape) look awful when
>> rendered through AGG. This may be because of the anti-aliasing or
>> because AGG does some intersection computing. Anyway, one can clearly
>> recognize those triangles when a simple rectangle should be displayed.
>> 
>> Anyway, I'd like to learn more about the tesselator because it's the
>> missing piece in my Gnash puzzle.
>> 
>> I hope someone can answer any of these questions:
>> 
>> - What's the true story behind the tesselator and the trapezoids? I
>>   admit I don't know anything about filling algorithms theory.
>> 
>> - Are the triangles really just two pieces of the trapezoids? I ask
>>   because the "tri_stripper" is implemented rather complicated for
>>   such a simple task. Apparently the order of the triangles follow
>>   some logic?
>> 
>> - What do the arguments passed to add_trapezoid() exactly mean?
>> 
>> - Is all this tesselator/trapezoid/triangle stuff used *only* for
>>   rendering or has it an additional uses, for example collision
>>   detection? With other words: Would it be safe to disable it
>>   altogether?
>> 
>> Looking forward for any hint,
>> Udo
>> 
>> 
>> 
>> _______________________________________________
>> Gnash-dev mailing list
>> address@hidden
>> http://lists.gnu.org/mailman/listinfo/gnash-dev




Udo