Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.postscript > #1753 > unrolled thread

designing a data structure in C for PS paths.

Back to article view | Back to comp.lang.postscript

Contents

  designing a data structure in C for PS paths. luser- -droog <mijoryx@yahoo.com> - 2013-12-26 11:27 -0800
    Re: designing a data structure in C for PS paths. luser- -droog <mijoryx@yahoo.com> - 2013-12-26 11:38 -0800
    Re: designing a data structure in C for PS paths. luser- -droog <mijoryx@yahoo.com> - 2014-12-07 22:09 -0800
      Re: designing a data structure in C for PS paths. Carlos <angus@quovadis.com.ar> - 2014-12-08 15:53 +0100
        Re: designing a data structure in C for PS paths. luser- -droog <mijoryx@yahoo.com> - 2014-12-08 23:32 -0800
          Re: designing a data structure in C for PS paths. Carlos <angus@quovadis.com.ar> - 2014-12-09 14:49 +0100
            Re: designing a data structure in C for PS paths. luser- -droog <mijoryx@yahoo.com> - 2014-12-09 10:08 -0800
              Re: designing a data structure in C for PS paths. luser- -droog <mijoryx@yahoo.com> - 2014-12-09 10:40 -0800
                Re: designing a data structure in C for PS paths. luser- -droog <mijoryx@yahoo.com> - 2014-12-09 10:49 -0800
                  Re: designing a data structure in C for PS paths. Carlos <angus@quovadis.com.ar> - 2014-12-11 00:18 +0100

#1753 — designing a data structure in C for PS paths.

This is I think is of general interest, although motivated by work on Xpost.

I want to implement in C a data structure for PS paths. 

Here's the version from the draft interpreter xpost0c, before I rewrote it to use Cairo for graphics. This isn't my earliest version because there was something in flips that make Xlib calls, but I'm not finding any copies of that at the moment.

These are xpost0c's operator functions. They receive a pointer to a C-array of the object arguments from the ps operand stack, and place their return values into the same array (which is, in fact part of the ps operand stack directly accessed by the pointer).

/* path construction operators */

typedef struct s_path {
    enum e_path { MOVE, LINE, CURVE, CLOSE } type;
    double v[6];
} Path;


void Onewpath (Object *o);
void Omoveto (Object *o);
void Olineto (Object *o);
void Ormoveto (Object *o);
void Orlineto (Object *o);
void Ocurveto (Object *o);
void Oclosepath (Object *o);


#include "global.h"

/* -  newpath  -
   initialize current path to be empty
 */
void Onewpath (Object *o) {
    tailpath = subpath = curpath;
}

/* x y  moveto  -
   set current point to (x, y)
 */
void Omoveto (Object *o) {
    promote(o[0]);
    promote(o[1]);
    if (!typearg2(real,real)) error(typecheck, OP_moveto);
    if (tailpath == NULL) tailpath = curpath;
    subpath=tailpath;
    *tailpath++ =
        (Path){
            .type=MOVE,
            .v[0] = applyCTMx(o[0].r,o[1].r),
            .v[1] = applyCTMy(o[0].r,o[1].r),
        };
    cp[0] = o[0].r;
    cp[1] = o[1].r;
}

/* dx dy  rmoveto  -
   relative moveto
 */
void Ormoveto (Object *o) {
    promote(o[0]);
    promote(o[1]);
    if (!typearg2(real,real)) error(typecheck, OP_rmoveto);
    o[0].r += cp[0];
    o[1].r += cp[1];
    subpath=tailpath;
    *tailpath++ =
        (Path){
            .type=MOVE,
            .v[0] = applyCTMx(o[0].r,o[1].r),
            .v[1] = applyCTMy(o[0].r,o[1].r),
        };
    cp[0] = o[0].r;
    cp[1] = o[1].r;
}

/* x y  lineto  -
   append straight line to (x, y)
 */
void Olineto (Object *o) {
    promote(o[0]);
    promote(o[1]);
    if (!typearg2(real,real)) error(typecheck, OP_lineto);
    *tailpath++ =
        (Path){
            .type=LINE,
            .v[0] = applyCTMx(o[0].r,o[1].r),
            .v[1] = applyCTMy(o[0].r,o[1].r),
        };
    cp[0] = o[0].r;
    cp[1] = o[1].r;
}

