The missing building pieces

by IllvilJa on 03/27/2008 08:07, 34 messages, last message: 04/01/2008 00:25, 6705 views, last view: 05/18/2024 09:23

Hello!

The intent with this thread is to discuss what "building blocks" you find missing when you create maps.

Creating maps in Sauerbraten is a bit like building with Lego in those days when you were a kid. You dig around in that pile of building pieces of yours until you find something that suits what you are constructing or, perhaps even more fun, you run across that piece that you first was not looking for but which immediately sparks new ideas of how to proceed with your little building project.

But sometimes, when building in Lego as well in Sauerbraten, no matter how much you dig in the pile of pieces, you don't find THAT critical piece you need for the moment. The solution is to rethink what you build or scrap it altogether. Or in the case of Sauerbraten, perhaps to identify EXACTLY what the missing piece is and look into what value it would provide for mappers and what cost it would impose on the Sauerbraten project (or a mod thereof).

Please note, this is a thread for discussions of new features to the mapmakers, features that basically are hypothetical and which not necessarely ever will be implemented.

Dear Sauerbraten users: if you like some suggestion, feel free to say so but do not DEMAND that it get's implemented into the official Sauerbraten releases, not even you are capable to code it yourself. ANY demands expressed will effectively KILL this thread, ok? (and I don't want it to die...)

Dear Sauerbraten and forum maintainers: even if this discussion never result in a single line of executable code, please let the discussion continue. I for one really enjoy trading ideas and discussing various software features, spatial geometrics, data structures, project management etc... If it then actually results in usable features, the better.

   Board Index   

#1: ..

by IllvilJa on 03/27/2008 08:32

Ok, here is one set of "missing pieces" I have ran across or rather, a situation in the current Sauerbraten map editing where I've run into problems.

(I'm short on time right now so I'll provide just the "problem situation" for now and in a later post, the suggested additional building pieces to add to the Sauerbraten repertoire of "Lego pieces" to solve the problem. I promise, I do have an idea what those pieces will look like.)

Ok. The problem is this: when you take a single cube in Sauerbraten and deform it by pushing the various corners in different ways you might end up with a "cube" which cannot be subdivided into 8 sub-cubes without ruining the appearance of the original cube. Some cubes might be subdivided, but definitely not all cubes. This problem is frustrating as one cannot always avoid subdividing (it happens if you want to apply a separate texture to a sub-face on one of the cube faces for instance or when you create some small feature using small cubes close to the bigger cube but still disjoint to it). The problem is a bit more serious as it makes it much harder to write automated tools which work with the geometry of the world, both tools ingame in the Sauerbraten engine itself as well as external tools that work with the ogz data. Sometimes this problem can be worked around by carrying out a lot of extra subdividing, but IMHO, that subdividing often leads to excessive cluttering of the object being modelled, making it harder to work with (in addition to taking more storage space in the octree and demanding more performance to render ingame).

To create an example of a cube that cannot safely be subdivided follow these steps:

Enter edit mode.

Extract a new cube somewhere on the map.

Use the mid button on one of the cube's corner to select it for deformation. Pick a corner on the top face just to make it easier to inspect "subdivision damages" later on.

Use the scroll wheel to push down that corner EXACTLY 5 steps. Now the cube you have in front of you is "unsafe" to subdivide. Follow the steps below to see for yourself!

Decrease the grid size to half that of the cube (press down the "G" key and then roll the scroll wheel ONE single step).

Select any subsurface on the cube (on top of it for example). You should now have 1/4 of a face selected.

Now provoke a subdivision of the cube into 8 smaller cubes by pressing "y" and then select some new texture to the subface by rolling the scroll wheel.

Now carefully inspect the new cube. You will notice that the slope that were present on the undivided cube now is incorrectly subdivided (take care to look at BOTH the new sub-cubes that replaced the old slope and you see the problem)


Yes, solving this would require to add additional functionality/complexity into the Sauerbraten engine code. The gain however would be to get a more consistent and generalized set of building blocks. But more on the new suggested building blocks and their cost of implementation (if it ever happens) in a later post.

reply to this message

#2: Re: ..

by Hirato Kirata on 03/27/2008 10:00, refers to #1

