Thread: [Algorithms] portal engines in outdoor environments
Brought to you by:
vexxed72
Menu
▾
▴
gdalgorithms-list
|
From: Charles B. <cb...@cb...> - 2000-08-18 17:26:38
|
.. is a hopeless proposition, I think. I'd just like you guys to check my reasoning before I give up. Consider, for example, a building placed on a landscape. The goal is to construct portals so that when you stand on one side of the building, you can't see the other. If the player is constrained to stay on the ground, this is easy enough, it's really a 2d occlusion problem, and you need 8 portals (two * 4 faces of a square in 2d; two portals cuz you need one on each side of a face of the square, parrallel to that face) which splits the universe into 9 zones (8 outside and one inside the occluding cube). However, if we have a plain cube in 3d and the player can go anywhere around it, we need 48 portals !! (8 for each of the 6 faces on the cube). Now if you have two cubes near eachother, you need massive numbers of portals, and they must all not intersect with eachother or other geometry. This quickly becomes unworkable. I think something like a "real-time" occcluder (shadow volumes, etc.) is the only hope for outdoors. -------------------------------------- Charles Bloom www.cbloom.com |
|
From: John R. <jra...@ve...> - 2000-08-18 18:00:55
|
In my game the player is almost always on the ground. I'm just going to do a precomputed visiblity solution on a hash grid against the ground. Meaning, wherever you are standing it has precomputed what objects, nodes, etc. can be seen from that position. I've done it before, works fine. John -----Original Message----- From: Charles Bloom [mailto:cb...@cb...] Sent: Friday, August 18, 2000 12:26 PM To: gda...@li... Subject: [Algorithms] portal engines in outdoor environments .. is a hopeless proposition, I think. I'd just like you guys to check my reasoning before I give up. Consider, for example, a building placed on a landscape. The goal is to construct portals so that when you stand on one side of the building, you can't see the other. If the player is constrained to stay on the ground, this is easy enough, it's really a 2d occlusion problem, and you need 8 portals (two * 4 faces of a square in 2d; two portals cuz you need one on each side of a face of the square, parrallel to that face) which splits the universe into 9 zones (8 outside and one inside the occluding cube). However, if we have a plain cube in 3d and the player can go anywhere around it, we need 48 portals !! (8 for each of the 6 faces on the cube). Now if you have two cubes near eachother, you need massive numbers of portals, and they must all not intersect with eachother or other geometry. This quickly becomes unworkable. I think something like a "real-time" occcluder (shadow volumes, etc.) is the only hope for outdoors. -------------------------------------- Charles Bloom www.cbloom.com _______________________________________________ GDAlgorithms-list mailing list GDA...@li... http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list |
|
From: Jason Z. <zi...@n-...> - 2000-08-18 18:48:00
|
As usual John has done something I've only idly thought about then dismissed. :) Hope you dont mind me picking your brain on this for the whole list to see. What about RAM requirements for this pre-computed list? If your terrain is fairly large I can imagine the RAM usage could get quite high. Do you cut up the terrain into very large chunks so the visibility lists at each node don't get too high? And of course there is the inevitable question of how you compute what is visible to what node. I'd assume its done as a pre-process? And do you do a full 3D solution with volumes, etc. or a 2.5D type of thing? I was thinking some sort of grid-tracing like approach might work, where you check heights at each grid sample point to see if its visible. Thanks, - Jason Zisk - nFusion Interactive LLC ----- Original Message ----- From: "John Ratcliff" <jra...@ve...> To: <gda...@li...> Sent: Friday, August 18, 2000 2:05 PM Subject: RE: [Algorithms] portal engines in outdoor environments > In my game the player is almost always on the ground. I'm just going to do > a precomputed visiblity solution on a hash grid against the ground. > Meaning, wherever you are standing it has precomputed what objects, nodes, > etc. can be seen from that position. I've done it before, works fine. > > John > > -----Original Message----- > From: Charles Bloom [mailto:cb...@cb...] > Sent: Friday, August 18, 2000 12:26 PM > To: gda...@li... > Subject: [Algorithms] portal engines in outdoor environments > > > > .. is a hopeless proposition, I think. I'd just like you > guys to check my reasoning before I give up. Consider, > for example, a building placed on a landscape. The goal > is to construct portals so that when you stand on one > side of the building, you can't see the other. If the > player is constrained to stay on the ground, this is > easy enough, it's really a 2d occlusion problem, and you > need 8 portals (two * 4 faces of a square in 2d; two portals > cuz you need one on each side of a face of the square, > parrallel to that face) which splits the universe into 9 > zones (8 outside and one inside the occluding cube). > > However, if we have a plain cube in 3d and the player can > go anywhere around it, we need 48 portals !! (8 for each of > the 6 faces on the cube). Now if you have two cubes near > eachother, you need massive numbers of portals, and they > must all not intersect with eachother or other geometry. > This quickly becomes unworkable. > > I think something like a "real-time" occcluder (shadow volumes, > etc.) is the only hope for outdoors. > > -------------------------------------- > Charles Bloom www.cbloom.com > > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list |
|
From: John R. <jra...@ve...> - 2000-08-18 19:05:45
|
>>What about RAM requirements for this pre-computed list? Oh, it's not really that bad. You just keep a bitstream, where each bit represents a 'node'. Each node has a 'node-id'. When you go through your rendering pipeline, each time you hit a node you just test the node_id bit. Pretty much the same way Quake does it. It's not that much memory really, and you can always tweak your grid size. What you are looking for is gross culling anyway. If you've got a big mountain in front of you, no sense in drawing all the crap behind it. That sort of thing. >>And of course there is the inevitable question of how you compute what is visible to what node. I'd assume its done as a pre-process? Yes. In a previous engine what I did was stick a camera at a bunch of places inside the grid that would represent "a guy standing here", and then spun the camera around in all directions, rendering the entire world into a span-buffer. I then queried the span buffer for which *individual polygons* could be seen. For this new engine I have an insanely fast ray-tracer. What I intend to due is just cast rays out from the camera position to the vertex of every polygon inside the nodes I am testing against. I'm pretty sure this will work with no holes. If I get some holes, I'll just do some more samples until they go away. I don't think this is going to take that long to build either, because as soon as any ray hits, then that node is visible. My raytracer is extremely fast (because this is a massively multiplayer online game which is supposed to fit hundreds of people in a single environment firing weapons!). I wrote a class I called 'cyclops' which would generate 256 ray trace tasks every single frame out of the eyeballs of a character I moved around the environment. When the raytrace task would complete I would highlight the polygon in the world that it hit and draw a ray from his eyes to the hit location. I set the raytracer up to 2 kilometers range on a terrain of about 100k polygons. On this terrain I had dozens of very high polygon density buildings, each in their own co-ordinate space, including a two tiled polygon bridges each spanning about 500 meters. It was able to compute the solution set with virtually no noticable peformance hit. The way my raytracer and all collision detection routines work is by creating a circular cache of polygons which are being hit tested. The faces in the cache have all kinds of pre-computed information to allow for very high speed hit testing. > And do you do a full 3D solution with volumes, etc. or a 2.5D type of thing? 2 1/2 D. My game does have some low flying aircraft, but once you are up in the air you can pretty much see everything and LOD is your only hope there. John |
|
From: Joe B. <jb...@av...> - 2000-08-18 20:07:27
|
> -----Original Message-----
> From: gda...@li...
> [mailto:gda...@li...]On Behalf Of John
> Ratcliff
> Sent: Friday, August 18, 2000 1:10 PM
> To: gda...@li...
> Subject: RE: [Algorithms] portal engines in outdoor environments
>
<snip>
> What I intend to due is just cast rays out from the camera position to the
> vertex of every polygon inside the nodes I am testing against. I'm pretty
> sure this will work with no holes. If I get some holes, I'll just do some
> more samples until they go away. I don't think this is going to take that
> long to build either, because as soon as any ray hits, then that node is
> visible.
I was thinking of the same system, but ran into a problem with looking down
hallways
at large polygon walls. The eye-to-vertex algorithm tells me the wall is not
visible because I can't see its vertices. I don't know what to do about it
yet. Any ideas?
--------------- <-- Single Polygon wall (in node A)
---- ----
| |
| | <-- Hallway
| |
^
Eye (in node B)
|
|
From: John R. <jra...@ve...> - 2000-08-18 20:14:57
|
>at large polygon walls. The eye-to-vertex algorithm tells me the wall is not >visible because I can't see its vertices. I don't know what to do about it >yet. Any ideas? Send more rays. For large polygons tesselate them down to some minimum threshold size and send rays to them. John |
|
From: Mark W. <mwi...@cy...> - 2000-08-18 21:39:46
|
----- Original Message ----- From: "John Ratcliff" <jra...@ve...> To: <gda...@li...> Sent: Friday, August 18, 2000 4:19 PM Subject: RE: [Algorithms] portal engines in outdoor environments > > >at large polygon walls. The eye-to-vertex algorithm tells me the wall is > not > >visible because I can't see its vertices. I don't know what to do about it > >yet. Any ideas? > > Send more rays. For large polygons tesselate them down to some minimum > threshold size and send rays to them. > > John > Assuming all this work is done as a pre-process, wouldn't it be easier to simply render the scene and read back the frame buffer? To be more specific: 1) Assign each node some unique RGB color. 2) Render all polygons in a node using its unique RGB color. 3) Read back the frame buffer and record all unique RGB values in the image. This will give you all nodes visible from this node. The Z-Buffer will take care of eliminating any invisible nodes. 4) If you do this with 6 images/orientations (like those used to make skyboxes) you will cover the entire view. The main problem (which also exists in John's method) is that you don't know where to place the camera inside the node before you render the images or do your ray-casting. I guess you would need to repeat all this from random locations within a node to make sure you catch all possible cases. IIRC, the method I described above was used for Rogue Squadron on the N64. They used some hi-end SGI workstation to render thousands of images and analyze them to determine visibility. -Mark |
|
From: Charles B. <cb...@cb...> - 2000-08-18 22:44:42
|
Is there a fast and correct way to ask a BSP if it intersects with a primitive (AABB or sphere, for example) ? The context of this question is the traditional hack which all the BSP-based games used. They use a collision detection scheme where they take a primitive, and send it down the tree as if it were a point, but shift the BSP planes by the radius of the primitive in the direction of the plane's normal. The problem with this test is that it just doesn't work near corners where planes intersect. Many people are under the false impression that if you put extra "cap" planes on your leaves it will fix the problem, and while it certainly greatly decreases the error (because the error is roughly proportional to the angle difference of the joint, so adding more planes at a joint smooths out the error), the problem does remain. Of course, you can test an AABB against a BSP exactly by sending the polygons of the AABB down the bsp tree and doing the full polygon clipping shish-poo-bah, but that seems a rather expensive way to an AABB-in-region test. Using "cap planes" the error can be controlled, and you can make sure that the error is conservative (returns more intersections) so perhaps that's the best solution - be approximate. -------------------------------------- Charles Bloom www.cbloom.com |
|
From: Will P. <wi...@cs...> - 2000-08-18 23:04:58
|
This is a paper that supposedly deals with that issue (by plane shifting; you probably have seen it already), but I haven't read it thoroughly: http://www.cs.ualberta.ca/~melax/bsp/ In a way, I'm dealing with the same problem, because I want to do a full simulation of rigid bodies in a bsp tree based world. I don't want to pass every point down the bsp tree, but a spherical bounding volume might cull enough rigid bodies to make it okay. Will ---- Will Portnoy http://www.cs.washington.edu/homes/will On Fri, 18 Aug 2000, Charles Bloom wrote: > > Is there a fast and correct way to ask a BSP if it > intersects with a primitive (AABB or sphere, for example) ? > > The context of this question is the traditional hack > which all the BSP-based games used. They use a collision > detection scheme where they take a primitive, and send it > down the tree as if it were a point, but shift the BSP planes > by the radius of the primitive in the direction of the > plane's normal. The problem with this test is that it just > doesn't work near corners where planes intersect. Many > people are under the false impression that if you put > extra "cap" planes on your leaves it will fix the problem, > and while it certainly greatly decreases the error (because > the error is roughly proportional to the angle difference > of the joint, so adding more planes at a joint smooths out > the error), the problem does remain. > > Of course, you can test an AABB against a BSP exactly by sending > the polygons of the AABB down the bsp tree and doing the full > polygon clipping shish-poo-bah, but that seems a rather expensive > way to an AABB-in-region test. > > Using "cap planes" the error can be controlled, and you can > make sure that the error is conservative (returns more > intersections) so perhaps that's the best solution - be approximate. > > -------------------------------------- > Charles Bloom www.cbloom.com > > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > |
|
From: Charles B. <cb...@cb...> - 2000-08-18 23:31:00
|
That's a good writeup of the approximate method which I describe, where the error can be limited by bevelling corners, but never eliminated. For historical accuracy, I believe that method was known to Naylor and all the old-school BSP gurus. I heard a story that Carmack came up with the plane-shifting trick for Quake and was delighted with himself, and then one of the old computer graphics guys pointed out that they'd been doing it for years... At 04:04 PM 8/18/2000 -0700, you wrote: >This is a paper that supposedly deals with that issue (by plane shifting; >you probably have seen it already), but I haven't read it thoroughly: > >http://www.cs.ualberta.ca/~melax/bsp/ > >In a way, I'm dealing with the same problem, because I want to do a full >simulation of rigid bodies in a bsp tree based world. I don't want to >pass every point down the bsp tree, but a spherical bounding volume might >cull enough rigid bodies to make it okay. > >Will > >---- >Will Portnoy >http://www.cs.washington.edu/homes/will > >On Fri, 18 Aug 2000, Charles Bloom wrote: > >> >> Is there a fast and correct way to ask a BSP if it >> intersects with a primitive (AABB or sphere, for example) ? >> >> The context of this question is the traditional hack >> which all the BSP-based games used. They use a collision >> detection scheme where they take a primitive, and send it >> down the tree as if it were a point, but shift the BSP planes >> by the radius of the primitive in the direction of the >> plane's normal. The problem with this test is that it just >> doesn't work near corners where planes intersect. Many >> people are under the false impression that if you put >> extra "cap" planes on your leaves it will fix the problem, >> and while it certainly greatly decreases the error (because >> the error is roughly proportional to the angle difference >> of the joint, so adding more planes at a joint smooths out >> the error), the problem does remain. >> >> Of course, you can test an AABB against a BSP exactly by sending >> the polygons of the AABB down the bsp tree and doing the full >> polygon clipping shish-poo-bah, but that seems a rather expensive >> way to an AABB-in-region test. >> >> Using "cap planes" the error can be controlled, and you can >> make sure that the error is conservative (returns more >> intersections) so perhaps that's the best solution - be approximate. >> >> -------------------------------------- >> Charles Bloom www.cbloom.com >> >> >> _______________________________________________ >> GDAlgorithms-list mailing list >> GDA...@li... >> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list >> > > >_______________________________________________ >GDAlgorithms-list mailing list >GDA...@li... >http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > > -------------------------------------- Charles Bloom www.cbloom.com |
|
From: Bernd K. <bk...@lo...> - 2000-08-18 23:53:58
|
Charles Bloom writes:
> Using "cap planes" the error can be controlled, and you can
> make sure that the error is conservative (returns more
> intersections) so perhaps that's the best solution - be approximate.
I can also see benefit in decoupling rendering geometry
detail from collision geometry. Esp. with hardware T&L
you don't want the CPU to have to push the same scene
geometry. Then there's POV-dependend dynamic LOD in
multi-POV/player. If hardware support for tesselation
should hit us, it'll be even worse.
b.
|
|
From: Angel P. <ju...@bi...> - 2000-08-19 07:05:59
|
You can just test the individual polygons of the mesh ( a low
LOD representation of your model ) against the BSP tree.
It's quite fast and very simple to do.
And there's fast and easy (although not quite trivial) way to find
the intersection shape and the normals at each vertex in that
shape of the 2 colliding objects. Tell me if you need more info
on this.
You can speed this algho by first doing a quick test just with the
vertices of the mesh.
Here's the code:
bool CBSPNode::PolygonColiides( CPolygon &P )
{
CBSPNode *Node=this;
while( 1 )
{
int side = P.PlaneSide( Node->SplitPlane );
switch( side )
{
case SIDE_Front:
{
if( Node->Front==NULL )
retrun false;//no collision
Node=Node->Front;
}
case SIDE_Behind:
{
if( Node->Back==NULL )
retrun true;//collision
Node=Node->Back;
}
case SIDE_Intersect:
{
CPolygon FrontP, BackP;
P.Split( Node->SplitPlane, FrontP, BackP );
if( Node->Front!=NULL && Node->Front->PolygonCollides( FrontP ) )
return true;//collision
if( Node->Back==NULL || Node->Back->PolygonCollides( BackP ) )
return true;//collision
return false;//no collision
}
}
}
}
>
> Is there a fast and correct way to ask a BSP if it
> intersects with a primitive (AABB or sphere, for example) ?
>
> The context of this question is the traditional hack
> which all the BSP-based games used. They use a collision
> detection scheme where they take a primitive, and send it
> down the tree as if it were a point, but shift the BSP planes
> by the radius of the primitive in the direction of the
> plane's normal. The problem with this test is that it just
> doesn't work near corners where planes intersect. Many
> people are under the false impression that if you put
> extra "cap" planes on your leaves it will fix the problem,
> and while it certainly greatly decreases the error (because
> the error is roughly proportional to the angle difference
> of the joint, so adding more planes at a joint smooths out
> the error), the problem does remain.
>
> Of course, you can test an AABB against a BSP exactly by sending
> the polygons of the AABB down the bsp tree and doing the full
> polygon clipping shish-poo-bah, but that seems a rather expensive
> way to an AABB-in-region test.
>
> Using "cap planes" the error can be controlled, and you can
> make sure that the error is conservative (returns more
> intersections) so perhaps that's the best solution - be approximate.
>
> --------------------------------------
> Charles Bloom www.cbloom.com
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
|
|
From: Jaimi M. <ja...@al...> - 2000-08-18 18:19:59
|
I use a combination approach. The exteriors of buildings are always visible when you are on the grid, and Portals only link to the interiors of the buildings. When you are inside, the terrain grid is drawn last (if any portal to the outside is visible). Jaimi -----Original Message----- From: gda...@li... [mailto:gda...@li...]On Behalf Of Charles Bloom Sent: Friday, August 18, 2000 12:26 PM To: gda...@li... Subject: [Algorithms] portal engines in outdoor environments .. is a hopeless proposition, I think. I'd just like you guys to check my reasoning before I give up. Consider, for example, a building placed on a landscape. The goal is to construct portals so that when you stand on one side of the building, you can't see the other. If the player is constrained to stay on the ground, this is easy enough, it's really a 2d occlusion problem, and you need 8 portals (two * 4 faces of a square in 2d; two portals cuz you need one on each side of a face of the square, parrallel to that face) which splits the universe into 9 zones (8 outside and one inside the occluding cube). However, if we have a plain cube in 3d and the player can go anywhere around it, we need 48 portals !! (8 for each of the 6 faces on the cube). Now if you have two cubes near eachother, you need massive numbers of portals, and they must all not intersect with eachother or other geometry. This quickly becomes unworkable. I think something like a "real-time" occcluder (shadow volumes, etc.) is the only hope for outdoors. -------------------------------------- Charles Bloom www.cbloom.com _______________________________________________ GDAlgorithms-list mailing list GDA...@li... http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list |
|
From: Conor S. <cs...@tp...> - 2000-08-19 03:21:34
|
I happen to agree. I'm with John Ratcliff on this though. A precomputed system. I think I've actually come up with a decent system, that takes LoD etc into account. This is the problem with precalc'd vis on current systems. Firstly, the minimum occlusion zone after LoD, is the convex shell of the bottom of the landscape occluder. Fairly easy. I use a vertical c-buffer style implementation, with back to front sorting, similar to Fredo Durand's precalculated occlusion using extend projections (although, you could use height intersections of extreme stabbing lines). I then store the minimum height visible for each node, and make a sort of collapsed balanced binary tree, which can be sorted by height. Storage is fairly compact (each node in the tree only contains newly visible objects for that node. The ones below it are used to find the other information. The tree is split into nodes between the lowest height of the current visibility node. For 16*16 sized grid nodes per visibility node, the storage is below 100k in most instances. (Note, this method is also quickest lower to the ground, and is slightly conservative, but accurate enough). This method should do fairly well in most reasonable cases. Conor Stokes > > .. is a hopeless proposition, I think. I'd just like you > guys to check my reasoning before I give up. Consider, > for example, a building placed on a landscape. The goal > is to construct portals so that when you stand on one > side of the building, you can't see the other. If the > player is constrained to stay on the ground, this is > easy enough, it's really a 2d occlusion problem, and you > need 8 portals (two * 4 faces of a square in 2d; two portals > cuz you need one on each side of a face of the square, > parrallel to that face) which splits the universe into 9 > zones (8 outside and one inside the occluding cube). > > However, if we have a plain cube in 3d and the player can > go anywhere around it, we need 48 portals !! (8 for each of > the 6 faces on the cube). Now if you have two cubes near > eachother, you need massive numbers of portals, and they > must all not intersect with eachother or other geometry. > This quickly becomes unworkable. > > I think something like a "real-time" occcluder (shadow volumes, > etc.) is the only hope for outdoors. > > -------------------------------------- > Charles Bloom www.cbloom.com > > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > |
|
From: Angel P. <ju...@bi...> - 2000-08-19 13:33:25
|
> .. is a hopeless proposition, I think. I'd just like you > guys to check my reasoning before I give up. Consider, > for example, a building placed on a landscape. The goal > is to construct portals so that when you stand on one > side of the building, you can't see the other. If the > player is constrained to stay on the ground, this is > easy enough, it's really a 2d occlusion problem, and you > need 8 portals (two * 4 faces of a square in 2d; two portals > cuz you need one on each side of a face of the square, > parrallel to that face) which splits the universe into 9 > zones (8 outside and one inside the occluding cube). > > However, if we have a plain cube in 3d and the player can > go anywhere around it, we need 48 portals !! (8 for each of > the 6 faces on the cube). Now if you have two cubes near > eachother, you need massive numbers of portals, and they > must all not intersect with eachother or other geometry. > This quickly becomes unworkable. Actually these will be just 12 portals - 4 on the ground plane, 4 on the roof plane and 4 vertical ones. And 6 cells. The main problem with portalized outdoors is that a portal may be split into many tiny pieces while it is traversed through the other portals. Look at the first screenshot at http://thegeleto.tripod.com/sshots/ and you'll see what I mean. Consider this picture: __________________ | | | Portal A | | x1__________________ | | | | | Portal B | | _______________|_____________ | | | | | | | | Portal C | | | | | | | | | Ca | Cb | | | | | | | | |_______________|_____________| | | | | |__________________x2_________________| Portals A and B are two adjacent coplanar portals sharing same edge (x1-x2). Portal C is behind these 2 portals and is split in 2 pieces - Ca and Cb. The ordinary portal traversal algho will work like this: -- Create the frustum for portal A. -- Clip C to this frustum , crete a new frustum from the clipped portal -- Recurse further through the new frustum -- Create the frustum for portal B. -- Clip C to this frustum , crete a new frustum -- Recurse further through the new frustum The key to fixing the problem with the many splits is an algho that will work like this: -- Create the frustum for portal A : Fa -- Store the portal edge x1-x2 with the frustum Fa -- Clip C to this frustum (Fa) , crete a new frustum from the clipped portal :Fac -- Clip the stored in Fa edge x1-x2 to the new frustum (Fac) and store it in that frustum. (when clipping the case when x1-x2 lies on a plane will be considered as if it is in front of the plane ) -- DONT recurse further through the new frustum but rather store it inside C -- Create the frustum for portal B : Fb -- Store the portal edge x2-x1 with the frustum Fb -- Clip C to this frustum (Fb) , crete a new frustum from the clipped portal :Fbc -- Clip the stored in Fb edge x2-x1 to the new frustum (Fbc) and store it in that frustum. (when clipping the case when x2-x1 lies on a plane will be considered as if it is in front of the plane ) -- Clip all edges stored in Fac(currently stored inside C) to Fbc and all edges stored in Fbc to Fac (when clipping the case when an edge lies on a plane will be considered as if it is BEHIND the plane!!! ) -- If there are no edges stored in Fac and Fbc (as is in this case because they were clipped ) - try to merge Fac and Fbc (succesfully in this case) in one frustum - Fc -- Recurse further through Fc While this algho is a lot more complicated it will decrease the portal splitting in portalized outdoors quite a lot. I have not tried it yet, and there probably will be many gotchas. > I think something like a "real-time" occcluder (shadow volumes, > etc.) is the only hope for outdoors. You can use a structure of cells connected with occulders instead of portals. As you traverse the cells you can put these occulders in a beam tree after clipping them to that tree. To make things faster you can put inside the beam tree only edges shared by 2 polygons one of which is backface culled and the other isn't. At each cell the beam tree will be used to determine the visible polygons. The process ends when there are no edges left in the beam tree. It's a good optimization the remove the beam tree nodes that contain no edges (after the clipping to a new occulder these edges were removed) when possible (this will not be possible when both node->front and node->back are not NULL). So if this optimization is used - the process will end when the beam tree collapses (e.g. all nodes are deleted). This beam-tree approach can be easily combined with conventional portals. But this sounds too complicated to me and probably it won't be faster than the above portal approach. With both alghos you will have to deal with too many portals/occulders. > -------------------------------------- > Charles Bloom www.cbloom.com > > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list |
×
Want the latest updates on software, tech news, and AI?
Get latest updates about software, tech news, and AI from SourceForge directly in your inbox once a month.
Thanks for helping keep SourceForge clean.
X