• Create Account

# Bacterius

Member Since 28 Feb 2011
Online Last Active Today, 01:59 PM

### #5118117Ray tracer : fill an uniform grid

Posted by on Yesterday, 08:01 AM

For the first solution is there an algorithm to speed up?

You could start with all the triangles in your scene and remove a triangle when you've fully explored all the cells that might contain it, then you have less and less triangles to process as you work through the algorithm. I would personally start by walking the grid along the triangle's edges, and then exploring the cells "in between". Your code might end up looking somewhat like a 3D "scanline" (or, more appropriately, scanplane) algorithm.

A more efficient method could be to partition your triangles into an octree (this might require your grid to be a power of two). Once you've done that it's a simple matter of looking up each triangle at the right depth (depending on your grid's resolution) and binning it inside the corresponding cells. It might be possible to do it all in one step by building the grid at the same time you build the octree, but I can't think of a way right now. This seems to handle enormous triangles which overlap lots of cells much better than the first approach.

There's probably a better way to do it, but that could be a starting point. I'd go with a divide and conquer approach anyway, anything else is likely to not scale well with the number of triangles.

### #5117789Are GPU constants really constants?

Posted by on 18 December 2013 - 03:58 AM

I heard some GPU's simply reserve a section of global memory for constant buffers which is then pushed into the (small) hardware cache so that shaders can access them very quickly. So they are not technically read-only (e.g. they could plausibly get written to through a driver bug) but doing so would violate assumptions made by the driver, shader, and application, so the runtime tries very hard to ensure shaders cannot write to these constants.

I'm not sure if that is how it happens anymore, but in any case, this is all abstracted from you by the hardware layer and the graphics API, so you should avoid relying on assumptions about the underlying hardware implementation if you want to ensure your code runs the same everywhere.

### #5117484Programs going way too slow since moving to a new computer...

Posted by on 16 December 2013 - 09:02 PM

d3d11ref.dll is the reference device implementation for the D3D11 runtime. No wonder it's running so slow, you're rendering in software (with the reference driver, no less).

### #5117041[solved] Calling recv() in a loop

Posted by on 15 December 2013 - 01:27 AM

But it doesn't say which. And since I've been having networking-related bugs, I want to make sure that I'm not accidentally dropping data while not being susceptible to buffer overflow bugs/exploits. Blocking isn't too much of an issue; the program is supposed to be a daemon anyways. The program is connecting to game server instances, which may stream small or large amounts of data, and connecting to admin tools, which stream short commands. However, there is no set packet size, so I want to know if I can play it safe by reading from a socket into a growing list of buffers until it is dry.

TCP (SOCK_STREAM) never drops data from the internal buffer, and will only give you what you request, leaving the rest available for subsequent calls to recv (I think internally it asks the remote host to send the data again if it can't keep up). So in that case you don't need to worry about losing bytes. What you do need to worry about is your stream getting fragmented, so you need to maintain some state during the connection, e.g. "ok so I've received 50 bytes of this 100-byte string, I still need 50 bytes..", because simply checking recv()'s return value as an indicator that a send() call on the remote host has been received is unreliable - TCP is stream-oriented, so it's possible that a remote host sends "hello" and then "test", and you, in your recv() loop, receive first "he", then "l", then "lote" and finally "st" (*this is a simplification, in reality this exact scenario does not really happen because packets have a minimum size before being fragmented, but it occurs all the time for longer streams). You cannot use recv()'s return value as an indicator that all data has made it to you, unless the remote host immediately closes afterwards (and even then I am not sure - someone will have to confirm this but I believe it's possible for the socket to close while data is still in transit to you, so you need some synchronization).

On the other hand UDP (SOCK_DGRAM) gives you no guarantees. The packet may have been discarded anywhere between source and destination, and that includes your system's internal buffer if it happens to run out of space. That's part of the deal, and it is a reality you will have to accept if you do UDP networking.

### #5115775Creating an Open World game

Posted by on 09 December 2013 - 07:01 PM

Nathan2222: people are referring to http://www.gamedev.net/blogs, you can create your own blog right here on gamedev.net and keep everyone up to date on your progress. I think that's what they meant~

### #5114546handy inline assembly environment

Posted by on 05 December 2013 - 05:12 AM

Inline assembly is typically messy and doesn't look at all like ordinary assembly because you need to get the compiler to understand your assembly code so it can allocate registers properly and not screw up your own assembly. Do you really need inline assembly, would a separate assembly file with external declarations do the trick? You don't need to mess with the compiler, and you get all the instructions you want (as long as the compiler is configured to understand them).

It looks like this:

// main.c

void my_function(int arg1, char *arg2, void *arg3); // specify calling convention if needed

int main()
{
my_function(...); // call your assembly function
}

// assembly.S

my_function:
// freely write your assembly code here
// (assuming arg1, arg2, arg3 are in the proper register
// or stack location depending on the calling convention chosen)


Then you just compile assembly.S as an ordinary C file, and link it along with the rest of your source files, and the linker will link the "my_function" declaration with the assembly function.

If this is not good enough, then, sorry, I don't know (and ignore this post).

### #5114175Square not showing

Posted by on 03 December 2013 - 05:11 PM

Your index buffer setup code is wrong. You start to set up the index buffer description, then you seemingly change your mind and make it a vertex buffer instead. Then you try and bind that as an index buffer, which obviously fails. Look at the beginning of the DrawTriangle() function.

PS: for debugging I recommend using the debug layer by enabling it in your DirectX control panel, creating a debug device in your code, and then using DebugView or the like to get the debug output. You would have gotten something descriptive like "cannot bind a buffer with D3D11_BIND_VERTEX_BUFFER as an index buffer". Trying to debug D3D errors without the debug layer is tedious at best, voodoo at worst.

### #5113158Histogram: logarithmic binning in O(1)?

Posted by on 29 November 2013 - 08:05 PM

$\text{bin}(x) = \left \lfloor \log_{10}\left ({\frac{x}{x_\text{min}}} \right ) \right \rfloor$

In your case, $$x_\text{min} = 0.1$$ and the bin numbering starts at zero. You can derive this by starting the histogram at the 1..10 bin and accounting for the smaller bins afterwards.

### #5112402PinWheel Encryption

Posted by on 27 November 2013 - 04:06 AM

If the program knows the password is incorrect before decrypting and decompressing the data, then it means the hashed password is easily accessible - perhaps in the file header? Shouldn't the data be decrypted and decompressed regardless if the password is correct or not, the only difference being an incorrect password will produce a huge pile of garbage? Can someone explain this?

Sure, the hashed password is available. But you can't use it for decryption. Basically it goes like this:



+----------------------------------------------+              +-------------------------------+
|                                              | ONE WAY ONLY |                               |
| Plain password (typed by the user)           | +----------> | Encryption key                |
|                                              |              |                               |
+----------------------------------------------+              +-------------------------------+
+
|
| ONE WAY ONLY
|
|
v
+----------------------------------------------+
|                                              |
| Hashed password (useful only for comparison) |
|                                              |
+----------------------------------------------+


The two are unrelated and you can't deduce one from the other. So the hashed password is used to find out if you typed the right password, and then when you did, the program can calculate the encryption key and decrypt the program. That way it can warn you if you typed the wrong password without decrypting garbage, without any security issues. So technically the hashed password isn't "needed", it's a quality of life thing to guarantee that you don't end up decrypting garbage, and also lets you check the key *without* decrypting anything (which is relevant in some cases).

You can also do more advanced stuff with this such as making sure the file was not compromised (modified surreptitiously) etc.. basically it's a useful technique, and does not indicate a security flaw

### #5112371Mystery of the Game Loop: How high can the 'n' in Big O can go?

Posted by on 27 November 2013 - 01:05 AM

As you can see, the level of nested loops reached 4, therefore, my game is running at O(n4).

No it doesn't. "n" might not be the same in every loop (and in general it isn't). For instance in your game loop, the first two "while"'s are basically based on the elapsed time. Do they count as complexity? Of course not, the only thing that matters is what gets done every frame (and whether it meets your frametime requirements). Big-O doesn't mean "there are four nested loops, complexity is O(n^4)", you haven't understood what big-O represents.

