Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Don't forget to read Tuesday's email newsletter for your chance to win a free copy of Construct 2!


cadjunkie

Member Since 28 Feb 2013
Offline Last Active Nov 21 2014 12:55 PM

#5194006 Line intersection algorithm?

Posted by cadjunkie 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 




#5189927 Does Valve have a good working methodology?

Posted by cadjunkie on 29 October 2014 - 08:11 AM


Assuming respect and non-corporate bullshit, they might actually have their own sub-system to trade amongst peers: "If you dedicate some time to my project, I'll lend a hand with yours" similar to what civilized people tend to do out of the industry (and even sometimes "in" the industry).

 

If you're dealing with people that have respect, I agree. However, most of the brilliant and talented coders I've worked are astoundingly arrogant. Now that may be just my experience (and it can be said arrogance is arguably a necessary trait for brilliance in coding), but I can't imagine trying to get a couple of them to work on your project without them intimating that the trade isn't equal in their view.

 


I don't know that. Steam was a pretty cool R&D piece. It is true they don't release often, but there's something to be said of companies that make a lot of money and can afford to trash multi-million ideas (WOW fueled Blizzard so much they could actually trash Titan, and kill SC2 2 times before releasing something). What's to say we're not better, as customers, for not witnessing half-assed ideas? I like there's some form of filtering that can happen when a company makes piles of cash because, I for one, hate shovelware.
Of course, this could mean a bunch of good ideas don't get through because the majority of valve's employees don't believe in this, but I don't think this should be perceived as some form of oligarchic censorship.

 

There's no question that Steam is a wonderful example of R&D work. However, they'll need maintenance teams to really get all the bang out of it. Maintenance, IMHO, is not glamorous. Most coders I know (including myself) wouldn't do it unless they "have" to. I'd much rather choose to start a new, fresh project rather than maintain the old project's code. Valve purposefully allows their employees to choose what they do, so why wouldn't they decide to do something else? I'm sure like all coders they've come up with a few ideas during development they've been wanting to work on. I think a few people that are really interested in Steam might choose to maintain the code and some might do it to make their peer review ratings higher or possibly even garner favor with the "decision-making" employees, but I don't see it being done in an altruistic way like Valve would have you believe based on their employee manual.

 

 

Don't get me wrong. I think Valve's culture is admirable. They're trying to take the open-source coding model and build a radical business management concept from it. Props to them. However, I think it gets more complicated and eventually unstable when you introduce money into the equation. 




#5189390 Does Valve have a good working methodology?

Posted by cadjunkie on 27 October 2014 - 07:46 AM

I can't imagine a large percentage of people do actual productive work at Valve. Sure, I get how if you get enough people from within the company that think your idea is cool enough, most likely it will be fueled, released, and probably succeed in the marketplace. I would think the problem would be that *everyone* probably thinks their idea is infinitely cooler than everyone else's, so you've got lots of half-finished products and hundreds of valuable man-hours wasted because you've got no real authority (other than gravitas) to say "let's all focus on this". R&D teams are needed to keep things fresh and they shouldn't consist of the same people all the time, but the company manual makes me think the culture there is "R&D all the time" because they say their personal project time is 100%. Any company will tell you that they need some workers to focus on the core products people buy in order to fuel future development. Working to refine a product that's already "complete" isn't the most fun thing ever, but it's needed to allow the company to take risks without collapsing. I'm sure the older, more experienced Valve employees see that, but maybe their fringe employees don't. Makes me wonder what will happen to the company when the "old guard" start to exit. 




#5154070 Whats a good mathematical model for heat transfer?

Posted by cadjunkie on 16 May 2014 - 12:01 PM

Depends on the type of heat transfer and how detailed you want. Are you trying to model conduction and convection or radiation as well? Conduction and convection are pretty simple, but radiation takes a bit of code. For a simple model with conduction and convection, the resistive model is a good one.




#5150627 Article - Programming Sucks

Posted by cadjunkie on 30 April 2014 - 02:43 PM

"It always starts with 'Bro'." So true.




#5128459 Unity-like transform component

Posted by cadjunkie on 03 February 2014 - 10:55 AM

