Sign in to follow this  
szecs

Outline detection

Recommended Posts

I couldn't come up with a better name for it.
This question is risen for time to time and I was so interested, that I finally tried out "my algorithm".

The idea is here.

I'm talking about this stuff:
image
image

So, we are searching for the contour of the thing.

It turned out, that the problem is more complicated than I thought in that thread, but I could overcome the issues and the algorithm stayed quite general. There are only a few cases that need to be handled, but they are mostly related to the behavior of the outline, not the algorithm itself (for example: how to handle sharp turns (>90 degrees); how to handle the two ends, if they turn, and are very short compared to the outline distance, these are addressed later).

briefly about the algorithm:

control polyline: obviously the line strip that needs to be outlined
contour: the thing we are looking for.

The parallel lines (outlines from now) need to be determined first, which is a pretty simple thing (HAHA! see later).
This is the trapezoid stuff:

trapezoidz

Every segments of the contour polyline has two outlines (on both sides). We had to add the two "caps" at the ends to the outlines of course.

Simply calculating the trapezoids (as shown in the image) has a mayor issue (red line):

trapezoidz_issue

This can be solved:

trapezoidz_solution
So, we don't let the parallel lines (red lines) to be shorter.
(maybe that was only an issue for me...)

Intersecting every outlines with each other: only in the segment of course (p = p0 + t*direction, 0 <= t <= 1). That means we will get a bunch of intersection points (at most outline_num^2 / 2). It's practical to store the intersection points in a structure: position, indices of the two lines, and the "t" params on both lines (see the line equation above)

Finding valid points on the contour:
this is the hardest and most important step. An intersection point is a valid contour point if: it's not inside any of the trapezoid patches (but it's allowed to be on the edges of it). A patch is defined by one outline, and one segment of the control polyline. Since one control polyline segment has two outlines, indexing thus finding the patches is quite simple. (handling of the "caps" is a bit hacky).
By finding the valid points, most of the work is done.

Finding valid segments on the contour:
We can exploit one thing:

valid_segments

If you look at all the lines: there are always even number of valid points on a line.
And the segments are always in the following sequel on a line: valid-invalid-valid-invalid-valid.
This is true for any situations (I knew the reason before, but I've forgotten it...).

So all we have to do is sorting the valid points by their "t" parameter, then assign their index to the contour line buffer exploiting the valid-invalid-valid stuff.
The contour line buffer can store the indices of the two points that define the valid segment

This means we have all the contour segments (including inner loops). But in a screwed sequence, so not very usable yet (but okay for displaying).

Sorting valid segments:
The starting and end points of the segments can be matched, so we can get the line strips (this is the part where we have to handle the different loops).
I haven't implemented this yet (I don't care, looks good anyway).

That's basically it.
It has issues:
precision issues: collinear control points, or neighbor control points too close to each other can screw the whole stuff.
the two ends can couse trouble:
end issue
All these issues can be solved with a simple trick:
The user defined control polyline, and the real polyline used for the calculation is separated:
The real polyline is "repaired": too close points and collinear points are removed, and the end segments are elongated if necessary.

I haven't handled sharp turns in the contour polyline yet, I could simply add a new piece of segment if the turn is greater than 90 degrees, but that means I have to add some triangle data to the stuff (for the point validation), but I don't have time for it now. (adding points to the real control line is not an option, since 180 degree turns need to be handled too).
180 degree turns mean infinite long outlines, so precision error, so near 180 degree turns will cause the algo to fail ATM.
The end elongation stuff is still a heck (so fails sometimes), I need to come up with a more general solution.

I can tell more details if someone is interested, but I don't think I will show the code, because it's a horrible spaghetti heck. (it's not the algo's fault, it's my fault, and the lack of time's).

Anyway, you can try the stuff here:

