hello,
I have a terrain which is described using polygons, I want to collect all object (build from polygons) which are perpendicular to the terrain…
wainting 4u
This isn’t an OpenGL question.
You have to manually iterate through the polygons and compare them with your ground/terrain.
Get the normal of the terrain (typically (0, 1, 0)) and those of the other polygons. Do a dot-product between the two normals. If it returns 0, the two normals, and thus the two polygons, are perpendicular to each other.
Since this is basic linear algebra you might want to read a bit about vectors, planes, the dot-product and linear algebra in general. Try wikipedia as a starting point, if that is not good enough, they certainly have good links to other websites explaining the concepts in more detail.
Happy coding,
Jan.
10x alot, I wanted to know maybe there is a more efficient alog to do the job, instead of iterate on all my polygons.
just a thought.
There are many more efficient algorithms than this. Just look for space partitioning algorithms like BSP and Quadtree.
Erm, not in this case.
If he just wants to find all perpendicular polygons ONCE, then there is no better way. He needs to look at each polygon at least once, so O(n) is the best he can get.
Of course, if he wants to do certain operations repeatedly, say, each frame, then it is more efficient to SORT the polygons ONCE and then only look the result up. However the particular operation he is trying to do cannot be speed up using BSP-trees or Quadtrees, those are used for other things. For example, if you only want to find all polys perpendicular to the ground IN A CERTAIN AREA (say within a radius of 10m around the player), then BSP-trees can help you to speed up your search, by limiting it to a subset of the polygons.
If you really want to do things with all polygons perpendicular to the ground each frame, find them once at startup and put them in a list. Then each frame you can work with only those polygons, ignoring the rest.
Although BSP and Quad-trees won’t help you in this case, it is indeed a good idea to get to know them, they are very useful for many (other) things.
Jan.
Well althought it wasn’t clearly defined in the original question, I got the feeling he was finding the polygons real-time in each frame. In this case, restricting the set of polygons to be tested can be optimized using preprocessed BSP and Quadtrees.