 |
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|||||||||||||||||
Add Forum to Favorites | Send Topic To a Friend | View Forum FAQ | Track this topic |
Last Thread Next Thread |
| Quadtrees |
|
 |
Do0d Member since: 1/5/2001 |
|||
 Posted - 2/12/2001 11:08:31 PM |
||||
| woohoo finnaly a proper expanation great tut thanx how bout another on detecting wher u are?  |
||||
|
||||
|
mja Member since: 10/13/2000 From: United Kingdom |
|||
 Posted - 2/17/2001 7:41:22 PM |
||||
| Nice one! icq = 95539717 mail = mja_today@hotmail.com |
||||
|
||||
|
Thygrrr Member since: 1/30/2000 From: Giebelstadt, Germany |
|||
 Posted - 4/9/2001 8:42:10 AM |
||||
| It doesn't point out that the Quadtree structure will also work for Irregular Triangle Meshes! Checking for a frustum in a regular mesh can be done more trivially even by just LERPing along the frustrum's edges, rasterizing the map into triangles and strips. Apart from that, nice tutorial (albeit I find the tree "struct" far from optimal, considering size and datatybe choice). Regards, Thy' www.optionoverkill.com |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 4/19/2001 5:06:06 AM |
||||
| Very good Tut. Nice to see that things learned in school is used in Game programming... /Trob |
||||
|
||||
|
GalaxyQuest Member since: 10/7/2000 From: ca, usa |
|||
|
Posted - 5/11/2001 6:14:22 PM |
||||
| I have 2 complaints/problems with the examples. First, the author does not explain in any detail how he figured out which way camera is pointing. Its obvious from a picture that its pointing towards a corner, and so the nodes 2-4 are eliminated from drawing. What he doesnt point out is this: what happens if that camera was in same position but looking in opposite direction. His example would still eliminate nodes 2-4 still, because we are excluding based on camera position. (well, at least thats how he goes about his example, by position only) Second, i tried his little quadtree.exe and it didnt do a thing AFTER it reads in height... it just sits there. I dont care too much about the app.exe problem, but would like some comments on what is "really" done to figure out what to draw and what not to draw, because position dont mean a thing "when we can see miles," as the author comments on. Anyone?? Visit my Webpage and Project: LoreQuest |
||||
|
||||
|
HellRiZZer Suspended Member since: 3/19/2000 From: Bathurst, Australia |
|||
 Posted - 5/16/2001 4:52:32 AM |
