Crate soft_edge[−][src]
Expand description
Soft Edge: efficient bithackery for making 3D collision meshes out of grids and stacked tile maps
indecipherable wailing guitar noises and tape echo sounds - Wata (Boris - Soft Edge)
soft-edge
is a crate which provides utilities for dealing with 3D grids where the cells are
colliders defined as convex hulls of subsets of the unit cube.
Things it gives you:
Vertex
, representing a vertex of the unit cube as an index in0..8
VertexSet
, representing a subset of the vertices of the unit cube as a 1-byte bitsetAtom
, representing a valid convex non-coplanar subset of the vertices of the unit cubeCompoundHull
, representing a clippable convex hull of anAtom
HullFacet
, representing a polygon of a potentially clipped compound hull of an atom. Facets calculated from aCompoundHull
will always be in CCW winding order.
Why?
If you’ve ever tried building a game physics system with a tile-based map before, you’ve probably run into the “crack problem”. This is where if you have two adjacent tiles, things which should smoothly move over the “crack” between them (which mathematically does not exist because the vertices of these two tiles are shared) instead get caught on the crack, because during collision detection the object is moved into a tile by some force and ends up spuriously colliding with an unexposed edge of one tile.
soft-edge
’s CompoundHull
type represents a sort of encoded tile collider with a
join_exteriors
method that erases any of these unexposed edges between two tiles, leaving you
with the surface polygons that can’t cause the crack problem. In addition, these clipping
operations are extremely fast, requiring only three bitwise operations (maybe some more because
they’re done on only a subset of the bits of a thing, but still, it’s fast.)
Does it work?
Uh, I think so. All the tests pass, at least?
Many things in this crate are specialized/brute forced/handwritten as lookup tables. I’ve fixed
all the bugs I could find, but I’m sure there are more hiding somewhere, probably in mistakes in
bit-significance or something. Though most bitwise ops are done through the bitvec
crate
exactly to avoid this as much as possible.
Vertex numbering
Vertices are numbered as follows:
v3 v7
*----*
v2 /| v6/|
*----* | +Y
| *--|-* ^ ^ +Z
|/v1 |/v5 |/
*----* +--> +X
v0 v4
For more convenience, a conversion between vertex index and unit cube coordinates:
// v0 is the origin.
v0 <=> {0, 0, 0} <=> 0b000
v1 <=> {0, 0, 1} <=> 0b001
v2 <=> {0, 1, 0} <=> 0b010
v3 <=> {0, 1, 1} <=> 0b011
v4 <=> {1, 0, 0} <=> 0b100
v5 <=> {1, 0, 1} <=> 0b101
v6 <=> {1, 1, 0} <=> 0b110
v7 <=> {1, 1, 1} <=> 0b111
This is derived as a bitwise representation 0bXYZ
where the X bit represents whether or not
the X axis is 1
, Y bit is whether or not the Y axis is 1
, etc.
“Exact” coordinates for vertex index deduplication
In order to facilitate vertex deduplication (for an indexed triangle mesh, for example) most of
the output coordinates for things like the CompoundHull
’s facets (HullFacet
) are
presented using the Exact
type. This wraps nalgebra’s Point3<i32>
, and is essentially
just the same coordinates you would expect but scaled by a factor of 2 on every axis. This
allows us to represent centroids of faces with no possibility of error, and also provides a
hashable type which can be used to build a set mapping vertices to indices.
Generally speaking, how do you expect me to use this?
- Encode your collision map as a grid of bytes, which correspond to valid
Atom
s. Deserialize these bytes intoVertexSet
s usingVertexSet::from_u8
, and try to construct atoms from them withAtom::try_new
. - Construct a three-dimensional grid consisting of the
CompoundHull
s of the atom grid elements, and then for every hull in the grid,join
it with its neighbors on the proper axes. - Extract facets of these joined compound hulls as
HullFacet
s, and then construct your collision geometry with them. This will end up as a very much non-convex mesh, which you may want to decompose into convex sub-meshes (but don’t have to, if you do collisions directly on polygons and only allow contact normals which penetrate through their “surface” side.)
Step 3 has some caveats. soft-edge
attempts to produce hull facets with the correct winding
order, which should allow you to easily calculate their normals. If it does not, this is a bug,
and must be fixed. The caveat here is that soft-edge
does not yet have a full test suite.
Re-exports
pub use bitvec;
Macros
Construct a vertex set in such a way that it can be used in a const
expression. This macro
requires that the bitarr!
macro and Lsb0
type from the bitvec
crate are in scope, for
technical reasons related to the limitations of bitvec’s bitarr
macro itself.
Construct a vertex set.
Structs
An Atom
is the smallest individual unit of our collision mesh. It is a convex polyhedron
represented as a subset of the vertices of a cube. For an Atom
to be valid, it must have at
least four non-coplanar vertices (it must have nonzero volume.)
The “compound hull” of an atom is its convex hull, possibly with pieces missing from its exterior.
The error type returned on trying to construct an atom using a degenerate vertex set.
A point in “exact” cube coordinates; integer coordinates scaled by a factor of two.
Facets which are on an atom’s convex hull and which exist on the six “face planes” of the cube,
and which may be clipped during join
operations.
A Face
represents a combination of four triangles around a central vertex:
Triangles which lie on the planes of the faces of an atom are taken care of by Face
s. However,
we still need to complete the picture by adding back in any missing facets which lie “inside”
that cube (and not on its faces.) There are 8 ways to choose 3 triangles from eight
vertices. Of these 56 possible triangles, there are 4 times 24 which exist on the faces of the
cube, and which are therefore superseded by the Face
calculations. We now have 32 triangles
remaining. Of these, we have six “symmetry planes” of the cube; these are the planes that run
through an edge each, and both contain four vertices. Like the face quads, these contain 24
possible triangles, which leaves us with a total of 8 anomalous configurations. To sum up (pun
intended):
A plane, represented as a point on the plane and a normal vector (not necessarily guaranteed to be normalized).
A vertex of a cube, represented as a byte index encoded w/ three bits, each representing an axis
as a boolean (true = 1, false = 0.) See the constants [X_AXIS
], [Y_AXIS
], [Z_AXIS
] for a
reference of which bits are which.
Enums
Represents a single signed axis: +X
, +Y
, +Z
, -X
, -Y
, or -Z
.
A facet of a hull is either a rectangle or a triangle.
Constants
The eight “anomalous configurations” of subsets of the unit cube; these are triangular interior faces which can be calculated as part of finding the interior convex hull of an atom, and which are always triangular (within an atom, can never be joined with another triangle into a quad.) Also, “anomalous configuration” sounds badass. Admit it.
Axis unit vectors in i32
coordinates corresponding to the same index order as faces and the
axis to_index()
and u8
representation.
The six faces of the unit cube, each corresponding to an axis.
Six quadrilaterals which happen to match planes of symmetry of the cube. These are the planes which exist between pairs of edges of the cube, and represent six possible ways we might end up with a quad as an interior face of an atom, plus a total of 24 possible ways we could end up with triangles as interior faces of an atom (by cutting those quads in half, four ways each.)