outline.zip
(A added to an existing project, I'm lazy).

The algo is realtime (runs at every event: even when panning the view, but laggy with 100 control points), instructions inside (hopefully the text will be rendered).

Thanks for reading.

EDITIED some typos

[Edited by - szecs on May 30, 2010 10:41:21 AM]

Share this post


Link to post
Share on other sites
Would it be fair to summarize this as,
- Replace each line segment with a rectangle.
- Compute the CSG union of these rectangles.

?

Share this post


Link to post
Share on other sites
Quote:
Original post by Emergent
Would it be fair to summarize this as,
- Replace each line segment with a rectangle.
- Compute the CSG union of these rectangles.

?
I don't know. I don't know how CSG represents shapes (never did CSG stuff).
I just presented a possible solution, which I can link if the question comes up again.

Share this post


Link to post
Share on other sites
no it is not as simple as replacing line segments with rectangles and taking the union, if you look at the example mid length through his post with the zig-zag you can immediately see simply doing the CSG trick wouldn't work.

Share this post


Link to post
Share on other sites
Quote:
Original post by luca-deltodesco
no it is not as simple as replacing line segments with rectangles and taking the union, if you look at the example mid length through his post with the zig-zag you can immediately see simply doing the CSG trick wouldn't work.


I see...

I wonder what the central principle is then... I.e.; there's an algorithm; it compute something; it looks very good... but what is it computing?

It doesn't jump right out at me what the answer is. Clearly, "the output of the algorithm" is an answer, but usually there's also a simpler answer...

Share this post


Link to post
Share on other sites
It computes the green lines. That means you will have line strips (series of vertices), that you can use as wall data or for triangulation for example.

Look at the thread I linked. The OP wanted to calculate the green lines precisely. Sure, the effect that you can see could be replicated with shaders, drawing the stuff then image processing or anything else. But the whole point is to calculate the green lines.

This question is asked sometimes (there was a thread about polygon inset ("inner contour"), this can be modified to do that), it interested me, that's all I guess.

To the CSG stuff: it is something like that, not with rectangles, but with trapezoids (and triangles, if sharp turns are handled).

The CSG gave me an idea, I could covert the stuff to patches (which is simply another form of data representation), I think that would simplify the point validation part.

Share this post


Link to post
Share on other sites
The algorithm woks nicely with arbitrary lines.
But fails miserably with more structured stuff:
it handles collinear edges very poorly. I could solve some of them with a hack, so the contour will be displayed well most of the time, but it has degenerate elements, or it may not be closed, some segments are duplicated.

In the end, Emergent is right, it's just a CSG problem. Maybe I will try to solve it myself, but I guess it will be reinventing the wheel.

Anyway, added some new editing features, so you can try and see the algo fail.

outline.zip

Share this post


Link to post
Share on other sites
Awesome! I implemented something similar a year or so ago and it was definitely much trickier than anticipated :)

To handle the problem of the intersection shooting off to infinity as the lines become parallel, we add bevel/miter planes which clip/truncate things.

We took a slightly different approach overall, which is that we didn't want to explicitly CSG/clip anything. Instead, we avoid degenerate solutions by using a relaxation-type solver which adjusts the inflation amount per-segment (we support different inflation amounts, adding bevel planes to fix cases such as e.g two parallel adjacent segments with different inflation amounts). This way, as you squeeze stuff towards an awkward state (where the outline would buckle or self-intersect) it shrinks the segments to avoid self-intersection.

Of course it's still not 100% as we got busy and didn't have time for fun projects :)

Your solution of clipping all edges together explicitly and then extracting the valid regions is a great alternative. Do you plan on posting the source or pseudocode for your algorithm? Your explanation is good, but there are a few parts I don't understand (such as the meaning of the diagram with the caption "So, we don't let the parallel lines (red lines) to be shorter.
(maybe that was only an issue for me...)").

Anyway.. nice!!

raigan

Share this post


Link to post
Share on other sites
Thanks!

I meant that using simply the trapezoids won't do (see image in my first post with red thick lines, and the little "pit").

image

So simply don't let alpha to be less than 90 degrees.
Of course, this stuff is for uniform outline distance, I haven't thought about variable distance, But I guess the mayor issue is the clipping.

I replaced the valid segment detection with a more general one: if the middle point of the segment is a valid point, the segment is valid, otherwise not.

I don't know if I work with it further, because it is really a CSG problem which is a solved stuff so I don't know if I want to reinvent it.

Maybe. One idea I have is to boolean collinear lines together, and to have a data structure of one patch (primitive) like: coordinates of vertices, indices of border lines, but that's all. The biggest problem I have is the point in poly algorithm, because it has to be dead precise (impossible). Or I have to come up with a clever data structure (which indicates shared vertices/lines), and do some magic with it...


I don't think I will post the code, because it's a real mess and I don't have time to clean it up. Maybe a pseudo, but since it clearly has issues (although visually it may look perfect) I don't know if it's meaningful to post.
If I ever implement the CSG stuff, maybe I'll make a small editor that is usable for I have no idea what...

Anyways, did you try the program? Is it more stable than your solution?

Share this post


Link to post
Share on other sites
Yes, your solution is completely different than mine.

I looked into CSG (more precisely polygon-polygon clipping) and it is a very complex topic. The problem is with the numerical errors and degenerate cases (3 lines intersect at one point, collinear segments etc). So I was very naive to think I can solve the stuff in a few days hacking.

Anyways, "my" algo could still be useful for editors, because the user can remove false points, edit degenerate stuff etc. (if this function is useful for something).

Maybe a simple bitmap image processing would do: simply render the stuff into a high resolution buffer, then perform an edge detection algorithm (slow as hell).

Share this post


