1
$\begingroup$

You have two lines, $A$ and $B$, in $3$-space, given by their respective endpoints, $(x^A_1,y^A_1,z^A_1),\ (x^A_2,y^A_2,z^A_2)$ for line $A$, and similarly for $B$.   And you're looking at them from your "eye point" $(x^e,y^e,z^e)$ of view. So, to your eye, which line crosses in front of the other? Notation-wise, let $d^A_1$ denote the distance from your eye to endpoint-$1$ of line $A$, etc. (P.S. In case you hadn't guessed, I need the answer for programming purposes -- which line's pixels overwrite the other's where they appear to intersect from the eye-point-of-view. Thanks.)

Edit No answers yet (24 hours later), so let me add the approach I'd come up with, and maybe somebody can elaborate it to a full solution, or at least suggest how to do the algebra (which was my "sticking point"...see below).

So, you can take any point $p_A$ whatsoever along line $A$, and any point $p_B$ along line $B$, and draw the unique line the goes through both points. But that line's very unlikely to also go through your eye-point. However (unless $A$ and $B$ happen to be parallel lines), if you consider the entire family of such lines, i.e., $\forall p_A,p_B:\mbox{the line through them both}$, then there'll necessarily be a unique one of those lines that also passes through your eye-point. So find that line, and then the nearer of those particular $p_A,p_B$ points to the eye-point indicates which line crosses in front of the other.

Okay, so my problem was the "find that line" part. In two dimensions, where lines can always be written in the form $y=ax+b$, I could do it pretty easily. But that form doesn't generally work in three dimensions, i.e., you can't generally write $z=ax+by+c$. Rather, there exist parametric forms, etc, and I'm not seeing how to set_up/solve the corresponding "three equations in three unknowns" kind of problem.

Edit#2 One way to set the problem up is to write a general point $(x^A,y^A,z^A)$ along line $A$ in the form $$(x^A,y^A,z^A)=(x^A_1,y^A_1,z^A_1) +k^A(x^A_2-x^A_1,y^A_2-y^A_1,z^A_2-z^A_1)$$ whereby $(x^A,y^A,z^A)=(x^A_1,y^A_1,z^A_1)$ when you choose constant $k^A=0$, and $(x^A,y^A,z^A)=(x^A_2,y^A_2,z^A_2)$ when constant $k^A=1$. And, similarly for line $B$, $$(x^B,y^B,z^B)=(x^B_1,y^B_1,z^B_1) +k^B(x^B_2-x^B_1,y^B_2-y^B_1,z^B_2-z^B_1)$$ And now you want to choose $k^A,k^B$ such that a line passing through both $(x^A,y^A,z^A)$ and $(x^B,y^B,z^B)$ also passes through your eye-point $(x^e,y^e,z^e)$. So write that line in the same form, introducing a third constant, $k^e$, and your given $(x^e,y^e,z^e)$ eye-point on the left-hand side, $$(x^e,y^e,z^e) = (x^A,y^A,z^A) + k^e(x^B-x^A,y^B-y^A,z^B-z^A)$$ where, in terms of the above two equations, the right-hand side expands to $$(x^e,y^e,z^e) = (x^A_1,y^A_1,z^A_1) +k^A(x^A_2-x^A_1,y^A_2-y^A_1,z^A_2-z^A_1)\hspace{75pt}\\ + k^e\left(\ x^B_1+k^B(x^B_2-x^B_1)-x^A_1-k^A(x^A_2-x^A_1),\hspace{25pt} \\ y^B_1+k^B(y^B_2-y^B_1)-y^A_1-k^A(y^A_2-y^A_1),\\ z^B_1+k^B(z^B_2-z^B_1)-z^A_1-k^A(z^A_2-z^A_1)\ \right)$$ So that's equations for all three $x,y,z$-components "bundled" into one. Taking it apart for the $x$-component, we have, $$ x^e = x^A_1 + k^A(x^A_2-x^A_1)\hspace{125pt}\\ + k^e(x^B_1+k^B(x^B_2-x^B_1)-x^A_1-k^A(x^A_2-x^A_1))$$ and two more identical-looking equations for the $y,z$-components. And all the $x,y,z$'s are known, with the three $k^A,k^B,k^e$ to be solved for.

But that's quite a mess to solve, especially with those terms involving those $k^ek^B$ and $k^ek^A$ products. So I'm thinking/hoping there's got to be a simpler approach, simply to find which line crosses in front of the other. But I'm not seeing what it might be. Any thoughts?...


