• Create Account

# Bacterius

Member Since 28 Feb 2011
Online Last Active Today, 09:54 AM

### #5087916Metaballs with Marching cubes

Posted by on 21 August 2013 - 03:50 PM

[snip]

Haha you should write one then you can help me make mine better

Anyway I have been messing about with it for a while but still cannot draw outside the 0->1 range. I found this source online

https://github.com/kamend/3D-Metaballs-with-Marching-Cubes/tree/master/src (Note its not mine) to try and see how they control range and I see it uses gridX gridY gridZ which is basically the same thing as my m_volume_depth etc...

Can anyone have a look through that source and see which bit alters range so I can draw more than a unit cube.

Thanks

Well I don't have time to look into it right now (gotta go in five minutes) but reading your original post's code again, you are normalizing your i, j, k counters so that they always fall in (-0.5 .. 0.5), and are always evaluating the metaballs there (so increasing volume_width and so on only increases resolution but not range). A quick fix is to keep the code the same, but multiply your x, y, z values by some factor like "scale". Then scale = 2 would render in (-1.. 1), scale = 4 between (-2..2) and so on. Try it and see if that works.

### #5087289Metaballs with Marching cubes

Posted by on 19 August 2013 - 07:11 AM

After changing the equation, I had to reduce the iso value quite alot to 0.008 is it normal to be that low?

The isovalue really tells you where the limit between solid regions and empty space (the "contour") is to be located. If it is too high or too low, everything will be considered solid or empty, and as you vary it more (or less) of the density field is considered solid, which leads to interesting results. I don't think there is really any "good" value for an isovalue, it depends a lot on your metaball implementation and on the effect you want to achieve, so I wouldn't be worried if you need to tweak it a bit to get good-looking metaballs.

Also I can only specify metaball positions between 0 -> 1 anything outside doesn't get drawn and I want to be able to draw them anywhere on screen, Im not sure which part of the algorithm decides the range?

This shouldn't be a problem with the metaball algorithm itself. I would check your marching cubes code to verify it is working outside the 0..1 unit cube. If it isn't, then obviously everything outside it will never be polygonized, and therefore never rendered. It's not possible to polygonize things arbitrarily far away, unfortunately, there is always a tradeoff between range and resolution, because marching cubes is a discrete algorithm. Other methods like ray marching can sort of scale to arbitrary distances, but have their own set of drawbacks.

To make sure your balls can move around, you can compute the bounding box of your metaballs and use that to define the range for the marching cubes algorithm, but you can't have them go too far away from one another else you will lose in accuracy. You might wonder why, since in that case the marching cubes algorithm would spend most of its time on empty voxels, and, yes, it is possible to do better, but it gets rather nasty as you then need to find an approximate bounding box for every set of connected metaballs and run the marching cubes algorithm on each of them, separately, which sounds great on paper but isn't that efficient in practice. I think most people deal with this by making reasonable tradeoffs between the size of their worlds and how precise the polygonization should be.

Finally just a general question, eventually I wanted to use this to render fluid. Some people seem to use marching cubes to render fluid, however It took my app like 4seconds just to render those four static metaballs. What kind of technique is good for fluid rendering?

Marching cubes can be rather expensive, especially if you want really good resolution. Looking at your screenshot, your mesh is quite smooth, meaning it's probably trying to polygonize up to 128x128x128 voxels, which is *a lot* especially done on the CPU. If you wanted to go interactive - it is possible - you would move the marching cubes code to the GPU, in a shader, and perhaps scale back the resolution a notch. It isn't too hard at all, in fact, and the speed boost is huge since doing the same calculation over a lot of different locations is what the graphics card does best. Then you can add lots of algorithmic optimizations to avoid calculating every single sphere's potential for each voxel - which obviously won't do when you start rendering dozens of metaballs - by using techniques like octrees or spatial hashing. It can get rather efficient, really, but it has its limits. As we all know, the really cool stuff is done by cleverly combining different techniques

I don't know if metaballs would be my first choice for fluid rendering, though. It stills seems like an inefficient method overall, I would just use a grid-based fluid dynamics system if I wanted to do it properly (though a fractal heightmap or even FFT water works well for static water bodies). Marching cubes itself sounds good to display the results, however. Remember to dissociate what you are rendering (metaballs) from how you are rendering it (marching cubes), the two have nothing in common except being often used together.

... great, now I want to write a metaball renderer

### #5087199pong game and opengl

