Jump to content
  • Advertisement
Sign in to follow this  
szecs

Outline detection

This topic is 2971 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!