Is there a framework that you're using or are you creating something like that in DirectX/OpenGL/etc?




#5123722 Solve path around a given point and radius

Posted by cadjunkie on 14 January 2014 - 06:44 PM

Here's a fairly decent way to solve this problem. I'm assuming this will be a "line,circle,line" problem, but you can alter this for different cases. I would put the line into parametric form and the circle into implicit form:

\[ C(t) = (x-a)^2 + (y-b)^2 - r^2 = 0; L(x(t),y(t)) = [x_0 + ct, y_0+dt] \]

Here, \( (a,b) \) is the center of the circle, \( r \) is the radius, and \( (x_0,y_0) \) is the start point of the path and your direction vector \( V_1 = (c,d) \). By substituting the parametric line formulas into the implicit circle formula, we can get a polynomial whose roots are the intersection points in the line parameter space:

\[ \begin{aligned} (x_0+ct-a)^2 + (y_0+dt-b)^2 -r^2 &= 0 \\ (c^2+d^2)t^2+2[c(x_0-a)+(y_0-b)]t+[(x_0-a)^2+(y_0-b)^2-r^2] &= 0 \\ At^2+Bt+c &= 0 \\ \end{aligned} \]

The roots can be solved for quickly using the quadratic equation:

\[ t = \frac{-B\pm \sqrt{B^2-4AC}}{2A} \]

If the discriminant \( B^2 - 4AC < 0 \), then you have no intersections. If  \( B^2 - 4AC = 0 \), you've got 1 intersection. If  \( B^2 - 4AC > 0 \), you've got 2 intersections, which is really the only case you have to worry about to avoid the object since the path can stay linear for any other cases. You can then evaluate the parametric line at the roots of the polynomial to get the intersection points in (x,y) form. You can get the angles of the points on the circle using \( \theta = \text{atan2}(y-b, x-a) \). If the problem is as shown in the OP's picture (where the starting path point isn't inside the circle), you also know which point to start from and which point to end with because the point with the lesser parameter value t is the point closest to \( (x_0,y_0) \).

 

Deciding which path around the circle is shorter is the last issue to resolve. We could calculate arc length, but we can figure out which way to go by using the implicit form of the line and figuring out which side of the line the circle's center is. The implicit line formula is given by \( \mathcal{A}x+\mathcal{B}y+\mathcal{C}=0 \). The coefficients for the implicit line are simple to calculate from the parametric form: \( \mathcal{A} = -d, \,\mathcal{B} = c, \,\mathcal{C} = dx_0-cy_0 \). The equation then becomes \( D = d(x_0-a)+c(b-y_0) \). If D < 0, then the circle center is on the right side of the line (looking in the direction of the line). That means the clockwise path around the circle is the shortest path. If D > 0, then the circle center is on the left side of the line, which means the counterclockwise path is the shortest. If D = 0, then the circle center lies on the line and each path is the same length.

 

You can step with constant velocity along the path by using the parametric form of the line and along the circle by figuring out your angle step via \( ds = r d\theta \). As I see it, this is fairly elegant because there's nothing more than additions, multiplications, atan2, and a square root function, making it a fairly fast method.

 

Hope that helps!




#5120731 Sorting (mathematical) vectors in list

Posted by cadjunkie on 02 January 2014 - 11:38 AM

You could create a sort method that takes in a lambda expression so you can sort differently depending on your case. I can envision a lot of ways to sort vectors (by length, by coordinate, by dot product with another vector, etc.) so you might want to keep your options open.




#5118491 Building background knowledge for high level math-physics

Posted by cadjunkie on 20 December 2013 - 09:56 PM

If you want to understand fluid dynamics, then I suggest picking up an introductory book on it. The math is a different matter, IMHO. I don't pretend to understand why Hodge decomposition works for this, so I can't help you there.

 

This paper is actually very interesting. As an mechanical engineer, I have a decent understanding of fluid dynamics and the Navier-Stokes equations. After reading this paper, it's interesting that they don't exactly follow the Navier-Stokes equations because of the problems when dealing with nonlinear partial differential equations. I always wondered how games handle fluids because real CFD is even hard to set up so it runs right in a proper solver, let alone program a solver that runs in real-time. 




#5110772 question about quadratic bezier patch

Posted by cadjunkie on 20 November 2013 - 09:31 AM

Sorry for my misleading picture. The blue curve is a curve generated by the middle control points. As apatriarca said, it is NOT on the Bezier surface, however, the middle control point for any v-isoparameter curve will be on that blue curve. This is analogous to the first and last control points being on the edge curves of the Bezier surface, and these edge curves are generated by the left and right control points at the edge of the control net. 

 

The idea is that you can treat the columns of the control grid as separate Bezier curves and evaluate them at a specific v. Then, those evaluated points can become another Bezier curve (a v-isoparameter curve) that you can evaluate at a specific u. Then, that evaluated point is on the surface. You can do the same thing with the rows of the control grid to get a u-isoparameter curve, and then evaluate that at a specific v to get the point on the surface.

 

HTH




#5110483 question about quadratic bezier patch

Posted by cadjunkie on 19 November 2013 - 09:20 AM

Apatriarca's right on. Each point on the Bezier surface corresponds to a (u,v) parameter. You can get what's called an isoparametric curve by holding one of the parameters constant. In your example, you're holding v = 0.7, which does yield a curve like you've drawn. The control points of that curve can be found by evaluating the Bezier curves in that direction at v = 0.7. I've modified your drawing to show what I mean:

 

Untitled.png

 

The blue curve is just the Bezier curve defined by the 3 middle control points. The point on that curve at v = 0.7 is the middle control point for the orange curve, just like the end control points for the orange curve are the surface edge Beziers evaluated at v = 0.7. Mathematically, the Bezier surface is defined like this:

\[ S(u,v) = \sum_{j=0}^n \sum_{i=0}^m P_{ij} B_{i}^m(u) B_j^n(v) \]

where m and n are the degrees in the u and v directions, respectively, and \( B_i^n(t) = \binom{n}{i} (1-t)^{n-i}t^i \). If you hold a parameter constant (in this case, we'll hold \( u = u_0\)), and group the inside terms like so:

\[ S(u,v) = \sum_{j=0}^n \left [ \sum_{i=0}^m P_{ij} B_{i}^m(u_0) \right ] B_j^n(v) =  \sum_{j=0}^n Q_j B_j^n(v) \]
you can see that \( Q_j \) are control points for an isoparametric curve at \( u = u_0 \). The above picture shows how this works graphically. I hope that helps to back up what apatriarca was saying.
 
@apatriarca: I think the forums use MathJax, like the articles do. You can use \ [ and \ ] to enable LaTeX and \ ( and \ ) for inline typesetting. I had to add spaces between the slashes and brackets above to stop MathJax from rendering them as LaTeX.



#5110188 question about quadratic bezier patch

Posted by cadjunkie on 18 November 2013 - 08:48 AM

With Bezier curves, the only control points that are guaranteed to be on the curve are the endpoints. Bezier surfaces are like Bezier curves, where the corner control points of the Bezier patch are guaranteed to be on the surface. In a biquadratic Bezier surface patch, you'll have 9 control points, but every point but the center one will control the edges of the Bezier patch. In the example below, the surface is a bicubic patch, but as you can see, the edges are controlled by all the control points at the edges of the patch, not just the corners. The control points at the corners are on the surface, but none of the others are. 

 

surf2.gif

I don't quite understand what you mean with all your talk about infinities. It might be better to explain what you're using the Bezier patch information for so others here can help you devise a good strategy for solving your problem.




#5100184 NURBS / line intersection

Posted by cadjunkie on 10 October 2013 - 08:39 AM

You can do NURBS/line intersection, but it's not easy. Bezout's theorem states that the number of intersection points of 2 polynomials is equal to the product of their degrees, but you have to count intersection points at infinity, intersection points with a multiplicity greater than 1, and so on. For example, 2 lines (degree-1 polynomials) intersect at one point. Even if the lines are parallel, they intersect at infinity. So what you have is a NURBS of degree p intersecting a line with degree 1, so they intersect p times. 

 

One way is to use implicitization and resultants to find common roots of the curves. This will be quick for NURBS of degree 3 or less, but for greater degrees you should use subdivision methods. A good link to study implicitization and resultants is http://cagd.cs.byu.edu/~557/text/ch17.pdf. You could also just get a polyline of the NURBS and do line-line intersection tests. 




#5067116 NURBS vs Rational Bezier Patches

Posted by cadjunkie on 03 June 2013 - 09:52 AM

1) A NURBS can be easily decomposed into a set of Bezier curves with a specified continuity between consecutive curves. That means that a NURBS surface patch can be decomposed into a set of Bezier patches. It does work both ways via knot insertion and knot deletion. (Aside: knot deletion can't always be performed and yield the same curve/surface, so you'll have to know when you can do it)

 

