Cramer's Rule for the calculation of alpha and beta in the 2nd book, chapter 6.5

[Bowen951209]

I want to propose another way to calculate $\alpha$ and $\beta$ in quad intersection in chapter 6.5 in the 2nd book.
In the book, we calculate $\alpha$ and $\beta$ using this formula:

$$ \alpha = \vec{w} \cdot (\vec{p} \times \vec{v}) $$ $$ \beta = \vec{w} \cdot (\vec{p} \times \vec{p}) $$

where $\vec{w} = \frac{\vec{n}}{\vec{n}\cdot\vec{n}}$.

However, I've never seen the trick described in the book to calculate this. Instead, I would use Cramer's Rule. For a quick reminder, if we want to solve:

$$ \begin{aligned} a_1 x + b_1 y &= c_1 \\ a_2 x + b_2 y &= c_2 \end{aligned} $$

The solutions for $x$ and $y$ are:

$$ x = \frac{\Delta_x}{\Delta}, \quad y = \frac{\Delta_y}{\Delta} $$ , where $$ \Delta = \begin{vmatrix} a_1 & b_1 \\ a_2 & b_2 \end{vmatrix} = a_1 b_2 - a_2 b_1\\ $$

$$ \Delta x = \begin{vmatrix} c_1 & b_1 \\ c_2 & b_2 \end{vmatrix} = c_1 b_2 - c_2 b_1 $$

$$ \Delta y = \begin{vmatrix} a_1 & c_1 \\ a_2 & c_2 \end{vmatrix} = a_1 c_2 - a_2 c_1 $$

If we assume that $\vec{p}$ can be the linear combination of $\vec{u}$ and $\vec{v}$, then there must be solutions for $\alpha$ and $\beta$.
Set $\vec{p} = (p_{x}, p_{y}, p_{z})$, $\vec{u} = (u_{x}, u_{y}, u_{z})$, $\vec{v} = (v_{x}, v_{y}, v_{z})$. And we want to solve the below equation for $\alpha$ and $\beta$:

$$ (p_{x}, p_{y}, p_{z}) = \alpha (u_{x}, u_{y}, u_{z}) + \beta (v_{x}, v_{y}, v_{z}) $$

In a clearer form:

$$ \begin{aligned} \alpha u_{x} + \beta v_{x} = x \\ \alpha u_{y} + \beta v_{y} = y \\ \alpha u_{z} + \beta v_{z} = z \end{aligned} $$

To solve $\alpha$ and $\beta$, you might think only two of the above equations are needed to get $\Delta$, $\Delta \alpha$, and $\Delta \beta$ in Cramer's Rule, but it's actually not the case. We can only use the components that ensures $\Delta$ is not $0$, and this how I check it in GLSL:

float delta, alpha, beta;

if((delta = u.x * v.y - u.y * v.x) != 0) {
    alpha = (planar_hitpt_vector.x * v.y - planar_hitpt_vector.y * v.x) / delta;
    beta = (planar_hitpt_vector.y * u.x - planar_hitpt_vector.x * u.y) / delta;
} else if((delta = u.x * v.z - u.z * v.x) != 0) {
    alpha = (planar_hitpt_vector.x * v.z - planar_hitpt_vector.z * v.x) / delta;
    beta = (planar_hitpt_vector.z * u.x - planar_hitpt_vector.x * u.z) / delta;
} else {
    delta = u.y * v.z - u.z * v.y;
    alpha = (planar_hitpt_vector.y * v.z - planar_hitpt_vector.z * v.y) / delta;
    beta = (planar_hitpt_vector.z * u.y - planar_hitpt_vector.y * u.z) / delta;
}

We simply find a non-zero $\Delta$ (and there must be at least one) and calculate the respective $\Delta \alpha, \Delta \beta$, and solve $\alpha = \frac{\Delta \alpha}{\Delta}$, $\beta = \frac{\Delta \beta}{\Delta}$.

In my implementation in OpenGL, I get a 10% boost in the 5 quads scene at max ray depth of 50 and 200 samples.

Book's approach:

My approach:

[petershirley]

Cramer's rule is a lovely approach and I think was made popular here: https://en.wikipedia.org/wiki/M%C3%B6ller%E2%80%93Trumbore_intersection_algorithm I think its only drawback is that it requires linear algebra which some readers might not be familiar with.

…

