Quake's TraceLine
Author
I''m looking for method to trace a line between two points and be able to get what it hit based on an entity''s bounding box. Any ideas?
First, I am going to assume you know how to do a trace point through a BSP tree. This is not that hard to do.
The trick that Quake and many other games uses is a very common trick. For each different entity AAB box size, you create another version of the BSP tree. When building the tree, every face is moved out the distance specified by the face normal times the extent of the AABB. (The extent being half the width, height, and length).
What this does is make doing a collision test for a AABB as simple as doing a trace point.
Also, when building the BSP trees for the AABBs, Quake tries to round the edges off of the corners. This helps to remove the harse edges of the AABB. Makes movement much smoother to the player.
Tim
The trick that Quake and many other games uses is a very common trick. For each different entity AAB box size, you create another version of the BSP tree. When building the tree, every face is moved out the distance specified by the face normal times the extent of the AABB. (The extent being half the width, height, and length).
What this does is make doing a collision test for a AABB as simple as doing a trace point.
Also, when building the BSP trees for the AABBs, Quake tries to round the edges off of the corners. This helps to remove the harse edges of the AABB. Makes movement much smoother to the player.
Tim
Well, one easy way to do this (and I think this is the way it''s done in Quake, at least this is the way it''s done in the light util) is :
Compare the start and endpoint of the line to the root node of the BSP tree. If both points are on the same side, compare the line to the corresponding child node in the same way. If the line is split by the node, split the line in 2 parts, each one with a point on the node plane, and then compare both these lines to the correct child node. When you get to a leaf (Quake stores all polygons etc. in leafs), check to see if it''s a solid leaf. If it is, then you know that this line is obscured by that leaf.
To find out if the line has hit an entity, you could just compare the bbox of every entity in the current leaf to the line in the same way (I think, never done this myself, though)
Compare the start and endpoint of the line to the root node of the BSP tree. If both points are on the same side, compare the line to the corresponding child node in the same way. If the line is split by the node, split the line in 2 parts, each one with a point on the node plane, and then compare both these lines to the correct child node. When you get to a leaf (Quake stores all polygons etc. in leafs), check to see if it''s a solid leaf. If it is, then you know that this line is obscured by that leaf.
To find out if the line has hit an entity, you could just compare the bbox of every entity in the current leaf to the line in the same way (I think, never done this myself, though)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
