#### Archived

This topic is now archived and is closed to further replies.

# Quake's TraceLine

This topic is 6914 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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?

##### Share on other sites
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

##### Share on other sites
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)

• 9
• 10
• 13
• 57
• 11