Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (524)
Games in Android Showcase (127)
games submitted by our members
Games in WIP (592)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  quadtree search question  (Read 1660 times)
0 Members and 1 Guest are viewing this topic.
Offline Daath

Junior Devvie




Java games rock!


« Posted 2003-01-26 16:03:51 »

Hi all,
I am working on terrain code and using quadtree for frustrum culling. Was wandering what might be the best way to search quadtree to eliminate nodes which will not be rendered. One way might be to have just plain array and assign nodes to it as there are being recurcively created and then search through that array - or maybe more(or less) efficient might be to search recurcively tree along the edges. Does anybody have any input on this?
Later.
Offline elias

Senior Devvie





« Reply #1 - Posted 2003-01-26 16:56:22 »

I'm not sure what you mean, but the whole point of using quadtrees for frustum culling is to cut away nodes that will not be renderes asap. When rendering a quadtree test if the root node is in the view frustum (nearly always of course). If it is recurse on the 4 root children, checking all 4 nodes in turn. That way, nodes and their subtrees not in the view will be discarded as soon as possible.

- elias

Offline Daath

Junior Devvie




Java games rock!


« Reply #2 - Posted 2003-01-26 18:00:49 »

thanks for reply - I guess I was not making myself clear - it is the actaull method for searching a node I am concerned with. Once the tree is built and I am to find node which is to be rendered. SO my question is what is the most efficient way of finding a node in quatree. I saw some c++ based code and and the way they were searching for a node was to have array which was storing reference of each newly constructed node - and then they basically go through that array and search for node. I was thinking storing that reference might be a waste - search function can be done recursively .....  which way then is more efficient then ....I hope I am making more sense now Smiley
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline elias

Senior Devvie





« Reply #3 - Posted 2003-01-26 18:43:45 »

Why would you search for a node? I'm guessing the C code was really storing the tree in an array, but that makes no difference to the algorithm for traversing and rendering the tree.

- elias

Offline Daath

Junior Devvie




Java games rock!


« Reply #4 - Posted 2003-01-26 18:59:48 »

why would I be searching for a node? ....I create quadtree and it it loaded into memory ..... then when it comes to finding which  leaf node (being Shape3D - having its own BranchGroup and reference to patch holding geometry and texture ) is to be included I am going through tree find them and those are then attached to a main BrachGroup .......it is already working - I was just wandering if there is a better way for a search .... basically my question is more about  manipulation of data structures then graphics ...
Offline elias

Senior Devvie





« Reply #5 - Posted 2003-01-26 19:23:01 »

if you mean "to be rendered this frame" when you say "included" there is a better way, namely _the_ recursive way to traverse a quadtree. How is your quad tree built, data structure wise?

- elias

Offline Daath

Junior Devvie




Java games rock!


« Reply #6 - Posted 2003-01-26 19:42:03 »

I use  a rescricted fixed-lenght quadtree ... it is actually quite primitive to construct such a structure and I imagine there are better ways to attack this problem but the reason I decided for this approach is I have easy (maybe only for me) way of handling heightmaps....see I am using for some portion of terrain more then 2 heightmaps being referenced by one leaf node - reason is I am trying to have a tunnel  through mountain -  that part is not done yet I am trying to figure out tringulation of such a geometry ...... later on I wanna move from static tree to something like CLOD described by Roettger http://wwwvis.informatik.uni-stuttgart.de/~roettger/

Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

toopeicgaming1999 (57 views)
2014-11-26 15:22:04

toopeicgaming1999 (51 views)
2014-11-26 15:20:36

toopeicgaming1999 (10 views)
2014-11-26 15:20:08

SHC (24 views)
2014-11-25 12:00:59

SHC (24 views)
2014-11-25 11:53:45

Norakomi (27 views)
2014-11-25 11:26:43

Gibbo3771 (24 views)
2014-11-24 19:59:16

trollwarrior1 (37 views)
2014-11-22 12:13:56

xFryIx (75 views)
2014-11-13 12:34:49

digdugdiggy (52 views)
2014-11-12 21:11:50
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!