I heard that Build uses portals & sectors to cull lots of the levels away for fast rendering. I know a little about portal engines, but im still confused as to how you implemented it.
How did you check whether a portal(s) was visible from the current sector, or what was your algorithm like? Some sort of view frustrum clipping?
And also, did portals have to be placed manually in the map editor for Build?
Thanks
Anonymous at
This has been bugging me for a while, was Build or wasn't it a polygon based engine!? I hear its something called "2.5d" engine, yet the games looked as if they used polygons (in some places atleast).
Yet, i believe the maps were all constructed as 2D maps only?
Fernando at
BUILD is a 3D Sector and Sprite-based engine.
Maps are built in 2D mode, as well in 3D.
Anonymous at
Fernando said
BUILD is a 3D Sector and Sprite-based engine.
Maps are built in 2D mode, as well in 3D.
3D Sector? could you elaborate?
Do you mean polygons?
Agent ME at
Just use build.exe for yourself to see how it works!
And it's not polygon based, or at least not in the sense that quake is polygon based.
Fernando at
Anonymous said
Fernando said
BUILD is a 3D Sector and Sprite-based engine.
Maps are built in 2D mode, as well in 3D.
3D Sector? could you elaborate?
Do you mean polygons?
What I mean with 3D is this: The BUILD engine uses 3D perspective to work around, for textures. And the engine uses 2D mode for line drawing mode.
Awesoken at
How did you check whether a portal(s) was visible from the current sector, or what was your algorithm like? Some sort of view frustrum clipping?
Build works like a portal engine in the way that it follows invisible walls into neighboring sectors. My method for hidden surface removal is probably very different than most portal engines though. The classic Build engine uses a simple vertical span buffer. Every vertical column of the screen has 2 heights: a top and a bottom point. Any future pixels drawn to that column (or x-coordinate) must fall inside this range to be drawn. At the beginning of each frame, I set these two heights to 0 and yres (the height of the screen in pixels). Build draws walls in front-to-back order, 1 wall at a time. I have a nice way of guaranteeing proper order, but I won't get into that now. Anyway, as I draw walls, I clip to the current height values for each column, and I update them after drawing the wall piece. The height values always creep towards the middle of the screen (or horizon). When they meet or cross, that column is done - meaning nothing else can be drawn to that column. A portal (or wall connecting to a neighboring sector) is visible if any part of the invisible part of the wall happens to fall inside the visible range of any column.
In Polymost, I use a similar idea. The main difference is that clipping is done with a series of line segments instead of points defined for each columns.
And also, did portals have to be placed manually in the map editor for Build?
Yes. Sectors are essentially portals.
was Build or wasn't it a polygon based engine!? I hear its something called "2.5d" engine, yet the games looked as if they used polygons ...
People always argue over the meaning of "2.5d". It means better than 2d, but worse than full 3d. I don't want to say more because I'm afraid it would just start a pointless argument.
Alexey at
Hello Ken.
I need help.
As far as I understand, Build first renders walls, then floors/ceilings
flats/slopes and then sprites.
How does Build Engine determines if the screen is filled during "bruteforceing" and drawing the walls (bunches of walls)?
How does it render and texture maps floors and ceilings ("flats" with horizontal lines and "slopes" with ?diagonal lines?)?
As far as I know, in DOOM flats are drawn with a flood fill-like algorithm and
the floor and ceiling are drawn as "visplanes".
How does Build do it?
Thank you in advance.
Awesoken at
I use 2 ways to determine when drawing is finished. The final decision happens at this line of ENGINE.C (don't hesitate to search for it):
while ((numbunches > 0) && (numhits > 0))
"numhits" is a counter, initialized to the number of columns of the 3D view. It is decremented whenever a column is filled during rendering (for example: umost[x] >= dmost[x]).
"numbunches" is a counter for the wall "bunches" left to consider rendering. Wall bunches are added to the list whenever the renderer traverses into a new sector (crossing a red sector line). Bunches are removed from the list permanently as they are drawn.
Theoretically, it should have been sufficient to only test "numhits" to end drawing. I used both methods just in case it missed a column (which can happen with precision errors).
For my "floodfill" algorithm, please look at ENGINE.C of the Build Engine source code. Search for this line:
if (!(globalorientation&0x180))
There are 2 occurences. The first one is for ceilings. My algorithm is different from general flood filling because it uses a list of vertical spans as input instead of a 2D bitmap array. The code takes a list of vertical spans specified this way:
0 (top of screen, 0 for all columns)
uplc[x] (y-coordinate of the top of the wall for each column x)
Then it intersects this list with another list of vertical spans:
umost[x] (up-most pixel on column x that can still be drawn to)
dmost[x] (down-most pixel +1 on column x that can still be drawn to)
The intersection of these 2 lists is:
umost[x]
min(dmost[x],uplc[x])
If you look at my code, you'll see 4 while loops. These loops convert the list of vertical spans to a list of horizontal spans. The horizontal spans are then passed onto my hline() function.
Build does not use diagonal lines (also known as free-directional mapping) to render slopes. I could have done it this way, but never had time to implement it. Instead, I render slopes using single column vertical lines. I do a divide (actually a reciprocal lookup) every 8 pixels and linearly interpolate U&V in between.
Alexey at
How does Build render multiple walls per column? (Does it?)
For example, when there is a small buliding (which you can enter)
in front of a much taller scyscraper, or when rendering "cracks" and "windows" in walls.
How does it determine that the column is filled,
when rendering multiple walls per column?
How does it render "cracks" and "windows" in walls?
Awesoken at
How does Build render multiple walls per column?
Columns are only marked "done" when the umost value goes below the dmost value for the particular column. For example, if you're looking at a strairway, it could bump the "dmost" value up many times before it crosses "umost".
when rendering "cracks" and "windows" in walls.
Cracks and windows are drawn as sprites. All sprites are drawn in back-to-front order in the second pass. Basic walls, ceilings, and floors are all drawn in the first pass.
Anonymous at
Well, I tried looking over the render code a few times, but never quite understood the code for sprites. ;) Anyway, I was just curious what causes the cliping errors between floor sprites and walls? Sometimes floor sprites wouldn't clip at the edge of a wall. Other times when floor spite is between your view and a wall point, one of the walls would clip through.
Awesoken at
I was just curious what causes the cliping errors between floor sprites and walls?
Classic 8-bit Build does sprite clipping by keeping a history of changes to the vertical span buffer. This history is a record of all changes to umost[] and dmost[] during the previous drawrooms() call. (Drawrooms renders the walls, ceilings, and floors). Due to limitations of the vertical span buffer, I never figured out a good way to clip floor sprites quickly. The problem with floor sprites is they are rendered with horizontal strips, while the span buffer (and other sprite types) are all done in vertical strips.
So the answer to your question is: I never wrote clipping code to handle floor sprites intersecting walls properly. Basically, I left it up to the mapper or game programmer to keep them away from walls.
Anonymous at
Awesoken said
So the answer to your question is: I never wrote clipping code to handle floor sprites intersecting walls properly. Basically, I left it up to the mapper or game programmer to keep them away from walls.
I guess that it turned out fairly well considering.
TX at
Anonymous said
Awesoken said
So the answer to your question is: I never wrote clipping code to handle floor sprites intersecting walls properly. Basically, I left it up to the mapper or game programmer to keep them away from walls.
I guess that it turned out fairly well considering.
Well, it doesn't exactly take rocket science to keep your sprites away from walls. :)
Semicharm at
Well, it doesn't always work right even if you do.
Alexey at
Hello, Ken
I need help.
VERY stupid question(s):
Ken, how it can be proven, that there is always a segment (a wall)
of an arbitrary closed non-convex polytope (sector), that is not "blocked" by
any other segments (walls), if a viewpoint (camera loation) is placed inside
a polytope?
Of course, if we draw a figure, it could be obviously seen, but how it can be "strictly" proven?
And how did you and/or John Carmack think that out?
Can this be extended to 3-dimensional polyhedras?
Does any arbitrary closed non-convex polyhedron has the property, described above?
Or, for example, if we have a 2-dimensional slices of an arbitrary
non-convex polyhedra (it's a non-convex polygon), does this slice have that property?
REALLY stupid question:
What is a difference between a "polytope" and a "polygon" (the first is planar and the second is not?), and between a "polyhedra" and a "polyhedron"?
Awesoken at
Ken, how it can be proven, that there is always a segment (a wall)
of an arbitrary closed non-convex polytope (sector), that is not "blocked" by any other segments (walls), if a viewpoint (camera loation) is placed inside a polytope?
Your statement is actually false. Here's a counter-example: (a hex-encoded PNG file)
The above case is only a problem when you need to draw all 360 degrees around you, such as when you're looking up or down and the zenith is in view. The good news is you need to make a maximum of only 1 split to make things work ok. In Build, this is not a problem because you can never see more than a 180 degree field of view - the view frustrum clipping takes care of the "split" for you.
And how did you and/or John Carmack think that out?
Doom uses a 2D BSP for wall sorting. A BSP can sort walls faster than my more brute-force algorithm in Build, but keep in mind 2 things: A BSP is much less suited for a dynamic environment, and wall sorting isn't much of a factor in engine speed.
Can this be extended to 3-dimensional polyhedras?
Not that I know of.
What is a difference between a "polytope" and a "polygon" (the first is planar and the second is not?), and between a "polyhedra" and a "polyhedron"?
I have no clue. I've never even seen the word "polytope" used before with computer graphics - sounds like something from Chemistry if you ask me.
counting_pine at
Isn't "polyhedra" the plural of "polyhedron"?
Alexey at
Awesoken said
What is a difference between a "polytope" and a "polygon" (the first is planar and the second is not?), and between a "polyhedra" and a "polyhedron"?
I have no clue. I've never even seen the word "polytope" used before with computer graphics - sounds like something from Chemistry if you ask me.
I found this word here: http://www.faqs.org/faqs/graphics/bsptree-faq/
Look for the section "How do you perform boolean operations on polytopes with a BSP Tree?"...
Alexey at
And there is a phrase: "...considering polytopes instead of just polygons..."
So, what is the difference between the two?
counting_pine at
According to MathWorld:
Coxeter (1973, p. 118) defines polytope as the general term of the sequence "point, line segment, polygon, polyhedron, ...," or more specifically as a finite region of n-dimensional space enclosed by a finite number of hyperplanes.
So basically I think it's a general term that includes polygons, polyhedrons, and the 4+ dimensional equivalents.
Since 3D graphics are by definition 3-dimensional, it's probably not a particularly useful word in this context. I suppose it could be used to describe an object which could either be a single polygon, or a set of polygons that combine to form a polyhedron.
Jinroh at
Re: Visibility algorithm used in Build engine
Sorry to resurrect this old thread, but I read through it and looked through BUILD and am still not 100% sure how BUILD goes about finding the nearest walls. I have been trying to figure this out.
Thank you ^_^
Awesoken at
The goal is not to find the nearest wall, but the unoccluded wall. Depending on the scene, the unoccluded wall could be far away. A simple method is to compare every wall to every other wall at every step. This isn't fast, but it will work. Before you draw each wall, you make a list of 'potentially unoccluded walls'. You then check every pair of walls. If any wall is in front of another, then you can cross the occluded wall off the list. Once you finish, there should always be at least 1 unoccluded wall. (This is assuming you are using a 4dof engine, and none of the walls intersect). Here are the steps to do a wall vs. wall test:
1. In the 2D overhead view, clip your walls to the left and right edges of the screen view. 2. Project the wall's left and right edges to screen-x coordinates. 3. Using the projected coordinates, test whether the walls overlap. If they do not overlap, then you are done with this pair (i.e. neither wall can be crossed off your list of potential unoccluded walls) 4. Look at wall A. Are the 2 endpoints of B on the same side of line A? If not, then swap the walls and do step 5, remembering to invert your final result. 5. Looking at wall A, is your viewpoint on the same side of it as wall B? If yes, then wall B is in front, and wall A is occluded, meaning it can be crossed off your list. If no, then wall A is in front, and wall B can be eliminated.
Try following the steps using the attached image. If you do it right, you'll have to swap walls in step 4, and use wall B as your splitter.
Jinroh at
Ah, I see. ^_^
Thank you Ken, that clears things up for me. That is right I want Unoccluded walls. I will take that to heart as I am writing my Visibility Determination for my Engine.
Jinroh at
Hey Sorry to Double Post Ken, but I was curious about the BUILD.
Say we have the map here that is attached in the picture.
I am curious, does like the fish looking sector know that the little rectangle is within it? I'm just trying to figure out how it knows which sectors are where. Sorry if this is a painfully obvious question?
Awesoken at
This detection happens inside the Build editor, as you are editing. In BUILD.C, search for the word 'island'. Right above it, you'll see a loop that checks whether the first point of the loop that you just drew is inside an existing sector. If it finds one, then the new loop is appended (merged) to that sector's list of points. If not, then the loop becomes a new sector.
Jinroh at
Ok, so as your editing if a sector has a sector within, it makes a big list of all the walls within that main sector for that sector that the engine then processes at run time. Ok. That is what mine does similarly too.
Thank you for your prompt reply Ken, I appreciate it very much.
Alex at
Ken, how do you update umost and dmost, when drawing a wall?