2) The knot vector affords properties that you don't get with the Bezier formulation. The biggest problems with Beziers are local control and degree increase. For example, adding more control points to a Bezier curve increases your control of the curve shape, but it also increases the degree of the polynomial, increasing your computation time. As well, if you move a Bezier control point, the whole curve changes. The knot vector of the NURBS allows for a collection of multiple Bezier curves of the same degree and the order of the NURBS with local control, because each NURBS control point only influences a certain part of the whole NURBS, not all of it (local control).

 

Mathematically, the knot vector specifies a parameter interval over which the recursive basis functions act. A better way to picture this is to visualize the knot vector as specifying the start and end parameter values of the constituent Bezier curves. For example, the knot vector [0 0 0 0 1 2 2 2 2] for a 3rd-order NURBS says that the NURBS consists of 2 Bezier curves, one on the interval (0,1) and one on the interval (1,2). Furthermore, the knot vector tells us what the continuity of the curves are. In this case, the curves have C2 continuity at the parameter value 1. If the knot vector was [0 0 0 0 1 1 2 2 2 2], we'd still have 2 Bezier curves at intervals (0,1) and (1,2), but the continuity between the curves would only guaranteed to be C1 (however, if we inserted this knot, then the curves would still be C2). Middle knots (i.e. not the start or end knot values) can have a maximum of multiplicity "n" in the knot vector, and the minimum continuity of the Bezier curves at those parameter values is C^(n-k), where n is the order of the NURBS and k is the multiplicity of the knot. The properties of the knot vector also explain your question (4). Simply put, the knot vector adds a measure of control you don't have when working with Bezier curves.

 

3) The calculations for finding a NURBS point and normal are certainly more complicated than finding ones for Bezier surface patches. There are techniques for evaluating them more quickly, but you can always decompose the NURBS into Bezier surface patches and get points and normals that way. It's probably about the same amount of work either way.

 

4) In addition to the info on the knot vector, since the starting parameter value has multiplicity 4 (i.e. since the NURBS in this example is 3rd-order, it's n+1), then we know this NURBS curve passes through the starting control point. The end parameter value is also multiplicity 4, so the curve passes through the end control point. The knot vector doesn't necessarily have to have those "end conditions". The knot vector for a cubic NURBS can be [0 1 2 3 4 5 6 7 8], which means that the curve doesn't pass through the ends, consists of 2 Bezier curves at intervals (3,4) and (4,5) with continuity C2 at t=4.

 

In my opinion, Bezier surface patches are nicer to work with, but unless you know exactly how to "stitch" the Bezier patches together via control point placement, NURBS patches are probably what you want.




#5044932 Ordinary Differential Equation ?

Posted by cadjunkie on 20 March 2013 - 10:49 AM

It really depends on what kind of modeling you want to do. Like it's been said many times above, to achieve more physical realism you'll have to resort to ODEs sometime. I think taking a course on ODEs before numerical methods would probably be useful. Numerical methods are what you're going to need if you ever want to actually apply your ODE knowledge, but understanding what it is that the numerical methods are actually doing is important.

 

 

and ODEs like the heat and wave equations are themselves solved by eigendecomposing a linear operator (the sines/cosines are its eigenvectors).

Not to be too nitpicky, but as far as I remember, the heat and wave equations are second-order PDEs, not ODEs.






PARTNERS