• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.


  • Content count

  • Joined

  • Last visited

Community Reputation

825 Good

About Anfaenger

  • Rank
  1. 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 2-manifold (e.g. they often have singular vertices (hourglass-like 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 non-manifolds? (For 2-manifold meshes I can quickly build a compac (half-)edge adjacency table using a linear scan and sorting.)  
  2. 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 fixed-size 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?
  3. Hi! I'd like to render a procedurally-generated Earth-sized voxel planet (i.e. not using heightmaps and quadtrees). I have mostly working view-dependent octree-based crack-free rendering of a gigantic smooth (i.e. not blocky/Minecraftish) isosurface. If I make the world too big (16 LoDs), floating-point precision (?) starts to break down: the surface is no longer smooth but dimpled, edges become jagged, and large ugly-looking 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?
  4. Hi, I'd like to implement multi-threaded 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 (octree-based) frustum culling in favor of the DOD approach, because the former is 'branchy' and un-threadable (and also more messy).)
  5. 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.)
  6.   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 LoD0-chunk (smallest) containing the view point. AABBi eyeAABBi; // Min-corner 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 non-negative 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, clipmap-style LoD regions (the third picture; the first uses 1-norm 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.  
  7. Hi there! In my octree-based voxel terrain engine, to prevent cracks, each octree node (chunk) must know the LoDs/sizes of its neighbors. Currently, this info is stored as 18-bit adjacency masks (for 6 face- and 12 edge-adjacent 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 integer-based (i.e. not use floating-point) and cause a square, clipmap-style 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 "[Tchebychev|Chessboard|Center] Distance" or "maximum [metric|norm]"): /// the maximum of the absolute rank- and file-distance 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) ); }
  8. 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 32-bit 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 memory-efficient solution based on snapping positions to some global grid?  
  9. 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 on-demand, 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/T-junctions (except for pixel-sized gaps far from camera).   Here is a picture from a week ago (gyroid, each LOD is 4x4x4 cells):     1) How to re-generate 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 far-away 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, 'bottom-up' mesh connects seamlessly with procedurally-generated, 'top-down' 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?  
  10.   IIRC, Ronen Tzur's (Uniform) Dual Contouring sample contains some well-commented 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.)  
  11. 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 cone-like 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, Minecraft-style / Bloxel / Boxel / Cuberille worlds). 2) QEF_Solver_Simple - simply places the vertex into the mass point (i.e. averages all intersections - smooth, Surface-Nets style). 3) QEF_Solver_ParticleBased - uses Leonardo Augusto Schmitz's easy-to-understand 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, Particle-based minimizer function". I think, some google summer-of-code 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
  12. [!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 Distance-Dependent 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 NegX-vertices 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?
  13. Hey! I suggest you use linear octrees: 0) Build a full-res, 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 edge-adjacent cells.   As a powerful optimization, you can mantain an active edge mask for each cell as in "Out-of-core adaptive iso-surface extraction from binary volume data, R. Uribe Lobello et al. / Graphical Models 76 (2014), PP. 593–608: 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 hash-table for cell searching.   Advantages: - super simple (10x less code that the standard, recursive top-down impl); - the resulting meshes are more vcache-friendly.   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 well-suited for out-of-core 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 sharp-feature 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 de-quantizing vertex positions. const OctreeBoundsF rootBounds = { V3f::Zero(), _options.rootSize }; mxDO(_mesh.vertices.SetNum(cells.Num())); // calculate world-space _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 right-handed Z-up 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 right-hand rule to the edge loop. UP NORTH | / | / WEST--O--EAST /| / | SOUTH DOWN LABELING OF VERTICES, EDGES AND FACES: Vertex enumeration: 6___________7 /| / / | /| / | / | 4------------5 | | 2________|__3 | / | / | / | / | / |/ 0/___________1 or using locational (Morton) codes (X - lowest bit, Y - middle, Z - highest): 110__________111 /| / / | /| / | / | 100-----------101 | | 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 right-hand 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 edge-adjacent 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; } /// Edge-table 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 );
  14.   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 clip-box // so that it fully encompasses the inner clip-box (including the margin of one-cell-at-this-LOD 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; }
  15. 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 minimum-length translation vector for A so that A, when translated, fully covers B?     (Whence this problem came: I'm implementing a clipmap (aka 'nested clip-boxes') which is a LOD-scheme 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 A-B differences along each axis), but there surely is a simple and elegant solution.)