what you describe there is present with all odd numbers. so 'subdividing' 1, 3, 5 and 7 will result in the same 'incorrect subdivision'

if it's an even number, subdivision should go a lot smoother, but it will by no means be perfect either. like for example if you push one edge 8 spaces, and then edit the cube with a smaller gridsize, you'll see noticeable errors.
If course, unlike the other scenario, these can in most cases, be fixed up quite easily.

~Hriato Kirata

reply to this message

#3: ..

by IllvilJa on 03/27/2008 10:31

Ok, here's my suggested solution to the above problem (and now, for a moment we only focus on the building blocks themselves as they appear in the map editor, implementation details will be discussed later in post).

First let's recap what we got TODAY. In Sauerbraten, every cube side is a simple heightfield: each of the corners of the side is possible to slide "into" the cube, deforming the side in question. (I'm from now on taking the liberty of assuming everyone reading this is familiar with that "deformation" exercise.)

Each of these four corners can be in one of 9 different positions. Let's call the position when the corner is "all the way down" into the cube position 8 and call the position when the corner is undeformed (at the cube top surface) for 0. Obviously, the steps in between is called 1 through 7 ;-).

So, what I suggest is that when deforming the corners of a cube, the following applies.

* The corners might be pushed beyond position 8, all the way down to position 15 (yes, beyond the far end of the cube!).

* The corners might be pulled above the surface of the cube, up to position -7.

* The max difference between the positions of any two corners cannot exceed 8, that is, we do not permit any steeper slopes than Sauerbraten permit today. Exactly how to best enforce this max slope in the user interface in the map editor is open for suggestion.

* If all corners reach position 8 or a higher value, the cube "degenerates" into an empty cube (as Sauerbraten do today when all positions go to 8).

* If all corners reach position 0 or a lower value, the cube "degenerates" to a full cube and all corners get position 0.

* That is, in order for any positions to make sense when higher than 8 or lower than 0, it is required that at least some corner of the face still is in the range 1 to 7. (Otherwise, the cube degenerates into a full/empty cube as appropriate)

* If corners of the cube is having negative values (being "above" the topmost surface of the cube) the surface is NOT extended to reach outside of the cube, instead it is clipped against the front face of the cube. Another way to put it is that the cube still maintains a (partial) topmost face, but have part of it "chopped off" by the heightfield that partially is within the cube. This way a corner, two corners, an edge or two edges etc of the cube can be cut off at various angles, creating useful pieces for a number of situations (including subdividing a larger cube).

* If corners of the cube is having values above 8 (that is, being "beyond" the rear end of the cube) the surface is NOT extended beyond the far end of the cube, but instead, the heightfield is clipped by the far side of the cube. This way one might create useful building blocks (e.g cube fragments with just a corner or an edge of a cube).

I hope the above was clear enough. If not, my apologizes (I realize I need to create graphical illustrations).


So, perhaps we have an idea of the VALUE of this addition. But what is the COST?

First, it requires changes to the code, which by itself is a cost: someone has to read, understand, modify and debug the core octree code (yikes!), so at least SOME blood, sweat and tears will be paid for this.

Second, it will most likely introduce some increase in the complexity of the engine, which per definition is some slight departure from the minimalism wanted in the code. Maybe the value of the change warrants this "loss of minimalism", maybe not. As heightfields are clipped against near or far end of the cube, additional surfaces of the cube need to be introduced when it is rendered as well as when physics, line of sight etc are determined.

Third, this change, even if it intuitively is quite simple (we just extend the range of how corners can be pushed with an addition 14 positions each) requires that we still store the positions of the corners of the cube. Unfortunately, having 23 positions for each corner makes it impossible to use the current storage code as that one (if I got it right) expects corner positions to be stored in just 4 bits. This can be solved in different ways, depending on what tradeoffs one want to do. One way is to allow octree leafs to take some more memory to store corner positions, which simplifies coding but which perhaps increases RAM footprint and definitively increases disk footprint (not to mention breaks backward compatability). Another way is to encode the corner positions in such a way that we can continue to use 4 bits per corner, leave the encoding of corners of "unclipped" cube faces unchanged (allowing backward compatability with todays OGZ format) and STILL managing to encoding the new more exotic clipped cube faces' positions. Unfortunately, the latter require more elaborate code to carry out encoding/decoding of the 4 bits per corner into heighfield positions.

