Is there a triangulation lib somehwere?

You need to explain yourself better, is this for 2D?, 3D? do you mean triangulation as in tessellation or do you mean "the process of determining the location of a point by measuring angles to it from known points at either end of a fixed baseline, rather than measuring distances to the point directly"?

Click

xissm thanks. Didnt know the name of that :) But did you understand me? I was not talking about mesh creation or tesselation of shapes. Your google search did not produce the hoped results

@Kwizatz: It is in 2D and I need to locate points in a planar xy layer which are determined by cordinate and width.
Just imagine a 2d drawing tool for vectors (e.g 2d poly-line). You place n points and define a width. And this rendering is quite complex for many situations :)

Edit: Just to be sure, I looked into CGAL for instance and I found nice polygon generation from points, like I describe some area and CGAL calculates the vertices but I describe a path and width which need to be transformed into some polygonal representation

[Edited by - Seikilos on November 4, 2009 10:04:01 AM]

It is absolutely not clear what you are trying to achieve. It sounds like you want an algorithm that generates limiting points along a extruded spline, and triangulate the result. If that is indeed the case, then this problem needs two very distinct algorithms. A spline extruder and some form of parametric tesselator or triangulator (depending on the output of your spline system). But in order to give any meaningful advice, you need to explain yourself better.

That said, for pure geometric (and not parametric) triangulation, the GLU reference tesselator from SGI (libtess, I believe) is extremely stable, accepts all kind of weird input, can be compiled into an independent library without OpenGL dependencies, and is free (really free, ie. not GPL).

Ok, to be clear now with image:


Left is the input data, I get vertices and a width. E.g user clicks three times onto a canvas and defines a width. On the right side the green dots are the required output.
To draw it I need the real coordinates of the vertices extruded (is this the right word) about the factor "width" .

What you need is a path extrusion algorithm. It has nothing to do with triangulation nor tesselation.

There are many different ways to accomplish this. It's a pretty simple problem in 2D. The basic algorithm works like this:

1) Create a path from input points. This can be a simple line graph (connect successive points with straight lines) or something more complex like one or more splines.

2) Parametrize the path. That simply means that the entire path should be indexable by a parameter p in the range [0,1] which will cover the entire path (0 being the start, 1 being the end).

3) Walk along the path by increasing p (in regular distance intervals, adaptively depending on curvature, by jumping from control point to control point - many different schemes exist), and create limiting points by extruding the path at the current position p. This is very simple in your case, since you just have to create two points along the path normal at a certain distance. It's more complex when extruding in 3D.

4) Optionally you can now triangulate the resulting polygon to get a triangle mesh for rendering.

Yeah that's somehow wrong :)

It is very complex and not even Inkscape does it good.

I have already done that and Image this example above with much more points, like an spline rasterizer would generate a dense vertex list. Bow if you extrude these vertices by a certain length where where the "normals" of the direction start to intersect you end up with a degenerated vertex geometry.
And to avoid reinventing this wheel I ask here for libs. There is already a significant amount of time spent for this task including several people. The complexity lies in the details.

So thats why I look for a "path extrusion" library :)

I've been working on the same problem, I generate a "contour" (points along the boundary/surface of the extruded shape) and then triangulate them using knowledge about how they were generated; I don't know if the latter step is a good idea, it may have been less effort to just use a general triangulation method (i.e the glut tesselator).

I have to disagree with Yann, this is a *very* hard problem if you're trying to avoid degeneracies. Problems happen when there are any combination of: concavities (especially sharp/acute ones), short segments in the "core" (non-extruded) path, or very large/wide amounts of extrusion.

For example, in your picture, if you steadily increase the amount of inflation/extrusion, the points you generate along the bottom edge will converge. I'll attach a diagram showing this; any amount of inflation past the point circled in blue and you'll get "buckling" (not sure if that's the correct term; the contour turns inside-out.

Possibly there's no correct solution, in such cases it seems like the extrusion process itself is ill-defined.

I'd love to know if there are any papers about this sort of process.

Does it have to be real time?
If no, then find out all the possible situations, detect them, and solve them one by one.

Or detect the degrading points somehow then eliminate them.

I think that didn't help you at all.

Or:
calculate all the parallel lines. You can calculate their start and end points (by intersecting them with the 2 'width' lines of the segment).
Express the equations of these parallel segments with these 2 points.
In the form of v=p_start+parameter*(p_end-p_start), where 'parameter' is the scalar parameter.

After that intersect all calculated lines against all the other calculated lines. And if you find intersection points that are inside the 0
After all this (at least I think) you have the lines with new endpoints, and some lines that degenerate completely.

Or maybe not........

[Edited by - szecs on November 4, 2009 12:20:44 PM]

It must be highly realtime since it is a mission critical here :)

Quote:

Original post by raigan I have to disagree with Yann, this is a *very* hard problem if you're trying to avoid degeneracies.

From the explanation the OP gave (and from his picture), I assumed he did not want to geometrically remove degenerated and self-intersecting faces, but simply hide them in the rendering process through a very tolerant triangulator. Which makes the problem very easy. It seems I misunderstood him. If you want to clean up the result, then things become obviously more involved.

