17 Aug, 2019

Bounding Geometry With EKL: Box and Rectangle

In my previous post, I showed how to create a convex hull around a set of points or a polygon. Today’s post will focus on creating a bounding box and a bounding rectangle, depending on the input.

Determining the boundary of an object will be guided by 3 directions: X, Y, and Z.

In today’s example I’ll use object’s inertia directions. Alternatively, we can ask the user to pass an Axis-System as an input and extract directions from it– take a look at this post for how to extract data from an Axis System.

Directions will be used to obtain points at the extremities of the given object. We’ll CATIA’s extremum function which takes three sets of arguments–each comprising a direction and a boolean value to determine the extremity–maximum [true] or minimum [false]. Note that directions order matters. The function will use the first direction to travel along curve (whether max or min), then travels along the second, then travels along the third. The last travel location is the extremum point. Hence, the shape on which the point travel has an impact on the computation. For example, the point might reach the end of the shape before it exhausts all 3 directions. Thus, we’ll generate all possible extremity points by using all permutations, which are 24. Here is how we compute the number of combinations:

  • We can pass 3 orders: x, y, z; y, z, x; and z, x, y.
  • Each direction can take a true or false value.

The number of permutations is 2^3 x 3, that is 2 to the power of 3 multiplied by 3 (2 x 2 x 2 x 3), which is 24.

Here is an enumeration of all values:

Combination Ordering Value 1 Value 2 Value 3
Group 1
1 X-Y-Z true true true
2 X-Y-Z true true false
3 X-Y-Z true false false
4 X-Y-Z false false false
5 X-Y-Z false false true
6 X-Y-Z false true false
7 X-Y-Z true false true
8 X-Y-Z false true true
Group 2
1 Y-Z-X true true true
2 Y-Z-X true true false
3 Y-Z-X true false false
4 Y-Z-X false false false
5 Y-Z-X false false true
6 Y-Z-X false true false
7 Y-Z-X true false true
8 Y-Z-X false true true
Group 3
1 Z-X-Y true true true
2 Z-X-Y true true false
3 Z-X-Y true false false
4 Z-X-Y false false false
5 Z-X-Y false false true
6 Z-X-Y false true false
7 Z-X-Y true false true
8 Z-X-Y false true true

Pseudo Code

The algorithm to find the box goes like this:

1 Get inertia lines to generation corresponding directions and planes: xy, yz, zx.
2 Get extremum points
3 Project points inertia planes and generate 3 sets
4 Sort the 3 point-sets using x, y, and z coordinates
5 Get min and max points and generate offset min and max planes at points (xyMin, xyMax, yzMin, yzMax, zxMin, zxMax)
6 Intersect the planes to get lines using zy, and zx min and max planes. 
7 Intersect lines with one of the xyMin or xyMax planes to get points.
7 Generate box (surface) or rectangle depending on distance between xyMin and xyMax

Let’s how it works:

Code

Here is the code.

/* Action created by melkhaldi 8/17/2019 */

//get the owner of the object and create a geoset inside
let geoset(OpenBodyFeature)
geoset = new ("OpenBodyFeature", "Boundary Data", geoObject.Owner)

//get the inertia axis line
let xLine, yLine, zLine(Line)
xLine = inertiaAxis(1, geoObject)
yLine = inertiaAxis(2, geoObject)
zLine = inertiaAxis(3, geoObject)

//using the lines, we get directions
let dirX, dirY, dirZ(Direction)
dirX = direction(xLine)
dirY = direction(yLine)
dirZ = direction(zLine)

//lets build planes using those lines as well.
let xy, yz, zx(Plane)
xy = plane(xLine, yLine)
yz = plane(yLine, zLine)
zx = plane(zLine, xLine)

//lets build an axis system to visualize the inertia axes
let cog(Point)
cog = centerofgravity(geoObject)

//represent the axis system (this is only for visualization purposes). we won't use it in the script.
let iAxis(AxisSystem)
iAxis = new ("AxisSystem", "iAxis", geoset)
iAxis = axisSystem(cog, dirX, dirY, dirZ)

//all permutations for 3 variables of two values (true false) is 2 to the power of 3, which is 8. We have three groups, so 8*3 is 24.
//here are all combinations.
let extremumPoints(List) 
//x y z combinations
extremumPoints.Append( extremum(geoObject, dirX, true, dirY, true, dirZ, true)) //1
extremumPoints.Append( extremum(geoObject, dirX, true, dirY, true, dirZ, false)) //2
extremumPoints.Append( extremum(geoObject, dirX, true, dirY, false,dirZ, false)) //3
extremumPoints.Append( extremum(geoObject, dirX, false, dirY, false,dirZ, false)) //4
extremumPoints.Append( extremum(geoObject, dirX, false, dirY, false,dirZ, true)) //5
extremumPoints.Append( extremum(geoObject, dirX, false, dirY, true, dirZ, false)) //6
extremumPoints.Append( extremum(geoObject, dirX, true, dirY, false, dirZ, true)) //7
extremumPoints.Append( extremum(geoObject, dirX, false, dirY, true, dirZ, true)) //8

//y z x combinations
extremumPoints.Append( extremum(geoObject, dirY, true, dirZ, true, dirX, true)) //1
extremumPoints.Append( extremum(geoObject, dirY, true, dirZ, true, dirX, false)) //2
extremumPoints.Append( extremum(geoObject, dirY, true, dirZ, false , dirX, false)) //3
extremumPoints.Append( extremum(geoObject, dirY, false,dirZ, false, dirX, false)) //4
extremumPoints.Append( extremum(geoObject, dirY, false, dirZ, false, dirX, true)) //5
extremumPoints.Append( extremum(geoObject, dirY, false, dirZ, true, dirX, false)) //6
extremumPoints.Append( extremum(geoObject, dirY, true, dirZ, false, dirX, true)) //7
extremumPoints.Append( extremum(geoObject, dirY, false, dirZ, true, dirX,true)) //8

