TGLZBoundingBox

[dicepd]

Starting on this I noticed the create has strange behaviour.

Create takes a point and at the moment creates a bounding box which is larger than the point itself. It negates each of the X,Y,Z components and create a box sized from the point to the negative vector passed in. If this BB were then to be added to either by point or BB it would be a lot larger than it needed to be for any spacial tests. Potentially leading to having to process the internal points in situations where the contained points would not intersect the opposing volume, wasting processing time.

It does not even fit the use case of potential rotations which is already handled by a bounding sphere if you want to use a bounding sphere in that manner. (BSphere of max vector length from origin)

There maybe something I am missing here but a create like this feels wrong to me especially if we are making 'optimised' routines for spacial tests. I am presuming this is the BB used for local BB of non transformed scene objects. Though such a BB could be constructed with far less storage and processing using just two vectors.

[jdelauney]

Create takes a point and at the moment creates a bounding box which is larger than the point itself. It negates each of the X,Y,Z components and create a box sized from the point to the negative vector passed in. If this BB were then to be added to either by point or BB it would be a lot larger than it needed to be for any spacial tests. Potentially leading to having to process the internal points in situations where the contained points would not intersect the opposing volume, wasting processing time.

This comes from GLScene. This behavior is not foreign to me at all. And that's a bit what I feared and that I suspected since already a time, that some GLscene 3D routines were not very reliable

this two screenshot from GLScene BB is the white box. We can see that the BBs are not very precise

I am presuming this is the BB used for local BB of non transformed scene objects.

Yes this why TGLZFrustum have BBSphere Parameters, is for quick space partionning

Though such a BB could be constructed with far less storage and processing using just two vectors.

Yes for less strorage. we need see how to change the actuals functions

I'll do more research on BoundingBox Maths.

[dicepd]

I can only comment on implementations I have done in the past. Mostly for local BB we generated the minvec and maxvec from the items array of points. Basically iterating through the items array of points doing a min.max against min and max vec. These were used as storage points for the BB. If we required a transformed cuboid we then generated the 8 local points and faces if required and transformed them with the items stored transform matrix. Sometimes for spacial inclusion it can be quicker to use 6 planes as in frustum don't know which would be quicker in SIMD as it does not really liking branching or comparison.

[jdelauney]

Mostly for local BB we generated the minvec and maxvec from the items array of points. Basically iterating through the items array of points doing a min.max against min and max vec. These were used as storage points for the BB. If we required a transformed cuboid we then generated the 8 local points and faces if required and transformed them with the items stored transform matrix

I visualize what you mean, i think. A more "dynamicaly" way should be best for performance.

Sometimes for spacial inclusion it can be quicker to use 6 planes as in frustum don't know which would be quicker

If you want you can take a look in GLScene\Sources\GLSpacePartition.pas for give you and idea. But No waste your time now with that :)

[dicepd]

I will modify BB to what I am used to and if you don't like it we can roll back (but I am sure you will see the simplicity of it)

[jdelauney]

I trust you on it and in addition you much more stall than me in math :) 👍

[dicepd]

Something like this

  TGLZBoundingBox = record
  private
  public
    { Create a starting BB with zero volume}
    procedure Create(Const AValue : TGLZVector);
    { Create a BB from two abitary points}
    procedure Create(Const P1, P2 : TGLZVector);
    { Create a BB from precomputed min max values}
    procedure CreateQ(Const AMin, AMax : TGLZVector);

    class operator +(ConstRef A, B : TGLZBoundingBox):TGLZBoundingBox;overload;
    class operator +(ConstRef A: TGLZBoundingBox; ConstRef B : TGLZVector):TGLZBoundingBox;overload;
    class operator =(ConstRef A, B : TGLZBoundingBox):Boolean;overload;

    function Contains(P1: TGLZVector): boolean;

    // Todo rewrite to return Array[0.7] of TGLZVector or move to SceneObject
    //function Transform(ConstRef M:TGLZMAtrix):TGLZBoundingBox;

    Case Integer of
     0 : (Points : Array[0..1] of TGLZVector);
     1 : (MinV, MaxV :TGLZVector);
     2 : (MinX, MinY, MinZ, MinW: single;
          MaxX, MaxY, MaxZ, MaxW: single);
  end;                                         

procedure TGLZBoundingBox.Create(Const AValue : TGLZVector);
begin
  MinV := AValue;
  MaxV := AValue;
