Posts

Inscryption GOTY 2021. I liked it a lot just from watching it on YouTube earlier in the year, but I played it with my friend aaron and finished that on Jan 2, and it was so great like that.

I highly recommend playing Inscryption with your friend who is an ARG/internet weird fiction/meta stuff nerd. Perfect experience, 10/10.

I’ve been curious about how .map files from Quake editors or Hammer, etc. get compiled into usable map files. What’s the BSP compilation process?
There are some videos online that talk about how to render from a BSP, which is cool, but I like compilers :3.

The structure of a map file

The input you’re producing is a collection of entities. Each entity is has key/value information about what that entity is. Every entity has a class that defines what it is for the game or for tools that process the map file. Any other keys/values are interpreted by the tools based on what class that entity is. A player spawn entity might have a position key with coordinates in the value, etc.

Some entities have a list of “brushes”, which are convex polyhedra defined by their faces as planes (the intersection of all the corresponding half-spaces bounded by each plane). Those surfaces have information about the texture on that surface, etc.

You can read the whole syntax for this format on the quake wiki or in the unofficial quake spec. I recommend looking at the Valve variation of the format, it’s a simple baseline with better texture information.

Map compilation

Map compilers take some subset of these entity classes (like worldspawn, func_detail, func_group, func_door, func_plat, etc.) and process the brush geometry into a spatial acceleration structure and mesh. It will produce one mesh for each moving object (so a func_door becomes its own model), and one for the static geometry (merging worldspawn with all the func_detail, and various other conventional rules).

Map compilers output the information in any useful format. If you want to be compatible with Quake, you can read about the Quake .bsp format, or you can just invent your own formats like I’m doing—map compilation doesn’t just have to be for classic games, these editors are still nice!

Basically essential functions of a map compiler:

• Turning a collection of planes into polyhedra with vertices.
• Generating texture coordinates, etc.

Functions that a map compiler should be doing:

• Removing faces that are contained inside other geometry.
• Removing geometry in inaccessible parts of the level.
• Fixing T-junctions.

Depending on your output format:
- Generating texture and lightmap coordinates.
- Producing extra metadata like special collision data.

BSP compilation algorithms

In order to achieve the goals above, you’ll want to use “binary space partitioning”—recursively dividing the world into two sub-spaces in order to divide up objects/surfaces. Traditionally this tree structure was used for rendering with a precise potentially-visible-set, so that games like DOOM and Quake didn’t have to render polygons for offscreen geometry. Nowadays, this function isn’t as necessary since you can rely on other types of culling, and more powerful GPUs to make fine-grained culling less essential. However, the structure of the BSP is still extremely useful for many of those compilation goals.

My map compiler process:

1. Read the .map file.
2. Gather up the brushes from different entities into the appropriate groups.
 This step requires keeping multiple groups, because some solid brushes are invisible, some visible brushes aren’t solid, and only some of them should be used to divide the world. You need to separately store:
   • Brushes that “seal” the map—used for flood-filling geometry.
   • All solid brushes—those that should be used for collision generation.
   • All visible brushes—for render mesh generation. This requires properly accounting for hint/clip/etc. brush textures and not just entity classes.