/* dx dy  rlineto  -
   relative lineto
 */
void Orlineto (Object *o) {
    promote(o[0]);
    promote(o[1]);
    if (!typearg2(real,real)) error(typecheck, OP_rlineto);
    o[0].r += cp[0];
    o[1].r += cp[1];
    *tailpath++ =
        (Path){
            .type=LINE,
            .v[0] = applyCTMx(o[0].r,o[1].r),
            .v[1] = applyCTMy(o[0].r,o[1].r),
        };
    cp[0] = o[0].r;
    cp[1] = o[1].r;
}

/* x_1 y_1 x_2 y_2 x_3 y_3  curveto  -
   append Bexier cubic section
 */
void Ocurveto (Object *o) {
    *tailpath++ =
        (Path){
            .type=CURVE,
            .v[0] = applyCTMx(o[0].r,o[1].r),
            .v[1] = applyCTMy(o[0].r,o[1].r),
            .v[2] = applyCTMx(o[2].r,o[3].r),
            .v[3] = applyCTMy(o[2].r,o[3].r),
            .v[4] = applyCTMx(o[4].r,o[5].r),
            .v[5] = applyCTMy(o[4].r,o[5].r),
        };
    cp[0] = o[4].r;
    cp[1] = o[5].r;
}

/* -  closepath  -
   connect subpath back to its starting point
 */
void Oclosepath (Object *o) {
    *tailpath++ = (Path){ .type=CLOSE, .v[0] = subpath-curpath };
}



Hm. Looks like closing segments may have been having y-coordinate problems. :)

So this code just uses a global array (curpath) and a pointer (tailpath) and an auxiliary pointer (subpath) into an array of structs containing an enum and up to 6 coordinate values.

My current code implements the path entirely in postscript, using dictionaries for almost everything due to their nice properties: named elements, auto-growing, support for integer keys.

I won't quote everything here, you can browse it at code.google.com/p/xpost in data/path.ps.


% path == <<
%             0 << subpath0 >>
%             1 << %subpath1
%                   0  << elem0 /move >> %first elem must be /move
%                   1  << elem1 >>
%               >>
%         >>
% A /move element will always start a new subpath
% Any other element appends to the last subpath

% Path Construction Operators

% -  newpath  -
% initialize current path to be empty
/newpath {
    graphicsdict /currgstate get 
        /currpath 1 dict put 
} bind def 

% -  currentpoint  x y 
% return current point coordinates
/currentpoint {
    cpath dup length 0 eq {
        pop /currentpoint cvx /nocurrentpoint signalerror
    }{  
        dup length 1 sub get % last-subpath
        dup length 1 sub get % last-elem
        /data get dup length 2 sub 2 getinterval % last data pair
        aload pop itransform
    } ifelse
} bind def 

/cpath { graphicsdict /currgstate get /currpath get } bind def 


/addtopath { % << /data [...] /cmd /... >> <<path>>
    %(addtopath)=
    %(addtopath start pstack:)= pstack()=
    dup length 0 eq {                       % elem path
        1 index /cmd get /move eq {         % elem path
            %(New Path)=
            << 0 4 3 roll >> % new subpath  % <path> <subpath>
            0 exch put                      %
        }{
            /addtopath cvx /nocurrentpoint signalerror
        } ifelse
    }{                                  % elem path
        1 index /cmd get /move eq {     % elem path
            dup dup length 1 sub get    % elem path last-subpath
            dup length 1 sub get        % elem path last-elem-of-last-subpath
            dup /cmd get /move eq { % elem path last-elem
                %(Merge /move)=
                3 1 roll pop            % last-elem elem
                /data get /data exch put
            }{                          % elem path last-elem
                %(New subpath)=
                pop                     % elem path
                dup length 3 2 roll     % <path> n <elem>
                << 0 3 2 roll >>        % <path> n <<0 <elem>>>        % new subpath
                %pstack()=
                put
            } ifelse
        }{                              % elem path
            %(Append elem)=
            dup length 1 sub get        % elem last-subpath
            dup length                  % elem last-subpath key
            3 2 roll
            %pstack()=
            put
        } ifelse
    } ifelse
    %(addtopath final pstack:)= pstack()=
    %(addtopath exit)=
} bind def

