PDA

View Full Version : Detection of edge of a polygon



jenny_wui
01-02-2013, 10:27 AM
I have one polygonal model with sharp edge at one end. Howcan I automatically detect the edge of apolygon? Is there any algorithm available? Thanks.

Carmine
01-02-2013, 12:31 PM
I have one polygonal model with sharp edge at one end. Howcan I automatically detect the edge of apolygon? Is there any algorithm available? Thanks.


What do you mean by 'sharp edge'? I can think of two interpretations:
1) the poly does not share this edge with any other polys, or
2) the angle between this poly and a neighboring poly is large (> 10 degs?).

Unshared edges are fairly easy to search for assuming non-redundant vertices.
Just loop through all the edges of the model, checking against all other edges (defined by vertices).
It's not fast, but it's easy to code up. This won't work if you have redundant vertices, which means
vertices sharing the same coordinates. In this case you'd have to do a preprocessing loop to merge
redundant verts.

To find large (up to you to define) angles between neighboring polys, compute the flat normals to
each poly, then compute angles between normals of neighboring polys. In this case the proprocessing
might consist of merging redundant verts, then looping through all polys and edges to figure out which
polys neighbor each other.

Have fun.

jenny_wui
01-02-2013, 02:35 PM
Thank you very much for the reply. Could you explain"vertices sharing the same coordinates", I didn't get it. I aminterested to find the ends of a polygon. I want to consider a simple case.Suppose i have cylinder with two ends closed. That means the cylinder has twoedges. As the ends are closed, I think your first suggestion won't apply. Ineed to go for second one i.e. 2) the angle between this poly and a neighboringpoly is large (> 10 degs?). Isn't it?

But in my case I am interested about the end edges (if there is any) and edgesare closed. Can I put some other conditions to separate the end edge from theinternal edge? Is there any other solution for the ends? Do I need to checkwhether the vertices form a loop to separate the edges?

Carmine
01-02-2013, 03:17 PM
....second one i.e. 2) the angle between this poly and a neighboringpoly is large (> 10 degs?). Isn't it?
The angle between the top and bottom faces of a cylinder and the side faces are 90 degs, which is far more than 10 degs.


.... I am interested about the end edges (if there is any) and edges are closed.
I assume you have access to all of the geometric information on this cylinder shaped object. That would include which vertices make up which polygons, and what the x, y, and z coordinates of each vertex is. With this info you can compute flat normals of every polygon making up the object. Do you know how to do this? That would be the first step in identifying which edges are 'sharp'.

Redundant vertices would be two or more vertices at exactly the same coordinates. For example it's quite possible that an extra set of vertices is specified to define the end polygons of a cylinder, even though their coordinates would be the same as the vertices making up the side polygons. This is done intentionally to prevent rendering codes from trying to do smooth shading around sharp edges.

jenny_wui
01-02-2013, 03:28 PM
Yes, but I am thinking about some more complex model; how can I separate end edges from other sharp corner?? Like cyliner, the end vertices may not always lie on a plane.

Carmine
01-02-2013, 04:05 PM
Yes, but I am thinking about some more complex model; how can I separate end edges from other sharp corner?? Like cyliner, the end vertices may not always lie on a plane. The end vertices of a cylinder do lie in a plane, even if it's not a right, circular, cylinder. Sounds like you have some tube-like structures. Are the ends of the tubes closed or not? You seemed to indicate that they were closed before. If so, what are they closed by - a non-planar polygon? What about the rest of your model? Is it also made up of non-planar polygons?

_michaelm
01-04-2013, 11:06 AM
Can I recommend 'Computational Geometry in C' by Joseph O'Rourke - excellent coverage of collision/edge detection with convex/concave shapes (2d) hulls (3d) and a whole host of other things. (28 on amazon: http://www.amazon.co.uk/Computational-Geometry-Cambridge-Theoretical-Computer/dp/0521649765/ref=sr_1_1?s=books&ie=UTF8&qid=1357326361&sr=1-1) - helped me massively through advanced graphics module at university.

sevenfold
01-05-2013, 04:45 PM
If you're working with edges, you should probably use a half-edge data structure to find them quickly and easily.
Then you can start building your own tools upon it.

jenny_wui
01-06-2013, 10:24 AM
Thank you all for the suggestion. If the edges of the polygon is closed, will still the half-edge data structure will apply? Actually what I wantto do is as follows:
I have a polygonnal data where boundary edges are closed.
There is also some non-boundary sharp edges.
I want to separate only the boundary edges;
closed boundary may be non-planar polygons;

Thanks in advance for your suggestions.

jenny_wui
01-08-2013, 05:07 PM
Also I would like to know whether the edges form a ring, is any algorithm available for it?

Carmine
01-09-2013, 11:37 AM
Also I would like to know whether the edges form a ring, is any algorithm available for it? Would like to help, but the info you're providing is too vague to answer such detailed questions. How are your polygons defined? Could you post a small example of the data? If you post a list of ~10 polygon definitions and corresponding vertex definitions, I think you'll get some responses.

