Is there a triangulation lib somehwere?
Author
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 :)
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"?
Author
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]
@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).
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).
Author
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" .
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.
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.
Author
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 :)
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.
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<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]
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]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