% x y  moveto  -
% set current point to (x,y)
/moveto {
    transform
    2 array astore
    << /data 3 2 roll /cmd /move >> cpath addtopath
} bind def


% dx dy  rmoveto  -
% relative moveto
/rmoveto {
    currentpoint
    3 2 roll add
    3 1 roll add exch
    moveto
} bind def

% x y  lineto  -
% append straight line to (x,y)
/lineto {
    transform
    2 array astore
    << /data 3 2 roll /cmd /line >> cpath addtopath
} bind def

% dx dy  rlineto  -
% relative lineto
/rlineto {
    currentpoint
    3 2 roll add
    3 1 roll add exch
    lineto
} bind def

% x1 y1 x2 y2 x3 y3  curveto  -
% append Bezier cubic section
/curveto {
    3 { 6 2 roll transform } repeat
    6 array astore
    << /data 3 2 roll /cmd /curve >> cpath addtopath
} bind def


You see that the dict has very nice properties for a simulating a growing array. The key for the tail is always at `length 1 sub`. The element dict can hold a size=2 or size=6 array as needed. And everything interacts naturally with save/restore.

The idea I've been toying with for a "new way" is to use stacks. That's the basic auto-growing structure at the C level of the interpreter (lower overhead than a dict because it doesn't exist as a postscript object, so it doesn't take up a slot in the memory table).

With stacks, I think I can arrange the objects to pretty much match the normal postscript syntax.

[0]:0
[1]:0
[2]:moveto
[3]:100
[4]:100
[5]:lineto
[6]:200
[7]:100
[8]:lineto
[9]:closepath

This would be a "subpath" stack or in the original Warnock/Wyatt language, a trajectory as distinct from a complete shape.

To make it nestable, I suppose we have to violate the "no overhead" description above, and wrap the stack in an object. There is precendent for this elsewhere in the interpreter. A savetype object contains a vm address for a stack. Ok, that's still pretty low for overhead. It still doesn't need a memory table slot (aka 'ent').


/**
 * @struct Xpost_Object_Save
 * @brief The savetype object, for both user and on the save stack.
 */
typedef struct
{
    word tag; /**< savetype */
    word lev; /**< save-level, index into Save stack */
    dword stk; /**< address of Saverec stack */
} Xpost_Object_Save;


So if there's a pathtype object implemented the same way, the "current" path could be a stack of "subpaths" which are pathtype stacks.

[0]:path
[1]:path
[2]:path

And this stack would then be stacked in a top-level "path stack", which is pushed (dup) and popped (... free the stack? ...) in coordination with gsave/grestore and save/restore, since it's no longer contained in the ps-level adt implementation of the gstate stack....

... Hm. Or is that a bad choice? Maybe it can still be in the ps-level gstate dict. I'll have to think on that. That would seem to take care of the (g)*(save/restore) issue.

[toc] | [next] | [standalone]

#1754

On Thursday, December 26, 2013 1:27:41 PM UTC-6, luser- -droog wrote:
> These are xpost0c's operator functions. They receive a pointer to a C-array of the object arguments from the ps operand stack, and place their return values into the same array (which is, in fact part of the ps operand stack directly accessed by the pointer).
> 

This may have been true for earlier versions like flips or podvig. By xpost0, I think it was actually making a holding array in the operator handler. So only the stack operators were accessing the stack directly. And all polymorphic operators.

[toc] | [prev] | [next] | [standalone]

#2109

