Copy Link
Add to Bookmark
Report
Quake Editing Digest Volume 1 : Number 12
quake-editing-digest Tuesday, 19 March 1996 Volume 01 : Number 012
Rendering Quake surfaces
Re: WAD Conversion sketch
Re: WAD Conversion sketch
Re: WAD conversion sketch
Re: WAD Conversion sketch
Re: WAD conversion sketch
Legal stuff (was Re: WAD conversion sketch)
Visibility Lists
Re: Visibility Lists
Legal issues (was: WAD conversion sketch)
Re: Legal stuff (was Re: WAD conversion sketch)
Re: Legal stuff (was Re: WAD conversion sketch)
Re: WAD Conversion sketch
----------------------------------------------------------------------
From: etherton@netcom.com (David Etherton)
Date: Sun, 17 Mar 1996 20:47:17 -0800
Subject: Rendering Quake surfaces
[Please forgive me if this is asked a lot, I can't get through to
the mail archives on http://www.nero.uni-bonn.de/~dn/qd/qd_welcome.html
right now]
Like just about everybody else around here, I've been playing around
with trying to render the Quake levels. The Quake specs (3.0) have
proved invaluable.
First, in the List of Edges, if the sign bit of the edge is set, are
we supposed to look at edge ~i or -i? (Nodes use ~i to mark leaves
according to both the spec and my own experience). For the List of
Edges, though, neither ~i nor -i seem to work particularly well,
although -i seems to work slightly better.
I can traverse the BSP tree and find the leaf containing my camera
position correctly, so I know I've got the basics right. However,
when I try to render, I find that the list of surfaces often
tells me to (say) render surface 7 three times in a row, and that
it's got 30 edges in the surface.
Surfaces with small numbers of edges seem to "connect" together well
(ie the end vertex of one edge is the start vertex of the next, and
it forms a closed figure). Some surfaces with larger numbers of
edges seem to form closed figures if you sort the edges after
reading them in, but surfaces with 16 or more edges seem to not
form closed figures.
I can't imagine a fast renderer wanting to deal with anything larger
than a tri or a quad, so I'm suspicious of anything with more than
four edges. Combined with my experience with surfaces with large
numbers of edges having nonsensical edge lists, I wonder if we're
supposed to interpret the edge count differently if it's above
a certain value.
Also, why would the list of surfaces explicitly tell me to render
the same surface two or three times in a row? I haven't done an
exhaustive check, but it appears that every time a surface is
supposed to render several times in a row, it usually also has
a large number of edges.
Am I totally off in the weeds here or is anybody else fighting
the same things I am?
- -David Etherton
ps. For what it's worth, I have been able to parse and render the
models perfectly; either a Z-buffer or a bucket Z-sort seems
to produce good results; the latter has some slight defects
(ever seen a PlayStation?) but is *much* faster on both my
PC and my SparcStation
------------------------------
From: Uffe Friis Lichtenberg <uffefl@diku.dk>
Date: Mon, 18 Mar 1996 11:47:35 +0100 (MET)
Subject: Re: WAD Conversion sketch
On Sat, 16 Mar 1996, Bernd Kreimeier wrote:
> I thought again about the recent discussion of the
> possibility of a WAD conversion, and I recognized that
> I forgot one important detail. IMO the 2D BSP and a
> REJECT lump w/o special effects contains all information
> necessary to create a valid Quake BSP.
>
> We do not need a new BSP/REJECT builder for conversion.
Well, I tend to disagree. You do need additional information, as you
say in your 'WAD conversions sketch', like plane-bundling (trivial),
vertices (trivial), hull generation (not so trivial?), etc. But firstly
you do need a 3D BSP tree: remember all the floors and ceilings are
planes in Quake, and must thus partition the rest of the polygons in some
way. This could lead to a number of problems if not handled right.
My guess is that wad conversion would be easiest to implement if you had
two utilities: one to convert a wad to an intermediate file format
(perhaps the same used to distribute Quake levels) specifying polygons
(with textures) and entities, and another tool to build a valid .BSP from
this file format (ie. a 3D BSP generator, as well as texture reference
resolving and so on.)
Having it split up into two utilities would also make .DXF ->
intermediate file format, .3DS -> intermediate file format, etc. a lot
easier to manage, as we would be able to use all sorts of excellent 3D
editors already available to edit Quake levels, and let the second
utility to all the hard work afterwards.
But of course, it wouldn't be trivial to create a utility that builds an
efficient BSP tree. But it wouldn't be any more difficult than doing it
in 2D was.
> Any such converted map will still have only one floor
> and ceiling per z coordinate, or BSP and REJECT would not
> be sufficient for conversion. Nonetheless, the advantages
> seem to be worth the effort.
But where do you find wads that fulfil this requirement? I can't think of
a single one. (If I understand you right.)
> I refrained from posting a lengthy but still sketchy
> proposal to the list. If you are interested, you will
> find a pointer on the Quake Developers Support page,
> at
>
> http://www.nero.uni-bonn.de/~dn/q-sup/
Regarding the legal issues:
Maybe iD's licence doesn't explicitly forbid the creation/distribution of
add-on levels for Quake, but personally I feel that we should respect
iD's work and not bring out any fully-fledged editor before the
registered version becomes available. But perhaps I'm alone in this?
Zonk,
Uffe. [uphfe]
uffefl@diku.dk
------------------------------
From: "Brian K. Martin" <brian@phyast.pitt.edu>
Date: Mon, 18 Mar 1996 07:53:25 -0500 (EST)
Subject: Re: WAD Conversion sketch
>
> On Sat, 16 Mar 1996, Bernd Kreimeier wrote:
>
> Regarding the legal issues:
>
> Maybe iD's licence doesn't explicitly forbid the creation/distribution of
> add-on levels for Quake, but personally I feel that we should respect
> iD's work and not bring out any fully-fledged editor before the
> registered version becomes available. But perhaps I'm alone in this?
>
I agree. I was upset to see complete levels and mdl files uploaded
to ftp and net sites. I think the level/model editors should not
work with the shareware release, unless id gives an ok. I will
most likely hold back the next version of meddle because of this.
brian
------------------------------
From: Bernd Kreimeier <Bernd.Kreimeier@NeRo.Uni-Bonn.DE>
Date: Mon, 18 Mar 1996 14:23:42 +0100 (MET)
Subject: Re: WAD conversion sketch
I try to separate the legal issues thread from the more
technical aspects. It is a futile discussion anyway.
There is only one way to resolve this, namely a request
from id Software. You might want to ask them.
> Legal issues: not bring out any useful tools prior to
> registered release.
This is a slightly difficult issue. I have no intention
to end discussion of such topics, which is a far cry from a
public production release of anything. After all, we might
as well shutdown this list for a few months if we all
agree to wait for registered Quake.
> tools should not work with shareware release
In this case we could as well abandon any discussion
of distribution file formats, and DMADDS/DeuSF-style
or pack/unpack tools source distribution. It has always
been possible to create a replacement IWAD because id
decided to distribute the same EXE as shareware,
registered, and commercial. The qtest1 seems to indicate
that this will not change, which is a bad thing.
b.
------------------------------
From: Bernd Kreimeier <Bernd.Kreimeier@NeRo.Uni-Bonn.DE>
Date: Mon, 18 Mar 1996 14:35:18 +0100 (MET)
Subject: Re: WAD Conversion sketch
>From: Uffe Friis Lichtenberg <uffefl@diku.dk>
>additional info need, namely convex hulls
Has anybody verified that a Slab BSP tree is needed, or might
it be easily omitted with a zero length entry? If there is
only one Slab, does it have to be a convex hull, or is a
bounding box sufficient?
>we do need a 3D BSP tree
If I am not mistaken, you could simply copy the 2D BSP into
a matching 3D BSP, and convert the information from the old
NODES and SSECTORS. Think about it.
>the floors and ceilings are planes and have to be partitioned
You are perfectly right. In fact, this might be the most
difficult task to solve. It breaks down to creating closed
polygons from SECTORS and LINEDEFS for each floor (ceilings
will have the same partitions), and using the 2D BSP NODES
info (namely the partition lines) to split the SECTORS'
polygon into the Leaf2D surfaces. I already added this
to the proposal.
>misc. remarks on conversion, DXF, intermediate file formats
All very true. However, I am skeptical that any file format
not done by id will ever be agreed upon. Anybody remember the
porposal by Tom Neff (WAD Interchange Format)?
>>The WAD will have to have only one floor/ceiling per xy plane,
>>i.e. the DOOM world geometry restrictions
>But where do you find wads that fulfil this requirement?
Hmmm? Any WAD that can be used with DOOM does :-).
b.
------------------------------
From: Bernd Kreimeier <Bernd.Kreimeier@NeRo.Uni-Bonn.DE>
Date: Mon, 18 Mar 1996 15:03:43 +0100 (MET)
Subject: Re: WAD conversion sketch
I updated the proposal at
http://www.nero.uni-bonn.de/~dn/q-sup/
and added some details I omitted in the first draft. It is
still sketchy.
Here are some important aspects:
A modified DOOM BSP Node builder might be a better solution,
instead of a completely separate conversion tool. I would
appreciate any comment from those on the list who have
actually written such a tool.
Automatic conversion and DOOM map recycling is no worthwhile
reason to create such a tool. Texture, door, switch issues
will make any such attempt futile. Any given WAD map will
not be playable, and look worse. What's the point of DOOM
restricted geometry in Quake anyway?
The DOOM WAD file format provides a commonly accepted
intermediate file format. We could start there, and might
even agree on how it should be extended.
Any DOOM map editor could be modified along with a
qbsp/BSP_3D Node builder to take into account different
texture handling, different entities. This is a migration
path.
Put quite simply: if there were a 3D editor, full specs,
and a working node builder guaranteed, I wouldn't waste
a single thought. Right now, this project is quite
educational in several regards.
b.
------------------------------
From: Raphael.Quinet@eed.ericsson.se
Date: Mon, 18 Mar 1996 15:32:56 +0100 (MET)
Subject: Legal stuff (was Re: WAD conversion sketch)
On Mon, 18 Mar 1996, Bernd Kreimeier <Bernd.Kreimeier@NeRo.Uni-Bonn.DE> wrote:
> I try to separate the legal issues thread from the more
> technical aspects. [...]
I changed the subject, so that it is more obvious...
> > tools should not work with shareware release
>
> In this case we could as well abandon any discussion
> of distribution file formats, and DMADDS/DeuSF-style
> or pack/unpack tools source distribution.
As long as the full-featured editors do not allow you to edit the
shareware game, it should be OK. The current tools are far from being
"full-featured". I don't think that small tools would really harm id
Software, if they work with the shareware game. Besides, it would be
too much trouble for some of these small tools to check if the user
has the registered game.
Here is what I am planning to do for QEU: I will probably split the
code in three parts. There will be the GUI library (SWAPI), the
routines for handling Quake files as well as the files for other games
such as Doom (I will probably call this part "GEL", for "Game Editing
Library") and the programs themselves: the editor and the tools that
are currently in QEU 0.3.
The first two parts (SWAPI and GEL) will work with the shareware
version of the game. The GUI library is independent of the game and I
am planning to use it for other programs, so it is normal that it
doesn't check for a registered version of anything. The Game Editing
Library (or whatever it is called - suggestions are welcome) will also
work with the shareware game(s) because it contains mostly low-level
functions for loading and saving file related to various games. These
routines don't know much about the high-level structures or the
contents of the PACK file and they should be independant of the
version of the game being loaded or saved.
The editor will check for the registered version, because this is the
only part of the code which will know the meaning of the various parts
of the PACK file (or BSP files). Thus it will be able to check if the
PACK file contains some entries that are only available in the
registered game.
By the way, I intend to release the first two parts (SWAPI and GEL)
under a non-restrictive license so that anyone can copy, modify or
distribute this code. The editor and tools will also be free and the
source code will be available, but I will restrict commercial
distribution and encourage people to contribute to the main code
instead of distributing modified versions.
> It has always
> been possible to create a replacement IWAD because id
> decided to distribute the same EXE as shareware,
> registered, and commercial. The qtest1 seems to indicate
> that this will not change, which is a bad thing.
I'm not sure if it is a bad thing. Maintaining two different EXE's
would mean more work for id Software (creating the two versions,
supporting them, etc.). They cannot simply create a shareware EXE
which differs only by a few bytes (i.e. a hard-coded flag), because
some cracker would certainly post a patch to enable all the disabled
features. Also, it is easier to pirate and distribute a single EXE
file than to copy the whole CD-ROM, so a different EXE wouldn't
protect id Software for a long time.
If all editors are fair (towards id Software) and refuse to work with
the shareware version, I think this will be enough. Some of them will
be distributed as source code (such as QEU for Quake or DEU for Doom),
so it would theoretically be possible for someone to patch them so
that they work with the shareware game. However, someone who takes
the time to go through the whole source code and track the various
tests that have been scattered in the code by the author of the
program would probably find it easier to get a pirate copy of the
game, so I don't think this is a real problem. Of course, I assume
that the authors of the editors include more than one test which
checks if the user has a registered version of the game.
- -Raphael
------------------------------
From: etherton@megatek.com (David Etherton)
Date: Mon, 18 Mar 1996 09:11:28 +0800
Subject: Visibility Lists
When trying to determine which leaves are visible from a current
leaf, one looks at the vislist memory of the leaf data structure.
However, it's not clear to me which of the following two
formulas is correct:
int i; // leaf number to check
u_char *vp = start_of_vislist + leaf->vislist
if (vp[i>>3] & (1<<(i&7))) { puts("is visibile"); }
- - or -
if (vp[i>>3] & (128>>(i&7))) { puts("is visibile"); }
My renderer isn't far enough along that I can readily tell;
the obvious solution would be to play with the bits and
run it through quake itself, but id didn't distribute a
Sparc version of quake yet :(.
My guess is that the first formula is correct, but I suspect
there's something weird with the visibility lists because
I had assumed (hoped) that for any leaf i, its own visibility
bit is set in its visbility list. This would seem to make
sense to me because (barring special effects), two adjacent
leaves may very well have the exact same visibility lists,
so they could share the list.
Unfortunately, while test1.bsp and test2.bsp both have
starting positions in leaves that can "see" themselves,
test3.bsp does not.
Any comments? Obviously my own implementation could be at
fault and I'm wondering if anybody else is having similar
problems.
On another topic [as a bonus if you've actually read this far :)],
I've found that augmenting the node structures with backpointers
to their parents (after reading in the map) might prove useful
for optimizing rendering. In order to render from a specific
position, I'm doing the following:
- Traverse the bsp tree to find which leaf the camera is in,
caching the result so that I can do a quick bbox check the
next time to see if I'm in the same leaf.
- See if the current leaf has the same visibility list (ie offset)
as our cached result.
- If it does not, scan the visibility list, and for each leaf
which is visible, mark the leaf as needing to be rendered,
then mark its parent node as needing to be visited, and
then mark *that* parent's node, and so on, until we either
hit the root of the tree or hit a node that's already marked
for visitation.
- Start traversing the tree at the top.
- If neither child node needs to be visited, stop.
- If only one child node needs to be visited, only visit that
child.
- If both children need to be visited, then and only then test
the camera position against the node's split plane to see
which child needs to be visited first.
We can also project the bounding box of a node or leaf into the
view frustum to see if we can trivially reject the entire subtree
(off the side, or behind the viewer) before visiting it as well.
- -David Etherton
------------------------------
From: etherton@megatek.com (David Etherton)
Date: Mon, 18 Mar 1996 09:46:28 -0800 (PST)
Subject: Re: Visibility Lists
Here's a data dump from test1.bsp:
VISILIST SIZE 14039
494 total leaves, 1068 total nodes
leaf 0: visoffs=0 {0 bits since last}
leaf 1: visoffs=0 {0 bits since last}
leaf 2: visoffs=29 {232 bits since last}
leaf 3: visoffs=54 {200 bits since last}
leaf 4: visoffs=76 {176 bits since last}
leaf 5: visoffs=102 {208 bits since last}
leaf 6: visoffs=125 {184 bits since last}
leaf 7: visoffs=148 {184 bits since last}
leaf 8: visoffs=171 {184 bits since last}
leaf 9: visoffs=197 {208 bits since last}
leaf 10: visoffs=223 {208 bits since last}
leaf 11: visoffs=246 {184 bits since last}
leaf 12: visoffs=272 {208 bits since last}
leaf 13: visoffs=298 {208 bits since last}
leaf 14: visoffs=321 {184 bits since last}
leaf 15: visoffs=344 {184 bits since last}
leaf 16: visoffs=370 {208 bits since last}
leaf 17: visoffs=393 {184 bits since last}
leaf 18: visoffs=416 {184 bits since last}
leaf 19: visoffs=442 {208 bits since last}
leaf 20: visoffs=468 {208 bits since last}
leaf 21: visoffs=494 {208 bits since last}
leaf 22: visoffs=520 {208 bits since last}
....
I suspect there's something weird about the visibility lists.
While all of the offsets are within the boundaries of the
visibility list, and some of the lists do run off the end
of the end of the lump, I find the fact that all of the
visibility lists overlap is rather disturbing. I can't
see how sharing the same bit pattern between multiple visibility
lists could ever be useful.
I suspect that there's an offset and length field that we don't
know about yet which would allow us to say that all leaves not
in a specified range are either visible or invisible; leaves
within the specified range check the visibility bitmask.
Also, several of the later leaves have a visibility offset
of -1; does that mean no other leaves are visible from here
or all other leaves are visible from here?
- -David
- --
David Etherton | Megatek Corporation | "Shop as usual, and avoid panic buying."
------------------------------
From: Uffe Friis Lichtenberg <uffefl@diku.dk>
Date: Mon, 18 Mar 1996 19:17:14 +0100 (MET)
Subject: Legal issues (was: WAD conversion sketch)
On Mon, 18 Mar 1996, Bernd Kreimeier wrote:
> You might want to ask them.
I don't think there could be any other answer than 'no, please don't make
editors available for anything other than the registered version', but of
course I could be wrong.
> > Legal issues: not bring out any useful tools prior to
> > registered release.
>
> This is a slightly difficult issue. I have no intention
> to end discussion of such topics, which is a far cry from a
> public production release of anything. After all, we might
> as well shutdown this list for a few months if we all
> agree to wait for registered Quake.
No no. There is IMO a BIG difference between discussing Quake
hacking/editing and releasing small utils to demonstrate the concepts,
and releasing fully-fledged software to modify Quake with (ie. hacking
tools vs. end-user products.)
I can't see any harm in the discussion or release of viewers/small
editors/file format converters/etc. as long as they are not "marketed" as
Quake-editors.
BTW: until a Quake non-test version comes out this is all we have to play
around with anyway, so there's no need trying to stop us now :)
> > tools should not work with shareware release
>
> In this case we could as well abandon any discussion
> of distribution file formats, and DMADDS/DeuSF-style
> or pack/unpack tools source distribution.
Well, it's a bit hard to speculate on that until the shareware finally
hits the net.
Zonk,
Uffe. [uphfe]
uffefl@diku.dk
------------------------------
From: Uffe Friis Lichtenberg <uffefl@diku.dk>
Date: Mon, 18 Mar 1996 19:29:55 +0100 (MET)
Subject: Re: Legal stuff (was Re: WAD conversion sketch)
On Mon, 18 Mar 1996 Raphael.Quinet@eed.ericsson.se wrote:
> As long as the full-featured editors do not allow you to edit the
> shareware game, it should be OK. The current tools are far from being
> "full-featured".
Agreed.
> I don't think that small tools would really harm id
> Software, if they work with the shareware game.
Dunno about that. Perhaps a message in these small tools that simply
states "Will Not Work With The Shareware" (or something similar) would be
sufficient, even though they might actually work?
> The editor will check for the registered version, because this is the
> only part of the code which will know the meaning of the various parts
> of the PACK file (or BSP files). Thus it will be able to check if the
> PACK file contains some entries that are only available in the
> registered game.
This is of course assuming that iD will choose a strategy similar to Doom
with the registered contra shareware versions.
> I'm not sure if it is a bad thing. Maintaining two different EXE's
> would mean more work for id Software (creating the two versions,
> supporting them, etc.). They cannot simply create a shareware EXE
> which differs only by a few bytes (i.e. a hard-coded flag), because
> some cracker would certainly post a patch to enable all the disabled
> features. Also, it is easier to pirate and distribute a single EXE
> file than to copy the whole CD-ROM, so a different EXE wouldn't
> protect id Software for a long time.
I don't think it would be difficult for iD to do separate compiles
(perhaps with a -DSHAREWARE for the shareware version) that actually
makes two very different exes. But the discussion is futile anyway:
pirates will circumvent anything iD can throw at them, so iD are probably
better off directing their energy towards the game engine.
> Of course, I assume
> that the authors of the editors include more than one test which
> checks if the user has a registered version of the game.
Can't see the problem here. If there is just a single test the author of
the editor can't take responsibility for modified versions of the editor.
Again, pirates circumvent just about anything, and wasting time on
copy-protection is useless.
Just make the test so an ordinary user wouldn't be able to circumvent it.
Zonk,
Uffe. [uphfe]
uffefl@diku.dk
------------------------------
From: "Michael G. Clawson" <clawsonm@nsc2.gordon.army.mil>
Date: Mon, 18 Mar 96 17:07:29 EST
Subject: Re: Legal stuff (was Re: WAD conversion sketch)
In reply to 18 Mar message from quake-editing@nvg.unit.no:
>> It has always
>> been possible to create a replacement IWAD because id
>> decided to distribute the same EXE as shareware,
>> registered, and commercial. The qtest1 seems to indicate
>> that this will not change, which is a bad thing.
>I'm not sure if it is a bad thing. Maintaining two different
>EXE's would mean more work for id Software (creating the two
>versions, supporting them, etc.).
Allow me to add to that: It may or may not be the best way of doing
business, but I would hardly call giving people the benefit of the
doubt by simply asking programmers to not make their tools work with
the shareware version of doom a 'bad thing'. I rather admire that
policy. It's refreshing.
------------------------------
From: Jimmy Sieben <l-sieben@memphis.edu>
Date: Mon, 18 Mar 1996 16:31:07 -0600 (CST)
Subject: Re: WAD Conversion sketch
> On Sat, 16 Mar 1996, Bernd Kreimeier wrote:
>
> Regarding the legal issues:
>
> Maybe iD's licence doesn't explicitly forbid the creation/distribution of
> add-on levels for Quake, but personally I feel that we should respect
> iD's work and not bring out any fully-fledged editor before the
> registered version becomes available. But perhaps I'm alone in this?
I think editors should be released; the 3D design interface would
need some extensive end-user testing. The file formats and graphics are
changing, as stated by several id employees, so there is no risk of
shareware compatibility there. I cannot see any reason not to release an
editor, technical/programming issues aside.
+-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-+
| _______ _ _ _____ IRC: EvlGenius |
| |______ \ / | | Mail: l-sieben@memphis.edu |
| |______ \/ __|__ |_____ |
| ______ _______ __ _ _____ _ _ _______ DOOM Player, Programmer, |
| | ____ |______ | \ | | | | |______ IRC hacker extraordinaire |
| |_____| |______ | \_| __|__ |_____| ______| Bow down to The Genius |
+-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-+
------------------------------
End of quake-editing-digest V1 #12
**********************************
