# Algorithm to join hexahedra and obtain outline volume

I would like to join several hexahedra and obtain an outline volume.

First, I started with 2D implementation. In 2D, there are non-intersecting quadrangles which always touch each other as shown in the figure. I used CGAL to join polygons and obtain the outline which is also a polygon.

Now I want to extend my code to 3D. In this case, instead of quadrangles, there are hexahedra which also touch each other and do not intersect. CGAL, in this case, is not my first choice because it was a pain to achieve my goal in 2D when I used CGAL.

I would like to know if there is an intuitive algorithm to solve this problem without reading bunch of articles.

• I take it you can assume that the hexahedra are aligned to Cartesian axes, so that each hexahedron can be given by its extent in x, y, and z? Is there anything else that simplifies the problem, e.g. are the original hexahedra aligned to a regular grid? – LedHead Jul 11 '19 at 16:36
• Yes the hexahedra are aligned to Cartesian axes. In fact, the hexahedra are obtained by adaptively refining the initial bounding volume into octants. After refinements, groups of hexahedra should be assigned to processors (parallel programming). – Shibli Jul 12 '19 at 7:56
• It sounds like you can view your geometry as simply a 3D array of voxels, each of which is associated with one of several region or groups of voxels. If that's the case, you can simply find neighboring voxels which are in different groups -- the rectangle between the voxels should be included in the overall surface that bounds each region. – LedHead Jul 13 '19 at 5:43