|
Author Topic:   List/Quadtree indexing
Hardy
New Member 		posted November 19, 1999 07:02 AM            
Right here we go again,
At present I have a linked list which contains my vertices.

What I'am trying to do is calculate a position within this list and link
it to a pointer in a quadtree block.
So each block then has a pointer to list position.

Does anyone know how to go about calculating this position ?.

The reason for this is so for each visable block I can tessellate
out from this link.

Matt......

IP:

LDA Seumas
unregistered 		posted November 23, 1999 03:20 AM           
I haven't dealt much with Quadtrees, so I can't help you directly, but it does strike me that storing vertices in a separate linked list might be sub-optimal. You might want to consider storing vertices in a static array of some maximum reasonable size, which will allow you to allocate vertices quickly, and they'll also be sitting in a format that you may be able to pass directly to OpenGL or Direct3D for rendering. I don't know the specifics of your engine, so perhaps this isn't an applicable suggestion.

------------------
-- Seumas McNally, Lead Programmer, Longbow Digital Arts

IP:

MikeC
Member 		posted November 23, 1999 08:19 PM            
If you are using an NxN matrix to store your height information, there really is no reason to store vertice information at all. As a matter of fact, in my quadtree implementation, I didn't even need to store texture coordinates. (But I did for speed). Basically I just have one texture over then entire grid, so I allocated an N dim array of floats and computed the texture coordinates for each point in N.

So what I was getting at about the vertices is that if you do it recursively, you can pass them on the stack. For instance if you have a 256 x 256 grid, your largets quad is 0,0,256,256.


a snipet from my code:

drawQuadrants(UINT32 ulx, UINT32 ulz, UINT32 wid, UINT32 dpt)

UINT16 midx, midz;

midx = wid>>1;
midz = dpt>>1;

drawQuadrants(ulx, ulz, midx, midz);
drawQuadrants((ulx+midx), ulz, midx, midz);
drawQuadrants((ulx+midx), (ulz+midz), midx, midz);
drawQuadrants(ulx, (ulz+midz), midx, midz);


All of my code is available at : http://www.salug.org/~mcoker if you want to take a look at it. There are no pointers at all in my code.

thanks,

Mike

IP:

MikeC
Member 		posted November 23, 1999 09:03 PM            
OK, that's not 100% accurate.. of course there are pointers, but no "nodes" so to speak.

mike

IP: