# Tag Info

10

There is really no good way of doing this efficiently analytically for all corner cases. Most or all commercial 2D renderers that attempt to do analytic coverage calculation make predictable errors that multisampling methods do not. A typical problem is two overlapping shapes that share the same edge. The common situation is that alpha channels sum up to a ...

9

All conics (including rotated ellipses) can be described by an implicit equation of the form H(x, y) = A x² + B xy + C y² + D x + E y + F = 0 The basic principle of the incremental line tracing algorithms (I wouldn't call them scanline) is to follow the pixels that fulfill the equation as much as possible. Depending on the local slope of the line, you ...

9

The classic book Computer Graphics: Principles and Practice (second edition) by Foley, van Dam, et al. describes such an algorithm in section 19.2. The explanation in the book seems to come from an MSc thesis, Raster Algorithms for 2D Primitives by Dilip Da Silva. See also these papers: Curve-drawing algorithms for raster displays by Van Aken and Novak (...

7

What you (probably) want to achieve is something like this: When having a closer look at one of the corners and add a few lines, we see this: The black lines indicate that the center points of the circles along the borders of the red and blue boxes is the same. If the outer radius of the red box, for example, is $50px$, and the distance between the outer ...

6

Ignoring Non-uniform B-splines (rational or not), I have had some experience with rasterisation of Beziers and, since there is a trivial mapping from Uniform B-Splines to Beziers, those too. I have used two different techniques: The first was a scan-line renderer that used Newton-Rhapson to compute the intersection of the current scanline with the curve. ...

6

You have an instance of a problem called curve reconstruction from unorganized points. Now that you know what to search for you'll find several methods, such as the crust, NN-crust, etc. Here are a few links: The Crust Curve Reconstruction Applet Curve Reconstruction by Tamal Dey Curve and Surface Reconstruction: Algorithms with Mathematical Analysis, book ...

6

The subdivision schemes are not arbitrary. Catmull-Clark, arguably the most used subdivision scheme, generalizes bicubic B-splines to meshes of arbitrary topology. Most, other subdivision schemes also generalize other degree B-splines to arbitrary topology. Doo-Sabin for biquadratic B-splines and Loop subdivision generalizes quartic box-splines defined ...

5

Check out the section on Circular Arcs and Circles, from Ching-Kuang Shene's excellent computational geometry course notes: [G]iven three control points P0, P1 and P2 such that P0P1 = P1P2 holds, if we choose w, the weight for P1, to be sin(a), where a is the half angle at control point P1, the resulting rational Bézier curve is a circle. The second ...

5

What you want is linear interpolation like @Tim points out. However he uses a formula that is not so easily understandable form, we can refactor it differently. Basically linear interpolation is a weighted average where the weight of the first term is in range of 0-1 and the weight of the other value is 1-weight. Literature usually uses t for the weight and ...

5

The math you need is linear interpolation. I think of a player sprite which moves from position X to position Y. Pseudocode: playerSprite.x = Y.x + t * (X.x - Y.x) playerSprite.y = Y.y + t * (X.y - Y.y) where t is a value between 0.0 and 1.0 (floating point). Instead of incrementing the position components of Y you increment t till it reaches 1. When it ...

5

One way I can think of is to make a "signed distance transform" of the image where there is information for each pixel about how far the pixel is to the closest surface of the shape. Since it's signed, youll be able to know if the pixel is inside or outside he shape, and by how much. Using this knowledge, you could easily make a new image, where the pixel ...

4

Subdivision can be used for curves in 2D just as easily as for surfaces in 3D. Usually the subdivision algorithms applied to 2D are called subdivision curves. Subdivision curves do not suffer from the problem that subdivision surfaces have around extraordinary points and therefore all subdivision surfaces can easily be converted to (uniform) B-splines. This ...

4

Quoting the comments above for context: Just to confirm, are you asking, given a set of $N$ CatRom control points, $$\{CR_0, CR_1, CR_2, CR_3 ... CR_{n-1}\}$$ forming a piecewise curve, what is the equivalent $N$ points, $$\{B_0,B_1,B_2...B_{n-1}\}$$ for a matching piecewise uniform cubic bspline? Exactly. That is what I'm looking for. I think conversion ...

4

Ok, monotonic interpolation depends on what you are monotonic about. For a simple 1D function interpolation monotonicity is easy to define. But for a 2D and 3D dataset its not so self evident what the situation would be. First you could interpolate along a independent variable t in which case your monotonicity is most probably in relation to t. This is the ...

4

After some clarifications, there is probably a much better approach that doesn't even require knowing the parametric form of the curve, and also avoids the potentially problematic numeric minimisation step. If the curve does not intersect itself and the points are sufficiently densely packed on the curve (and by that I mean they have to be closer than any ...

3

A simple example of taking a the derivative of a B'ezier curve can be shown using a cubic curve. $$C_3(u) = \sum_{i=0}^3 B_{3,i}(u) P_i,$$ where $u \in [0,1]$ and $B_{n,i} = {n \choose i} u^i (1-u)^{n-i}$ is the $i$-th Bernstein polynomial of degree $n$. $P_i$ are the control points. written out it is: $$C_3(u) = (1-u)^3 P_0 + 3(1-u)^2 u P_1 + 3 (1-u)u^2 P_2 ... 3 Most software rendering engines dice the parametric primitives to micropolygons, usually on the fly as needed. In essence this reduces the needed complexity to determine intersections. The surface will still look smooth, since each polygon is smaller than a pixel. This allows for Data caching. Discrete geometric derivates. Displacement is easy to ... 3 Since you've only got floating-point representations of the points, there is no guarantee that these still lie exactly on the curve, due to rounding errors. So I think the only generic approach is to approximate where on the curve they were, by finding the closest point on the curve to your sample (X,Y,Z). E.g. if your parametric curve is (x(t), y(t), z(t)... 2 No, B is constant for given type of cubic spline, e.g. B-spline, Bezier, Hermite or Catmull-Rom cubic splines have different B matrix. To make B-spline continuous, you need to copy 3 control points from the previous spline segment a to the control points of spline segment b and add a new point as the last control point of b such that: Pb_{i-3}=... 2 No, the B matrix (basis coefficient matrix) does not change from one segment to the next. It is a property of the type of spline you're using, in this case cubic B-splines. If you used Bézier splines or Hermite splines instead, you'd have a different B matrix. 2 I have no knowledge of the literature on the topic, but I did something very similar to what you're asking some time ago: I wanted to generate lathe meshes and bend them according to a spline. I think the same technique could be adapted to your case quite easily. First you would need to define what your default axis is: if the input mesh corresponds to the ... 2 In line 15 use the half-open interval, i.e., if u>=t[i] and u<t[i+1]: Otherwise, at knot values, you evaluate two basis functions at the k=1 basis when you only want one. This causes the wrong evaluation of the basis function at the knot values and therefore the spikes. 2 For a function y = f(x) the (signed) curvature at x is given by:$$ \kappa(x) = \frac{f''(x)}{(1+f'^2(x))^{\frac{3}{2}}} $$If you assume that the slope is very small compared to 1:  f'^2<\!<1 , then:$$ k(x) \approx f''(x)$$Suppose you are given data points (x_0<x_1<\cdots<x_N):$$(x_0,y_0), (x_1,y_1), ..., (x_N, y_N) You ...

2

Splines confuse me which is one reason I asked somebody else to write that chapter. But I like this explanation: https://www.johndcook.com/blog/2009/02/06/the-smoothest-curve-through-a-set-of-points/

1

So you have a series of points and, at each point, a supplied derivative? Is a piecewise cubic sufficient or does it need higher derivative continuity? If the former is ok, then Cubic Hermite Splines will do the job. (If you need, they can be trivially mapped into cubic Beziers)

1

Winding number as in https://en.wikipedia.org/wiki/Winding_number? Unless I'm mistaken, one way is to fire, say, a horizontal 'ray' out from your point towards, say, $+\infty$. Each time you cross an edge, $(V_n V_{n+1})$ that is going up (i.e.$V_n[y] <V_{n+1}[y]$) , increment a counter, and decrement if the edge is going down. The special cases of ...

1

Disclaimer: I've done some work in the past with wavelet decomposition of image data but it occurred to me that it may be applicable to your problem. Admittedly, I don't actually know if the following will work well in practice but, given how simple the approach is, and, as no other answer has been put forward, it seems to warrant investigation Let's ...

1

What you're looking for is called de Boor's algorithm. It lets you compute a point on a b-spline curve by doing a series of linear interpolation (LERP) calculations. So, it works very much like the de Casteljau algorithm for Bezier curves. In fact, the de Casteljau algorithm is a special case of de Boor's algorithm. A link Another one And another

Only top voted, non community-wiki answers of a minimum length are eligible