   3d flood fill algorithms?
  hi, I've been looking for algorithms that will flood fill a triangle soup given a certain position in space.currently I am just constructing an array of points across each triangle and then casting rays between each of them to see whether a triangle is visible from another, I store this data in a visibility matrix so that I can look up which triangle is visible from which.to flood fill from a point I find the first visible triangle from that point and recurse through all of its visible triangles and all triangles visible to these and so on... until all the visible triangles have been flagged:The problem with this is that its really slow and inaccurate, the accuracy depends on how far apart the sample points are placed, and if you increase the number of points then it takes even longer.Is there any good solution to this, one that preferably doesn't require using a bsp tree?   
  So it has to be a triangle soup, if it wasnt a soup maybe you could use adjacency and fill across triangle edges to get it to work.But a soup eh?  God that sounds complex, what is this algorythm actually for?Maybe some sort of spacial division would be mandatory.you could use a grid too, That would be quick but would be very expensive to the ram.   ;Quote:But a soup eh? God that sounds complex, what is this algorythm actually for?I'm trying to 'portalize' a scene by putting a point on either side of a portal and then performing a flood fill.I've already got portalization working using a bsp, where I rejoin the leafs back together until I hit a portal but it can take forever on a complex scene and usually doesn't work because the geometry isn't perfect, or because of some floating point precision error.I think what I'm trying to do is something simlar to radiosity calculations, i.e. if you shine an infinently bright light in a room, calculate all illuminated surfaces.Quote:you could use a grid too, That would be quick but would be very expensive to the ram.I thougt about this but would it not miss certain triangles if the size of each grid cell is too large, or if the triangle is too small?   ;  Have you coded point light shadow maps before?If you did an id render for 6 cube perspective directions around the point, you could record triangle ids.Could you manage that?(your idea is really cool btw)then you would place a small cube instead of a point.   ;I take it you would just orientate the camera to face in the direction of each face of the cube, set the viewport to be the size of the face and then render?...then just scan the backbuffer for the triangle id's?as for triangle id's I would guess you would just set the color of each vertex to be the id and turn off lighting, texturing etc.anything I'm missing?;  Thats it,That would get infinite light coming out of a point... but its not quite a flood fill unfortunately, would it still be useful to you?   