These functions have existed for several years now, with stable
implementation and interface. They are exposed via JS interface and used
by gltfpack, and thus are unlikely to change dramatically.
A recent change added meshopt_EncodeExpClamped, which also had a
possible alternative of adding more fine-grained exponent clamping
control to meshopt_encodeFilterExp. Instead of marking the entire
function as experimental, let's mark just the enum entry as
experimental. If more control is necessary in the future, we can remove
this enum entry and add a meshopt_encodeFilterExpClamped instead.
Our initial heuristic adjustment is a little too aggressive wrt global
flow: it is very happy to leave the last vertex of a meshlet unused
(when a triangle with extra=2 and a valence-2 edge exists it will always
be selected over a triangle with extra=1), and that increases the
not-full meshlet count more than optimal.
Using 1+extra instead fixes this by using priority 3 for these triangles
so that they can be weighted against extra=1 triangles. This is a
compromise, as fully separating the priorities results in worse global
outcome.
When a triangle has two vertices with valence 2, it's typically
advantageous to prioritize it above others even if that may require an
extra vertex; after removing this triangle, we'll have between one and
two isolated triangles with valence=1 vertex which we'll pick up
immediately.
Avoiding this triangle risks leaving the small triangle cluster alone
and going in a different direction only to collect it later.
This significantly reduces the number of disconnected clusters due to a
better global flow; note that it's important to check for the edge, not
just a single valence=2 vertex, as that results in a worse local
decision that doesn't sufficiently improve global traversal.
When getNeighborTriangle's best selection can't fit into the current
meshlet, we redo the search process using an adjusted criteria that
ignores position/normal as that is irrelevant. However, internally
getNeighborTriangle adjusted best_extra to act as a topology score
instead of just the extra count. This would lead to the last triangle of
the meshlet being reselected in addition to the first one in some cases.
Also change _extra variables to int as these are small.
Note: by itself, this change actually slightly reduces the
clusterization quality due to non-local effects of the rescoring.
When we switched from frexp to optlog2, the behavior for negative zero
changed: instead of being encoded as if it had exponent 0, it was
mistakenly encoded as if it had exponent min_exp.
Both encodings are equivalent; in fact, there is some leeway in encoding
zeroes that we are not exploiting as they could repeat the last non-zero
exponent - but this is an unexpected change and should be corrected for
consistency.
When using SharedComponent or SharedVector, exponents compress fairly
well on their own because their range is normalized in a more or less
optimal way; when using Separate mode, the reduced bit count truncates
mantissa which fixes some issues with input entropy, but if the values
are clustered around zero then the exponent will also see a lot of
variance that is generally unwarranted for precision, when the input
range is known to be further away from zero.
While there are ways to solve this in a more general fashion, eg by
exposing min_exp as well as mode, this is probably too involved and it's
simple and mostly sufficient to add a clamped mode.
This is helpful when encoding values like texture coordinates, where
SharedVector or SharedComponent may not have enough precision in case
where a component is tiled with a high repeat value, but we know we need
a limited precision around 0 so clamping the exponent works well.
This API is still experimental so it's easy to rework it later if we
discover a more general solution is warranted.
This change fixes a few idiosyncrasies in clang-format integration:
- extern/ code should not be formatted
- All other code, including meshoptimizer.h/gltfpack.h, should be
- Fix indentation issues because of extern "C" block
- Work around clang-format bug wrt calling convention qualifiers
The only reason why seam pair was computed separately was to reuse that
computation between collapse and quadric updates as it is fragile; now
that we have split quadric updates completely, sx is only used for
collapse update and it's thus better and cheaper to process inline.
This way performEdgeCollapses no longer needs access to quadrics data,
and when attributes are used and we need to compute distance error, the
access to vertex quadrics is maximally local as we use them right after
aggregation, which saves 1-2% on large meshes.
For now we keep the optimization of not recomputing the distance error
unless attributes are used; it makes the data flow slightly awkward and
seems to have <1% performance impact but we can remove it later if it
becomes more problematic.
Instead of updating quadrics as we are collapsing edges, we can update
them in batch after all collapses are done. This makes the code cleaner
since we do not need to replicate the collapse structure explicitly for
both remap and quadric update, and also makes it ~5% faster on many
large meshes - presumably due to better data locality during the update.
The only subtle part here is vertex_quadrics update: we need to do this
just once, and we *know* the primary vertex will have to move if any
wedge moved, so we do that during the corresponding collapse. The
target vertex may not have had any collapses to the primary vertex in
case some vertex gets collapsed into a locked vertex.
This change results in exactly identical results; in the future, this
would result in a more careful handling of Complex collapses as our note
about the attribute quadrics not requiring a merge was incorrect - even
though the attributes might be similar, merging quadrics is still
valuable to get area accumulation.
When attributes are incorporated into the metric, depending on the
attribute weights we may see divergence between the error as returned by
vertex quadrics alone and the result. Especially when the simplification
does not have a set limit, this may lead to unexpectedly aggressive
component pruning.
While ideally pruning should only be used with a reasonable error limit
that negates these concerns, for now it is probably better to accomodate
this use case by tracking the positional error separately.
To reduce the cost of tracking this error we recompute it as collapses
are performed; this may seem counter-intuitive since we've already
computed it during ranking, but conserving memory is more important
here, and since we only need to do it when using attributes and only for
collapses we end up taking, the performance cost ends up being
negligible.
Tabs only give us a limited amount of alignment if some byte streams are
much longer than others; instead, explicitly specify the width for all
numbers.
bitg[0] is always 0 because we accumulate only sizes, and we store zero
data bits for bit0... we might need to print count percentages in the
future instead but this is probably ok for now.
Also reduce the space wasted by extra whitespace.
Within each byte group, we count the number of consistent bits: bits
that, in that byte group, all match the corresponding bit from the last
vertex. Consistent bits amplify compression rates when they are properly
aligned.
Note that this is not exactly the same as having small deltas, eg 0xff
vs 0x00 is still consistent from the delta perspective in most high
bits, but it would be the same if we used xor deltas (which may be an
option worth having).
This is also *not* the same as having bits consistent between
consecutive bytes: in a very random sequence, about half of the bits in
each position usually match from one value to the next, but that's a
very low consistency as it's hard to take advantage of.
For now we just need a single trace level that incorporates both the
macro stats (per byte) and the micro stats (within the individual byte).
Instead of separately collecting occurrences/sizes for bit groups we
just record the size and print all numbers as percentages within the
given group.
This is a partial revert of a10c311fb2
which removed tracing support from both codecs; to make further progress
on vertex codec v1 we need some amount of tracing back, and while the
tracing we used to have isn't sufficient it's a good start.
Previously, we would only read vertex_lock data for the primary vertex
(the vertex with the smallest index among those with the same position).
When using sparse mode, this would be the first vertex referenced by the
index buffer due to how the sparse remap works.
If the input locks were inconsistent between all copies, there could be
a situation where a vertex with the wrong index was asked to be locked,
and the vertex would still be not-locked and could move. When *not*
using sparse mode, this was particularly problematic as the flags would
be read from the vertex that might not be referenced by the index buffer
at all.
We now propagate the locked status into the primary vertex in a separate
pass; this requires re-locking the wedges in a separate pass, but all of
this is very quick especially when using sparse mode.
The collapse scheduling mechanics actually permit collapsing more than
one vertex to the same target. We normally don't do this because that
may lead to collapses v0->v1 even if v1->v0 has better error, since we
haven't had a chance to recompute the error.
However, if the target vertex can not move (if it's kind is locked)
anyway, this constraint does not apply: we dutifully update quadrics of
locked vertices but these updates aren't used for any evaluation. This
could allow us to collapse more vertices in a single pass if the target
is locked.
Trying this on a set of test meshes, however, a few percentage of meshes
exhibit somewhat higher resulting error, and this error is also
apparent visually. This is probably due to an unfair advantage that
collapses to locked get; even though the error is technically correct,
we may go further in the original sorted collapse list and select edges
that we would not need to collapse as edges with smaller error become
available.
So this change is a no-op but this discovery and testing results seem
important to document for the future.
- Edge eval is very verbose because it gets printed for every edge, even
the ones that we do not collapse, so this bumps it to the next tracing
level;
- Component measure should be using TRACE >= for consistency.
For optimum compression, the vertex buffer should carry quantized values
and have consecutive vertices be reasonably local which can be achieved
with regular vertex cache/fetch optimization for most meshes.
An alternative to quantization is filtering but since it is unlikely to
be as broadly used it's probably enough to just call out quantization
here.
This was originally added so that we have a pruneComponents call at the
end of any simplification process. However, since pruneComponents will
only do work if the error has increased since last time, and early-outs
from the edge collapse loop are only possible if the error has not
updated, even before cleanup passes this should have been redundant with
a rare exception of pruning zero-error components in a fully locked mesh.
With the cleanup passes this is entirely redundant now, and is never hit
on any real test meshes.
Since we rarely have no-op pruning now, it should be fine to always
print pruning stats; this also makes it easier for us to print single
line traces for the cleanup passes.
Instead of only computing the next component error at the end of the
collapse loop, we keep track of it as we prune components. This is
fairly cheap, as usually the number of components is much smaller than
the number of indices at any point in time, and this helps us avoid
calling pruneComponents excessively: after this change, while the
behavior of simplification stays the same, only ~1% of calls to
pruneComponents end up removing no triangles (which happens when the
component was entirely removed through edge collapses).
In addition to pruning after each pass, where we are limiting the error
by the current worst-case error reached, we now also prune components at
the end of simplification with a series of passes of increasing error.
This helps on meshes where available edge collapses are very low error
so the total error must increase to prune components; without this
meshes would be stuck at a higher triangle count. This also improves the
behavior with varying target_error: if some edge collapses have error
1.1e-2, and some components have an error 0.9e-2, then without this we
might see components pruned with target error 1.2e-2 but not with 1e-2
because earlier edges might have lower error.
Instead of computing an AABB and using half diagonal as an error,
compute an approximate sphere bounds and use radius as an error.
This makes the error rotationally invariant (modulo inaccuracies of the
computation), and produces a more reasonable pruning order in practice
on a few test meshes, although both measurement methods have their own
issues.
When pruning is enabled, we perform a second pass filtering of the index
buffer using the current reached error limit; any triangles that are
part of components with a smaller error get removed.
Note that this is done for all components regardless of whether or not
some of them are unnecessary to remove to reach the resulting count (but
only done if we haven't reached the count yet). This means we do not
need to sort the components by error but may result in bursts of triangle
counts depending on how the edge collapses end up working out.
After computing component ids, we can compute a bounding box for each
component and derive an error value from it that will be used for
pruning.
For now we allocate an entire bounding box for each component for
performance, but we might use some other way of computing these in the
future that is less memory intensive; usually, component sizes are
fairly large so this is an acceptable use of memory.
It's not clear yet if AABB diagonal is a reasonable approximation of
component error; this is pending future testing. Note that we square
the value for consistency with quadric errors.
Add a few comments to make the code easier to read, and simplify the
component update.
Because the last pass renumbers the components which changes the meaning
of the values from parent links to component ids, we *need* an
intermediate pass to finalize component values; make that clear in
comments.
For pruning, we need to identify small isolated components that can be
removed entirely. This requires computing connected components of the
mesh graph.
There are two ways to look at connectivity, either triangles connected
by edges or vertices connected by edges. Both types of analysis are
possible, but for now we use vertex analysis. This is easier to compute,
and would not require continuous updates as the triangles get collapsed
and recreated during edge simplification.
For computing components, we could use union-find or a graph traversal.
For now we settle on union-find: it's usually measurably faster on
complex meshes, and does not require extra memory for a vertex queue. To
compute the components, we first do a classical union-find pass over all
edges, and then renumber the roots (and other vertices) sequentially,
thus mapping every single vertex into a component id.
Since we need seam pair for gradient update as well as collapse remap,
including a temporary safety measure for invalid loop data, we now share
this code between the two blocks instead of duplicating parts of it.
This is not performance sensitive but will help if we ever need to
change anything here.
While the new seam handling code seems correct and robust based on
testing and fuzzing, it's theoretically possible that loop lookup
returns ~0u. Since this is used for indexing various vertex arrays it
would be a memory safety issue if it ever happened. Builds with enabled
assertions will abort, but if assertions are compiled out this may go
unnoticed.
For now, handle the ~0u case that should never happen by collapsing to
the next wedge; this is not correct for locked vertices but should not
create more issues downstream. Eventually this code could be removed.
Similarly to border->locked collapses, enabling seam->locked collapses
is important to reduce topology based restrictions as that allows us to
reach lower triangle counts or same triangle counts at lower error for
meshes with islands of irreducible topology.
A seam-seam edge is bidirectional whereas a seam-locked edge is
unidirectional and may be connected to any wedge out of an arbitrary
count in the locked vertex. Because of this we can't use wedge[] to find
the seam pair anymore, and need to switch to using loop/loopback based
on whether the edge is forward or backward wrt original topology.
This is somewhat risky as it requires loop/loopback to stay valid and
coherent throughout the entire simplification process, whereas
previously bugs here would simply block certain collapses; now it's
theoretically possible to get an out of bounds read if the loop data for
the other wedge points nowhere. However, extensive testing and fuzzing
did not uncover any further issues with this.
Sometimes edges that connect two wedges may be classified as seams,
which invalidates assumptions about coherent topology around seam
vertices and prevents future improvements to seam collapses. These are
incredibly rare and should not be classified as seams.
While locked vertices can't move by themselves, ideally we should be
able to move any vertex into a locked vertex; currently this is allowed
for manifold but not allowed for border/seam. This artificially limits
the allowed collapses which can lead to larger than necessary result or
worse than necessary error as the simplifier is forced to consider edges
with worse error.
To enable border collapses, we simply need to extend the picking logic;
border-border edges are symmetric so it is enough to validate them in
one direction, but border-locked edges may be forward or backward (as
in, they may align with the topological edge direction or be opposite to
it), so we need to check loop or loopback depending on which vertex is
border.
The same logic would work for seam collapses but they require changes
elsewhere in the pipeline to be permissible.
When the seam edge is collapsed in the opposite direction to the loop
flow, we need to follow the previous link to discover the new
connection. However, if that link pointed to a remapped vertex, we
previously would create an invalid loop edge. This would result in
inconsistent loop metadata between loop & loopback, and could prevent
future seam collapses around the problematic area.
The correct thing to do is to remap the connection, unless the loop
stopped after that vertex in which case our vertex becomes terminal.
We use a subset of bits of collapse error to produce an approximate
ordering of collapses; to keep stack usage and cache utilization
reasonable, we used 11-bit counting sort which uses 8 bits of exponent
and 3 bits of mantissa.
3 bits of mantissa may not be enough and can result in choosing
suboptimal collapse order. Ideally we should probably use 5 bits here,
but that needs much more stack space.
For now, switch to 8+4 bits but to avoid doubling the stack usage,
constrain the exponent range on the high end so that excessively high
errors (>2^32) are bucketed together, as they are not useful.
In the future there's an opportunity to similarly constrain exponent
space on low end by clamping errors that are too low to zero.
In addition to improving the error selection in some cases this also can
sometimes reduce the amount of simplification passes as eligible
collapses in error limited regime get sorted better and can be processed
earlier.
In large meshes with complex topology we occasionally hit a case where
error_goal cutoff is not monotonic: a previous pass would simplify up to
a certain goal, but a subsequent pass would arrive at a smaller goal
(for example as invalid collapses get eliminated) and hit it before an
error that it already encountered.
If we already collapsed an edge with a given error it is always correct
to collapse other edges with a smaller error. This change tweaks the
conditional, which results in fewer passes on some meshes (eg
thai_buddha gets ~10% faster to simplify), 2-3% smaller error on some
meshes, and occasionally 1-2% larger error; most meshes simplify as they
did before however.
We now record the reason for each pass termination and adjust edge
collapse goal logic to match the code we are actually using for
rejection; previously, goal in the log was used as an "ideal" error
assuming no collapses are locked in progress but that is not realistic.
We now display the actual goal used or, if the collapse list is
exhausted, the error limit, which should be more clear.
For meshopt_simplifyWithAttributes, the weights depend on the attribute
type so it is probably best to leave the guidance to the documentation.
For meshopt_simplifyPoints, we can just suggest 1.0.
Since the error for points is pos + color_weight * col, it is hard to
tweak color weight to be scale-independent. We had a similar issue in
the edge collapse metric, but here the issue is complicated by the fact
that it's incorrect to compute errors as pos * (1 + col), since multiple
points can have the same position but the color delta must be used for
picking the right replacement.
As a compromise, we scale the color weight by the grid scale; since the
maximum position error along any axis is the grid scale, this makes the
errors compatible, and makes it easier to tweak the weight: similarly to
edge collapse, a weight of 1 is a good default; at a weight of 1 a
distance of 1 in color is equivalent to a worst case positional delta,
so a point like this will only be selected if there is no closer option.
Arseny Kapoulkine