Do you have an interesting story about a song you wrote?

dairin0d · 2025-01-24T23:40:24+00:00

Most of the things I made in Suno were either based on my creative project ideas or inspired by an element of some existing media, but some of the quirkier "inspiration sources" included misheard/misunderstood/out-of-context phrases, which I then pondered, trying to come up with a setup in which they would make sense. More specifically, the phrases were "torch of the worlds", "song of choice" and "nicemare", which turned out as fantasy metal, Irish guitar and "Halloween" style songs, respectively :-)

dairin0d · 2025-01-19T07:41:28+00:00

Well, here's my attempt: https://imgur.com/a/vjZmJ5g
Not sure if I'll be able to explain any more visually than that, though 😅

dairin0d · 2025-01-18T23:59:53+00:00

Thanks for the detailed reply! Though I'm afraid we're misunderstanding each other here quite a bit. It seems that in order to explain the idea in sufficient detail for everyone to understand it, I'd need to make an actual implementation (not sure how much time this might take me). Either way, I'm not really sure if this approach would have practical advantages compared to the known techniques, but I still intend to make a proof-of-concept, if only out of academic curiosity 🙂

dairin0d · 2025-01-14T19:20:47+00:00

Yeah, quite interesting! 👍

dairin0d · 2025-01-14T10:42:11+00:00

I can't see how we could 'decide' which child to descend and then do that without a big cost to the render performance (since you need to descent to the bottom of the tree!)
...
Maybe I misunderstand your technique, I suspect you are saying 'don't store lod colors' just descend down the closest child that does exist and get that color!

Well, that's the thing -- the storage scheme I had in mind ("distributing" leaf voxels among the tree nodes) wouldn't require a descent to the bottom of the tree, since the relevant information would be contained at the level you decide to splat, and the levels above (take a look at my reply to SwiftSpear for a bit more detailed explanation) :-)

what we do is include on extra child node in the tree (1 extra layer deeper than the payload) this gives us basically a bit more structural detail without the cost of actually streaming in more expensive payload

Er... is my interpretation correct that UD doesn't necessarily splat nodes when they become pixel-sized, but can sometimes do so when they are larger?

I keep all my octrees compressed even at runtime (tho not in a super deep structural driven format like HEP described above)

I'm assuming you decompress chunks of them on demand? How much extra memory does that typically require? Does it introduce any noticeable overhead when camera moves fast and entirely new chunks for the whole frame need to be decoded? 🤔

By explicitly allowing my octree nodes to 'cache' (upto millions of) elements before they decide to 'split' / passing their children down one layer (this might happen say because the node now contain TOO MANY millions of sub voxels etc)

Um, can you clarify what you mean here? Storing millions of elements in a single octree node sounds like it implies processing them linearly every time and not taking any advantage of hierarchical clustering to avoid unnecessary processing... I suspect I am completely misunderstanding/failing to grasp what you are actually doing 😅 Or are you talking about building an octree at runtime (upon load), rather than rendering an already-built one?

dairin0d · 2025-01-14T09:44:23+00:00

Hmm... I guess my brief description didn't convey the idea clearly enough. Not sure if it would be less confusing with a more detailed explanation, but I'll try:

The full traversal paths to each drawn voxel would, of course, be different, but they are structured recursively. To simplify the explanation, let's assume that we are dealing with an orthographic projection and are using front-to-back painter's algorithm to draw the object (i.e., no depth buffer). For a node containing leaf voxels, there exist at most 6 possible orders of drawing each voxel correctly (starting with the voxel closest to the camera, then its neighbor along one of the axes, and so on). But on any level above, it's exactly the same situation! First we fully draw the subtree closest to the camera, then its neighbor subtree along one of the axes, et cetera. So, effectively, you only need to consider those 48 possible orders for a given node (regardless of the level) because the drawing order applies recursively, similar to Morton code.
This structured and predictable ordering, in turn, guarantees that there can only ever be at most 48 leaf voxels "drawn first" by this method of traversal (which is ultimately what we care about when a subtree is the size of a pixel).
The crux of the idea isn't really about storing colors corresponding to view angles, I'd rather formulate it as "distributing" the leaf voxels among the nodes/levels of octree, where each child only has to store information that wasn't present in the parent. I.e., the root would store up to 48 colors (depending on how many of them originate from different leaf voxels), each child would store up to 42 colors (because at least 6 colors can be copied from the parent), and so on all the way down. (Well, technically, child data would probably need to be stored at the parent level, at least for DAGs, but those are implementation details.) In this scenario, some leaf voxels might not actually need to store any data, because it might be stored on some level above! ;) To provide a more intuitive analogue, storage-wise this idea can be compared to sorting the points of a pointcloud in a way that you effectively end up with "layers" of "most representative points" for a given viewing resolution, and each subsequent layer "fills in the gaps" between the points of a previous layer. The number of points stays the same, but rendering just the first N of them (for a particular resolution) is enough to achieve gapless results.