On Thursday, December 26, 2013 1:27:41 PM UTC-6, luser- -droog wrote:
> This is I think is of general interest, although motivated by work on Xpost.
> 
> I want to implement in C a data structure for PS paths. 
> 
> Here's the version from the draft interpreter xpost0c, before I rewrote it to use Cairo for graphics. This isn't my earliest version because there was something in flips that make Xlib calls, but I'm not finding any copies of that at the moment.
> 
> These are xpost0c's operator functions. They receive a pointer to a C-array of the object arguments from the ps operand stack, and place their return values into the same array (which is, in fact part of the ps operand stack directly accessed by the pointer).
> 
[snip]
> So this code just uses a global array (curpath) and a pointer (tailpath) and an auxiliary pointer (subpath) into an array of structs containing an enum and up to 6 coordinate values.
> 
> My current code implements the path entirely in postscript, using dictionaries for almost everything due to their nice properties: named elements, auto-growing, support for integer keys.
> 
> I won't quote everything here, you can browse it at code.google.com/p/xpost in data/path.ps.
> 
[snip]> 
> 
> You see that the dict has very nice properties for a simulating a growing array. The key for the tail is always at `length 1 sub`. The element dict can hold a size=2 or size=6 array as needed. And everything interacts naturally with save/restore.
> 
> The idea I've been toying with for a "new way" is to use stacks. That's the basic auto-growing structure at the C level of the interpreter (lower overhead than a dict because it doesn't exist as a postscript object, so it doesn't take up a slot in the memory table).
> 
> With stacks, I think I can arrange the objects to pretty much match the normal postscript syntax.
> 
> [0]:0
> [1]:0
> [2]:moveto
> [3]:100
> [4]:100
> [5]:lineto
> [6]:200
> [7]:100
> [8]:lineto
> [9]:closepath
> 
> This would be a "subpath" stack or in the original Warnock/Wyatt language, a trajectory as distinct from a complete shape.
> 
> To make it nestable, I suppose we have to violate the "no overhead" description above, and wrap the stack in an object. There is precendent for this elsewhere in the interpreter. A savetype object contains a vm address for a stack. Ok, that's still pretty low for overhead. It still doesn't need a memory table slot (aka 'ent').
> 
[snip]> 
> So if there's a pathtype object implemented the same way, the "current" path could be a stack of "subpaths" which are pathtype stacks.
> 
> [0]:path
> [1]:path
> [2]:path
> 
> And this stack would then be stacked in a top-level "path stack", which is pushed (dup) and popped (... free the stack? ...) in coordination with gsave/grestore and save/restore, since it's no longer contained in the ps-level adt implementation of the gstate stack....
> 
> ... Hm. Or is that a bad choice? Maybe it can still be in the ps-level gstate dict. I'll have to think on that. That would seem to take care of the (g)*(save/restore) issue.


Buttoning-up this thread for the archive. 

The stack nonsense was way too complicated and never happened.
Instead, we translated the functions directly to C, using
the same postscript-level data structures. This had the
effect of factoring out many cycles of the main interpreter
loop from the execution of each operator. Crude testing
showed a 50% speed-up in the drawing tests.

So it's still growing dicts with the same member names in the
element dicts.

Now, a lot of my old links to code are going dead as stuff
gets moved from src/bin to src/lib. But everything is in /lib
now so current links should be stable for the forseeable.
http://code.google.com/p/xpost/source/browse/src/lib/xpost_op_path.c

[toc] | [prev] | [next] | [standalone]

#2110

On 08/12/2014 7:09, luser- -droog wrote:
> [...]
>> With stacks, I think I can arrange the objects to pretty much match
>> the normal postscript syntax.
>>
>> [0]:0 [1]:0 [2]:moveto [3]:100 [4]:100 [5]:lineto [6]:200 [7]:100
>> [8]:lineto [9]:closepath
>>
>> This would be a "subpath" stack or in the original Warnock/Wyatt
>> language, a trajectory as distinct from a complete shape.
>>
>> To make it nestable, I suppose we have to violate the "no overhead"
>> description above, and wrap the stack in an object. There is
>> precendent for this elsewhere in the interpreter. A savetype object
>> contains a vm address for a stack. Ok, that's still pretty low for
>> overhead. It still doesn't need a memory table slot (aka 'ent').

Hi,
I was trying to follow, but I'm not getting why paths should be nestable 
(or at least, paths represented as a sequence of operations). Could you 
elaborate about it?

Carlos.
-- 

[toc] | [prev] | [next] | [standalone]

#2111