Although this is still 'simple' when you compare it to doing it in 3D ;)

I edited my previous post. Hope it helps you.

if you do the p_start, p_end think consistently.

idea:

I'm not sure about that....

EDIT: if you intersect the lower-left red with the little marked red line ('intersection 1'), then intersect the lower-right red with the small one ('intersection 2'), the order of the intersection points will be reversed, if you compare to the start and end points of the little marked red line.
So you could determine that the small line can be eliminated completely.

[Edited by - szecs on November 4, 2009 1:57:23 PM]

Yeah, you got the issue pretty well (without me requiring to draw it :D)

And since there is also alpha involved I cannot simply hide some "not-so-good" situations :)

Basically it must be perfectly generated

Quote:

Original post by Seikilos And since there is also alpha involved I cannot simply hide some "not-so-good" situations :)

Hmm, that depends. Can you elaborate a bit on how exactly you intend to use the final result ? In fact, many geometrical algorithms that tend to be numerically unstable can be stabilized very well by putting them into a quantized domain, and potentially converting them back into a non-degenerated geometrical form. Transforming a degenerated geometry into a voxel cloud and performing iso-surface extraction is an example.

Rendering inherently converts geometry into image space domain, and can therefore be used to hide such artifacts very well. If you don't need to perform additional geometrical operations on the result, then rendering it in its degenerative form can be a good option. By using appropriate layered shaders, transparency is usually not a problem even if you have thousands of partially overlapping triangles. In the end, you are looking for an union operator.

Quote:

Basically it must be perfectly generated

There are situations where this is impossible due to numerical instabilities.

Well the list of vertices is drawn by opengl as single triangles and is somehow restricted since the draw process is already under heavy usage where using additional stencil buffer is already a performance hit. Using voxel cloud and iso surface extraction on a large amount of data would not be accepted by the client.

Even though I would love to use some third party lib since the details of this process are quite irrelevant for us atm and not to implement additional algorithms which create a new set of possible errors and testcases

Yann is right, only get as complex as you need; for instance, if you need alpha and don't want overlapping regions to be darker, you can always render the (potentially overlapping) geometry into the stencil buffer, and then render a transparent quad using the stencil as a mask.

If you need/want anti-aliasing, smooth edges, or to do further processing on the generated geometry, this isn't a feasible solution though.

If you CAN get by with such an image-based method, the good news is that you don't even need to triangulate the shape since you can use the stencil for concave polygon rendering as well. See for example http://zrusin.blogspot.com/2006/07/hardware-accelerated-polygon-rendering.html (although that page describesan Even-Odd fill rule, which will make overlapping regions look wrong -- other rules are possible, but not with 1-bit stencil).


In general I think that the problem is very hard to solve, because you need a global solution. For instance take szecs's solution: this is a local solution which solves the problem at that one bend, but if there are many such bends in close proximity, then it fails.

We spent several weeks attempting to get such a rule-based method to work, and it was always almost-perfect but never all the way. Our current solution is to use a constraint solver which relaxes the extrusion amount per segment in order to avoid buckling (the "order reversal" that happens when the extrusion is too large), however this is specific to our application and you might not be able to get away with arbitrarily decreasing extrusion.

We also investigated a CSG-based solution, which might be a better approach if you have heavy degeneracies. Sadly robust CSG is also another hard problem.. :(

Also, if anyone knows what this sort of process is actually called, we had a very hard time googling for relevant material. Medial-axis and straight-skeleton of a polygon are similar concepts, but not quite the same thing.

[Edited by - raigan on November 4, 2009 3:43:22 PM]

Quote:

Original post by raigan If you need/want anti-aliasing, smooth edges, or to do further processing on the generated geometry, this isn't a feasible solution though.

Antialiasing is not a problem with a multisampled render target. Keep in mind that stencil is also sampled at subtexel resolution. Alternatively, you could also use the depth buffer for this, and save yourself the stencil pass.

Or: (last reply)


So intersect all parallel lines with all parallel lines. The intersection points that count on a segment are between its start and end points.

start from the first red segment and find the first valid (dark green) point, than go to the next segment (which shares that valid point), and go in the same direction, until the next valid point and so on. Do it on the other side of the black line too.

I don't know how to manage the closed areas (green circle with the green '?').
Maybe going along the first line (in the case the drawing shows) on the false direction (blue line), until finding valid points (the first has to be an intersection point, not an endpoint of the parallel segment).
If you reach the first point again, you can close the loop.

The biggest problem is to decide wich point is valid or not. A valid point is the closest intersection point to the current point on the red path (or endpoint) in the proper direction: arrow on the image.
If the starting point of the whole thing is valid, you can find all the edges this way (red lines).

One situation has to be handled: if the black curve intersects itself.

Just the idea, but maybe a good starting point.

Respond if anyone thinks it's a usable idea. (I'm very curious about this one)

[Edited by - szecs on November 4, 2009 4:29:53 PM]

3ds Max can do this operation on splines, it is called outline:





But if you exaggerate in the parameter the spline overlaps itself.