||||
| I was thinking about improving a structure of a quad.. In the code, it seems that EVERY quad except leaf, must have numbers in it's next children coordinates. If we'd have the following structure: typedef struct pt3f { float x,y,z; } Pt3f; class NODE { bool Last; // If this node is leaf, don't tesselate, Last=true Pt3f *P1; // Top left corner Pt3f *P2; // Top right corner Pt3f *P3; // Bottom right corner Pt3f *P4; // Bottom left corner NODE *Child1; // Top left child NODE *Child2; // Top right child NODE *Child3; // Bottom right child NODE *Child4; // Bottom left child }; Ok, the explanation? Here.. If we start from "start", we define map dimensions by reading from file or assigning at startup. Those points are the global ones: Pt3f *Start1.x ..y, ..z loaded or assigned; Pt3f *Start2; same for next ones.. Pt3f *Start3; Pt3f *Start4; Then, the first node is the whole map; NODE *MAP; MAP->P1.x=Start1->x; MAP->P1.y=Start1->y; and so on for all points.. MAP->P2.x=Start2->x; MAP->P2.y=Start2->y; so, we defined our points for a MAP.. Now, we tesselate the map on 4 parts (sorry, i'll be using the word "tesselate" for quad division, ok? )So, we can call function MAP->Tesselate(); and in it we assign points for new four children like: // Top left child Child1->P1=P1; // just assume that point is one dimensional Child1->P2=P2/2; Child1->P3=P3/2; Child1->P4=P4/2 and so on for all children (too long to write code for all children, soz. )SO, each child will have a reference to 3 values, not 12 values for triangle strips... That's the idea.. It's looks similar to ROAM, at least it uses the ROAM principle of triangle linked lists... Hmm..That's about it.. I just wanted to explain the better, as I think, way to do quadtrees with data and memory consume... Cya !! |
||||
|
||||
|
Maximus Member since: 8/9/2000 From: Dingoland |
|||
|
Posted - 5/16/2001 5:14:51 AM |
||||
quote: Firstly, if you dont know which way your camera is pointing then its most likely pointing at an angle of 0 (zero) degrees. You need to know the angle it will be looking at to be able to tell it to look at that angle, so its obvious that you save it somewhere (like in the camera's struct/class/etc). Secondly, the nodes are eliminated from drawing by frustum culling, so the position of the camera doesnt really matter too much when walking the tree, only in the culling routine, and even then it takes into account the angle of the view. Hope that helps a bit. |
||||
|
||||
|
Chris Ferraris Member since: 11/19/2001 |
|||
 Posted - 11/19/2001 12:02:16 PM |
||||
| Awww... my little bro finally doing something useful! Nice one! |
||||
|
||||
|
GBGames Member since: 1/25/2001 From: Chicago, IL, United States |
|||
|
Posted - 8/21/2002 1:11:51 PM |
||||
quote: I agree. I must be looking at these tutorials incorrectly and perhaps I need a real game/graphics example that demonstrates how the polygons are avoided. The position in a node algorithm doesn't make sense if I should be able to see polygons in a node that I am not in. Maybe it was if the viewing frustrum could see the node? But that was not how it was explained. |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 7/10/2003 5:26:51 PM |
||||
| I'm really sorry, but i didn't get one point: "The above formula gives us the number of leaves. The Leaf Width is the number of triangles across in each leaf. As we said each leaf will be one cell by one cell, we also said each cell contains 16 triangles. In our case, seeing as cells are 16x16 triangles, the Leaf Width will be 4. Grid Width is the width of the grid in triangles. As each cell is 4 triangles across, 16 cells x 4 is 64. To find out the total number of nodes in the tree, we call the function CalcNodeNum." What do you mean by "each cell contains 16 triangles"? How can this be? As I understand, the leaves are simple "cells", quadratic squares... And these can only be filled with 2 tris or 8 tris or 32 tris..... And what do you mean by "across in each leaf"? thank you. |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 9/20/2003 4:08:25 PM |
||||
| Great example! I can understand the confusion, because he stopped the example at the quadrant that the camera was in, but just before the end of the page he wrote "For your information, there are 16 more tests, resulting in 5 cells being visible". This meant to me that he was testing each cell based on the frustrum of the camera (the proper way to do it) because obviously 5 cells (arguably possibly more, but roughly yes 5) exist in the frustrum space, for the entire test. |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 9/20/2003 6:14:25 PM |
||||
| Thinking about this problem a little further, I have come up with a theoretical approach that might help. Let's play 2D for a minute. You can create 3 vectors from a camera. 1 vector from the origin vertex of the camera to the outer left frustrum vertex, 1 vector from the origin vertex of the camera to the outer right frustrum vertex (here left is -z, right is +z), and 1 vector from the outer left to the outer right frustrum vertex. Draw out a camera and its frustrum to understand it a little easier. Now, we determine if each of the 3 vectors lies in the bounding node of the quadtree. If one of them does, we iterate through that node to find out which sub-node(s) the vector lies in. It could be 1, it could be more. When you get to the point where you've checked all four child nodes and they all contain the vector, there's no reason to continue on. Make note that the whole node needs to be rendered. What may seem somewhat difficult is determining if the vector lies inside a box. Actually, it's not that hard. If we consider quadrant 1 for example, there are 4 lines defining the node. You can consider the enclosed area as a solid. There are plenty of algorithms for determining if a line/point lie within a solid, but I'm not good enough to remember them off the top of my head. Hope that helps, Chris |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 4/12/2004 7:09:35 PM |
||||
| I'm pretty new to CS, but I think I get the quadtree concept. I have a question though: can a quadtree be used to detect hits dynamically? Say you have lots of squares, each with their own corner points, that move around and don't necessarily fill up all the space on the map, and most of the time don't touch. If you were trying to find any and all intersections between squares, how would you go about it? Could you store the squares in a quadtree somehow, with each node either being a square or a section of the map? That's probably confusing. I don't know how to ask what I'm asking. I guess my main question is, can you make a quadtree out of things that move around, or just static scenery? |
||||
|
||||
|
mrbastard Member since: 10/9/2000 From: Nottingham, United Kingdom |
|||
|
Posted - 4/12/2004 7:25:15 PM |
||||
| AP: yes, you can use quadtrees for dynamic objects. However, you get a problem when dynamic objects are on boundries of quad nodes, and could be considered to be in more than one node at once. For an elegant solution google for "loose" quadtrees, invented by Thatcher Ulrich. |
||||
|
||||
|
Halsafar Member since: 8/29/2004 From: Saskatoon, Canada |
|||
|
Posted - 12/23/2004 4:07:28 PM |
||||
| How on earth do you find out how many nodes/leaves I need. My heightmap is 128x128. The final vertice points I will apply a scale to but the quad tree will be divided from the height map. So, 128x128 with each pixel on the heightmap containing 2 triangles. each leaf shall contain 8 triangles (ie. 2x2 on the heightmap). So is the formula to find out how many leaves simply 128*128 / LeafWidth?? If so, then how do I find how many nodes???? |
||||
|
||||
|
blueblood Member since: 12/12/2005 From: Ronneby, Sweden |
|||
|
Posted - 2/17/2006 1:53:19 PM |
||||
| Hi, I got a, what I think, is a stupid question. But how do i get vertices, and select wich to render? (DirectX this) As you can see I can't even explain correctly :( I got my Terrain renderd, 100x100 verticies. What I'm thinking is that it has something to do with my Vertexbuffer? And how do I render just some vertices? A pure DX example would make me a very happy coder.. /blueblood |
||||
|
||||
|
Silkjc Member since: 1/28/2006 From: Melbourne, Australia |
|||
|
Posted - 2/19/2006 12:02:31 AM |
||||
| As blueblood tried to say... Once the quadtree is constructed, and the terrain vertices in the index and vertex buffer, how can you determine which vertices make up the node(s) within the view frustum, and render only this set of vertices? DirectX examples would be nice :) |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 2/19/2006 1:41:59 AM |
||||
| You may have to do someindex & vertex bufferstuff - maybr refill your index buffer with the appropriate indices. The vertex buffer stays on system mem (I think, when using index buffers), only the "indexed" ones of it are sent to the card, so just refill the index buffer each time to point to the right vertices in your vb. |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 2/19/2006 1:50:27 AM |
||||
| Get used to handeling your vertices as quads (made of 2 triangles), in the demo there were five cells to be rendered, that means 5 quads, so you should maybe have already sorted the data out in terms of which vertices & indices belong to (or are used by), a quad, then just hook into them and draw them. |
||||
|
||||
|
appel Member since: 6/6/2005 From: Kopavogur, Iceland |
|||
|
Posted - 11/16/2006 5:58:57 PM |
||||
| In my opinion, this is not the *best* way to do quad-trees. A common thinking, a misunderstanding perhaps, when talking about quad-trees is to think about datastructures. Indeed the method works like traversing a binary tree from rootnode to throughout the child nodes, but a quad-tree is a TECHNIQUE, or an ALGORITHM on how to effeciently render terrains. Putting it up in a quad-datastructure-tree is one way, but it is an overkill since the method/algorithm is so simple. Doing it in this special-purpose "quad-tree-datastructure" also limits you from doing other optimizations using other techniques. Here is a method for QT using recursion. It basically involves using a two dimensional float array containing the y values. maxSubdivisions means how far (in recursion) to go in details before rendering the square. (Note, you should not exceed more than 4 subdivisions, as 2^4 = 16) drawSquare tries to draw a square from start point (x1,z1) to end point (x2, z2), but if it hasn't reached the drawing-level yet then it subdivides itself into 4 squares. But before it does that it checks if it is visible inside the frustum... if not then there is no need to continue. (NOTE, THIS IS JUST A PSEUDO CODE)
float[][] map = new map[16][16];
int maxSubdivisions = 4; // each drawable square is size 1x1
void drawSquare(x1, z1, x2, z2, int levels) {
levels++;
if(levels == maxSubdivisions) {
...do the actual rendering...
}
else if(isInsideFrustum(x1,z1,x2,z2)) {
/*
* +---+---+
* | A | B |
* +---+---+
* | C | D |
* +---+---+
*
*/
drawSquare(....A..., levels); // top left
drawSquare(...B..., levels); // top right etc.
drawSquare(...C..., levels);
drawSquare(...D..., levels);
}
}
boolean isInsideFrustum(x1, z1, x2, z2) {
...
}
void render() {
drawSquare(0, 0, 16, 16);
}
|
||||
|
||||
| All times are ET (US) |
Last Thread Next Thread |
|
