simple python algorithm needed in finding bounding box of meshes from an OBJ file

Question

I'm trying a packing problem using Python and OBJ files. I'm a novice in python and not sure how to manipulate the OBJ file vertices to find the optimal bounding box. Any sample python code to get me started? Here's a simple box OBJ file to start with which I'll need to fit into a larger container. In short, can object X fit into object Y. Then ultimately how many x can fit into Y with the most optimal solution, but that's for way later.

Here's the .OBJ files for the small and bigger boxes Small:

# Rhino

v -5 -5 0 v -5 -5 5 v 0 -5 0 v 0 -5 5 vt 0 0 vt 0 1 vt 1 0 vt 1 1 vn 0 -1 0 vn 0 -1 0 vn 0 -1 0 vn 0 -1 0 f 4/4/4 2/2/2 1/1/1 3/3/3 v 0 -5 0 v 0 -5 5 v 0 0 0 v 0 0 5 vt 0 0 vt 0 1 vt 1 0 vt 1 1 vn 1 0 0 vn 1 0 0 vn 1 0 0 vn 1 0 0 f 8/8/8 6/6/6 5/5/5 7/7/7 v 0 0 0 v 0 0 5 v -5 0 0 v -5 0 5 vt 0 0 vt 0 1 vt 1 0 vt 1 1 vn 0 1 0 vn 0 1 0 vn 0 1 0 vn 0 1 0 f 12/12/12 10/10/10 9/9/9 11/11/11 v -5 0 0 v -5 0 5 v -5 -5 0 v -5 -5 5 vt 0 0 vt 0 1 vt 1 0 vt 1 1 vn -1 0 0 vn -1 0 0 vn -1 0 0 vn -1 0 0 f 16/16/16 14/14/14 13/13/13 15/15/15 v -5 -5 0 v 0 -5 0 v -5 0 0 v 0 0 0 vt 0 0 vt 0 1 vt 1 0 vt 1 1 vn 0 0 -1 vn 0 0 -1 vn 0 0 -1 vn 0 0 -1 f 20/20/20 18/18/18 17/17/17 19/19/19 v -5 -5 5 v -5 0 5 v 0 -5 5 v 0 0 5 vt 0 0 vt 0 1 vt 1 0 vt 1 1 vn 0 0 1 vn 0 0 1 vn 0 0 1 vn 0 0 1 f 24/24/24 22/22/22 21/21/21 23/23/23

Bigger box:

# Rhino

v 0 0 0 v 0 0 20 v 0 20 0 v 0 20 20 vt 0 0 vt 0 1 vt 1 0 vt 1 1 vn -1 -0 -0 vn -1 -0 -0 vn -1 -0 -0 vn -1 -0 -0 f 4/4/4 3/3/3 1/1/1 2/2/2 v 0 20 0 v 0 20 20 v 20 20 0 v 20 20 20 vt 0 0 vt 0 1 vt 1 0 vt 1 1 vn 0 1 0 vn 0 1 0 vn 0 1 0 vn 0 1 0 f 8/8/8 7/7/7 5/5/5 6/6/6 v 20 20 0 v 20 20 20 v 20 0 0 v 20 0 20 vt 0 0 vt 0 1 vt 1 0 vt 1 1 vn 1 0 0 vn 1 0 0 vn 1 0 0 vn 1 0 0 f 12/12/12 11/11/11 9/9/9 10/10/10 v 20 0 0 v 20 0 20 v 0 0 0 v 0 0 20 vt 0 0 vt 0 1 vt 1 0 vt 1 1 vn 0 -1 0 vn 0 -1 0 vn 0 -1 0 vn 0 -1 0 f 16/16/16 15/15/15 13/13/13 14/14/14 v 0 0 0 v 0 20 0 v 20 0 0 v 20 20 0 vt 0 0 vt 0 1 vt 1 0 vt 1 1 vn -0 -0 -1 vn -0 -0 -1 vn -0 -0 -1 vn -0 -0 -1 f 20/20/20 19/19/19 17/17/17 18/18/18 v 0 0 20 v 20 0 20 v 0 20 20 v 20 20 20 vt 0 0 vt 0 1 vt 1 0 vt 1 1 vn 0 0 1 vn 0 0 1 vn 0 0 1 vn 0 0 1 f 24/24/24 23/23/23 21/21/21 22/22/22

enter code here

Answer 1

You will want to iterate over the obj data looking for 'v's and checking if the following x y and z coordinates and recording the highest and lowest value each time you encounter it. The following code prints out the highest and lowest value for each dimension and then gives you the bounding box from that

