DOOM maps to SVG to laser cutter

2023-04-15 03:35:20

I’ve heard so much about basic Doom’s knowledge format and determined to put in writing some Rust code to extract its maps and convert that to vector graphics I may laser reduce.

I’ll undergo the method, from the info extraction to the geometry reconstruction to outputting laser-cuttable SVGs, together with the geometrical useless finish I enthusiastically ran to after I tried to preview the end result utilizing bevy.

DOOM’s knowledge was designed with modding as a purpose : the complete recreation is an executable and a .WAD knowledge pack. The shareware/demo model shipped with DOOM1.WAD, which continues to be accessible freely.

The WAD format is nicely documented – see the Unofficial DOOM spec or the ZDoom wiki. The gist of it’s :

the WAD file begins with a header observe by the precise knowledge, ends with listing entries describing that knowledge
the header incorporates a pointer to the primary listing entry and the entry depend
every listing entry incorporates a pointer to the info and its measurement

I’ll skip some (fascinating!) particulars, because the DOOM game engine black book of the great Fabien Sanglard already covers all of that.

These knowledge objects are referred to as “lumps” in doom parlance. Some incorporates map geometry, others textures, sounds, textual content, … the whole lot wanted for a recreation.

A map is described by a number of lumps

VERTEXES is a listing of world positions
LINEDEFS describes strains becoming a member of two segments and references one SIDEDEF per line “facet”
SIDEDEFS are “partitions”, textures for a line, and belong to a SECTOR
SECTORS are polygons with a ground and ceiling top

The map knowledge additionally features a BSP tree whose leaves are subsectors, sectors break up to be convex polygons, but additionally texture definitions compositing a number of sprites and way more.

Implementation

I used nom, a rust parser combinators library that may parse textual content and binary codecs. Here’s a typical utilization: parsing THINGS, the map objects/energy ups:

pub struct Factor {
    pub pos_x: i16,
    pub pos_y: i16,
    pub angle: i16,
    pub thing_type: u16,
    pub flags: ThingFlags,
}

impl Lump for Factor {
    // used to find out what number of objects in a lump
    const SIZE: usize = 10;
}

pub fn parse_thing(enter: &[u8]) -> IResult<&[u8], Factor> {
    map(
        // parse 5 unsigned shorts
        tuple((le_i16, le_i16, le_i16, le_u16, le_u16)),
        // map them to the struct fields
        |(pos_x, pos_y, angle, thing_type, flags)| Factor {
            pos_x,
            pos_y,
            angle,
            thing_type,
            flags: ThingFlags::from_bits(flags).unwrap(),
        },
    )(enter)
}

I’ve a pleasant parse_lump operate in a WAD struct, taking the lump identify and the parsing operate :

let issues: Vec<Factor> = wad.parse_lump("THINGS", factor::parse_thing);

Getting line segments is comparatively straightforward (group linedefs by sidedef.sector). Nonetheless, I additionally intend to group sectors by related ground heights to scale back the layer depend and I must mark edges as reduce or engrave strains if they’re polygon borders or inner strains.

The parsed WAD knowledge is an unordered assortment of edges. We have now a assure that edges gained’t cross. Merging polygons is only a set union, and eradicating inner strains is a matter of discovering duplicate edges in a polygon.

Strictly talking, this is sufficient to produce a SVG that may be laser reduce.

It’s now time to separate sectors into layers, in accordance with their ground top. That is achieved by offering an array of heights and grouping sectors by the smallest higher certain, eg. I used [-70, -24, 0, 40] for E1M1.

It could possibly be automated, however I went for inventive management. Sectors could possibly be sorted by ascending top, then break up into teams of comparable measurement. That group measurement could possibly be in operate of sector counts or areas. One other standards could possibly be the sector properties – if a sector is flagged as inflicting injury (acid, lava…) it may deserve its personal layer.

