Path: chuka.playstation.co.uk!news From: "Martin Keates" Newsgroups: scee.yaroze.freetalk.english Subject: Re: Quadtrees (again) Date: Fri, 29 Jun 2001 13:07:33 +0100 Organization: PlayStation Net Yaroze (SCEE) Lines: 30 Message-ID: <9hhr8u$dmm2@www.netyaroze-europe.com> References: <9hgh6q$b9r8@www.netyaroze-europe.com> NNTP-Posting-Host: modem-755.barracuda.dialup.pol.co.uk X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 5.50.4133.2400 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400 > difficulty with is the implementation. For example, how would you determine > which areas are visible (especially if the size of the areas are number of > polygons rather than physical size) and how do you keep track of where I don't follow what you mean about size here. > objects are and which area leads to which other areas. There are more Pointers! Obviously there are many ways of setting up the data structures. When I did a hybrid gridcell/octree implementation I used 2 basic structs; a leaf cell (with an object list) and a subdivided cell (with a 3D array in it - for octrees this is always 2x2x2). The arrays in the subdivided cells contain pointers to other subdivided cells and leaf cells (I think I used void * pointers and judicious use of casts - bit eurgh when I look at it now). > Does anyone know of a site (or books) which describes the implementation of > them? When I searched, I just found lots of information on what they are > and very few specific examples. Don't know of any sites, sorry. Most books I've read only had theoretical details and not much about implementation. Incidentally, I personally don't think octrees are much use for either view culling or collision detection - I would only ever use that kind of SMS for ray intersection testing. YMMV, as they say. Martin.