3D Flood Fill

235b371d8fea8dbf60a687b31f8b5f67
0
staticVoid2 101 Jun 14, 2009 at 10:28

I’m trying to perform a 3d flood fill on a triangle soup so that I can set a 3d point and all triangles directly or indirectly visible from this point will be flagged. I think this is the same as performing radiosity calculations with an infinently bright light source?

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?

6 Replies

Please log in or register to post a reply.

Ceee4d1295c32a0c1c08a9eae8c9459d
0
v71 105 Jun 14, 2009 at 12:00

I have dealt with this problem years ago, i don’t want to influence in a bad way , but i discarded this method and i explain why
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

235b371d8fea8dbf60a687b31f8b5f67
0
staticVoid2 101 Jun 14, 2009 at 13:00

but isn’t it true that if you considered the point to be a light source and triangle surfaces to emit light in all directions, then this boils down to well known radiosity calculations?

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?

Ceee4d1295c32a0c1c08a9eae8c9459d
0
v71 105 Jun 14, 2009 at 16:40

basically yes, this is what radiosity does, the visibility preprocesing though, assumes that you need to stand inside the triangle ‘s frustum to be able to see what the triangles sees.
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 .

235b371d8fea8dbf60a687b31f8b5f67
0
staticVoid2 101 Jun 14, 2009 at 18:41

but the only expensive part is calculating what triangle is visible from another, as soon as a ray passes from triangle A to triangle B without being occluded you can return early, if you calculate from A to B then you don’t need to from B to A, only test if two triangles are in front of each other, using this coupled with some for of spatial tree structure. Wouldn’t this be acceptable speed for a preprocess step?.

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:(

235b371d8fea8dbf60a687b31f8b5f67
0
staticVoid2 101 Jun 14, 2009 at 21:27

raycastfloodfill.th.jpg

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?

Ceee4d1295c32a0c1c08a9eae8c9459d
0
v71 105 Jun 14, 2009 at 23:53

Yes that would be acceptable, you can use an octree or whatever data structure you feel confortable with.
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..