On Monday, December 8, 2014 8:53:38 AM UTC-6, Carlos wrote:
> On 08/12/2014 7:09, luser- -droog wrote:
> > [...]
> >> With stacks, I think I can arrange the objects to pretty much match
> >> the normal postscript syntax.
> >>
> >> [0]:0 [1]:0 [2]:moveto [3]:100 [4]:100 [5]:lineto [6]:200 [7]:100
> >> [8]:lineto [9]:closepath
> >>
> >> This would be a "subpath" stack or in the original Warnock/Wyatt
> >> language, a trajectory as distinct from a complete shape.
> >>
> >> To make it nestable, I suppose we have to violate the "no overhead"
> >> description above, and wrap the stack in an object. There is
> >> precendent for this elsewhere in the interpreter. A savetype object
> >> contains a vm address for a stack. Ok, that's still pretty low for
> >> overhead. It still doesn't need a memory table slot (aka 'ent').
> 
> Hi,
> I was trying to follow, but I'm not getting why paths should be nestable 
> (or at least, paths represented as a sequence of operations). Could you 
> elaborate about it?
> 

Sure. I think I was using confusing terminology. I was using the same word
'path' to refer to a subpath (a sequence of `lineto` and `curveto` beginning
with `moveto`, possibly ending with `closepath`), the currentpath (which can 
contain many subpaths), and the graphics-state stack.

If I were to make the 'path' out of stacks then that would separate it
from the rest of the graphics state, and I would need a top-level stack
for `gsave/grestore` to operate on. The elements of the top-level path 
stack would be "normal" path stacks, the elements of which would be
"subpath" stacks, the elements of which would be path operations (moveto, 
line, curveto, closepath). 

[toc] | [prev] | [next] | [standalone]

#2112

On 09/12/2014 8:32, luser- -droog wrote:
> On Monday, December 8, 2014 8:53:38 AM UTC-6, Carlos wrote:
>> On 08/12/2014 7:09, luser- -droog wrote:
>>> [...]
>>>> With stacks, I think I can arrange the objects to pretty much match
>>>> the normal postscript syntax.
>>>>
>>>> [0]:0 [1]:0 [2]:moveto [3]:100 [4]:100 [5]:lineto [6]:200 [7]:100
>>>> [8]:lineto [9]:closepath
>>>>
>>>> This would be a "subpath" stack or in the original Warnock/Wyatt
>>>> language, a trajectory as distinct from a complete shape.
>>>>
>>>> To make it nestable, I suppose we have to violate the "no overhead"
>>>> description above, and wrap the stack in an object. There is
>>>> precendent for this elsewhere in the interpreter. A savetype object
>>>> contains a vm address for a stack. Ok, that's still pretty low for
>>>> overhead. It still doesn't need a memory table slot (aka 'ent').
>>
>> Hi,
>> I was trying to follow, but I'm not getting why paths should be nestable
>> (or at least, paths represented as a sequence of operations). Could you
>> elaborate about it?
>>
>
> Sure. I think I was using confusing terminology. I was using the same word
> 'path' to refer to a subpath (a sequence of `lineto` and `curveto` beginning
> with `moveto`, possibly ending with `closepath`), the currentpath (which can
> contain many subpaths), and the graphics-state stack.
>
> If I were to make the 'path' out of stacks then that would separate it
> from the rest of the graphics state, and I would need a top-level stack
> for `gsave/grestore` to operate on. The elements of the top-level path
> stack would be "normal" path stacks, the elements of which would be
> "subpath" stacks, the elements of which would be path operations (moveto,
> line, curveto, closepath).
>

OK, but if the elements of the "normal" path were the operations 
themselves (just the concatenated operations of all subpaths, without 
structuring), it would be conceptually the same, right?

[toc] | [prev] | [next] | [standalone]

#2113

On Tuesday, December 9, 2014 7:49:05 AM UTC-6, Carlos wrote:
> On 09/12/2014 8:32, luser- -droog wrote:
> > On Monday, December 8, 2014 8:53:38 AM UTC-6, Carlos wrote:
> >> On 08/12/2014 7:09, luser- -droog wrote:
> >>> [...]
> >>>> With stacks, I think I can arrange the objects to pretty much match
> >>>> the normal postscript syntax.
> >>>>
> >>>> [0]:0 [1]:0 [2]:moveto [3]:100 [4]:100 [5]:lineto [6]:200 [7]:100
> >>>> [8]:lineto [9]:closepath
> >>>>
> >>>> This would be a "subpath" stack or in the original Warnock/Wyatt
> >>>> language, a trajectory as distinct from a complete shape.
> >>>>
> >>>> To make it nestable, I suppose we have to violate the "no overhead"
> >>>> description above, and wrap the stack in an object. There is
> >>>> precendent for this elsewhere in the interpreter. A savetype object
> >>>> contains a vm address for a stack. Ok, that's still pretty low for
> >>>> overhead. It still doesn't need a memory table slot (aka 'ent').
> >>
> >> Hi,
> >> I was trying to follow, but I'm not getting why paths should be nestable
> >> (or at least, paths represented as a sequence of operations). Could you
> >> elaborate about it?
> >>
> >
> > Sure. I think I was using confusing terminology. I was using the same word
> > 'path' to refer to a subpath (a sequence of `lineto` and `curveto` beginning
> > with `moveto`, possibly ending with `closepath`), the currentpath (which can
> > contain many subpaths), and the graphics-state stack.
> >
> > If I were to make the 'path' out of stacks then that would separate it
> > from the rest of the graphics state, and I would need a top-level stack
> > for `gsave/grestore` to operate on. The elements of the top-level path
> > stack would be "normal" path stacks, the elements of which would be
> > "subpath" stacks, the elements of which would be path operations (moveto,
> > line, curveto, closepath).
> >
> 
> OK, but if the elements of the "normal" path were the operations 
> themselves (just the concatenated operations of all subpaths, without 
> structuring), it would be conceptually the same, right?

Yes, I suppose so. I think it would make `closepath` O(n),
though, since it now has to search for the most recent
`moveto`, whereas the two-level structuring makes it
easier to find (and O(1)).

[toc] | [prev] | [next] | [standalone]

#2114

On Tuesday, December 9, 2014 12:08:56 PM UTC-6, luser- -droog wrote:
> On Tuesday, December 9, 2014 7:49:05 AM UTC-6, Carlos wrote:
> > On 09/12/2014 8:32, luser- -droog wrote:
> > >
> > > Sure. I think I was using confusing terminology. I was using the same word
> > > 'path' to refer to a subpath (a sequence of `lineto` and `curveto` beginning
> > > with `moveto`, possibly ending with `closepath`), the currentpath (which can
> > > contain many subpaths), and the graphics-state stack.
> > >
> > > If I were to make the 'path' out of stacks then that would separate it
> > > from the rest of the graphics state, and I would need a top-level stack
> > > for `gsave/grestore` to operate on. The elements of the top-level path
> > > stack would be "normal" path stacks, the elements of which would be
> > > "subpath" stacks, the elements of which would be path operations (moveto,
> > > line, curveto, closepath).
> > >
> > 
> > OK, but if the elements of the "normal" path were the operations 
> > themselves (just the concatenated operations of all subpaths, without 
> > structuring), it would be conceptually the same, right?
> 
> Yes, I suppose so. I think it would make `closepath` O(n),
> though, since it now has to search for the most recent
> `moveto`, whereas the two-level structuring makes it
> easier to find (and O(1)).

Hm. Maybe not `closepath` itself, if you're just accumulating the data,
but at some point during processing, all the `closepath`s must be
associated with `moveto`s to define the subpaths. If you `stroke` the
path, it must be processed several times: dashing, tracing the outline,
clipping, filling. 

[toc] | [prev] | [next] | [standalone]

#2115

On Tuesday, December 9, 2014 12:40:16 PM UTC-6, luser- -droog wrote:
> On Tuesday, December 9, 2014 12:08:56 PM UTC-6, luser- -droog wrote:
> > On Tuesday, December 9, 2014 7:49:05 AM UTC-6, Carlos wrote:
> > > On 09/12/2014 8:32, luser- -droog wrote:
> > > >
> > > > Sure. I think I was using confusing terminology. I was using the same word
> > > > 'path' to refer to a subpath (a sequence of `lineto` and `curveto` beginning
> > > > with `moveto`, possibly ending with `closepath`), the currentpath (which can
> > > > contain many subpaths), and the graphics-state stack.
> > > >
> > > > If I were to make the 'path' out of stacks then that would separate it
> > > > from the rest of the graphics state, and I would need a top-level stack
> > > > for `gsave/grestore` to operate on. The elements of the top-level path
> > > > stack would be "normal" path stacks, the elements of which would be
> > > > "subpath" stacks, the elements of which would be path operations (moveto,
> > > > line, curveto, closepath).
> > > >
> > > 
> > > OK, but if the elements of the "normal" path were the operations 
> > > themselves (just the concatenated operations of all subpaths, without 
> > > structuring), it would be conceptually the same, right?
> > 
> > Yes, I suppose so. I think it would make `closepath` O(n),
> > though, since it now has to search for the most recent
> > `moveto`, whereas the two-level structuring makes it
> > easier to find (and O(1)).
> 
> Hm. Maybe not `closepath` itself, if you're just accumulating the data,
> but at some point during processing, all the `closepath`s must be
> associated with `moveto`s to define the subpaths. If you `stroke` the
> path, it must be processed several times: dashing, tracing the outline,
> clipping, filling.