end;

procedure TGLZBoundingBox.Create(Const P1, P2: TGLZVector);
begin
  MinV := P1.Min(P2);
  MaxV := P1.Max(P2);
end;

procedure TGLZBoundingBox.CreateQ(Const AMin, AMax : TGLZVector);
begin
  MinV := AMin;
  MaxV := AMax;
end;

class operator TGLZBoundingBox.+(ConstRef A, B : TGLZBoundingBox):TGLZBoundingBox;overload;
begin
  Result.MinV := A.MinV.Min(B.MinV);
  Result.MaxV := A.MaxV.Max(B.MaxV);
end;

class operator TGLZBoundingBox.+(ConstRef A: TGLZBoundingBox; ConstRef B : TGLZVector):TGLZBoundingBox;overload;
begin
  Result.MinV := A.MinV.Min(B);
  Result.MaxV := A.MaxV.Max(B);
end;

class operator TGLZBoundingBox.=(ConstRef A, B : TGLZBoundingBox):Boolean;overload;
begin
  Result := CompareMem(@A, @B, SizeOf(TGLZBoundingBox));
end;

function TGLZBoundingBox.Contains(P1: TGLZVector): boolean;
var
  minT, maxT: TGLZVector;
begin
  minT := MinV.min(P1);
  maxT := MaxV.max(P1);
  Result := (minT = MinV) and (maxT = MaxV);
end;

// Todo rewrite to return Array[0.7] of TGLZVector
//function TGLZBoundingBox.Transform(ConstRef M:TGLZMAtrix):TGLZBoundingBox;
//var
//  I: Integer;
//begin
//  //Result := Self;
//  //for I := 0 to 7 do
//  //  Result.Points[I] := M * Result.Points[I];
//end;

[dicepd]

The contains function shows how this method allows minimum usage of compares to do the simple contains point. This is SIMD friendly unlike the previous code.

And I would be inclined to move the transform BB to be a method on an array of Vectors or SceneObject. Or a helper defined after we introduce simple cube.

[dicepd]

Damm I have just realised I have just recreated the AABB by doing this. Need to look at/think about what happens with a transformed BB as 8 Corners.

[jdelauney]

Ok i've open my 3D Maths book and this is what it say about AABB first

Bounding boxes may be either axially aligned or arbitrarily oriented. Axially aligned bounding boxes have the restriction that their sides must be perpendicular to principal axes. The acronym AABB is often used for axially aligned bounding box, and OBB is used for oriented bounding box.

A 3D AABB is a simple six-sided box with each side parallel to one of the cardinal planes. The box is not necessarily a cube—the length, width, and height of the box may each be different.

Computing an AABB for a set of points is a simple process.We first reset the minimum and maximum values to “infinity,” or what is effectively bigger than any number we will encounter in practice. Then, we pass through the list of points, expanding our box as necessary to contain each point. In our AABB class, we will define two functions to help with this. The first function “empties” the AABB: void AABB3::empty() { const float kBigNumber = 1e37f; min.x = min.y = min.z = kBigNumber; max.x = max.y = max.z = -kBigNumber; } The other function “adds” a single point into the AABB by expanding the AABB if necessary to contain the point: void AABB3::add(const Vector3 &p) { if (p.x < min.x) min.x = p.x; if (p.x > max.x) max.x = p.x; if (p.y < min.x) min.y = p.y; if (p.y > max.x) max.y = p.y; if (p.z < min.x) min.z = p.z; if (p.z > max.x) max.z = p.z; }

Transforming AABBs As an object moves around in our virtual world, its AABB needs to move around with it.We have two choices—either we compute a new AABB from the transformed object, or we can try applying the same transform to the AABB as we did to the object. What we get as a result is not necessarily axially aligned (if the object rotated), and it is not necessarily a box (if the object skewed). However, computing an AABB for the “transformed AABB” (we should perhaps call it a NNAABNNB — a “not-necessarily axially aligned bounding not-necessarily box”) should be faster than computing a new AABB for the transformed object because AABBs have only eight points. So, to compute an AABB for a transformed AABB, it is not enough to simply transform the eight corner points. Nor can we simply compute new pmin and pmax by transforming the original pmin and pmax—this could result in xmin > xmax, for example. To compute a new AABB, we must transform the eight corner points and then form an AABB from these eight points. Depending on the transformation, this may result in a bounding box that is larger than the original bounding box. For example, in 2D, a rotation of 45
will increase the size of the bounding box significantly,