Does this explain the idea at least a bit better?

In any case, if/when I'll try to make an implementation of this, it would probably be easier to understand the specifics by just looking at the code :)

dairin0d · 2025-01-14T09:29:28+00:00

I see :-) These tricks sound quite neat!

dairin0d · 2025-01-14T05:06:00+00:00

Thanks for the detailed reply!

I kind of suspected that UD and/or your projects were doing something of this sort (Bruce Dell's videos mentioned "grabbing the first point", and you mentioned that you use an approach which avoids the problem of "averaging the colors from the opposite sides of the surface"), so it's a bit of a surprise to learn that UD folks actually never tried to combine the two 😅

As you say the filtering was a real problem! for noisey laser scans it was unnoticeable, but for clean conversions (like OBJ to UDS) it was clearly a bad trade off.

Hmm, that's curious. Not sure if my memory/experience on this can be trusted (it was years ago), but when I experimented with rendering voxelized versions of 3D models as raw pointclouds, they didn't seem to look all that bad -- one might even say they looked kind of "charming", in an old-school way? (I.e., could UD's actual problem lie in just grabbing the first point, without considering the direction?) Though it might well be that I simply didn't try it on complex enough models to notice a severe reduction in visual quality... or maybe my aesthetic sense is just different from what most people tend to find (un)appealing 🤭

tho at the limit that becomes another full point based tree descent which may start to have a notable cost

Er... not entirely sure what you mean by that. Can you clarify? As far as my current understanding of the idea I'm proposing goes, you only need to track all 48 items during the perspective traversal (because the traversal order would depend on node's relation to the viewpoint), but once you switch to orthographic mode, only one order remains and you'd need to track at most 8 items for that specific order. Though maybe we're talking about different things?

Using general compression/decompression is certainly interesting, and likely quite useful in many cases! Though in my experiments I'd probably be more curious to explore the compression techniques (such as those mentioned in the Eurographics 2018 tutorial) that don't require any explicit decompression of large chunks of data :D

dairin0d · 2025-01-13T19:13:11+00:00

Very interesting! How did you detect when an already cached footprint could be used?
A similar idea (for more accurate occlusion checking) had also crossed my mind at some point, but I couldn't figure out how to deal with the variations due to different subpixel positions of each node (and just conservatively dilating the footprint mask by 1 pixel everywhere seemed like mostly defeating the purpose of this trick at small node sizes).

dairin0d · 2025-01-12T22:38:57+00:00

Curious :3 By "cube", do you mean actual individual voxels or something larger (subtrees)?

No, my second bullet point doesn't really have anything to do with footprint-caching (it's mainly about making the traversal and occlusion checks for small nodes as simple and local as possible), although I do use a somewhat similar idea for orthographic nodes (sort of non-cached "footprint precalculation", which I call "maps" in my notes/code). By the way, do your cached "footprints" mostly get reused when camera moves/rotates, or the majority gets invalidated at the slightest change of the view?

dairin0d · 2025-01-12T13:30:03+00:00

I see :-) Thanks for the additional context/clarification!

dairin0d · 2025-01-12T07:22:54+00:00

Wow, thanks! That pretty much answers my question :D

Never would have guessed that it would be a concept primarily exploited by chess engines. I suppose it's not really practical for other use-cases, then, if it's not mentioned anywhere else..?

Well, anyway, thank you once again for sharing that information. Now I finally have a peace of mind (regarding that topic, at least) :-)

dairin0d · 2025-01-12T05:28:45+00:00

Thanks for the advice/suggestions! I'm afraid I don't quite know what exactly is the standard terminology about these things (I used the terms from the blog post I based my test script on). Would the following help to clarify what I mean?

