Timmmm3d
December 22nd, 2006, 07:19 PM
Hi, I'm writing a mapping program that is basically a big plane of polygons and lines.
In order to render view of the plane in a reasonable time (it could be a very sparse plane with only parts of the map loaded) I am planning to use a quadtree or some similar spatial indexing scheme.
However! The items have a z-order - they overlap and I can't use z-buffering because some of them are transparent.
Does anyone know of a good scheme to allow me to render the items, within a certain square in their z-order.
So far I've thought of the following possibilities:
1) A simple (or complex) grid of squares, each square has a link to all the objects that are visible in it, which are sorted by z-order (sorted when they are inserted for speed). Render each visible grid-square clipped to that square. This would work and I think it would be fast, but it requires drawing polygons on the edge more than once, and there might be artifacts at the join between the squares.
2) Force the z values to be a integers, and store a count of how many items use each value. Then go through a normal quadtree once for each z-value and render all the items with that z-value. This would work but it might be a bit slow.
3) Hmmm that's all I can think of. 2 seems most reasonable, but I'm sure there must be a better way! Does anyone know any good websites about spatial indexing?
Thanks
In order to render view of the plane in a reasonable time (it could be a very sparse plane with only parts of the map loaded) I am planning to use a quadtree or some similar spatial indexing scheme.
However! The items have a z-order - they overlap and I can't use z-buffering because some of them are transparent.
Does anyone know of a good scheme to allow me to render the items, within a certain square in their z-order.
So far I've thought of the following possibilities:
1) A simple (or complex) grid of squares, each square has a link to all the objects that are visible in it, which are sorted by z-order (sorted when they are inserted for speed). Render each visible grid-square clipped to that square. This would work and I think it would be fast, but it requires drawing polygons on the edge more than once, and there might be artifacts at the join between the squares.
2) Force the z values to be a integers, and store a count of how many items use each value. Then go through a normal quadtree once for each z-value and render all the items with that z-value. This would work but it might be a bit slow.
3) Hmmm that's all I can think of. 2 seems most reasonable, but I'm sure there must be a better way! Does anyone know any good websites about spatial indexing?
Thanks