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:



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:



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):



This can be solved:


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:



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:

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]

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.

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.

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

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").



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?