Geometry Boost List: Re: [geometry] 3D box -> 3D multi_polygon conversion

Subject: Re: [geometry] 3D box -> 3D multi_polygon conversion
From: Tomislav Maric (tomislav.maric_at_[hidden])
Date: 2013-06-12 08:28:51

Hi,

I don't think the OGC PolyhedralSurface model will work together with a
multipolygon concept for a polyhedron (surface mesh), since the
connectivity between polygons will be severely complicated to compute
and change during topological operations if the points are repeated for
each polygon.

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'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..

Best regards,
Tomislav

On 06/12/2013 12:32 PM, Barend Gehrels wrote:
> Hi,
>
>
> On 12-6-2013 10:49, Tomislav Maric wrote:
>> On 06/12/2013 01:51 AM, Adam Wulkiewicz wrote:
>>> Tomislav Maric wrote:
>>>> On 06/11/2013 10:12 PM, Adam Wulkiewicz wrote:
>>>>> Correct me if I'm wrong but shouldn't ring, polygon, multipolygon,
>>>>> etc. be always flat? It may be 3D, may have even some orientation and
>>>>> position in 3D space, not only height, but should be flat. This way we
>>>>> can perform some 2D operations on it by e.g. first projecting it into
>>>>> the 2D plane. E.g. we can calculate convex hull (also flat) or
>>>>> triangulate. I'm not so sure if using MultiPolygon concept to describe
>>>>> 3D mesh is a good idea. I'd rather provide additional concept.
>>>> IMHO this would be quite expensive. Coordinate transform is a Matrix
>>>> Vector multiplication, and it costs for nothing, if its only done to
>>>> enable 2D calculation on a 3d object. Another point, consider
>>>> incremental convex hull in 3D: computing the visible face is not
>>>> possible to do this way (mixed product makex only sense for non
>>>> co-planar vectors) simply because the hull construction will lie in 3D
>>>> and transforming it to 2D projection will not work. I'm sure the
>>>> quickhull algorithm is similar.
>>>>
>>> Sure, this was only an example. My point was that maybe there should
>>> be introduced a new, as you've written, MultiPolygon-like concept. And
>>> then algorithms should be built for it. Maybe even you'd like to
>>> extend MultiPolygon somehow or change it to describe meshes in better
>>> way? E.g. should 3D mesh contain faces which are polygons with holes?
>>> Or could those containing only triangles be represented in some
>>> optimized way?
>> Well, I am working on numerical methods for simulating fluid flow, and
>> they need flow domain to be decomposed into polyhedra like MultiPolygon,
>> so physics prevents the polygons of those polyhedra to have holes...
>> What I am aiming at is working on the algorithms in 3D in
>> boost.geometry, that I need in order to optimize my geometrical code for
>> speed + efficiency, and then extend what I get later for a more general
>> purpose.
>>
>> Triangles: that's a great question actually. Basically, the answer is
>> yes and no. Initially the polyhedron is consisted of polygons, but then
>> it is decomposed into tetrahedra to compute its volume and do subsequent
>> intersections. This is done because some of its polygons will be *non
>> planar* (search for voFoam on arXiv.org, page 12 I think).
>>
>> So, there are three concepts, I believe: polyhedron (multipolygon
>> extended), tetrahedron and tetrahedral decomposition of a polyhedron
>> (just triangle faces: e.g. optimized normal vector calculation).
>
>
> The OGC model is our reference model for the concepts point,
> linestring, polygon, multi_point, multi_linestring, multi_polygon. Up
> to now we have followed this model.
>
> See also this webpage, where it can be downloaded:
> http://www.opengeospatial.org/standards/sfa
>
> The OGC talks consequently about a "PolyhedralSurface".
>
> I copy a part from the PDF here for convenience:
>
> "
> */6.1.12 PolyhedralSurface/**/
> /**/6.1.12.1 Description/**/
> /*/A PolyhedralSurface is a contiguous collection of polygons, which
> share common boundary segments. 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. A TIN (triangulated irregular network)//
> //is a PolyhedralSurface consisting only of Triangle patches.//
> //
> For any two polygons that share a common boundary, the "top" of the
> polygon shall be consistent. This means//
> //that when two LinearRings from these two Polygons traverse the
> common boundary segment, they do so in//
> //opposite directions. Since the Polyhedral surface is contiguous, all
> polygons will be thus consistently oriented.//
> //This means that a non-oriented surface (such as Möbius band) shall
> not have single surface representations.//
> //They may be represented by a MultiSurface. Figure 14 shows an
> example of such a consistently oriented surface//
> //(from the top). The arrows indicate the ordering of the linear rings
> that from the boundary of the polygon in which//
> //they are located.//
> //
> /
> /
> Figure 14: Polyhedral Surface with consistent orientation//
> //
> If each such LineString is the boundary of exactly 2 Polygon patches,
> then the PolyhedralSurface is a simple,//
> //closed polyhedron and is topologically isomorphic to the surface of
> a sphere. By the Jordan Surface Theorem//
> //(Jordan's Theorem for 2-spheres), such polyhedrons enclose a solid
> topologically isomorphic to the interior of a//
> //sphere; the ball. In this case, the "top" of the surface will either
> point inward or outward of the enclosed finite solid.//
> //If outward, the surface is the exterior boundary of the enclosed
> surface. If inward, the surface is the interior of the//
> //infinite complement of the enclosed solid. A Ball with some number
> of voids (holes) inside can thus be presented//
> //as one exterior boundary shell, and some number in interior boundary
> shells.//
> /"
>
> Regards, Barend
>
>
>
> _______________________________________________
> Geometry mailing list
> Geometry_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/geometry