"In doing that they usually jump to the most uncharitable, horrible reasons they can imagine for why we might have done so."
So you do understand why one wouldn't want to deal with a significant part of the user base here given that they behave in such ways, and thus why one might want to avoid any traffic coming from here, but feel that it's not your job to deal with those users, because then their behavior would affect you? I really hope you'll reflect on that...
I haven't expressed myself clearly enough if that's a possible response to what I tried to say there.
Unfortunately I'm at a workshop today and not free to take the hours I normally would to go over the explanation until it's clearly understandable. I only have a few minutes of break time. Perhaps it would have been better not to try in the first place, under such circumstnaces; but I'm not going to delete my GP comment now.
I've read it a couple times and it's hard for me to disagree with them. It sounds an awful lot like you're saying 'if we ban the domain, people will yell at me and get mad,' with the implication of 'and I would rather they yell and get mad at someone else.'
Those are interesting questions! For example generating and looking at all networks of optimal size which have distinct circuits (assuming unlabeled inputs, so that rearranging those doesn't count as distinct) is something I still want to do at some point. Extending my search to produce this wouldn't be too complicated... but I haven't found the time for this so far.
Codish et al. have a background in SAT solving, which is somewhat related to logic programming. In SAT solving subsumption of clauses usually doesn't involve any substitutions. That's the notion of subsumption I was familiar with before reading Codish et al. Given that, extending subsumption to handle the symmetries inherent in the problem felt like a natural extension as it maintains all the relevant properties, but I also wouldn't be surprised if this was inspired by ILP.
>> In SAT solving subsumption of clauses usually doesn't involve any substitutions.
I guess not, because SAT is propositional so just substituting variables for terms would yield a ground propositional clause. Actually I wasn't even sure we say "clause" in propositional logic. Anyway Plotkin's subsumption is really based off Robinson's unification algorithm and it makes a lot more sense in that context and in the context of resolution theorem proving. Or I'm just hopelessly stuck forever thinking in the first order.
Do you know if Codish et al. were based on an earlier paper for their definition of subsumption? It really sounds like they are simply describing it, rather than introducing it as a new concept.
Edit: of course, the obvious question in my mind now is whether it would be possible to learn sorting networks using one of the ILP approaches that build on Plotkin's work and don't have to perform an expensive search of a large hypothesis space.
The paper where they introduce subsumption is "Michael Codish, Luís Cruz-Filipe, Michael Frank, and Peter Schneider-Kamp. 2016. Sorting nine inputs requires twenty-five comparisons. Journal of Computer and System Sciences 82, 3 (May 2016), 551–563." and I just realized that I lost the actual citation while editing my blog post, fixed that now.
Computing s(11) and s(12) together took just below 5 hours on a 24 core server, but it also required almost 200 GB of RAM. Verifying the computation took about 3 days in total on the same server.
Computing s(9) and s(10) with the same approach takes under a second and a few megabytes, so while this is much faster than the previous approach (the one I described in the blog post) it still grows very quickly.
I don't know exactly how much s(13) would take, but extrapolating from the number I have for smaller n, my estimate is that it would take over 20000 TB of RAM and take proportionally longer. Distributing the computation would also slow it down a lot as all cores are doing frequent random accesses to all the used memory.
So s(12) seems to be the end of what's possible with this exact approach, but I think some of the theory I developed might be usable beyond.
I haven't read everything, but it does contain a section about something I'm quite familiar with:
The article says "We compute the hashcode of the entire graph by hashing the multiset of WL labels. With one round, we’re just comparing the degree histogram. The more rounds we add, the more likely we are to detect a symmetry-breaker:", which is not correct.
Repeatedly re-labeling a graph by assigning a unique label to each unique neighborhood histogram, until the corresponding partition reaches a fixpoint would compute the one-dimensional Weisfeiler-Lehman refinement. But there are many non-isomorphic graphs that you cannot tell apart with this! It cannot tell apart any two regular graphs of the same size and degree, and you can easily run into those in practice.
Even if the code would repeat this process until a fixpoint is reached, instead of hoping that 10 iterations suffice, non-isomorphic graphs that result in the same WL partition means that "The more rounds we add, the more likely we are to detect a symmetry-breaker" doesn't hold.
There are also more efficient ways of computing this.
Now apart from one-dimensional WL refinement, where you compute a label from the neighborhood of individual vertices, there is also k-dimensional WL refinement, which very roughly speaking looks at all length k sequences of vertices and computes statistics for those. Here it is true that as k reaches |V| you will be able to tell apart any two non-isomorphic graphs, but only because if k=|V| you're trying all permutations! There is no fixed k that will tell apart any two graphs.
It combines two-dimensional WL refinement with a recursive search to tell apart all graphs, while using computational group theory algorithms to efficiently prune the search space for graphs with many symmetries. It is very efficient in practice.
It is described in https://arxiv.org/abs/0804.4881 (also linked from the website) and also has references for everything I wrote (modulo any mistakes I made while summarizing).
Thanks for your feedback! I like the WL algorithm for its simplicity, but agree there are specific cases it does not handle well. It is meant to illustrate a simple message passing algorithm, and is not a particularly efficient implementation. Will clarify this point, thanks!
That's just defining the term. AFAICT the law only says that an employee has a right to receive fair compensation for a technical improvement in some cases. It explicitly says that apart from that, procedures covering technical improvements are a matter of contracts: https://www.gesetze-im-internet.de/arbnerfg/__20.html
Thanks for writing this. I didn't really expect that much attention, so I kind of assumed most people reading it are at least somewhat familiar with the graphics hardware of that area. I shouldn't have assumed that :)
Not a question. But I just wanted to say that this sort of thing is amazing to me.
I literally:
1. Saw this article headline about a polygon rendering engine on the Mega Drive
2. Thought, oh this is going to be good
3. Made some tea
4. Settled in to enjoy it.
Not only did I love the demo and your article, you cleared up a longstanding mystery to me. I know that Another World (aka Out of This World) and Flashback (intro only) used similar techniques to render "canned" or "pre-baked" polygon animations on the Mega Drive, but I knew literally nothing about how that was possible. Thanks to you, now I have some kind of idea. Were you inspired by those games, to pull off this awesome effect in your demo? (BTW, you achieved a much better frame rate AND did it without borders... totally badass)
Last but not least, thank you for the inspiration. I'm not a graphics programmer but I am a programmer and I have always been inspired by demos ever since the days of Future Crew. Coders like you inspire coders like me to better ourselves and be unafraid of challenges.
I had a couple of games on Mega Drive that did basic 3D, or seemed to. One was F1, where a few objects seemed to be true 3D. See the overbridge at 59s and then the long tunnel at 1:01 here for instance:
https://youtu.be/qofonsN3Nwc?t=57
The long tunnel is made of several short tunnels.
I don't know about the F1 game but I can take a guess on Gunstar Heroes.
I noticed the cubes are always aligned perfectly to the axis. And they have an isomorphic projection so the cube is always the same height (although that shouldn't be strictly necessary) as it's rotating. I also noticed the cubes never seem to get smaller if they are closer to the background.
Because of this you could just have a series of sprites each showing the cube in a different angle of rotation.
Now all you need to do is properly position a bunch of sprite (16 cubes + head) and it looks like a bunch of cubes that are actually drawn in 3-D. It wouldn't surprise me if they have some small table of the X/Y positions of the cubes precomputed so they don't have to do that in real time.
In fact since every cube is always rotated at the same angle you could just have one sprite in the system table and update it every frame.
That's my guess anyway. Clever sprite trickery.
It wouldn't surprise me if F1 uses something closer to what is described in the article (although much less capable).
Your analysis appears correct, as several sources write that Gunstar Heroes uses multi-sprite bosses [1][2].
F1 on the Mega Drive owes its existence to an earlier game for the Atari ST, Vroom [5]. The brainchild behind that game, "Dan McRae", talks in a video interview [3] about how he arrived at that particular version of the game from his earlier revisions on older platforms -- where techniques shown in Lou's Pseudo 3d Page [4] apply, to more advanced techniques [6] similar to the ones presented in this submission.
F1 on the Mega Drive was done by the same dev studio that collaborated with McRae on Vroom, and at least one of the same programmers, but presumably had to do some advanced tilemap trickery specific to the console. Unfortunately, compared to other games in this series, there is very little information on the technical aspects of the Mega Drive version.
I've never had a Mega Drive before working on this, so I wasn't really familiar with a lot of its games.
I took a quick look at F1 just now though. The way it makes use of the nametable and patterns is very similar to what I do. There are precomputed fully solid patterns at a fixed location and the non-solid patterns seem to be bump allocated.
It makes use of both layers though, drawing the street on one and everything else on the other. I think it uses per scanline scrolling to apply correct perspective to the street.
I can't say anything about how it actually renders into the tile map for now. That would require a lot more than looking at the VDP (graphics chip) debugger in an emulator.
Thanks so much for taking the time to check it out. I've had that game for >20 years now so it's nice to learn a little bit more about it. Cool that they were doing something similar 24 years ago.
The Gunstar Heroes boss reminds me of an old demo effect called vectorballs or "bobs" https://youtu.be/Itv3f7o7Zac?t=167 combined with a Doom-style pre-rendered set of rotated sprites.
Were there any alternatives/dead ends you went through to arrive at this technique, or any extensions you wanted to do but didn't find the time? Really amazing work BTW, this might be my favorite demo ever!
There weren't really any dead ends. Mostly because I started with a very simple naive way to draw polygons and improved it incrementally. I didn't implement all those steps, but convinced myself that they would work.
I started with a generic plot-individual-pixels-into-tilemap routine. Going by tile-rows and columns with special casing solid tiles came next. That required "convexity" in x direction but at that point I was only thinking of triangles. Then I noticed that avoiding overdraw and working with a tesselation of the screen is probably faster. A that point I also extended it from triangles to polygons. While fleshing out the details of everything I noticed that I don't have to be exact for right-side edges if I draw the polygons in the right order.
There actually was an extension I did, that was scrapped because it just didn't look good. At some point there was support for dithering. That helps with the low color precision of the Mega Drive (3-bit/channel). It only supported 50% checkerboard dither though, which looked odd when animated. I toyed with some ideas on how to improve upon that and discussed them within our demo group, but in the end the decision was to not use dithering.
For the Mega Drive/Genesis the framerate depends on the region, matching the local video standard. The European Mega Drive uses PAL with 50Hz.
As the biggest part (but not all) of the demoscene is based in Europe, most demos target PAL hardware. The same is true for our demo group. NTSC ports can be very difficult if not impossible as PAL often does have a slight advantage in CPU cycles per frame. This is also the case on the Mega Drive.
Porting the polygon renderer shouldn't be a problem as it renders in an off-screen CPU RAM buffer. In the worst case it would have to skip more frames, having a lower effective framerate.
A lot of the other effects have very critical timing though. I've been told that porting some of them to NTSC is just impossible.
There is a little more CPU time, but the extended vertical blanking interval means there is a huge difference in video memory bandwidth, which is critical for a long DMA transfer from 68000-bus memory to VRAM through the Mega Drive's VDP.
60Hz V-blank DMA: 7524
50Hz V-blank DMA: 17622
That's at 320x224 resolution for both. I don't know how much this affects this one demo in particular, but for other things it can be a little annoying sometimes to be bandwidth-starved.
For this project I don't really have to say much about the rust side of it. There were no surprises. The only thing special I can think of is the excellent cross-compiling support. That came in handy as I had to produce windows binaries for the 3D artists.
No. Apart from the mapper chip used to address 8MB of ROM this demo requires no additional chips on the cartridge. Everything is done by the 68k CPU (running the effects) and the z80 CPU (running the sound engine).
Not all everdrive flash carts support the mapper/rom size our demo uses (the SSF2 mapper with an 8MB rom). The included nfo file lists some supported flash carts.
I didn't know that. Thanks for info. I had set up a sweet broadcast CRT and Mega Drive with RGB, along with a 50/60Hz switch on it. Looking forward to enjoying demo on real hardware. I'm looking into Mega EverDrive X7.
So you do understand why one wouldn't want to deal with a significant part of the user base here given that they behave in such ways, and thus why one might want to avoid any traffic coming from here, but feel that it's not your job to deal with those users, because then their behavior would affect you? I really hope you'll reflect on that...