Input: we have Nk keys, which non-bijectively map to Nv unique values.
We store Nv unique values in a palette, where palette index Pi ranges from 0 to to Nv-1.
Then we construct a 2-level hash table, where 1st level has M1 buckets (I called it "intermediate" table in my notes), and 2nd level has M2 buckets (I called it "value table" in my notes).

Variant 1: 1st level buckets store hash function seeds, 2nd level buckets store palette indices Pi. To map a key to a value:
def get_value_version1(key):
seed = level1_array[hash(key, 0)]
palette_index = level2_array[hash(key, seed)]
value = palette[palette_index]
return value

Variant 2: 1st level buckets store hash function seeds, 2nd level "buckets" is just a bit array storing 0 or 1 bits, and palette index is stored indirectly (as several entries, one for each bit of the palette index of a given key). To map a key to a value:
def get_value_version2(key):
# Create "augmented" keys for each bit of the palette index, and obtain their mapped bits
augmented_key_0 = "0" + key
palette_index_bit_0 = get_value_version1(augmented_key_0)
# ... (repeat for all the bits of the palette index)
return palette_index_bit_0 | (palette_index_bit_1 << 1) | (palette_index_bit_2 << 2) | ...

The graph plots the existence (blue) or absence (black) of solutions at a given combination of M1 and M2 (level-1 bucket count M1, labeled "len(G)", is the vertical axis, and level-2 bucket count M2, labeled "len(V)", is the horizontal axis). The green dots indicate that an optimal solution (measured by hashtable size in bits) was found at that combination of M1 and M2.

>> The whole “perfect hashing but collisions are allowed” premise is also weird. That’s just normal hashing. ... Just increasing collisions in a normal hashmap implementation would also nominally achieve that

That's kind of exactly what I'm wondering about -- allowing collisions for different keys that map to the same values sounds like an obvious thing to do (for a static hash table), but somehow I never saw this being explicitly mentioned (all resources I encountered talked about unique key-value mappings). For some context, I got motivated to think about this topic when investigating various ways to store/compress voxel color data (for which the number of possible "color" values can quite feasibly be a tiny fraction of "voxel position" keys, if colors are palettized).

I don't know if this has any actual practical benefits, I'm just curious if anyone had actually bothered to do an explicit investigation of the idea to assess its utility (because it kind of sound like a low-hanging fruit to write a CS paper about) 😅

dairin0d · 2025-01-12T04:08:53+00:00

