Tell me more ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 2 down vote favorite

I'm implementing non-projective decals. As described in many places (ie: lengyel in the gpg2) I first need to detect all triangles that lie within some sort of frustum.

Besides obvious brute-force solutions (ie: checking each triangle), what are better ways to generally search triangles in a mesh? One solution i can think of is, for each mesh, keep some parallel data structure better suited for searching. are there any well know algo/solutions?

share|improve this question

2 Answers

up vote 0 down vote accepted

I agree that frustum culling type algorithms are the way to go. Although, I would just use an Octree or KD-Tree, and hierarchically test for an intersection using that. Unless you expect high depth complexity and a poor rendering order, I would skip a technique that does occlusion computation to save development time. It is possible to use multiple Oct/KD-tree hierarchies to support complex animated objects, or dynamic Oct/KD-trees of simple objects to prevent testing against each moving object.

share|improve this answer
Some kind of space partitioning is quite surely the right thing. I'm just trying to understand which is the best tool for this. – user8884 Jul 28 '11 at 6:17
I for sure need to traverse complex meshes, checking each traingle, many times per frame. So, you are right about being carefull not to waste development time, but i think I should at least consider it. – user8884 Jul 28 '11 at 6:25
I suppose a bounding volume hierarchy (BVH), where each node fully contains all triangles therein (therefore nodes potentially overlap) is what you need: it will save you from having to check every triangle. If a node is entirely in or out the frustum, all it's triangles are in or out respectively. If it overlaps the border of a frustum, you subdivide and test again. It is only for partially in/out leaf nodes that you test triangles. The runtime will be (mostly) sensitive to the number of triangles on the border of the frustum, which likely much smaller that all N triangles. – Crowley9 Jul 28 '11 at 12:19
up vote 1 down vote

Are you referring to frustum culling? There are many algorithms developed to speed up the process, but primarily, you aim to perform as little comparisons as possible per-object. So for instance, rather than checking that each triangle within an object lies within the viewing frustum, you can check the extremities (i.e. the left-most and right-most polygons), if these are both within the viewing frustum, no further check is necessary, the entire object is within the viewing frustum, if one of the extremities does not lie within the frustum, then check the middle polygon, and think of it as the same principle as binary sorting. As the polygons are ordered by position, you can get away with a lot fewer checks than O[n].

Other techniques include that used by the Quake Engine (and by extension the Source engine), with their BSP mapping, this process involves sorting your map into VisLeafs (Visibility leaves), which allows the engine to determine when a player is at one point in the map, what it is impossible for him to see, and thus that is never rendered, even if it is technically within the viewing frustum. This is done by dividing up the space using a series of planes and storing the information within the .bsp itself.

I hope this answers your question, and I've not just digressed into something totally irrelevant to you, if I have then leave a comment and I'll try my best to ammend this answer. :)

share|improve this answer
Well I don't think is strictly a frustum culling problem, I'm not trying to decide if an object is in view or not. – user8884 Jul 27 '11 at 16:13
@user8884 Then you can use the same principle as frustrum culling, but instead of culling the object, just return true on your test. You can also improve efficiency a lot here, because you only need to test the extremities to know if it's either partially or fully in view which is what you want. You will also need to perform depth testing on the object, to determine whether or not it's occluded by an object in front of it (either GPU z-testing or CPU z-testing will do here). – Shaktal Jul 27 '11 at 16:23
Say i have a mesh made of n tris. I need to identify the triangles of this mesh that are inside some range. This range could be a 'small' frustum. The brute-force way is: foreach tris, check if it is in range. When the mesh has many triangles, that could be inefficient. I think is basically a search problem, and for sure has some very well accepted solutions. Yuo are right, BSP is probabily one. – user8884 Jul 27 '11 at 16:25
Well, I'm just shooting in the dark here, but what if you have a step-size (i.e. number of triangles to jump) inversely proportional to the object distance. For instance, if you have an object to test within your PVS (assuming you implement BSP), you can do a depth-test and from that you can choose step size, if the object is far, you have a larger step size, as each triangle takes up less space on your screen. This could be one way to improve efficiency. But I'm slightly confused, you say that you need to find which triangles are in view, this means you will have O [n] regardless. – Shaktal Jul 27 '11 at 18:38
I'm sorry, object distance or screen size has nothing to do with my problem. I understand i miserably failed in explaining myself. Searching triangles within a mesh without paying O[n] is exactly what i'm looking for. – user8884 Jul 28 '11 at 6:11
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.