From owner-quake-editing@nvg.unit.no Thu Apr 4 02:29 MET 1996 Received: from sabre-wulf.nvg.unit.no (bin@sabre-wulf.nvg.unit.no [129.241.161.9]) by marvin.nero.uni-bonn.de (8.7.4/8.7.1) with SMTP id CAA00133 for ; Thu, 4 Apr 1996 02:29:15 +0200 (MET DST) Received: (from bin@localhost) by sabre-wulf.nvg.unit.no (8.6.12/8.6.9) id CAA17887 for quake-editing-digest-outgoing; Thu, 4 Apr 1996 02:22:42 +0200 Date: Thu, 4 Apr 1996 02:22:42 +0200 Message-Id: <199604040022.CAA17887@sabre-wulf.nvg.unit.no> From: owner-quake-editing-digest@nvg.unit.no To: quake-editing-digest@nvg.unit.no Subject: quake-editing-digest V1 #23 Reply-To: quake-editing@nvg.unit.no Errors-To: owner-quake-editing-digest@nvg.unit.no Precedence: bulk Content-Type: text Content-Length: 1624 X-Lines: 56 Status: RO quake-editing-digest Thursday, 4 April 1996 Volume 01 : Number 023 coordinate system Unofficial Quake Specs 3.1 ---------------------------------------------------------------------- From: larsen@sunset.cs.utah.edu (Steve Larsen) Date: Wed, 03 Apr 96 14:33:58 MST Subject: coordinate system Hi all, Can someone verify for me which coordinate system Quake uses? I assume it is left-handed, but I'd just like to make sure. Thanks, Steve ------------------------------ From: Bernd Kreimeier Date: Wed, 3 Apr 1996 23:47:38 +0200 (MET DST) Subject: Unofficial Quake Specs 3.1 Forwarded from rec.games.computer.quake.editing. - --------------------------------------------------------------------------- From: Raphael.Quinet@eed.ericsson.se (Raphael Quinet) The latest version (3.1) is currently available at the following URL: http://www.stud.montefiore.ulg.ac.be/ftp-mirror/quake/docs/qkspecs31.html I uploaded it to ftp.cdrom.com too, so it should be available soon in: http://www.cdrom.com/pub/idgames2/docs/qkspecs31.zip Version 3.1 is bigger than 3.0: 120K for the new HTML file instead of 74K for the previous version. It takes 42 pages when printed with Netscape! This very useful document was written by Olivier Montanuy, with contributions from Brian Martin, John Wakelin, David Etherton and others (including myself). It is an important source of information for anyone who wants to develop a Quake editor or build Quake levels. - -Raphael ------------------------------ End of quake-editing-digest V1 #23 ********************************** From owner-@gamers.org Wed Apr 17 20:14 MET 1996 Received: from gamers.org (majordomo@thegate.gamers.org [128.205.37.150]) by marvin.nero.uni-bonn.de (8.7.4/8.7.1) with ESMTP id UAA09095 for ; Wed, 17 Apr 1996 20:14:47 +0200 (MET DST) Received: (from majordomo@localhost) by gamers.org (thegate/gamers) id OAA23966 for quake-dev-digest-outgoing; Wed, 17 Apr 1996 14:14:37 -0400 Date: Wed, 17 Apr 1996 14:14:37 -0400 Message-Id: <199604171814.OAA23966@gamers.org> From: owner-$LIST@gamers.org To: quake-dev-digest@gamers.org Subject: quake-dev-digest V1 #1 Reply-To: $LIST@gamers.org Errors-To: owner-$LIST@gamers.org Precedence: bulk X-gamers.org: quake-dev@gamers.org Content-Type: text Content-Length: 1264 X-Lines: 43 Status: RO quake-dev-digest Wednesday, 17 April 1996 Volume 01 : Number 001 ---------------------------------------------------------------------- From: Bernd Kreimeier Date: Wed, 17 Apr 1996 19:19:43 +0200 (MET DST) Subject: Total Recall Done. Back to business. You will find in the Hypermail archive all messages that reached me, at http://www.nero.uni-bonn.de/~dn/qd/archive/ The following events might have been missed by some of you during the blackout since that disk failure: - tools for editing qtest1 are okay - MAP file info by John Carmack released - CGDC talk by Michael Abrash on Quake rendering details on which can be found in said archive, and the support pages at http://www.nero.uni-bonn.de/~dn/q-sup/. Thanks to Piotr Kapiszweski for providing a new home for this list, and for making the move as painless as possible. b. - ----------------------------------------------------------- "Having you here has me kept busier than a one-armed paperhanger." - ----------------------------------------------------------- ------------------------------ End of quake-dev-digest V1 #1 ***************************** From owner-quake-dev-digest@gamers.org Wed Apr 17 21:28 MET 1996 Received: from gamers.org (majordomo@thegate.gamers.org [128.205.37.150]) by marvin.nero.uni-bonn.de (8.7.4/8.7.1) with ESMTP id VAA09817 for ; Wed, 17 Apr 1996 21:27:55 +0200 (MET DST) Received: (from majordomo@localhost) by gamers.org (thegate/gamers) id PAA24237 for quake-dev-digest-outgoing; Wed, 17 Apr 1996 15:26:57 -0400 From: owner-quake-dev-digest@gamers.org Date: Wed, 17 Apr 1996 15:26:57 -0400 Message-Id: <199604171926.PAA24237@gamers.org> To: quake-dev-digest@gamers.org Subject: quake-dev-digest V1 #2 Reply-To: quake-dev@gamers.org Errors-To: owner-quake-dev-digest@gamers.org Precedence: bulk X-gamers.org: quake-dev@gamers.org Content-Type: text Content-Length: 2075 X-Lines: 61 Status: RO quake-dev-digest Wednesday, 17 April 1996 Volume 01 : Number 002 ---------------------------------------------------------------------- From: Bernd Kreimeier Date: Wed, 17 Apr 1996 21:24:11 +0200 (MET DST) Subject: FYI: info from John Carmack The following are recent updates on the MAP and BSP details. Note that the second one is intended to solve the problem of distributing BSP files w/o including the Mipmaps. The basic idea is to have a modified "qbsp", or a separate tool, parsing a MAP file, and emitting lines like "_texture" "1 WALL14_5" in the worldspawn entity. Reference WAD files might be provided using "_wad" ".../base.wad" lines, or parameters to whatever tool is used for BSP extension. That tool will have to use the "_texture" key/value lines to determine which Mipmaps to add. I would still prefer a unified handling of PACK, WAD, WAD2, and BSP, but that's a different issue. After all, physicists always prefered GUTs. b. >From: John Carmack, Thu, 11 Apr 96 the current format has expanded miptex, sofs, tofs, and flags to 16 bits. While we probably won't ship a level with more than about 64 textures in it, I agree, 256 is never really enough of anything. The limit on offsets also prevented us from using >256 size textures in some situations, which people will probably want to do even before hitting the 256 unique textures limit. >From: John Carmack, Tue, 16 Apr 96 On the subject of storing additional info in .map and .bsp files, I decided that all key names that begin with an underscore will be dropped by quake, so you can store whatever you want in them for utility communication. I am probably going to change all of our map uses of "wad" and "light" to "_wad" and "_light" so I can remove the unused dummy variables from the progs. ------------------------------ End of quake-dev-digest V1 #2 ***************************** From owner-quake-dev-digest@gamers.org Sat Apr 20 19:55 MET 1996 Received: from gamers.org (majordomo@thegate.gamers.org [128.205.37.150]) by marvin.nero.uni-bonn.de (8.7.4/8.7.1) with ESMTP id TAA17272 for ; Sat, 20 Apr 1996 19:55:42 +0200 (MET DST) Received: (from majordomo@localhost) by gamers.org (thegate/gamers) id NAA12670 for quake-dev-digest-outgoing; Sat, 20 Apr 1996 13:55:18 -0400 From: owner-quake-dev-digest@gamers.org Date: Sat, 20 Apr 1996 13:55:18 -0400 Message-Id: <199604201755.NAA12670@gamers.org> To: quake-dev-digest@gamers.org Subject: quake-dev-digest V1 #2 Reply-To: quake-dev@gamers.org Errors-To: owner-quake-dev-digest@gamers.org Precedence: bulk X-gamers.org: quake-dev@gamers.org Content-Type: text Content-Length: 28358 Status: RO X-Lines: 752 quake-dev-digest Saturday, 20 April 1996 Volume 01 : Number 002 ---------------------------------------------------------------------- From: Bernd Kreimeier Date: Wed, 17 Apr 1996 21:36:47 +0200 (MET DST) Subject: ADMIN: Quake Developers fixes The QDev list's digest is working now. I had to fix a reply/sender problem with both the list and the digest. The QDev pages might be unreacheable at times; today we replaced the CERN server with Apache. It seems the protection is not yet configured right. Should be fixed now. The list is open for postings, and will be openend for new subscriptions again on monday. I honestly hope this is the last ADMIN posting for some weeks. b. ------------------------------ From: larsen@sunset.cs.utah.edu (Steve Larsen) Date: Wed, 17 Apr 96 14:23:26 MDT Subject: Re: Total Recall >Done. Back to business. You will find in the Hypermail archive >all messages that reached me, at > > http://www.nero.uni-bonn.de/~dn/qd/archive/ > >The following events might have been missed by some of >you during the blackout since that disk failure: > > - tools for editing qtest1 are okay > - MAP file info by John Carmack released > - CGDC talk by Michael Abrash on Quake rendering > >details on which can be found in said archive, and the >support pages at http://www.nero.uni-bonn.de/~dn/q-sup/. > >Thanks to Piotr Kapiszweski for providing a new home for >this list, and for making the move as painless as possible. > > > b. Hi, Just thought you might want to know that when I tried to access www.nero.uni-bonn.de/~dn/q-sup, I was not allowed (said I didn't have permission). BTW, thanks for all the work you've been doing. Steve ------------------------------ From: Bernd Kreimeier Date: Thu, 18 Apr 1996 18:40:20 +0200 (MET DST) Subject: Re: No texture patches A posting back from the quake-editing era.... >From: Uffe Friis Lichtenberg >It is clear to us by now that Quake does not support Doom-like >texture patches, so that we could create a multitude of textures using >only a small set of building-block-textures. The question is: is it a >problem that we somehow can circumvent? >The best I can come up with is implementing signs using billboard >objects. Having an object (entity) aligned with a wall will work, as long as you do not forget that the light maps will not be used on the object, only on the surfaces behind. Btw., a better (OpenGL-ish) name for such objects pasted to walls would be "decals" >I can't really think of a situation where I would wan't the >texture patches from Doom available, If I understood correctly: textures are references by MAP files by name. The "qbsp" utility creates surfaces from brushes, and keeps track of which textures have been used. Then it will look up the textures in a (might even by DOOM-style) WAD ("wad" ".../gfx/base.wad"), and create the mipmaps. I wonder if the anti-aliased scaling is done every time, and if TEXTURE1/2 are still (perhaps modified) in use. Any such processing of multi-patch textures (from DOOM or whatever) to mipmaps could be done seperately. >Anyway, I think that the problems of integrating texture patches in the >Quake engine now would surely exceed the gained flexibility (unless >ofcourse they already are supported, and nobody found out yet :). Perhaps my page has been inconclusive: a) using patches saves some texture memory, but not surface cache. It would ease adding small variations and navigational aids to basic (flat) textures b) all available descriptions of the renderer state that the suitable mipmap from a texture and the light map for (potentially) visible surfaces are combined once. The result is stored in the surface cache, as long as memory is available, and the surface remains in sight. Adding some simplified patch mechanism (e.g. one flat texture, opaque, and an optional list of partly transparent patches/decals) to this preprocessing "mipamp+lightmap -> texture in surface cache" would surely be feasible. In this case, the decals would be subject to the same lighting. They might even be flagged for "bright", in that case the patches would be added after lighting the appropriate mipmap. Hope that made more sense, this time. b. ------------------------------ From: Uffe Friis Lichtenberg Date: Fri, 19 Apr 1996 00:48:38 +0200 (METDST) Subject: Re: No texture patches On Thu, 18 Apr 1996, Bernd Kreimeier wrote: > A posting back from the quake-editing era.... :) (BTW: Thanks for all the hard work!) > >From: Uffe Friis Lichtenberg > > >The best I can come up with is implementing signs using billboard > >objects. > > Having an object (entity) aligned with a wall will work, as long as > you do not forget that the light maps will not be used on the object, > only on the surfaces behind. This is a problem! Billboard objects would probably always be flat- or perhaps gouraud-shaded, and not with light maps, so they would always stand out in some way. This would have to be taken into account when designing the level, and thus put a constraint on the level designer. This is a Bad Thing. > Btw., a better (OpenGL-ish) name for > such objects pasted to walls would be "decals" Quite. But having another term for billboard objects used only in this context would only lead to confusion. Anyway they aren't (as far as I can see) in any way usable as decals: they are individual objects that can be placed anywere in the world; they are not bound to a wall! > >I can't really think of a situation where I would wan't the > >texture patches from Doom available, > > If I understood correctly: textures are references by MAP files by name. > The "qbsp" utility creates surfaces from brushes, and keeps track of > which textures have been used. Then it will look up the textures in > a (might even by DOOM-style) WAD ("wad" ".../gfx/base.wad"), and create > the mipmaps. I wonder if the anti-aliased scaling is done every time, > and if TEXTURE1/2 are still (perhaps modified) in use. Well that depends on qbsp of course. Though the anti-aliased scaling isn't a very computationally expensive process, it would be a rather silly waste of CPU resources to do it everytime the textures were needed. My guess is that the wad files with textures contain all the four resolutions needed. Hopefully it is so: this opens up for some interesting special effects, like secret messages only visible when very close to the texture (or possibly very far away :). Try fooling round with MipDip and edit the different mipmaps without resampling them, and you'll see what I mean. > Any such processing of multi-patch textures (from DOOM or whatever) to > mipmaps could be done seperately. Yes. Even if Quake doesn't support patches it would be rather easy to implement a small utility that could build the relevant textures using some sort of patch description. This would of course not bring down the runtime overhead induced by having many textures in memory at one time, but would allow level-designers to easily create textures using the many existion Doom texture packages. Besides if the target machine has enough RAM it would clearly be more speed-efficient to disable patch building in real-time! > Perhaps my page has been inconclusive: > > a) using patches saves some texture memory, but not surface cache. > It would ease adding small variations and navigational aids to > basic (flat) textures Well... Using billboard objects could probably make adding navigational aids equally easy, but the small variations is still something that Quake seemingly doesn't support well. This might need a separate utility depending on how qbsp handles it. Alternatively my previously shown method of splitting up a surface in several sub-surfaces could solve some of these problems. > b) all available descriptions of the renderer state that the suitable > mipmap from a texture and the light map for (potentially) visible > surfaces are combined once. The result is stored in the surface > cache, as long as memory is available, and the surface remains in > sight. > > Adding some simplified patch mechanism (e.g. one flat texture, opaque, > and an optional list of partly transparent patches/decals) to this > preprocessing "mipamp+lightmap -> texture in surface cache" would surely > be feasible. In this case, the decals would be subject to the same > lighting. They might even be flagged for "bright", in that case the > patches would be added after lighting the appropriate mipmap. Though the combination of mipmap and lightmap is a trivial process (using colour mixing LUTs, or in Quakes case, colour lighting LUTs) it is not computationally cheap. It does involve at least one table-lookup per texel. Adding a patched texture building before (or after) this would add to the total overhead each time a texture had to be fetched into the surface cache. I'm not sure of how much overhead this would amount to, but it is still something that would slow down Quake. By this reason alone I would say that the patch building of textures should be done as a preprocessing step, even though it would make distribution files larger (unless we can agree on a distribution format that supports patches) and memory requirements larger. It is though a serious problem that Quake only supports 256 textures total on a level: lets hope that id fixes this ASAP. (BTW: files with many areas of great similarity --- as those build using a patch texture building approach --- would compress very well with Lempel-Ziv based compression algorithms. This of course includes most of the compression utilities today. So the net.bandwith load wouldn't necessarily get excessive.) > Hope that made more sense, this time. Quite. I guess the motto of todays lesson would be: buy more RAM :) And harddisk too... Zonk, Uffe. [uphfe] uffefl@diku.dk - -- "This .signature hasn't been left unintentionally void of blankness" ------------------------------ From: larsen@sunset.cs.utah.edu (Steve Larsen) Date: Thu, 18 Apr 96 20:46:33 MDT Subject: new level Hi all, I just finished hacking together a REAL small quake level (just two rooms connected by a couple of hallways). In the meantime, I learned a couple of things of interest that I thought I might share: 1. The UQS says that the edges for a surface must be constructed such that the vertices would be traversed in a counter-clockwise manner. I think this must be wrong. I could only get it to work in clockwise order. 2. As you may know, there is a limit to the maximum extent that a surface can displace (based on texture size, I'm guessing??). There doesn't seem to be such a limit on that animated worms texture (the one with the periodic noise-filter). 3. I had trouble using a single plane to describe the position of multiple surfaces when these surfaces where not on the same side of a BSP node. So, for the following: ^ | ------------------------|--------------------- a | b | | | | | BSP partition surface a and b are co-planar. However, if I used the same plane for them I would get unpredictable results (mostly, they would just not show up). I am sure I was doing something wrong, but I don't know what. Anyone have any experience with this? Anyway, now that I have the basics down, I can work on getting my editor up to speed. laters, Steve P.S. If you want to see this little level, visit: http://www.cs.utah.edu/~larsen. It is called "tworooms.zip". ------------------------------ From: Chris Carollo Date: Thu, 18 Apr 1996 12:06:14 -0400 Subject: line intersecting plane... I have a geometric question... What is the easiest way to calculate where a line intersects a plane (given by two non-colinear vectors)? I started to work out the math (three equations, three unknowns), but it got REAL ugly REAL quick. I'm trying to convert my two-vector plane representation to the normal- distance representation...calculating the normal is simple (cross product), the distance from the normal to (0,0,0) is screwing with me. Does anyone have a simple way to calculate this? - -Chris ------------------------------ From: Olivier Montanuy Date: Fri, 19 Apr 1996 11:01:23 +0200 Subject: RE: line intersecting plane... >I have a geometric question... You're welcome >the distance from the normal to (0,0,0) is screwing with me. Rather difficult indeed. Take the scalar product between normal vector and any point of the plane, and multiply by the exponent of your personal level in maths. You might have to scale down, but I doubt it. Olivier ------------------------------ From: Olivier Montanuy Date: Fri, 19 Apr 1996 14:21:25 +0200 Subject: New version of specs Dear Quake hackers, I haven't updated the specs in 3 weeks, despite all the new info, because I lack time for serious work on them. Very sorry for this, but work becomes quite involving (at times). Maybe it's time for someone else to maintain those specs. As some of you might have noticed, a few areas in the Quake specs are real unclear: I list some here: - Could someone confirm the surface edges are in clockwise order, not anticlockwise as stated? I admit I said anticlockwise at random (I knew it was one or the other. 1 chance out of 2, no?) but later forgot to update. - anyone could confirm the BSP split notes split or don't split the surface edges? - Could someone give a working formula or code for the layout of lightmaps and textures? I roughly know, but don't have time to check. - Some of you are working on the .MAP format. Your input is welcome in the specs (I don't have any time for them). Also, my BSP viewer WinTex 4.3 didn't make any progress in one month. It's too rudimentary to be worth publishing (only wireframe). If some of you know where I can get a second life for free, let me know. With regards, Olivier Montanuy ------------------------------ From: Bernd Kreimeier Date: Fri, 19 Apr 1996 14:52:33 +0200 (MET DST) Subject: Re: line intersecting plane... >From: Olivier Montanuy > multiply by the exponent of your personal level in maths. Well, this is not much of a useful answer, in any sense :-(. > From: Chris Carollo > What is the easiest way to calculate where a line intersects a plane > (given by two non-colinear vectors)? You will find a Dr. Dobb's Sourcebook article in the March/April 1996 issue by Michael Abrash (thanks to Derek Nickel for providing the pointer in first place): "3-D Clipping and Other Thoughts". I will simply quote: "If we take any point and dot with the plane normal, we'll find out how far from the origin the point is, as measured along the plane normal. [..] a simple comparison of the two values [the distance of the plane to the origin, the projection of the point's vector on the plane's normal] suffices to tell us which side of the plane the point is on." Hence the normal + distance representation. > I'm trying to convert my two-vector plane representation to the normal- > distance representation...calculating the normal is simple (cross > product), the distance from the normal to (0,0,0) is screwing with > me. You have the vector from the origin to the 1st of your three points defining the plane. You know that this point is on the plane. A dot product with your normal will give you the distance from origin to plane (again: projection of the vector on the normal). b. - ------------------------------------------------------------------------- "Sharing knowledge makes the world a better place." - ------------------------------------------------------------------------- ------------------------------ From: jschuur@flash.globalnews.com Date: Fri, 19 Apr 1996 23:32:33 +0000 (GMT) Subject: Quake map distribution: speed vs. legality if i understand correctly, it is being proposed new quake levels should only be redistributed in a .map format, since each level contains the textures it uses. reditributing quake levels in a .bsp format would be a violation of id's copyright. calculating the nodes to a quake level however can take up to an hour even on a 4 processor alpha (according to information from id). surely no average home user is going to wait for hours before his level is converted from .map to .bsp. or am i misunderstanding something here? is there an intermittent format with calcutated nodes (and lighting and whatever else qbsp, light and vis do) that merely needs to be assembled to the finished product quickly? -- joost schuur, Online Magic Ltd. ------------ Tel: +44 171 820 7766 -- ------------------------------------------------------------------------ ------------------------------------------------------------------------ - --- http://jalad.globalnews.com/~jschuur/ - jschuur@onlinemagic.co.uk -- ------------------------------ From: Uffe Friis Lichtenberg Date: Sat, 20 Apr 1996 01:28:07 +0200 (METDST) Subject: Re: Quake map distribution: speed vs. legality On Fri, 19 Apr 1996 jschuur@flash.globalnews.com wrote: > if i understand correctly, it is being proposed new quake levels should > only be redistributed in a .map format, since each level contains the > textures it uses. reditributing quake levels in a .bsp format would be a > violation of id's copyright. > > calculating the nodes to a quake level however can take up to an hour > even on a 4 processor alpha (according to information from id). surely no > average home user is going to wait for hours before his level is > converted from .map to .bsp. > > or am i misunderstanding something here? is there an intermittent format > with calcutated nodes (and lighting and whatever else qbsp, light and > vis do) that merely needs to be assembled to the finished product quickly? As I see it destributing a .bsp file does not necessarily infringe ids copyright, unless you include some of their textures. So what we need is to destribute a .bsp file without ids textures, that only needs to be preprocessed before use (ie. copy missing textures from id1.pak). I remember Carmack stating that all entries beginning with "_" (underscore) will be ignored by the quake engine. Therefore we could transport the texture information in such entries (or am I wrong?). Something _really_ smart would be to have the distributed .bsp file be a valid .bsp file, ready for play. Only before being preprocessed all surfaces would have the same texture! And this texture could simply be black with the inscription: "Don't play this level before running smartutil.exe on it..." or something similar! This way newbies could download their Quake levels, play them, and _not_ have to ask in newsgroups or on IRC why the levels never work! (Cool: self-documenting and all ;) Zonk, Uffe. [uphfe] uffefl@diku.dk - -- "This .signature hasn't been left unintentionally void of blankness" ------------------------------ From: Stephen Crowley Date: Fri, 19 Apr 1996 23:52:59 -0500 Subject: Map Files Can someone please help me with a little problem "Note that it takes six cubes (brushes or building blocks) to define on box " "volume, and each brush has six planes, the intersections of which define the " "surface of the brush. " John Carmack - quoted from one of the qdev pages. I understand that the planes are stored in 3point form for accuracy. What I need to know is how would you take a list of planes and turn that into a list of vertices and lines (a convex polyhedron)? Also, I made a little function to take 3 points and turn it into a plane (Ax+By+Cz+D=0). It has some problems that I havn't been able to work out. Could someone please tell me what I'm doing wrong. typedef struct { float a,b,c,d; } m_plane; typedef struct { int x,y,z; } point; float sqr(float r) { return pow(r,2); } float pos(float r) { if (r > 0) return r; else return -r; } float neg(float r) { if (r < 0) return r; else return -r; } int ispos(float r) { return (r >= 0); } // Takes 3 points and returns a plane in the form of Ax+By+Cz+D=0 m_plane getplane(point p1,point p2,point p3) { float r; m_plane p; // Get the normal vector p.a=((p1.y - p2.y) * (p1.z - p3.z)) - ((p1.z - p2.z) * (p1.y - p3.y)); p.b=((p1.z - p2.z) * (p1.x - p3.x)) - ((p1.x - p2.x) * (p1.z - p3.z)); p.c=((p1.x - p2.x) * (p1.y - p3.y)) - ((p1.y - p2.y) * (p1.x - p3.x)); // Substitute a known point into the Equation for D p.d=(p1.x*p.a) + (p1.y*p.b) + (p1.z*p.c); // Convert to normal form // The sign of R is chosen opposite to the sign of D when D!=0, the same // as the sign of C when D = 0 and C!=0, the same as the sign of B when // C = D = 0 // *** IS THIS RIGHT OR IS THERE MORE TO IT? r=sqrt(sqr(p.a)+sqr(p.b)+sqr(p.c)); if (p.d != 0) if (ispos(r)) r = neg(r); else r = pos(r); else if (p.d == 0 && p.c != 0) if (ispos(p.c)) r = pos(r); else r = neg(r); else if (p.c == p.d == 0) if (ispos(p.b)) r = pos(r); else r = neg(r); p.a=p.a / r; p.b=p.b / r; p.c=p.c / r; p.d=p.d / r; return p; } // returns >0 in front of plane // =0 on plane // <0 behind plane float side(point p, m_plane m) { return (m.a*p.x)+(m.b*p.y)+(m.c*p.z)+m.d; } Thanks, Stephen ------------------------------ From: amoon@odin.mdn.com (Alex R. Moon) Date: Sat, 20 Apr 1996 01:26:00 -0500 (EST) Subject: Re: Quake map distribution: speed vs. legality Uffe Friis Lichtenberg wrote: > As I see it destributing a .bsp file does not necessarily infringe ids > copyright, unless you include some of their textures. So what we need is > to destribute a .bsp file without ids textures, that only needs to be > preprocessed before use (ie. copy missing textures from id1.pak). > > I remember Carmack stating that all entries beginning with "_" > (underscore) will be ignored by the quake engine. Therefore we could > transport the texture information in such entries (or am I wrong?). That was in reference to the .MAP files. I presume he meant that all entries beginning with '_' would be filtered out by the qbsp/light/vis tools and not show up in the .BSP file at all. > Something _really_ smart would be to have the distributed .bsp file be a > valid .bsp file, ready for play. Only before being preprocessed all > surfaces would have the same texture! And this texture could simply be > black with the inscription: "Don't play this level before running > smartutil.exe on it..." or something similar! > > This way newbies could download their Quake levels, play them, and _not_ > have to ask in newsgroups or on IRC why the levels never work! > > (Cool: self-documenting and all ;) I think the most compatible/efficient way to do this would be to fully compile the BSP tree, but instead of having the full MIP texture data for copyrighted textures, it would just have the texture name and either a 0x0 texture (no texture data) or a dummy self-documenting texture like you describe above. Then the end-user compiling utility would just go searching through that user's other BSP files (or a WAD or whatever) for a texture with the same name as a dummy texture in the target BSP. Viola, a complete level. - -- Alex R. Moon | "A university is what a college become when the amoon@odin.mdn.com | faculty loses interest in students." 71513.1453@compuserve.com | -- John Cardi ------------------------------ From: mpolis@polbox.com.pl Date: Sat, 20 Apr 1996 10:41:52 +0200 Subject: To seam or not to seam... Hi. Two of my friends and myself are learning 3D through making Quake .MDL viewer :). Of course we know a bit about 3D (all sorting algorithms, free-dir.text.mapping, env.mapping, Lamert/Gouraud/Phong, etc.), but yet we have a little trouble with .MDL files... 1. On-seam, off-seam. We get the idea. To make textures linked seamless. Okay. There is a boolean. Okay. So we know which vertexes are on-seam, and which are not. But how to use this information in practice? I guess it has something to do with the fact that back texture is put on width/2... 2. Hmmm... A bit strange that noone made his own .MDL file yet. Of course there are a lot of home-made .MDLs (even the one with player as Duke Nukem...), but noone did it from scratch. Some people made whole new levels, but noone did monsters... Any ideas where lies the most difficult part of making 3D sprites (so to speak :)? 3. Now something for fun: it is suspected, that monsters gfx data will contain much more info that now. But now I can't think of anything else we would want! We have textures (and we're not restricted to one per monster), we have 'removable', independent body parts, we have information about the light, we have animations (in which we can even morph our monsters)... What more can one do with it?! Any hints, especially for 1st questions, will be very appreciated. Thanks... Adrian Chmielarz Metropolis ------------------------------ From: Bernd Kreimeier Date: Sat, 20 Apr 1996 19:55:09 +0200 (MET DST) Subject: Re: Quake map distribution: speed vs. legality >>Uffe Friis Lichtenberg wrote: >> I remember Carmack stating that all entries beginning with "_" >> (underscore) will be ignored by the quake engine. Therefore we could >> transport the texture information in such entries (or am I wrong?). You are right. That is the idea. >That was in reference to the .MAP files. I presume he meant that >all entries beginning with '_' would be filtered out by the >qbsp/light/vis tools and not show up in the .BSP file at all. This is not correct. Please re-read my comments along with the mail forwarded last week. If I understood correctly, the bottom line is: - the "wad" and "light" entries are used by qbsp and light, but not by qtest1 (not sure about this) - there are currently QuakeC dummies (entities) for these to keep Quake qtest1 from complaining (anybody put a undefined key into the entities file already?) - John Carmack changed Quakes handling of the entities lump, all "_*" keys will be ignored now - he intends to change said entries to "_wad" and "_light", to get rid of the dummies - he proposes using "_*" key/value lines in the MAP files for tasks like a BSP completion Distribution of MAP files is useful if one wants the level to be modified and edited by others. Automatic generation of MAP from BSP is a nice task we could tackle along with generating MAP from DOOM level descriptions. Distribution of BSP files w/o mipmaps lump requires a lookup assigning indices (as used in surfaces, generated by qbsp) to textures (as defined in the MAP file). It is no good idea to distribute this lookup separately. The current proposal is to add "_texture" " 1 WALL54_0" lines to the entities lump in the BSP. These will not be deleted by qbsp, and will be ignored by Quake. To use this approach with qtest1, these lines would have to be deleted after adding the mipmaps, to prevent warnings or errors. However, we are far from generating BSP files for qtest1 :-). b. ------------------------------ End of quake-dev-digest V1 #2 ***************************** From owner-quake-dev-digest@gamers.org Mon Apr 22 21:08 MET 1996 Received: from gamers.org (majordomo@thegate.gamers.org [128.205.37.150]) by marvin.nero.uni-bonn.de (8.7.4/8.7.1) with ESMTP id VAA05777 for ; Mon, 22 Apr 1996 21:08:35 +0200 (MET DST) Received: (from majordomo@localhost) by gamers.org (thegate/gamers) id PAA23533 for quake-dev-digest-outgoing; Mon, 22 Apr 1996 15:08:22 -0400 From: owner-quake-dev-digest@gamers.org Date: Mon, 22 Apr 1996 15:08:22 -0400 Message-Id: <199604221908.PAA23533@gamers.org> To: quake-dev-digest@gamers.org Subject: quake-dev-digest V1 #3 Reply-To: quake-dev@gamers.org Errors-To: owner-quake-dev-digest@gamers.org Precedence: bulk X-gamers.org: quake-dev@gamers.org Content-Type: text Content-Length: 27019 X-Lines: 712 Status: RO quake-dev-digest Monday, 22 April 1996 Volume 01 : Number 003 ---------------------------------------------------------------------- From: amoon@odin.mdn.com (Alex R. Moon) Date: Sat, 20 Apr 1996 13:20:42 -0500 (EST) Subject: Re: Quake map distribution: speed vs. legality Bernd Kreimeier wrote: > Distribution of MAP files is useful if one wants the level to > be modified and edited by others. Automatic generation of > MAP from BSP is a nice task we could tackle along with > generating MAP from DOOM level descriptions. > > Distribution of BSP files w/o mipmaps lump requires a lookup > assigning indices (as used in surfaces, generated by qbsp) to > textures (as defined in the MAP file). It is no good idea > to distribute this lookup separately. The current proposal is > to add > > "_texture" " 1 WALL54_0" > > lines to the entities lump in the BSP. These will not be > deleted by qbsp, and will be ignored by Quake. To use this > approach with qtest1, these lines would have to be deleted > after adding the mipmaps, to prevent warnings or errors. But a lookup table mechanism for textures already exists in the BSP format. If you just use the mipmaps lump with dummy textures (textures with a name like WALL54_0 and an implied index by their position in the lump, but a size of 0x0 and no actual texture data) then a utility program can go through and replace all dummy textures with real textures from the quake BSP files based on the names of the dummy textures. There is no need to clutter up the entities lump with redundant data. - -- Alex R. Moon | "A university is what a college become when the amoon@odin.mdn.com | faculty loses interest in students." 71513.1453@compuserve.com | -- John Cardi ------------------------------ From: Bernd Kreimeier Date: Sat, 20 Apr 1996 20:36:35 +0200 (MET DST) Subject: Re: Quake map distribution: speed vs. legality > If you just use the mipmaps lump with dummy textures (textures > with a name like WALL54_0 and an implied index by their position in the > lump, but a size of 0x0 and no actual texture data) then a utility program > can go through and replace all dummy textures with real textures from the > quake BSP files based on the names of the dummy textures. You are perfectly right. Somehow I entirely forgot about the "name" entry in the mipmaps lump. Too much sysad work last week, I guess. It might be a good idea to set the version index in the BSP header to some value unused and unknown to Quake, to keep it from loading a distribution BSP (let's call it dBSP for convenience sake). We could write a tool to "strip" a BSP file, creating a dBSP, and test it with the qtest1 BSP files (no practical use, as we should not distribute, but nice to test it already). Same for the "add_mip". Neat. Now I wonder wether those "_entries" are good for anything... b. ------------------------------ From: Uffe Friis Lichtenberg Date: Sat, 20 Apr 1996 21:16:22 +0200 (METDST) Subject: Re: Quake map distribution: speed vs. legality On Sat, 20 Apr 1996, Bernd Kreimeier wrote: > Distribution of MAP files is useful if one wants the level to > be modified and edited by others. Automatic generation of > MAP from BSP is a nice task we could tackle along with > generating MAP from DOOM level descriptions. Having the .map follow the .bsp file all the way would be optimal. This way both level-editing and level-playing would be supported. I propose to designate an entry "_mapfile.zip" were a zip-compressed .map representation of the .bsp file could be kept. This way an editor would only have to deal with .bsp files (and thus avoid confusion for users). If the user wants to play the level he starts it up using the console command "map whatever", and if he wants to edit it he loads up an editor with whatever.bsp. This I propose because I find the idea of a completely self-contained (immidiately 'playable') .bsp-file very attractive. Instead of the typical Doom-multifile-zip-distribution each level would have one, and only one, file associated with it. The typical readme.txt could also easily be added to the .bsp-file as "_readme". Now, as earlier stated, a user might have to run an external utility on the .bsp-file (to get all textures right) to get the full experience, but basically it is playable right-away. Hmmm... I'm rambling, let me summarize: * A distributable .bsp-file contains none of ids textures, but "_texture" entries that tell a preprocessing utility how to build the right .bsp-file from the distributable .bsp-file. All the surfaces that should have had one of ids textures, are assigned a dummy texture in the distributable .bsp-file. This assignment is changed by a preprocessing utility according to the "_texture" entries. The preprocessing utility should also be able to reverse this process, so you don't have to keep the distributable file as well as the playable one. * To help map-editing a .bsp-file builder should, as a post-processing step, zip the .map-source-file and include it into the .bsp-file in the "_mapfile.zip" entry. This way an editor could work on .bsp-files only (and even save editor project information in the .bsp file as "_MYQED:varname=value" or similar; as long as we keep the MYQED string unique for each editor and editor version) and rebuilding .map-files from .bsp-files wouldn't be necessary. Also, a level author who doesn't wish other people to use his levels as a base, could easily mark this be _not_ including the "_mapfile.zip" entry. * The level-information, copyright and so on, could be placed in a "_readme" entry, which the previously mentioned preprocessing utility could show to the user while processing the .bsp-file. It would be especially nice if we could agree this early on, on a general layout of the "_*" entries. Even though we aren't even (thinking of :) building .bsp-files from .map-files yet, it would be nice to agree on a standard of sorts. > Distribution of BSP files w/o mipmaps lump requires a lookup > assigning indices (as used in surfaces, generated by qbsp) to > textures (as defined in the MAP file). It is no good idea > to distribute this lookup separately. The current proposal is > to add > > "_texture" " 1 WALL54_0" > > lines to the entities lump in the BSP. These will not be > deleted by qbsp, and will be ignored by Quake. To use this > approach with qtest1, these lines would have to be deleted > after adding the mipmaps, to prevent warnings or errors. I haven't tried it, but does qtest1 complain when encountering "_*" entries? Zonk, Uffe. [uphfe] uffefl@diku.dk - -- "This .signature hasn't been left unintentionally void of blankness" ------------------------------ From: Uffe Friis Lichtenberg Date: Sat, 20 Apr 1996 21:19:25 +0200 (METDST) Subject: Re: Quake map distribution: speed vs. legality On Sat, 20 Apr 1996, Bernd Kreimeier wrote: > > If you just use the mipmaps lump with dummy textures (textures > > with a name like WALL54_0 and an implied index by their position in the > > lump, but a size of 0x0 and no actual texture data) then a utility program > > can go through and replace all dummy textures with real textures from the > > quake BSP files based on the names of the dummy textures. > > You are perfectly right. Somehow I entirely forgot about the "name" > entry in the mipmaps lump. Too much sysad work last week, I guess. > > It might be a good idea to set the version index in the BSP header to > some value unused and unknown to Quake, to keep it from loading a > distribution BSP (let's call it dBSP for convenience sake). I still think that having a format for the dBSP files that would allow them to be playable (though ugly to look at) would be the best solution. > We could write a tool to "strip" a BSP file, creating a dBSP, and test > it with the qtest1 BSP files (no practical use, as we should not > distribute, but nice to test it already). Same for the "add_mip". Neat. Shouldn't be so difficult really. As long as people who add textures assign them new names... But isn't this (almost) exactly what Thingy does? > Now I wonder wether those "_entries" are good for anything... ? See previous posting... They sure could be used for a lot of creative things. Just put your mind to it :) Zonk, Uffe. [uphfe] uffefl@diku.dk - -- "This .signature hasn't been left unintentionally void of blankness" ------------------------------ From: Jim Bucher Date: Sat, 20 Apr 1996 21:00:09 -0500 Subject: rendering question I currently have a program that will display a wire frame of the quake levels. Now I want to use the visibility list to do some culling. To do this I need to know which leaf the camera is in. I am currently just searching through the array of leaves and checking if the camera is in the bounding box for each leaf. However, I have found that the camera can be in several of the bounding boxes. In other words, how do I find which leaf is the actual leaf the camera is in? ------------------------------ From: Bernd Kreimeier Date: Sun, 21 Apr 1996 08:22:47 +0200 (MET DST) Subject: Re: rendering question > In other words, how > do I find which leaf is the actual leaf the camera is in? Use the BSP. Start at the root, do a dot product of camera position vector and plane normal, compare with distance to origin. This gives you wether you are in the left or right subtree/halfspace. Repeat with the appropriate child node, until you reach a leaf. Done. I keep wondering wether Quake does this for any moving object for each frame... does anybody have any insights on how actual "EntityInLeaf" information is maintained? b. ------------------------------ From: "Brian K. Martin" Date: Sun, 21 Apr 1996 09:28:35 -0400 (EDT) Subject: Re: To seam or not to seam... > > 1. On-seam, off-seam. We get the idea. To make textures > linked seamless. Okay. There is a boolean. Okay. So > we know which vertexes are on-seam, and which are not. > But how to use this information in practice? I guess > it has something to do with the fact that back texture > is put on width/2... yes i thought this was in the quake specs... if a polygon is on the back, then add w/2 to the points that are on seem (texture coords that is). > 2. Hmmm... A bit strange that noone made his own .MDL file > yet. Of course there are a lot of home-made .MDLs (even > the one with player as Duke Nukem...), but noone did > it from scratch. Some people made whole new levels, but > noone did monsters... Any ideas where lies the most > difficult part of making 3D sprites (so to speak :)? I have orginal mdl files. The only difficult part (not really difficult but time consuming) is placing the texture on the object. I'm thinking of making a web page for model making. I'll post if i do. > we have 'removable', independent body parts, we have > information about the light, we have animations (in which > there is no light info in the model files. brian ------------------------------ From: "Drizzt Do'Urden" Date: Sun, 21 Apr 1996 13:34:48 -0700 (PDT) Subject: Visibility lists I've recently been messing with creating a homemade level from scratch, but have run into some trouble. My test level is a simple 128x128x256 room, with 2 leaves. The level runs okay, but I get some strange problems during play. It seems that only the first leaf renders properly. (i.e. draws all the walls, etc..) While in the second leaf, none of the walls are drawn unless the back wall of the first leaf in in your line of sight. I am guessing this has something to do with the visibility lists. I have written what seems to be a working lmp to txt and txt to lmp converter for the visibility lists (entry04.lmp using unbsp). Assuming that is working corectly, I have no idea where to go from here. Any information on how the visibility lists work would be greatly appreciated. (Yes, i've read the Quake Specs) Brent ------------------------------ From: Stephen Crowley Date: Sun, 21 Apr 1996 20:05:30 -0500 Subject: Map Info from Carmack Here is the info I got when I asked him about implementing seperate hulls in .map files. *** E-Mail from John Carmack - 4/21/96 The seperate clipping hulls (there was one in qtest, but there are more now) are automatically generated in the bsp utilities by doing a beveled hull expansion on the brushes. You don't need to do anything in the map editor. You can add brushes that only show up in the clipping hulls (invisible blocking brushes) by giving them the texture name "clip". John Carmack **** If anyone knows what "beveled hull expansion" is then please feel free to share. Stephen ------------------------------ From: Chris Carollo Date: Sun, 21 Apr 1996 10:49:00 -0400 Subject: Re: Map Info from Carmack > > *** E-Mail from John Carmack - 4/21/96 > > The seperate clipping hulls (there was one in qtest, but there are more > > now) are automatically generated in the bsp utilities by doing a beveled > > hull expansion on the brushes. You don't need to do anything in the map > > editor. What does he mean by "clipping hulls"? And there was only *one* of them in qtest? It doesn't sound like he just mean hulls separate from the main level hull... > > You can add brushes that only show up in the clipping hulls (invisible > > blocking brushes) by giving them the texture name "clip". So we can define invisible volumes? Or does he mean that we can define a brush that does a boolean subtract? > If anyone knows what "beveled hull expansion" is then please feel free to > share. Seconded. :) - -Chris ------------------------------ From: Olivier Montanuy Date: Mon, 22 Apr 1996 17:03:22 +0200 Subject: Re: To seam or not to seam... >yes i thought this was in the quake specs... This is in the spec, indded. But that doesn't mean it's understandable for everyone :-) (like 50% of the .BSP description). Can someone take a look and propose a simpler explanation? > The only difficult part is placing the texture on the object. And maybe generating the animation frames themselves... >there is no light info in the model files. I confirm. Once again, the wording of the specs (lightnormalindex) probably is just confusing. Someone has a better wording? Olivier (building spec 3.2) ------------------------------ From: Olivier Montanuy Date: Mon, 22 Apr 1996 17:50:54 +0200 Subject: RE: Map Files >What I need to know is how would you take a list of planes and turn that >into a list of vertices and lines (a convex polyhedron)? sounds like the kind of stuff that happens in the simplex's algorithm (a classic stuff used in optimisation). No idea how id does this, but the result isn't perfect (many duplicated segment references). I assume most vertex will appear naturally when doing the BSP splitting. >// The sign of R is chosen opposite to the sign of D when D!=0, the same I wonder why the heck you would want to change the sign of r. It's positive. Else your normal vector will be inverted. ------------------------------ From: Bernd Kreimeier Date: Mon, 22 Apr 1996 18:14:25 +0200 (MET DST) Subject: RE: Map Files >>What I need to know is how would you take a list of planes and turn that >>into a list of vertices and lines (a convex polyhedron)? > sounds like the kind of stuff that happens in the simplex's algorithm > (a classic stuff used in optimisation). I do not think so, frankly. > No idea how id does this, but the result isn't perfect (many duplicated > segment references). I assume most vertex will appear naturally when doing > the BSP splitting. Again: beg to differ. It seems that our current understanding of the MAP format is incomplete. In my opinion, there are the following processing steps that have to be done *within QuakeEd*: define/modify planes of a single brush calculate a boundary representation of the brush. based on plane-plane-intersections add brush to the map as already done Note that the boundary representation is necesary, as human beings are not likely to think in infinite planes. We need the building blocks to be convex polyhedra, solid bricks of material. See QuakeEd screenshots, the top-down view. Note that all planes of one brush do intersect, but that planes of different brushes do not intersect. Brush-brush intersection is calculated using CSG with the polygons, not the planes. I refer to the "recommended readings" page, the book by Martti Mantyla (and his Geometric Workbench source), and the Ian Ashdown code in the HELIOS radiosity package - both use half-edge representations, IIRC, that allow for boolean operations with boundary representations: solid modeling, that is. There is a reprint of the CSG book by Mantyla scheduled for May, it is currently out of print. The "qbsp", as much as my two cents are worth, calculates brush-brush intersection - the QuakeEd screenshot does not demonstrate the 3D camera view. A z-buffer for slow preview will work nicely with intersecting polyhedras, so there it might be better to keep that calculations out of the editor. To understand the MAP files, we should ask ourselves: What does a MAP with only one brush looks like, i.e. one solid that is surrounded by nothing. What does a MAP look like with only non-intersecting and non-touching brushes? What does "sealing the world" mean (mentioned by Abrash and Carmack), but removal of all outside surfaces that cannot be seen from the interior? Will there be anything left in the two MAPs described above, once "qbsp" is done? Note that John Carmack mentions "convex polyhedra operations" in both "qbsp" and QuakeEd. Again, anybody who is working on a MAP editor should be aware of the processing of planes and brushes necessary for any previewing during editing. Vertices and edges are only implicit in the MAP files, but they have to be made explicit to the user. b. ------------------------------ From: "Brian K. Martin" Date: Mon, 22 Apr 1996 12:49:35 -0400 (EDT) Subject: Re: To seam or not to seam... > > Can someone take a look and propose a simpler explanation? > source code > > I confirm. Once again, the wording of the specs (lightnormalindex) > probably is just confusing. Someone has a better wording? > I stand by vertex normals. anyone? ------------------------------ From: larsen@sunset.cs.utah.edu (Steve Larsen) Date: Mon, 22 Apr 96 12:00:17 MDT Subject: Re: Visibility lists > I've recently been messing with creating a homemade level from scratch, >but have run into some trouble. My test level is a simple 128x128x256 >room, with 2 leaves. The level runs okay, but I get some strange problems >during play. It seems that only the first leaf renders properly. (i.e. >draws all the walls, etc..) While in the second leaf, none of the walls >are drawn unless the back wall of the first leaf in in your line of sight. Is this room non-convex, or is there some other reason you have two leaves for one room? One thing you might check tho. I had a similar problem if I used the same plane for more than one surface. I am not sure why. I thought any surfaces that were co-planar would use the same plane for caching efficiency. This might still be the case, but I had a lot of problems whenever I tried it. Steve ------------------------------ From: Tom Wheeley Date: Mon, 22 Apr 96 00:36:59 GMT Subject: Quake map distribution: speed vs. legality In article you write: > * A distributable .bsp-file contains none of ids textures, but > "_texture" entries that tell a preprocessing utility how to > build the right .bsp-file from the distributable .bsp-file. > > All the surfaces that should have had one of ids textures, are assigned > a dummy texture in the distributable .bsp-file. This assignment is > changed by a preprocessing utility according to the > "_texture" entries. > > The preprocessing utility should also be able to reverse this process, > so you don't have to keep the distributable file as well as the > playable one. I wrote a similar utility to this ages ago, but you can only use id's textures :-) Maybe texture names in the texture list beginning with `_' would be picked up by the pre-pro as `filenames' (perhaps in a PAK file?) of mip textures, whereas standard names would be taken to be standard id tex. Remember that the mip header only gives 16 chars for the name (IIRC). People could be encouraged to keep a local .PAK file (or similar) of all their custom textures - -- an interface for this would have to be rigidly adhered to, but may prove too difficult to manage. :( The BSP file as it stands is a very limited structure, expansion wise. .splitbung - -- * TQ 1.0 * The 'Just So Quotes'. C++ -- The language in which only friends can access your private members. ------------------------------ From: mpolis@polbox.com.pl Date: Mon, 22 Apr 1996 20:35:55 +0200 Subject: Re: To seam or not to seam... >>yes i thought this was in the quake specs... > This is in the spec, indded. But that doesn't mean it's understandable for > everyone :-) (like 50% of the .BSP description). > Can someone take a look and propose a simpler explanation? Well, as usually in such situations we figured it out ourselves :) Here is a part of the source of our viewer: if(texture[face->v1].onseam && !face->facefront) { tp[0].x = texture[face->v1].tx + txcor; tp[0].y = texture[face->v1].ty; } else { tp[0].x = texture[face->v1].tx; tp[0].y = texture[face->v1].ty; } - -------------------------------------------------------------------- >> The only difficult part is placing the texture on the object. > And maybe generating the animation frames themselves... Second thought is obvious, and first one is right. Working on 2D picture to wrap it around 3D object in the way Quake does it is very difficult... - -------------------------------------------------------------------- >>there is no light info in the model files. > I confirm. Once again, the wording of the specs (lightnormalindex) > probably is just confusing. Someone has a better wording? Hmmm... We are thinking if id isn't just going to fake lightining on monsters. Using this normal we could make them Gouraud shaded, but with so many restrictions, that we can for a sure forget dynamic/various lights on the monsters... Guess we will have to wait till another test release :)... Well, it's just 3 weeks till E3. - -------------------------------------------------------------------- I new thing started to bug me. Michael Abrash said (on CGDC) that they use z-buffer for monsters. In no way I can believe it. We used quick-sort and there is almost no polygons glitching when displaying monsters. They are very cleverly modelled, probably not from scratch (we suspect they were build from thousands of polygons then some kind of polygon-reduction process was run; all SGI programs have such things and - otherwise than in 3D-Studio - they work fine). So why taking so much memory and processing power for z-buffer, when quick-sort or radix will be much better and have quality enough?... Adrian Chmielarz Metropolis ------------------------------ From: Bernd Kreimeier Date: Mon, 22 Apr 1996 21:08:07 +0200 (MET DST) Subject: Re: To seam or not to seam... >> I confirm. Once again, the wording of the specs (lightnormalindex) >> probably is just confusing. Someone has a better wording? Index refering to a predefined vertex normal sounds about right. I second that. Btw., the UQS should clearly state what is found in the MDL, and what is found in the EXE. >I new thing started to bug me. Michael Abrash said (on CGDC) that > they use z-buffer for monsters. You will have in the order of 10e1 polygons within view from the static environment. There are some 10e2 triangles in an MDL object. Each single object is more complex than an entire DOOM level. A wall polygon occupies up to 10e3 average (up to full view). Any triangle is likely to occupy a dozen pixels. Quoting from the CGDC transparencies: "Polygon models are meshes of 100-400 polygons, with a single front/back skin stretched over them. We couldn't clip them to the world BSP, because it would be too expensive, so we just drew each triangle in the nearest leaf it had a vertex in, which caused occasional errors. Errors sorting polygons within models. Errors sorting between models in same leaf (and also with other BSP models and sprites)." Conclusion: trying several alternatives, they settled for a z-buffer. Thus the rendering should look like this: They use the BSP front-to-back order for all environment polygons. Abrash says that, using an edge-sorted rasterizer, overdraw is zero. Thus a simple z-fill (write-only during BSP traversal) is not too expensive. Note that you calculate z for perspective correct texture mapping anyway for each pixel. I read a claim of 15% costs over the drawing. In a second pass, all possibly visible objects are rendered using the z-buffer (read-than-write), which is supposed to be less costly than sorting. I do not know wether BSP objects are treated the same like the MDL. I guess billboards (sprites) should better be. Actually, it surprised me a lot the first time I heard about it. Talk about preconceptions. The more you think about it, the more advantages you see. The z-buffered stuff could be anything: separate polygons, intersecting, even a depth map could be used. Triangles could intersect the walls (remember the lava/water). It will be interesting to see how this benefits from upcoming hardware z-buffering, too. In any case, I believe that Mike Abrash is right: it is the mixture of sophisticated spatial subdivision (BSP) and simple, straight processing of the visible triangles that works best. b. ------------------------------ End of quake-dev-digest V1 #3 ***************************** From owner-quake-dev-digest@gamers.org Wed Apr 24 00:23 MET 1996 Received: from gamers.org (majordomo@thegate.gamers.org [128.205.37.150]) by marvin.nero.uni-bonn.de (8.7.4/8.7.1) with ESMTP id AAA19548 for ; Wed, 24 Apr 1996 00:23:48 +0200 (MET DST) Received: (from majordomo@localhost) by gamers.org (thegate/gamers) id SAA30468 for quake-dev-digest-outgoing; Tue, 23 Apr 1996 18:23:39 -0400 From: owner-quake-dev-digest@gamers.org Date: Tue, 23 Apr 1996 18:23:39 -0400 Message-Id: <199604232223.SAA30468@gamers.org> To: quake-dev-digest@gamers.org Subject: quake-dev-digest V1 #4 Reply-To: quake-dev@gamers.org Errors-To: owner-quake-dev-digest@gamers.org Precedence: bulk X-gamers.org: quake-dev@gamers.org Content-Type: text Content-Length: 29126 X-Lines: 656 Status: RO quake-dev-digest Tuesday, 23 April 1996 Volume 01 : Number 004 ---------------------------------------------------------------------- From: Jim Bucher Date: Mon, 22 Apr 1996 14:49:29 -0500 Subject: Re: To seam or not to seam... > Can someone take a look and propose a simpler explanation if (!poly.onFront) for (i = 0; i < poly.numVerts; i++) if (poly.vert[i].onSeem) poly.vert[i].u += poly.textureWidth / 2; > I stand by vertex normals. anyone? I agree. ------------------------------ From: Jim Bucher Date: Mon, 22 Apr 1996 14:56:40 -0500 Subject: Re: rendering question Bernd Kreimeier wrote: > Use the BSP. Start at the root, do a dot product of camera > position vector and plane normal, compare with distance > to origin. This gives you wether you are in the left or > right subtree/halfspace. Repeat with the appropriate > child node, until you reach a leaf. Done. By camera position vector do you mean the forward vector of the camera or position of the camera in world space? Also, how do I compare with the distance to origin? Do I compare if the dot product is < or > the distance? It would be great if you could post some psuedo code. ------------------------------ From: Randy Linden Date: Mon, 22 Apr 1996 12:42:31 -0700 Subject: RE: To seam or not to seam... - ------ =_NextPart_000_01BB304D.B0D53B40 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable > I new thing started to bug me. Michael Abrash said (on CGDC) that >they use z-buffer for monsters. In no way I can believe it. Believe it, it's true -- they use a Z-Buffer for the Alias Models. There are a *multitude* of sorting problems that cannot be solved with = Z-based sorting. In *very* simple cases, you could take the "average" Z = of a given polygon and sort based on that, however with the models that = they have, many polygons interesect and overlap many other polygons = (both within the same model, and otherwise). BTW, If you're not having these problems with your displayer, try = looking at a different model...Many of them will exhibit the sorting = errors. Rand. ShockWave Studios, Inc. - ------ =_NextPart_000_01BB304D.B0D53B40 Content-Type: application/ms-tnef Content-Transfer-Encoding: base64 eJ8+IjQUAQaQCAAEAAAAAAABAAEAAQeQBgAIAAAA5AQAAAAAAADoAAENgAQAAgAAAAIAAgABBJAG ACABAAABAAAADAAAAAMAADADAAAACwAPDgAAAAACAf8PAQAAAEcAAAAAAAAAgSsfpL6jEBmdbgDd AQ9UAgAAAABxdWFrZS1kZXZAZ2FtZXJzLm9yZwBTTVRQAHF1YWtlLWRldkBnYW1lcnMub3JnAAAe AAIwAQAAAAUAAABTTVRQAAAAAB4AAzABAAAAFQAAAHF1YWtlLWRldkBnYW1lcnMub3JnAAAAAAMA FQwBAAAAAwD+DwYAAAAeAAEwAQAAABcAAAAncXVha2UtZGV2QGdhbWVycy5vcmcnAAACAQswAQAA ABoAAABTTVRQOlFVQUtFLURFVkBHQU1FUlMuT1JHAAAAAwAAOQAAAAALAEA6AQAAAAIB9g8BAAAA BAAAAAAAAANhNAEIgAcAGAAAAElQTS5NaWNyb3NvZnQgTWFpbC5Ob3RlADEIAQSAAQAeAAAAUkU6 IFRvIHNlYW0gb3Igbm90IHRvIHNlYW0uLi4APwkBBYADAA4AAADMBwQAFgAMACoAHwABAEMBASCA AwAOAAAAzAcEABYADAAlADUAAQBUAQEJgAEAIQAAADY4NzJDOUUzM0E5Q0NGMTE5RkU3NDQ0NTUz NTQwMDAwAAMHAQOQBgBoBAAAEgAAAAsAIwAAAAAAAwAmAAAAAAALACkAAAAAAAMANgAAAAAAQAA5 AACnbtiDMLsBHgBwAAEAAAAeAAAAUkU6IFRvIHNlYW0gb3Igbm90IHRvIHNlYW0uLi4AAAACAXEA AQAAABYAAAABuzCD2GfjyXJpnDoRz5/nREVTVAAAAAAeAB4MAQAAAAUAAABTTVRQAAAAAB4AHwwB AAAAFwAAAHJsaW5kZW5AY29ubmVjdG5ldC5jb20AAAMABhD6UjdpAwAHEDACAAAeAAgQAQAAAGUA AABJTkVXVEhJTkdTVEFSVEVEVE9CVUdNRU1JQ0hBRUxBQlJBU0hTQUlEKE9OQ0dEQylUSEFUVEhF WVVTRVotQlVGRkVSRk9STU9OU1RFUlNJTk5PV0FZSUNBTkJFTElFVkVJVEJFAAAAAAIBCRABAAAA 4QIAAN0CAACIBAAATFpGdUu8REr/AAoBDwIVAqgF6wKDAFAC8gkCAGNoCsBzZXQyNwYABsMCgzID xQIAcHJCcRHic3RlbQKDM3cC5AcTAoB9CoAIzwnZO/EWDzI1NQKACoENsQtg4G5nMTAzFFALChRR nQvyYwBAAzABkSA+Gc0VE1BvE9BjBUAgSSCSbgfRdGgLgGcgE8ALCsAT0GQdIG8gYnWrHXAHgC4F 0GkRcWUUoeBicmFzaB2AC3Ad8AIoAiAgQ0dEQykJHSFhdAqLbGkzNn8cIRt/HIMZzxrfG+wdMGWI eSB1EbAgei0eQPsN0ASQIAIQBcAEYACAE9ArEaAeoEkDoG4eIHdhayawHNBjA5FiHxAIkHZxJvBp dC4KjyPcKjVClSmXLCnxJwQgdHIKUAggLS0meGEgWi3+QidIJoEUsCGwH3AF0ARx7mwoUCo1KjVU JpAWEC6ggTHCICptdWx0KgDCdQ2wKiBvZh2AFbH/HVIcQQJgE+AtgSCxKTIosPcFQCmAMzFsKdAd 8APwHTB9LsFiH3Ad4TNFHqAocirZKdByeTLwAJBtC1Am8OspQBGwcy0weQhgKTAIYDJsHfFhaybw L6IiYeE3YWFnZSIuwDMCLrAsZ2kp0AOgcAbweWf/IBEAcDZkHjA2MyARIKItMPhob3cpwQXANbMv ogRi/zCANEQmgxGAKdAtMAOBJrB/O0UEIAuAKCEHkByCO8JvezdhC2BwP7QcYDGhQAgo/wbgNdE1 sguAL5MfsAeAPkRPLTBBU0JyA/FlKTCtQrRUVy0wSTMgOKEnMcH/NNI/YR1SJoEm4TPHNbM4oe0F wGQEAAtReQSQLTAtoPMmsBWgb2sdUjRxLrBKIK8nUgnwBUA+Uy5M0E1CIyszICaBbTWhbAMgZXj9 HUBiKgBEFDNVBJADYChBLTC8UjvBKiZTPUBja85XOeEGADKxaW84cSiAvmMqKCU/HIIqNRUxAFVw AAAAAwAQEAEAAAADABEQAQAAAEAABzDgNdgygzC7AUAACDDgNdgygzC7AR4APQABAAAABQAAAFJF OiAAAAAAd0A= - ------ =_NextPart_000_01BB304D.B0D53B40-- ------------------------------ From: "Brian K. Martin" Date: Mon, 22 Apr 1996 16:37:32 -0400 (EDT) Subject: Re: To seam or not to seam... > > > >>there is no light info in the model files. > > Hmmm... We are thinking if id isn't just going to fake lightining > on monsters. Using this normal we could make them Gouraud shaded, > but with so many restrictions, that we can for a sure forget > dynamic/various lights on the monsters... Guess we will have to > wait till another test release :)... Well, it's just 3 weeks till > E3. > ?? id Doesn't fake light. I am sure. these are the vertex normals and they are used for gouraud shading. The lighting on the monsters is indeed dynamic. That's why it says that in the quake specs. Believe me, I tested it and even implemented it in the newest version of meddle. (see that appendix in the specs for the normal table) I doubt id will change much about the MDL files (execpt maybe that bug of having invalid vertex normals in the MDL file). > -------------------------------------------------------------------- > > I new thing started to bug me. Michael Abrash said (on CGDC) that > they use z-buffer for monsters. In no way I can believe it. We used Carmack had told me that they do use a z-buffer. Look how nice the clipping is on the models when they stick in a wall. Also try to load up you memory with tons of things and then run quake in a hi res mode. You can get an error saying there isn't enough memory for the z-buffer. well that doesn't mean diddly crap but it is some evidence. Also notice that in some angles where you get an error in sorting, you don't see that in quake. (but you may have a better sorting algo than me..) He also said the reason for the z buffer was that in most cases the monsters are only a few pixels in size so the z-buffer wasn't used heavily, so it's not too time consuming. But I have to agree with you that it is hard to believe because I can never fill the z-buffer that fast. brian brian ------------------------------ From: Chris Carollo Date: Mon, 22 Apr 1996 06:51:55 -0400 Subject: Re: Map Files Bernd Kreimeier wrote: > In my opinion, there are the following processing steps that have to > be done *within QuakeEd*: > > define/modify planes of a single brush > calculate a boundary representation of the brush. > based on plane-plane-intersections > add brush to the map as already done > > Note that the boundary representation is necesary, as human beings are > not likely to think in infinite planes. We need the building blocks to > be convex polyhedra, solid bricks of material. See QuakeEd screenshots, > the top-down view. I concur. IMO, the following steps are necessary: 1. Load MAP file and convert brushes from list-of-planes to vertex-edge representation. 2. Allow users to move vertices, add/move brushes, and move/add edges. Possible checks here that the sides of the brush remain coplanar. Or, the editor could restrict the user to only moving vertices in such a way as to preserve coplanarity...but this seems like it would be overly complex and not really needed. Comments? 3. Convert brushes from vertex-edge list-of-planes representation. If coplanarity wasn't checked before, definitely do it here. As I see it, the only operation that is really complex is #1, and possibly the coplanar checks. I'm sure there is information out there on calculating the intersections of multiple planes, though. > Note that all planes of one brush do intersect, but that planes of > different brushes do not intersect. Brush-brush intersection > is calculated using CSG with the polygons, not the planes. True. Though you have to take into account case where polygons of one brush lie completely in the interior of another brush. In this case, the polygons won't intersect, but still need to be clipped. I'm sure this is documented in a CSG source somewhere. > What does "sealing the world" mean (mentioned by Abrash and Carmack), > but removal of all outside surfaces that cannot be seen from > the interior? This is #1 on my question list - how does qbsp determine that certain surfaces are "outside" the map? Like in the cube map that Carmack gave us...how does it know that only 6 surfaces are ultimately going to be used? - -Chris ------------------------------ From: "Drizzt Do'Urden" Date: Mon, 22 Apr 1996 15:22:46 -0700 (PDT) Subject: Re: Visibility lists > Is this room non-convex, or is there some other reason you have two leaves > for one room? No, the room is convex. The reason for having two leaves for the room is because I get the "Surface Extent > 256" error if I don't use two. I ran into that problem before while using one leaf, even when the surfaces were smaller than 256. > One thing you might check tho. I had a similar problem if I used the same > plane for more than one surface. I am not sure why. I thought any surfaces > that were co-planar would use the same plane for caching efficiency. This > might still be the case, but I had a lot of problems whenever I tried it. As far as the surfaces on the planes go. My view is this: id uses multiple surfaces on single planes, so I will too. Although currently, I am having problems with it as you did. Not to put down first.bsp and tworooms.bsp, but as far as following ids format, and the rules set down in the QuakeSpecs, they are wrong. A few things I noticed: testx.bsp maps NEVER use negative vectors for planes unless that plane is slanted. So you will never see: - -1.000000 0.000000 0.000000 etc... This was done in both first and tworooms. Also, tworooms defines multiple planes for the same plane in 3D space. The quake specs say not to do this. The visibility lists for these two levels contains one entry...255. While the level works, this can't be right either. There's also the fact that the surface list is basically not used. The entries mimic the surface file. I also noticed that weapons don't stop at the walls in tworooms. (though this could make for an interesting deathmatch) I'm almost sure the problems with my level are related to the visibility list, and perhaps the surface list. I have no idea how many entries the vislist should contain. test1 contains about 494 leaves, and has over 14,000 entries in the vislist, so it would seem the vislist entry to leaf ratio is fairly high. I suppose there is some mathematical formula that could be used to determine an aproximate number of entries. I have yet to find it. Any help in this area would be greatly appreciated. Brent ------------------------------ From: Mike Ruete Date: Mon, 22 Apr 1996 21:48:56 -0400 Subject: RE: Visibility lists >test1 contains about 494 leaves, and >has over 14,000 entries in the vislist, so it would seem the vislist >entry to leaf ratio is fairly high. I (with my limited understanding of BSPs) would guess that you would probably *not* see a linear relationship between leaves and vislist entries. I would think the vislist would get a lot bigger a lot faster as you got more leaves... _/_/_/ _/_/_/_/ _/ _/_/ ruetem@lafayette.edu _/_/_/_/ _/ _/ _/ ftp://139.147.124.250 _/ _/ _/ _/ _/_/_/ http://139.147.124.250/index.htm _/ _/ _/ _/ _/ _/ _/ a.k.a.=> Gripp (all you ifraggers know and _/ fear me... Well, not all of you...:) "Everything is aerodynamic if you throw it hard enough." ------------------------------ From: Mike Ruete Date: Mon, 22 Apr 1996 21:48:55 -0400 Subject: RE: Map Files > Or, the editor could restrict the user to only moving vertices in > such a way as to preserve coplanarity...but this seems like it would > be overly complex and not really needed. Comments? Actually, once you have the equation of a plane, it's pretty easy to test whether a point is still on it... Just plug it in. Getting the equation of the plane, on the other hand, is the harder part. However, if Quake stores info on surface normals, that makes the job much easier. The plane equation is just x*i + y*j + z*k = C where is any normal vector to the plane (doesn't have to be a unit vector). If you have the normal, and a single point on the plane (like a vertex), just calculate to get C. Now, I've probably just told you all something you already knew........ _/_/_/ _/_/_/_/ _/ _/_/ ruetem@lafayette.edu _/_/_/_/ _/ _/ _/ ftp://139.147.124.250 _/ _/ _/ _/ _/_/_/ http://139.147.124.250/index.htm _/ _/ _/ _/ _/ _/ _/ a.k.a.=> Gripp (all you ifraggers know and _/ fear me... Well, not all of you...:) "Everything is aerodynamic if you throw it hard enough." ------------------------------ From: Stephen Crowley Date: Mon, 22 Apr 1996 21:40:04 -0500 Subject: RE: Map Files - ------ =_NextPart_000_01BB3094.73571300 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable - ---------- From: Chris Carollo[SMTP:carollo.1@osu.edu] Sent: Monday, April 22, 1996 5:51 AM To: quake-dev@gamers.org Subject: Re: Map Files >Bernd Kreimeier wrote: >> In my opinion, there are the following processing steps that have to >> be done *within QuakeEd*: >>=20 >> define/modify planes of a single brush >> calculate a boundary representation of the brush. >> based on plane-plane-intersections >> add brush to the map as already done >>=20 >> Note that the boundary representation is necesary, as human beings = are >> not likely to think in infinite planes. We need the building blocks = to >> be convex polyhedra, solid bricks of material. See QuakeEd = screenshots, >> the top-down view. >I concur. IMO, the following steps are necessary: >1. Load MAP file and convert brushes from list-of-planes to vertex-edge > representation. >2. Allow users to move vertices, add/move brushes, and move/add edges. = > Possible checks here that the sides of the brush remain coplanar. > Or, the editor could restrict the user to only moving vertices in > such a way as to preserve coplanarity...but this seems like it would > be overly complex and not really needed. Comments? >3. Convert brushes from vertex-edge list-of-planes representation. =20 > If coplanarity wasn't checked before, definitely do it here. >As I see it, the only operation that is really complex is #1, and=20 >possibly the coplanar checks. I'm sure there is information out there >on calculating the intersections of multiple planes, though. The way I'm trying to implement plane intersection code is to. First get a list of all the vertices 1. Take 3 planes from the list 2. Use the first 2 and get the line where they intersect (hopefully this = is easy) 3. Find where that line intersects the 3rd plane, this will be the = vertex , add it to the list (be sure check for dups before adding) 4. repeat step 1 until all combinations of planes are used. Now that we have a list of vertices: find all the edges they intersect 1. Take 2 vertices from the list 2. Create a line from vertex1 to vertex2 (x1,y1,z1) to (x2,y2,z2) 3. Scan through the list of planes and see if the line lies on both = planes, if it does then it's an edge, add it to the list (check for = dups) ( if a line is parallel or list on a plane then = A(x1-x2)+B(y1-y2)+C(z1-z2) will equal 0 (at least I read that yesterday, = I haven't tried it yet) 4. repeat step 1 until all combinations of vertices are used Note: In theory this should work. However, reality is a different story. = :-) =20 I hope there is be a better way to do this. This seems rather slow.=20 >> Note that all planes of one brush do intersect, but that planes of >> different brushes do not intersect. Brush-brush intersection >> is calculated using CSG with the polygons, not the planes. >True. Though you have to take into account case where polygons of >one brush lie completely in the interior of another brush. In this >case, the polygons won't intersect, but still need to be clipped. =20 >I'm sure this is documented in a CSG source somewhere. All planes in a surface do intersect, except for the ones that are = parallel of course. Stephen - ------ =_NextPart_000_01BB3094.73571300 Content-Type: application/ms-tnef Content-Transfer-Encoding: base64 eJ8+IhcCAQaQCAAEAAAAAAABAAEAAQeQBgAIAAAA5AQAAAAAAADoAAENgAQAAgAAAAIAAgABBJAG ACABAAABAAAADAAAAAMAADADAAAACwAPDgAAAAACAf8PAQAAAEcAAAAAAAAAgSsfpL6jEBmdbgDd AQ9UAgAAAABxdWFrZS1kZXZAZ2FtZXJzLm9yZwBTTVRQAHF1YWtlLWRldkBnYW1lcnMub3JnAAAe AAIwAQAAAAUAAABTTVRQAAAAAB4AAzABAAAAFQAAAHF1YWtlLWRldkBnYW1lcnMub3JnAAAAAAMA FQwBAAAAAwD+DwYAAAAeAAEwAQAAABcAAAAncXVha2UtZGV2QGdhbWVycy5vcmcnAAACAQswAQAA ABoAAABTTVRQOlFVQUtFLURFVkBHQU1FUlMuT1JHAAAAAwAAOQAAAAALAEA6AQAAAAIB9g8BAAAA BAAAAAAAAANhNAEIgAcAGAAAAElQTS5NaWNyb3NvZnQgTWFpbC5Ob3RlADEIAQSAAQAOAAAAUkU6 IE1hcCBGaWxlcwAiBAEFgAMADgAAAMwHBAAWABUAKAAEAAEALwEBIIADAA4AAADMBwQAFgAVAAcA HAABACYBAQmAAQAhAAAARjBDQTM1Njg3QjlDQ0YxMUIzNUE0NDQ1NTM1NDAwMDAA/QYBA5AGAKAK AAASAAAACwAjAAAAAAADACYAAAAAAAsAKQAAAAAAAwA2AAAAAABAADkAoH8qLb4wuwEeAHAAAQAA AA4AAABSRTogTWFwIEZpbGVzAAAAAgFxAAEAAAAWAAAAAbswvizeaDXK8Zx7Ec+zWkRFU1QAAAAA HgAeDAEAAAAFAAAAU01UUAAAAAAeAB8MAQAAABIAAABzdGVwaGVuY0BmcmVlLm9yZwAAAAMABhA3 dzUqAwAHEKcJAAAeAAgQAQAAAGUAAAAtLS0tLS0tLS0tRlJPTTpDSFJJU0NBUk9MTE9TTVRQOkNB Uk9MTE8xQE9TVUVEVVNFTlQ6TU9OREFZLEFQUklMMjIsMTk5NjU6NTFBTVRPOlFVQUtFLURFVkBH QU1FUlNPUkdTAAAAAAIBCRABAAAAMAkAACwJAABzFQAATFpGdQtosrb/AAoBDwIVAqgF6wKDAFAC 8gkCAGNoCsBzZXQyNwYABsMCgzIDxQIAcHJCcRHic3RlbQKDM3cC5AcTAoM0EQUTUw/fZt41A0UT NQdtAoM2EswUxS59CoAIzwnZOxu/MjUeNQKACoENsQtgbmcxDDAzFFALA2xpMTiCMALRaS0xNDQN 8LcM0CAjC1kxGYATUG8T0PpjBUAtIkcKhyD7DDAhxjpGA2E6I04hxgyCIEN2aAUQBCBDCsAG8BtQ W0BTTVRQOmMndC5AMUBvc3UuCYB1fl0i7yP9BmACMCUvJjtN4QIgZGF5LBSwE1ADEQQyMi3QMTk5 NiDQNTo1MRSwTSlfI/0MVG8rnyY7cXVha4RlLQ2wdkBnYQeANRGgLgWwZy9fKm51Yk5qIgExfyY7 UmU3AE38YXAk0AMQB5AKhQqLH4AcMzYgxxdRC/A0ID4vC0YUUQvyIcZCBJFkIE5LG8AHcQiRIHch 0jpHNJ07zzzcPiBJA6Bt0Hkgb3ALgGkCIC3Q5HRoBJBlIArAQ0BDAV4gAhAnoQPwHsAgIcFjbweQ AJBEURPBcAQgQwBh6wVAEYB2Q4FvPx9AL0E82mJDQGQCIENAKgPwQwCJC4AgUTNiRWQqPw//R19B LUrvS/9BPFDSDbELgPxlLwRhBpBCUAtRSaAEIHxvZkNQRSBEQTmASUByuHVzaE3vTv9QDyAoMHhs Y3ULYBPQUpEG4HX9LZFyQlAbwBNQB5ArYUWw70KxUmJDolMzLlOPVJ9Vr3lQ0WJhEbA98FjRUgMt /13EC4AT0BGhIhBCsTmmWk/zW19QeWFkPfBTM0YhQ5PvAMA5QF1AQ1BsG8BikEJQf0mCX19gb00P ZQ9mH0FpTv8h4UWEWTNXn1ikJzFJoESx52wBLdBj4Wh1A4JJUERBX2PxG8Bn32jvQTxuIeAgux+A M4BsQlBjMwuAa20gPW0RblFBSfBDQFIELiDeV0NASaBdYVkzdQMQUbD3RFECYESga0VxRk9wP0hv t1awAiBGAHhEcAbweUMQqGRyYS3QcwbwaWKy/ml2MlJxAMBeoQcxdJAGYH9DQEpVRSAFAAnhU2Ah 4HO+LHafd69BPEOidnBwM6DrRCADoHYIkHdZxn4Pfx9tPPpJebJW8HJ0kEIATf5PQuND2UU0Q2Jt Y22iStaXgp+Drzz6MXSQTG9ikPkF0EFQQ9A5cUNQPeF5w78AIFMkB5EDUnJhE8AtUnBfXhR2UoHA jXF6AC0JgGf/by+KDzzrUNBYHFnPkV886+oydJBBRAIgU1A0IWMi/wRgRgGNYntgB5Bt4WKgUYHf RgGNtW3hPeGYQi9ikpASz3SBiP+VT5JtIFAo0ACQ/wJgeaFDEHYyQxNrJwCQDbD/UlNZN1gBAMBK IQWgUgIKwOeUP5yvnb5PcoZUCYBJ8N8FsQWgVwA98FhBdHtRa1T/l7JjIgIgcrGYQURCmJZzYb+i z6Pfnc0o4BFwUpF3LbB3Y9JjMVgzckYBojZJ8Hn+Lq9AdXBrUicxEbAT4AQg93JybSAFQHem0qnv qv+dzdtJUZhRcnKxBaBtC1B6Af+M8nIyZDEnoEJQdOIJgIXxzQhQbQeAAjBzP7E/sk/9PPozdJAI UI1fjmCPqY5+75Ndm4+4b7M/SVKArpmtUfhzbicFQJ9DXWFJUAIQ/xvALdBRI3PxcrFJgLCiQxLv gh+/L8A/IhFBBCCFcLAB/7ChhlSoc0JwBJBYpEWTJzHnteW05icxIzGaNMXfxu//PPp6MJ7TcsFD saI2nzWF8v4njmAo4EN0QzEnMXOhBbD/e+FYw6+DQyHM383vPPpY0f9WxkRCQ6Jei3ujVwBYsLUR 91H1QuIIYGdZuQsZ1QXatd5UQ7GtYtGip1B516PEwf+1ArcSUfTYG3mxDbBtInZw/6K2OWARoAVA kDAFQFKgjoK/UmMnoEOTmJbatYvhVDNxf7pAUfaOM0OijoLatZchVf8RsEOU4TMR4Izy4YLlNEmh mneftWVCUF6HICh9sH3KIGZXANAT0pIEIGRAc/x5Kdq1ulE5YD3h6GZFsf/oE16HRXLkMQsgUfRC 4icx/wPw4nFJUeKmegGZE7CiYzX94eMoSVHR459DQ9EFwCkg30Vhw4RigkRB6yY0dJBYEf9kQAVA RTIugJegAjADEeJi/bThYguAWKNSU1IFQ2KXsd+2oDm8atAH4EWTd0NAReP/4ciYljcAUUE98OJm myPovd/jbRHgqTfk7+X0Q2QxVzNf6BO7iS8Qj3cR4CgggCziecxgejEpYyICwC5g0nkuYHoy6ylT VsDKkv8XgNpx8Pj26T3hyQNZFOgT/x+AUkJucSHgYxDZxgdhsLHnSYD8RG0RdCcGwpsT8E/38VPy LOsmKFDQB2EA1Scx/9rhtgFyoEJg+NDh5G5wUqAr3tQKI0ECwS0CkCkrNEIoAwAtA+ARcEMobQMw LQQR7wRlM1H1sDC/6aDsourhhVJkMkWEeacx/z3ALaOFcEXiwsKnUV1hsLH9FOB08+/0//YPqTf3 hvge/z7hQgJDAaaQ6kV9oabisOD0cmt0kEhEIDPAPcAt0N+14sJSJzFSoFGxZkMh3qHnGBAc0XSQ Oi3rJlzE2rX/FZHKEdIoSVFXYeGQXqGtU/9jMcSxr7Lj4a/IykFDEUUg/5dxdJA5vzrP1R9p72r2 4mL/UghJkmLUxLJelhVwr3RFsf9SB9QfKI9BPB+YjbbEsXIy616HdJBCU0ItYtReii6ffy+vQTwf QVbHPfD3wERCQ7xTR+8BCMFDonoyZ18h/xVwcjI6I3RExW81/zcP4aC+VFNAxUBQ0NzQBWN504Cf RdZC8OQSXoFjQGFjpsH/3qFWwOZh6GQ6Zi5vPU/WD/+hRgghtNXEY0oh1+eUAPjQ/1JycjElsll0 hgHKkv+QQ2//RH/AukIChlRCt7DgwsIszb8YEO8idORjQHmSJ5BwyiD/tqJKf0uPhLvRuOqEgYBW 8P/eghZiEBI5knrghdDjMHrR/96A6GPar9u/l0IrRlYj0eG+ZkGAa5AsnHoA4zBw4aD/8oLJhPxD KuJCgg8HwbKF0PfmYDvubMBiBNAYIQoxJs+tJ9c2wJxXxX1XwABkIAMAEBAAAAAAAwAREAAAAABA AAcwAKUyn7kwuwFAAAgwAKUyn7kwuwEeAD0AAQAAAAUAAABSRTogAAAAAHwr - ------ =_NextPart_000_01BB3094.73571300-- ------------------------------ From: Bernd Kreimeier Date: Tue, 23 Apr 1996 10:16:08 +0200 (MET DST) Subject: RE: Visibility lists >From: Mike Ruete > I (with my limited understanding of BSPs) would guess that you would >probably *not* see a linear relationship between leaves and vislist entries. >I would think the vislist would get a lot bigger a lot faster as you got >more leaves... Let's do some guesstimates: the worst case is that every leaf is potentially visible to every other leave, thus O( sqr(N) ). Average case: To get a level framerate, any coder could only hope the level designers take into consideration requirements like: the average number of polygons to be clipped per frame should not vary too much. As Abrash wrote: no matter how fast the hardware, or how sophisticated the renderer, they will just add more polys and create more complex geometries. Assume some not too much varying average of polys/leaf (any cube is fine, any fine-grained approximation of a sphere like some 320-hedron of course contradicts this assumption, but let's stick with euclidian geometry for convenience sake). To get constant average polys/frame, both polys/leaf and visible leafs/frame have to be approx. constant (of course, a level designer could always trade less complex leafs to get a larger range of view - prime example will be outdoor areas). In conclusion, the average case could indeed be a linear relationship between number of vislist entries and number of leafs, assuming that RLE encoding will be able to compress all the zero flags to some constant overhead. Anybody care to comment on RLE performance? However, the average case looks pretty much like being the best as well. So Mike is probably right: we will face something that is worse than linear, but luckily not as bad as quadratic. b. ------------------------------ From: Bernd Kreimeier Date: Tue, 23 Apr 1996 10:33:16 +0200 (MET DST) Subject: z-buffer (was: to seam ...) >From: "Brian K. Martin" >But I have to agree with you that it is hard to believe >because I can never fill the z-buffer that fast. The following as a quote from the Game Programming mailing list at majordomo@inquo.net, from a recent posting by Scott C. Cottrille: >And the interesting thing to note from Chris [Hecker]'s article is >that he (and now id, I believe they borrowed Chris's code) has >ordered and scheduled his texture mapper's inner loop instructions >in such a way that the perspective division does not cost him any >cycles. That is, he's not sitting there waiting for it to complete. >He's using linear interpretation between everything 8th or 16th >pixel, at which point he recalibrates by dividing. If you perform >the initial 2 divisions outside the loop, then the inner division >is for the next z value you will need. 7.5 texturing cycles/pixel >average! IIRC he refers to Chris Heckers perspective texture mapping article series in the Game Developer Magazine, issues Apr/May to Aug/Sep 95 and Dec/Jan 96 - anybody happen to have access to these and could confirm the claims above? The point being: in this inner loop, you will have to increment an offset into the z-buffer (one ADD), and to write the the 1/z value already computed. I guess that, using float registers, you have the integer register to spare. I do not do assembly, but from a laymans point of view, this should be two cycles at least, or approx. 25% overhead. To match that 15% claimed, it would have to be less effectively. Hmm.. Of course, the really neat thing about this architecture is that you do not have to clear the z-buffer. b. ------------------------------ From: jschuur@flash.globalnews.com Date: Tue, 23 Apr 1996 11:17:28 +0000 (GMT) Subject: john carmack's work log on the net incase you haven't heard: john carmack has made his work log available via his .plan file. you can now finger johnc@idsoftware.com for a regular update of his bug fixes/changes and notes since the release of qtest1. a version on the web is available at http://www.nuqneH.org/aftershock/ in the news section. -- joost schuur, Online Magic Ltd. ------------ Tel: +44 171 820 7766 -- ------------------------------------------------------------------------ ------------------------------------------------------------------------ - --- http://jalad.globalnews.com/~jschuur/ - jschuur@onlinemagic.co.uk -- ------------------------------ From: Chris Carollo Date: Mon, 22 Apr 1996 19:20:33 -0400 Subject: Re: Map Files Stephen Crowley wrote: > > The way I'm trying to implement plane intersection code is to. [algorithm snipped] > Note: In theory this should work. However, reality is a different > story. :-) I'm going to be talking to one of my professors whose research is in optimizing 3-d intersection calculating, so hopefully he can show me a good way to do this. I'll post if I learn anything interesting. (Though the method you described was basically what I had in mind for calculating the vertex & edge list) > >True. Though you have to take into account case where polygons of > >one brush lie completely in the interior of another brush. In this > >case, the polygons won't intersect, but still need to be clipped. > >I'm sure this is documented in a CSG source somewhere. > > All planes in a surface do intersect, except for the ones that are > parallel of course. True. My point was that polygons that lie completely in the interior of another brush need to be clipped out of existance, even though they might not intersect with any of its polygons. - -Chris ------------------------------ From: amoon@odin.mdn.com (Alex R. Moon) Date: Tue, 23 Apr 1996 17:24:45 -0500 (EST) Subject: Re: Map Files Chris Carollo wrote: > 2. Allow users to move vertices, add/move brushes, and move/add edges. > Possible checks here that the sides of the brush remain coplanar. > Or, the editor could restrict the user to only moving vertices in > such a way as to preserve coplanarity...but this seems like it would > be overly complex and not really needed. Comments? Since the user can only easily indicate 2 dimensions of a point (graphically, on a monitor, at least :), the program should transparently calculate the third dimension of the point such that all of the surfaces involved remain planar. This way you don't have objects splitting up into hundreds of planes you didn't intend every time you move a vertex. - -- Alex R. Moon | "A university is what a college become when the amoon@odin.mdn.com | faculty loses interest in students." 71513.1453@compuserve.com | -- John Cardi ------------------------------ End of quake-dev-digest V1 #4 ***************************** From owner-quake-dev-digest@gamers.org Fri Apr 26 22:54 MET 1996 Received: from gamers.org (majordomo@thegate.gamers.org [128.205.37.150]) by marvin.nero.uni-bonn.de (8.7.4/8.7.1) with ESMTP id WAA28731 for ; Fri, 26 Apr 1996 22:53:29 +0200 (MET DST) Received: (from majordomo@localhost) by gamers.org (thegate/gamers) id QAA03520 for quake-dev-digest-outgoing; Fri, 26 Apr 1996 16:53:10 -0400 From: owner-quake-dev-digest@gamers.org Date: Fri, 26 Apr 1996 16:53:10 -0400 Message-Id: <199604262053.QAA03520@gamers.org> To: quake-dev-digest@gamers.org Subject: quake-dev-digest V1 #5 Reply-To: quake-dev@gamers.org Errors-To: owner-quake-dev-digest@gamers.org Precedence: bulk X-gamers.org: quake-dev@gamers.org Content-Type: text Content-Length: 28254 X-Lines: 645 Status: RO quake-dev-digest Friday, 26 April 1996 Volume 01 : Number 005 ---------------------------------------------------------------------- From: Chris Carollo Date: Tue, 23 Apr 1996 09:14:22 -0400 Subject: Re: Map Files Alex R. Moon wrote: > > Since the user can only easily indicate 2 dimensions of a point (graphically, > on a monitor, at least :), the program should transparently calculate the > third dimension of the point such that all of the surfaces involved remain > planar. This way you don't have objects splitting up into hundreds of planes > you didn't intend every time you move a vertex. Of course, this only works if the camera view is perpendicular to the plane being edited. - -Chris ------------------------------ From: Uffe Friis Lichtenberg Date: Wed, 24 Apr 1996 14:40:22 +0200 (METDST) Subject: Re: Map Files On Mon, 22 Apr 1996, Chris Carollo wrote: > 2. Allow users to move vertices, add/move brushes, and move/add edges. > Possible checks here that the sides of the brush remain coplanar. > Or, the editor could restrict the user to only moving vertices in > such a way as to preserve coplanarity...but this seems like it would > be overly complex and not really needed. Comments? As I see it, the easiest way to do this, as well as the easiest way to work with it, would be to convert the input from a .map file to a triangle mesh. This way moving points could never destroy coplanarity. When saving the .map file again the triangle mesh is then converted into a plane intersection representation (not difficult -- one plane per triangle, unless triangles are co-planar). Ofcourse you would also need to have some sort of editing tool to align triangles on a plane to avoid getting too many planes. Also the editor must still ensure that the triangle mesh stays convex, otherwise it can't be converted to a `plane-intersection-mesh' again. BTW: would it be too difficult for a human to work directly with the planes? If the user worked with the planes directly none of these problems would exist. (Plane-plane intersection is reasonably easy to do in real-time, as long as we don't get overtly many planes in a single brush.) > True. Though you have to take into account case where polygons of > one brush lie completely in the interior of another brush. In this > case, the polygons won't intersect, but still need to be clipped. > I'm sure this is documented in a CSG source somewhere. I don't think the editor has to deal with this. This happens in qbsp as I understand it. Zonk, Uffe. [uphfe] uffefl@diku.dk - -- "This .signature hasn't been left unintentionally void of blankness" ------------------------------ From: Bernd Kreimeier Date: Wed, 24 Apr 1996 14:58:14 +0200 (MET DST) Subject: Re: Map Files >From: Uffe Friis Lichtenberg >BTW: would it be too difficult for a human to work directly with the >planes? If the user worked with the planes directly none of these >problems would exist. (Plane-plane intersection is reasonably easy to do >in real-time, as long as we don't get overtly many planes in a single >brush.) It will not be a problem, as long as visual feedback is guaranteed (see below). See my sketchy proposal of QED on the support/info pages. In some "Brush Edit" mode/tool, the user could simply move the plane along the normal (increase/decrease distance from origin). But you will have to show him the resulting Brush as a polyhedra (edges, vertices / hence intersection for each update). Even the number of planes does not matter: select one polygon of the polyhedron (mouse click), then change distance. Same for changing the normal (e.g. mouse/cursor movement does rotation in azimuth, altitude angle). It is the visual feedback that matters for interactive editing. >> I'm sure this is documented in a CSG source somewhere. > >I don't think the editor has to deal with this. This happens in qbsp as I >understand it. The editor has to *show* brushes as polyhedra (see above). It must be obvious which brush a given plane belongs to. According to John Carmack, there are polyhedra operations in QuakeEd. I keep wondering about how much 3D preview QuakeEd provides - there are some remarks in his work log indicating that this is still improved, if I am not mistaken. Brush Editing and map editing uses Brushes is entirely different from triangle/poly/spline based modeling. I guess conversion from WAD to MAP and, subsequently, from DXF/3DS/.. to MAP will be very interesting indeed. Of course, one could always extend each polygon to a solid brush with minimal thickness, and let "qbsp" sort it out. b. ------------------------------ From: Mike Ruete Date: Wed, 24 Apr 1996 13:18:27 -0400 Subject: RE: Map Files >> Since the user can only easily indicate 2 dimensions of a point (graphically, >> on a monitor, at least :), the program should transparently calculate the >> third dimension of the point such that all of the surfaces involved remain >> planar. This way you don't have objects splitting up into hundreds of planes >> you didn't intend every time you move a vertex. > >Of course, this only works if the camera view is perpendicular to the plane >being edited. This is a common problem with CAD. That's why there's usually a "construction plane" setting, which can be set chosen in many ways including selecting two line-segments that lie in the plane. It's also nice to be able to change a view angle so that the plane you're editing is parallel to the screen. _/_/_/ _/_/_/_/ _/ _/_/ ruetem@lafayette.edu _/_/_/_/ _/ _/ _/ ftp://139.147.124.250 _/ _/ _/ _/ _/_/_/ http://139.147.124.250/index.htm _/ _/ _/ _/ _/ _/ _/ a.k.a.=> Gripp (all you ifraggers know and _/ fear me... Well, not all of you...:) "Everything is aerodynamic if you throw it hard enough." ------------------------------ From: Stephen Crowley Date: Wed, 24 Apr 1996 17:53:31 -0500 Subject: RE: Map Files - ------ =_NextPart_000_01BB3207.86AA7AE0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable - ---------- From: Alex R. Moon[SMTP:amoon@odin.mdn.com] Sent: Tuesday, April 23, 1996 12:24 PM To: quake-dev@gamers.org Subject: Re: Map Files >Since the user can only easily indicate 2 dimensions of a point = (graphically, >on a monitor, at least :), the program should transparently calculate = the >third dimension of the point such that all of the surfaces involved = remain >planar. This way you don't have objects splitting up into hundreds of = planes >you didn't intend every time you move a vertex. I'm thinking about taking a different approach. 1. Convert the planes into a vertex-edge representation 2. When a vertex changes position, recalculate all the planes, that the = points lies on, normal & dist. 3. When recalculation the planes normal move all the vertices on that = plane so that they stay on the plane (note: the vertex you are moving = will already be on the plane, so move all the others by repeating step2 = until all vertices lie on the plane) This will have a pretty neat effect when moving vertices, because it may = inadvertanly (sp?) move every vertex in the brush, but it would still = look similar. Strange eh? Hope that was not too confusing.=20 Stephen - ------ =_NextPart_000_01BB3207.86AA7AE0 Content-Type: application/ms-tnef Content-Transfer-Encoding: base64 eJ8+IiYWAQaQCAAEAAAAAAABAAEAAQeQBgAIAAAA5AQAAAAAAADoAAENgAQAAgAAAAIAAgABBJAG ACABAAABAAAADAAAAAMAADADAAAACwAPDgAAAAACAf8PAQAAAEcAAAAAAAAAgSsfpL6jEBmdbgDd AQ9UAgAAAABxdWFrZS1kZXZAZ2FtZXJzLm9yZwBTTVRQAHF1YWtlLWRldkBnYW1lcnMub3JnAAAe AAIwAQAAAAUAAABTTVRQAAAAAB4AAzABAAAAFQAAAHF1YWtlLWRldkBnYW1lcnMub3JnAAAAAAMA FQwBAAAAAwD+DwYAAAAeAAEwAQAAABcAAAAncXVha2UtZGV2QGdhbWVycy5vcmcnAAACAQswAQAA ABoAAABTTVRQOlFVQUtFLURFVkBHQU1FUlMuT1JHAAAAAwAAOQAAAAALAEA6AQAAAAIB9g8BAAAA BAAAAAAAAANhNAEIgAcAGAAAAElQTS5NaWNyb3NvZnQgTWFpbC5Ob3RlADEIAQSAAQAOAAAAUkU6 IE1hcCBGaWxlcwAiBAEFgAMADgAAAMwHBAAYABEANQAfAAMAVwEBIIADAA4AAADMBwQAGAARABYA HQADADYBAQmAAQAhAAAAOEY4NDQwMjVGNDlEQ0YxMUIzNUE0NDQ1NTM1NDAwMDAA5AYBA5AGANAF AAASAAAACwAjAAAAAAADACYAAAAAAAsAKQAAAAAAAwA2AAAAAABAADkAQEIn3DAyuwEeAHAAAQAA AA4AAABSRTogTWFwIEZpbGVzAAAAAgFxAAEAAAAWAAAAAbsyMNv0JUCEkJ30Ec+zWkRFU1QAAAAA HgAeDAEAAAAFAAAAU01UUAAAAAAeAB8MAQAAABIAAABzdGVwaGVuY0BmcmVlLm9yZwAAAAMABhAs X8GLAwAHELQDAAAeAAgQAQAAAGUAAAAtLS0tLS0tLS0tRlJPTTpBTEVYUk1PT05TTVRQOkFNT09O QE9ESU5NRE5DT01TRU5UOlRVRVNEQVksQVBSSUwyMywxOTk2MTI6MjRQTVRPOlFVQUtFLURFVkBH QU1FUlNPUkdTAAAAAAIBCRABAAAAXQQAAFkEAAALCAAATFpGddfvUj//AAoBDwIVAqgF6wKDAFAC 8gkCAGNoCsBzZXQyNwYABsMCgzIDxQIAcHJCcRHic3RlbQKDM/cC5AcTAoM0A0UTNQdtAoP2NRLM FMV9CoAIzwnZAoAHCoENsQtgbmcxMDODFFALA2xpMTQ0AtE8aS0cYwzQHGMLWTE21wqgA2AT0GMF QC0fBwqH1x27DDAehkYDYTogDh6GowyCFLBsZXgH8C4F0AJvAiBbU01UUDo2YQRgAiBABHALgC5t 5mQlcAWgbV0fryC9BmAXAjAh7yL7VApQc2RhnHksFLATUAMRMjMqoBAxOTk2K1AyOjIwNCBQTSYf IL1UbwMoXyL7cXVha2UtMQ2wdkBnJOAEkHMujQWwZyw/Jy51YmoewRMuXyL7UmUz4E1hcP8hkAMQ B5AKhQqPC5EVYQvwfSvwPgtGFFEL8ieXC4Bj0GUgdGg6cHURsAXABmMDkQIgbHkgZWF/AJA7gQuA JVA7IBPQKxAgHyVQB4AAgQIgBCBvZiCwYSBwbwuABUAoCcDVNhBoPFFsO4AsMX04T985XAIgPaEE YAMAdAWwKqCdPHAgI9A7wAVAOikqoIc6kh6BPkFtIHNoCGD8bGQ6gD5QAIA3MSghO4H9PqFjRIA8 cjqRPw9AHzl6fTqQaQsgPMg9ckOTPeNzfnURcDqBQsE+sUpGSyByrmYA0AeRC4B2BvB2CYD+IBnQ AMALgEZ/R485egtRvm4KwCQgFkA+gAQgdyqA3CB5CGA8wAIgJwVAEYD/TVA7UDOTBCBFABxAAkAL gK5nOsA2ID3xb1KAdTww/xnRPWNQ0jZ3Tm9Pfx6zUfP+aSWgUmE98QnwRKAwoASQ/zuQU7AHgFHj BGBSsT2wWbGZE9B4LjafN69JJ0Qw+UlRbmtTwgGgCGBJMTBQv14jPMEN0ASQKCE9oHAegfUA0Ghb bTEkIAhQTRBbEa9DhFVTVCRa5i0JgGc6cH8Z0BNQB5AoITxwPTFb5TL9JCBXOqBB8lsEOxARgBuA /weRPdAAkGSSKqAZ0EWoS8L/YhhDckLBSocEIBxAB5FnMu5uBbAAwAMgJjzBE8BbZv4zZVVneEoS YhlqxVqUaEX/WwI8UGpTS2RVQ0RAVGBpNv87kBPAUcFtSj4gasAT0DPg/28mI+FR8kUhWoJTwgPw S9HTB0AZ0GFkO5BiUsFtWf8qoHDRbpseoDqgEaB1kDuQ72PxO7BTsxPBcBHgVJBTsN91AgMgb2dq MXHrKVt8UWT/dOJSkz2xGdACQDuQVXBCwfsNwR7Cd2WCdGVvZiqgdaD/OyA60TwQBUAAwDwCdWBb AssAcDuBKEUAPylahFmkp2XlC4A6g2JyOtBof/F7XpGAkXdEcxPAdOIZYG/ea0RAB3ADEFESU0TC Y8HIZWg/W3xIb3hwS2S/UbBuAkkxJFA7EAIgZjrQ/1PBJCBbfSOChkBkAGWBC0YvF5I5iVvlGPEA jaAAAAADABAQAAAAAAMAERAAAAAAQAAHMMAWMoYsMrsBQAAIMMAWMoYsMrsBHgA9AAEAAAAFAAAA UkU6IAAAAADyzQ== - ------ =_NextPart_000_01BB3207.86AA7AE0-- ------------------------------ From: Squirrel Eiserloh Date: Wed, 24 Apr 1996 20:40:12 -0500 (EST) Subject: 2D Input Device problem >> Since the user can only easily indicate 2 dimensions of a point >> (graphically, on a monitor, at least :), the program should transparently >> calculate the third dimension of the point such that all of the surfaces >> involved remain planar. This way you don't have objects splitting up >> into hundreds of planes you didn't intend every time you move a vertex. We've shirked away from this (our original approach) because of several problems associated with it: (1) having the program determine z-depth (relative) of the point in this way takes a lot of control and precision away from the user, and can easily cause the very problem you're trying to get away from here (ie: shapes escaping their plane). We ended up snapping the user's "viewplane"/"editing plane" (though the two are actually different, but parallel, in Tremor) to that of the polygon being edited. No z-depth can be specified - by user or automation - since any points in that polygon must stay in the viewplane==polygon plane anyway. Which, at least, solves the 2d-input device problem. And prevents people from screwing up/breaking up planes. Then, theoretically, you will be able to rotate the polygon's orientation plane later (through the Polygon Tool, in our case). And breaking surfaces into sub-surfaces will also be implemented in this way. Besides, if you really must specify a depth location outside of the viewplane, you can just slide the viewplane toward or away from you such that the new location IS on it. Every time I think about vertex-specific movement, I get an intellectual gag reflex. At this point, I don't think single-vertex movement is fruitful or even necessary... can anyone think of reasons why it would be needed? (as opposed to line-moving only, or even polygon-moving and -shaping only) > I'm thinking about taking a different approach. > > 1. Convert the planes into a vertex-edge representation > 2. When a vertex changes position, recalculate all the planes, that the > points lies on, normal & dist. > 3. When recalculation the planes normal move all the vertices on that > plane so that they stay on the plane (note: the vertex you are moving > will already be on the plane, so move all the others by repeating step2 > until all vertices lie on the plane) > > This will have a pretty neat effect when moving vertices, because it may = > inadvertanly (sp?) move every vertex in the brush, but it would still = > look similar. Strange eh? This is similar to my solution, only it incorporates the plane re-orientation in with the point-moving. Hmmm... I can't decide which I like better. Ideally, I think this way is much better, but you're still pretty much stuck with the 2d-input-device issue... And can inadvertantly (sp? :-) screw up all sorts of other polygons if you've got them "attached" to this one's edges. So it may be too difficult in terms of interfacing. I dunno - need to think about it some more. I definitely need to do SOMETHING like that, though. - -squirrel P.S. Tremor is the name of our editor, in case of confusion (above). ============================================================================= Brian "Squirrel" Eiserloh "Never trust an operating system squirrel@css.tayloru.edu you don't have sources for." http://www.css.tayloru.edu/~squirrel -Linus Torvalds ============================================================================= ------------------------------ From: "Jens Hykkelbjerg" Date: Fri, 26 Apr 1996 18:31:56 +0000 Subject: Re: rendering question Hi Jim > I currently have a program that will display a wire frame of the > quake levels. Now I want to use the visibility list to do some culling. > To do this I need to know which leaf the camera is in. I am currently > just searching through the array of leaves and checking if the camera > is in the bounding box for each leaf. However, I have found that the > camera can be in several of the bounding boxes. In other words, how > do I find which leaf is the actual leaf the camera is in? To do this you need to search down in the BSP tree, so that you start at the top, and decide if the camera is in the front part or in the back of the first surface plane. If the camera is in the front part then you recurse into the front BSP subtree, and if it's in the back, you recurse into the back subtree, until you reach the BSP leaf... (Yes I know the above is over simplified, but If I had more detail I'd send them to you. I'm having similar problems with my own wireframe viewer...) With kind regards, Jens Hykkelbjerg - -- Jens Hykkelbjerg Email: jensh@cybernet.dk Haslehoejvej 5b Phone: (+ 45) 8615 2007 8210 Aarhus V Author of: RMB, sfx doom pages. http://www.cybernet.dk/users/jensh/ ------------------------------ From: "Donovan C. Young" Date: Fri, 26 Apr 1996 11:48:41 -0600 Subject: RE: 2D Input Device problem Hello all! Let me first say that although I am merely an observer to this list (I don't pretend to understand 3D Model programming), I am enjoying the fascinating discussions going on. However, it seems to me that there is a lot of skill out there that is being wasted on duplicate effort. I have noticed that several of you are in the process of creating Quake editors (BTW, I love the name Tremor for a Quake editor! Great thinking Squirrel - if that is your real name ;-) ). I dare say that if some of you were to pool your talents, you could quite possibly create a Quake editor that would be, simply put, awesome! Now I know that iD has said they were going to release QuakeEd (and/or part of its source) but let's be honest. QuakeED may work great for iD's needs, but will it meet the needs of the masses? Unfortunately, only time will tell, but I do believe that iD is (and should!) be concentrating thier efforts on the game itself and not nessesarily on all the bells and whistles of QuakeED. :-) Please forgive me is this is not the correct forum for this type of message, but I couldn't find a better place given my observations. Oh well, Just my .02 ;-) Thanks for your patience... Donovan Young donovan@mindspring.com Donovan.Young@bridge.bellsouth.com http://www.mindspring.com/~donovan ------------------------------ From: Olivier Montanuy Date: Fri, 26 Apr 1996 20:54:17 +0200 Subject: RE: 2D Input Device problem >However, it seems to me that there is a lot of skill out there that is >being wasted on duplicate effort. I have noticed that several of you are >in the process of creating Quake editors... > I dare say that if some of you were to pool your talents, you could >quite possibly create a Quake editor that would be, simply put, awesome! Real programmers prefer to waste a lot of energy than take the time to see if another dude is willing to help. And some here are even looking for raw bucks (names! names!) Basic ops might resuire a bit of cooperation, but for GUI there *must* be some competition. No GUI fits everyone's needs. > QuakeED may work great for iD's needs, but will it meet the needs > of the masses? I tend to agree with that remark. > but I do believe that iD is (and should!) be concentrating thier efforts >on the game itself Actually, I would assume that's what they basically do, don't they? Olivier ------------------------------ From: jouhaud@mr.insa-tlse.fr (Frederic JOUHAUD as FIRK) Date: Fri, 26 Apr 1996 21:56:43 +0100 Subject: Front or Back node? Hello, I currently make a little program to display a wire frame of the quake levels. But now i want know how can you decide if the camera is in the front or in the back part of the plane that splits the node. back part | front part <--------------------------------->|<---------------> | +----------------------------------+----------------+ | | | | | | | P | | | * |--> | | | | | | | | | | +----------------------------------+----------------+ | The node split plane In this case, we must choose the back child because the player is in the back part of the node (if type of the plane is 0 or 1 or 2 else it's the opposite). But how can i decide if the player is front or back of the plan? With a dot product but how exactly? Frederic JOUHAUD E-Mal: jouhaud@mr.insa-tlse.fr ------------------------------ From: Squirrel Eiserloh Date: Sun, 21 Apr 1996 15:29:47 -0500 (EST) Subject: Re: rendering question and speed problems > To do this you need to search down in the BSP tree, so that you start > at the top, and decide if the camera is in the front part or in the > back of the first surface plane. If the camera is in the front part > then you recurse into the front BSP subtree, and if it's in the back, > you recurse into the back subtree, until you reach the BSP leaf... This I understand. The [conceptual] problem I'm currently having is: once I use the front/back BSP traversal, what do I actually draw (and not draw)? Are you using Artist's Culling (or whatever it's called) and drawing ALL polygons, just in reverse-distance order (so that the near ones overwrite the far ones)? or can you use the front/back tree to determine which polygons (and which parts of polygons!!) to simply not draw at all? I'm not up on all the 3d-drawing algorithms... Another problem is speed; right now we're trying to draw "thick" points (both size and brightness represent z-nearness to the viewplane). Each point is a diamond (so, four lines) of variable size, etc. Basically, the program is unreasonably slow when displaying/redrawing upwards of 800+ points (with lines connecting each). We can get totally clean, acceptable redraw rates with as many as 2000 vertices AND lines connecting them, but only if we comment out the diamond-point-drawing code. But I'd really like to have the diamond-points in since their size and color variance produce a really convincing depth-effect... Is this going to be too slow? id's sample levels are, I think, relatively small (in comparison to what's to come) and they're already up into several thousands of vertices. And we've got several different viewing-windows going at once, so basically double or treble the amount we'd have to display simultaneously. Maybe it's worth some heavy math- crunching to eliminate drawing unneeded/obscured points (since the graphics seems like so much more of a bottleneck than math at this point). ============================================================================= Brian "Squirrel" Eiserloh "Women... can't live with 'em - squirrel@css.tayloru.edu pass the Beer Nuts." http://www.css.tayloru.edu/~squirrel -Norm, from Cheers ============================================================================= ------------------------------ From: Bernd Kreimeier Date: Fri, 26 Apr 1996 22:43:12 +0200 (MET DST) Subject: Re: Front or Back node? >But how can i decide if the player is front or back of the plan? >With a dot product but how exactly? Viewpoint: (x,y,z) Normal of plane: (nx, ny, nz) Front is: normal points towards viewpoint. Back is: normal points away from viewpoint. Dot product is projection of viewpoint onto normal: dotp = x*nx+y*ny+z*nz Now use the distance of plane to origin along normal to calculate the distance d of viewpoint to plane: d = dotp - dist If d == 0 :: viewpoint is on the plane If d>0 :: viewpoint is in front (the normal points towards viewpoint) If d<0 :: the viewpoint is in the back (the normal points away from the viewpoint) Example: plane | origin dist | x.......a........p-----------> normal \ ! | \ ! | \ ! | \ ! \ ! xa is dotp \ ! xp is dist \! v both are positive in this case, and dist>dotp, thus d<0 viewpoint Final remark: there is a working source that does exactly this calculation: the 3D clipping demo by Michael Abrash, that you will find on the QuakeDev support pages at http://www.nero.uni-bonn.de/~dn/q-sup/info/ Note that this demo does not do BSP traversal. Nonetheless... ....hope this helps b. P.S.: with 2D BSP (DOOM), one would use the z component of the cross product of viewpoint and vector pointing along the line segment, as has been described e.g. in the file accompanying ITT by William Doughty. ------------------------------ From: Squirrel Eiserloh Date: Sun, 21 Apr 1996 15:45:16 -0500 (EST) Subject: Re: 2D Input Device problem > However, it seems to me that there is a lot of skill out there that is > being wasted on duplicate effort. I have noticed that several of you are > in the process of creating Quake editors. [snip] > I dare say that if some of you were to pool your talents, you could > quite possibly create a Quake editor that would be, simply put, awesome! I agree, in theory... But I have a hard enough time co-ordinating efforts with only one other guy who lives on campus, let alone a dozen who live who-knows-where. I should think most people would be pretty free with sharing source-code (I'm fine with it), so we basically are doing that anyway, to some extent. Besides, with Chouser (co-author) I can set up a shared filespace easily and securely. I know I'm almost definitely going to hork (/'hork/: beg, borrow, steal) somebody's node-building code (from .MAP to .BSP) since I don't have enough free time to spend get pissed off at file formats. =) > Now I know that iD has said they were going to release QuakeEd (and/or > part of its source) but let's be honest. Whoa, I'm out of it... I thought they changed their mind (a while back?) and decided not to release QuakeED since they didn't want to support it, et al. Has this changed again - anyone know? > (BTW, I love the name Tremor for a Quake editor! Great thinking > Squirrel - if that is your real name ;-) Real name's Brian. Hate it. =( Only my GF gets away with using it. And thanks. Tremor originally was an acronym too, but we thought of it at 4:00am and mispelled it. :-) (suggestions welcome) ============================================================================= Brian "Squirrel" Eiserloh "The average woman would rather have squirrel@css.tayloru.edu beauty than brains, because the average www.css.tayloru.edu/squirrel man can see better than he can think" ============================================================================= ------------------------------ From: Bernd Kreimeier Date: Fri, 26 Apr 1996 22:52:47 +0200 (MET DST) Subject: Re: rendering question and speed problems >Are you using Artist's Culling (or whatever it's called) Painters algorithm. This will be slow because of overdraw (i.e. often drawing the same pixel more than once). >I'm not up on all the 3d-drawing algorithms... Then you are up for some reading. Again: see the Quake Developers support pages, the infos provided by Michael Abrash: his CGDC talk, and the reference to the article in visible surface determination. You will have to use the visibility lists to cut down the amount of leafs considered for clipping against view frustrum. You will have to use the bounding box of the leafs to determine which are within the view frustrum (see the 3D clipping demo by Michael Abrash). Finally, you will end up with front-to-back sorted, clipped polygons. Now you might try painters algorithm (still slow), or span blitting including clipping (needs to clip against lists of already drawn slices), or you might use an edge-sorted scanline rasterizer (as id does). b. ------------------------------ End of quake-dev-digest V1 #5 *****************************