(L) [2006/04/06] [One_NotLogged] [Looking for an advice on 2D raycast] Wayback!To begin with, right now I'm struggling with my pet project : a 3D (actually 2.5D) 6DOF urban GIS. It is based on a dataset of approximately 130 thousand simple polygons with somewhat about two million vertices in total. Each polygon has a height associated with it, but it's limited (i.e. the highest building/tree/hill is 45 m, which is small compared to the whole map of 65 x 65 km).
I've done some experimentation with raycasting at the visualisation core. The idea is simple - to trace rays from the center of projection, compute all intersections with map geometry, perform 1D HSR and draw a ready line into the framebuffer - pretty much like a usual freelook "voxel-based" terrain. The decision to use raycasting was based primarily on the ability to do hiqh quality antialiasing (at least in one dimension [SMILEY Wink] )
Well, at first that task seemed easy to me, because the number of rays is quite small (5-7k is typical), the demand on interactiveness is not very high (0.25 sec per frame is OK, though the lower the better), and the whole thing is happening in 2D. But things are not so easy as they seem from the first sight.
The most important restriction I'm facing right now is the one on memory. Even in the original form the dataset is about 70 Mb in size, which is already outside the limit, so there's need in some form of on-the-fly decompression. Of course, big acceleration structures are not possible in that setting. Moreover, all the asymptotically efficient algorithms are using enormous amounts of memory.
The thing I'm optimizing now is based on the lazy construction of the segment kd-trees, which are rooted at the nodes of the original BBH. They're stored in a LRU list, and the oldest ones are deleted to impose the 16 Mb restriction on "geometry cache". That thing is needed mainly because majority of the objects has less than 10 segments. Everything works quite well on fixed query radius, but when taking it off the number of intersections per ray becomes way too high. Additionally most of the intersections are in the faraway area and contribute only slightly to the final image. The only way of removing this countereffect I can think of right now is doing some easy form of LOD, based on the kd-tree representation.
Additional requirements of the purchaser are : pure C++ code (no SIMD, not even MMX ;( ), high portability, ability to switch between 2d and 3d modes (raycasting can be used for 2D display as well, if applied to individual scanlines), probably some eye candy (shadows, reflections on water, etc., but that's last in the priority list).
What i want to ask is whether there are some algorithms or even working code for voxel-like all-intersections raycasting in the 2D plane taking into account the constrained memory environment? Maybe someone of the experts here can think of some good solution to my problem. I will highly appreciate any help.
I can give out some portions of the dataset on request, if there's need.
Regards,
One
P.S. Sorry for my English - i'm not a native speaker
(L) [2006/04/12] [lycium] [Looking for an advice on 2D raycast] Wayback!just a quick post to toss in an idea since i'm really supposed to be doing other things :/
since it's a 2.5d problem at heart, you could transform those really-3d triangles you're intersecting atm to a heightmap (just z-rasterise them, with a gpu if you can), which you then generate a few lods for (so res must have a power of two factor in there somewhere). you divide this bigass heightmap into a grid with maybe 256^2 texels per patch (needs tuning i bet), storing the max height for each patch. simple 2.5d raycasting will tell you when you go inside one of these patch-boxes while doing a coarse traversal, after which you do the detailed intersection with the heightmap (using nice interpolation and whatnot- if you use cubic interpolation you also get the normal as a byproduct if i remember correctly from calculus class). if the ray misses everything in the patch-box you go back to tracing the coarse representation, etc (also be sure to store a global max height and check that when exiting a patch for early-out when doing rays with direction.z > 0). if the map is utterly huge you can very quickly generate quarter-res patch-maps by using the max of 4 sub-patch heights hierarchically, switching levels as needed. i'm sure there's an empirical formula like some_cost_const * log2(max_map_dimension) you can derive for how many levels are appropriate given a fullres map size.
it shouldn't be too difficult to maintain caches for the different resolution lods (i think it's worthwhile to keep them seperate, but that's just a guess i can't substantiate without more tought) so you don't have to store the whole thing in memory at once; the latency of lazy-loading the fullres tiles from disk is tolerable since you don't need a zillion fps sustained; just don't wiggle the mouse around too much if your cache is small ;)
my only concern is that with interpolation you might lose out on those sharp edges (eg for tall buildings), but i guess you could use some kind of maximum contrast measure over the tile when you do the preprocess to see if it needs higher res than your initial 256^2 guesstimate; there's no reason why they should all be the same, and it should really be inversely proportional to smoothness. [edit: another concern is computing normals at the patch boundaries, this problem can be solved by various inelegant means, but i can't think of anything nice/clever at 2:45am after all this horrible linear algebra and number theory crap i'm forced to do :( basically you should always duplicate heightmap values from the neighbouring patches since they may not be in the cache, and even if they are it's ugly as hell to be fetching from all over the place; note that this doesn't preclude using power of two patch sizes if you do a bit of rescaling.]
you could get fancy and trace packets of rays through these grids with "live" flag bits (this is esp effective if they all miss more or less the same patches, which is an easy test if you're using bits). even without simd that's approximately a linear bandwidth saving with packet size, ignoring incoherence. if you pack all your antialiasing rays together that gets you a sublinear overall cost i think. another extremely important optimisation is to block your memory layout into cacheline-sized quads rather than a big linear thing inside the patches; besides a massive speedup due to better cache behaviour it levels the performance a lot (think about tracing diagonally through the patch bottom-right-to-top-left versus straight along the x-direction).
argh now i've spammed like mad already. i'm sure you could have thought of half of this stuff too :P btw your english is just fine, a million times better than most native speakers on the net who don't even bother to be clear, let alone mind spelling and grammar ;)
[yet another edit since the ideas won't stop coming: in the preprocessing stage, since it's all 2.5d, you can precompute a horizon map for each texel, dividing the angles around each point into equal segments. let's say 8 angle segments and 4 elevation levels, for 32bits (btw if you choose 4 angle segments you only need to check signs, but it may not be more efficient overall due to reduced culling accuracy etc). when doing a shadow ray you first check if the ray's direction.z value in whatever angle segment is above the 4-level stored's corresponding z-value; if so it's guaranteed to not hit anything and you don't trace it. if you keep track of the lowest and highest elevation per patch and make the 4 levels' range map to that, it could be quite efficent. these horizon maps can be efficiently generated if you have those lods with max heights for fast bailout during the precomp.]