• Content count

  • Joined

  • Last visited

Community Reputation

1122 Excellent

About TheAdmiral

  • Rank
  1. Perimiter Path from a Contiguous Discrete 2D Area

    CPPNick, That's close, but what I'm after is kind of the converse. Rather than the smallest convex hull containing the area, I want the largest (in terms of area enclosed) potentially concave closed curve that fits inside it. Thanks all the same Admiral
  2. Hi, I have a little problem that I'd like solved as efficiently as possible. It seems like quite a common task and so I was hoping that somebody here knows of a standard routine. Suppose I have a 2D, bounded, regular Cartesian grid of points. Within this grid is defined a 'zone of control'; imagine the border of a country for instance. The only query operation available is a boolean test that tells me if any given point is within this zone or not. If I can guarantee that the area of 'controlled' points is contiguous, but not necessarily convex, how can I efficiently compute the closed path that represents the zone's perimeter? I can see half a dozen ways to do this but they're all fairly messy and O(n3) or worse. Considering that the grid can get pretty big and I'm hoping to perform the computation in a single frame (but only occasionally) I'd like something snappy. Thanks Admiral Ps: It's good to be back and see so many familiar names [smile]
  3. very interesting problem

    Quote:Original post by Zahlman 0) You have a question, not a doubt. (This seems to be a very common English error nowadays; I have no idea why.) As you probably guessed, the two terms are interchangeable in many other languages. I'm not an expert, but this is a very common mistake for Indian speakers as the two words are synonymous in their language. Furthermore, the two terms are often more correctly used the other way around from English in certain languages, apparently, including Italian.
  4. approximating a surface with a spline

    You may be interested in the oscillation theorem. There are many variants, but the basic 'continuous real-valued function' version roughly says that the best order n L∞ polynomial approximation to a curve will be such that its error oscillates n-1 times between +E and -E, where E is the maximum error on the interval. It sounds like a mouthful, but it's fairly intuitive when you break the expression up and think about it. This theorem directly leads to the exchange algorithm, which provides an iterative method of refining a spline-approximation by repositioning the abscissas. The theorem translates quite directly to approximation of surfaces, and I would be surprised if there is no way to adapt it to efficiently regress a surface with the node count as a parameter. I also recommend you take a look at Numerical Recipes, as I recall it has a fairly strong section on this sort of business.
  5. Triangulation of two Segments in 3D

    How about this? There are three possible assignments of four points to two line-segments. In each case, compute the dot-product of the two normalised edge vectors. I assert that the assignment pertaining to the largest product, in magnitude, will not produce a complex quadrilateral [citation needed].
  6. ZeroMemory in a constructor

    You can't put executable code in the initialisation list. Unless XINPUT_STATE provides a constructor that does this then you must make the call from the body of your constructor: struct CONTROLLER { DWORD connected; DWORD controllerNumber; XINPUT_STATE state; CONTROLLER(); }; CONTROLLER::CONTROLLER() { ZeroMemory( &state, sizeof(XINPUT_STATE) ); }
  7. rotating an object to fit a vector

    Quote:Original post by amerisgeekon what is the matrix arithmetic that can churn out one vector into another? What?
  8. missing pixel after rotating

    You're not just missing one pixel, but the entire left column and bottom row. The image is defined on the domain [0, source->w - 1]×[0, source->h - 1]. Note the exclusivity. So when you compute dx = source->h - y; the interval becomes [1, source->h] and the row is lost. Similarly for dy. The correct code would use: dx = source->h - y - 1; dy = source->w - x - 1;
  9. Quote:Original post by padli Solution found... If this is a small-scale project and you don't want to force the user to install the redistributable, you can link against the VC runtime libraries statically and avoid all the SxS mess.
  10. DirectX DirectSound

    How about this? if (current_position >= last_position) { num_bytes_to_read = current_position - last_position; } else { num_bytes_to_read = current_position + (size_of_buffer - last_position); }
  11. Physically enabled object bound to a bezier curve

    Quote:Original post by Vorpy How do I find the closest point on the curve to the object? I don't understand how to do this at all. I googled this but every answer I find seems rather heavy (like, dissertations or white papers), and I was hoping there was a somewhat standard method of doing this. EDIT: Also, if i use this method I would then have to find where on the curve the object is, in terms of a float between 0 and 1 (in order to ascertain the progress along the curve so the gradient of the current point can be found). Yes, you need to keep track of this value. The primitive way to proceed is as follows: First, establish a bound on the parameter within which the closest point must lie. This will depend on the instantaneous speed of the particle, the arc-length of the spline segment and the maximum arc-velocity of the segment, but a rough approximation would do just fine. From this maximum delta value and the previous parameter value, determine an upper- and a lower-bound (on the arc-length parameter) for the possible closest point. Now perform a binary-search on this up as far as the desired accuracy. That is, recursively or iteratively evaluate the distance between the point and the current interval's edges & midpoint; reassign the interval to the appropriate half-interval. When the interval becomes small enough (say, smaller than a pixel), you're done. Obviously, this algorithm is fallible. It assumes uniqueness of a local minimum and won't work very well for splines with sharp curves. This is why you should aim to keep the object moving 'slowly' with respect to the frame-rate. But given these constraints, the algorithm is fast and effective. If you need something a bit more advanced, look up gradient-descent. It's a more intelligent iterative procedure, but is a little harder to understand. Quote:Is there a way to do this through a standard equation or function?Theoretically, yes (assuming your spline segments are polynomials of order five or less), but you'll run into no end of problems with regard to uniqueness and bounding. It's probably best avoided.
  12. 4x4 Matrix Inversion

    I don't like the way this code tests for singularity. Testing (determinant == 0.0) is only asking for trouble. (fabsf(determinant) < EPSILON) is a far more stable alternative. I say so not only due to floating-point inaccuracy, but because this method of inversion will give stupid answers even for non-singular matrices, given a small enough determinant.
  13. Perspective projection matrix

    That's a block-matrix. Behold the power of recursive inversion: aspect/f 0 0 0 0 1/f 0 0 0 0 0 -1 0 0 dp/(2*far*near) (far+near)/(2*far*near) Edit: Damn you, Zipster. I'll take consolation in the fact that this provides some level of verification [rolleyes].
  14. B-spline curve intersection

    Please don't cross-post. You've been told before. This is probably the best forum for this question, but I already posted here.
  15. There are plenty of ways to do this, but I can't see a way to get much improvement, in the general case, over using the rasteriser to do the work for you. If you are using shaders, this is even easier: On a separate render-target, simply draw the alpha channels of the two sprites - transformed as usual - onto an empty buffer using a logical-and operator. Then check the area of intersection for any non-empty pixels. Existence of such pixels signifies collision. What API are you using? I imagine this method would be pretty snappy when implemented correctly under programmable 3D acceleration, but perhaps not so much for a CPU-based pixel renderer. If this won't do, then you could always sample the sprites under your own rotation operator. It's fairly straight-forward to use a little matrix-mathematics and point-sample the result, but it may be a little heavy on the CPU for large sprites.