Sample animated gif image. Watch carefully (very carefully:), and note that when lines intersect, sometimes the wrong color is in front. I want to render the correct foreground/background colors whenever lines intersect... enter image description here


First attempt at implementing "John McClane"'s solution illustrated below. In the preceding gif, note the gray line along the top edge >>incorrectly<< in front of the black line as the cube swings into the back-left quadrant. The gif below correctly shows black-in-front-of-gray. Ditto for the dark-green/turqoise intersection at the top edge as the cube swings through the front-left quadrant (wrong above, correct below)... enter image description here

$\endgroup$
1
$\begingroup$

Consider the vectors $\mathbf a_1 =(x_1^A, y_1^A, z_1^A)$, $\mathbf a_2 =(x_2^A, y_2^A, z_2^A)$, $\mathbf b_1 =(x_1^B, y_1^B, z_1^B)$, $\mathbf b_2 =(x_2^B, y_2^B, z_2^B)$. Also let $\mathbf e =(x^e, y^e, z^e)$ express your point of view.

The line $A$ is then parameterized by $\mathbf a_1+p\,(\mathbf a_2-\mathbf a_1),\,p \in \mathbb R$, similar is for $B$: $\mathbf b_1+q\,(\mathbf b_2-\mathbf b_1),\,q \in \mathbb R$. Essentially, you are looking for a homothety with center at $\mathbf e$ that sends the lines to intersecting (actually, not visually) ones . This means solving the equation $$\lambda\,(\mathbf a_1+p\,(\mathbf a_2-\mathbf a_1) - \mathbf e)=\mathbf b_1+q\,(\mathbf b_2-\mathbf b_1)-\mathbf e \qquad (1)$$ for the unknowns $\lambda, p, q$. Finding the value of $\lambda$ from it and comparing it with $1$ and $0$ will give you the desirable "visual precedence" property.