(If the above is implemented by changing the OGZ format to increase per octree leaf memory, it might have the benefit of allowing us to add information necessary for yet some MORE missing building blocks I have run into needing... more on those nifty things in future posts).

So folks, what are your thoughs on this? Brilliant? Bullshit? In between?

reply to this message

#4: ..

by IllvilJa on 03/27/2008 10:38

Hirato, I agree that the "broken subdiv" at times can be fixed up, but not too seldom I run into situations where I see no way forward but giving up the particular design. The frustrating thing is that I'm not trying to do any really fancy or elaborate but rather quite basic shapes when this limitation hits me.

Also, this limitation makes top down design of a landscape far less straightforward and much more of a gamble, as subdivisions from time to time fails.

Not to mention the problems an automated piece of code for landscape generation might run into.

Don't get me wrong, I'm not claiming that this is trivial to implement, but I think the generality and consistency it adds to the building blocks of the engine would warrant the cost of it.

(I'm willing to implement this, but before starting the effort I need to understand if the feature as such would be accepted or not even given that I and noone else carries out the implementation work).

reply to this message

#5: Re: ..

by a`baby`rabbit on 03/27/2008 12:26, refers to #4

If I understand your idea correctly of extending the corner range so that the cube clips, i.e. from (0..7) to (-7..16) - then the effect is identical to that of working at the next cube size down. Therefore it doesn't give the ability to make odd (or rather non-factor of 8) slopes.

reply to this message

#6: ..

by SheeEttin on 03/27/2008 20:08

It's possible to hack around this effect. See the sloped corners of metl4 for an example.

That only works if you can cover that part, though... Else it looks weird.

reply to this message

#7: Re: ..

by tman_elite on 03/27/2008 20:14, refers to #3

If this were to be implemented, IMHO there would definitely need to be a tool to import ogz maps, like the current tool to import original cube maps.

reply to this message

#8: Re: ..

by jbuk2k7s cookie has gone on 03/28/2008 17:54, refers to #7

I know it sounds simple, but an auto-generator for curves would be nice- ie you select an area for the curve, then determine a gridsize, and when you press a button, the engine automatically creates as perfect of a curve as is possible with your current gridsize.

reply to this message

#9: ..

by rknigh21 on 03/28/2008 19:03

I agree an automatic curve generator would be very useful.

Things I would really find useful are

1)For the fps, move the list of available monsters into the config file so we could easily change the monsters without re-compiling.
2)An easy way to find textures, maybe a tree format.

If this includes Eisentern then.

1)Monsters (npcs?) that can carry weapons.
2)Greater Ability to influence monster behaviour (maybe scripted AI).

Thanks Robin

reply to this message

#10: Re: ..

by jbuk2k7s cookie has gone on 03/28/2008 19:11, refers to #9

2) Press F2.

If that's still not good enough, then maybe a textures dialog that creates separate tabs for every directory in packages might be useful.

reply to this message

#11: Conclusion regarding 'Clipped Cubes' (WARNING: LONG!)

by IllvilJa on 03/28/2008 19:25

(Wow! This were a very long post. My apologizes for putting ppl to sleep, but I hope the memory, bandwidth and the attentionspan used by it to be worth the read...)

First: I briefly read the source (perhaps about time, ISN'T IT??) for the Sauerbraten Octree cubes and there, position 0 for an edge means that the corner is pushed ALL the way to the far end and position 8 is the corner is pushed all the way to the near end (so when a new cube is created, all edges are in position 8). So from now on in this thread, let's follow this convention used in the source (and forget my earlier suggested convenion).

A Baby Rabbit: very short answer: no worries, even in cases when the surface is clipped all the usual slopes for the surface WILL be available. Longer answer: yes, the cube "one size down" does have half sized steps compared to the current cube BUT the cube "one size down" OTOH is only half as wide as the current cube so both the "one size down" cube as well as the curren cube will have the same slopes. One of them is just half the scale of he other, but all possible proportions (and hence, all options for slopes) are identical for them.

(I know, there is a desperate need for some graphical illustration of what 'A Baby Rabbit' and I are discussing)

tman_elite: Yes, it is a must to be able to read in old maps, one way or another. Actually, you are touching the unpleasant concept of saving format versions and backward compatability and I realize that adding these "clipped cubes" to sauerbraten most likely will require changes to the format of maps on disk (and most likely to in memory data structures, even if that is slightly less invasive). I cannot say I'm particularly thrilled by the concept of changing the OGZ file format (or inventing it's next generation), it's not something that should be taken lightly. This might be a hint that the "clipped cubes" might rather belong to Cube 3 (aka Sauerbraten 2) than the current version. If they are to be implemented at all.

