## Re: [Algorithms] spatial sorting

 Re: [Algorithms] spatial sorting From: - 2002-04-30 13:36:38 ``` I guess we should read : > > recurse_over_tree(node* n, int mask, query_info > query) > { > if (n == NULL) return; > > if (query can't touch this node's BB) return; > > // check contact in this node > > // check contact in children > for (int i = 0; i < 4; i++) { > // Here's the trick; order of traversal depends > mask. > int index = i ^ mask; > > recurse_over_tree(n->child[i], mask, query); // <- no use of index ????????? recurse_over_tree(n->child[index], mask, query); > } > } ___________________________________________________________ Do You Yahoo!? -- Une adresse @yahoo.fr gratuite et en français ! Yahoo! Mail : http://fr.mail.yahoo.com ```

 [Algorithms] spatial sorting From: LtJ - 2002-04-30 10:49:17 ```Hi! I'm having problems to find an Algorithm for a fast and accurate Collision Querry in a quadtree terrain mesh. My problem is that if I cast a line or a ray, I want the first collision point/surface on the line and not one at the end. I guess I need some kind if spatial sorting while I travel the tree, which doesn't seem quite nice in a quadtree. Does it make sense to convert the quadtree into a bsp for the collision part? That tree is static and won't be changed at runtime, so the time needed to do a conversion like that is not an issue. Thx, Marius Elvert ```
 Re: [Algorithms] spatial sorting From: Thatcher Ulrich - 2002-04-30 13:14:10 ```On Apr 30, 2002 at 12:44 +0200, LtJax wrote: > Hi! > I'm having problems to find an Algorithm for a fast and accurate > Collision Querry in a quadtree terrain mesh. My problem is that if I > cast a line or a ray, I want the first collision point/surface on the > line and not one at the end. I guess I need some kind if spatial sorting > while I travel the tree, which doesn't seem quite nice in a quadtree. > Does it make sense to convert the quadtree into a bsp for the collision > part? That tree is static and won't be changed at runtime, so the time > needed to do a conversion like that is not an issue. A quadtree is already perfect for what you want. You should add min/max vertical extents to the nodes, if you don't have them already, so each node has a bounding AABB (not strictly necessary -- whether it's worth it depends on how "3D" your queries & data are). A trick for traversing a quadtree in a particular order: traverse(node* root, vec3 dir, query_info query) { int mask = 0; if (dir.x < 0) mask |= 1; if (dir.z < 0) mask |= 2; recurse_over_tree(root, mask, query); } recurse_over_tree(node* n, int mask, query_info query) { if (n == NULL) return; if (query can't touch this node's BB) return; // check contact in this node // check contact in children for (int i = 0; i < 4; i++) { // Here's the trick; order of traversal depends mask. int index = i ^ mask; recurse_over_tree(n->child[i], mask, query); } } The idea is that you can cheaply go in front-to-back order by analyzing the line direction before traversing. If you only have data at the leaf nodes, then you'll get a correct front-to-back sort over the nodes. If you have data in interior nodes, or if your nodes have multiple triangles in them, then you will need to pick the closest contact (no big deal -- when you get a contact just compare with the distance of any previous contact). -- Thatcher Ulrich http://tulrich.com ```
 Re: [Algorithms] spatial sorting From: - 2002-04-30 13:36:38 ``` I guess we should read : > > recurse_over_tree(node* n, int mask, query_info > query) > { > if (n == NULL) return; > > if (query can't touch this node's BB) return; > > // check contact in this node > > // check contact in children > for (int i = 0; i < 4; i++) { > // Here's the trick; order of traversal depends > mask. > int index = i ^ mask; > > recurse_over_tree(n->child[i], mask, query); // <- no use of index ????????? recurse_over_tree(n->child[index], mask, query); > } > } ___________________________________________________________ Do You Yahoo!? -- Une adresse @yahoo.fr gratuite et en français ! Yahoo! Mail : http://fr.mail.yahoo.com ```
 Re: [Algorithms] spatial sorting From: Thatcher Ulrich - 2002-04-30 16:20:27 ```On Apr 30, 2002 at 03:36 +0200, Emmanuel Astier wrote: > > recurse_over_tree(n->child[i], mask, query); // <- > no use of index ????????? > > recurse_over_tree(n->child[index], mask, query); Whoops, you're right, thanks. -- Thatcher Ulrich http://tulrich.com ```