![2018-02-19_231658](https://user-images.githubusercontent.com/29355534/36399212-1d63c210-15cb-11e8-8489-3f5a30b782d7.jpg)

Vector3 AABB3::corner(int i) const {
// Make sure index is in range...
assert(i >= 0);
assert(i <= 7);
// Return it
return Vector3(
(i & 1) ? max.x : min.x,
(i & 2) ? max.y : min.y,
(i & 4) ? max.z : min.z
);
}

Testing Against the View Frustum Testing a bounding box (either axially aligned or oriented) against the view frustum is relatively simple. The basic idea is to test the eight corner points of the box against the six clip planes. If all of the points are on the “outside” of one or more of the clip planes (for example, if they are above the top clip plane), then the box is obviously not visible and can be rejected. For example, in Figure 16.1, the box on the lower left can be rejected because it is completely outside the left clip plane.

Now for OrientedBB

An OBB is an oriented bounding box: this is a box placed at an arbitrary orientation. Computing intersections against OBBs is more complex than against AABBs, but OBBs can sometimes more closely enclose an object and moreover have the flexibility to move with an object as it changes orientation.

So in essence, all eight corners of the box touch the surface of the sphere so that the box is contained within the sphere. An alternative would be that the sphere is contained within the box so that the sphere touches the middle of each of the six sides of the box

This is the infos i have. it will take me some time to decipher and visualize all that

[dicepd]

Ok my thoughts so far.

Assumptions

• Each group of Points (SceneObject) has a local AABB
• Center of AABB does not have to be origin of local Axis.['bones have origin at flexure point]
• AABBs are created trivially at generation or load time
• AABB are invariant over the unmodified life of the object.
• Change to Points will require generation of new AABB

We can construct two types of BSphere from this AABB Enclosing and Enclosed. I have not yet seen indications of an Enclosed BSphere in the current code base but it is useful to have as a short cut to deciding if we definitely have to do a full test of the objects points. Enclosed center is the same obviously, Enclosed radius is MinXYZ(MaxV - Center) so not an onerous calculation at object generation/load time.

So when the dist plane to center is between Enclosing and Enclosed radius this is the grey, non trivial, area of interest to possibly using a OBB, or other shortcut, to determine volume overlap.

Let us think of the worst case scenario for such a body. This would be a near planar object with minimal thickness (piece of paper for instance). This would have large enclosing radius and tiny enclosed radius.

One shortcut that springs to mind here would require a short axis normal and go something like If we are undecided then Check inclination of short axis normal to plane normal against enclosing radius v dist to plane.

This looks like it could be done with some form of cross/dot prod single test. Could be coded within a modified BSphere. Would not require any OBB here for trivial case. This test would guarantee 'outsideness' of the object only. Which is a good thing as we could reject it quickly.

Then is the time to test the OBB points.

Here efficiency would dictate that we build OBB from non transformed AABB as everything is orthogonal at that stage in the model build. When we place an object in the scene the transform is applied to these points as well for static items. Here we have a trade off of static v dynamic scene objects and whether to precompute the OBB transform or not.

For compound objects I would envisage that combined AABBs would be at each level of heirachy.

Ok the more I think of this the more I think that the AABBPoints struct is the only storage we require. Operations on base AABB are quick. Adding transformed OBB looks much slower than using the transformed AABBPoints Struct in a proper heirarchy of scene objects. One of these will need storage space within a scene object.

[jdelauney]

First I like how you explain more simply :)

One shortcut that springs to mind here would require a short axis normal and go something like If we are undecided then Check inclination of short axis normal to plane normal against enclosing radius v dist to plane.

I'm reading some other articles on web. AABB is used for fast collision detection and the most frequently cited solution is to use the "Separating Axis Theorem" And OBB are often use with BSPTree and Octree.

This looks like it could be done with some form of cross/dot prod single test. Could be coded within a modified BSphere. Would not require any OBB here for trivial case. This test would guarantee 'outsideness' of the object only. Which is a good thing as we could reject it quickly.

Yes, definitively a good thing. When we render a scene the first thing to do is to exclude object if not in field of view.

For compound objects I would envisage that combined AABBs would be at each level of heirachy.

I agree, At each level a test a little more precise each time.

Ok the more I think of this the more I think that the AABBPoints struct is the only storage we require. Operations on base AABB are quick. Adding transformed OBB looks much slower than using the transformed AABBPoints Struct in a proper heirarchy of scene objects. One of these will need storage space within a scene object.

For what I could read, most of the 3D engines implements only AABB because it is faster.

I forgot. OBB is use most in raytracer engine. It's normal in deep, this needed more accuracy for raycast

[jdelauney]

I found this https://www.scratchapixel.com/lessons/advanced-rendering/introduction-acceleration-structure/bounding-volume not have the time for read now. But seems interesting and have some C code as reference (it's seems for OBB)

[dicepd]

Your last reference is good for ray intersection but not volume to volume intersection which is our current area of investigation. Here is a well illustrated Separating Axis Theorem reference not read it fully yet.

Separating Axis Theorem for Oriented Bounding Boxes.pdf

[dicepd]

So TGLZHmgPlane.IsInHalfSpace is, in essence, doing a projection of a point onto the plane perpendicular line. It is fast and work well until we hit the following scenario.

Here all points of the OBB are outside the frustum so TGLZHmgPlane.IsInHalfSpace tests will not pick this up. However we should have got a hit from all planes saying we are inside due to enclosed radius.

However if the BB intersect was nearer to the points the enclosed radius would not intersect a plane and we would be left with a possible, as would the case here if they were just separated. The current AABB has a method which tests all eight points from BB in frustum then all eight points from frustum in BB then 12 BB edge intersect Frustum. That is a lot of processing, 28 * 6 tests. If we got a possible in this scenario then using SAT for just the 3 transformed axis of the BB against the 8 Frustum points would give us a solution.

We should be able to construct the three plane normals from the OBB points or maybe even quicker from the transform matrix(it should already contain the axis normals in the rotation parts of the matrix). Then we require 3 * 12 (4 from the BB 8 from the Frustum) points to give a solution.

[jdelauney]

Ok i see i visualize better this :

The basic problem with spheres is that there is only one degree of freedom to their shape — the radius of the sphere. An AABB has three degrees of freedom — the length, width, and height. Thus, it can usually adapt to differently shaped objects better. Notice that the AABB is highly sensitive to the orientation of the object; compare the AABBs for the two rifles on the bottom. In each case, the size of the rifle is the same: only the orientation is different between the two. Also, notice that the bounding spheres are the same size, since bounding spheres are not sensitive to the orientation of the object.

You said :

or maybe even quicker from the transform matrix

my book say that,

The trick to minimizing the entire sum is to minimize each of the products individually. Let’s look at the first product, m11x.We must decide which of xmin or xmax to substitute for x in order to minimize the product. Obviously, if m11 > 0, then the smaller of the two, xmin, will result in the smaller product. Conversely, if m11 < 0, then xmax gives a smaller product. Conveniently, whichever of xmin or xmax we use for computing x'min, we use the other value for computing x'max. We then apply this process for each of the nine elements in the matrix

It seems it will not hard to do in asm into my mind. I'll deep in" TGLZAABB", since I understand things a little better

[jdelauney]

I looked a little closer the structure of TGLZAxisAlignBoundingBox (boring longname but clear) and I simplified and put small notes in comments

TGLZAABB = record
  private
  public

    { : Create a starting BB with zero volume}
    procedure Create(Const AValue : TGLZVector);overload;
    { : Create a BB from two abitary points}
    procedure Create(Const P1, P2 : TGLZVector);overload;
    { : Create a BB from precomputed min max values}
    procedure CreateQ(Const AMin, AMax : TGLZVector);
    { : Create a BB from a Bounding Sphere. Need to keep ???? }
    procedure Create(const BSphere: TGLZBoundingSphere; Const InsideSphere:Boolean = False); overload;
    { : Create a BB from abitary Sphere definition }
    procedure CreateFromSphere(const Center: TGLZVector; Radius: Single; Const InsideSphere:Boolean = False); overload;

    // Transform the box and compute the new AABB --> or move to SceneObject
    //procedure SetFromTransformedAABB(const A: TGLZAABB const m : TGLZMatrix);

    class operator +(ConstRef A, B : TGLZAABB):TGLZAABB;overload;
    class operator +(ConstRef A: TGLZAABB; ConstRef B : TGLZVector):TGLZAABB;overload;
    //class operator *(ConstRef A: TGLZAABB; ConstRef B : TGLZVector):TGLZAABB;overload; IT IS Correct ????
    class operator =(ConstRef A, B : TGLZAABB):Boolean;overload;

  {: Virtually Add a point to the box.
       Expand the box as necessary to contain the point.  can be usefull in future }
    procedure AddPoint(P1:TGLZVector); 

   // We need keep this functions below ??????
   { : Converts the AABB to its canonical BB. }
    function ToBoundingBox: TGLZBoundingBox; overload;
    { : Transforms the AABB to a BB. }
    function ToBoundingBox(const M: TGLZMatrix) : TGLZBoundingBox; overload;
    { : Convert the AABB to a BSphere }
    function ToBoundingSphere: TGLZBoundingSphere; 

    { : Return true if the box contains a point }
    function Contains(P1: TGLZVector): boolean;
    { : Return the closest point on this box to another point }
    function ClosestPointTo(P1 : TGLZVector):TGLZVector;

    { : Return one of the eight corner points }
    function getCorner(Const Idx : Byte) : TGLZVector;

    { : Static AABB-plane intersection test
        Return if the box as being on one side or the other of a plane :
      < 0 Box is completely on the BACK side of the plane
      > 0 Box is completely on the FRONT side of the plane
      = 0 Box intersects the plane
    }
    function getOrientation(planeNormal : TGLZVector; + ?????) : Integer;

    { Those functions below need optionally return the AABB
      of their intersection if an intersection is detected ???? if yes an overload function ???? }

    { : Check if two AABB intersect, and return true if so. }
    function IntersectAABB(Const box : TGLZAABB): Boolean; overload; // var IntersetAABB : TGLZAABB):Boolean;

    { : Determines if two AxisAlignedBoundingBoxes intersect.
        The matrices are the ones that convert one point to the other's AABB system

        Need to keep or not ??????
    }
    function IntersectAABB(const B: TGLZAxisAlignedBoundingBox;const M1, M2: TGLZMatrix):Boolean;overload;

    { : Check if the AABB intersect with a Sphere, and return true if so. }
    function IntersectSphere(const Center: TGLZVector; Radius: Single):Boolean;  //+ Inside:Boolean ????

    { : Dynamic AABB-plane intersection test.
     How and what's the out result, surely not and "intersection aabb" ??????
    }
    function IntersectPlane(planeNormal , + ?????):Boolean;

    { : Finds the intersection between a ray and an axis aligned bounding box and return if intersect and optionaly the normal plane. }
    function RayCastIntersect(const RayOrigin, RayDirection: TGLZVector; out PlaneNormal: TGLZVector): Boolean; overload;

    //  Need to keep or not ??????
   // function RayCastIntersect(const RayOrigin, RayDirection: TGLZVector; out TNear, TFar: Single): Boolean; overload;
    //function RayCastIntersect(const RayOrigin, RayDirection: TGLZVector; IntersectPoint: PGLZVector = nil): Boolean; overload;

    Case Integer of
     0 : (Points : Array[0..1] of TGLZVector);
     1 : (MinV, MaxV :TGLZVector);
     2 : (MinX, MinY, MinZ, MinW: single;
          MaxX, MaxY, MaxZ, MaxW: single);

  end; 

[dicepd]

One comment on the above you can only Create a BB which Encloses a sphere, as a sphere can enclose an infinite possible BB.

[dicepd]

I have been tracking down some of the references in the code around this area, some of it is getting harder to find (websites no longer exist, articles moved etc). Should we start an external references documentation folder where we can store all of this for future reference, and if so, what would be the layout/ preferred format we would want to store? Example fast-extraction-viewing-frustum-planes-from-world-view-projection-matrix.pdf

[jdelauney]

One comment on the above you can only Create a BB which Encloses a sphere, as a sphere can enclose an infinite possible BB.

In my mind this option was "Const InsideSphere:Boolean" but i understand what you mean

Should we start an external references documentation folder where we can store all of this for future reference, and if so, what would be the layout/ preferred format we would want to store?

Yes we can, in named "DoscRef" folder ? In PDF and a Simple html or markdown for urls, and/or ref to the PDF file for easiest search. I can do a little Html page it will be easy to add some urls, i'll make something simple.