Box selection using Physics (Havok)

[KungFooMasta]

Hi all.

I'm working on my game project (which uses Ogre of course) and I was wondering if anybody has done Box selection (RTS style) using Havok and/or could share some information on how to do it.

The help docs mention "hkpShapeRayCast" in a few places, but I think this is misleading, according to the comments this "Finds the closest intersection between the shape and a ray defined in the shape's local space". What I wanted was something more like the PhysX Intersection Queries.

This is the scenario I'm aiming for:

User wants to select multiple units and uses the mouse to draw a box on the screen. When the Left Mouse button is released, I want to get a list of all shapes that intersect a cube-like area that represents the users selection area. (This cube-like area cannot be axis aligned as I am not using a strictly top-down view)

There is also mention of using the Havok Phantom classes, I will probably look into this more, but I'm hoping its something that will give me immediate results. For example, when casting a ray, the results get returned immediately. I'm hoping the Phantom route doesn't require creating a Phantom shape, stepping the physics world, retrieving results, and then deleting the phantom shape.

Many commercial games have used Havok for physics, like AOE III. Do games use physics for unit selection, or simply graphics, based on AABBs? (The latter option seems very innacurate, especially with a lot of units close together)

[jacmoe]

I think simple AABB queries will be good. It's more accurate than the player.
You are not strictly topdown, doesn't make AABBs less attractive. IMO.

[KungFooMasta]

The cube-like area cannot be axis aligned because then it can't match the camera's orientation. (the camera's view is not aligned to axis, so why should the selection area by aligned to axis?)

For now I guess we'll stick with the ogre volume bounded query. Still, if anybody has input, feel free to share.

[jacmoe]

Just because you're viewing something from an angle, doesn't make what you view any less axially aligned ?
(unless you're drunk )

[KungFooMasta]

I thought that for axis aligned boxes, the faces must be parallel to the xy plane, the xz plane, and the yz plane. If this is true, then the idea of projecting a box out of your viewport into 3d space won't likely be axis aligned. Is my definition of axis aligned wrong? I remember viewing the bounding boxes for meshes, and no matter which way you turn the ninja, his box faces are always parallel to the planes I previously mentioned. (for example you can rotate a plank of wood and the axis aligned box would transform from a rectangular cube to an equal sided cube. The faces never change orientation, they only grow/shrink to encapsulate the mesh)

[Fish]

(The latter option seems very innacurate, especially with a lot of units close together)

You are probably thinking of Tutorial 4 which shows how to perform volume selection at the AABB level. That technique can then coupled with ray casting to the polygon level to ensure that object is truly in the selection box.

-Fish

[Kojack]

Take a look at Havok's hkpWorld::getPenetrations() method. You give it a collidable object (such as a convex mesh build from the frustum of the user's rectangular selection on the screen) and it returns a collection of every physics body which intersects it.
They say if you want it to happen every update then a phantom shape (a trigger in PhysX terms) should be used instead, because it's faster. But for infrequent events like rectangular selection of units (and especially since the shape will change every time it's tested), it should be fine to use getPenetrations.

[betajaen]

Personally I wouldn't go with a phantom/trigger for box selections.

PhysX has a more efficient function "overlapOBBShapes" in NxScene, which performs an OBB (Orientated Bounding Box) test on the scene and gives an array of NxShapes that are wholly or partially inside the OBB.

I'm sure Havok has a similar function or two.

[Kojack]

I'm sure Havok has a similar function or two.

Yes, the one I just said: hkpWorld::getPenetrations()
It's a one shot overlap test using any physics shape you want.

[betajaen]

Whoops.

Oh, well Havok wins this round; PhysX only has Spheres, Boxes and Capsules for intersection testing.

[Akinz]

Hi guys,

I'm trying to implement this using a hkpConvexVerticesShape that should be shaped like the frustrum we are projecting via our selection rectangle. I'm a little new to creating shapes and 3d space confuses me, so I haven't been able to figure out how to create the right shape out of 8 vertices.

In order to check that my shape is correct, after I draw the selection rectangle I try to create the ConvexVerticesShape and drop it into the world. I have been able to get their example shape (a pyramid) to work using this code:

Code: Select all

			//do volumequery
			Ogre::Ray topLeft = camera->getCameraToViewportRay(mSides[LEFT], mSides[TOP]);
			Ogre::Ray topRight = camera->getCameraToViewportRay(mSides[RIGHT], mSides[TOP]);
			Ogre::Ray bottomLeft = camera->getCameraToViewportRay(mSides[LEFT], mSides[BOTTOM]);
			Ogre::Ray bottomRight = camera->getCameraToViewportRay(mSides[RIGHT], mSides[BOTTOM]);

			// Data specific to this shape.
			int numVertices = 4;

			// 16 = 4 (size of "each float group", 3 for x,y,z, 1 for padding) * 4 (size of float)
			int stride = sizeof(float) * 4;

			float vertices[] = { // 4 vertices plus padding
				-2.0f, 2.0f, 1.0f, 0.0f, // v0
				1.0f, 3.0f, 0.0f, 0.0f, // v1
				0.0f, 1.0f, 3.0f, 0.0f, // v2
				1.0f, 0.0f, 0.0f, 0.0f  // v3
			};

			/////////////////// SHAPE CONSTRUCTION ////////////////
			hkArray<hkVector4> planeEquations;
			hkGeometry geom;

			hkStridedVertices stridedVerts;
			{
				stridedVerts.m_numVertices = numVertices;
				stridedVerts.m_striding = stride;
				stridedVerts.m_vertices = vertices;
			}

			hkGeometryUtility::createConvexGeometry( stridedVerts, geom, planeEquations );

			{
				stridedVerts.m_numVertices = geom.m_vertices.getSize();
				stridedVerts.m_striding = sizeof(hkVector4);
				stridedVerts.m_vertices = &(geom.m_vertices[0](0));
			}

			hkpShape* shape = new hkpConvexVerticesShape(stridedVerts, planeEquations);

			// Create rigid body
			hkpRigidBodyCinfo rbInfo;
			rbInfo.m_shape = shape;
			hkpInertiaTensorComputer::setShapeVolumeMassProperties(shape, 100, rbInfo);
			rbInfo.m_motionType = hkpMotion::MOTION_DYNAMIC;
			rbInfo.m_qualityType = HK_COLLIDABLE_QUALITY_MOVING;
			rbInfo.m_collisionFilterInfo = hkpGroupFilter::calcFilterInfo(0);
			rbInfo.m_position.set(100, 100, 100);

			hkpRigidBody* rigidBody = new hkpRigidBody(rbInfo);
			shape->removeReference();

			// Add rigid body to world
			hkpWorld* world = mScene->_getHavokWorld();
			world->lock();
			world->addEntity(rigidBody);
			world->unlock();

This code works and I see a pyramid created and dropped at the top of the scene. However, when I try to change the number of vertices to 8, and use code something like this, it doesn't work:

Code: Select all

			int numVertices = 8;
			int stride = sizeof(float) * 8;
			float vertices[] = {
				topLeft.getOrigin().x, topLeft.getOrigin().y, topLeft.getOrigin().z, 0.0f,
				topLeft.getPoint(10).x, topLeft.getPoint(10).y, topLeft.getPoint(10).z, 0.0f,
				
				topRight.getPoint(10).x, topRight.getPoint(10).y, topRight.getPoint(10).z, 0.0f,
				topRight.getOrigin().x, topRight.getOrigin().y, topRight.getOrigin().z, 0.0f,
				
				bottomRight.getOrigin().x, bottomRight.getOrigin().y, bottomRight.getOrigin().z, 0.0f,
				bottomRight.getPoint(10).x, bottomRight.getPoint(10).y, bottomRight.getPoint(10).z, 0.0f,

				bottomLeft.getPoint(10).x, bottomLeft.getPoint(10).y, bottomLeft.getPoint(10).z, 0.0f,
				bottomLeft.getOrigin().x, bottomLeft.getOrigin().y, bottomLeft.getOrigin().z, 0.0f
			};