Posted by on 18 August 2013 - 10:49 PM

pongzip.zipwell I tried  this on my laptop and it works except that you have to extract it to a regular folder and I cant get the sound to work also.

Works! No sound, it seems to be that the audio library you're using doesn't seem to support wave files with format other than PCM. If I substitute the .wav file with a PCM-encoded audio file, it works fine. Perhaps you can reencode your file to PCM and it should work then (did the sound work on your development machine?)

Some feedback:

- the paddle isn't very responsive, to move it quickly we either have to bash the up/down keys (which is slow) or keep them pressed (which has a delay before you start moving). I know this comes from how keystrokes are handled in Windows, because I assume you are relying on the KeyUp/KeyDown events. To make this better, you can try not using the events but instead, in your game loop, checking the keyboard state to see if the up/down arrow keys are pressed or not, and react accordingly.

- there is something wrong with the collision detection at the edge of the paddles, the ball will start spasming inside the paddle instead of bouncing back at an angle, eventually coming back out the same way it entered. We'd have to see the code to diagnose this one.

- the AI is unbeatable.

- after some period of time, everything gets slower (not sure if this intended, but it does make the game easier).

Other than that it looks pretty good! Are you going to share the source code as well?

### #5087185Metaballs with Marching cubes

Posted by on 18 August 2013 - 09:44 PM

Unless I've misunderstood your code, there's something wrong with your potential function. It should go to zero as you go further away from the sphere's center, and reach zero at some distance, not be negative inside the sphere and then tend to infinity, otherwise it will be really hard for a sphere to interact with the potential field of another (since the "most negative" value is negative radius squared, whereas far away from the first sphere your potential becomes arbitrarily large).

The basic "metaball" potential function is 1 / (distance to center squared). There are faster/smoother approximations out there, check out http://en.wikipedia.org/wiki/Metaball.

Posted by on 18 August 2013 - 09:33 AM

As to 'go figure' I do not know how to find that, many project sizes are probably  avaliable in google - could somebody help with finding that?, I would appreciate

You can find source code for some of the old games from ID Software (aka Doom, Quake, etc..) on github and probably other places. Just google it, you'll find it

I am not sure how you can give such accurate estimates on how many lines of code you've written in your whole life (unless you started relatively recently and kept all your code so far), personally I've been coding for almost a decade and have probably written hundreds of thousands of lines of code, though most of it is boilerplate, straightforward, etc.. (a lot of your code is, really, if you go strictly on a per-line basis, as you said most of the work is in the reasoning and logic involved, not so much in the code itself). I would guess what most developers would consider their finest code probably doesn't span that many lines.

But lines of code is hardly a useful metric. Yes, more features = more lines of code on average, but it's not a straightforward relationship like saying "big 3D game = 2 million lines of code, 2D indie tetris = 3k lines of code, hello world = 5 lines of code". It depends on a lot of stuff, and I am not really sure it is helpful to compare your codebase to another purely on the basis of number of lines of code. In fact it's probably detrimental on some level.

For what it's worth, my current project (not a game) has around 7000 lines of code all around, and I do consider it a medium project, not because of the number of lines of code but because the concepts that I need to integrate into that code are far from trivial. If you start measuring project size by applying hard limits like "above 100k is a medium project, period" then you're in for a surprise, because I am sure some really, really fun and complex games have been made in far less than that. More isn't always better.

Lines of code quite simply isn't a useful metric, really. If you really need to attach some number to every codebase I would suggest using man-hours spent which is already a much more concrete metric for measuring, roughly, how "complex" something is, in relation to the amount of time a bunch of programmers have been working on it. Because I too can also write horribly bad tetris code unrolling every possible game state and spanning millions of lines - if not more - but that won't make my tetris game any better than a clever implementation fitting in 500 lines of code.

### #5085975What on earth is wrong with this really basic rotation?

Posted by on 14 August 2013 - 07:07 PM

How exactly are you using the world matrix in your shader? It may be you're doing it wrong there and this more complex transformation has revealed a bug.

Also, are you sure your centerPosition field is correct, have you checked it?

### #5085022Oh my glorious code!

Posted by on 11 August 2013 - 02:59 PM

I think he meant he just wanted to add colors to the terminal as-is and nothing else. Honestly though, if one starts adding things like that one may as well end up just taking over the entire console, which is what ncurses does, pretty much.

