[gameprogrammer] Re: Vector graphics filling woes

On Sunday 14 October 2007, Alan Wolfe wrote:
> Heya,
>
> I've been struggling w/ a problem for a while and am not getting
> anywhere so I'm posting it to the list in hopes that someone can
> help.
>
> The problem I'm having is that I have a lot of line data in the form
> of 2d line segments like this...
>
> Line 0 has 5 verts
> V1 = 3,5
> V2 = 6,7
> V3 = 10,10
> V4 = 0,0
> V5 = 50,-20
>
> Line 1 has 2 verts
> V1 = 0,0
> V2 = 24,25
>
> Line m has n verts
> ...
> (etc)

So are you filling arbitrary closed polygons from arbitrary point?
Or are you filling from arbitrary point with lines forming possibly 
closed shape?

The first one is much easier, but I think you are after the second one 
or something between.

Tell more and I try help as much as I can.



> What i'm trying to do is if I'm given a point (such as 5,5), I want
> to find the outline of the shape that encloses that point (if there
> is such a shape).
>
> All this line data is in memory and is generated by the end user...
>
>
>
> Here's the best I've been able come up with so far but it's not quite
> there yet...
>
> A) I know the bounding box of the line data so i shoot a horizontal
> or vertical line to the nearest edge of the bounding box (to
> hopefully minimize false positives), and i find the line segment that
> collides with that line, that is closest to the fill origin.
>
> B) From there i look to see which side of the line segment is closer
> to the fill point, either the low numbered side or the high number
> side and at this point call a recursive function to search the lower
> side and if that side fails, call the recursive function to search
> the higher side.
>
> C) What the recursive function does is iterate down the line segment
> until any of a couple of things happen...
> 1) The end of the line segment is reached which means it failed and
> it returns false
> 2) The starting point is reached again, which means it succeeded and
> it returns true
> 3) An intersection is reached.
>
> D) When an intersection is reached it has 3 possible paths that it
> can choose from, so what it does is calculate the distance that the
> next segment on each path lies from the fill origin, and it recurses
> to the closest one, and if that fails, to the next closest one, and
> if that fails, to the farthest one.
>
>
> Upon success, as the function is uncoiling the recursion, I have it
> store the vertex information in a buffer so that the outline can be
> known and then the fun part happens where another function breaks
> that outline into triangle fans and actually fills it in.
>
> Sheesh!
>
> The above algorithm isn't working for me and i don't know if it's
> because i'm forgetting some important case or because i didn't
> implement it correctly (it's alot more code than you would think to
> do this!!!).
>
> Does it sound solid? Is there any easier way?
>
> BTW i don't have access to the pixels directly so i can't do scaline
> conversions, i have to come up with geometry to fill it ):
>
> Thanks so much for any help!
> Alan
>
> ---------------------
> To unsubscribe go to http://gameprogrammer.com/mailinglist.html



---------------------
To unsubscribe go to http://gameprogrammer.com/mailinglist.html

Other related posts: