Inside: SereneScreen Fan Forum - View Single Post

flipper · 10-27-2009, 11:55 AM

Originally posted by Jim Sachs:

That's pretty much exactly the scheme I've always used for tank boundaries, and it worked great for previous versions. The problem with MA3 is determining what's "inside" or "outside" of objects in a very complex 3D environment. The fish will be able to peck at the coral, which means they need to know exactly where the boundary of the object is.

As I look around my desk, I see a similar situation - a mouse, keyboard, speakers, stacks of papers, a desk lamp. I can reach out and touch the lamp shade, and I can see when my finger is about to make contact, but I wouldn't have any idea how to write an algorithm to do that.

Instead of a heightmap, I use small bounding boxes by subdividing each non-fish object into a 3D grid along each world axis. Think of a bunch a sugar cubes stacked and arranged to encompass your model's interior. You can also combine boxes that are "next" to each other as long as the result is still a box. You can generate these at runtime, using each non-fish model's vertex data, or you can pre-calc and store them ala your heightmap, or you can use your modeller to create a separate "collision" mesh for each non-fish model, load that model into system memory, and then use that vertex and face data. Just remember to keep the vertices aligned so that they form "axis aligned bounding boxes." (I'm sure you've seen that term before.)

Then, for the "close enough to influence" objects, iterate through each of that object's sub-boxes, and find the distance between the fish's world geometric center point and that box's closest surface, edge, or corner, using a "point to box" routine.

The "point to box" routine is pretty straight-forward. It compares the point against the box's min and max boundaries for each world axis, developing a bit mask that represents which of the possible 27 sub-cubes the point is in with respect to the box's interior region.

To generate the bitmask, start it out as 0, which represents the box's interior sub-cube. If the fish's x value is less than the box's min x value, add 1 to the bitmask. If the fish's x value is greater than the box's max x value, add 2 to the bitmask. Use 4 and 8 for the y axis and 16 and 32 for the z axis. This gives you the 27 possible values of 0, 1, 2, 4, 5, 6, 8, 9, 10, 16, 17, 18, 20, 21, 22, 24, 25, 26, 32, 33, 34, 36, 37, 38, 40, 41, and 42 for the bitmask. If you work through an example in 2D you should see how the numbering scheme works.

Then work out what's closer for each given sub-cube that the fish may be in. It will either be a box corner, edge, or side, or the fish is within the box, in which case you can consider the "point to box" distance to be 0.

There are 8 corners, 12 edges, and 6 sides to consider. For bitmasks 21, 22, 25, 26, 37, 38, 41, and 42, the corners are closest. For example, bitmask 21 represents a point that is left, below, and in front of the box. For bitmasks 5, 6, 9, 10, 17, 18, 20, 24, 33, 34, 36, and 40, the edges are closest. For example, bitmask 5 represents a point that is left and below the box but within its front/back boundary. For the other bitmasks (besides 0), the sides are closest. For example, bitmask 1 represents a point that is left of the box but within its up/down and front/back boundaries. (I used lefthandedness-speak here.)

So all that's left is to do a 3D "point to point" calculation using the fish's position and the box's closest point as specified by the bitmask. For closest corner calculations, the box's closest corner is the box's closest point. For closest edge calculations, you get the box's closest point by using its 2 axis values for the axes that don't "bound" the fish, along with the fish's axis value for the axis that does "bound" the fish. And for closest side calculations, you get the box's closest point by using its 2 axis values for the axes that do "bound" the fish, along with the fish's axis value for the axis that doesn't "bound" the fish.

Does that make enough sense to give it a try? If not I'm sure there's code on the web that uses the same idea. Or I'll post the code I use if you want.

10-27-2009, 11:55 AM	#36
flipper Registered Join Date: Mar 2002 Location: Texas Posts: 60	Originally posted by Jim Sachs: That's pretty much exactly the scheme I've always used for tank boundaries, and it worked great for previous versions. The problem with MA3 is determining what's "inside" or "outside" of objects in a very complex 3D environment. The fish will be able to peck at the coral, which means they need to know exactly where the boundary of the object is. As I look around my desk, I see a similar situation - a mouse, keyboard, speakers, stacks of papers, a desk lamp. I can reach out and touch the lamp shade, and I can see when my finger is about to make contact, but I wouldn't have any idea how to write an algorithm to do that. Instead of a heightmap, I use small bounding boxes by subdividing each non-fish object into a 3D grid along each world axis. Think of a bunch a sugar cubes stacked and arranged to encompass your model's interior. You can also combine boxes that are "next" to each other as long as the result is still a box. You can generate these at runtime, using each non-fish model's vertex data, or you can pre-calc and store them ala your heightmap, or you can use your modeller to create a separate "collision" mesh for each non-fish model, load that model into system memory, and then use that vertex and face data. Just remember to keep the vertices aligned so that they form "axis aligned bounding boxes." (I'm sure you've seen that term before.) Then, for the "close enough to influence" objects, iterate through each of that object's sub-boxes, and find the distance between the fish's world geometric center point and that box's closest surface, edge, or corner, using a "point to box" routine. The "point to box" routine is pretty straight-forward. It compares the point against the box's min and max boundaries for each world axis, developing a bit mask that represents which of the possible 27 sub-cubes the point is in with respect to the box's interior region. To generate the bitmask, start it out as 0, which represents the box's interior sub-cube. If the fish's x value is less than the box's min x value, add 1 to the bitmask. If the fish's x value is greater than the box's max x value, add 2 to the bitmask. Use 4 and 8 for the y axis and 16 and 32 for the z axis. This gives you the 27 possible values of 0, 1, 2, 4, 5, 6, 8, 9, 10, 16, 17, 18, 20, 21, 22, 24, 25, 26, 32, 33, 34, 36, 37, 38, 40, 41, and 42 for the bitmask. If you work through an example in 2D you should see how the numbering scheme works. Then work out what's closer for each given sub-cube that the fish may be in. It will either be a box corner, edge, or side, or the fish is within the box, in which case you can consider the "point to box" distance to be 0. There are 8 corners, 12 edges, and 6 sides to consider. For bitmasks 21, 22, 25, 26, 37, 38, 41, and 42, the corners are closest. For example, bitmask 21 represents a point that is left, below, and in front of the box. For bitmasks 5, 6, 9, 10, 17, 18, 20, 24, 33, 34, 36, and 40, the edges are closest. For example, bitmask 5 represents a point that is left and below the box but within its front/back boundary. For the other bitmasks (besides 0), the sides are closest. For example, bitmask 1 represents a point that is left of the box but within its up/down and front/back boundaries. (I used lefthandedness-speak here.) So all that's left is to do a 3D "point to point" calculation using the fish's position and the box's closest point as specified by the bitmask. For closest corner calculations, the box's closest corner is the box's closest point. For closest edge calculations, you get the box's closest point by using its 2 axis values for the axes that don't "bound" the fish, along with the fish's axis value for the axis that does "bound" the fish. And for closest side calculations, you get the box's closest point by using its 2 axis values for the axes that do "bound" the fish, along with the fish's axis value for the axis that doesn't "bound" the fish. Does that make enough sense to give it a try? If not I'm sure there's code on the web that uses the same idea. Or I'll post the code I use if you want.