Path: chuka.playstation.co.uk!news
From: "Alex Herbert" <alex@herbs.dabsol.co.uk>
Newsgroups: scee.yaroze.freetalk.english
Subject: Re: Quadtrees - am I missing something
Date: Sat, 17 Feb 2001 18:17:17 -0000
Organization: PlayStation Net Yaroze (SCEE)
Lines: 60
Message-ID: <96melm$3gi1@www.netyaroze-europe.com>
References: <96kfp8$rfo1@www.netyaroze-europe.com>
NNTP-Posting-Host: host213-123-130-134.btopenworld.com
X-Priority: 3
X-MSMail-Priority: Normal
X-Newsreader: Microsoft Outlook Express 5.50.4522.1200
X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4522.1200

Right, I've never heard of a quadtree before but I think I get it.  I think
it goes something like this:

Divide the terrain into quadrants.  For each quadrant define a bounding
rectangle (or a cuboid maybe better) then bash it through your view
transformation matrix (i.e. transform to screen coord's).  If none of the
vertices end up within the screen area then the whole quadrant is out of
view and can be eliminated from drawing.  If all the vertices are within the
screen area then the whole area needs to be drawn.  If only some of the
vertices are within the screen area then that quadrant is partially visible
and needs to be sub-divided further.

Does that sound right?

Alex


"John ( QuietBloke )" <quietbloke@btinternet.com> wrote in message
news:96kfp8$rfo1@www.netyaroze-europe.com...
> OK.. I've just been looking into Quadtrees today. Part of my 3d self
> training course. I can see its a very simple concept but I must be being
> real dim tonight because I cant see the point of them.
>
> Reason...
> OK.. the main example I saw was a small example terrain of a 16x16 grid.
The
> reasoning was you dont want to draw the whole terrain just the bit the
> camera can see.
> This is the bit I dont get.. the tutorial then goes through how with a
> quadtree you start from the root and check the camera in the four quarters
> and eliminate the ones its not in.. then sub divide again etc etc and
> eventually you end up with just the leaf(s) that the camera is in and the
> leafs point to triangle data to draw the scene.
> Thats all fine and dandy but if its a grid then surely you can just do a
> quick calculation to figure out which leaf the camera is in...
>
> ie.. the camera x and y position will tell you exactly what cell the
camera
> is in.
>
> So what has this tutorial missed out ?... anyone ?.. why would I need to
use
> an quadtree when drawing a terrain ?
>
> Also... what happens next ?.. I know what leaf the camera is in but how do
> you decide what cells are visible going out to the horizon ( or a fair
> distance at least ) ?
>
> Im sure some of you have done this and its obvious and sorry for being dim
> but this really is all new to me and from what I've discovered I have a
> awful lot to learn !
>
> Ahhh who knows.. by tommorow morning I may have it figured out.
>
> Cheers
> John
>
>