I'm pretty sure my intial problem is that the shape vertices are supposed to be in local space, I have tried changing the 8 coordinates to dummy numbers that make a 1x1x1 cube but when it goes to add the shape to the world I get an exceededMaxBounds exception. Anyone have an idea what I'm doing wrong? Or can provide a list of 8 vertices that they know works that I can try?

[Akinz]

Figured I'd update this thread with my progress, I had some whacky things going on with my code earlier, stemming from an incomplete understanding of 3d shape construction (my understanding is still incomplete but less so! ).

The first problem was that my stride size should still be 16 (sizeof(float) * 4). Second was that the Ogre::Camera::getCameraToViewportRay is supposed to be using normalized coordinates. And the final third problem was translating the coordinates to local space. Here's what my coords look like now:

Code: Select all

			//do volumequery with normalized coords (e.g. [0,1])
			Ogre::Ray topLeft = camera->getCameraToViewportRay(mSides[LEFT] / camera->getViewport()->getActualWidth(), mSides[TOP] / camera->getViewport()->getActualHeight());
			Ogre::Ray topRight = camera->getCameraToViewportRay(mSides[RIGHT] / camera->getViewport()->getActualWidth(), mSides[TOP] / camera->getViewport()->getActualHeight());
			Ogre::Ray bottomLeft = camera->getCameraToViewportRay(mSides[LEFT] / camera->getViewport()->getActualWidth(), mSides[BOTTOM] / camera->getViewport()->getActualHeight());
			Ogre::Ray bottomRight = camera->getCameraToViewportRay(mSides[RIGHT] / camera->getViewport()->getActualWidth(), mSides[BOTTOM] / camera->getViewport()->getActualHeight());

			float distanceFromCenterX = ((topRight.getOrigin().x - topLeft.getOrigin().x) / 2) + topLeft.getOrigin().x;
			float distanceFromCenterZ = ((bottomRight.getOrigin().z - topRight.getOrigin().z) /2) + bottomRight.getOrigin().z;
			float distanceFromCenterY = ((topLeft.getOrigin().y - topLeft.getPoint(projectionDistance).y) / 2) + topLeft.getPoint(projectionDistance).y;

            //
            // Create convex vertices shape
            //

            // Data specific to this shape.
			int numVertices = 8;

			// 16 = 4 (size of "each float group", 3 for x,y,z, 1 for padding) * 4 (size of float)
			int stride = sizeof(float) * 4;

			float vertices[] = {
				topLeft.getOrigin().x - distanceFromCenterX, topLeft.getOrigin().y - distanceFromCenterY, topLeft.getOrigin().z - distanceFromCenterZ, 0.0f,
				topRight.getOrigin().x - distanceFromCenterX, topRight.getOrigin().y - distanceFromCenterY, topRight.getOrigin().z - distanceFromCenterZ, 0.0f,
				bottomRight.getOrigin().x - distanceFromCenterX, bottomRight.getOrigin().y - distanceFromCenterY, bottomRight.getOrigin().z - distanceFromCenterZ, 0.0f,
				bottomLeft.getOrigin().x - distanceFromCenterX, bottomLeft.getOrigin().y - distanceFromCenterY, bottomLeft.getOrigin().z - distanceFromCenterZ, 0.0f,
				bottomLeft.getPoint(projectionDistance).x - distanceFromCenterX, bottomLeft.getPoint(projectionDistance).y - distanceFromCenterY, bottomLeft.getPoint(projectionDistance).z - distanceFromCenterZ, 0.0f,
				bottomRight.getPoint(projectionDistance).x - distanceFromCenterX, bottomRight.getPoint(projectionDistance).y - distanceFromCenterY, bottomRight.getPoint(projectionDistance).z - distanceFromCenterZ, 0.0f,
				topRight.getPoint(projectionDistance).x - distanceFromCenterX, topRight.getPoint(projectionDistance).y - distanceFromCenterY, topRight.getPoint(projectionDistance).z - distanceFromCenterZ, 0.0f,
				topLeft.getPoint(projectionDistance).x - distanceFromCenterX, topLeft.getPoint(projectionDistance).y - distanceFromCenterY, topLeft.getPoint(projectionDistance).z - distanceFromCenterZ, 0.0f
			};

Hopefully this helps any other people trying to use Havok for their group selection!