Computationally, it is more convenient to rewrite $(1)$ as $$\lambda\,\mathring{\mathbf a}+\mu\,\mathbf{\tilde a}+\nu\,\mathbf{\tilde b}=\mathring{\mathbf b}, \qquad (2)$$ where $\mathring{\mathbf a}=\mathbf a_1-\mathbf e$, $\mathbf{\tilde a}=\mathbf a_2-\mathbf a_1$, $\mathring{\mathbf b}=\mathbf b_1-\mathbf e$, $\mathbf{\tilde b}=\mathbf b_2-\mathbf b_1$ and $\mu=\lambda p$, $\nu=-q$ are new unknowns. $(2)$ is a linear system of 3 equations with 3 unknowns $\lambda, \mu, \nu$. You can easily compute two determinants $$\Delta_a=\det \left[ \begin{array}{c|c|c} \mathring{\mathbf a} & \mathbf{\tilde a} & \mathbf{\tilde b} \end{array} \right]= \begin{vmatrix} x_1^A-x^e & x_2^A-x_1^A & x_2^B-x_1^B \\ y_1^A-y^e & y_2^A-y_1^A & y_2^B-y_1^B \\ z_1^A-z^e & z_2^A-z_1^A & z_2^B-z_1^B \\ \end{vmatrix}$$ and $$\Delta_b=\det \left[ \begin{array}{c|c|c} \mathring{\mathbf b} & \mathbf{\tilde a} & \mathbf{\tilde b} \end{array} \right]= \begin{vmatrix} x_1^B-x^e & x_2^A-x_1^A & x_2^B-x_1^B \\ y_1^B-y^e & y_2^A-y_1^A & y_2^B-y_1^B \\ z_1^B-z^e & z_2^A-z_1^A & z_2^B-z_1^B \\ \end{vmatrix}$$ and compare them, to avoid division in $\lambda = \frac {\Delta_b} {\Delta_a}$. More precisely, use the following decision tree.

  • Check the sign of $\Delta_a \Delta_b$.
    1. $\Delta_a \Delta_b > 0$. Compare the absolute values $|\Delta_a|$ and $|\Delta_b|$.
      1. $|\Delta_a| < |\Delta_b|$. This corresponds to $\lambda > 1$ and means that the line $A$ is in front of $B$.
      2. $|\Delta_a| > |\Delta_b|$. This corresponds to $0 < \lambda < 1$ and means that the line $B$ is in front of $A$.
      3. $|\Delta_a| = |\Delta_b|$. This corresponds to $\lambda = 1$ and means that the lines have a unique actual point of intersection, so there is no visual precedence.
    2. $\Delta_a \Delta_b < 0$. This corresponds to $\lambda < 0$, in which case the lines do not visually intersect but pseudo-intersect. This means they cross some line passing through the point of view on opposite sides w.r.t. this point. On a computer screen, you may see such lines as nonintersecting (but not necessarily parallel) rays.
    3. $\Delta_a \Delta_b = 0$. This corresponds to some exceptional cases.
      1. $\Delta_a \ne 0, \Delta_b = 0$. Visually, it may be seen as the infinite point on $A$ (the endpoint of its ray on screen) lying on the image of $B$ or its extension. Conventionally, we may think of $B$ as located in front of $A$. The extreme case of this is when $\mathring{\mathbf b}$ and $\mathbf{\tilde b}$ are linearly dependent meaning that $B$ is passing right through the viewpoint.
      2. $\Delta_a = 0, \Delta_b \ne 0$. Visually, it may be seen as the infinite point on $B$ (the endpoint of its ray on screen) lying on the image of $A$ or its extension. Conventionally, we may think of $A$ as located in front of $B$. The extreme case of this is when $\mathring{\mathbf a}$ and $\mathbf{\tilde a}$ are linearly dependent meaning that $A$ is passing right through the viewpoint.
      3. $\Delta_a = 0, \Delta_b = 0$. This corresponds to cases in which you are unlikely need to determine the visual precedence of the lines. They are:
        1. $\mathbf{\tilde a}=0$ or $\mathbf{\tilde b}=0$. Then corresponding $A$ or $B$ is not line at all but a single point.
        2. $\mathbf{\tilde a} \ne 0$ and $\mathbf{\tilde b} \ne 0$.
          1. $\mathbf{\tilde a}$ and $\mathbf{\tilde b}$ are linearly independent. $A$ and $B$ both belong to a plane passing through the viewpoint. They have a single actual intersection point but, unlike the case 13, their images are parts of the same line except for the extreme cases described in 31, 32.
          2. $\mathbf{\tilde a}$ and $\mathbf{\tilde b}$ are linearly dependent. It means $A \parallel B$. The only time you may want to determine their precedence is when one line completely obscures the other. It is possible only if $\mathring{\mathbf a}, \mathring{\mathbf b}, \mathbf{\tilde a}$ are linearly dependent. In this case you can put $p=0$ in $(1)$ and solve it for $\lambda$ and $q$. If $A$ not passes through the viewpoint, this system of 3 equations with 2 unknowns has a unique solution. Examine $\lambda$ as described in the items 1-2 above, except that $\lambda = 1$ will mean $A=B$ in this case.

Remark 1. You may also want to determine the on-screen relationship between $A$ and $B$ when one or both of them is a segment or a ray, i.e. to know whether they really have a visual intersection from the current point of view. For this, you need to solve $(1)$ instead of merely calculating and comparing determinants as described above. After that, compare $p$ and $q$ with $0$ and $1$ depending on at which point the corresponding line is bounded. For example, if $A$ is a ray from $(x_1^A, y_1^A, z_1^A)$ and $B$ is a segment, then $A$ and $B$ visually intersect if and only if $0 \le p$ and $0 \le q \le 1$.

In addition, you may want to introduce the eyeline (direction of sight) vector $\mathbf d =(x^D, y^D, z^D)$ to determine whether the visual intersection point, if exist, is in front of you or behind. Let $\mathbf c$ be the vector from both sides of $(1)$ with found $\lambda, p, q$ substituted. Check for $\mathbf c \cdot \mathbf d > 0$ for the point to be in front of you.

Remark 2. The test image added to the question body and complications involved made me take a closer look at the item 3321 which is what we're exactly dealing with in this case. I've said that you're unlikely to determine the visual precedence in general description of the branch 33, and that is true because I've answered a question about lines. Thus, if you continue two visually overlapping segments on the picture beyond their common point, the line on screen will switch its color and there is no "front" line. But if you actually need to determine the precedence of segments or rays (as in this case), then take into account first part of Remark 1 and combine it with the method described in the item 3322 making a slight modification. Just put, say, $p = 0.5$ in $(1)$ and solve it for $\lambda, q$ to determine which segment or ray is closer.

