greggles

Thanks for the help! That gives me a bit more confidence in figuring it out. I need to better understand the big 'B' I think. The examples I've seen with the 3 order PN-Triangles seem a lot simpler than that crazy 'B' formula. There must be a way to simplify it. For example, check this out.

 

I guess that B number also has a i,j,k index, I guess that is what is creating the decreasing exponent on these terms... somehow. How do you know which exponent goes with which point?

 

The first thing to understand is that B (a bernstein polynomial) determines how much each point contributes to the final p(u, v) point. The value it returns is between 0 and 1, with 0 meaning that the point won't affect the final output and 1 meaning that it completely determines the output.

 

The "simplified" equation you give is just that... a simplified version of B when n = 3. You can do the math yourself if you want to take the time. Just take the equation for B, make n always 3, and compute the result for every valid i, j, k combination. Then with a bit of algebraic manipulation you could get the same equation. But the way this equation is written is only true for n=3. Breaking down the case of seven control points into a single equation is going to be too unwieldy. Instead, I would suggest trying to understand how to use:

which works for any n, before trying to simplify it.

 

Let's look at how this will be used:

 

Let's say that we have a triangle patch with n = 5 and are trying to determine how much point p₃₀₁ will contribute to the output point at (u,v). We would use the "big B" to determine this. B of 3,1,1 at u,v. The equation would be:

 

( 5! / (3! * 1! * 1!) )   * (uⁱ) * (v^j) * (1 - u - v)^k =

(5*4 *3*2*1) / (3 * 2 * 1 * 1 * 1)  * u³ * v * (1 - u -v) =

20*(u³) * v * (1 - u - v)

 

This means that when u = 0.1 and v = 0.5), the point p₃₀₁ would contribute to the point:

20*(0.001) *0.1 * 1 * (1 - 0.1 - 0.5) =

20*(0.0001)*(0.4) =

0.0008

 

Then back in the for-loop I had talked about before, p(3, 0, 1) would be multiplied by 0.0008 and added to the output point.

 

Note that B can be created as a function in code somewhat easily once you have a factorial function (something that can also be created easily) and a power function (should be available in your favorite programming language's standard library). All that it needs to do is take in multiple parameters (n, u, v, i, j, and k) and output a double value.

 

...well, that was a long explanation. I probably got something in there wrong

Let me know if something needs to be clarified.

First of all, the bold vs. not bold: Anything bold is a point, anything not bold is a number. So when you see p(u, v), it means the Point at the barycentric coordinates u, v.

 

Secondly, the sigma notation used in the article means "sum together all of the values where this equation is true." So, for example, the equation i+j+k=n could be true when 1+0+6=7 or when 0+3+4=7, and so on. 

 

Let's look at the first equation you have posted:

 

When determining how to create the loops, I found the picture of the triangle very helpful. Lets assume that each digit in the point corresponds to the variables i, j, and k in order. Thus, the lower left point of the triangle p003 means i=0, j=0, and k=3. 

 

The first thing that I notice is that i increases from 0 to 3 from bottom to top of the image. This is a basic for loop that we can easily handle.

 

Next, I notice that for any i, the j value starts at 0 on the left and increases until i+j=n on the right. This is another loop we can handle.

 

Finally, the original equation gives us k via algebra: i+j+k=n can be rearranged to k = n - (i+j). That is the final value we need to know.

 

This gives us our final form:

Point p;
for (int i = 0; i <= n; ++i) {
    for (int j = 0; i+j <= n; ++j) {
        int k = n - (i + j);
        p += B(i, j, k, u, v, n) * p(i, j, k); //Probably not quite what you want here, but this is an example of what this might look like.
    }
}

 

Now, the B() function refers to the function on the Gamasutra page and the p function here means "give me the point with i, j, k index." For example, p(0, 6, 1) means p061. 

 

Does this help? The partial derivatives would then be created in a very similar way.

First of all: great post! I like that you brought up such an interesting topic and it got me thinking a bit more about permadeath as another tool in a game designer's arsenal. Some things that I considered and thought I would share:

1. As was mentioned, permadeath forces the player to concentrate and rely more on strategy. This makes it harder for a player to sprint into the action with a shotgun or try a crazy move just to see if it succeeds. It adds the thrill of thinking through your actions and being correct, but reduces the possibility of the thrill of "I can't believe that worked!" 
2. It makes the player more protective of his character, which can lead to a stronger emotional attachment.
3. If a player is going to perform an action, he must be confident it will succeed. I think this is where THPS3 utterly fails as a permadeath game, since it is built on repetitive skill honing (eg. keep practicing until you are able to perform the required steps to reach the secret tape).
4. It can be used to help produce a strong sense of accomplishment ("I can't believe I've made it this far!"), which continually pays off in thrill and feeling of achievement.
5. If the game requires repetition, it may be good to help the gamer have an enjoyable fresh start by producing a new gameplay experience (through procedural levels, changing gameplay, or some other way). Note that cut scenes can become dull because of reduced suspense and surprise. The other option is to build levels in a way that it is exciting to play through again, maybe the earlier parts become easier after repetition. Replay ability becomes paramount.
6. Permadeath isn't necessarily all-or-nothing. Consider games like Super Mario Bros. (first example that popped in my head, though many games fit this description). When considered from the big picture you wouldn't consider it a permadeath game, but inside individual levels it is; hit the lava and you must start back at the beginning. If you wanted to make it more permadeath-esque it could be that each world must be replayed if you die in any level. Take it to the extreme and you must always restart from level 1-1. So death can be considered a bit of a continuum from restart from your last save to restart from the beginning.

Maybe I'm missing something, but what is wrong with (0, 20)?  Although it is not one of the vertices, it is on the bounds of the minkowski difference. My understanding of the GJK algorithm is that it should still work correctly.

Greggles maybe I'm misunderstanding you, what you say is correct but the vertex (0,20) or any support point is indeed one of the vertices... if you mean the vertices of the Minkowski difference.

I think you may have misunderstood me. Let me clarify the calculations:

The original shapes are define by vertices
(-5, 5), (5, 5), (5, 15), (-5, 15)
and
(-5, -5), (5, -5), (5, 5), (-5, 5)

We know (intuitively, but this can be determined algorithmically with more calculation) that the resultant diffence will be a square, so finding the four vertices of the difference:
(-5, 5) - (5, 5) = (-10, 0)
(5, 5) - (-5, 5) = (10, 0)
(5, 15) - (-5, -5) = (10, 20)
(-5, 15) - (5, -5) = (-10, 20)
So there is an edge from (10, 20) to (-10, 20).

(0, 20) lies in the middle of this edge instead of one of its endpoints; thus it is not a vertex.

Maybe I'm missing something, but what is wrong with (0, 20)?  Although it is not one of the vertices, it is on the bounds of the minkowski difference. My understanding of the GJK algorithm is that it should still work correctly.