Not necessarily. What I meant was doing some minimal coloring of whatever you're outputting, without taking over the entire console, where simply wrapping up a string constant in an ANSI escape sequence is much easier than working with ncurses when the extra flexibility (menu helpers, borders, and so on) are not needed. Different solutions to different problems, really. ncurses is a nifty little library, and is great for making roguelikes and other games which lend themselves well to a 2D ASCII representation, as well as creating complete console interfaces, but that doesn't mean you need to use it every time you need to push a few colors to a terminal... sometimes a script is just a script

### #5084085Anyone know the probability density function for this?

Posted by on 08 August 2013 - 04:37 AM

Well, let's take the leftmost piece of string. It doesn't really matter where we look since the cuts have a uniform distribution. Let's try to work out the probability that this piece of string has length $$l$$ or less. Clearly this is easy - all we need is that no cuts be done at a distance from the left endpoint of the string less than $$l$$. So the probability that the piece of string has length $$l$$ or less is just $$1 - (1 - l)^n$$ where $$n$$ is the number of cuts. This is, of course, valid for $$0 \leq l \leq 1$$ only, since the probability that a cut falls outside that interval is $$0$$; the density of the random variable is also $$0$$ outside it.

In other words, $$\text{Pr}[0 \leq L \leq l] = 1 - (1 - l)^n$$, where $$L$$ is our random variable. Let's also recall that because the cuts are made with a uniform distribution, the "order" of the string doesn't matter as long as you stay within the unit interval (you can also use a symmetry argument - the uniform distribution is symmetric about the unit interval, and therefore so are the cuts) and we can conclude that:

$\displaystyle \text{Pr}[0 \leq L \leq l] = 1 - (1 - l)^n ~ ~ ~ \text{for} ~ ~ 0 \leq l \leq 1$

This is the cumulative distribution function of the length of a piece of string. To get the probability density function of this random variable, differentiate:

$\displaystyle f_L(l) = \frac{\text{d}}{\text{d} l} \left [ 1 - (1 - l)^n \right ] = n (1 - l)^{n - 1}$

Let's verify this quickly by ensuring the mean value is as expected. Consider $$n$$ cuts. Then the mean length is going to be:

$\displaystyle E[L] = \int_{-\infty}^{+\infty} l \cdot f_L (l) ~ \text{d} l = \int_{0}^{1} l \cdot n (1 - l)^{n - 1} ~ \text{d} l = \frac{1}{n + 1}$

As expected. For instance, with a single cut, you end up with a mean length of one half. For two cuts, one third, and so on.

To answer the question, then, the probability density function of the length of one piece of the string cut $$n$$ times is:

$\displaystyle f_L(l) = \begin{cases}n (1 - l)^{n - 1} ~ ~ ~ &\text{if} ~ ~ 0 \leq l \leq 1 \\ 0 ~ ~ ~ &\text{otherwise}\end{cases}$

Take as an example the case of three cuts, and the theoretically determined PDF looks like this:

And the same PDF experimentally determined by programmatically cutting a piece of string three times (here's hoping I didn't screw up my implementation) with 500 bins and 5 million samples:

So, yeah, here you go  don't know if this family of PDF's has a name, though.

Just to make sure this is what you meant, my implementation of the "string-cutting routine" was:

Select N uniform integers in [0..1)
Sort them into a real array named "cut"
Calculate the length of each piece of string:
cut[0] - 0
cut[1] - cut[0]
cut[2] - cut[1]
...
1 - cut[N - 1] 

Resulting in N + 1 lengths.

### #5083870No clue what to call this, any help welcomed

Posted by on 07 August 2013 - 08:18 AM

Well, I spoke with him ( earthmark ) and another coder that just happens to be my roomate ( 015r ) and they kept discussing a few different points. Without going into crazy detail and boring all of you, the problem is that octree's are rather large. When a player modifies a block the node that the octree is associated with has to be sent. If our estimates are correct this is close to 44kb being sent just for the octree alone.

One aspect of octrees is that they don't change too much if you delete a single block inside them. You should be able to just send the difference between the old and new octree (probably just a leaf is gone, perhaps one node that becomes a leaf, or perhaps two nodes are changed, and so on with lower and lower probability). If all else fails, just diff the octrees as a starting point (by constructing a new octree which has nodes if and only if the old one and the new one are different at that node) and send that over for the client to reconstruct using his old octree.

The octree lends itself well to your geometry as well, and to your gameplay since you're only removing blocks a few at a time and that change is localized (i.e. you're not deleting random blocks from all over the map) which should make this rather efficient.