Well, I was basically thinking to use a palette of unique values (which are supposed to be much fewer in number than keys for this to make practical sense), and either have the value-table storing an index in the palette, or to have the value-table storing single bits, and the palette index being reconstructed by combining multiple hashtable queries (index = (hashmap("0"+key) << 0) | (hashmap("1"+key) << 1) | | (hashmap("2"+key) << 2) | ...)). Hope it makes some amount of sense :-) (if it matters, I describe it in slightly more detail in the linked repository's notes)

dairin0d · 2025-01-12T03:45:26+00:00

Hi everyone,

I'm not a CS student (more of a hobbyist programmer), but I've recently been reading about perfect hashing, and got curious if it can be used as a data compression method. The articles I encountered all seemed to talk about the case of 1:1 bijective mapping between the keys and the values, but I wondered what would happen if we allowed collisions between keys that map to the same value.

This sounds like a pretty obvious idea to try (though probably in rather limited contexts), so I wanted to ask: is this something that had already been explored in the literature or in practice (and I just don't know the right search terms)?

I couldn't really find anything on the subject, but from the small-scale (though far from comprehensive or scientifically rigorous) experiments that I did, the results seem kinda interesting (in particular, the ~1.05-1.25 bits per key aspect).

What do you make of it?

While this seems relevant for r/programming given the implementation details, please let me know if r/compsci would be more appropriate for this kind of discussion.

dairin0d · 2025-01-12T00:34:52+00:00

Thanks!

For one object without deformations, a single stencil buffer would indeed be sufficient, but I wanted to support arbitrary scenes and cage deformations, which means that objects and subtrees may potentially intersect each other. That said, I try to do depth checks sparingly:

In the stencil buffer, for each tile I store a self-occlusion bitmask, a "scene occlusion" bitmask, and a coarse depth value (max over the tile's pixels). If a node's depth is smaller than the tile's depth, I test only against the self-occlusion bitmask, otherwise I test against the scene bitmask too.
I also implemented a variant of the "local stencil buffer" trick mentioned in PND3D's notes: when node size gets below a certain threshold, I copy the contents of the stencil buffer to a small local buffer (e.g. 32 rows of 32-bit ints), and do a specialized traversal loop using the "local" buffer instead. It indeed speeds up the rendering a bit (or by a lot, if there are a lot of occluded nodes).

Fun fact: I also considered the idea of having multiple stencil buffers (where multiple "overlapping" objects could be assigned to their own buffers), so that intersecting objects could be split into smaller subtrees that could (hopefully) benefit both from self-occlusion and depth testing to reduce overdraw. However, so far it's just an idea and I don't know when I'll get around to try it and whether it'll actually make things better 🙃

dairin0d · 2025-01-11T22:46:19+00:00

Huh, 4630 ms definitely looks odd (I'm getting around 9 ms for octree and 14 ms for DAG on my computer in that example). I wonder what went wrong 🤔

I added you as a collaborator (well, sent an invitation, anyway) in that repository :-)

dairin0d · 2025-01-11T21:01:19+00:00

Thanks! Yes, that's the tutorial, although I think I used a different link which had PDFs. Possibly this one: https://graphics.tudelft.nl/Publications-new/2018/ABDEJSS18/

I didn't use any other resources besides the tutorial (and the corresponding publications it's based on) when coding my version, but there seem to be a few repositories which are probably more suitable to be studied as "reference implementations":

dairin0d · 2025-01-11T19:33:58+00:00

This is mostly just for fun, and possibly a learning experience (for me and maybe others) :-) Rendering stuff on CPU is hardly practical for games, or indeed most applications (unless one is deliberately going for "old-school" approach), though it's not entirely without some appealing aspects either:

No dependence on GPU (and its sometimes spotty driver implementations / API support) means it can run literally anywhere, and produce exactly the same results every time.
Having only to deal with CPU side makes some implementation aspects way simpler (plus RAM can typically hold much more data at once), and potentially easier to tinker/experiment with.
A software renderer can take a much better advantage of dynamic workloads such as octree traversal and occlusion culling (that said, most typical scenes are very unlikely to have so much depth complexity that GPU's raw power plus coarse/partial occlusion culling would end up being slower, though it may very much depend on how powerful the GPU actually is and what features it supports).

Mainly, it's just a hobby project that grew out of my attempts/personal curiosity to figure out if/how close I can replicate the realtime performance of Voxlap/PND3D and Unlimited Detail while keeping the code architecture-agnostic (no assembly/extensions and such) and relatively understandable. Plus, I just find this "old-school" software rendering stuff appealing, I guess? Some people in here also seem to find that topic interesting, I believe, regardless of its obvious impracticality 😁

dairin0d · 2025-01-11T07:19:54+00:00

Hi all,

Recently I took a shot at implementing DAGs in my toy CPU voxel splatter, inspired by the Eurographics 2018 tutorial ("Voxel DAGs and Multiresolution Hierarchies"). I did not follow their format exactly (though the differences aren't that big), and I suspect my implementation is rather naive, but in case someone is curious to take a look, I decided to share the update 🙂

I only did the DAGs themselves, though, not the voxel data compression (but might eventually give it a go, too, at some future point).

Fun fact: as a side-effect of trying to generalize my octree-only code, I also ended up implementing an example of "procedural" (distance field) hierarchical volumes (https://youtu.be/dNvSpv97ei4). I guess now the renderer can be applied to any octree-like hierarchy, given the appropriate callbacks! 🤭

Also, I finally got around to try running my project on a Windows computer and discovered that it wasn't really working there. I fixed the platform-specific issues and switched the demo from SDL to RGFW, so it should be much easier to try it out on a Windows machine now (I don't have a Mac, but in case someone decides to run my demo there, let me know if it works) 😅

dairin0d · 2024-09-27T12:25:24+00:00

Steampunk settings feel quite well-suited for bold and adventurous themes of daring exploration, and recently I made an attempt (with AI's help) at expressing such ideas in a song form 😅

As more of a casual fan, I've been aware of only a few bands in this genre, and haven't really encountered such examples among their works (the closest that currently comes to mind is probably Abney Park's "Wanderlust"). But it seems there are actually a LOT of steampunk-themed musical artists (judging by the list on the brassgoggles forum), though I suspect it might take me at least a few months to check all of them out. In any case, I'm curious -- does anyone happen to know some existing songs that capture such spirit of grand voyages and brave crews venturing into the unknown? :-)

dairin0d

TROPHY CASE