GitLab

When the input coordinates to the hash function were integers (in
floating point form), the resulting hash function was incredibly poor.

It generated too many collisions because it mostly used the entropy from
the lower bits, and for integer values many lower bits are 0.

This change fixes the problem by lightly mixing the bits before hashing,
which seems to completely fix this issue in practice. On a Minecraft
export, the stats are as follows:

Total number of vertices (with many duplicates): 13 408 528
Number of unique 32-bit hashes with Murmur: 2 525 651
Number of unique 32-bit hashes with spatial hash: 205 457
Number of unique 32-bit hashes with scrambled spatial hash: 2 525 626

Without this, we'd silently skip the rescale step when using basisu for
encoding.

Remove outdated information about `-tb` option.

Fixes #272.

DFD for ETC1S images seems to be in continuous flux :( This change
updates it again to match the current validation code in ktx2check.

The previous change missed one version number due to the use of "whole
word" string search.

gltfpack: Fix various issues with texture compression

When using native Windows builds and using TOKTX_PATH or BASISU_PATH
that had spaces in them, gltfpack didn't automatically quote these,
resulting in the executable not being runnable.

We now automatically quote paths on Windows that have spaces in them to
fix this.

When -vv command line argument is used we now don't suppress command
output when testing the existence of toktx/basisu executables; this
should help future diagnosis of issues around launching these easier.

Our previous code blindly replaced the executable in the input command
with the env. variable value, which actually didn't handle cases when
the environment variable wasn't set and additionally didn't handle paths
with spaces well.

We now use shell:false execution option and give it a pre-split command
line - this doesn't work for arguments with spaces but we never handled
them correctly (and also they shouldn't occur as the paths that are
passed to the compressor are that of temp files...).

gltfpack: Restructure mesh processing to filter streams first

While filtering redundant streams during mesh optimization almost always
works well, there are rare cases where the input meshes have
inconsistent redundant streams (that block merging), and even though
these streams are removed that happens too late after the merging has
already been done.

This change splits off stream filtering from general mesh processing so
that we can run it early. This also slightly simplifies the flow since
we only need combined material information for filtering anyhow.

Reported in https://github.com/zeux/meshoptimizer/discussions/262.

Updated cgltf to 1.10, fast_obj to 1.1 and sdefl to latest.

Also fix gltfpack version in the header comment which was supposed to be
0.15 for a while now.

vertexcodec: Improve Wasm SIMD movemask fallback

Instead of using bit shifts to compute the bit mask, use a magic 64-bit
constant to extract the necessary bits in one multiply & shift per
64-bit lane.

The constant has been found using z3 SMT (thanks to @0b0000000000000 for
the idea) with the following program:

	; $ z3 bits.smt2
	; sat
	; (model
	;   (define-fun magic () (_ BitVec 64)
	;     #x000103070f1f3f80)
	; )

	(set-logic BV)

	(declare-const magic (_ BitVec 64))

	(define-fun same ((v (_ BitVec 8))) Bool
	 (or (= v #x00) (= v #xFF)))

	(assert
	  (forall ((x (_ BitVec 64)))
	    (let ((y (bvmul x magic)))
	      (or
		(not
		  (and
		   (same ((_ extract 63 56) x))
		   (same ((_ extract 55 48) x))
		   (same ((_ extract 47 40) x))
		   (same ((_ extract 39 32) x))
		   (same ((_ extract 31 24) x))
		   (same ((_ extract 23 16) x))
		   (same ((_ extract 15 8) x))
		   (same ((_ extract 7 0) x))
		   )
		)
		(and
		  (= ((_ extract 63 63) x) ((_ extract 63 63) y))
		  (= ((_ extract 55 55) x) ((_ extract 62 62) y))
		  (= ((_ extract 47 47) x) ((_ extract 61 61) y))
		  (= ((_ extract 39 39) x) ((_ extract 60 60) y))
		  (= ((_ extract 31 31) x) ((_ extract 59 59) y))
		  (= ((_ extract 23 23) x) ((_ extract 58 58) y))
		  (= ((_ extract 15 15) x) ((_ extract 57 57) y))
		  (= ((_ extract  7  7) x) ((_ extract 56 56) y))
		)
	      )
	    )
	  )
	)

	(check-sat)
	(get-model)

This improves vertexcodec performance by ~5% on latest node.js/x64.

gltfpack: Implement support for KHR_materials_variants

To make sure that all variants can be used interchangeably we need to
make sure that whenever multiple materials can be used on a given mesh,
the quantization grid for these materials matches.

Since multiple meshes can use a single material as well, this means that
multiple materials can be bound by the same quantization rules even if
they are never used on the same mesh, for example:

	mesh 0: materials 0, 1
	mesh 1: materials 2, 3
	mesh 2: materials 0, 3

Here all 4 materials must use the same quantization settings even though
materials 1 & 2 never overlap; to make all 3 meshes render correctly we
need to use the common quantization for all 3 meshes for all 4
materials.

To make this work, we use union-find to find a single "canonical"
material for each source mesh & material; we use that slot to accumulate
UV bounds and then redistribute the resulting quantization parameters to
all relevant materials.

When a mesh uses multiple materials through the use of variants, we need
to make sure that the quantization parameters for UV for a given
material incorporate all meshes that refer to it, including variants.

In addition, when processing a mesh, we need to take all variant
requirements into account, so that e.g. if only one material needs a
second UV set, we still include it even if it's a variant.

This isn't quite correct in cases when materials are used in other
meshes as well, since we need to ensure that the quantization data is
the same across all materials.

Instead of merging materials across meshes, we find unique materials
first by going just through the material list, and then simply remap
mesh materials and variants.

This has a slightly different complexity - from O(meshes * materials) to
O(materials^2) - however, assuming each material is used by at least one
mesh in the source data, the resulting algorithm is still faster.

We were previously emitting the same material mapping for all primitives
in a batch.

This change implements basic support for material variants. Each mesh
now keeps track of a set of material mappings; mesh merging is limited
to cases when the variant set is the same, and all material variants are
preserved.

Since we don't correctly compute the UV bounds for variant materials,
this only works without quantization so far.

This adds support to KHR_materials_variants, stored as an array of
mapping pairs.

gltfpack: Add support for KHR_materials_volume

This extension is in draft but the specification is reasonably complete.
This change adds support for the extension as well as fixing a bug with
KHR_materials_specular writing.

This change is https://github.com/jkuhlmann/cgltf/pull/133 with an extra
float.h include to keep the code compiling.

gltfpack: Update KHR_materials_specular to match new draft

Instead of implementing separate queries for texture transform & texture
set, this change centralizes querying of material requirements in
analyzeMaterials and calls it once before mesh processing.

This allows us to also fold the image type classification into the same
function, which makes adding new material extensions less fragile, and
additionally fixes a corner cases where tangent information could be
removed from meshes that had clearcoat normal map without a regular
normal map.

image/basis and .basis aren't standard per glTF spec; when support for
using Basis encoding directly was removed, two conditions were missed
that are now redundant.

This change adjusts the implementation of KHR_materials_specular; the
last update to the specification split the single texture (RGB+A) into
two separate texture slots (RGB + A). This requires associated changes
to handle the case when these are separate.

The cgltf change is using this PR:
https://github.com/jkuhlmann/cgltf/pull/131

image/basis and .basis aren't standard per glTF spec; when support for
using Basis encoding directly was removed, two conditions were missed
that are now redundant.

indexgenerator: Implement support for triangle adjacency index buffers

This code is identical and self-sufficient so it's easy to extract.
Building the edge table is more specialized due to the need for storing
the opposite vertex, and the hasher along with other data is necessary
during lookup, so it's better to leave that duplicated for now.

Several algorithms that use geometry shaders to render data require
adjacency information; triangle-with-adjacency topology in various APIs
provides a way to supply 3 extra vertices per each triangle that
represent vertices opposite to each triangle's edge.

This data can then be used to compute silhouettes and perform other
types of local geometric processing.

This change implements the data preprocessing step that is similar to
the previous tessellation IB - but instead of storing vertices that
adjoin the triangle from the opposite side, we need to store
complementary / opposite vertices of adjacent triangles, which requires
a separate temporary table.

indexgenerator: Implement support for PN-AEN tessellation buffers

To render a mesh with normal/UV seams using hardware tessellation, the
PN-triangles method is not sufficient as it produces cracks on normal
discontinuities (position displacement based on normal is not consistent
along both sides of the seam), and displacement mapping uses slightly
different texture samples which results in cracks along UV seams.

In 2010, NVidia proposed a PN-AEN tessellation scheme that fixes the
problem around normal discontinuities by using opposite edge normals and
averaging the resulting control point data. In 2011, NVidia proposed a
further tweak on top of this technique that allows to select the
"dominant" edge by choosing the min. edge index out of the
current/adjacent edges, and using the UV data from that edge on the
patch edges to sample the displacement data. For corners, there can be
more than two wedges that have the same position, so you need to store
the dominant vertex for each patch corner as well.

As a result, generating a 12-vertex patch for each input triangle allows
to use the hardware tessellation engine to implement PN-AEN (using 9
vertices) and/or displacement mapping (using 3 more vertices) without
cracks.

This change implements the data preprocessing step for this algorithm as
meshopt_generateTessellationIndexBuffer; this index buffer can be
directly fed to the GPU along with the requisite hull/domain shaders.

For implementing the shader code, the following papers are recommended:

John McDonald, Mark Kilgard
Crack-Free Point-Normal Triangles using Adjacent Edge Normals. 2010

John McDonald
Tessellation on Any Budget. 2010

Bryan Dudash
My Tessellation Has Cracks! 2012