Portal Engines
torqu...@my-dejanews.com
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 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+
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:
-+---+---+---+---+---+---+---+-
... | 1 | 2 | 3 | 4 | 5 | 1 | 2 | ...
-+---+---+---+---+---+---+---+-
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
Rob Barris
Marathon does this. There's one level called "5-D Space" that does
something like this.
Rob
William Scarboro
torqu...@my-dejanews.com wrote:
> 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.
William Scarboro
torqu...@my-dejanews.com
<229832B2891B0709.768F89FF...@library-proxy.airnews.net
>, William Scarboro <wa...@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
Efi Ferenduros
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.
>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.fe...@infogrames.co.uk
m.fere...@btinternet.com
Please reply to one of the above, NOT the 'reply' address.
E&OE
William Scarboro
torqu...@my-dejanews.com wrote:
> In article
> <229832B2891B0709.768F89FF...@library-proxy.airnews.net
> >, William Scarboro <wa...@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.
> --
> Torque
> http://travel.to/tanelorn
>
> -----------== Posted via Deja News, The Discussion Network ==----------
> http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
William Scarboro
William Scarboro
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.fe...@infogrames.co.uk
> m.fere...@btinternet.com
> Please reply to one of the above, NOT the 'reply' address.
> E&OE
William Scarboro
torqu...@my-dejanews.com
<FD056165B785F288.BD890B18...@library-proxy.airnews.net
>, William Scarboro <wa...@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.
Tell me if you do!
Efi Ferenduros
William Scarboro wrote in message ...
[snip]
>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 ;)
anthony crawley
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
darx...@my-dejanews.com wrote in message
<7efcqd$psb$1...@nnrp1.dejanews.com>...
>Hi...
>
>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.
darx...@my-dejanews.com
darx...@my-dejanews.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.
> >many ugly problems in maintaining such an engine
>
>
> 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.
>
> 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.
>
> 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).
>
> 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.
Bernie Freidin
rendering (being used to 3Dfx, stencil buffers are new to me).
Bernie Freidin
(bfre...@hampshire.edu)
<darx...@my-dejanews.com> wrote in message
news:7efcss$psj$1...@nnrp1.dejanews.com...
Kekoa Proudfoot
>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?
-Kekoa
darx...@my-dejanews.com
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?
l0r3n...@gmail.com
I've tried the Prey demo many years ago.