Many years ago I was into the idea of using portal engines to render 3d scenes however I moved out of the games industry and never got a chance to implement some of my ideas so here are some thoughts that people may or may not have thought of before...
In a portal engine you divide space up into convex regions and then render recursively...all well known stuff. However one thing I haven't seen people do is take advantage of the fact that you don't have to embed your complete 3d scene in a larger 3d space. All you need is a transform saying how each convex region gets glued to the next. Here's an obvious example
1 is glued to 2, 2 to 3, 3 to 4 and 4 to 5. But we can also glue 5 back to one using a translation by 5 rooms. That way when we render the scene it will look like:
ie. an infinite corridor in which you see yourself.
Slightly more interesting is:
+---+---+---+ | a | ----v | +---+===+---+ | b |===| f | +---+===+---+ | c | d | e | +---+---+---+
We have what looks like a ring of 8 rooms but in fact there are only 6 it's just that f is glued to a. A player can travel round the ring through 270 degrees and get back to where they started from. Very disorienting until you know what's going on. But that's uninteresting from a rendering point of view...however if you shrink the central block down to being just a pillar there's a curious result. The net effect is that you are viewing a single room that cannot be embedded in Euclidean spacetime - reminiscent of that short movie Not Knot. If you shoot the walls to leave marks you can count you count three walls - and yet it looks patently square. If you care about game plots you can explain it by saying a singularity exists in the pillar or some such nonsense. That's not so silly - this is essentially a piecewise approximation to rendering on a curved spacetime with a curvature singularity along the pillar.
Anyway...I hope someone gets around to implementing it 'cos I want to see what it looks like and haven't time to code it myself...and maybe it's been done by someone already... -- Torque http://www.tanelorn.demon.co.uk
-----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
In article <7ded6g$9f...@nnrp1.dejanews.com>, torquem...@my-dejanews.com wrote: > Many years ago I was into the idea of using portal engines to render 3d scenes > however I moved out of the games industry and never got a chance to implement > some of my ideas so here are some thoughts that people may or may not have > thought of before...
> In a portal engine you divide space up into convex regions and then render > recursively...all well known stuff. However one thing I haven't seen people do > is take advantage of the fact that you don't have to embed your complete 3d > scene in a larger 3d space. All you need is a transform saying how each convex > region gets glued to the next. Here's an obvious example
> 1 is glued to 2, 2 to 3, 3 to 4 and 4 to 5. But we can also glue 5 back to one > using a translation by 5 rooms. That way when we render the scene it will look > like:
> ie. an infinite corridor in which you see yourself.
> Slightly more interesting is:
> +---+---+---+ > | a | ----v | > +---+===+---+ > | b |===| f | > +---+===+---+ > | c | d | e | > +---+---+---+
> We have what looks like a ring of 8 rooms but in fact there are only 6 it's > just that f is glued to a. A player can travel round the ring through 270 > degrees and get back to where they started from. Very disorienting until you > know what's going on. But that's uninteresting from a rendering point of > view...however if you shrink the central block down to being just a pillar > there's a curious result. The net effect is that you are viewing a single > room that cannot be embedded in Euclidean spacetime - reminiscent of that > short movie Not Knot. If you shoot the walls to leave marks you can count you > count three walls - and yet it looks patently square. If you care about game > plots you can explain it by saying a singularity exists in the pillar or some > such nonsense. That's not so silly - this is essentially a piecewise > approximation to rendering on a curved spacetime with a curvature singularity > along the pillar.
Marathon does this. There's one level called "5-D Space" that does something like this.
torquem...@my-dejanews.com wrote: > Many years ago I was into the idea of using portal engines to render 3d scenes > however I moved out of the games industry and never got a chance to implement > some of my ideas so here are some thoughts that people may or may not have > thought of before...
> In a portal engine you divide space up into convex regions and then render > recursively...all well known stuff. However one thing I haven't seen people do > is take advantage of the fact that you don't have to embed your complete 3d > scene in a larger 3d space. All you need is a transform saying how each convex > region gets glued to the next. Here's an obvious example
> 1 is glued to 2, 2 to 3, 3 to 4 and 4 to 5. But we can also glue 5 back to one > using a translation by 5 rooms. That way when we render the scene it will look > like:
> ie. an infinite corridor in which you see yourself.
> Slightly more interesting is:
> +---+---+---+ > | a | ----v | > +---+===+---+ > | b |===| f | > +---+===+---+ > | c | d | e | > +---+---+---+
> We have what looks like a ring of 8 rooms but in fact there are only 6 it's > just that f is glued to a. A player can travel round the ring through 270 > degrees and get back to where they started from. Very disorienting until you > know what's going on. But that's uninteresting from a rendering point of > view...however if you shrink the central block down to being just a pillar > there's a curious result. The net effect is that you are viewing a single > room that cannot be embedded in Euclidean spacetime - reminiscent of that > short movie Not Knot. If you shoot the walls to leave marks you can count you > count three walls - and yet it looks patently square. If you care about game > plots you can explain it by saying a singularity exists in the pillar or some > such nonsense. That's not so silly - this is essentially a piecewise > approximation to rendering on a curved spacetime with a curvature singularity > along the pillar.
> Anyway...I hope someone gets around to implementing it 'cos I want to see what > it looks like and haven't time to code it myself...and maybe it's been done by > someone already... > -- > Torque > http://www.tanelorn.demon.co.uk
> -----------== Posted via Deja News, The Discussion Network ==---------- > http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Been there, done that. I coded what was going to be the Prey engine for the game Prey from 3D Realms; there was an exodus of people from the team, including myself, and the engine has since been scrapped. I'm really not a big fan of portal engines anymore, especially where all rooms are relative (which is what I had) in the manner you propose. There are many ugly problems in maintaining such an engine: two rooms linked by more than one portal (which results in rendering a room twice, basically, and even though they won't overlap, all the culling and transforms are duplicated), graph maintenance with spatial discontinuities, collision detection through portals, handling sound where one sound can seem to be coming from many different locations, rendering characters moving across portals that the z-buffer won't handle correctly, etc. It wasn't fun. The effects were really awesome, though.
In hindsight, portal tricks such as these should be used as tricks, not as an engine paradigm.
In article <229832B2891B0709.768F89FFC912A7B7.80A6E7552DDBB...@library-proxy.airnews.net
>, William Scarboro <w...@airmail.net> wrote: > Been there, done that. > There are > many ugly problems in maintaining such an engine: two rooms linked by more than > one > portal (which results in rendering a room twice, basically, and even though they > won't overlap, all > the culling and transforms are duplicated)
Well there's no extra cost here. You're rendering the same room twice - yes - but in a conventional engine you'd be rendering another room anyway. You still generally see the same amount in total.
> collision detection through portals,
I know. I had a lot of trouble trying to figure out how to do this.
> handling sound where one sound can seem to be coming from many different > locations
I really don't see that this is a problem! You're basically dealing with pretty standard multiple instancing. The technique is to replace objects with the path you took to get to them (in mathematical language you work on the 'universal cover'). You have a sound source for each path.
> rendering > characters moving across portals that the z-buffer won't handle correctly
Oh yes. I know *that's* tricky. You've got to work if you want something really funky :-)
> The effects > were really awesome, though.
I'm jealous - I wish I'd seen it. Could you briefly describe some of the stuff you did?
> In hindsight, portal tricks such as these should be used as tricks, not as an > engine paradigm.
Unfortunately these kind of effects can't easily be hacked in as an afterthought. If you just want a small amount of this stuff you probably still have to build your whole engine around it. -- Torque http://travel.to/tanelorn
-----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
>Been there, done that. I coded what was going to be the Prey engine for the game >Prey >from 3D Realms; there was an exodus of people from the team, including myself, and >the engine has >since been scrapped. I'm really not a big fan of portal engines anymore, >especially >where all rooms are relative (which is what I had) in the manner you propose. >There are >many ugly problems in maintaining such an engine
[list of nasty problems snipped]
I too had a go at implementing this a while ago and the following quickly became apparent:
1) As you also found, throwing away your world coordinate system is a bad idea and you'd better have a *really* good reason to do it.
2) The real fun starts when you start using 4x4 matrices to connect cells together; mirrors, pseudo-refraction Quake3 style 'see-through teleports' and all manner of strange effects become not only easy to implement, but also trivially cheap.
3) There are a lot of nasty problems as you described but they're solvable, and there are definite benefits to having a world data-format that closely relates to the actual structure of the world (as opposed to, say, BSPs).
Interestingly, one of the major problems with portal-engines - the high CPU load required for all the clipping - disappears once you've got a stencil-buffer and it also solves a lot of problems inherent to the room-relative portal algo. A number of consumer boards already support fast stencil-buffers, and the fact that Quake3 uses them means that there's a good chance they'll be a standard feature soon...this would be *very* handy, as nowadays most 3D -accelerated engines are CPU-bound even with a high-end processor and a mid-range 3D card.
Mike F (using his mum's email account)
mike.ferendu...@infogrames.co.uk m.ferendu...@btinternet.com Please reply to one of the above, NOT the 'reply' address. E&OE
torquem...@my-dejanews.com wrote: > In article > <229832B2891B0709.768F89FFC912A7B7.80A6E7552DDBB...@library-proxy.airnews.net > >, William Scarboro <w...@airmail.net> wrote:
> > Been there, done that. > > There are > > many ugly problems in maintaining such an engine: two rooms linked by more > than > > one > > portal (which results in rendering a room twice, basically, and even though > they > > won't overlap, all > > the culling and transforms are duplicated)
> Well there's no extra cost here. You're rendering the same room twice - yes - > but in a conventional engine you'd be rendering another room anyway. You still > generally see the same amount in total.
> > collision detection through portals,
> I know. I had a lot of trouble trying to figure out how to do this.
> > handling sound where one sound can seem to be coming from many different > > locations
> I really don't see that this is a problem! You're basically dealing with > pretty standard multiple instancing. The technique is to replace objects with > the path you took to get to them (in mathematical language you work on the > 'universal cover'). You have a sound source for each path.
What is the 'universal cover'? I solved it by expressing the sound in the coordinate system of the listener, over every mathematically unique transform path that connected the sound and the listener. I solved all the problems I mentioned, but I could have encapsulated things better.
My graph handling routines needed to be more robust. I could have had more foresight in designing things.
> > In hindsight, portal tricks such as these should be used as tricks, not as an > > engine paradigm.
> Unfortunately these kind of effects can't easily be hacked in as an > afterthought. If you just want a small amount of this stuff you probably still > have to build your whole engine around it.
It depends on what level you want to take it to; for mirrors, spatial warps, and the like, those could go in pretty simply;
What I had in Prey was an entirely different beast; the entire game universe was hierarchical, meaning the entire universe was one big skeleton which could be transformed beyond belief, and I had a visual motion editing system that was righteous. Even the portals could be moved all over the place, following hierarchical spline paths, opening and closing. It was cool.
As I'm still into graphics, planning on doing stuff at home and perhaps getting back into the game industry, I may recode and restructure what I had to make it nice.
Efi Ferenduros wrote: > [list of nasty problems snipped]
> I too had a go at implementing this a while ago and the following quickly > became apparent:
> 1) As you also found, throwing away your world coordinate system is a bad > idea and you'd better have a *really* good reason to do it.
One way to keep some semblance of world space in a portal engine is to designate
a "reference room".
> 3) There are a lot of nasty problems as you described but they're solvable, > and there are definite benefits to having a world data-format that closely > relates to the actual structure of the world (as opposed to, say, BSPs).
Oh yeah, they're solvable, but your class design (in the C++ sense) has to be exceptional, or else you'll have special-case portal code all over the place. Collision detection is especially nasty.
> Interestingly, one of the major problems with portal-engines - the high CPU > load required for all the clipping - disappears once you've got a > stencil-buffer and it also solves a lot of problems inherent to the > room-relative portal algo. > A number of consumer boards already support fast stencil-buffers, and the > fact that Quake3 uses them means that there's a good chance they'll be a > standard feature soon...this would be *very* handy, as nowadays most > 3D -accelerated engines are CPU-bound even with a high-end processor and a > mid-range 3D card.
I didn't have clipping issues, because I clipped to the screen-space bounding box of the portal, and this method scales nicely to APIs (OpenGL, etc). The time that it would have been nice having a stencil buffer is when z-buffering doesn't sort things correctly, i.e,. a mirror floating in the middle of space. I solved it using some wacky z-buffer tricks, but it was pretty painful. I had this amorphous blob portal effect which required six passes: in essence, the portal was defined by an animating texture.
> Mike F (using his mum's email account)
> mike.ferendu...@infogrames.co.uk > m.ferendu...@btinternet.com > Please reply to one of the above, NOT the 'reply' address. > E&OE
In article <FD056165B785F288.BD890B18A43A8EC7.3C8B9691755EE...@library-proxy.airnews.net
>, William Scarboro <w...@airmail.net> wrote: > What is the 'universal cover'? I solved it by expressing the sound in the > coordinate system of the listener, over every mathematically unique > transform path that connected the sound and the listener.
You've basically figured out what the universal cover is. 'Universal cover' is the standard mathematical terminology that's already used by topologists for this sort of thing. The universal cover of the corridor with ends identified, for example, is the universal cover. Crudely the universal cover is what the world looks like to someone who's too stupid to realise they've come back to the same point that they were at before.
> It depends on what level you want to take it to; for mirrors, spatial warps, and > the like, > those could go in pretty simply;
And Alice-in-Wonderland/SuperMario64 type corridors which make you change size as you travel or look through them (I guess you should look at the determinant of the total transform along the path to an instance so that you can make small instances of things quieter and higher pitched :-). You can build spaces with interesting topologies - the 3D equivalent of the mobius strip or even the space of 3D rotations (You know the way that an x rotation is the same as an x+2*pi rotation so it's like a sphere with corridors going out and joining back onto the direct opposite side of the sphere).
> As I'm still into graphics, planning on doing stuff at home and perhaps getting > back into the game > industry, I may recode and restructure what I had to make it nice.
>I didn't have clipping issues, because I clipped to the screen-space bounding >box of >the portal, and this method scales nicely to APIs (OpenGL, etc). The time that >it >would have been nice having a stencil buffer is when z-buffering doesn't sort >things >correctly, i.e,. a mirror floating in the middle of space. solved it using >some >wacky z-buffer tricks, but it was pretty painful. I had this amorphous blob >portal effect which required six passes: in essence, the portal was defined by >an >animating texture.
I'm intrigued....Can you explain more or is it classified? I'm about to embark on a game engine so I can't guarantee I won't steal your ideas ;)
Mike F (using his mum's email account)
mike.ferendu...@infogrames.co.uk m.ferendu...@btinternet.com Please reply to one of the above, NOT the 'reply' address. E&OE
Hello There is!! Partition you're space into cells and get the list of polygons visible from anywhere inside the cell. This way you have a defined list of potentially visible polygons. You can also use portals to eliminate further polygons if needed i.e. you define what polygons are visible through a portal, If the portal is not visible onscreen then remove the portal's polygon list from the cell's rendering lists. have fun.... Anth
>I got some questions. I wrote a 3d portal based engine and editor. I use >cubes, spheres and so on. The editor then splits all the objects in convex >hulls and it works just fine. In a scene I have 3 cubes and the whole scene >gets splitted in 19 convex hulls. When it gets rendered it renders 25 hulls >(some of them get more then one time rendered) and get only 10 fps without >drawing the rendered scene. It's just the loop. I optimized a lot. There is >almost nothing to optimize anymore. Is there a trick? How come portal games >get 20-16 fps? Do they use convex hulls with bsp in hulls like Crystal Space >does? I also buffered the 2d polygons of of the 3d surfaces and the >transformation from world to aligned of the sectors. The slow part would be >the 2d clipping. I made a test and the average is 0.66 ms for two polygons >that get intersected and have up to 10 edges. Oh yes and i use for 2d >clipping the hodging ( and something) algorithm. Is there something faster >than the above named algorithm? How many fps does CS reach with 25 sectors?
>Tnx. >Darx_Kies.
>-----------== Posted via Deja News, The Discussion Network ==---------- >http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
I got some questions. I wrote a 3d portal based engine and editor. I use cubes, spheres and so on. The editor then splits all the objects in convex hulls and it works just fine. In a scene I have 3 cubes and the whole scene gets splitted in 19 convex hulls. When it gets rendered it renders 25 hulls (some of them get more then one time rendered) and get only 10 fps without drawing the rendered scene. It's just the loop. I optimized a lot. There is almost nothing to optimize anymore. Is there a trick? How come portal games get 20-16 fps? Do they use convex hulls with bsp in hulls like Crystal Space does? I also buffered the 2d polygons of of the 3d surfaces and the transformation from world to aligned of the sectors. The slow part would be the 2d clipping. I made a test and the average is 0.66 ms for two polygons that get intersected and have up to 10 edges. Oh yes and i use for 2d clipping the hodging ( and something) algorithm. Is there something faster than the above named algorithm? How many fps does CS reach with 25 sectors?
Tnx. Darx_Kies.
-----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
> >Been there, done that. I coded what was going to be the Prey engine for the > game > >Prey > >from 3D Realms; there was an exodus of people from the team, including > myself, and > >the engine has > >since been scrapped. I'm really not a big fan of portal engines anymore, > >especially > >where all rooms are relative (which is what I had) in the manner you > propose. > >There are > >many ugly problems in maintaining such an engine
> [list of nasty problems snipped]
> I too had a go at implementing this a while ago and the following quickly > became apparent:
> 1) As you also found, throwing away your world coordinate system is a bad > idea and you'd better have a *really* good reason to do it.
> 2) The real fun starts when you start using 4x4 matrices to connect cells > together; mirrors, pseudo-refraction Quake3 style 'see-through teleports' > and all manner of strange effects become not only easy to implement, but > also trivially cheap.
> 3) There are a lot of nasty problems as you described but they're solvable, > and there are definite benefits to having a world data-format that closely > relates to the actual structure of the world (as opposed to, say, BSPs).
> Interestingly, one of the major problems with portal-engines - the high CPU > load required for all the clipping - disappears once you've got a > stencil-buffer and it also solves a lot of problems inherent to the > room-relative portal algo. > A number of consumer boards already support fast stencil-buffers, and the > fact that Quake3 uses them means that there's a good chance they'll be a > standard feature soon...this would be *very* handy, as nowadays most > 3D -accelerated engines are CPU-bound even with a high-end processor and a > mid-range 3D card.
Would you be that kind and explain me what are stencil buffers about? Where can I get more infos on that subject.
Darx Kies.
-----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
> In article <7dgg1v$35...@plutonium.btinternet.com>, > "Efi Ferenduros" <E...@btinternet.com> wrote: > > >Been there, done that. I coded what was going to be the Prey engine for the > > game > > >Prey > > >from 3D Realms; there was an exodus of people from the team, including > > myself, and > > >the engine has > > >since been scrapped. I'm really not a big fan of portal engines anymore, > > >especially > > >where all rooms are relative (which is what I had) in the manner you > > propose. > > >There are > > >many ugly problems in maintaining such an engine
> > [list of nasty problems snipped]
> > I too had a go at implementing this a while ago and the following quickly > > became apparent:
> > 1) As you also found, throwing away your world coordinate system is a bad > > idea and you'd better have a *really* good reason to do it.
> > 2) The real fun starts when you start using 4x4 matrices to connect cells > > together; mirrors, pseudo-refraction Quake3 style 'see-through teleports' > > and all manner of strange effects become not only easy to implement, but > > also trivially cheap.
> > 3) There are a lot of nasty problems as you described but they're solvable, > > and there are definite benefits to having a world data-format that closely > > relates to the actual structure of the world (as opposed to, say, BSPs).
> > Interestingly, one of the major problems with portal-engines - the high CPU > > load required for all the clipping - disappears once you've got a > > stencil-buffer and it also solves a lot of problems inherent to the > > room-relative portal algo. > > A number of consumer boards already support fast stencil-buffers, and the > > fact that Quake3 uses them means that there's a good chance they'll be a > > standard feature soon...this would be *very* handy, as nowadays most > > 3D -accelerated engines are CPU-bound even with a high-end processor and a > > mid-range 3D card.
> Would you be that kind and explain me what are stencil buffers about? Where > can I get more infos on that subject.
> Darx Kies.
> -----------== Posted via Deja News, The Discussion Network ==---------- > http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Darx_Kies <darx_k...@my-dejanews.com> wrote: >I got some questions. I wrote a 3d portal based engine and editor. I use >cubes, spheres and so on. The editor then splits all the objects in convex >hulls and it works just fine. In a scene I have 3 cubes and the whole scene >gets splitted in 19 convex hulls. When it gets rendered it renders 25 hulls >(some of them get more then one time rendered) and get only 10 fps without >drawing the rendered scene. It's just the loop. I optimized a lot. There is >almost nothing to optimize anymore. Is there a trick? How come portal games >get 20-16 fps? Do they use convex hulls with bsp in hulls like Crystal Space >does? I also buffered the 2d polygons of of the 3d surfaces and the >transformation from world to aligned of the sectors. The slow part would be >the 2d clipping. I made a test and the average is 0.66 ms for two polygons >that get intersected and have up to 10 edges. Oh yes and i use for 2d >clipping the hodging ( and something) algorithm. Is there something faster >than the above named algorithm? How many fps does CS reach with 25 sectors?
From your own description, your clipping sounds incredibly slow. Let's say your machine runs at 200 MHz. 0.66 ms on a 200 MHz machine is 132,000 cycles. Even if your clipper clips (or clip tests) all 10 edges of one polygon against all 10 edges of another, that's 1,320 cycles per edge; more if your machine is a faster one. What are you doing that takes that many cycles?
> >I got some questions. I wrote a 3d portal based engine and editor. I use > >cubes, spheres and so on. The editor then splits all the objects in convex > >hulls and it works just fine. In a scene I have 3 cubes and the whole scene > >gets splitted in 19 convex hulls. When it gets rendered it renders 25 hulls > >(some of them get more then one time rendered) and get only 10 fps without > >drawing the rendered scene. It's just the loop. I optimized a lot. There is > >almost nothing to optimize anymore. Is there a trick? How come portal games > >get 20-16 fps? Do they use convex hulls with bsp in hulls like Crystal Space > >does? I also buffered the 2d polygons of of the 3d surfaces and the > >transformation from world to aligned of the sectors. The slow part would be > >the 2d clipping. I made a test and the average is 0.66 ms for two polygons > >that get intersected and have up to 10 edges. Oh yes and i use for 2d > >clipping the hodging ( and something) algorithm. Is there something faster > >than the above named algorithm? How many fps does CS reach with 25 sectors?
> From your own description, your clipping sounds incredibly slow. Let's say > your machine runs at 200 MHz. 0.66 ms on a 200 MHz machine is 132,000 > cycles. Even if your clipper clips (or clip tests) all 10 edges of one > polygon against all 10 edges of another, that's 1,320 cycles per edge; more > if your machine is a faster one. What are you doing that takes that many > cycles?
Good question. I have no idea. I use a p200 MMX. The clipping routine is really optimized. For example it dumps all the edges that are too small, copies the left edges if there are two intersections or dumps them if the second end is outside of the poly.
Darx Kies.
BTW: Unreal doesn't render more than 5 sectors at once and it uses BSP trees in sectors. And I have no idea how to reject the portals that are let's say behind a wall. Unreal does it but I have no idea how.
I mean:
+-------------+----+-------------------------+ | (Portal) | | | (Sector) | *==========================* (Wall) | | | | # (Viewer) | +--------------------------------------------+ How do you know that you have to reject the portal behind the wall?
-----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