Besides, talking about the big-O complexity of a game loop is not particularly insightful, there is so much stuff going on that it doesn't "mean" anything for a game loop to have any given complexity (big-O is hardly appropriate as a game loop is concrete, you're not measuring its asymptotic performance as some quantity tends to infinity, but its true performance). It's much better to isolate smaller parts of your code (for instance, the pathfinding) and then say that, for instance, for n units the pathfinding algorithm takes O(n^2) time to do whatever it needs to do. Then you can detect problematic areas of your code and improve them. For instance here you could improve the pathfinding code to not have to iterate over every unit, by using an appropriate data structure for nearest unit searching.

### #5112295PinWheel Encryption

Posted by on 26 November 2013 - 07:02 PM

For those of us under Linux, this is how you build:

1. remove Windows.h includes

2. replace "intrin.h" with "emmintrin.h"

3. Fix the alignment stuff by changing it to __attribute__((align)) and moving them after the "struct" definition, i.e:

#define ALIGN( n ) __attribute__((align(n)))

struct Block16
{
// ...
} ALIGN(16); // <-- here


I encrypted the all-zeroes file and unfortunately the algorithm only produced 0xFF's and 0x00's in regular patterns. Your algorithm is certainly fast but that is enough to show that it is no good at all as an encryption algorithm, as it does not meet the security properties of one. Don't take it badly though, one famous cryptographer said once that "it is easy to create a cipher that you yourself cannot break". Also, just to make sure: it's really fun to design ciphers, but please never use them for real stuff outside the lab. It's not worth it.