I first only considered cubes that were clipped by the far end cube side in the height field, something that COULD be encoded by using the 4 bits per edge Sauerbraten use today (edges only need 16 distinct values in that case). Then I realized that there also were a need for cubes that were clipped by the near end face of the cube and suddenly I needed to 23 different values per edge, and immediately I did not feel that fricking brilliant anymore. So much for cramming in additional stuff into the current data structures.

SheeEttin: I'll have a look at the suggested map to check out what you mention. Thanks for the advice.

Regarding reusing the current data structures for heightfield edges:
Short answer: Possible but inefficient and complicated (= bug prone...), so no, I don't think it's worthwile..
Long answer:For a heightfield on a cubeside, there are 6560 valid shapes as Sauerbraten works today. But those are stored using in a total of 16 bits (4 per edge) which can actually store up to 65536 different values so one is tempted to at least CONSIDER trying to encode also the clipped cubes into this. However, I've tried to figure some way to do this that does not require too complex mappings between the "compact" 16 bit format and the "real" positions of each edge but all attempts result in a bit too complex calculations (remember, these values must be accessed quickly, so if they need to be calculated, the calculations must be pretty much trivial). As a more "intutitive" argument AGAINST trying to cram in the clipped cubes into the "unused" values in the 16 bits Sauerbraten haves today, I did an attempt to calculate the number of valid clipped cubes that could exist for a heightfield and, my calculations ended up with 54144 different clipped heightfields (provided my calculations are correct of course, the combinatorics of this problems drove me almost crazy...). So, we have a total of 60704 valid shapes for the heigh field (assuming my messy calculations are correct) and that is awfully close to the max 65536 values that can be stored in the 16 bits used today. My gut feeling is that there is very little headroom for easy encoding for various corner cases, instead there probably will be pretty messy encodings necessary (equal complex calculations ledaing to SLOW access to "real" values).