obj = 'v -5 -5 0 v -5 -5 5 v 0 -5 0 v 0 -5 5 vt 0 0 vt 0 1 vt 1 0 vt 1 1 vn 0 -1 0 vn 0 -1 0 vn 0 -1 0 vn 0 -1 0 f 4/4/4 2/2/2 1/1/1 3/3/3 v 0 -5 0 v 0 -5 5 v 0 0 0 v 0 0 5 vt 0 0 vt 0 1 vt 1 0 vt 1 1 vn 1 0 0 vn 1 0 0 vn 1 0 0 vn 1 0 0 f 8/8/8 6/6/6 5/5/5 7/7/7 v 0 0 0 v 0 0 5 v -5 0 0 v -5 0 5 vt 0 0 vt 0 1 vt 1 0 vt 1 1 vn 0 1 0 vn 0 1 0 vn 0 1 0 vn 0 1 0 f 12/12/12 10/10/10 9/9/9 11/11/11 v -5 0 0 v -5 0 5 v -5 -5 0 v -5 -5 5 vt 0 0 vt 0 1 vt 1 0 vt 1 1 vn -1 0 0 vn -1 0 0 vn -1 0 0 vn -1 0 0 f 16/16/16 14/14/14 13/13/13 15/15/15 v -5 -5 0 v 0 -5 0 v -5 0 0 v 0 0 0 vt 0 0 vt 0 1 vt 1 0 vt 1 1 vn 0 0 -1 vn 0 0 -1 vn 0 0 -1 vn 0 0 -1 f 20/20/20 18/18/18 17/17/17 19/19/19 v -5 -5 5 v -5 0 5 v 0 -5 5 v 0 0 5 vt 0 0 vt 0 1 vt 1 0 vt 1 1 vn 0 0 1 vn 0 0 1 vn 0 0 1 vn 0 0 1 f 24/24/24 22/22/22 21/21/21 23/23/23'

elements = obj.split(' ')

x_min = 0.0
x_max = 0.0
y_min = 0.0
y_max = 0.0
z_min = 0.0
z_max = 0.0

i = 0

while i < len(elements):
    if elements[i] == 'v':
        #find min and max x value
        if float(elements[i + 1]) < x_min:
            x_min = float(elements[i + 1])
        elif float(elements[i + 1]) > x_max:
            x_max = float(elements[i + 1])

        #find min and max y value
        if float(elements[i + 2]) < y_min:
            y_min = float(elements[i + 2])
        elif float(elements[i + 2]) > y_max:
            y_max = float(elements[i + 2])

        #find min and max x value
        if float(elements[i + 3]) < z_min:
            z_min = float(elements[i + 3])
        elif float(elements[i + 3]) > z_max:
            z_max = float(elements[i + 3]) 

        #incriment the counter int by 4 as we know the next 4 elements are not a vertex
        i += 4

    else:
        i += 1

print 'x_min = ' + str(x_min)
print 'x_max = ' + str(x_max)   
print 'y_min = ' + str(y_min)
print 'y_max = ' + str(y_max)
print 'z_min = ' + str(z_min)
print 'z_max = ' + str(z_max)
print ''
print 'x_widh = ' + (str(x_max - x_min))
print 'y_widh = ' + (str(y_max - y_min))
print 'z_widh = ' + (str(z_max - z_min))

And heres the output i get

x_min = -5.0
x_max = 0.0
y_min = -5.0
y_max = 0.0
z_min = 0.0
z_max = 5.0

x_widh = 5.0
y_widh = 5.0
z_widh = 5.0

Hope that makes sense

Answer 2

First to answer the question in your title:

• Load each object file as a list of vertices, I assume you already hsve some code to load .obj files in python (if not, you could adjust this loadObj() function for example, make it return the verts variable)
• for each object, compute the bounding box, e.g.:

---

def verts_to_bbox(verts):
    xs = [v[0] for v in verts]
    ys = [v[1] for v in verts]
    zs = [v[2] for v in verts]
    return (min(xs), max(xs), min(ys), max(ys), min(zs), max(zs))

---

Now on to testing if one object 'fits' in the other. Basically, you want to know if one bounding box is equal or smaller than the other in all dimensions, as I understand you. So,

• Compute for each bounding box its size in x, y and z dimension, e.g.:

---

def bbox_size(bbox):
    # return tuple with sizes (dx, dy, dz)
    return (bbox[1] - bbox[0], bbox[3] - bbox[2], bbox[5] - bbox[4])

def fits_bbox(bigbox, smallbox):
    bdx, bdy, bdz = bbox_size(bigbox)
    sdx, sdy, sdz = bbox_size(smallbox)
    # return True if small box fits in bigbox in all three dimensions
    return (sdx<bdx and sdy<bdy and sdz<bdz)

---

Good luck!