Hi Barend

On 06/12/2013 11:26 PM, Barend Gehrels wrote:

Note that it is the Concept which repeat points. The implementation might be different. I mean: the Concept has methods as NumPatch, Patch(index), or probably an iterator returning polygons. However, this can be stored internally as the implementator thinks it is good.

Besides this, I don't understand - if you want to use multipolygons to store the polyhedron, I always assumed that you wanted to repeat coordinates...

I would definitely like to use multipolygons to store polyhedra, at least as a start, then see how fast the intersection and collision detection wil work coupled with axis aligned bounding box tests.

It is a bit as a collection of polygons, some files (shapefiles) store all coordinates per polygon, others (ESRI coverages) use topology, however, retrieving one polygon always returns just that polygon, regardless how it is stored.

Retrieving a polygon is O.K., but retrieving a common boundary costs with repeating points. And for algorithms relying on polygon boundaries, this incurrs complexity increase. A part in the description of the OGC Polyhedral Surface Model says:

"
For each
pair of polygons that “touch”, the common boundary shall be expressible as a finite collection of LineStrings. Each
such LineString shall be part of the boundary of at most 2 Polygon patches.
"

So, lets say I have two polygons that touch, with repeating points as shown on the attached image for two squares (see attached Figure). Even if the normals of the polygons are consistent (as indicated by the order of the point labels), I don't think that finding the common boundary is trivial. If the points are repeated per each polygon, the touching edge is not known without computation that compares equality of points. If I am to construct a polyhedron that's a multipolygon, I would do:

polygon p1;
p1.push_back...

polygon p2;
p2.push_back...

multipolygon M1;

M1.push_back(p1);
M1.push_back(p2);

At this point M1 has no idea that its two polygons have a common boundary, since for a multipolyon, there are no topological restrictions, if I understand the concept right...

So the only way to compute the common boundary is to find out (checking if points are equal?) that the edge 0-1 in polygon p1 is the opposite of the edge 1-2 in the polygon p2. This is what I mean by complicating things. I am very new to Concepts, so I might be missing your point as well, if so, I'll need read more about it, maybe things get clearer for me.

But if the model is to provide "an accessible common boundary", then the unique-point implementation does it automatically (graph based works better for intersection operations, this I can back up with articles), and the non-unique point (multipolygon concept) requires calculation of connectivity based on I guess equality of points... and equality == precision issues.

To ensure logical point uniqueness (not involving tolerances to drop duplicates), the topology of the surface mesh must be described either as a graph, or using indirect addressing like Adam described in his previous email/ However, I am 100% certain that ensuring point uniqueness with indirect addressing will cause the algorithm complexity to literally explode.

I don't exactly understand why the complexity explodes by just using indirect addressing. It is IMO just a way to access the coordinates. If the Concept gives certain methods, the implementations (using either direct or indirect addresses and either unique or duplicated points) might vary. The algorithms should use the Concept to support different types of polyhedrons.

Say that there is a polyhedron described with indirect addressing. If it is intersected by a half-space, you can know exactly which edges are cut, and from the edge-faces connectivity, you know exactly which edges do not have a face accross them anymore (hole created by the intersection). Intersecting it and updating indirect addressing topology is more difficult then clipping each polygon in a polygon soup and storing 2 intersection points per edge.

Say that there is a polyhedron described as a multipolygon. The intersection with a half-space loops over all polygons, and the results will be polygon clips, or complete polygons, if they are completely within the halfspace. But now we have a hole in our result polyhedron, where the plane lies. How to connect the points of that hole? One way is to re-compute edge connectivity for a concept that doesn't support it (multipolygon) which might involve point equality (quadratic if not worse with respect to the sum of points of both polyhedra). The other way is to do a convex hull in 2D of an already convex set of points which resorts to a single sort operation.

I've tried using indrect addressing and subsequently ensuring point uniqueness, and that is the reason why I want to switch to a multipolygon representation and loose the connection between polygons of the surface mesh, for intersecting smaller non-planar polyhedra. In the end my goal is to efficiently intersect and compute volume of the result between a halfspace and a small polyhedron, two tetrahedral decompositions and two polyhedrons. Maybe this is too specific for the geometry library.. I don't know.. this is just my experience..

I don't think it is too specific, but we need a generic concept able to store polyhedrons described either as triangles, or as polygons.

I'm new to Concepts, I'm only putting in my 2 cents from my experiences with 3D algorithms....

Best regards,
Tomislav

Regards, Barend

_______________________________________________
Geometry mailing list
Geometry@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/geometry