3D Flood Fill
Posted 14 June 2009 - 10:28 AM
The way i'm planning on doing it is by constructing a grid of points along each triangle and performing a brute force ray cast to see what triangles are visible from one another, the basic steps are:
1. calculate triangle visibility matrix (what triangles are visible from which)
2. find the first triangle visible from the point
3. recursively flag all triangles visible from this triangle until all visible triangles have been flagged
If I could accurately determine which triangles are visible from which would this algorithm ever fail in any case?
and how can I accuratly determine which triangles are visible from each other?
Posted 14 June 2009 - 12:00 PM
First i voxelized the 3d space and then i performed a flood fill from each cell to see which cell is visible from there.
Now, this sounds good on paper and the implementation isn't difficult, the problem is that light travels in a straight line and doesn't flood fills anything
in fact you may end to reach point which aren't visible form the cell you start to perform the flooding, further there were cases where the entire 3d voxel grid was filled.
Another variation is the method you describe, plot points over a surface of triangle and see which triangle are visible from there, again this is good on paper but the complexity is O( n^2 ) , where n is the amount fo triangle beetween your source traingle and the target triangle assuming you have produced an alogrithm to build a frustum from the source triangle and having considered triangles included inside this frustum itself
I have written almost every conceivable visibility algorithm and i have discarded 99% of them because of the enormous amount of time involved in preprocessing , i have other ideas but they are currenlty on hold
Posted 14 June 2009 - 01:00 PM
In other words if you stand in a non-convex room that is painted pure white, and turn the light on that every surface in that room will be illuminated, wheras anything outside won't be. (assuming the light is bright enough).
and even if you place any sort of geometry in this room the light will still reach even the most hidden/smallest triangle by bouncing off of other surfaces.
would this statement be true?
Posted 14 June 2009 - 04:40 PM
I can assure you that this kind of algorithm has a complexity far too heavy for a precomputed level.
I don't want to influence you, once again, but compiling a level may take several hours if you consider every rays' intersection with every other triangle in a map level .
Posted 14 June 2009 - 06:41 PM
what other efficient ways are there? I've already tried using a bsp, it works but as soon as geometry gets the slightest bit complex it usually fails:(
Posted 14 June 2009 - 09:27 PM
I got it working for a relatively simple level, this took roughly 2 mins. I can see what you mean about the O(n^2) time, the green dots are all the sample points spread over the triangles.
I am using this for determining what triangles belong to a sector and I use portals to occlude the rays cast between triangles. any better way to go about this?
would I be better to just manually flag all geometry that belongs to these sectors?
Posted 14 June 2009 - 11:53 PM
I did in this way i had a regular grid subdivision, then for each cell i iterated trhough each triangle and for each triangle i built a frustum all other celle were checked for inclusion , note that you may stop here , without going further if you wanted a coarser level of visibility , or, dot a regular vertex subdivision for each triangel and shoot a ray trhough all the cells intersected by the frustum.
My algo took 1.5 hours for a large level. This was at the time i had a single cpu computer, since 1 year i upgraded to a quad, so i may return considering this algorithm again.
You made me start again thinking about visibility algorithm and taking me up all night..
1 user(s) are reading this topic
0 members, 1 guests, 0 anonymous users