Sign in to follow this  
Seikilos

Is there a triangulation lib somehwere?

Recommended Posts

Does someone know a triangulation library? For example: I have 3 vertices describing an angle and I have a width of let's say 100 pixels. What I need is the triangulated list of vertices to be drawn. It is pretty basic for usual scenarios to write an own algorithm but this is, however not trivial for all situations. There must be such a lib somewhere, I just can't find it. Those complex situations arise when the vertex positions + width create intersecting points, so drawing them creates areas of overlapping. I do not need the drawing itself just the triangulation, well let's say a robust triangulation :)

Share this post


Link to post
Share on other sites
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"?

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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" .

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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 :)

Share this post


Link to post
Share on other sites
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.


Share this post


Link to post
Share on other sites
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<parameter<0 interval you will know, that one of the endpoints are degenerate.

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]

Share this post


Link to post
Share on other sites
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 ;)

Share this post


Link to post
Share on other sites
I edited my previous post. Hope it helps you.

if you do the p_start, p_end think consistently.

idea:

imageI'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]

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Or: (last reply)

image
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]

Share this post


Link to post
Share on other sites
@szecs: Your approach is currently similar to our current solution. The issue with it, as you pointed is a posssible intersection of your black line.

We did some fallback paths for those kind of solution but it turned out that the client is twisting this damned polyline as long as he find some instability, e.g. intersections.

@xissburg: Im sure this isnt stable too. Or there is an additional AND-ing done to create a correct description of the area.
You could try to draw szecs first image and create a very thick outline and check whethere the inner edge does intersect or not

Share this post


Link to post
Share on other sites
Self intersection is not an issue, if you think it over, at least for the outlines.
The inner lines, well if you find a valid line segment (that's not on the outlines), you can repeat the algorithm (until you find the segment you started with.)

valid segment: upper, invalid: lower
image

i, j, k, f, g, are the indexes of the parallel segments. (if you calculate in sequence)
If an intersection point from a line, that has a greater index, has greater 't' parameter value, than an intersection point from a line, that has a lesser index, that's a valid segment. (There can be more of it on a line).

A segment is invalid (the whole segment), if its direction is opposite to the generator line (t = 1 comes first, than t=0);
A segment is invalid if it seems valid (it fulfills the above conditions), BUT: one of its endpoints is nearer to the generator the line, than the 'distance' (loop through all the generator segments)

So:
1. find a valid segment, that's not included in the already found outlines
if not found: we're done!
if found, continue
2. Go through the path as I described in my previous post ('t' parameter increases)
3. Go through the opposite direction the same way('t' parameter decreases)
4. go to step 1

It works with self intersecting generator lines too, in any cases.
Because it only cares of going through the outline, and if you consider, if we're on a valid segment, we always can find the next valid (or reach the end, or the starting segment (inner outline loop))

Because you intersect all precalculated outline segment with all the others, so this method doesn't care of the topology.

All you have to do is index sequentially (that should be easy)

But of course this process is real slow. So only update when the generator line changes.

Share this post


Link to post
Share on other sites
The "slow" factor is key issue here. We have of course cached drawing so no recalculating if not necessry but at some point when redrawing occurs, it always occurs on all such lines at the same time (of course only within view bounding rect) but a typical test case which we somehow 'must' pass is a recalc of several hundred polylines with dense packed path coordinates resulting in some >10.000 vertices for which intersection and reiterion must be done.
Oh and of course this is not the only part of the draw, there textures and so on.


It's like wanting a great AI but only giving 1% of the computation power to it

Share this post


Link to post
Share on other sites
Ok then the question, the others have asked already: Why is has to be perfect?
I tell you that you will never find a method that finds the outlines perfectly, in realtime.
It's like looking for the perpetuum mobile.

A path-finding problem is nothing compared to this problem.

Share this post


Link to post
Share on other sites
Last idea:
Find all the intersection points (intersect all pre-calculated outline segments with all the others)

1.Find a valid point (valid point = if its distance of all the generator segments are greater or equal to the given distance ('width'))
2.Find the next (neighbour) valid point
3.If you are done with one outline, go for the next one.

for the distance form a segment:
image
in that area

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