[Closed] Smallest volume box to fit a shape?

Hi focomoso, thanks for your interest. On monday I will get some images together to give a better idea of what I’m up to. The solution you mentioned could be viable, if you can show me how it works. It would mean reworking some of what I have already done, but I’m resigned to that anyway.

Okay, here is one of the vertebrae (C6) with the planar sections set up. My goal here is to be able to create an optimal quadrangle for each of these which can then be used for purposes of skin wrapping. Then, I can adjust the shapes of each of the quadrangles to more closely match the shape of a different sample C6 vertebra. From there, I will be able to use the new shape as a morph target for the original and show the differences.

I’m swamped right now. If no one comes up with an answer by tomorrow, I should be able to take a look at it then…

Does this help?
http://valis.cs.uiuc.edu/~sariel/papers/98/bbox.html

Cannot find a 2d version of it right now, but google for “minimum area boundign rectangle” and “rotating calipers”.

Well, for all practical purposes there is no difference between a rectangle and a box with a height of zero.

At any rate, I’m not familiar with C programming beyond a “learn in 24 hours” level, but from what I understand from reading the descriptions, they are still talking about a cuboid bounding box.

I’ve taken a look at the rotating calipers, and it does seem to be at the very least a useful starting place.

I tried to write a script to find a coordsys matrix based on a polygon’s face normal and its diameter (furthest distance between 2 points), but I’m having trouble getting it to work. Any suggestions?

Update: Never mind, got it working. What’s my next step?

   global pointA, pointB
theDist = 0

-- Function courtesy of Martijn van Herk
fn AlignPivotTo Obj Tgt =
(
	-- Get matrix from object
	if classOf Tgt != matrix3 then Tgt = Tgt.transform
	
	-- Store child transforms
	local ChldTFs = in coordSys Tgt (for c in Obj.children collect c.transform)
	
	-- Current offset transform matrix
	local TF_Scale = scaleMatrix Obj.objectOffsetScale
	local TF_Rot = Obj.objectOffsetRot as matrix3
	local TF_Pos = transMatrix Obj.objectOffsetPos
	local TF_Offset = TF_Scale * TF_Rot * TF_Pos
	
	-- New offset transform matrix
	TF_Offset *= obj.transform * inverse Tgt
	
	-- Apply matrix
	Obj.transform = Tgt
	
	-- Restore offsets
	Obj.objectOffsetPos = TF_Offset.translation
	Obj.objectOffsetRot = TF_Offset.rotation
	Obj.objectOffsetScale = TF_Offset.scale
	
	-- Restore child transforms
	for i = 1 to Obj.children.count do Obj.children[i].transform = ChldTFs[i] * inverse Tgt * Obj.transform
) -- end function

--find the diameter of the polygon
for i = 1 to $.numVerts do
(
	for j = 1 to $.numVerts where j != i do
	(
		a = polyOp.getVert $ i
		b = polyOp.getVert $ j
		d = distance a b
		
		if d > theDist do
		(
			pointA = a; pointB = b; theDist = d
		)
	) -- end j loop
) -- end i loop

faceNormal	= polyOp.getFaceNormal $ 1 -- "1" is the only face in a single polygon editable poly
dVector			= normalize (pointA - pointB)
crossVector	= normalize (cross dVector faceNormal)

theMatrix = matrix3 crossVector dVector faceNormal ((pointA + pointB) / 2)
alignPivotTo $ theMatrix

This code can’t work. “bPoint” and “aPoint” are undefined. OK. They’re defined now. By the way, what is a practical value of this code in your case? I can align an object’s pivot to any face (or poly) easy but what is the use?

Well, I’m still kind of feeling my way around, but continuing from the end of the previous code, I’ve added on a bit. Now I have the orientation of the face, a 2D bounding box to use as a starting point, and the area of said bounding box.

I will probably not end up using what I’ve written in the final script, but it’s helping me to understand a bit of what’s involved in approaching the problem. If you can already see a solution for what I need, please feel free to share

xMin = 0; xMax = 0
yMin = 0; yMax = 0

for i = 1 to $.numVerts do
(
	thePos = (in coordSys theMatrix polyOp.getVert $ i)
	
	if thePos.x < xMin do xMin = thePos.x; if thePos.x > xMax do xMax = thePos.x
	if thePos.y < yMin do yMin = thePos.y; if thePos.y > yMax do yMax = thePos.y
)

thePlane = plane()
convertToPoly thePlane

--set the four points to determine the bounding box
in coordSys theMatrix
(
	polyOp.setVert thePlane 1 [xMin, yMin, 0]
	polyOp.setVert thePlane 2 [xMin, yMax, 0]
	polyOp.setVert thePlane 3 [xMax, yMin, 0]
	polyOp.setVert thePlane 4 [xMax, yMax, 0]
)
alignPivotTo thePlane theMatrix

As I said it’s not a big deal to make 2D optimal bbox. Check my post:
http://forums.cgsociety.org/showthread.php?f=98&t=791163

But you need not rectanguler optimal … (:shrug: ) volume. That is not easy.

Okay, my next step is going to involve getting rid of any concave points in the polygon. My idea for this is to test the area of the polygon, and then try removing each of the points. Each time it checks to see if this increases or decreases the polygon’s area. If it increases it, the change to the shape is kept, otherwise it will need to undo the change. Unfortunately, I can’t seem to figure out how to make an “undo” work within a script.

Any thoughts?

EDIT: Forgot to include the script in question (note that it does not work… it calls the undo every single time whether it should be or not.)

theHull = copy $
 theHull.name = $.name + "_Hull"
 
 select theHull
 theArea = polyOp.getFaceArea $ 1
 newArea = theArea
 
 fn removeConcaveVerts =
 (
 	vertCount = $.numVerts
 
 	for i = vertCount to 1 by -1 do
 	(
 		polyOp.setVertSelection $ #{i}
 			
 		undo on
 		(
 			$.editablePoly.remove selLevel:#Vertex
 			newArea = polyOp.getFaceArea $ 1
 		) -- undo off	
 		
 		if newArea > theArea
 			then
 			(
 				format "keep changes
"
 				theArea = newArea
 			)
 			else
 			(
 				format "undo
"
 				max undo
 			)
 	)
 )
 
 removeConcaveVerts()