Skip to content

A fast 2D and 3D game engine — TypeScript SDK, C++/WebAssembly core, visual editor. Ship one project to web, desktop, WeChat MiniGames, playable ads, and native Android / iOS.

3.2 KB
Raw Blame
// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
// SPDX-FileCopyrightText: Copyright (c) 2008-2026 NVIDIA CORPORATION & AFFILIATES. All rights reserved.
// SPDX-License-Identifier: Apache-2.0


#ifndef EXT_OCTREE_TETRAHEDRALIZER_H
#define EXT_OCTREE_TETRAHEDRALIZER_H

#include "ExtMultiList.h"
#include "ExtVec3.h"
#include "foundation/PxVec3.h"
#include "ExtInsideTester.h"

namespace physx
{
	namespace Ext
	{

		class InsideTester;

		// ------------------------------------------------------------------------------

		class OctreeTetrahedralizer 
		{
		public:
			OctreeTetrahedralizer();

			void clear();
			void createTetMesh(const PxArray<PxVec3> &verts, const PxArray<PxU32> &triIds,
				bool includeOctreeNodes = true, PxI32 maxVertsPerCell = 20, PxI32 maxTreeDepth = 5);

			void readBack(PxArray<PxVec3> &tetVertices, PxArray<PxU32> &tetIndices);			

		private:
			// input mesh

			PxArray<PxVec3> surfaceVerts;
			PxArray<PxI32> surfaceTriIds;

			// octree

			PxI32 maxVertsPerCell;
			PxI32 maxTreeDepth;

			struct Cell
			{
				void init()
				{
					firstChild = -1;
					orig = PxVec3d(0.0, 0.0, 0.0);
					size = 0.0;
					numVerts = 0;
					closestTetNr = -1;
					depth = 0;
				}

				PxI32 getChildNr(const PxVec3d& p);

				PX_FORCE_INLINE PxI32 getChildNr(const PxVec3& p) 
				{
					return getChildNr(PxVec3d(PxF64(p.x), PxF64(p.y), PxF64(p.z)));
				}

				PxI32 firstChild;
				PxI32 firstCellVert;
				PxI32 firstCellTet;
				PxVec3d orig;
				double size;
				PxI32 numVerts;
				PxI32 closestTetNr;
				PxI32 depth;
			};

			PxArray<Cell> cells;
			MultiList<PxI32> vertsOfCell;

			// tet mesh

			PxArray<PxVec3d> tetVerts;
			PxArray<PxI32> tetIds;
			PxArray<PxI32> tetNeighbors;
			PxArray<PxI32> tetMarks;
			PxI32 currentTetMark;
			PxArray<PxI32> stack;
			PxArray<PxI32> violatingTets;
			PxI32 firstABBVert;

			struct Edge 
			{

				PxI32 id0, id1;
				PxI32 faceNr, tetNr;

				void init(PxI32 _id0, PxI32 _id1, PxI32 _tetNr, PxI32 _faceNr) 
				{
					this->id0 = _id0 < _id1 ? _id0 : _id1;
					this->id1 = _id0 > _id1 ? _id0 : _id1;
					this->tetNr = _tetNr;
					this->faceNr = _faceNr;
				}

				PX_FORCE_INLINE bool operator < (Edge e) const
				{
					if (id0 < e.id0) return true;
					if (id0 > e.id0) return false;
					return id1 < e.id1;
				}

				PX_FORCE_INLINE bool operator == (Edge e)
				{
					return id0 == e.id0 && id1 == e.id1;
				}
			};
			PxArray<Edge> edges;

			void clearTets();
			void createTree();
			void treeInsertVert(PxI32 cellNr, PxI32 vertNr);
			void createTetVerts(bool includeOctreeNodes);

			bool findSurroundingTet(const PxVec3d& p, PxI32 startTetNr, PxI32& tetNr);
			bool findSurroundingTet(const PxVec3d& p, PxI32& tetNr);
			void treeInsertTet(PxI32 tetNr);
			void treeRemoveTet(PxI32 tetNr);

			PxI32 firstFreeTet;
			PxI32 getNewTetNr();
			void removeTetNr(PxI32 tetNr);

			PxVec3d getTetCenter(PxI32 tetNr) const;
			bool meshInsertTetVert(PxI32 vertNr);

			InsideTester insideTester;
			void pruneTets();

			mutable float prevClip;
			mutable float prevScale;
			mutable PxArray<PxVec3> renderVerts;
			mutable PxArray<PxVec3> renderNormals;
			mutable PxArray<PxI32> renderTriIds;
		};
	}
}

#endif