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
_______________________________________________
FreeSCI-develop mailing list
address@hidden
http://lists.nongnu.org/mailman/listinfo/freesci-develop