So, my conclusion so far for these new building blocks:
They now have a name (and that's nice): "clipped cubes".
They would be VERY useful.
They would be quite invasive to the Sauerbraten project:
* requiring quite a few changes to the code at several places
* requiring some changes to inmemory data structures
* increasing memory foot print
* perhaps MOST IMPORTANT, increasing size and changing format for saved maps!, This suggests that they don't get added to the current Sauerbraten but rather considered for Sauerbraten 2/Cube 3 or to some brave mod of Sauerbraten which dares to modify the game engine itself...

I REALLY feel I want these new building blocks.
And I REALLY feel I'll rather wait with the job of implementing them (if ever). Wait quite a long time, actually. ;-).

Ok. LONG post. Time to move on to OTHER missing building blocks, blocks that I will discuss in another post. Luckily, the next ones I'll pick (named 'hip-valley-cubes') are much easier to describe and hopefully, by far less invasive for the project to try to implement.

reply to this message

#12: Re: Conclusion regarding 'Clipped Cubes' (WARNING: LONG!)

by tentus_ on 03/28/2008 19:37, refers to #11

Interesting points. BTW, if you're looking to make illustrations right here in the forums, without an external image or anything, lots of the capital letters are the same width, allowing us to do basic ASCII art. For example, using the old X and 0 of tictactoe;

0000000X
000000XX
00000X0X
0000X00X
000X000X
00X0000X
0X000000
XXXXXXXX

Triangular slope!

reply to this message

#13: Re: Conclusion regarding 'Clipped Cubes' (WARNING: LONG!)

by tentus_ on 03/28/2008 19:37, refers to #12

That's the number 0, not letter O.

reply to this message

#14: Missing building pieces part 2: The Hip-Valley Cubes!

by IllvilJa on 03/29/2008 01:04

(Thanks for the advice Tentus, I'll try that when appropriate).

When deforming the corners of a cube, we can deform it in such a way that all four corners lie in the same plane and thus, the new side of the cube is one single plane. It gets subdivided into two triangles (which can be seen when enabling 'outline' by hitting the key '7' in edit mode) and even if it can be subdivided into triangles in two different ways, it does not really matter which way is chosen by the Sauerbraten engine.

However, when deforming a cube side in such a fashion that the four corners are NOT part of the same plane, then the choice between the two ways of subdividing it into triangles WILL matter. If one looks at the "division line" separating the two triangles the face is subdivided into, the two options of where to put that line will result in it being either a bit higher up (a hip) or a bit lower down (a valley).

The 'hip' subdivision will retain more of the cube's volume than the 'valley' subdivision' as the latter "digs deeper" into the cube's surface.

A picture would help here, and luckily our trustworthy friend Wikipedia has an EXCELLENT image of a house roof which serves as a good illustration of this concept as well as it shows the original situation (creating a roof with valleys) where I ran into problems because I were missing some building blocks.

Ok, here is the picture: http://upload.wikimedia.org/wikipedia/en/a/aa/Rf-iso1.gif

(It is taken from the article http://en.wikipedia.org/wiki/Hip_Roof BTW).

In this picture, we see an illustration of a roof. There are so called 'hips' (denoted with the letter 'h') and there are so called 'valleys' (denoted with 'v'). On my emerging attempts to create a wargame, I do of course like to have roofed houses on he battlefield, and when creating a house like the illustrated one, it's dead easy to create cubes with 'hips' so I can create the hip ends of the house without any problems. However, when I try to create anything like a valley, the cubes refuse to become the 'valley' cubes I need, they just become 'hip' cubes. Subdividing does not help, I get a valley cluttered with a stair of hip cubes. (And actually there is no way to tell the cube if it should be 'hip' or 'valley').

And, in a nutshell, that is what I'm missing, the ability to strictly control when these cubes with non planar deformations becomes 'hip' cubes and when they become 'valley' cubes. From a user interface perspective, this change is fairly easy to implement. Just let some key toggle a face between being either 'hip' or 'valley'.

I had a look into the source, but did not have time to find a definitive answer on how easy this feature would be to implement. I got the impression at least, both from source as well as from working with the editor, that all non-planar cubes consistently end up as 'hip' cubes. If this indeed IS the case, adding 'valley' cubes becomes easier, as we then only need to keep track of two different states for each cube face. Where to store that bit of information is of course a good question. If we are fortunate, we might find some unused bit in the already used data structures, some bit which today always is set to zero or one. That bit can then be used to tell if the cube side is 'hip' or 'valley'. For backward compatability, we do of course let the 'usual' value (used today by sauerbraten) of that bit to denote a 'hip' face whilst the other value then denotes 'valley' face.

If the current state of affairs is that we really cannot count on all these non-planar faces to be 'hip', then we need to find two unused bits which we can use to store the state for each side, be it 'hip', 'valley' or 'dontcare' (the latter being the state used today, given the assumption starting this paragraph).

In any case, we need to ensure that Line of sight code, physics code, rendering code, remipping code etc takes the 'hip' or 'valley' state of the cubes into consideration.

Your thoughts on THIS addition to the editing? It would be quite nice to be able to create 'valleyed' roofs as well, in addition to usual gabled roofs and hip roof.

Or is it just me who has misunderstood the editor and have not figured out how to switch between 'hip' and 'valley' cube faces? That possibility is definitively not ruled out either!

reply to this message

#15: Re: Missing building pieces part 2: The Hip-Valley Cubes!

by SheeEttin on 03/29/2008 02:55, refers to #14

Don't think it's currently possible.
I've been playing around for quite a while trying to get something like that to occur (and, for the map I'm working on right now, it's in a roof, strangely enough).

I guess the way to implement this would be to decide, somehow, which direction to "cut" along when deforming opposite corners.
(For a visual, take square ABCD (a face of a cube), vertices labeled clockwise. Press corners A and C in halfway. Sauer would make the ridge along BD. Instead, what if the "cut" were along AC, such that the cube formed a valley? This is what is being suggested.)

reply to this message

#16: Re: Missing building pieces part 2: The Hip-Valley Cubes!

by tentus_ on 03/29/2008 03:27, refers to #14

I'm gonna go a bit nuts with the ASCII art so I can visualize what you're saying: if I'm understanding correctly then I agree with what you're asking for, I've wanted it a few times myself.

Corners 1, 2, and 3 are lowered, resulting in a hip:
10002
0X000
00X00
000X0
30004

Corners 1, 2, and 3 are lowered, resulting in a valley:
10002
000X0
00X00
0X000
30004

Viewed from the side and diagonally, so that 3 and 3 are centered and 1 and 4 are on the far ends:
Hip:
------4 (I hope the - are the same width)
----X00
---X000
--X0000
1003000

Valley:
------4
-----X0
----X00
---X000
1--3000

So, now that my little monstrosities are out of the way, let's consider what other applications the same data could be used for. It's quite possible that giving the ability to dictate hip/valley to the mapper could result in unforeseen slowdown and complication, but it could also open up some possibilities that haven't been mentioned yet. Specifically, I'm thinking about cave modeling... a little while ago there was a nice discussion on layered geometry in order to create concave surfaces, like that of a complex cave. The general problem was that you would have to build your cave from a square, keeping the corners more or less intact, otherwise you ended up with funny, inorganic angles. Several artists found this very limiting.

If we could tell the engine hip/valley, that same data could be used to tell the engine how to put together caves. We wouldn't have to subdivide everything so much to break away from the grid, we could instead just tell it to make the ridge to go the other way. Example:

Corners 1 and 4 are lowered, resulting in a hip:
10002
0X000
00X00
000X0
30004

Corners 1 and 4 are lowered, resulting in a valley:
10002
000X0
00X00
0X000
30004

Viewed from the side and diagonally, so that 3 and 3 are centered and 1 and 4 are on the far ends:
Hip:
1000004
-X000X-
--X0X--
---X---
---3---

Valley:
1-----4
0X---X0
00X-X00
000X000
0003000

reply to this message

#17: Re: Missing building pieces part 2: The Hip-Valley Cubes!

by demosthenes on 03/29/2008 09:38, refers to #16

Gah!

Those last two (pairs of views) make no sense! Corners 1 and 4 are lowered, resulting in a hip (which looks like a mountain fold), but your line of Xs runs from 1 to 4... which are the low points!

And the second one is the opposite, with the same problem!

Your first two (pairs of views) make sense, though.

reply to this message

#18: Re: Missing building pieces part 2: The Hip-Valley Cubes!

by tentus_ on 03/29/2008 14:23, refers to #17

Whoops, I flipped my little diagrams. 1 and 4 are supposed to be on the bottom row. Just... pretend that my stuff got flipped because we're looking at the ceiling a cave now. (There's actually a good chance that's what I was thinking, I am more easily turned about when it's 2 am)

Basically, it works like this. Depending on your orientation, having points 1 and 4 up and 2 and 3 down will have these results:
(First diagram)
The division line runs from 1 to 4, resulting in triangles 124 and 134. This results in a little ramp shape I tried to express.
(Second diagram)
The division line runs from 2 to 3, resulting in triangles 123 and 234. This results in a little valley.

Next time I try this I'll just put a bunch of diagrams on my website.

reply to this message

#19: ..

by ezombie on 03/29/2008 20:44

So like a 'in/out' toggle? Basically you are changing the behavior from concave to convex deformation of the cube.

That would sure be handy. But I noticed that ALL possible cubes that can be currently created are fully convex. Perhaps there is an engine reason (some optimization, etc) that concave cubes are not available?

reply to this message

#20: Re: ..

by demosthenes on 03/29/2008 23:13, refers to #19

Aren't convex polygons "easier"?

No, I'm not *quite* sure what I mean by that, but it makes some sense to me. Just can't quite piece together why.

reply to this message

   Board Index