3d wall techniques
Blitzen
I've been working on a Direct3D first-person walk-around game with a team
for quite a while now, and we have come up with many wild schemes by which
to represent the walls/floors/ceilings/barriers of our world for collision
detection; we've been able to draw them fine, but each seems to become too
complicated or limiting in the long-run. I suppose the simplest thing to
do, with also the most flexibility, is to have an unlimited number of
arbitrary-sized rectangles, arbitrarily- rotated, and loop through all of
them (probably also dividing map into sectors, each with its own set of
walls) and test somehow if we've crossed it, like DOOM.
So my question is, what would be the best scheme for an
application like ours, which has many outdoor scenarious with hills,
trees and other semi-curved surfaces where you need more freedom
than merely flat walls, floors and ceilings? How do other games
like Tribes, Half-Life and other out-doorsy games with high poly
counts represent the world for collision detection? Is it pretty-
much what I mentioned, and if so, how did they represent it in
code, ie. an array of RECT structs, each with 4 D3DVERTEX, 3
rotation scalars, maybe an int to index its texture, etc. or
something like that?
Personal stories appreciated too.
--
Blitzen
Vince 15
tell me something more?
Thanks
Vince 15
Blitzen
Here are the basic systems we've designed and gotten to work to a point so
far, all of which involve dividing the map into separate sectors so each
player/monster only has to check those dividers within his own sector and
not the whole map:
-Heightmap system: each (hexahedronal) sector contains up to 6 walls which
make up a side. This wall has a flag to either exist or not, and if so,
it's a heightmap of yay high and yay long, say typically 10x15 heightmap
points or so. This allows for the walls and floors to be rather liberally
shaped into valleys and hills up to halfway across the sector (the player
is tested, for instance, for bottom-floor collision if he's lower than
half of the height of the sector). A -1 value for the height of a
vertex means that square is a hole in the wall (so it's a good
idea to have another sector on the other side to go to). However, for
anything else in the middle of the sector, we had to define separate model
types to create such things as trees and buildings.
-Arbitrary heightmap system: This has heightmaps like the first one, but
you can place as many heightmaps as you want in the map, and at any
position, and any size (spaces between heightmap points remain the same,
just more are added). Each has an orientation as to whether it is facing
left, up, front, etc., so you can re-create the 1st system with this one,
plus do some nifty things like make a big cylinder with 2 opposing
heightmaps that get high in the middle, from top to bottom, and low on the
ends, making a tree-trunk or silo or something. a box-shaped buildling can
be constructed with 5 small, flat heightmaps. We had planned also for the
ability to mark a heightmap as a water surface, so that in the game it
would cycle through its vertices and bob them around to look like
ripples/waves in the water, but we didn't get that far before pooping out
from the complexity.
-cosine-patch system: In this bizarre system cooked up by another team
member, each wall (which is arbitrarily positioned, sized, and oriented
like the last system) is a complicated heightmap but is generated by only
a few "control" vertices. The engine then takes these vertices and creates
a contour of very nicely rounded hills to fit them, in the first of 2
modes. In the 2nd mode, the shape of the surface is defined by several
samplings of a cosine wave traversing along the length of it, whose
amplitude is controllable as well. One can shrink the patch down to
half-size, so that only the "positive" half of the wave is showing, and
then put 4 of these around in a circle to create a cylinder like last
time. You can imagine how far this one got.
-So finally, now that you understand the cycle we've been going
through for a year and a half, I now desire to create the simplest system
possible and just accept it. I'd like to model after a system
similar to doom/quake, and just test if we've crossed a boundary line. I'd
like to have a system of nothing but free rectangles or triangles, and
just loop through all of them in the sector. This would not only be
simplest for D3D and the collision detector, but also allow the most
flexibility in designing the map. Most of the previous systems were
designed to save time for the map creator using the map editor, but
there's no need to have the engine worrying about all these complicated
schemes. One trick might be to hack our previous map editors to save in
this simple poly format after creating in their quicker heightmap or patch
schemes. The only difference between what this game needs to do and
doom/quake is that it's outdoors and involves a hilly landscape with more
polys to a floor/wall. Doom and Quake have largely flat, rectangular
floors, walls and ceilings.
But does anybody know what files in the quake source deal with collision
detection, or have pseudo-code suggestions as to how to implement this? I
suppose each sector would have an array of triangles or rectangles, each
of which would have its size, position, and rotations along each axis.
There might be other tricks to add for speed optimization like which half
of the sector it's on so it can be passed over if the character in
question is on the other side of the sector.
Anyway, hope that answers your question. You interested in joining? =o)
--
Blitzen