benji@hpfcdq.HP.COM (Jeff Benjamin) (04/22/89)
I'm posting this question for someone who can't do it himself, although
I'm also interested in the answer. If you email a reply, also send it
to: mikew@tahoe.unr.edu (Mike Wishart).
Does anyone know if there is a simple algorithm for filling a closed path?
The path may have several loops.
Data structures available: an array of the screen [166x199], a list
containing all the points in the path, or whatever you wish.
This is for a simple PostScript interpreter for CGA or better PC's.
Thanks.
-----
Jeff Benjamin {ucbvax,hplabs}!hpfcla!benji
Graphics Technology Division benji%hpfcla@hplabs.HP.COM
Hewlett Packard Co. Fort Collins, Colorado wiml@blake.acs.washington.edu (William Lewis) (04/23/89)
In article <390030@hpfcdq.HP.COM> benji@hpfcdq.HP.COM (Jeff Benjamin) writes: >Does anyone know if there is a simple algorithm for filling a closed path? >The path may have several loops. >Data structures available: an array of the screen [166x199], a list >containing all the points in the path, or whatever you wish. The following is called a 'seed fill'. Given a point, and some way of determining boundaries, it fills all points connected with the first. seedfill(x,y) { plot(x,y) if((x+1,y) is not a 'border' point) seedfill(x+1,y) if((x-1,y) is not a 'border' point) seedfill(x-1,y) and so on with all points adjacent to (x,y) } Note this is recursive. You can include diagonals as adjacent, or not, as you wish. Oops: when testing to see whether an adjacent point should be also seedfilled, you MUST double check to see if said point has been seedfilled already. IE, if borders are of color A, and you are filling with color B, the condition for calling seedfill() on point(x+h,y+k) is ((color_of(x+h,y+k) != A) and (color_of(x+h,y+k) != B)) hope this helps. ~~~~~~~~~~~~~~~~~sigless~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jonh@tekgen.BV.TEK.COM (Jon Howell) (04/24/89)
The basics are covered in Foley and Van Dam's _Fundamentals_of_Interactive_
_Computer_Graphics_, pp. 448-449 in pseudocode:
A FLOOD FILL converts all adjecent values of the same color to another
color. A BOUNDARY FILL converts all pixels within a certain-colored boundary
to another color.
Foley & Van Dam's FLOOD FILL code:
procedure FLOOD_FILL_4(
x, y, {Starting point}
old_value, {value to convert}
new_value: integer); {Color to conver to}
begin
if READ_PIXEL(x,y)=old_value
then begin
WRITE_PIXEL(x,y,new_value); {change color}
{Attempt to propagate in four (eight) directions}
FLOOD_FILL_4(x,y-1, old_value, new_value);
{Repeat for (x,y+1..),(x-1,y..),(x+1,y..), and
four more if you want an 8-bounded (diag.) region}
end
end
procedure BOUNDARY_FILL_4(
x, y, {Starting point}
boundary_value, {boundary color}
new_value: integer); {Color to fill with}
{it is permissible to have new_value=boundary_value; otherwise no
pixels may be initially set to new_value} [huh?!?]
begin
if READ_PIXEL(x,y)<>boundary_value {boundary not reached}
and READ_PIXEL(x,y)<>new_value {and prev. filled pel not " }
then begin
WRITE_PIXEL(x, y, new_value); {change color}
{four (eight) call to BOUNDARY FILL}
end
end
Get the book. Lots of handy code and algoritms amid the explanations of
hardware. Hope you can make sense of the PASCAL pseudocode. He shoulda
used C. :-)
--Jon
--
jonh@tekgen.bv.tek.com (503) MAK-SEMA Jon Howell | Q: How come they never
// // // _ __ _ . . . . ___ . _ | play that on the radio?
// // // / \(_ __ (_) |\/| /| |\ | | /| / | A: They should.
// // // \_/__) / | | /"| | \| _|_ /"| \_ | --Dave Barryfishkin@pixar.UUCP (Ken Fishkin) (04/25/89)
Seems I send this out every few months.
The fill algorithms alluded to are extremely ineffecient.
Allow me to recommend:
Marc S. Levoy, "Area Flooding Algorithms".
Presented at SIGGRAPH '82 2-D Animation Tutorial.
Uri Shani, "Filling Regions in Binary Raster Images: A Graph-Theoretic
Approach", pp. 321-327, SIGGRAPH '80.
Alvy Ray Smith, "Tint Fill", pp. 276-283, SIGGRAPH '79.
Alvy Ray Smith, "Fill Tutorial Notes", presented at '82 SIGGRAPH
2-D Animation Tutorial.
Ken Fishkin, "An Analysis and Algorithm for Filling Propogation",
pp. 203-212, Graphics Interface '85.
--
Ken Fishkin ...ucbvax!pixar!fishkinjmunkki@kampi.hut.fi (Juri Munkki) (04/26/89)
In article <4295@pixar.UUCP> fishkin@pixar.UUCP (Ken Fishkin) writes: >Seems I send this out every few months. > The fill algorithms alluded to are extremely ineffecient. Thanks, but... I think the original poster said that he wanted to fill the area inside a postscript path. He already had a set of lines so what he wanted was a polygon fill. I've never understood why people would want fast flood-fills. I also seem to remember that the poster wanted source code. On another matter: I don't think I want to see another public domain ray tracer until someone creates a good public domain solid modeling package. What's the use of calculating the same scenes over and over again? _._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._ | Juri Munkki jmunkki@hut.fi jmunkki@fingate.bitnet I Want Ne | | Helsinki University of Technology Computing Centre My Own XT | ^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^