On Sat, Nov 2, 2024 at 7:22 AM bowen951209 ***@***.***> wrote: I want to propose another way to calculate $\alpha$ and $\beta$ in quad intersection in chapter 6.5 in the 2nd book. In the book, we calculate $\alpha$ and $\beta$ using this formula: $$ \alpha = \vec{w} \cdot (\vec{p} \times \vec{v}) $$ $$ \beta = \vec{w} \cdot (\vec{p} \times \vec{p}) $$ where $\vec{w} = \frac{\vec{n}}{\vec{n}\cdot\vec{n}}$. However, I've never seen the trick described in the book to calculate this. Instead, I would use Cramer's Rule <https://en.wikipedia.org/wiki/Cramer%27s_rule>. For a quick reminder, if we want to solve: $$ \begin{aligned} a_1 x + b_1 y &= c_1 \\ a_2 x + b_2 y &= c_2 \end{aligned} $$ The solutions for $x$ and $y$ are: $$ x = \frac{\Delta_x}{\Delta}, \quad y = \frac{\Delta_y}{\Delta} $$ , where $$ \Delta = \begin{vmatrix} a_1 & b_1 \\ a_2 & b_2 \end{vmatrix} = a_1 b_2 - a_2 b_1\\ $$ $$ \Delta x = \begin{vmatrix} c_1 & b_1 \\ c_2 & b_2 \end{vmatrix} = c_1 b_2 - c_2 b_1 $$ $$ \Delta y = \begin{vmatrix} a_1 & c_1 \\ a_2 & c_2 \end{vmatrix} = a_1 c_2 - a_2 c_1 $$ If we assume that $\vec{p}$ can be the linear combination of $\vec{u}$ and $\vec{v}$, then there must be solutions for $\alpha$ and $\beta$. Set $\vec{p} = (p_{x}, p_{y}, p_{z})$, $\vec{u} = (u_{x}, u_{y}, u_{z})$, $\vec{v} = (v_{x}, v_{y}, v_{z})$. And we want to solve the below equation for $\alpha$ and $\beta$: $$ (p_{x}, p_{y}, p_{z}) = \alpha (u_{x}, u_{y}, u_{z}) + \beta (v_{x}, v_{y}, v_{z}) $$ In a clearer form: $$ \begin{aligned} \alpha u_{x} + \beta v_{x} = x \\ \alpha u_{y} + \beta v_{y} = y \\ \alpha u_{z} + \beta v_{z} = z \end{aligned} $$ To solve $\alpha$ and $\beta$, you might think only two of the above equations are needed to get $\Delta$, $\Delta \alpha$, and $\Delta \beta$ in Cramer's Rule, but it's actually not the case. We can only use the components that ensures $\Delta$ is not $0$, and this how I check it in GLSL: float delta, alpha, beta; if((delta = u.x * v.y - u.y * v.x) != 0) { alpha = (planar_hitpt_vector.x * v.y - planar_hitpt_vector.y * v.x) / delta; beta = (planar_hitpt_vector.y * u.x - planar_hitpt_vector.x * u.y) / delta; } else if((delta = u.x * v.z - u.z * v.x) != 0) { alpha = (planar_hitpt_vector.x * v.z - planar_hitpt_vector.z * v.x) / delta; beta = (planar_hitpt_vector.z * u.x - planar_hitpt_vector.x * u.z) / delta; } else { delta = u.y * v.z - u.z * v.y; alpha = (planar_hitpt_vector.y * v.z - planar_hitpt_vector.z * v.y) / delta; beta = (planar_hitpt_vector.z * u.y - planar_hitpt_vector.y * u.z) / delta; } We simply find a non-zero $\Delta$ (and there must be at least one) and calculate the respective $\Delta \alpha, \Delta \beta$, and solve $\alpha = \frac{\Delta \alpha}{\Delta}$, $\beta = \frac{\Delta \beta}{\Delta}$. In my implementation in OpenGL, I get a 10% boost in the 5 quads scene at max ray depth of 50 and 200 samples. Book's approach: image.png (view on web) <https://github.com/user-attachments/assets/ee6413c8-4808-4497-841e-602b236545c0> My approach: image.png (view on web) <https://github.com/user-attachments/assets/645418e3-3238-43d4-808f-4a22a8ab20be> — Reply to this email directly, view it on GitHub <#1648>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAVLVCTXWEZCBHPHUGVIZLDZ6TG3HAVCNFSM6AAAAABRBXLX7GVHI2DSMVQWIX3LMV43ERDJONRXK43TNFXW4OZXGQYTANBVGE> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[hollasch]

Nice! While I think we'll just stay with the geometric method in the book, we have a lot of small speedups that we leave on the table for implementers in favor of simplicity and letting readers create superior implementations.

That said, I'm loathe to just let tips like this lie in obscurity. We have had many conversations about how to best handle "further reading" topics, recommended books & papers, appendix topics, footnotes and discussions like this one. I think this one pushes me over the edge to somehow reference this in the material.

[hollasch]

Ref #1654