jenny_wui
01-09-2013, 01:37 PM
The polygon is defined as an .obj file. I have extracted the vertices and triangles.

Carmine
01-09-2013, 02:38 PM
The polygon is defined as an .obj file. I have extracted the vertices and triangles.That's a start. We are all familiar with .obj format. Could you post a small example of one of your .obj files and repeat your question(s) relative to the geometry in that file? You could probably get by with an .obj file containing 20 polys and their associated vertices.

Or - here's another approach. Can you compute and display the flat normals for the polys in one of your files? If you can do that, you can probably solve your problem.

jenny_wui
01-09-2013, 03:16 PM
Yes, I have vertices and triangle in obj file. I already calculated flat normals and vertex normals of each triangle.

Carmine
01-10-2013, 12:42 PM
Yes, I have vertices and triangle in obj file. I already calculated flat normals and vertex normals of each triangle. Now check the angle between the flat normals of the triangles sharing an edge. If that angle is greater than some threshold angle (which you set), you have a sharp edge. This should be easy assuming that shared edges use the same vertices. For example, say Poly A is defined by vertices V1, V2, and V3, and Poly B is defined by vertices V1, V2, and V8. Polys A and B share edge V1-V2. Check the angle between the flat normals of Polys A and B. If it's greater than your threshold angle, you've identified a sharp edge. If edge V1-V2 is only used by one poly, it's an open edge and should be flagged differently.

jenny_wui
01-10-2013, 01:47 PM
Thanks. Is there any way to find whether the edges form a ring?

Carmine
01-10-2013, 03:06 PM
Thanks. Is there any way to find whether the edges form a ring?
Don't know what you mean by a 'ring'. Do you know what you mean by 'ring'?
If you can clearly define to yourself what you mean by a 'ring', you'll probably
be able to come up with an algorithm to find 'rings'.

Would help us to see an example of your geometry with one of the so-called 'rings' highlighted.

Good luck.

jenny_wui
01-10-2013, 03:46 PM
Sorry., I could not explain properly. Ring is formed when vertex v1 has edge with v2, v2 with v3......vn-1 with vn and vn with v1 again.

Carmine
01-10-2013, 05:50 PM
Sorry., I could not explain properly. Ring is formed when vertex v1 has edge with v2, v2 with v3......vn-1 with vn and vn with v1 again.

Again, that's only a start. There has to be a LOT more to it than that - otherwise you could find infinite rings in an object. In fact, every polygon is a ring by your definition. This is what I meant when I said you have to think carefully about what you mean by a 'ring'. If you can define it, you'll be able to compute it.

RigidBody
01-11-2013, 05:40 AM
so, basically you have pairs of vertices, aka edges, e.g.

{v1, v2}, {v4, v3}, {v1, v4}, {v3, v2}

and want to find out if they make a closed loop?

that is rather complicated. i'll go and ask my colleagues...brb

edit: so, i after asking my colleagues, i can say you need something they call a "for-loop" and some "if-statement"s.
i got lost in the discussion when someone said something about "compiling" and "linking".

jenny_wui
01-11-2013, 08:29 AM
Actually I am working on some algorithm . Taking a seed point on the surface of a polygon. And propagate it considering the linked vertives. Suppose, v1 is my seed point. It has edge with v2, v3, v4 and so on. Next I am considering the link vertices of v2, v3, v4. Next iteration considering their links and so on. Now when viewed the behaviour of propagation of a seed point, it seems at some stage of iteration, some outermost layer points meet and forms a closed edge. Definitely one or a few of the outermost layer form a closed edge. I need to know at what stage the closed edgeis formed to avoid further iteration.
Thanks for any further suggestion. Pls ask me if needs further clarification.

Carmine
01-11-2013, 10:16 AM
Actually I am working on some algorithm . Taking a seed point on the surface of a polygon. And propagate it considering the linked vertives. Suppose, v1 is my seed point. It has edge with v2, v3, v4 and so on. Next I am considering the link vertices of v2, v3, v4. Next iteration considering their links and so on. Now when viewed the behaviour of propagation of a seed point, it seems at some stage of iteration, some outermost layer points meet and forms a closed edge. Definitely one or a few of the outermost layer form a closed edge. I need to know at what stage the closed edgeis formed to avoid further iteration.
Thanks for any further suggestion. Pls ask me if needs further clarification.

Once again, using that approach, every polygon will be a 'ring'.
I don't think that's what you want.
Also, you could easily wind up with an infinite number of rings.

A couple of ideas:

. . . . 1) disregard single polygons as rings,
. . . . 2) find a way to spatially constrain the vertices relative to your seed point.
. . . . . . (otherwise you'll get huge 100 point rings snaking all around your object)

- C

jenny_wui
01-11-2013, 03:21 PM
Yes, I am thinking some way to constrain the vertices relative to the seed point. Any further suggestion regarding this will be very helpful.