Oriented Bounding Box using a list of point and a plane

[petrasvestartas]

Issue Details

I am asking for an example how to compute an oriented bounding box from a list of points and plane (not the optimal bounding box).

Is there a data-structure that is a box not a bounding box CGAL::Bbox_3 ?

Source Code

I have following inputs:

typedef CGAL::Simple_cartesian<double> Kernel;

std::vector<Kernel::Point_3>points;
Kernel::Plane_3 plane;

[MaelRL]

Are the points assumed to be on the plane? What result do you expect?

[petrasvestartas]

Hi @MaelRL ,

I would like to get a box rotated in space. according to plane z axis. I have 2 problems that I do not know how to do in CGAL: 1) Is there a data structure of box but not an axis-aligned box? By box I mean a representation of a plane and 3 min/max intervals for x y z:

 //Orientation of a box
  Plane plane; 
  // intervals are finite and increasing when the box is valid
  double dxMin, dxMax;
  double dyMin, dyMax;
  double dzMin, dzMax;

2) An idea i have is to orient points from 3D plane to xy plane and compute axis-aligned bounding box, then transform axis-aligned bounding box back to 3d. But I do not know how to create transformation from one plane to another. And as mentioned before, I cannot find a box data structure. I tried to search for such transformation but it is not [here] (https://doc.cgal.org/latest/Kernel_23/classCGAL_1_1Aff__transformation__3.html) . From documentation I see that the box is represented by 8 points or a mesh.

PSEUDO CODE X0 Y0 Z0 are plane0 axes and X1 Y1 Z1 are plane1 axes

  // F0 changes x0,y0,z0 to world X,Y,Z
  Transformation F0;
  F0[0][0] = X0.x; F0[0][1] = X0.y; F0[0][2] = X0.z;
  F0[1][0] = Y0.x; F0[1][1] = Y0.y; F0[1][2] = Y0.z;
  F0[2][0] = Z0.x; F0[2][1] = Z0.y; F0[2][2] = Z0.z;
  F0[3][3] = 1.0;

  // F1 changes world X,Y,Z to x1,y1,z1
  Transformation F1;
  F1[0][0] = X1.x; F1[0][1] = Y1.x; F1[0][2] = Z1.x;
  F1[1][0] = X1.y; F1[1][1] = Y1.y; F1[1][2] = Z1.y;
  F1[2][0] = X1.z; F1[2][1] = Y1.z; F1[2][2] = Z1.z;
  F1[3][3] = 1.0;

  result = F1*F0;

In short: I really need to know if there is a box data structure in CGAL and how to perform such transformation from 3d plane to xy plane. Please be aware that I am relatively new user.

[petrasvestartas]

The transformation from plane to plane is this. Checked it works. I still do not know how to represented an object oriented box, not axis aligned. Also the planes are represented here are 4 vectors origin and xyz, which I also did not find any data structure in CGAL to represent. For now I represent a box like an array CGAL_Vector box [5] and plane CGAL_Vector plane [4]

//https://stackoverflow.com/questions/23270292/a-point-cgal-transformation-between-two-coordinate-systems
//https://github.com/mcneel/opennurbs/blob/7.x/opennurbs_xform.cpp Line1960
inline CGAL_Transformation TransformFromPlaneToPlane(
    CGAL_Vector O0, CGAL_Vector X0, CGAL_Vector Y0, CGAL_Vector Z0,
    CGAL_Vector O1, CGAL_Vector X1, CGAL_Vector Y1, CGAL_Vector Z1
) {

    // transformation maps P0 to P1, P0+X0 to P1+X1, ...

    //Move to origin -> T0 translates point P0 to (0,0,0)
    CGAL_Transformation T0(CGAL::TRANSLATION, CGAL_Vector(0 - O0.x(), 0 - O0.y(), 0 - O0.z()));

    //Rotate ->
    CGAL_Transformation F0(
        X0.x(), X0.y(), X0.z(),
        Y0.x(), Y0.y(), Y0.z(),
        Z0.x(), Z0.y(), Z0.z()
    );

    CGAL_Transformation F1(
        X1.x(), Y1.x(), Z1.x(),
        X1.y(), Y1.y(), Z1.y(),
        X1.z(), Y1.z(), Z1.z()
    );
    CGAL_Transformation  R = F1 * F0;

    //Move to 3d -> T1 translates (0,0,0) to point P1
    CGAL_Transformation T1(CGAL::TRANSLATION, CGAL_Vector(O1.x() - 0, O1.y() - 0, O1.z() - 0));

    return T1 * R * T0;
}

[lrineau]

Maybe I am off-topic, because that is not topic I am proficient with, but its seems that CGAL::oriented_bounding_box can compute the affine transformation you are looking for.

[petrasvestartas]

Thanks, I already looked at this. But in my case I already know the orientation, just have no clue how to store it besides 4 vectors + xyz dimentions as a 5th vector.

The issue is that this method outputs only points and transformation matrix. It would be really useful if CGAL would have a plane definition with origin point ant XYZ vectors which is what oriented bounding box is.

Probably I am used to using OpenNurbs that have these basic geometric types that is why it is a bit hard to shift to CGAL, but I am trying by replicating of few of these types which combines axial and plane equation definition into one:

• https://github.com/mcneel/opennurbs/blob/c20e599d1ff8f08a55d3dddf5b39e37e8b5cac06/opennurbs_box.cpp
• https://github.com/mcneel/opennurbs/blob/c20e599d1ff8f08a55d3dddf5b39e37e8b5cac06/opennurbs_plane.cpp

@lrineau Also thank you for replying to my posts, these days I am trying to learn a lot from CGAL and understand what it has and what I have to write from scratch.

[MaelRL]

Thanks, I already looked at this. But in my case I already know the orientation, just have no clue how to store it besides 4 vectors + xyz dimentions as a 5th vector.

If you already know the orientation, you just need the lengths and that's an axis-aligned box (that's pretty much what the OBB does: optimize the transformation and minimize the volume of the axis-aligned box).

There is no existing representation that will fit what you want.

The issue is that this method outputs only points and transformation matrix.

The 8 points returned by OBB are equivalent to the plane representation you would like to have: if you have x0...x7, you can take an arbitrary origin and get your three vectors (and lengths).

It would be really useful if CGAL would have a plane definition with origin point ant XYZ vectors which is what oriented bounding box is. Probably I am used to using OpenNurbs that have these basic geometric types that is why it is a bit hard to shift to CGAL, ...

There is a Plane_3 type (see https://doc.cgal.org/latest/Kernel_23/group__kernel__classes3.html and related pages for the existing objects), but it uses an algebraic representation internally, so you can construct from your 3 points, but you will lose your plane basis.

Do mind that in CGAL, geometric objects are not just storing a representation of that object, meaning Vector_3(Point_3(0,0,0), Point_3(1, 1, 1)) is the same as the Vector_3(Point_3(10,10,10), Point_3(11, 11, 11)), because mathematically it is the same vector.

[petrasvestartas]

There is a Plane_3 type (see https://doc.cgal.org/latest/Kernel_23/group__kernel__classes3.html and related pages for the existing objects), but it uses an algebraic representation internally, so you can construct from your 3 points, but you will lose your plane basis.

Can you show how to do what you wrote? I am trying to learn these new concepts.