StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>First off, you probably meant <code>and</code> rather than <code>or</code> in your if-condition, otherwise it'll just always return true. Second, if you're just testing whether there is an intersection or not, you can do it faster (without the float-division):</p> <ul> <li>You can determine which "side" of each plane any given point is on using vector math:<br> <code>side = dot(my_point - plane_point, plane_normal)</code><br> Now if <code>side</code> is positive, <code>my_point</code> is "in front of" the plane (i.e. it's on the side the normal is pointing towards); if negative, it's "behind" the plane. If <code>side</code> is zero, your point lies on the plane. </li> <li><p>You can check whether your segment intersects an (infinite) plane by just testing to see if the start point and end point are on different sides:</p> <blockquote> <pre><code>start_side = dot(seg_start - plane_point, plane_normal) end_side = dot(seg_end - plane_point, plane_normal) return start_side * end_side #if < 0, both points lie on different sides, hence intersection #if = 0, at least one point lies on the plane #if > 0, both points lie on the same side, i.e. no intersection </code></pre> </blockquote></li> <li><p>You can use the "side" check to do the axis-aligned-cuboid intersection too (actually, this will work for any parallelpiped): </p> <ul> <li>Treat your box as a set of six planes</li> <li>Make sure the plane normals are all pointing either "outwards" or "inwards" from the box. I'll assume you're using "outwards"</li> <li>For any point to lie inside your box, it has to be "behind" <em>all six planes</em>. If it isn't, it lies outside the box.</li> <li><strike>For any segment to intersect the box, one point has to lie outside it and one inside.</strike></li> <li>That's all! </li> </ul></li> </ul> <p><strong>edit:</strong> The last point is actually incorrect; as you say, voxels can be intersected even if both endpoints lie outside. So it's not the whole solution - actually, you can't really do this without calculating the intersection point. You can, however, still use the "side test" as an <em>early-reject</em> mechanism, so as to cut down on the number of full calculations you need to do: if both points are on the same side of <em>any one</em> of the six planes, there can be no intersection. </p> <p>As far as your specific case goes, it seems like you're trying to find all intersecting voxels for some given line segment? In that case, you'd probably be better served using something like <a href="http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm" rel="nofollow noreferrer">Bresenham's</a> to explicitly calculate the path, instead of testing for intersections against all of the voxels...</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload