$Id: dp.wml,v 1.14 2000/08/15 05:19:18 tjl Exp $
Tuomas Lukka lukka@iki.fi Dept. of Mathematical Information Technology University of Jyväskylä |
||
This is a short exposition of the design problems currently in ZigZag (as of June 2000). The intent is to eventually evolve this into an exposition of the internal design of GZigZag, after the problems are solved. But at the moment most of the problems still exist.
Note that this document contains some formatting that is best rendered using a true CSS1 standard-compliant browser such as Mozilla; however, it should work reasonably well with any browser that can at least ignore CSS that it doesn't understand. Unfortunately, Netscape Navigator 4.7, for example, doesn't. Well, that's life...
A non-CSS version exists: you can try by compiling this document from its WML version with some switches.. (if you came here through the WWW, there should be an alternate link on the referring page. However, I like the pretty rendering by Mozilla so much that that's still the default.
This document is intended as an internal discussion document on the most difficult design problems for the GZigZag source code. This is work-in-progress: if there are any unclear parts, feel free to ask me to clarify things.
The FloatingWorld graphics model built on top of ZigZag is based on flexibly plotting objects defined by cells on the screen. ZigZag rasters are simply a special case of this: the coordinates are given by hopping along ZigZag ranks and the objects rendered are simply the cells and the texts inside them.
Conceptually, there are two kinds of objects shown on the screen: flobs and relations. Also, there are three different processes in the background: where are flobs rendered, what kind of flobs are rendered and what relationships between them should be shown. All these are relatively independent of each other and should be clearly decoupled in the backend.
Animation has been supported from very early on in GZigZag with excellent results: the human eye can use the motion to understand the relation of the different views in time much better than if the views are just switched without the intermediate frames. This feature should be global: if the same object is shown in two consequent views, it should animate from the previous view to the next to show the deep relationship between the two appearances. Even a simple linear interpolation, without any regard to the true structure of the transformation between the two views is astonishingly helpful. It is easy to see that animation mostly concerns the flobs which must interpolate their coordinates frame by frame between rasters. In fact, currently the links are not shown when animating; this does not appear to be a significant problem to the human observer: maintaining a high frame rate is much more important than giving a complete picture.
In addition to animation, depth perception of the human eye is misused in the vanishing raster to a great advantage: cells further away from the cursor are shown smaller and grayer and are rendered behind the cells closer to the cursor. I term this a misuse since there is no 3D model behind: it's just an algorithm that lays out cells that happen to look smaller and grayer and thus further away.
A simple case where rendering a link in one go gives suboptimal results.
A beam with cells is even more complicated: the beam has to be between the text and the cell background but behind any other cells on the way to avoid cluttering the screen. If the beams' borders should float above the beams, then this gets even more difficult.
A fairly short-term goal in the expansion of GZigZag is to make it support 3D graphics using OpenGL, as well as retain the current functionality using pure Java graphics. Especially useful would be the ability to use the 2D views directly through the OpenGL layer, as well as 3D views, and the ability to animate between the two.
If small factories are used for letting the rasters create cells, handling depth gets more complicated.
There are also interesting problems in the rendering order of links: if there is a link between cells that are at different depths, then which cells should be in front. It is especially difficult to include something like beams into this framework, if a Z-buffer and a real third coordinate is not used. One possibility is to split all links and beams in the middle and render the two halves independently. However, as seen in the beam figure, that will not be enough.
Let us start from the obvious.
For each raster, the locations and appearances (and the depths for rendering) of the flobs must be stored somewhere quickly accessible for the animation between rasters.
The raster must ask the flob-producer what size and aspect ratio would be most suitable (given a shrinking factor). Being able to cache something that was calculated (such as a line breaking) would be most beneficial. Of course, depending on the form of the raster, it may or may not accept the size and aspect ratio given by the flob producer. The flobs are internally cached as objects that know how to render themselves and how to interpolate between two keyframes.
The links are produced after rastering, from the coordinates of the flobs. This operation is thus well encapsulated from changing rasters. In fact, the links do not even need to be made into self-standing objects at all times: all that is needed is that the FlobSet knows to call a certain method of a certain object to plot links.
These considerations produce a rather different picture
from the current one. The classes Flob
and
FlobSet
would be the natural starting point. A
FlobSet, unlike the current ZZCanvas, would only store the flobs
and not the connections. The connections could be drawn just as
the flobset is being rendered from back to front.
One interesting point regarding the identification of Flobs from the FlobSet is that the FlobSet may be hierarchical in nature. For example when doing the VStreams-in-Cells raster, the same vstream might be shown in two different cells (clones of each other). Now, if flobs were identified just by their cell, then the flobs for the spans of text would be identical and therefore interpolated animation could do very strange things. The trivial solution to this is to allow container flobs to exist, which exist just to identify that certain cells are accessed through a certain other cell. If the FlobSet has knowledge about this, it is easy to both treat the FlobSet as flat (for e.g. beams), or as the hierarchy (for identification of the corresponding flob in another FlobSet for animation).
This solution is currently being tested as of 20000806.
The hierarchy does not solve all the problems and brings some new ones. Some operations use hierarchy, some don't.
Because the hierarchy is kind of optional, the hierarchy in the current prototype is simply handled by identifying each flob with a string ("path") and a cell. This seems to give both enough detail and efficiency.
Another interesting feature with the views are decorations: things that either connect flobs between each other or show some relationship in some other way (for example, the three-line thing that shows the directions of the coordinate axes).
These decorations aren't considered first-class citizens like flobs in the current model. This may make it possible to find extremely efficient ways to implement them. One obstacle to efficiency, however, is that the decorations should be rendered at the same depth as the cells. If we have a Z-buffer like in OpenGL, this is of course not a problem.
Now, there are several kinds of decorations:
In order to trample over less memory, it would be nice to be able to render global decorations for a set of cells (at a given depth) at once.
There is one situation where decorations present a problem,
and that is when the decorations should move with the interpolation.
This is generally desirable in complicated views (e.g. email-flob)
to provide the user with additional visual cues about the structure.
There is a slightly incorrect solution that get us close to where
we want: a decoration that wants to interpolate is named a flob
and it stores references to the flobs and uses their
interpTo
fields to calculate the interpolated
coordinates. The only problem is the depth: this algorithm does
not correctly alter the depth in interpolation.
However, when using java.awt.Graphics
none of the other
flobs take care of their depths properly when interpolating so
it is not a problem. And if using three-D graphics, the renderer
can use the flobs' Z coordinates.
One of the versions of Ted's specs specifies the following
structure for flob.
First of all, there is the central handle cell which
is the center of the flob. The flob is referred through it and
all the parts of the flob can be found through it.
That version of the spec specifies d.handle
as the dimension to
reach the rest of the flob from the handle cell, and
d.ref
as the dimension to use to refer to that handle cell and
thereby to the whole flob. (the spec has apparently changed
now but the changes do not affect this problem).
The cells on d.ref
are basically stand-ins for the whole flob,
kind of like clones are stand-ins for a cell.
An email can be included in several mailboxes (lists of emails
running on d.2
) by including cells that are on d.ref
from
the original email's handle cell.
The problem, then, is basically about what is getting shown: we'd like to be able to show
FlobSet
knows
about the handle cell since otherwise connecting the flobs
becomes a less efficient procedure, requiring the FlobSet to
look at all referring cells to see whether they are included.
So the question really becomes: is there any point in storing the referring cell in the flob structure, except as presentational info about the string and cursor colors to show.
If ZZ is expanded to allow the user to place the text insertion cursor in a cell by a mouse click, then the referring cell is obviously needed if any of its text is rendered.
Well, currently this is solved by having the handle cell always
be the Flob.c
and if the flob has to give out
other events, it can be given a different cell.
The slowest part of the current implementation, as witnessed by time testing, is writing to the file. Also, the current file format does not properly allow undo & branching backtracking.
The goals for the system are
It is vital that the in-memory change list is compact in format and extremely light-weight for Java usage as it is going to be a hot spot.
One relatively sparing implementation would be to have one long
array of Object inside which every third element would be an operation,
and the other two would be its parameters. This way, no separate
Operation object would need to be created and the references to
operations sequentially would stay memory-local: the cost
of the typecast
of Object
to the Operation type is negligible compared
to the cost of accessing two or three long arrays instead of one.
There would likely be one to few Operation objects per dimension object, which is perfectly acceptable.
The long array would have the sequence stamps and would be operable either for undo or for committing to disk.
There is one important problem with this approach: the operations are fairly low-level ops: this cell connected to this one, or disconnected, or whatever. The semantic information about an operation such as insertion is not saved. This could be a problem with synching later on.
In the following, N is the number of cells changed, B is the number of observers. Also, K is the number of cells one observer typically observes.
It is important for the notification mechanism to be fast: specifying a set of cells that a particular entity is interested in and scrapping the whole set (when the entity is refreshed) will very likely be one of the most common operations. Not trampling through a lot of memory and being easily garbage collectible are vital considerations, as well as good scaling w.r.t.~several things.
Observer insertion is naturally O(K) and observer removal is either O(1) or O(K).
If a separate hashtable is used for each observer, testing which observers to wake up is O(N*B) operation, which is not very nice.
Slices are used for viewing a number of ZigZag spaces as one compound space, and for sending a group of cells over to another user. Slices are probably the most crucial aspect of the system for common use as they will enable collaboration and upgrading.
Among the issues here are
d.cursor
and slices.
d.cursor
work here?
d.ref
and d.handle
And of course the really important question of what we're really after. Slices have distinct, but related functionalities:
d.version
or somesuch.
Of the above functions, the most critical one for GZigZag currently is the packages: distributing the main default space as a slice would be a great step: then it would be possible for users to start stable personal spaces which would not be needed to be brought forwards for every new version of the bindings.
The most important problems here are cursors. Just about
everything else can be resolved by explicit hook cells ("hook your
own bindings negwards on d.3
here"). Cursors are
a different matter. They are used for several things, to name
a few:
Additionally, there is the cursor cargo dimension which allows cursors to piggyback on one another - for example, combining the cursors for one view and another view's X axis allows one to change the dimension list for the X axis by moving the other view's center.
The default space and other packages which have views will most likely have cursors. In order for the spaces to be useful, these cursors should be movable when the package-slice is included and should be movable by changing the main space, not the package-slice. Also, cursor cargo should be changeable.
There is a simple solution to these problems: the package slices'
own d.cursor
and d.cursor-cargo
are
mapped to some other dimensions, e.g. d.ps-cursor
.
When a slice is first incorporated into the system, the
default cursors from the slice are copied to the global
d.cursor
. There then need to be operations on the
slice cell to reload or commit the cursors of a slice, which
simply copy the assignments of the cursors to the package-slice
(provided all cursors lie on cells of that package-slice as
they should) or copy the cursors from the package-slice to the
main space.
Because waiting for the full design to be finalized would have seriously slowed down development (as the main developers wouldn't be able to use GZZ for real work) there is now a primitive slice implementation in place. Even in its rudimentary form it is surprisingly complete. In addition, this experiment gives valuable experience in the complexities of implementing any types of slice systems.
The system works by handling two dimensions, d.slices
and (naturally) d.cursor
specially. These are in
fact the only dimensions that are allowed to connect between the
slices; all others are constrained to be only among the cells
of the same slice.
The dimension d.slices
simply connects the homecells
of the slices in the slice order. There are no other connections
along this dimension and it cannot be modified.
d.cursor
is a different matter. In order to be
useful, even the most trivial slices must allow connections that
transcend the slices on d.cursor
. In this model,
d.cursor
is constrained so that the only operation
allowed is insertion negwards (currently the cursor is obtained
by going to the end of d.cursor
poswards, which
will change). Also, cells in slice 0 may be inserted to any
other cell but not vice versa: cells (cursors) in other slices
may only point to cells in the same slice.
These semantics are fairly simple but still their correct
implementation is not at all trivial, especially for
d.cursor
. The implementation uses preflets in
slice 0 to connect to the other slices and when reading, the
whole rank in slice 0 is placed before all the other cells in
the non-zero slice accursing the same cell, so the cursors are
not necessarily in the same order they were inserted in.
One possible solution in the long term to the package-slice problem is simply having adapter-like slices for the external packages. These slices would have preflets pointing to s.0 as well as the external package - possibly even without intervening cells.
Versioning is one of the most difficult problems in defining a ZZ space.
This is because having a versioned space is not useful, unless
cursors can point to past versions of cells using the normal mechanism,
d.cursor
. If views and pointing were handled outside the normal space,
this would be no problem.
This immediately suggests the trivial but unsatisfactory solution of
simply not versioning d.cursor
. This is unsatisfactory because d.cursor
is used for an increasing number of things, e.g. Clang variables: what
good would it be to have access to a previous state without being able
to access the values of the variables.
The other solution, simply allowing retroactive changes to d.cursor
of past cells to point to the future is more attractive but not without
its own downsides. Let's say the user, at time 100 looks at a cell A at time 5
and does some changes in the space, e.g. moves the other cursor or
writes text somewhere else, until time 105 after which he moves
the cursor away. In this case, the rank on d.cursor
from cell A would
contain the user's viewcell at times 100, 101, 102, 103, 104 and 105.
This is not that great either, because the algorithm that displays the
cursor moves through d.cursor
to find the coloring of the cell to show
the colors of the cursors on it. The number of cursors on past cells would
be compounded.
A potentially interesting solution, avoiding the preceding problem,
is to rename d.cursor
to d..cursor
-past for the past cells:
a connection on d.cursor
would mean that a current cursor is on the cell.
This solution is attractive, as it preserves the values of all Clang
variables "pickled" using another dimension on which they can be browsed,
but also does not grow the number of cursors on a cell too much.