# Anfaenger

Member

48

827 Good

• Rank
Member

• Role
Programmer
• Interests
Design
Education
Programming

## Recent Profile Visitors

The recent visitors block is disabled and is not being shown to other users.

1. ## Calculate vertex normals for correctly lighting sharp features in a voxel terrain

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. ## Implementing an efficient memory cache (or choosing an existing library)

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. ## Procedural voxel planet generation - precision problems

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. ## Multi-threaded frustum culling - how to gather and where to store visibility results?

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. ## Implementing a fast dynamic vertex/index buffer pool

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. ## Checking if an octree node should be split (refined) or merged (collapsed)

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.

8. ## Pixel-sized gaps at LOD transitions after compressing vertices

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. ## Voxel Terrain - Updating LOD hierarchy after modifications

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. ## Dual contouring implementation on GPU

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. ## Dual contouring implementation on GPU

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. ## How to pass LOD blend factors to vertex shader for CLOD in a voxel terrain?

[!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?

14. ## Find the minimum translation to fit one box inside another

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. ## Find the minimum translation to fit one box inside another

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.)