If you're already doing that, well, 44kb sounds a little excessive for a single block..

Another option is to not send octrees at all but only changes in blocks (deletion, addition, etc..) and let the client figure it out, which may be easier to implement. But I guess it depends on how your octree and netcode are set up.

### #5083459Program Stacks and Uninitialized function data

Posted by on 06 August 2013 - 12:30 AM

Once an executable is linked, will the value of 5 -- even it is referred to multiple times -- be associated with a single position within the executable?

Not necessarily. It can be duplicated, referenced, or even encoded inside the load/store instruction (on some CPU's), it's all up to the architecture. Remember that C doesn't really mandate anything with respect to the final machine code that ends up being generated. All that matters is that there exists some mapping between the machine architecture and the concepts used by the C language (a "stack", a "heap", a "program data section", and so on).

The fact that you've declared "int bob" does not really map to any well-defined equivalent in the executable code generated. Depending on your compiler, processor, operating system, all sorts of stuff, it might do absolutely nothing, increase register pressure, force the compiler to allocate 4 more bytes from the stack for this function (leading to a push/pop instruction pair or similar) or it might cause the executable to grow 200 terabytes in size if you're working on a futuristic computer where memory is near infinite.

It's really hard to predict what happens to the program when you do such and such change in the source code. Compilers are extremely clever these days. The best way to really know what's going on would be to get your compiler to output readable assembly code instead of translating it directly to executable machine code. If you're using gcc, the -S flag will do that for you.

### #5083200Relying on #includes from headers

Posted by on 05 August 2013 - 06:45 AM

My own convention is to #include in the header if and only if the header requires it (e.g. the header needs stdlib.h for a size_t parameter) and in the source file otherwise, but never in both. The source file need not be self-contained, because it will always include its respective header. So, in a sense, it becomes self-contained once preprocessed.

(I was thinking more of C when I typed this reply but I would do the same thing for C++ code)

### #5083197My OLD Syntax

Posted by on 05 August 2013 - 06:14 AM

Who needs vertical space?

k\
e\
y\
b\
o\
a\
r\
d\
_\
c\
h\
e\
c\
k\
(\
v\
k\
_\
l\
e\
f\
t\
)\

/* ... */


As a bonus, all curly brace, whitespace, and indentation arguments are solved.

PS: the alternative is using absolutely no newlines, which in my opinion is less readable and doesn't take advantage of large monitors as well as this variant.

### #5082657Understanting Gravitational Force

Posted by on 02 August 2013 - 08:52 PM

out of operators priority, it should be F=G((M*m)/d^2)

The brackets are redundant here. By operator precedence F = G * M * m / d^2 is perfectly correct.

### #5082486Why XML is all the rage now?

Posted by on 02 August 2013 - 08:19 AM

My quad-core i7 should be able to launch Microsoft Word faster than a 386 in the mid-90's. And yet... it takes 10x longer.

How much of that is due to picking inferior approaches just "because"?

Honestly that's because most programmers are just lazy and would rather commit code as soon as the unit test bar turns green and receive their "most productive employee of the month" award than read over their code and spend some time reviewing it to see what could be made better. Back a few decades software was optimized because it had to be. Now that computers are a lot faster, this problem doesn't exist any longer, so anything that works is "good enough". And if someone complains that it's unusably slow even though it does essentially the same thing it did ten years ago, no problem, just argue that it "actually does a lot more behind the hood" or "it will be faster in 18 months" or "it's the operating system's fault" or the good old "if you're not happy with the product then don't use it". Another popular one these days, especially with games, is "it's an alpha", as if that somehow excused everything.

Usability (for end users) is ultimately a measure of work done over time taken. Notice that doesn't include development time. The end user doesn't give a crap about how you whipped up that program in twenty minutes, he only cares that it gets the job done quickly enough. By sacrificing usability for development time, you are not doing your user a favor. And the instant the user's priorities take a back seat is the instant you have failed. Your job is to write software for other people to use, not to pump out lines of code as quickly as possible. Don't lose sight of what actually matters.

The current trend towards mediocrity and complacency is rather depressing. This "fast-paced" world sucks. Whatever happened to craftsmanship. Anyway, rant over.

### #5082326My OLD Syntax

Posted by on 01 August 2013 - 04:22 PM

Curly brace arguments. Keeping programmers busy since 1969.

Besides, the only correct brace style is the one I use.

PARTNERS