Link to post
Share on other sites
Quote:
In the end, Emergent is right, it's just a CSG problem. Maybe I will try to solve it myself, but I guess it will be reinventing the wheel.


Don't get me wrong; I think this is impressive! I'm just trying to understand it. Plus there's nothing "just" about CSG; it can be hard. (And anyway, there's more going on here than just CSG; you're generating bevels and stuff...)

Quote:
Uploaded a new version: sharp turns are handled.


Looks like there's a threshold on the turn angle, under which you add additional "bevel" segments?

Quote:
because it is really a CSG problem which is a solved stuff so I don't know if I want to reinvent it.


Although it probably would be good to figure out exactly what other people have done in this area, I've got to say that just because you may end up using some established CSG algorithms in your solution doesn't mean that it's not a contribution.

Actually, I think that being able to frame what you're doing in terms of known CSG operations is useful. It gives you a description of the algorithm that can "fit in your head," which is important.

So, on that topic, how about this:
- Start with a realization of a graph in 2d (i.e., points in a plane, connected by line segments, in some "network.")
- Create a collection of the following shapes:
    - A rectangle for each line segment (of width 'w')
    - A particular polygon* for each vertex
- Compute the CSG union of these shapes.

* Now, each "vertex polygon" is constructed by generating a number of points and sorting them, in the following way:
- For each graph edge incident on a graph vertex, there are two vertices that are added to your list: These are the endpoints of the segment of length 'w' that is perpendicular to the graph edge and whose midpoint is the graph vertex.
- Sort this list in clockwise/CCW order around your graph vertex; these are the ordered vertices of your "vertex polygon."

I think this does it.

This is illustrated below:


The graph vertices and edges are the black dots and line segments, respectively. In the top figures, the rectangles corresponding to each graph edge are drawn in blue, and the "vertex polygons" are drawn in red. The line segments whose endpoints are the vertices of the vertex polygons are drawn separately on the lower figures in orange.

Share this post


Link to post
Share on other sites
I didn't get you wrong, but it is more a CSG problem. I mean the generation of the offset edges is not a big deal. You can define the behavior of the sharp turns as you like. Your method (always using rectangles), my method (see image) or something else.

Yours would be simpler, since it's much easier to check against rectangles (in fact that means a distance from the generator segment and in the t = 0...1 region, so the code is the same as the line selection code (UI) ).
But I didn't want to always add a segment, so that corners can be sharp below 90 degree turns.

image


The hard part is the CSG itself, but in this particular case it can be specialized, so a bit simpler than a generic CSG.


Share this post


Link to post
Share on other sites
Quote:
Original post by szecs
I mean the generation of the offset edges is not a big deal. You can define the behavior of the sharp turns as you like. Your method (always using rectangles), my method (see image) or something else.

What I thought was important was the decoupling of the "how you generate vertex polygons" (my method, yours, or something else) from the "taking unions of everything." Also, it doesn't jump out from the image I made, but I actually didn't always use rectangles; the red "vertex polygon" in Example 2 is actually a hexagon.

I also wanted to generalize from a path to a more general graph structure, as I assumed this was something you'd eventually want -- and I think that the "vertex polygon" idea and the decoupling of their generation from taking unions makes this easier.

Quote:
I didn't want to always add a segment, so that corners can be sharp below 90 degree turns.

After I posted, I thought to comment that my method for generating "vertex polygons" wouldn't do that. Still, your desire for sharp 90-degree turns should be compatible with the idea of generating convex "vertex polygons;" it just means a somewhat more complicated rule. Nevertheless, you'll end up with convex "vertex polygons" -- something which I suspect is important.


Quote:
The hard part is the CSG itself, but in this particular case it can be specialized, so a bit simpler than a generic CSG.

I think there's a tension here between a pretty expression and implementation of your problem (generate shapes; take union), and the desire to put everything together in "one fell swoop." I guess here it comes down to preference, but I think that here I'd lean towards the former, since so long as you can use some robust and well-established algorithm to compute unions, then all you have to worry about is the aesthetic issue of how you want to generate your "vertex polygons." You seemed to be concerned about writing clean code and avoiding hacks, and this felt like a way to achieve that.

However if your code is complete and you're happy with it, awesome. In that case, this CSG union concept is really just a way for me to fit what your program does into my head.

Share this post


Link to post
Share on other sites
I am decoupling the two stuff. It's just the polygon-polygon clipping doesn't have to be generic. A generic stuff needs to handle situations like this:

image

and probably some more wicked stuff I can't even imagine.

For example I don't have to make calculations with the lines that connect the end of the outline and the control segment (the perpendicular segments). Since they will always be clipped. Otherwise I would have some hard time to handle the shared edges/vertices.

But I think I simply don't understand what you are saying. Sure, I could use a library for the CSG. But I'm crazy.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this