Re: [freesci-develop] OpenGL picmap renderer

[Christoph Reichenbach]

Jim,

On Sun, Nov 20, 2005 at 11:55:36PM -0500, James Albert wrote:
> I've been putting off mentioning this because I wanted to have working 
> code first, but during the time last year when I wasn't in touch with 
> anybody I was trying to write an OpenGL picmap renderer.  I'm only 
> mentioning it now because there's been speculation, are there has been 
> before, about using the z-buffer in place of the priority map.  I had a 
> little success, but is there anybody on the mailing list familiar with 
> Computational Geometry? - it could be a big help

  I have the OpenGL red book, version 1.1-- does that help? ;-)

> The current FreeSCI algorithm goes something like this from what I 
> understand:
> - Draw lines and points using the exact same methods as the original SCI 
> so as not to break the fills.
> - For each fill, fill from the given point to the non-white boundaries

  Careful, that's the pic drawing approach: The backend gfx drivers don't
actually seen anything of this. All they see is pixmaps.

> A polygon based algorithm would go something like this:
> - For each line or point, add the necessary geometry data to an internal 
> datamap.  Each line is actually two triangles, forming a quadrilateral.  
> Each point would have to be a polygon of whatever was drawn by the 
> classic algorithm.
> - for each fill, triangulate the current set of geometry data and fill 
> from the current triangle, the one that the given point lies on, to 
> every connected white triangle

  That's a very promising idea for improving the quality of scaled background
images, but beware:

  It is possible for two lines to bound an area for filling even if they do
not touch directly, as in the following example (lines 1, 2 are drawn, then
area '.' is filled):


Low-res (2x2 pixels):

--+--+--+--+--+--+--+--
11|11|..|..|..|..|22|22
--+--+--+--+--+--+--+--
11|11|..|..|..|..|22|22
--+--+--+--+--+--+--+--
  |  |11|11|11|11|  |
--+--+--+--+--+--+--+--
  |  |11|11|11|11|  |
--+--+--+--+--+--+--+--
  |  |  |  |  |  |11|11
--+--+--+--+--+--+--+--
  |  |  |  |  |  |11|11
--+--+--+--+--+--+--+--


Higher-res:

--+--+--+--+--+--+--+--
11|11|..|..|..|..|22|22
--+--+--+--+--+--+--+--
11|11|11|..|..|..|22|22
--+--+--+--+--+--+--+--
  |11|11|11|11|..|..|..
--+--+--+--+--+--+--+--
  |  |  |11|11|11|11|..
--+--+--+--+--+--+--+--
  |  |  |  |  |11|11|11
--+--+--+--+--+--+--+--
  |  |  |  |  |  |11|11
--+--+--+--+--+--+--+--


In the first image, you see what the flood-filling looks like in 320x190 pixel
rasterisation; in the lower image, you see what it looks like in
higher-resolution rasterisation. Effects similar to the ones in the latter
image arise with a purely vector-based approach. While I do believe that this
error can be compensated for (and might be worth a minor paper in CG, if it
hasn't been done before), it must be considered, for otherwise many real-life
SCI pictures don't render properly.

  However, this is unrelated to the difficulties potentially casued by an
OpenGL renderer. Which of the two problems are you primarily interested in
addressing?


> There's pros and cons of course to this approach besides a better 
> picture and hardware acceleration:
> pros:
> - intrinsic priority and control map support through the z-buffer and 
> stencil buffer.  I haven't looked into the stencil buffer other then to 
> speculate about whether it could be used this way.  I think it could but 
> the stencil buffer is more for real time graphic manipulation, like 
> raycasted shadows, and using the stencil buffer outside of the graphics 
> render - to do conditional calculations in the VM - might be very 
> detrimental.

  Depends on the implementation, so I have no idea ;-)

>  The other option here is to use a higher bit z-buffer.  
> Use the lower bits for the control map and the upper bits for the depth 
> map.  This sounds awkard, but as long as objects "jump" between depths, 
> then it won't matter if there's extra depth information at each pixel 
> because it won't affect the render visually.
> - less code to debug, because most of the clipping and other graphics 
> routines are handled by the api
> - portability, OpenGL can be run on systems even without hardware 
> acceleration.

  There is no need to scale the control map (other than that it might be
computed concurrently with the scaled image, but then again we currently
compute a low-res image anyway to ensure "perfect" compliance wrt OnControl()
etc. semantics).

> - There's still the problem of gaps in the fill, but they should be 
> easier to deal with because instead of dealing with pixels you're 
> dealing with geometry data.  My current approach is to add extra lines 
> to the geometry for any triangle smaller then a given size (the size of 
> a gap between pixels), and then fill any unfilled triangles smaller then 
> the gap size with the colors of the neighboring triangles.  The problem 
> with this though is filling holes that were *supposed* to be empty, so 
> if anybody has any other ideas please share them.

  Cf. the above example. I don't recall the precise solution we implemented
for the above issue, but I believe it was roughly based on the idea of
"constraining" the area something could flood fill to from the lower-res
image.

> Here's where I stand right now.  I can read the picmaps and draw the 
> lines but the fills are killing me.  My best solution right now is 
> drawing both the OpenGL and classic versions at the same time, and then 
> overlaying just the OpenGL lines.

  [...]

  It sounds to me as if you're trying to solve two problems at the same time:

(a) An OpenGL graphics driver for FreeSCI
(b) An algorithm which translates a line/pixel/floodfill image into a true
    vector graphics representation

  (a) shouldn't be too painful to do, but (b) is a challenging research
problem. However, doing (b) right won't be much use unless (a) works (and my
impression is that your version already does, at least partially).

  Thus, my personal suggestion would be to stick with (a) for the time being,
and then work on (b), keeping in mind that filling boundaries are nontrivial,
and that your algorithm will possibly be slow. (Then again, it can be
pre-computed). If and when you figure out a solution to this nontrivial
problem, we'll extend the API to support vector graphics drawing. Does that
make sense to you?

  I'm afraid that I can't offer you too much help on (b) myself. I spent some
time thinking about it, but couldn't come up with a good solution to the
"proper boundary region problem". In particular, I didn't even consider the
problem you mentioned above (gaps).

  Anyway, what you have so far does sound quite cool-- do you happen to have
a screenshot of it (with or without gaps)?


-- Christoph