Remark 3. One might be tempted to apply the following method of 3D drawing. Take all segments/rays/lines to be drawn, sort them using some sort method utilizing the above (or anyone other's) algorithm as a subroutine (callback), and draw the lines starting from the "outermost" and finishing with the "closest" one. I must warn against doing this because the visual precedence discussed here is nontransitive and therefore it cannot be used in any kind of sorting. Take, for example, 3 lines: $$A=(2,p,1), \; B=(1,2,q), \; C=(r,1,2), \quad p,q,r \in \mathbb R.$$ Let the viewpoint be at the origin and the eyeline be $(1,1,1)$. Here $$\left[ \begin{array}{c|c|c|c|c|c} \mathring{\mathbf a} & \mathbf{\tilde a} & \mathring{\mathbf b} & \mathbf{\tilde b} & \mathring{\mathbf c} & \mathbf{\tilde c} \end{array} \right]= \begin{bmatrix} 2 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 2 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 2 & 0 \\ \end{bmatrix}.$$ Comparing $A$ and $B$, we get $\Delta_{\;a}^{AB}=2, \Delta_{\;b}^{AB}=1$, so $B \prec A$, where the sign $\prec$ means "in front of". Similarly, $\Delta_{\;b}^{BC}=2, \Delta_{\;c}^{BC}=1$ and $\Delta_{\;a}^{AC}=-1, \Delta_{\;c}^{AC}=-2$. We see that $C \prec B$, but $A \prec C$. This creates nontransitive cycle $B \prec A \prec C \prec B$. Any optimized sorting algorithm would call the comparing subroutine only twice thus making wrong assumption about the third pair. This would eventually lead to rendering artifacts.

However, this remark applies to a "global" comparison only. You may still successfully compare lines "locally", i.e. take a bunch of lines presumably passing through one visual ray (and contributing to one pixel on a screen), give them a total local rank, and draw a pixel according to this rank. You may even use this rank for nearby pixels as it unlikely to change. Moreover, the order between any two lines never changes, so you can prepare a table of pairwise comparisons beforehand and use it during the whole drawing.

$\endgroup$
  • $\begingroup$ Thanks, "John". Just saw your solution and began reading it. Will comment again when I've digested what you wrote. (It's a bit "Hard" to follow, but I'll try not to "Die" doing it:) $\endgroup$ – John Forkosh May 30 '18 at 22:02
  • $\begingroup$ Thanks again, and for suggesting the change of variables such that the system of equations is linear in the unknowns, thereby allowing the "usual" solution. I'm still having a bit of trouble visualizing your interpretations of $\Delta_a\Delta_b$, but I imagine it's correct (the computer will soon demonstrate that one way or another:), and will work on my understanding of it some more. Re your remarks, the programming problem's actually a bit easier. Before writing a pixel, I check whether the current value is background color or not. If it's background, I can just overwrite it. (continued...) $\endgroup$ – John Forkosh May 30 '18 at 23:51
  • $\begingroup$ (...continued) Otherwise, I have to check as you've explained. But since there's a non-background pixel, we explicitly know a visual intersection occured. P.S. Noticing your stackoverflow.se posts, I added one of my test images to the question. Right now it's just unit-testing the quaternion rotations, projections onto the viewing plane, etc. But before finalizing the functional decomposition into objects,methods, I wanted to understand how all the math is going to work, just to make sure I don't box myself into a corner requiring some kludgey spaghetti code work-arounds. $\endgroup$ – John Forkosh May 31 '18 at 0:01
  • $\begingroup$ Thanks for your additional remarks. The "zero" cases probably aren't too important -- rare to begin with, and an occasional "mistake" won't be important (probably not even noticed). I should maybe have mentioned the intended application (at least initially): more or less a game toy-modelling molecular self-assembly. You choose a collection of monopoles/dipoles/multipoles (one or many species together), some force laws/constants, and watch a large number of randomly-placed such objects interact over time. Do they self-assemble into interesting/useful stable configurations? (continued...) $\endgroup$ – John Forkosh Jun 1 '18 at 11:58
  • $\begingroup$ (...continued) So there'll be many lines drawn, though a max of 256 colors (as per gif standard), so some lines will necessarily be the same color (probably, each multipole object "species" will be assigned a different color), and same-colored lines will be "unresolvable" anyway. The objective is just to let you visualize the 3D structure better, since the non-standard shapes probably won't be immediately intuitively recognizable. So a few mistakes probably aren't a problem. (P.S. I changed the sample, and will display a version with your algorithm when it's ready -- probably a week or 2). $\endgroup$ – John Forkosh Jun 1 '18 at 12:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.