
Advertisement
Anfaenger
Member
Content Count
48 
Joined

Last visited
Community Reputation
827 GoodAbout Anfaenger

Rank
Member
Personal Information

Role
Programmer

Interests
Design
Education
Programming
Recent Profile Visitors
The recent visitors block is disabled and is not being shown to other users.

Calculate vertex normals for correctly lighting sharp features in a voxel terrain
Anfaenger posted a topic in Graphics and GPU Programming
I have an indexed triangle mesh generated by Dual Contouring. I need to duplicate vertices lying on sharp features (i.e. corners and edges) and assign correct vertex normals ('flat' normals of the faces referencing those sharp vertices). Otherwise, lighting will look incorrect: the objects look odd and 'blobby', see the first picture below, where each vertex is shared by more than one face. [attachment=36223:lighting sharp features.png] Currently, I build from the triangle mesh a vertex <> face adjacency table, duplicate each sharp vertex (its feature dimension (corner,edge,plane) is known from Dual Contouring) for each face referencing this vertex and assign face normals to new vertices (the third picture in the row; there are also lighting seams across chunks, but that's a different problem). This is fast and easy, but leads to artifacts on sharp edges, where adjacent vertices in smooth regions shouldn't be split, as in the following image: [attachment=36224:sharp edges  lighting bug.png] I guess, I should identify and split crease edges instead of sharp vertices, but, unfortunately, meshes generated by Dual Contouring are not always 2manifold (e.g. they often have singular vertices (hourglasslike shape) and edges shared by four polygons). How can vertex normals be calculated for correctly lighting sharp features in this case? Is there a quick & dirty, simple and fast solution instead of a generic one for nonmanifolds? (For 2manifold meshes I can quickly build a compac (half)edge adjacency table using a linear scan and sorting.) 
Implementing an efficient memory cache (or choosing an existing library)
Anfaenger posted a topic in General and Gameplay Programming
Hi! I'm writing a procedural voxel>polygon engine and I need to frequently generate/save/load and destroy chunks. I'd like to avoid regenerating, and especially loading (== touching the disk) chunks, which have been recently used, by employing a memory cache. Ideally, I'd like to reserve a fixedsize memory block for the 'chunk cache', address cached chunks by their IDs and specify chunk eviction policy/expiration time. How to best implement such a cache? (i.e. fast and efficient, no fragmentation.) Could you give me any references to existing implementations? I found these libraries, but they seem too 'heavy' for my toy voxel engine: http://cachelot.io/ and memcached Is there anything more lightweight? 
Procedural voxel planet generation  precision problems
Anfaenger posted a topic in Graphics and GPU Programming
Hi! I'd like to render a procedurallygenerated Earthsized voxel planet (i.e. not using heightmaps and quadtrees). I have mostly working viewdependent octreebased crackfree rendering of a gigantic smooth (i.e. not blocky/Minecraftish) isosurface. If I make the world too big (16 LoDs), floatingpoint precision (?) starts to break down: the surface is no longer smooth but dimpled, edges become jagged, and large uglylooking black spots appear (wrong normals?). 1) How are such precision problems dealt with when generating very large terrains? Should I simply use 'doubles' as e.g. in the spacesim game Pioneer? 2) My isosurface sampling is slow, it runs on CPU and is implemented via an abstract 'SDF' interface, with lots of 'virtual's, etc. How should procedural generation be implemented on GPU? Should I use compute shaders or OpenCL? Should I post new 'GenerateChunk' requests in the current frame and retrieve them in the next frame to avoid stalls? Should I use 'doubles' on the GPU? 
Multithreaded frustum culling  how to gather and where to store visibility results?
Anfaenger posted a topic in Graphics and GPU Programming
Hi, I'd like to implement multithreaded frustum culling in my graphics engine, but I don't know how to best collect and 'merge' the results of visibility testing (i.e. an array of visible entities). I'm rewriting the renderer for fast frustum culling (i.e. storing AABBs (in SoA format) and pointers to graphics entities in two contiguous arrays), but I feel that having each worker thread writing pairs of {object_type, object_pointer} into a single array would be inefficient because of locking. What is a good (best?) way to gather visibility results from multiple threads and merge them into a single array for further processing? (I'm ditching hierarchical (octreebased) frustum culling in favor of the DOD approach, because the former is 'branchy' and unthreadable (and also more messy).) 
Implementing a fast dynamic vertex/index buffer pool
Anfaenger posted a topic in Graphics and GPU Programming
Hi! I'm implementing a destructible voxel terrain. For rendering changeable, dynamic geometry I need to frequently allocate and free dynamic vertex and index buffers. What is the preferred way to organize VBs/IBs for quick allocations and frees? (The usual approach is to organize buffers in several bins, round the size of each chunk up to the next power of two and iterate the linked list in the bin. But it degenerates to linear search if many chunks have almost equal size.) 
Checking if an octree node should be split (refined) or merged (collapsed)
Anfaenger replied to Anfaenger's topic in Graphics and GPU Programming
I've implemented your idea, it does work! Here is my code in case anybody would find it useful: int Calculate_Desired_LoD( const CellID& _nodeId, const V3f& _eyePosition ) { const int iNodeLoD = _nodeId.GetLOD(); const int iNodeSize = (1 << iNodeLoD); // size of this node, in LoD0 chunks // The bounding box of the node. AABBi nodeAABBi; nodeAABBi.mins = _nodeId.ToInt3() * iNodeSize; nodeAABBi.maxs = nodeAABBi.mins + Int3(iNodeSize); // The bounding box of the LoD0chunk (smallest) containing the view point. AABBi eyeAABBi; // Mincorner coordinates of the chunk containing the view point, in LoD0 chunks. eyeAABBi.mins = Int3( Float_Floor( _eyePosition.x / CHUNK_SIZE ), Float_Floor( _eyePosition.y / CHUNK_SIZE ), Float_Floor( _eyePosition.z / CHUNK_SIZE ) ); eyeAABBi.maxs = eyeAABBi.mins + Int3(1); const int distance = Calc_Chebyshev_Dist( nodeAABBi, eyeAABBi ); // in LoD0 chunks const int distance1 = Max( distance, 1 ); // bsr intrinsic expects arguments > 0 // LoD ranges increase as powers of two DWORD wantedLoD; _BitScanReverse( &wantedLoD, distance1 ); // log2(distance) return wantedLoD; } /// Computes Chebyshev distance between the two integer AABBs. int Calc_Chebyshev_Dist( const AABBi& _a, const AABBi& _b ) { Int3 dists( 0 ); // always nonnegative for( int axis = 0; axis < NUM_AXES; axis++ ) { const int delta_min = Abs( _a.mins[ axis ]  _b.mins[ axis ] ); const int delta_max = Abs( _a.maxs[ axis ]  _b.maxs[ axis ] ); if( _a.mins[ axis ] >= _b.maxs[ axis ] ) { dists[ axis ] = _a.mins[ axis ]  _b.maxs[ axis ]; } else if( _a.maxs[ axis ] <= _b.mins[ axis ] ) { dists[ axis ] = _b.mins[ axis ]  _a.maxs[ axis ]; } else { dists[ axis ] = 0; } } return Max3( dists.x, dists.y, dists.z ); } I use it so: if( _node.id.GetLoD() > Octree::Calculate_Desired_LoD( _node.id, eyePos ) ) then Split( _node ); It causes square, clipmapstyle LoD regions (the third picture; the first uses 1norm and the 2nd  Euclidean distance): But this function cannot still be used for neighbor LoD calculations. And it uses branches. I also use closest distance between eye position and the node's bounding box (or between bounding boxes). Otherwise, LoD regions may become rectangular. 
Checking if an octree node should be split (refined) or merged (collapsed)
Anfaenger posted a topic in Graphics and GPU Programming
Hi there! In my octreebased voxel terrain engine, to prevent cracks, each octree node (chunk) must know the LoDs/sizes of its neighbors. Currently, this info is stored as 18bit adjacency masks (for 6 face and 12 edgeadjacent nodes), with costly neighbor finding to update those masks, for each octree node (like four hundred nodes translating into two thousand checks!). I'd like to avoid maintaining adjacency masks and instead use an algorithmic approach. I need a fast function for checking if an octree node at the given position and with the given LoD/size exists in the octree, without walking the entire hierarchy. The function should preferably be integerbased (i.e. not use floatingpoint) and cause a square, clipmapstyle node arrangement. Here's the function I use for updating the octree; it ensures 2:1 LOD transitions, but sometimes creates rectangular 'rings' instead of cubic: /// returns true if the given node requires splitting bool Node_Should_Be_Split( const OctreeNode& _node, const OctreeWorld::Observer& _eye ) { const UINT nodeLoD = _node.id.GetLOD(); const UINT nodeSize = (1u << nodeLoD); const UINT nodeRadius = nodeSize / 2u; const UInt3 nodeCenterCoords = (_node.id.ToUInt3() * nodeSize) + UInt3(nodeRadius); const UINT distance = Chebyshev_Distance( Int3::FromXYZ(_eye.coordsInChunksGrid), Int3::FromXYZ(nodeCenterCoords) ); // Chebyshev distance is the 'smallest' norm: max(dx, dy, dz) <= distance(dx,dy,dz) <= dx + dy + dz. return distance < nodeSize * LOD_RANGE + nodeRadius; // this node is far away } /// Chebyshev distance (aka "[TchebychevChessboardCenter] Distance" or "maximum [metricnorm]"): /// the maximum of the absolute rank and filedistance of both squares. template< typename TYPE > TYPE Chebyshev_Distance( const Tuple3< TYPE >& _a, const Tuple3< TYPE >& _b ) { return Max3( Abs(_a.x  _b.x), Abs(_a.y  _b.y), Abs(_a.z  _b.z) ); } 
Pixelsized gaps at LOD transitions after compressing vertices
Anfaenger posted a topic in Graphics and GPU Programming
Hi there! I'm writing a voxel terrain engine which uses geomorphing/CLOD to render a seamless mesh which is composed of chunks with different LoDs (sizes and resolutions). Each vertex stores its attributes both at the current and the next, twice coarser LoD; the correct attributes are selected in the vertex shader based on the size of the chunk's neighbors. To reduce the size of a vertex to 32 bytes, I'm compressing vertex positions into 32bit integers: {x:11,y:11,z:10}. But this memory 'optimization' results in tiny gaps (dropped or shimmering pixels) at LOD transitions, like these: To avoid these gaps, boundary vertex positions must precisely match between adjacent chunks. I tried to quantize fine positions to 10 bits and coarse positions to 5 bits (so that 'quantization level/precision loss' would match between adjacent chunks which resolutions differ by 2), but that didn't work. Should I store vertex positions at full precision? Maybe, there is a simple and memoryefficient solution based on snapping positions to some global grid? 
Voxel Terrain  Updating LOD hierarchy after modifications
Anfaenger posted a topic in Graphics and GPU Programming
Hi! I'd like to be able to edit a procedurally generated voxel terrain. The terrain is represented by an octree which subdivides itself depending on the viewer's position. LODs are generated ondemand, progressively, from top to bottom. Each leaf node contains a mesh representing a part of the terrain surface at this node's LOD. Cracks are handled via geomorphing. I can fly over a large (~20 km) and boring terrain without any cracks/Tjunctions (except for pixelsized gaps far from camera). Here is a picture from a week ago (gyroid, each LOD is 4x4x4 cells): 1) How to regenerate the LOD hierarchy after some parts of the terrain have been modified? I want to be able to edit the floor right in front of the player (LOD0) as well as distant mountains (e.g., LOD6). In the former case, LODs of can be rebuilt lazily, via 'dirty flags'. But for faraway montains, LODs should be updated quickly, because they are currently being used for rendering. So, when recalculating LODs of 'dirty' nodes, I need to check if their parent is being used, and so on, all the way up the tree? Or maintain a queue with IDs of changed nodes, and after processing all nodes of LOD 'N' push onto the queue the IDs of their parents (LOD 'N+1')? There are other complications, e.g. ensuring that old border vertices are kept untouched during simplification so that the simplified, 'bottomup' mesh connects seamlessly with procedurallygenerated, 'topdown' parts. Actually, I have no idea how all of it should be implemented together. Could you please refer me to papers/code, or give me some ideas? 
Dual contouring implementation on GPU
Anfaenger replied to BlackJoker's topic in Graphics and GPU Programming
IIRC, Ronen Tzur's (Uniform) Dual Contouring sample contains some wellcommented numerical code. https://www.sandboxie.com/misc/isosurf/isosurfaces.html For the underlying theory, I can recommend the excellent book "Matrix Analysis & Applied Linear Algebra" [2000] by Carl D. Meyer, apart from classics such as "Matrix computations" and "Numerical Recipes in C". (I'm in no way a math geek, but the first book explains the theory very well.) 
Dual contouring implementation on GPU
Anfaenger replied to BlackJoker's topic in Graphics and GPU Programming
I use the standard approach: find the vertex which position minimizes the squared distance to the tangent planes, i.e. planes built from intersection points (of the cell's edges with the surface) and the surface normals at those points. If the minimizer lies outside the cell, I clamp it to the cell's bounds or place it into the mass point (average) of all intersection points (which causes unsightly dimples and notches in the reconstructed surface, e.g. see MergeSharp, SHREC papers). DC/DMC are far from perfect  a sharp conelike feature gets clamped if it passes through a face, but doesn't intersect any of the cell's edges. You can try to reconstruct a rotated cube, with one of its corners pointing up, and most likely that corner will get 'chamfered'. In my framework, I use different 'QEF' solvers (using a common 'virtual' interface): 1) QEF_Solver_Bloxel  simply places the vertex in the cell's center (for blocky, Minecraftstyle / Bloxel / Boxel / Cuberille worlds). 2) QEF_Solver_Simple  simply places the vertex into the mass point (i.e. averages all intersections  smooth, SurfaceNets style). 3) QEF_Solver_ParticleBased  uses Leonardo Augusto Schmitz's easytounderstand method with exact normals at intersection points to reduce complexity, can reconstruct smooth surfaces with sharpish features: http://gamedev.stackexchange.com/a/83757, "Efficient and High Quality Contouring of Isosurfaces on Uniform Grids, 2009, Particlebased minimizer function". I think, some google summerofcode Java impl used this method with ADC. 4) QEF_Solver_Direct_AtA  tries to solve the Least Squares problem using normal equations: A^T*A*x = A^T*b, simple and fast, but unstable. For an example you can see that swedish guy's impl on github, Emil (forgot his name), his blog is called "I love tits". 5) QEF_Solver_QR  Least Squares Solver from original authors (Scott Schaefer et al., 2011). 6) QEF_Solver_SVD_Eigen  uses the (excellent) Eigen math lib to solve LLS, e.g. as here: https://github.com/mkeeter/ao/blob/master/kernel/src/render/octree.cpp 7) QEF_Solver_SVD2  based on the code by Nick Guildea: https://github.com/nickgildea/qef 
How to pass LOD blend factors to vertex shader for CLOD in a voxel terrain?
Anfaenger posted a topic in Graphics and GPU Programming
[!EDIT!: I should've written this question as "How to ensure matching LOD blend factors on chunk faces in a voxel terrain?" Hi! I'm trying to adapt "Continuous DistanceDependent Level of Detail for Rendering Heightmaps (CDLOD)" by Filip Strugar to voxel terrain. In the paper above, geomorphing is used to solve two problems: 1) Eliminating cracks between chunks of different LODs; 2) Achieving smooth, continuous LOD transitions. For this to work, LOD morph/blend factors of vertices on "touching" boundary faces from adjacent chunks must coincide. E.g., I know that some particular octree node is touching a twice bigger node on PosX face, so for this smaller node all vertices on PosX face must have their LOD blend factors set to 1.0f (i.e. fully morph to parent vertex). At the same time, to prevent cracks NegXvertices of the bigger node must have LOD blend factors equal to zero. How to ensure in the vertex shader that blend factors of touching, boundary vertices concide between chunks? In the vertex shader, dynamically computed LOD blend factors must be set to their corresponding BoundaryFace_LOD_Factor? Do I need to associate each boundary vertex with the cube face on which the vertex lies? 
Dual contouring implementation on GPU
Anfaenger replied to BlackJoker's topic in Graphics and GPU Programming
Hey! I suggest you use linear octrees: 0) Build a fullres, maximally subdivided octree (basically, the same as uniform grid), simplify it by collapsing leaf nodes and create linear octree cells (store only leaf nodes with their address, locational codes or Morton codes). I've (probably) invented the following simple approach to Adaptive Dual Contouring: 1) Sort cells by size in increasing order (so that the smallest cells (or the deepest) are placed at the beginning of the array). 2) Create a mesh vertex for each cell. 3) Iterate each cell and create quads for each active edge of the cell, using binary search for finding edgeadjacent cells. As a powerful optimization, you can mantain an active edge mask for each cell as in "Outofcore adaptive isosurface extraction from binary volume data, R. Uribe Lobello et al. / Graphical Models 76 (2014), PP. 593–608: 3.2.3.1. Linear connectivity generation (P. 598)"; this will also allow you to sort cells in any order, or not sort them at all and using a hashtable for cell searching. Advantages:  super simple (10x less code that the standard, recursive topdown impl);  the resulting meshes are more vcachefriendly. Disadvantages:  somewhat slower (but OK for chunks of 32^3 cells);  may create isolated, unconnected vertices. I've been using this algo in my DC/DMC engine since may 2016. It's implemented on the CPU, but it can be easilty ported to GPU. Here's the reference code for ADC: /// Signed linear octrees are wellsuited for outofcore isosurface extraction. struct LinearOctree : LinearOctreeBase { struct Cell { Morton32 morton; //!< the (unique) locational code of this node // from LSB to MSB: // X8,Y8,Z7  quantized position of the representative vertex (relative to the cell's AABB) // S8  signs at corners (1 = inside, 0 = outside), cannot be zero or 0xFF // F1  is this a sharpfeature vertex? U32 data; //8,8,7, 1, 8  XYZ, sharp?, signs public: void PackData( const V3f& xyz01, const U8 signs, const bool sharp ) { //mxASSERT(vxNONTRIVIAL_CELL(signs)); this>data = (TQuantize<8>::EncodeUNorm( xyz01.x ) << 0 ) (TQuantize<8>::EncodeUNorm( xyz01.y ) << 8 ) (TQuantize<7>::EncodeUNorm( xyz01.z ) << 16) (signs << 23) (sharp << 31); } const V3f UnpackPosition() const { const U32 V = this>data; return V3f( TQuantize<8>::DecodeUNorm( V & 0xFF ), TQuantize<8>::DecodeUNorm( (V >> 8) & 0xFF ), TQuantize<7>::DecodeUNorm( (V >> 16) & 0x7F ) ); } const UINT UnpackSigns() const { return (this>data >> 23) & 0xFF; } bool HasSharpFeature() const { return (this>data >> 31) & 0x1; } bool operator == ( const Cell& other ) const { return this>morton == other.morton; } bool operator != ( const Cell& other ) const { return this>morton != other.morton; } bool operator < ( const Cell& other ) const { // smaller(=deeper) nodes must be placed first in the array return this>morton > other.morton; } }; public: DynamicArray< Cell > cells; //!< both keys and data are in the same array for simplicity public: LinearOctree( AHeap & heap ); public: /// Builds a linear octree directly from the isosurface. ERet FromSignedDistanceField( const SDF::Isosurface* _volume, const BuildOptions& _options, const AABB& _worldBounds, //!< octree bounds const UINT _resolution //!< octree resolution ); ERet FromHermiteData( const AVolumeSampler& _volume, const BuildOptions& _options, const V3f& _localBoundsSize,//!< size of octree AABB const UINT _resolution //!< octree resolution ); ERet FromSignedOctree( const SignedOctree& source, const AABB& octreeBounds, OctreeStats &stats ); void Empty(); }; ERet LinearOctree::Contour_ReferenceImpl( TriMesh & _mesh, const ContourOptions& _options ) { // The smallest leaves (or the deepest) are placed at the beginning: std::sort( cells.begin(), cells.end() ); // create vertices { // Scene bounds for dequantizing vertex positions. const OctreeBoundsF rootBounds = { V3f::Zero(), _options.rootSize }; mxDO(_mesh.vertices.SetNum(cells.Num())); // calculate worldspace _mesh bounds AABB meshBounds; AABB_Clear( &meshBounds ); for( UINT iCell = 0; iCell < cells.Num(); iCell++ ) { const Cell& cell = cells[ iCell ]; //mxASSERT(vxNONTRIVIAL_CELL(cell.UnpackSigns())); const U32 cellDepth = Morton32_GetCellDepth( cell.morton ); mxASSERT( cellDepth < MORTON32_MAX_OCTREE_LEVELS ); const AABB cellAABB = Calculate_Bounds_From_Morton_code( cell.morton, rootBounds ).ToAABB(); const V3f vertexPosition = AABB_GetOriginalPosition( cellAABB, cell.UnpackPosition() ); _mesh.vertices[ iCell ].xyz = vertexPosition; AABB_AddPoint( &meshBounds, vertexPosition ); } _mesh.localAabb = meshBounds; } { // node offsets for each edge of the cube (I'm using a righthanded Zup coordinate system) static const Int3 adjacentCellOffsets[12][3] = { Int3( 0, 1, 0 ), Int3( 0, 1, 1 ), Int3( 0, 0, 1 ), // 0 (X axis) Int3( 0, 0, 1 ), Int3( 0, 1, 1 ), Int3( 0, 1, 0 ), // 1 (X axis) Int3( 0, 1, 0 ), Int3( 0, 1, 1 ), Int3( 0, 0, 1 ), // 2 (X axis) Int3( 0, 0, 1 ), Int3( 0, 1, 1 ), Int3( 0, 1, 0 ), // 3 (X axis) Int3( 0, 0, 1 ), Int3( 1, 0, 1 ), Int3( 1, 0, 0 ), // 4 (Y axis) Int3(1, 0, 0 ), Int3( 1, 0, 1 ), Int3( 0, 0, 1 ), // 5 (Y axis) Int3( 0, 0, 1 ), Int3( 1, 0, 1 ), Int3( 1, 0, 0 ), // 6 (Y axis) Int3( 1, 0, 0 ), Int3( 1, 0, 1 ), Int3( 0, 0, 1 ), // 7 (Y axis) Int3(1, 0, 0 ), Int3( 1, 1, 0 ), Int3( 0,1, 0 ), // 8 (Z axis) Int3( 0, 1, 0 ), Int3( 1, 1, 0 ), Int3( 1, 0, 0 ), // 9 (Z axis) Int3( 1, 0, 0 ), Int3( 1, 1, 0 ), Int3( 0, 1, 0 ), // 10 (Z axis) Int3( 0, 1, 0 ), Int3( 1, 1, 0 ), Int3( 1, 0, 0 ), // 11 (Z axis) }; for( UINT iCurrentCell = 0; iCurrentCell < cells.Num()  1; iCurrentCell++ ) { const Cell& currentCell = cells[ iCurrentCell ]; const U32 cellDepth = Morton32_GetCellDepth( currentCell.morton ); // get position of the depth bit const U32 cellDepthBitMask = (1U << (cellDepth * 3)); // the index of the depth bit const U32 getBitsBelowDepthBit = cellDepthBitMask  1; // mask to extract bits below the depth bit const Morton32 cellCodeWithoutDepthBit = currentCell.morton & getBitsBelowDepthBit; const U32 getBitsAboveDepthBit = ~getBitsBelowDepthBit; // for checking overflow const Int3 cellCoords = Morton32_Decode( cellCodeWithoutDepthBit ); const UINT cornerSigns = currentCell.UnpackSigns(); //mxASSERT(vxNONTRIVIAL_CELL(cornerSigns)); U32 edgeMask = CUBE_EDGES_LUT.edgeMask[ cornerSigns ]; while( edgeMask ) { U32 iCurrentEdge; edgeMask = ExtractNextEdge( edgeMask, &iCurrentEdge ); U32 adjacentCells[3]; //!< indices of the other three cells sharing the edge UINT numAdjacentCells = 0; UINT octantMask = (1U << topMostOctant); for( UINT iAdjacentCell = 0; iAdjacentCell < 3; iAdjacentCell++ ) { mxOPTIMIZE("use dilated integers"); const Int3 edgeNeighborPos = cellCoords + adjacentCellOffsets[iCurrentEdge][iAdjacentCell]; // no need to check for underflow, because negative indices have the sign bit set and will fail the overflow check // check for underflow // if( (edgeNeighborPos.x >= 0) && (edgeNeighborPos.y >= 0) && (edgeNeighborPos.z >= 0) ) { const Morton32 neighborCode = Morton32_Encode_NoOverflowCheck( (U32)edgeNeighborPos.x, (U32)edgeNeighborPos.y, (U32)edgeNeighborPos.z ); // check for overflow: // after addition, Morton codes can 'wrap' around, connecting cells across the octree boundary and causing stretched polys. if( neighborCode & getBitsAboveDepthBit ) { // the neighbor cannot lie deeper in the octree than this cell continue; } // add the depth bit const Morton32 neighborCodeWithDepthBit = neighborCode  cellDepthBitMask; const U32 neighborIndex = FindLeafIndex( neighborCodeWithDepthBit, iCurrentCell+1/*skip this cell and all smaller*/ ); if( neighborIndex != CELL_NOT_FOUND ) { adjacentCells[ numAdjacentCells++ ] = neighborIndex; // found an adjacent leaf } else { continue; // neighbor not found  no quads should be formed } } }//For each edge neighbor. //NOTE: may contain a duplicate cell (which will correspond to the largest neighbor) if( numAdjacentCells == 3 ) { // determine orientation of the quad from the signs of the edge's endpoints // signs must be different => only one point should be examined const UINT iPointA = CUBE_EDGE[ iCurrentEdge ][0]; //const UINT iPointB = CUBE_EDGE[ currentEdge ][1]; // signs can only be 0 or 1 const UINT signA = (cornerSigns >> iPointA) & 1; //const UINT signB = (cornerSigns >> iPointB) & 1; //if( signA > signB ) { if( signA ) { // The first corner is inside the surface, the second is outside detail::AddQuad( iCurrentCell, adjacentCells[0], adjacentCells[1], adjacentCells[2], _mesh ); } else { // The second corner is inside the surface, the first is outside detail::AddQuad( adjacentCells[2], adjacentCells[1], adjacentCells[0], iCurrentCell, _mesh ); } }//If the edge is shared by 4 cells. }//For each active edge of the current cell. }//For each cell. }//Create Quads return ALL_OK; } static int FindCellIndex( const U32 _numLeaves, const LinearOctree::Cell* _leaves, const U32 _startIndex, const Morton32 _code ) { int lo = _startIndex, hi = _numLeaves  1; while( lo <= hi ) { int mid = lo + (hi  lo) / 2; if( _code == _leaves[mid].morton ) { return mid; } else if( _code < _leaves[mid].morton ) lo = mid + 1; else { hi = mid  1; } } return 1; } /// searches for the deepest (i.e. the smallest) leaf containing the given point U32 LinearOctree::FindLeafIndex( Morton32 _code, U32 _startIndex ) const { mxASSERT(Morton32_GetCellDepth(_code) > 0); while( _code > 3 ) { const int iCell = FindCellIndex ( this>cells.Num(), this>cells.Raw(), _startIndex, _code ); if( iCell != 1 ) { return iCell; } _code = _code >> 3; // search one level higher } return CELL_NOT_FOUND; } Cube/Edge relations: /* Z  /Y  / /_____X (0,0,0) Face orientation (normal)  apply righthand rule to the edge loop. UP NORTH  /  / WESTOEAST / /  SOUTH DOWN LABELING OF VERTICES, EDGES AND FACES: Vertex enumeration: 6___________7 / / /  / /  /  45   2__________3  /  /  /  /  / / 0/___________1 or using locational (Morton) codes (X  lowest bit, Y  middle, Z  highest): 110__________111 / / /  / /  /  100101   010_________011  /  /  /  /  / / 000/___________001 (see Gray code, Hamming distance, De Bruijn sequence) NOTE: two vertices are connected by an edge, if their indices differ by one and only one bit. Cube edge enumeration (edges are split into 3 groups by axes X,Y,Z  this allows: edge_axis = edge_index / 4; (numbered using righthand rule): ______2______ / / 5 11 6  /  / 10 3   _____1_____  /  / 8 4 9 7  /  / /___________/ 0 */ static const U32 CUBE_EDGES_AXIS_X = (BIT(0)  BIT(1)  BIT(2)  BIT(3)); static const U32 CUBE_EDGES_AXIS_Y = (BIT(4)  BIT(5)  BIT(6)  BIT(7)); static const U32 CUBE_EDGES_AXIS_Z = (BIT(8)  BIT(9)  BIT(10)  BIT(11)); /// maps the given cube edge to the diagonally opposite one, e.g. 0 > 2, 3 > 1, 10 > 8, etc. static mxFORCEINLINE UINT DiagonallyOppositeEdge( UINT iEdge ) { return ((iEdge + 2) % 4) + (iEdge & ~3); } /// Returns the index of the edge on the given edgeadjacent cube 'iAdjCube', /// where iAdjCube is the index [0..3] of the cube around the edge, listed in circular order. /// E.g. for a cube edge 2 the returned values will be 2, 3, 0, 1; /// for a cube edge 8 the returned values will be 8, 9, 10, 11; /// for a cube edge 6 the returned values will be 6, 5, 4, 7. static mxFORCEINLINE UINT EdgeOnNextAdjacentCube( UINT iEdge, UINT iAdjCube ) // iAdjCube <E [0..3] { const UINT iEdgeOnNeighbor = (iEdge + iAdjCube) % 4 + (iEdge & ~3); return iEdgeOnNeighbor; } mxFORCEINLINE U32 ExtractNextEdge( U32 edgeMask, U32 *edgeIndex ) { DWORD iEdge; _BitScanReverse( &iEdge, edgeMask ); edgeMask &= ~(1u << iEdge); // remove the edge bit from mask *edgeIndex = iEdge; return edgeMask; } /// Edgetable gives all the edges intersected in a given cube configuration: struct ActiveEdges { U16 edgeMask[256]; //!< set bits correspond to active edges }; alignas(128) extern ActiveEdges CUBE_EDGES_LUT; // precomputes a set of intersecting edges for each cube/sign configuration void GenerateActiveCubeEdgesTable( ActiveEdges & LUT ); 
Find the minimum translation to fit one box inside another
Anfaenger replied to Anfaenger's topic in Graphics and GPU Programming
Not really. B could be anywhere, e.g. to the bottom left, or top left, or top right of A. I need to align A (e.g. move it to the bottom left, or top left, or top right) so that it fully contains B. Yes, each LoD box is double the size of the previous (contained) box, but they cannot touch (to ensure proper 2:1 LoD transitions), so B is slightly larger (border size == 1 cell of A). Thanks for the answers, anyway. I just wanted to know if there's a nicer approach. Btw, here's my (fully working) ugly code: Int3 CalcMinCorner( const AABBi& _bigger, const AABBi& _smaller ) { ASSERT(Int3::GreaterOrEqual( _bigger.FullSize(), _smaller.FullSize() ) ); Int3 result( _bigger.mins ); if( !_bigger.Contains( _smaller ) ) { // Find the minimum translational distance to move the current clipbox // so that it fully encompasses the inner clipbox (including the margin of onecellatthisLOD width). for( int axis = 0; axis < 3; axis++ ) { const int deltaMins = Abs( _bigger.mins[ axis ]  _smaller.mins[ axis ] ); const int deltaMaxs = Abs( _bigger.maxs[ axis ]  _smaller.maxs[ axis ] ); if( deltaMins < deltaMaxs ) { if( _smaller.mins[ axis ] < _bigger.mins[ axis ] ) { result[ axis ] = _bigger.mins[ axis ]  deltaMins; } } else { if( _smaller.maxs[ axis ] > _bigger.maxs[ axis ] ) { result[ axis ] = _bigger.mins[ axis ] + deltaMaxs; } } } } return result; } 
Find the minimum translation to fit one box inside another
Anfaenger posted a topic in Graphics and GPU Programming
There are two cubes (AABBs), A and B, A is always bigger than B. When B is not fully inside A, how to calculate the minimumlength translation vector for A so that A, when translated, fully covers B? (Whence this problem came: I'm implementing a clipmap (aka 'nested clipboxes') which is a LODscheme allowing for ludicrously large volumetric terrains (e.g. planets in space). The space around the viewer is partitioned into a set of nested boxes of the same resolution, but different sizes. (in this image crack patching is not finished yet:) (apparently, clipmaps were first used for rendering planets in "Alien" [1979]:) Usually, the boxes remain nested and roughly centered around the viewer, but if the camera moves too fast, the inner boxes can intersect their 'parent' (the box, representing a coarser LoD) or even jump ouside of it. So, I need to update the positions of all boxes starting from the innermost one (immediately surrounding the viewer). I've written some crappy code to update LOD levels (if A doesn't fully contain B, then offset A by smallest absolute magnitude of mins/maxs AB differences along each axis), but there surely is a simple and elegant solution.)

Advertisement