• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.

eq

Members
  • Content count

    666
  • Joined

  • Last visited

Community Reputation

654 Good

About eq

  • Rank
    Advanced Member
  1. I don't find anything wrong in your equations. However I think it's wrong to call it "pixelWorldSize" since IMO a pixel can't have a "fixed" size (as in a single float) in world coordinates. It's really the length of a side of the square that results from projecting a pixel onto the viewing plane. As for coming up with a good name for this I'd leave it to someone with more imagination ;)
  2. One way to do compression of floats (delta) is to simply ignoring the lower bits. Here's a test where I ignore the least significant 18 bits (i.e down-shifting the bit representation of the float by 18): Server |Delta (as hex )|Comp (Hex )|Restored |Abs err |Rel err ============================================================================= +49.753967|-0.246033 (be7beff8)|-0.234375 (0be7)|+49.765625|+0.011658|0.0234% +49.923962|+0.169996 (3e2e135c)|+0.156250 (03e2)|+49.921875|-0.002087|0.0042% +50.586922|+0.662961 (3f29b7d3)|+0.625000 (03f2)|+50.546875|-0.040047|0.0792% +50.973202|+0.386280 (3ec5c68c)|+0.406250 (03ed)|+50.953125|-0.020077|0.0394% +50.807159|-0.166044 (be2a0754)|-0.140625 (0be1)|+50.812500|+0.005341|0.0105% +50.807159|+0.000000 (00000000)|-0.004883 (0bba)|+50.807617|+0.000458|0.0009% +51.472042|+0.664884 (3f2a35d4)|+0.625000 (03f2)|+51.432617|-0.039425|0.0766% +51.706005|+0.233963 (3e6f93e0)|+0.250000 (03e8)|+51.682617|-0.023388|0.0452% +51.883965|+0.177961 (3e363b6c)|+0.187500 (03e4)|+51.870117|-0.013847|0.0267% +52.314709|+0.430746 (3edc8aba)|+0.437500 (03ee)|+52.307617|-0.007092|0.0136% +52.116955|-0.197752 (be4a7f95)|-0.187500 (0be4)|+52.120117|+0.003162|0.0061% +52.762184|+0.645230 (3f252dca)|+0.625000 (03f2)|+52.745117|-0.017067|0.0323% +53.464577|+0.702391 (3f33cfe8)|+0.687500 (03f3)|+53.432617|-0.031960|0.0598% +53.361858|-0.102718 (bdd25da4)|-0.070313 (0bd9)|+53.362305|+0.000446|0.0008% +53.701660|+0.339801 (3eadfa5c)|+0.312500 (03ea)|+53.674805|-0.026855|0.0500% +53.752785|+0.051126 (3d5169a0)|+0.070313 (03d9)|+53.745117|-0.007668|0.0143% +53.691513|-0.061274 (bd7af9f8)|-0.050781 (0bd5)|+53.694336|+0.002823|0.0053% +53.987885|+0.296373 (3e97be30)|+0.281250 (03e9)|+53.975586|-0.012299|0.0228% +54.393696|+0.405812 (3ecfc6a0)|+0.406250 (03ed)|+54.381836|-0.011860|0.0218% +54.693333|+0.299638 (3e996a32)|+0.281250 (03e9)|+54.663086|-0.030247|0.0553% Server is the value that we modify (for instance X position of enemy Z). Delta is the difference since we last updated the client (i.e value to send over the network). as hex is the binary representation of delta. Comp is the compressed delta value (i.e clearing the lower 18 bits). Hex is the binary representation of delta down-shifted by 18. Restored is the server value as seen by the client (X position of enemy Z). Abs err is the absolute error (Restored - Server). Rel err is the relative error in percentage from the server value. Now why did I chose to represent the delta as 14 bits (32 - 18)? Well, look at the highest byte of the compressed delta values (Hex column). They are always 0x0b or 0x03! As long as the delta values stays about the same (i.e more or less constant velocity etc) the upper bits of a float is more or less the same. This could be exploited to make a very simple compressor that achieves a reduction of the data sent by 25% to 33% (of course the actual ratio depends on a lot of factors). I've done a compression class that uses the two lower bits of the first data byte to indicate which compression to use, I have 3 different packets: * Full (4 bytes), uses 4 bytes, only the two lower bits of the full float is dropped). * Half (2 bytes), contains the 14 most significant bits (as the example above). * Quad (1 byte), contains the 6 bits found from bit 25 to 20 + the top 6 bits coming from a special cache. The cache caches the two most recent MSB 6 bits found. Here's the results: Server | Delta | ClentView | S | Restored | Abs err | Rel err ============================================================================= +50.144604 | +0.144604 | +50.144592 | 4 | +50.144592 | -0.000011 | 0.0000% +50.096180 | -0.048425 | +50.096741 | 2 | +50.096741 | +0.000561 | 0.0011% +50.337101 | +0.240921 | +50.335022 | 2 | +50.335022 | -0.002079 | 0.0041% +50.871639 | +0.534539 | +50.835022 | 1 | +50.835022 | -0.036617 | 0.0720% +50.663052 | -0.208586 | +50.663147 | 1 | +50.663147 | +0.000095 | 0.0002% +50.663052 | +0.000000 | +50.663052 | 2 | +50.663052 | +0.000000 | 0.0000% +50.502411 | -0.160642 | +50.506802 | 1 | +50.506802 | +0.004391 | 0.0087% +50.399143 | -0.103267 | +50.405239 | 1 | +50.405239 | +0.006096 | 0.0121% +50.984863 | +0.585719 | +50.983364 | 2 | +50.983364 | -0.001499 | 0.0029% +51.138805 | +0.153943 | +51.123989 | 1 | +51.123989 | -0.014816 | 0.0290% +51.527740 | +0.388936 | +51.498989 | 1 | +51.498989 | -0.028751 | 0.0558% +51.356907 | -0.170835 | +51.358364 | 1 | +51.358364 | +0.001457 | 0.0028% +52.036530 | +0.679624 | +51.983364 | 1 | +51.983364 | -0.053165 | 0.1022% +52.330551 | +0.294023 | +52.327114 | 1 | +52.327114 | -0.003437 | 0.0066% +52.746738 | +0.416189 | +52.733364 | 1 | +52.733364 | -0.013374 | 0.0254% +53.013142 | +0.266404 | +52.983364 | 1 | +52.983364 | -0.029778 | 0.0562% +53.240330 | +0.227187 | +53.233364 | 1 | +53.233364 | -0.006966 | 0.0131% +53.065865 | -0.174467 | +53.077114 | 1 | +53.077114 | +0.011250 | 0.0212% +53.108719 | +0.042856 | +53.108364 | 1 | +53.108364 | -0.000355 | 0.0007% +53.598732 | +0.490013 | +53.577114 | 1 | +53.577114 | -0.021618 | 0.0403% ============================================================================= Bytes needed: 27 (80 for uncompressed), ratio: 33.75%, Max error: 0.1022% ClentView is the what the server thinks that the client should have (must be equal to clients real value). S is the size needed to send the change. Using this simple compression scheme we reduced the size needed to send the changes by 33% by allowing an error of about 0.1%. Running the same tests on 10000 delta increments gave: Bytes needed: 10376 (40000 for uncompressed), ratio: 25.94%, Max error: 0.1025% Edit2: Added support for specifying the maximum allowed error. When a max relative error of 0.01% was used I got: Bytes needed: 11301 (40000 for uncompressed), ratio: 28.25%, Max error: 0.0100% The source for the coder class (it will not compile out of the box): class DeltaFloatCoder { public: DeltaFloatCoder() : m_first(true) { m_clientView = 0.0f; m_cache[0] = 0; m_cache[1] = 0; } uint encode(const float f, uint& bytesReturned, const float maxErr = 0.0001f) { union { float asF; uint asU; }; asF = f - m_clientView; const uint m = asU >> 26; // Top 6 bits const uint h = updateCache(m); if (!m_first){ if (h < 2){ // Send as a single byte, h code in the two lower bits, then 6 bits of data const uint d = (asU >> (26 - 6 - 2)) & 0xfc; asU = d << (26 - 6 - 2); asU |= (m << 26); const float err = (f != 0.0f) ? fabsf(((m_clientView + asF) - f) / f) : 0.0f; if (err < maxErr){ logDebug("Encode: %f 0x%02x 0x%08x", asF, asU >> 26, (asU & 0x3ffffff) << 2); m_clientView += asF; bytesReturned = 1; return h | d; } asF = f - m_clientView; } // Send as two bytes asU &= 0xfffc0000; const float err = (f != 0.0f) ? fabsf(((m_clientView + asF) - f) / f) : 0.0f; if (err < maxErr){ logDebug("Encode: %f 0x%02x 0x%08x", asF, asU >> 26, (asU & 0x3ffffff) << 2); m_clientView += asF; bytesReturned = 2; return (asU >> 16) | 2; } asF = f - m_clientView; }else { m_first = false; } asU &= ~3; logDebug("Encode: %f 0x%02x 0x%08x", asF, asU >> 26, (asU & 0x3ffffff) << 2); m_clientView += asF; bytesReturned = sizeof(float); return asU | 3; } float decode(const uint data, uint& bytesUsed) { union { float asF; uint asU; }; const uint code = data & 3; if (code == 3){ asU = data & ~3; logDebug("Decode: %f 0x%02x 0x%08x", asF, asU >> 26, (asU & 0x3ffffff) << 2); m_clientView += asF; updateCache(asU >> 26); bytesUsed = sizeof(float); return m_clientView; } if (code == 2){ asU = (data & 0xfffc) << 16; logDebug("Decode: %f 0x%02x 0x%08x", asF, asU >> 26, (asU & 0x3ffffff) << 2); m_clientView += asF; updateCache(asU >> 26); bytesUsed = 2; return m_clientView; } const uint h = m_cache[code]; asU = (data & 0xfc) << (26 - 6 - 2); asU |= (h << 26); logDebug("Decode: %f 0x%02x 0x%08x", asF, asU >> 26, (asU & 0x3ffffff) << 2); m_clientView += asF; updateCache(asU >> 26); bytesUsed = 1; return m_clientView; } inline float getClientView() const { return m_clientView; } private: uint updateCache(const uint t) { if (m_cache[0] == t) return 0; if (m_cache[1] == t){ m_cache[1] = m_cache[0]; m_cache[0] = t; return 1; } m_cache[1] = m_cache[0]; m_cache[0] = t; return 2; } float m_clientView; uint m_cache[2]; bool m_first; } Code snippet that was used for these test: float serverValue = 50.0f; float clientValueView = serverValue; float clientValue = serverValue; cprintf("Server |Delta (as hex )|Comp (Hex )|Restored |Abs err |Rel err\n"); cprintf("=============================================================================\n"); uint i; for (i = 0; i < 20; ++ i){ float delta = RandFast::srandf() - 0.25f; if (i == 5) delta = 0; const uint deltaU = *((const uint*)&#948;); serverValue += delta; const float clientDelta = serverValue - clientValueView; const uint compDeltaU = *((const uint*)&clientDelta) >> 20; const uint t = compDeltaU << 20; const float compDelta = *((const float*)&t); clientValue += compDelta; clientValueView += compDelta; const float absError = clientValue - serverValue; const float relError = fabsf(serverValue != 0.0f ? absError / serverValue : 0.0f) * 100.0f; cprintf("%+8f|%+8f (%08x)|%+8f (%04x)|%+8f|%+8f|%1.4f%%\n", serverValue, delta, deltaU, compDelta, compDeltaU, clientValue, absError, relError); } cprintf("=============================================================================\n"); cprintf("Server | Delta | ClentView | S | Client | Abs err | Rel err\n"); cprintf("=============================================================================\n"); DeltaFloatCoder server; DeltaFloatCoder client; uint totSize = 0; serverValue = 50.0f; float maxError = 0.0f; float oldClient = 0.0f; for (i = 0; i < 10000; ++ i){ float delta = RandFast::srandf() - 0.25f; if (i == 5) delta = 0; serverValue += delta; uint size; const uint data = server.encode(serverValue, size); // Add size bytes to client stream const float clientValue = client.decode(data, size); // Fill data with up to sizeof(float) bytes of the server stream const float deltaClient = (i > 0) ? (clientValue - oldClient) : delta; oldClient = clientValue; // Remove size bytes from the server stream const float absError = clientValue - serverValue; const float relError = fabsf(serverValue != 0.0f ? absError / serverValue : 0.0f) * 100.0f; if (relError > maxError) maxError = relError; cprintf("%+8f | %+8f | %+8f | %u | %+8f | %+8f | %1.4f%%\n", serverValue, delta, server.getClientView(), size, clientValue, absError, relError); totSize += size; } cprintf("=============================================================================\n"); cprintf("Bytes needed: %u (%u for uncompressed), ratio: %.2f%%, Max error: %1.4f%%\n", totSize, i * sizeof(float), float(totSize) * 100.0 / float(i * sizeof(float)), maxError); A few notes (that apply to ALL delta encoding techniques): * If the client "misses" to perform an update (packet loss etc) the simulation will blow up. * The client and server must increment the expected value in exactly the same way or the simulation will blow up. The last point is VERY hard to achieve (doesn't sound like that, does it?). Everyone that have made 100% deterministic simulation running on several machine types in several different application know what I'm talking about.... The thing is that when you compile the code on the server, the compiler might optimize the code in one way and on the client in another way (giving more or less floating point accuracy). Even my class above is flawed since the increment of the float in the encode and decode process might not compile to the exact same instructions (the compiler might chose to inline these functions and do optimizations on the code that calls them etc). In fact the SAME function might be inlined in several places and optimized in different ways! Remember that (often) the internal precision of calculations is higher than the number of bits stored in memory so if the encoder does everything without storing something to memory and the decoder stores some temporaries to memory they will produce different results and in the end the simulator will blow up. Sometimes the code might use SSE, sometimes not etc. One way to make things deterministic is to put all the encoding / decoding stuff in a DLL. Use the exact same DLL in all applications on all machines. The first thing to do in every function in the DLL is to set the FPU rounding and precision to whatever you like. Test.. a lot... and pray... Edit: Forgot to mention that you also must setup the FPU after EVERY call to an OS function (or into some one else's code that you don't have access to). Some OS functions changes these flags, some functions load DLL's that changes these flags.. even if an OS function doesn't change the flags on your system it might on someone else's. I.e on one OS a services is installed that attaches a hook to OutputDebugString, the hooked function writes the text to a log file. Innocent enough? But some other program might log file writes, thus hooking the write functions and "accidently" change the FPU flags. Ans so on.. Just my 2c on the topic. Cheers, Eq [Edited by - eq on August 16, 2010 7:34:02 AM]
  3. Hi all, I need to render the scene as if the first hit surface was invisible. I.e in a ray tracer I would skip the closest hit and instead use the second closest hit along each ray. This needs to be done on the GPU effectively (using DirectX 9). One solution is to render the scene normally (closest hit) to a Z-buffer (using INTZ or to a color render target). In a second pass you frist clear the Z-buffer, then render the scene again, this time you kill all pixels that has a Z equal to or greater than the one found in the texture create by the first pass. The obvious drawbacks of the above is that no AA will work. Furthermore, the second pass requires me to rewrite all pixel shaders (and maybe vertex shaders too) and I've got tons of them (for the first pass I have a Z only version for all shaders that is used if stencil shadows are enabled and for some other effects). Can someone come up with a cleverer way of doing this? In order to reduce the number of shaders I need to rewrite I could do it using 3 passes: Pass 1, Clear the Z-buffer render to Z only. Pass 2, Clear the Z-buffer, render to Z only, rejecting all pixels that has a Z-value equal to the Z-value found in the texture created in pass 1. Pass 3, Render to color buffer and set the depth test so that only pixels that equals the value in the Z-buffer is drawn. Pass 2 would still require some new shaders, but since they are Z-only shaders there aren't too many of them. Any ideas are welcome! Cheers, Eq
  4. Hi, I'm looking for a good allocator strategy that works on regions of a texture. I.e the allocator is created with an initial size (matching a texture for instance). To allocate a region, a call to alloc with a width and height parameter is made. The allocator returns the x and y position of the "most suitable" free space (or false if no free space is found). I was thinking of an interface similar to: class RegionAllocator { public: RegionAllocator(const int width, const int height); bool alloc(std::pair<int, int>& pos, const int width, const int height); void free(const std::pair<int, int>& pos); }; Now, this is SIMILAR to texture packing, but still totally different IMO since I don't have all the blocks at once and I need to be able to dynamically free / alloc new blocks. Further I don't want to move any memory around during an alloc or free call, otherwise you could rebuild a new texture from scratch at every alloc op (but this will be to slow). Please spare me the references to texture packing (something I understand fully and made a good implementation of). Otherwise, any strategies, ideas, references to papers etc are most welcomed (I didn't find anything useful on google, but I probably didn't use the right keywords). I would imagine that only allowing power of two's would simplify things but for my needs I think I'll be wasting to much space with such a strategy. I imagine that maintaining some sort of tree would be necessary. Then traverse down the tree using the node that gives the least waste until you reach a leaf. Problem I see is that when allocating from a node there are at least two possible ways of building the new child nodes (with overlapping spaces), how could one maintain both children and choose the best, then adjust and so on. I'll give it a go tomorrow but as mentioned any pointers are welcomed. Cheers, Eq
  5. I haven't read your code but one thing I seemed to remember (it was years since I wrote my stencil-shadow code) is that for the vertices that you extrude, you just set the .w value to zero, and for the ones you don't want to extrude keep it at one (default). I.e, you don't need to manually manipulate your vertex positions.
  6. This is what I do in my code for this purpose (shadow volumes). const float zNear = mat[3][2] / mat[2][2]; static const float epsilon = 0.0001f; mat[2][2] = epsilon - 1.0f; mat[3][2] = (zNear * 0.5f) * (epsilon - 2.0f); This code works well for me. The major difference seems to be that I'm using HALF the zNear value (also the epsilon is used for the second multiplier. Cheers,
  7. Quote:Add a 1px border to each face, fill with the edge pixels of the adjacent faces. One group of conditionals to select the right face, then just math to fetch/lerp the nearest 4 texels. I think I'll go for this approach, I was planning on using a swizzled (tiled) memory layout to increase cache-coherence since I'm pretty sure I'll benefit from that. Quote:Why would you need any more SPH coefficients than cube map samples? I'm sure that you don't need that, the problem as I see it that you need to read (access in memory) every coefficients for every look up...sounds slow to me, correct me if I'm wrong?
  8. Thanks for the reply, you don't happen do have an idea on how to implement the look up in a clean/fast/robust way? In my mind I see a lot of conditionals and logic which isn't to fast. Reading my question again I realize that using SH or any other representation isn't really what I need, they are all about COMPRESSING data on the sphere surface, but I'm more interested in REPRESENTING data. I wonder if I could tessellate an icosahedron and storing the data at the vertices, that would solve edges but maybe it's too expensive. First finding which triangle a vector belongs too, then subdivide, normalize and recheck.. and so on?
  9. Hi, I'm currently trying to speed up a piece of code, basically it's an expensive function that returns a value based on a direction vector (in 3D). Since the function is more or less static and rather smooth I was thinking of storing pre-computed values in a cube map. So my first question is how to efficiently sample a cube map using a bilinear filter that avoids the seems at face borders? Secondly, since this is all running on a CPU I'm not bound to using cube maps but rather any data structure would do. I was thinking about spherical harmonics since they seems very suitable for this. However, I have some concerns since I need a lot more detail than the typical usage of SH (diffuse lighting etc). Initial tests seems to indicate that I need to have a cube map size of around 128 pixels in order to capture enough details of the function. What's the performance for evaluating higher order SH's? Are there any precision problems (floats, doubles) when evaluating higher order SH's? Another idea I had was to calculate the value of N points uniformly spread over the sphere surface. Store them in a KD-tree or similar for fast lookup, is there a way to get a smooth function from k-nearest neighbour points? Any other ideas? Cheers, Eq
  10. Oh.. and the source: (Will not compile out of the box, but you should be able to fix it up). typedef std::pair<uint, uint> CellIndex; bool getNeighborCellIndex(CellIndex& neighborIndex, const CellIndex& cellIndex, const uint direction, const uint w, const uint h) { static const int directions[4][2] = { 0, -1, 1, 0, 0, 1, -1, 0, }; neighborIndex.first = cellIndex.first + directions[direction][0]; if (neighborIndex.first >= w) return false; neighborIndex.second = cellIndex.second + directions[direction][1]; if (neighborIndex.second >= h) return false; return true; } void traceContour(std::vector<CellIndex>& contour, const Image* const im, const uint x, const uint y, const uint w, const uint h, const uint p) { CellIndex cellIndex = CellIndex(x, y); contour.push_back(cellIndex); uint oldDirection = 0; CellIndex firstCellIndex = cellIndex; for (; ; ){ uint testDirection; CellIndex testCellIndex; uint i; for (i = 1; i < 4; ++ i){ testDirection = (oldDirection + i) & 3; if (getNeighborCellIndex(testCellIndex, cellIndex, testDirection, w, h)){ uint pp; im->getIndex(testCellIndex.first, testCellIndex.second, pp); if (pp == p) break; } } if (i == 4){ // We're on single side that has no other connected neighbors than the previous one. So we must step back on the same cell. if (cellIndex == firstCellIndex) break; // found a complete path of a single cell testDirection = oldDirection; if (!getNeighborCellIndex(testCellIndex, cellIndex, testDirection, w, h)) break; // Should never happen! } if (testCellIndex == firstCellIndex) break; // Found a complete path cellIndex = testCellIndex; // Update current cell index oldDirection = (testDirection + 2) & 3; // Swicth direction from "going to" to "coming from" contour.push_back(cellIndex); } } bool getNeighborCellIndexDiag(CellIndex& neighborIndex, const CellIndex& cellIndex, const uint direction, const uint w, const uint h) { static const int directions[8][2] = { 0, -1, 1, -1, 1, 0, 1, 1, 0, 1, -1, 1, -1, 0, -1, -1, }; neighborIndex.first = cellIndex.first + directions[direction][0]; if (neighborIndex.first >= w) return false; neighborIndex.second = cellIndex.second + directions[direction][1]; if (neighborIndex.second >= h) return false; return true; } void traceContourDiag(std::vector<CellIndex>& contour, const Image* const im, const uint x, const uint y, const uint w, const uint h, const uint p) { CellIndex cellIndex = CellIndex(x, y); contour.push_back(cellIndex); uint oldDirection = 0; CellIndex firstCellIndex = cellIndex; for (; ; ){ uint testDirection; CellIndex testCellIndex; uint i; for (i = 1; i < 8; ++ i){ testDirection = (oldDirection + i) & 7; if (getNeighborCellIndexDiag(testCellIndex, cellIndex, testDirection, w, h)){ uint pp; im->getIndex(testCellIndex.first, testCellIndex.second, pp); if (pp == p) break; } } if (i == 8){ // We're on single side that has no other connected neighbors than the previous one. So we must step back on the same cell. if (cellIndex == firstCellIndex) break; // found a complete path of a single cell testDirection = oldDirection; if (!getNeighborCellIndexDiag(testCellIndex, cellIndex, testDirection, w, h)) break; // Should never happen! } if (testCellIndex == firstCellIndex) break; // Found a complete path cellIndex = testCellIndex; // Update current cell index oldDirection = (testDirection + 4) & 7; // Swicth direction from "going to" to "coming from" contour.push_back(cellIndex); } }
  11. I was bored at work so I tested the algorithm that I gave (on a grid), works like a charm: (The red lines are half an arrow so that you can see the direction) You can also allow for diagonals (8 neighbors): It handles "thin" cells ok: Even a single cell is ok: And lines: Everything I threw at it worked ok:
  12. Just coming up with this now so I dunno if it will work in all cases. A tile has six neighbors, let's number them from 0 to 5 in clockwise order where 0 is the one to the left and up. In pseudo code: cellIndex = findTopLeftCell(); addToPath(cellIndex); // Add this cell to the path oldDirection = 0; firstCellIndex = cellIndex; for (; ; ){ for (i = 1; i < 6; ++ i){ testDirection = (oldDirection + i) % 6; testCellIndex = getNeighborCellIndex(cellIndex, testDirection); if (!cellIsEmpty(testCellIndex)) break; } if (i == 6){ // We're on single side that has no other connected neighbors than the previous one. So we must step back on the same cell. if (cellIndex == firstCellIndex) break; // found a complete path of a single cell testDirection = oldDirection; testCellIndex = getCellIndex(cellIndex, oldDirection); } if (testCellIndex == firstCellIndex) break; // Found a complete path cellIndex = testCellIndex; // Update current cell index oldDirection = (testDirection + 3) % 6; // Swicth direction from "going to" to "coming from" addToPath(cellIndex); } The algorithm doesn't need you to first remove the "inner" tiles and handles single cell wide "lines". Edit: The algorithm should work equally well on a regular grid, using 4 neighbors instead of 6 for straight contours or 8 if stepping diagonally is allowed. Edit2: The find top left step could be replaced by a flood fill from a user selected starting cell. I.e flood fill from the selected cell until you find the top left cell.
  13. Just a heads up. I also think that your code creates two running processes of your exe. If your exe is big, doing a lot of static initiations (locking files maybe?) this could be a potential problem. A "fix" for this is to use CreateProcess instead of system to run the second instance of your exe since that could run be made to just start your process instead of start and wait for it to finish (like system does). Maybe it's possible to still use system but add "start" with the correct command line switches? Cheers, Eq
  14. How could I've missed that! It's so obvious, time to do a brain check soon, this whole parenting stuff must cause more damage than I imagined ;) TY!
  15. IMO the code below should work: template <typename T> struct Foo { }; template <typename T, typename K> void bar(T t, K k = Foo<T>()) { } void test() { int a; bar(a); // Can't compile bar(a, Foo<int>()); // Compiles fine } Does the standard allow this? If not what's the reasoning behind that? Any other workarounds available?