•      Sign In
• Create Account

Banner advertising on our site currently available from just \$5!

# cadjunkie

Member Since 28 Feb 2013
Offline Last Active May 28 2015 03:38 PM

### #5225112Better way for geometry problem

Posted by on 23 April 2015 - 12:44 PM

The easiest way I can think of is to use vector math to find BC (BA+AC=BC) and AD (AD = DB-BA) and get the intersection E from them. You can find the analogue to point C on the circle around D (call it G) to construct a line BG and F would be the intersection of BG and AD.

I wrote an article that details a method that simply uses the cross product to determine the intersection of 2 lines. The lines need to be in an implicit form (ax+by+c=0) and the resulting point is in homogeneous coordinates (x*w,y*w,w), but those transformations are very simple. This method also doesn't yield any infinities if the lines are parallel, and no trigonometric functions are used.

http://www.gamedev.net/page/resources/_/technical/math-and-physics/advanced-intersection-test-methods-r3536

### #5223446Can i do this using the fourier transform?

Posted by on 15 April 2015 - 09:57 AM

I'm unsure on what you're trying to accomplish. Can you provide a more detailed and concrete example?

### #5222938Understanding Generalized Barycentric Coordinates

Posted by on 13 April 2015 - 09:09 AM

Randy Gaul is right. You lose the one-to-one mapping because you can find other sets of weights that satisfy all the equations.

However, if I understand the application right (which maybe I don't), I don't think you need to care about that for a rasterizer. Losing the one-to-one mapping in this case means that you could have two points be rendered as the same color, but does that matter? I wouldn't think so, but then I might be missing the point of the application.

### #5222136Understanding Generalized Barycentric Coordinates

Posted by on 08 April 2015 - 04:54 PM

Your example doesn't work because of 2 things:

1. You're using the normal Cartesian coordinates of the triangle points instead of converting them to barycentric coordinates.
2. You're basically pre-selecting the barycentric coordinates. You need to use the formulas to compute all the $$w_j$$ values and then you'll see $$\sum_{j=0}^n w_j(\mathbf{q}_j-\mathbf{p}) = 0$$, where $$\mathbf{q}_j, \mathbf{p}$$ are in Cartesian coordinates.

In order to get the proper interpolation you're looking for, You have to use the formulas in that paper to convert the point to the barycentric coordinates (the $$\alpha_j$$ vector) and then dot that with the values you want those points to have in order to get the interpolated value of the given point.

I will agree with Randy Gaul that you do lose coordinate uniqueness if the polytope isn't a simplex. However, I disagree with him that this paper is not interesting. True, barycentric coordinates with a simplex will guarantee a unique coordinate value for any point, but there are a lot of uses beyond just finding points in a simplex, although you have to be sufficiently interested in computational geometry to appreciate them. In a game programming setting, there might be only a couple of relevant uses beyond this one.

### #5219365Cubic interpolation on an irregular grid (triangle mesh)?

Posted by on 26 March 2015 - 11:06 AM

As a quick note about the Bezier triangle, you have to be somewhat careful in "ghosting" your vertices. Interpolation is a way of getting continuous data out of a smaller set of discrete data. You've got a certain amount of information in your data set and interpolation won't increase that amount of information. The linear, quadratic, and cubic interpolation schemes are just ways of guessing what's happening between the data points, but it doesn't give you any new information that you didn't have before. I guess the main point here is if you're trying to linearly interpolate the triangle vertices to get these "ghost" points and then use a cubic interpolation to get the colors, you're going to end up with a cubic approximation of a linear interpolation.

The polyharmonic spline is probably a good way to go if you're comfortable with the approximations it's making. It assumes that the grid points are exact and that it minimizes the "bending energy". The way Eberly puts it, it's like a thin metal sheet that is constrained not to move at the grid points. However, you're right that the linear solve will take a lot of time, especially since the matrices are not sparse. It's really up to you.

http://www.geometrictools.com/Documentation/ThinPlateSplines.pdf

http://mathematica.stackexchange.com/questions/11765/data-interpolation-and-listcontourplot/11883#11883

### #5219073Cubic interpolation on an irregular grid (triangle mesh)?

Posted by on 25 March 2015 - 09:06 AM

Yes you can, in a similar fashion to how you're doing it there. You'll need to have more data points along the edges and in the middle (10 points for a cubic interpolation), similar to a Bezier triangle:

It's going to be tricky since it'll be hard to guarantee a 10-point triangle. There might be some sort of adaptive method, but I'm not sure how to make it work with the mesh you've shown here.

### #5217872Explaining to an idiot (me) about mathematics concerning ocean waves

Posted by on 20 March 2015 - 09:37 AM

From reading Tessendorf's paper and all the other code examples out there (and doing an implementation in Matlab), I think I can try to offer some explanations.

It seems you're getting the correct $$H_0$$ spectrum from the texture. My image (in grayscale) and images in other papers look similar to yours:

To get the height map, you need to use your texture values in the following formula and you can plug in the time parameter there as well:

$H(k,t) = H_0(k,t)e^{i \omega t} + H_0^* e^{-i \omega t},\, \omega = g \left | k \right |$

where $$H_0^*$$ is the complex conjugate of $$H_0$$. I think since your Y coordinate in the color vec3 seems to be the "imaginary" component of the complex number, then you can get the complex conjugate by just multiplying Y by -1. This $$H(k,t)$$ is your height map. Here you can plug in your time $$t$$ and get the animated displacements (at least I think it works; I didn't do the full animation). The decomposition into the spatial directions is given by:

$D_x(k)=i\frac{k_x}{\left | k \right |}H(k),\,D_y(k)=i\frac{k_y}{\left | k \right |}H(k)$

From there, you take the inverse FFT to get your spatial coordinates. In my Matlab implementation, those came out as complex numbers so I just took the norm and used that for the values, but I think you can just use the real parts as well. My 3 spectrum images look like this (dx, height, dy):

I haven't gotten around to using these to actually create waves. I've never done water simulations before, but the problem interested me from a theoretical standpoint so I figured I'd try it out. I'll post my Matlab code and if you use NumPy/SciPy the functions I used are very similar if you want to load it up and mess with it. Hope this helps!

clear;
clc;
close all;

M = 512;    % resolution of grid
N = 512;    % resolution of grid
L = 2000;   % height of waves used to calculate dx and dz

[m,n] = meshgrid(-M/2:1:M/2, -N/2:1:N/2);
kx = 2*pi/L * m;
ky = 2*pi/L * n;

W = [30,0];        % horizontal wind vector (m/s)
V = norm(W);        % m/s?
What = W / V;
g = 9.81;           % m/s^2
A = 1.0;            % amplitude of wave

% compute Phillips spectrum and freq amplitudes
P = zeros(M,N);
H0 = zeros(M,N);
for i=1:M
for j=1:N
k = [kx(i,j),ky(i,j)];
nk = norm(k);
if(nk == 0)
mag = 0;
else
khat = k / nk;
mag = A / nk^4 * exp(-1/(nk * V^2/g)^2) * ((dot(khat,What)))^2;
end
damping = exp(-nk^2*(L/1000)^2);
val = mag * damping;
P(i,j) = val;
H0(i,j) = 1/sqrt(2) * (randn + randn * 1i) * sqrt(val);
end
end

figure(1)
imshow(abs(H0))

% compute heightmap
H = zeros(M,N);
Dx = zeros(M,N);
Dy = zeros(M,N);
t = 1;
for i=1:M
for j=1:N
k = [kx(i,j),ky(i,j)];
nk = norm(k);
w = sqrt(g*nk);
val = H0(i,j)*exp(1i*w*t) + conj(H0(M-i+1, N-j+1))*exp(-1i*w*t);
H(i,j) = val;
if(nk == 0)
Dx(i,j) = 0;
Dy(i,j) = 0;
else
Dx(i,j) = 1i*k(1)/nk * val;
Dy(i,j) = 1i*k(2)/nk * val;
end
end
end

dx = abs(ifft2(Dx));
dy = abs(ifft2(Dy));
dz = abs(ifft2(H));

figure(2)
subplot(1,3,1)
imshow(dx)
subplot(1,3,2)
imshow(dz)
subplot(1,3,3)
imshow(dy)


### #5214574How to do 3D feature detection?

Posted by on 04 March 2015 - 06:01 PM

I work directly with Parasolid and if it has feature recognition capabilities, I've never seen them. I know that other CAD packages such as Solidworks have tools to do that, but those tools may only exist within the CAD program and not within the geometry kernel itself.

This is actually a big area of research in the CAD world because there are standards such as IGES and STEP that just give B-spline geometry but no "feature" information. We call them "dumb bodies" because they don't tell you anything about how they were created. However, B-spline geometry can give you clues as to what certain shapes are. For example, a NURBS curve might be a circular edge based on how the control points relate to each other. But in this case, you have a curve you can test and not a string of vertices.

I'm sure that simple features such as holes, bosses, etc. can be extracted from the point data but it would be somewhat more involved. For example, the triangle vertices on a circular edge will have some roundoff error so you'll have to tolerance that, etc. I don't know offhand of any software tools that do this kind of thing that don't cost an arm and a leg.

### #5213989Delaunay Traingulation

Posted by on 02 March 2015 - 12:21 PM

I think you're better off using Fortune's algorithm. Not only do you get exactly what you're after, the time complexity is pretty good.

### #5211497How to create code to map function for Coefficient of Lift

Posted by on 18 February 2015 - 11:47 AM

My aircraft textbook states that the continuous function can be approximated by blending the functions between the coefficient of lift for a flat plate and a linear function that increases with angle of attack:

$$C_L = (1-\sigma(\alpha)) C_{L,linear} + \sigma(\alpha) C_{L,flat}$$

The flat plate function can be expressed as: $$C_{L,flat}=2\,\text{sign}(\alpha)\sin^2{\alpha}\cos{\alpha}$$

The linear function can be expressed as: $$C_{L,linear}=C_{L_0}+C_{L_{\alpha}}\alpha$$

$$C_{L_{\alpha}} = \frac{\pi AR}{1+\sqrt{1+(AR/2)^2}}$$

$$AR=b^2/S$$

Here, b is the wingspan and S is the wing aspect ratio, and CL0 is a dimensionless quantity that depends on the aircraft but you can probably use 0 or something. The blending function you can use is:

$$\sigma(\alpha) = \frac{1+e^{-M(\alpha-\alpha_0)}+e^{M(\alpha+\alpha_0)}}{(1+e^{-M(\alpha-\alpha_0)})(1+e^{M(\alpha+\alpha_0)})}$$

Here, M is the transition rate and alpha_0 is the cutoff, so you can adjust the parameters to get the curve you want. When I was doing a small aircraft simulator for UAVs, I used these same equations so I know they work.

### #5209501Generate easing function from hash table/value pairs

Posted by on 08 February 2015 - 05:03 PM

Using that power polynomial to interpolate values is a good way to do it too. Just be careful with power polynomials with a large degree because they tend to be a bit numerically unstable. Bezier curves, Catmull-Rom splines or B-splines are better for this kind of evaluation because they are formulated in a Bernstein basis rather than a power basis. If the error becomes unacceptable, consider converting to a different kind of curve.

EDIT: Also you might be able to get away with a lower-degree polynomial if you were to use a Bezier curve since you will have more granular control over the curves by modifying control points. Power basis curves aren't intuitive to manipulate.

### #5209358Generate easing function from hash table/value pairs

Posted by on 07 February 2015 - 10:35 PM

I second Servant's suggestion. Constructing a Bezier curve, Catmull-Rom spline or even a B-spline can help you interpolate your values. Your real-valued range can be expressed as the "control points" of the curve and you can plug in some modified control values for the curve's parameter values (for Bezier curves, for example, parameter values will be between 0 and 1). Getting the right kind of function would require some effort on your part because you'd have to figure out what the control point values would be, but once the proper function would be determined, the calculations would be quick.

### #5206044How to figure out if something is in the area of a circle?

Posted by on 22 January 2015 - 02:28 PM

I'm not sure if the OP wants to detect if a point is inside a circle. He wrote about a "target" and in games a target is usually some kind of object that has a size, so checking a point might give wrong results. To the OP, if you want to do that thing I said you should research about collision detection, so you can detect a valid target even if only a part of the target is at a certain distance of the weapon.

Can't the OP just get some sort of bounding box/convex hull and tests each point if it lies inside the circle? I guess this is a weaker form of collision detection, but it might be tenable given the point-in-circle test is really computationally simple.

### #5198813static friction

Posted by on 17 December 2014 - 12:39 PM

Just for clarification for others reading this, there is no correlation between surface area and friction. Amontons' Second Law states "the force of friction is independent of the apparent area of contact." The difference in friction forces in your example comes from the difference in mass, not the difference in surface area.

### #5194006Line intersection algorithm?

Posted by on 21 November 2014 - 12:47 PM

There's actually a way easier way of doing a line intersection test in 2D, and it's probably better if you're coding in Javascript since JS needs all the speedup it can get. There's a line-line intersection test section in the article below. Let me know if this helps.

http://www.gamedev.net/page/resources/_/technical/math-and-physics/advanced-intersection-test-methods-r3536

PARTNERS