3. Clip the brushes against each other, leaving only faces that aren’t inside other geometry.
4. Build a BSP tree that contains all of those visible faces. We use the faces here, since faces inside walls end up being bad split candidates.
5. Take the BSP tree and build “portals”—the faces between tree leaves.
6. Mark some leaves as directly visible to point entities—like player spawn points, items, teleporters, etc. These are the start of the play area.
7. Flood-fill the non-solid leaves through the portal graph, starting at those occupied cells. This lets us find what leaves could be potentially reached by a player, and which ones are unreachable.
8. Remove all surfaces that aren’t adjacent to the play area. This removes external level geometry that can never be seen, and makes the level look like a cute diorama in noclip :3.
9. Insert T-junction points on edges that have another face’s vertex next to them. This is necessary to avoid cracks in the geometry for the rasterizer. (See also, this explanation of T-junction issues.
10. Deduplicate vertex positions and generate a mesh.
11. Write out the level data in my own format.

I’ll write more detailed notes about each of these points when I feel like it.
If you’re interested, bother me to turn this into a proper blog post.

Reading the map

Do this however you want, look at specs for the .map format variants you want to work with.

Grouping brushes

You need to consult the entity class, and also the face textures (clip and hint brushes are defined via textures), and potentially other data based on what map format you’re using.

Clipping the brushes

This deserves really thorough notes, but those will come later.
In the meantime, useful things to be careful about:

• You need to work with floating point epsilons.
• A good way to test what side of a plane a polygon is, is to project all vertices and find the range of coordinates. If the range is mostly on one side or another, it can be on that side. I have a slightly opaque diagram on twitter.
• You need to handle faces that are coplanar, in addition to entirely-inside.
  • Coplanar faces with the same vs opposite normals are different. If the normals are the same, then you need to remove one of them, if the normals are opposite, you can remove both (there’s solid material on both sides).
  • This is easy to handle by putting a priority on faces, which can include an arbitrary ordering of brushes/faces.
• All of this is made more complex by transparent materials. I’m not handling those properly yet.
• You’ll need to split individual faces, you can split any face that overlaps another brush, and then just delete any face that’s entirely inside one.

Building a BSP tree

Use faces that are touching the current region as candidate split planes.
Pick planes that divide the faces in the region appropriately.
You need to make sure you pick planes that constantly make progress, or you can get infinite recession here.
This part is hard, output visualizations so you can debug this.

Generating portals

Build portals with a depth-first approach. Build all the portals for the left side of the tree before you do any work on the right.
Track a map of what cells are connected through what portal polygons.
To make a portal, create an extremely large polygon on the split plane, and link it to the two nodes on either side of it. You should chop it against every other portal in the current cell, and split every other portal against its dividing plane.
When you split an existing portal, you can connect all of the faces on the other side to the appropriate cell on this side, replacing their connection to the parent region. Doing this in a depth-first pattern leaves only leaves connected to leaves.

Marking leaves

This is pretty easy compared to other parts, as long as you track the appropriate data, the leaves have all their bounding portal planes, and you can do a containment check on the entity points.
Store a set of leaves or something.

Flood filling the graph

This is a pretty standard graph traversal algorithm. You need to avoid entering solid cells, and start from any occupied cell. This should give you the right results.

Removing surfaces

This is made complicated because you need to check whether the geometry is inside a visible cell, or if its cell is an appropriate neighbor of a visible cell (because a visible wall can be inside a solid cell that’s not reachable, next to a reachable cell). Check what cells any given surface is close to.
You might have some trouble with extra faces adjacent to cells just because of precision issues with long edges. This hopefully doesn’t cause too much trouble.


Insert T-junctions

The simplest approach is to do a O(V×E) loop. For each edge in a face, check if any vertex is close to it (do an epsilon check). If it is, insert a vertex on that face at that vertex’s position. Avoid adding multiple vertices that are too close together. You need to make sure to insert these in the proper order for your face, to preserve the winding—sort them for each edge by their projection onto the line t. It’s somewhat easier to keep track of if you record all the insertions, and insert them all at once at the end.


Mesh generation and output

I haven’t actually done this yet.

So I already knew about imagemaps, but it was only today that I realized you could use the title attribute on ‘em to put different hover text on different parts of the image.

I have anchored all the posts

Note: this originally did an alert! Turns out I could script inject my own website. But I could do that anyway because it’s my website. I’m now treating it like untrusted input anyway just for cleanliness and principled-ness, cleaning it up with ammonia.

USV is “Unicode Separated Values”, a term that people have apparently come up with multiple times referring to similar things. What I mean is basically: I use the information separator characters to act as file/record/field separators, and don’t even bother doing quoting because I’m just working with plain text that doesn’t contain those control characters. It makes implementation very easy even in limited systems like Shortcuts.

Why does the notes app throw away the numbers/bullets on lists. It like gives you plain text instead of rich text?

I decided to make a bad micro blogging platform that uses the iOS notes app as its content source. It seemed like a good/bad idea, but also an easy one, side I already had the reading list code.

How it works:

1. I write content inside the iOS notes app, in a dedicated folder for posts.
2. I run an iOS shortcut which gathers up the information and formats it. This formatting is joining some properties like the creation and modification date, and the actual text, with the unicode UNIT SEPARATOR character. Then, joining each post with the FILE SEPARATOR character. Finally, sending a request to my server with that as the body.
3. This passes through nginx as a (reverse?) proxy so I don’t have to do HTTPS in the Rust server (Rocket 🚀 doesn’t support it in a production ready way yet.)
4. The Rust server saves the file in a directory as a dated file and also current.usv
5. The Rust server renders current.usv with a Tera template and saves that in my web content folder
6. nginx serves static files out of that folder so you can see these

I think iOS shortcuts are really cool, and I love building tiny servers, and USV is a good format.

This is the power of Microblogging with silly hacks. It’s great. It’s also silly. :3

What is a post Nonsense

It’s good to post What Hm

Blah