Of course there will be patterns, this is a worse case scenario test. The data in that image is LARGELY repetitive, in fact each row of 256 pixels, the width of the image, is usually close to identical to the row above it. Encrypting blocks that only have a 1 byte difference between one and another will unfortunately yield somewhat similar results. This effect is compounded by the fact that the change between rows is fairly regular. If I reduce the size of the image to 246 x 246 pixels and then encrypt with an 8 char password, we get this:

That's not good enough, sadly. For any input, the output should look completely like random noise, and for no two different inputs should the outputs be correlated (over any possible key). A strong encryption algorithm uses the principles of diffusion and confusion to destroy all structure in the input (while still making it possible to reverse with the right key). Take a look at SPN's (substitution permutation networks) to see how this can be achieved effectively, you could borrow some of this.

### #5112130Perspective projection: Intersection length between light and view

Posted by on 26 November 2013 - 07:14 AM

The ds * rs part is the inverse square law. Here you are only considering the width and not the whole area, so it increases linearly with distance as you would expect (if you stare at an object through a camera at a distance D and see it records a length of X pixels, then walk back to a distance 2D, its length will have decreased to X/2 pixels).

The cosine division part is basically the cosine law in action:

So as the angle approaches 90 (grazing) the perceived length gets smaller and smaller. So if you start with a ray bundle that hits a surface with an perceived width of ds, the true length is going to get larger as the angle tends to grazing (here think of ds as the width of the blue beam). Of course if you are looking at it at normal incidence, then its true length is the same as its perceived length, and cos(alpha) = 1 as expected.

### #5112117Digits of Pi

Posted by on 26 November 2013 - 06:01 AM

Together with the 50% chance of a bullet being there at all, the 100% chance of having it in your chamber if there is one gives you a 50% overall chance. No need for complicated proofs or experiments.

No, that is a fallacy, and one the paradox is designed to point out. Think about it, if the gun is empty then there is a much higher likelihood that both of you will survive the first five chambers (read: if you played many such games, where you and your opponent lived to the last chamber, then you will see the gun is empty more often than it is loaded - that is kind of the definition of probability). And so conversely, if you survived the first five chambers, then there is a higher probability the gun is empty than it is loaded. That probability turns out to be 6/7 by the proofs given above (so you die 1 out of 7 times) but that argument is enough to "intuitively" show it can't be 50%.

If you want, you can try out the problem "in real life" (with appropriate safety measures taken, please) and you will see that if you follow the problem statement carefully, the answer will come out at 1/7, not 1/2 like you say. It's not the mathematics that are wrong, it's your understanding of what the problem is saying and when it applies which is. That's why it's called a paradox, it's supposed to pick your brains. Don't take it personally, you're not the first (and won't be the last) to get all confused over things like this.

### #5111989How deep should Item subclass inheritance be?

Posted by on 25 November 2013 - 06:48 PM

You should use composition rather than inheritance. IMHO for games in particular inheritance deeper than one level (where it can come useful in some cases) is questionable.

Think about it - what if a potion could do multiple things? Inheritance becomes a tangled mess of relationships, whereas you could instead have a Potion class, which takes a list of Attributes which give a certain effect to the Player drinking them (say, +20 health, +50 strength for some time, cure all poisons, ..) and those Attributes could themselves be composed of smaller attributes (e.g. "cure" and "cure target: burn") in order to allow very complex effects while keeping the logic small and self-contained.

If you want to go full entity-component-system, then you don't even need the Potion class. You can just have an entity with components "name" (Potion of ...), "drinkable" (for instance), and then a bunch of Attributes that will be applied when drinking. But that may be overkill, or might not map well to the particular gameplay you have in mind.

Think about the first example, and see if you understand it, see if you can draw the benefits of using that approach. It will likely make your code much easier to reason about than using brute force inheritance.

### #5111389Some clarification about string to double conversion

Posted by on 22 November 2013 - 08:59 PM

Why is it "supposed" to print 1.0? The value "1" can be represented exactly in a double, and you didn't specify any particular format, so it just prints that number in the most natural way possible, that is, "1" (actually, I think it is implementation dependent). If ss contained "1.0000000000000000000000000000000000000000000000000000000000000000000000000000000000" would you argue that dd should also be printed exactly the same?

If you want to obtain a certain precision/number of digits, you can tell cout that by passing stream modifiers, e.g. std::setprecision, etc..

PARTNERS