Mayne I’ll examine later ; my intestine feeling is that this drawback is said to Map coloring.

I’ve used the svg crate in earlier experiments. It’s barebone, with no attribute kind, however works.

For laser reducing, I want :

one shade for every layer
one other for inner strains that I intend to engrave
one other for positioning strains. Some layers comprise free elements I’ll must accurately place earlier than glueing them ; the positioning strains draw these items’place on the layer beneath.

That is the end result for E1M1, with the inner strains in purple and the positioning strains in cyan:

Interlude: Halton sequence

I spent plenty of time producing svgs with varied colours to validate my work. I reused a trick I’m keen on to generate semi-random colours: utilizing a Halton sequence output because the hue of a HSL shade.

// base, f are parameters right here
let mut halton = halton::Sequence::new(base);

for i in 0..sectors.len() {
    let shade = colorsys::Hsl::from((
        // hue 0-360
        (h * 360.0 * f) % 360.0,
        // saturation 0-100
        80.0,
        // lightness 0-100
        50.0
    )).to_css_string();
}

It’s just like utilizing a pseudorandom generator with a hard and fast seed, however the Halton sequence is extra evenly distributed. Right here is the end result for 100 values with a couple of base/f mixtures :

Issues have been too easy at this level, so, in fact, I discovered one thing. It began after I thought, “wouldn’t or not it’s nice if I may preview the stacked laser reduce layers in 3D”.

I bootstrapped a easy Bevy app. To render the layers, I must triangulate them. It occurs there’s a triangulate crate, however it comes with constraints.

First, let’s take a look at the DOOM polygons three instances:

a easy polygon, which has a particular definition (Wikipedia) :
- precisely two edges meet at every vertex
- the variety of edges equals the variety of vertices

one polygon with holes (referred to as “weakly easy polygons” in probably the most primary case akin to a disc). This implies the sector represents a number of polygons the place one incorporates the others

a number of polygons sharing one vertex – to be correct a number of polygons the place every pair share at most one contiguous vertex, which makes it a advanced polygon. The truth that the perimeters intersections are vertices means the polygon might be break up into easy polygons.

The triangulate crate (and, AFAIK, all different implementations) wants precise paths – an ordered record of vertices. It additionally doesn’t help non-simple polygons, which excludes case 3.

To rebuild a path from the unordered record of edges, my preliminary strategy was to choose an edge, then discover any edge linked to it. This works for instances 1 and a couple of, however not for the final one, as these polygons have greater than two edges assembly at some vertices.

The answer to that drawback is to rebuild paths by repeatedly discovering the shortest loop from an edge, which is equal to discovering all loops the place no vertex is used greater than as soon as per loop:

If a doom sector incorporates a number of loops, it means it falls both in case 2 or 3. To determine it out, we will depend on empiric assumptions :

Instances 2 and three are unique – which means if a vertex is shared, it should not be a gap. solely I’m not certain that is true
it additionally signifies that if a loop incorporates one other, it’s the outer loop of a polygon with holes

I went with the latter, utilizing the geo rust crate which has in depth help for polygon operations.

I bought that to work ultimately:

The problem is that I now must invert these polygons, as I need to subtract them to an enclosing rectangle – which means boolean operations (additionally supported by geo), however now the triangulation fails.

Subsector try

However wait, the WAD does comprise easy, convex polygons, proper ? The results of the binary area partitioning. It does, however these polygons generally have implicit edges outlined by the partition strains. I began engaged on that, then realized that was an excessive amount of sidetracking. It ought to work nevertheless. Perhaps later…

Backtracking

I gave up on that strategy at this level. The answer to the preview, a really legitimate drawback, was less complicated: use TinkerCad to import the svg layers, extrude them, stack them export a .glb I may render in blender. That’s how I rendered the banner of this text. Be aware that tinkercad’s SVG import do count on correct SVG paths and never disjoint strains ; so a part of that work did serve to supply a cute render.