//z x y combinations
extremumPoints.Append( extremum(geoObject, dirZ, true,  dirX, true, dirY, true)) //1
extremumPoints.Append( extremum(geoObject, dirZ, true,  dirX, true, dirY,false)) //2
extremumPoints.Append( extremum(geoObject, dirZ, true, dirX, false, dirY,false)) //3
extremumPoints.Append( extremum(geoObject, dirZ, false, dirX, false, dirY,false)) //4
extremumPoints.Append( extremum(geoObject, dirZ, false, dirX, false,dirY,true)) //5
extremumPoints.Append( extremum(geoObject, dirZ, false, dirX, true, dirY,false)) //6
extremumPoints.Append( extremum(geoObject, dirZ, true, dirX, false, dirY,true)) //7
extremumPoints.Append( extremum(geoObject, dirZ, false, dirX, true, dirY, true)) //8

//project the extremum points on each of the planes
let xProjections, yProjections, zProjections(List)
let extrmPoint(Point)
let projX, projY, projZ(Point)
//here we will project each extremum point twice to get it on an axis.
for extrmPoint inside extremumPoints {
    projX=  project(project(extrmPoint, xy), zx):Point //from xy to zx
    projY=  project(project(extrmPoint, xy), yz):Point //from xy to yz
    projZ=  project(project(extrmPoint, zx), yz):Point //from zx to yz

    xProjections.Append(  projX)
    yProjections.Append(  projY)
    zProjections.Append(  projZ)
}

//lets sort the points now to get the min and max
let sortedX, sortedY, sortedZ(List)
//first sort in x
sortedX = xProjections.Sort("<" , "Point", "Length", "y=x.coord(1)")
//first sort in y 
sortedY = yProjections.Sort("<" , "Point", "Length", "y=x.coord(2)")
//first sort in z 
sortedZ = zProjections.Sort("<" , "Point", "Length", "y=x.coord(3)")

//get min and max
let xMax, xMin, yMax, yMin, zMax, zMin(Point)

//you can uncomment the code below if you want to add points to the tree
xMax =sortedX.GetItem(sortedX.Size())
xMin =sortedX.GetItem(1)

yMax =sortedY.GetItem(sortedY.Size())
yMin =sortedY.GetItem(1)

zMax =sortedZ.GetItem(sortedZ.Size())
zMin = sortedZ.GetItem(1)

//
//set the bounding planes
let yzMaxPlane, yzMinPlane, zxMaxPlane, zxMinPlane, xyMaxPlane, xyMinPlane(Plane)

//you can uncomment the beloe to add planes to the tree
yzMaxPlane = planeoffset(yz, xMax)
yzMinPlane = planeoffset(yz, xMin)
zxMaxPlane = planeoffset(zx, yMax)
zxMinPlane = planeoffset(zx, yMin)
xyMaxPlane = planeoffset(xy, zMax)
xyMinPlane = planeoffset(xy, zMin)

//now lets intersect y
//let's declare some variables

let t1,t2,t3,t4(Point)
let v1, v2, v3,v4(Line)

//get the vertical lines of planes intersections
v1 = intersect(yzMaxPlane, zxMaxPlane):Line
v2 = intersect(zxMaxPlane, yzMinPlane):Line
v3 = intersect(yzMinPlane, zxMinPlane):Line
v4 = intersect( zxMinPlane, yzMaxPlane):Line

//get rectangle points by intersecting lines with any zPlane
//here, we'll use z min
t1 = intersect( v1, xyMinPlane):Point
t2 = intersect( v2, xyMinPlane):Point
t3 = intersect( v3, xyMinPlane):Point
t4 = intersect( v4, xyMinPlane):Point

//generate lines going through the 4 points
let a, b, c, d(Line)
a = line(t1, t2)
b = line(t2, t3)
c = line(t3, t4)
d = line(t4, t1)

//get the difference between z plane to determine whether a 
//box or rectangle should be created
let zPlaneDiff(Length)
zPlaneDiff = distance( xyMinPlane, xyMaxPlane)

let boundingRectangle(Curve)

if( zPlaneDiff==0mm){
    //make a rectangle and add it to the tree
    boundingRectangle = new ("Curve", "Bounding Rectangle", geoset) 
    boundingRectangle = assemble( List(a, b, c, d)) 
    boundingRectangle.Update()
}
else{
    //box case
    let box(Surface)
    boundingRectangle = assemble( List(a, b, c, d))
    //make a fill surface
    let fillSrf(Surface)
    fillSrf = fill(boundingRectangle)

    //make a box and add it to tree
    box = new ("Surface", "Bounding Box For " + geoObject.Name , geoset)
    box =   extrude(fillSrf , dirZ, 0mm, zPlaneDiff, true)
    box.Transparency=20
    box.Update()
}

Note that the input can be changed to Curve or a Surface. The same code will work for both:

Notes

  • 1 Rohan Keswani just pointed out that I’d only need to generate 6 extremum points: combinations 1 and 4 from each group in the above table, because the rest will be redundent. I marked the combination numbers in the code. So anything other than 1 and 4 can be commented out–I’ll just leave it there for reference. Make sure to check out Rohan’s bounding box post.

  • 2 I tested the above code with user-defined axis system as input, it did not always work correctly. I’ll revise it and post an update.

Tags: , ,

About : Maher Elkhaldi

Maher Elkhaldi is a senior applications engineer at Tesla Motors. He founded the 3DXAutomation blog to help make knowledge of programming CATIA easier to find, and contribute to the open-source community.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.