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:
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
Please log in or register to post a reply.
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
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
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
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
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
would this statement be true?
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 .
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
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
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..