Quadtrees question

Right - the best way to check wether a node is inside the viewing
frustum is to check the bounding box of the node against said
frustum. There are lots of threads all about how to find out
the values for the frustum planes and how to check wether points
are inside it. One of them is quite a lenghty discussion I had
about it.

As to the back-front drawing, not sure how you''d do that.
One possible one is to check the distance from camera to the
center of the node, when the node is in the view frustum. Then
qsort the nodes from this value ?

That''s just a quick idea - probably a flaw in it somewhere ?

MrF.

MrF.
--
Code..reboot..code..reboot..sigh!

For front-to-back or vice versa:
For every node: see which of ist subnodes is closest (or not, depends on front-back of back-front) and draw that first.
If the node has no subnodes, draw it.

Hope this does the trick; you only have to sort eight of them which is quite easy... recursion does the rest for you. (I''m assuming you use the OOP approach).

Thanks for the quick reply

quote:

---

One possible one is to check the distance from camera to the
center of the node, when the node is in the view frustum. Then
qsort the nodes from this value ?

---

I guess i could do that but it would cost me two squareroots per node a frame. I am hoping theres a way that does not need costly calculations during run-time.

Who said anything about square roots?




Guess which subnode you draw first?
The left one or the right one?

Depends on front-to-back or back-to front... left first and right first respectively


It should be posible to apply this to three dimensions as in




The upper right and lower left are about equally far away... it's not the most accurate method there is but it IS fast.


[edited by - Kurioes on October 10, 2002 10:25:25 AM]

quote:

---

Original post by CProgrammer
I guess i could do that but it would cost me two squareroots per node a frame. I am hoping theres a way that does not need costly calculations during run-time.

---

You don''t really want to "use" the values, just to compare them. And since a^2 < b^2 => sqrt(a^2) < sqrt(b^2) you don''t need to compute the square roots, just compare the squared distances.

That''s another way

Oh i see what you mean.

So basically I could just take the midle of the node in which the cam is then check the distance to all nodes in view, by taking the distance as x-distance between nodes + z-distance between nodes.
That should work. Do you know what the FASTEST code is to sort the received vars from biggest to smallest?

Thanks for all your help.

-CProgrammer

You could just code for the four possibilities, since you know you only have four.

Cells:

|1|2|
|3|4|

If you're in cell 1, then draw 4-3-2-1
If you're in cell 2, then draw 3-1-4-2
If you're in cell 3, then draw 2-1-4-3
If you're in cell 4, then draw 1-2-3-4

Will that work? No calculations necessary.

If a cell contains a subtree, it works the same way at that level. Just do it recursively.


[edited by - Waverider on October 10, 2002 11:00:41 AM]

quote:

---

Original post by Waverider
Cells:

|1|2|
|3|4|

If you''re in cell 1, then draw 4-3-2-1
If you''re in cell 2, then draw 3-1-4-2
If you''re in cell 3, then draw 2-1-4-3
If you''re in cell 4, then draw 1-2-3-4

---

Something like that should work for 8 nodes (octree)...

Let me do the work ...

Cells:
(top)
1 2
3 4
(bottom)
5 6
7 8

Cell 1: 8-4-6-7-2-3-7-1
Cell 2: 7-3-5-8-1-4-6-2
Cell 3: 6-2-5-8-1-4-7-3
Cell 4: 5-1-6-7-2-3-8-4
Cell 5: 4-2-3-8-2-3-7-5
Cell 6: 3-1-4-7-2-5-8-6
Cell 7: 2-1-4-6-3-5-8-7
Cell 8: 1-2-3-5-4-6-7-8

However, it could be a good idea to consider how far the camera is away from "the" subnode... but I''d prefer using square roots in that case

Dang dude, yeah I knew that but I wasn''t going to actually do it!

[offtopic]
Off course you knew... I was bored
[/offtopic]