On third thought, goddamit you're right!

My implementations of all these other processing steps don't make use of
the structuring at all! They use knowledge of the element dictionaries, 
but they iterate through the current path using `pathforall` or xpost's 
non-standard `devpathforall` which skips the `transform/itransform` sandwich.

They can indeed be flat. Nice catch, dude.

[toc] | [prev] | [next] | [standalone]

#2116

[luser- -droog <mijoryx@yahoo.com>, 2014-12-09 10:49]
> On Tuesday, December 9, 2014 12:40:16 PM UTC-6, luser- -droog wrote:
> > On Tuesday, December 9, 2014 12:08:56 PM UTC-6, luser- -droog wrote:
> > > On Tuesday, December 9, 2014 7:49:05 AM UTC-6, Carlos wrote:
> > > > On 09/12/2014 8:32, luser- -droog wrote:
> > > > >
> > > > > Sure. I think I was using confusing terminology. I was using
> > > > > the same word 'path' to refer to a subpath (a sequence of
> > > > > `lineto` and `curveto` beginning with `moveto`, possibly
> > > > > ending with `closepath`), the currentpath (which can contain
> > > > > many subpaths), and the graphics-state stack.
> > > > >
> > > > > If I were to make the 'path' out of stacks then that would
> > > > > separate it from the rest of the graphics state, and I would
> > > > > need a top-level stack for `gsave/grestore` to operate on.
> > > > > The elements of the top-level path stack would be "normal"
> > > > > path stacks, the elements of which would be "subpath" stacks,
> > > > > the elements of which would be path operations (moveto, line,
> > > > > curveto, closepath).
> > > > >
> > > > 
> > > > OK, but if the elements of the "normal" path were the
> > > > operations themselves (just the concatenated operations of all
> > > > subpaths, without structuring), it would be conceptually the
> > > > same, right?
> > > 
> > > Yes, I suppose so. I think it would make `closepath` O(n),
> > > though, since it now has to search for the most recent
> > > `moveto`, whereas the two-level structuring makes it
> > > easier to find (and O(1)).
> > 
> > Hm. Maybe not `closepath` itself, if you're just accumulating the
> > data, but at some point during processing, all the `closepath`s
> > must be associated with `moveto`s to define the subpaths. If you
> > `stroke` the path, it must be processed several times: dashing,
> > tracing the outline, clipping, filling.

To avoid searching back on closepath, you can keep the subpath starting
point and angle in a variable, and on closepath "lineto" it (the stored
angle is to draw the join). On each path appending operation set the
variable if it's empty, and clear it after each closepath or moveto;
that should be enough for it to always hold the current subpath's
starting point.

> 
> On third thought, goddamit you're right!
> 
> My implementations of all these other processing steps don't make use
> of the structuring at all! They use knowledge of the element
> dictionaries, but they iterate through the current path using
> `pathforall` or xpost's non-standard `devpathforall` which skips the
> `transform/itransform` sandwich.
> 
> They can indeed be flat. Nice catch, dude.

I take no credit for that; it was just you using the old "Rubber Duck"
technique :)  (See http://c2.com/cgi/wiki?RubberDucking)

I guess structuring the path in subpaths could make sense if you
precalculate some values (bounding box, whether it's closed...) and
want to associate them with the subpath, or if your internal
representation requires it. But it's not necessary to do so---that's
what I wanted to make sure and you did.

-- 

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.postscript

csiph-web