Generating a heightmap 2004-02-24 - By Ian Thomas
Back
Hi guys,
I've been wrestling with this one for a while, and wondered if anyone
had any inspiration.
The setup: I've got a finite plane (the 'floor') of 240x240 at y=0,
scattered around which may be an arbitrary number of solids (the
contents of the room). The solids are just #box primitives, scaled,
rotated and translated but still essentially boxes.
I've divided the room into tiles of 12x12 for pathfinding purposes.
Basically I need to establish what the highest point is within in each
tile. (Note this may not be a vertex, as objects could cheerfully span
tiles without having a vertex within a tile.)
The routine I'm building is for precalcing the heightmap, so doesn't
need to be blistering - however, I'd like it to be pretty fast as my
room editing utility needs to rebuild on a regular basis. :)
Approaches I've tried:
Brute force:
-- ---- ----
- Apply a meshdeform to each object.
- For each tile:
- Discard objects whose bounding sphere is nowhere near.
- For each valid object, use Sutherland-Hodgeman clipping on each
face. If any of the face is inside, use the clipped vertices and take
the max height.
This seems to work very well, but is exceedingly slow; add to that I get
occasional anomalies and wonder if my S-H clipping implementation has
holes in (if anyone can point me at a good bit of sourcecode in whatever
language then I'd appreciate it).
Collision:
-- ---- --
- Turn on collision detection for the relevant objects
- For each tile:
- Move a tile-shaped solid upwards from y=0 upwards until it stops
colliding. That's the max height.
This works okay, is slow, requires updatestages and sleeps to make the
collision callback work, and the collision doesn't seem to be 100%
accurate.
Raycasting:
-- ---- ---
- For each tile
- Cast a network of angled rays downwards towards the floor (within
the volume of the tile) - the heighest point hit by a ray is the max
height for the tile.
This lacks precision - sometimes very thin blocks escape the net. :( To
catch those, you need more rays. The more rays, the slower it is.
Things I thought of but haven't tried:
Additive:
-- ------
- Reverse the process, and actually build the heightmap as I build the
map - for each object, work out which tiles it lies in and set heights
appropriately.
To be honest, I gave up on the maths for this in favour of trying the
other things. It sounds plausible but I still need to do lots of
clipping. :(
Any blindingly obvious solutions that I've missed? If not, I think next
step is to look at the additive solution using Sutherland-Hodgeman
*sigh* but it ain't pretty. :)
TIA,
Ian
__ ____ ____ ____ ____ ____ ____ ____ ____ ____
Dir3d-l mailing list
Dir3d-l@(protected)
http://nuttybar.drama.uga.edu/mailman/listinfo/dir3d-l
|
|
