« first day (2641 days earlier)      last day (581 days later) » 

1:49 PM
My first answer with 100 upvotes on SO.
2
 
 
3 hours later…
 
2 hours later…
6:27 PM
Congrats! Gold badge!
 
 
1 hour later…
7:52 PM
@AnderBiguri (I guess you're the most likely to have done this) Do you know how to draw a polyhedron in a 3D image? I know how to do this in 2D, but the 3D case baffles me, there's no simple order to the vertices in 3D!
 
8:20 PM
@CrisLuengo what language?
And what do you mean by "simple order"?
And what's a "3D image"?
 
8:39 PM
@AndrasDeak--СлаваУкраїні A 3D image is an image that has thee dimensions. The pixel grid extends along x, y and z. Ander does a lot of stuff with 3D images, with all the CT reconstruction he does.
 
I know, I'd still like to know your premise :P
I guess I should've also asked 'What's "draw"?'
 
@AndrasDeak--СлаваУкраїні In 2D, the polygon vertices you can enumerate in order. It's a list. In 3D there's no single, unique order you can visit the vertices.
@AndrasDeak--СлаваУкраїні Anyone!
@AndrasDeak--СлаваУкраїні At a minimum, turn on pixels inside the polyhedron, turn them off outside.
 
@CrisLuengo yeah, but do you need that? What you need is to enumerate the faces one by one (each a polygon). And perhaps each in an order so that their orientation is consistent.
@CrisLuengo ah, I see
I'd try to build the polyhedron from the intersection of semispaces(?), assuming it's convex
solutions to a linear optimization problem
 
@AndrasDeak--СлаваУкраїні True. But how do you quickly find the face at the opposite end of the line? If you have a line of pixels (along any axis) through the shape, you need to quickly find the first and last pixel that you should turn on. In 2D you can do this by enumerating the edges that go up, and those that go down, in order of y coordinate. You then traverse both lists to find the start and end point for each line of the image.
@AndrasDeak--СлаваУкраїні ...and that's why I asked Ander!!! :D
 
@CrisLuengo yeah, I'm not sure that enumerating faces is the right approach in higher dimensions
 
8:44 PM
Just kidding. But there must be some simple algorithm that allows you do to this.
 
it's integer point containment in a polyhedron, so probably, yeah
 
Doing an in/out test for each pixel is just too expensive.
 
but in a vectorized language having n bool masks for n faces would probably be faster
 
Yeah, that's possible...
 
you should probably triangulate the faces (unless they are already triangles) and then the hardest part is figuring out the orientation of each face
if it's convex then it's easy: orient normals toward the mean
 
8:47 PM
Actually, yes, this would be the output of a convex hull computation. So we can expect convexity.
 
Does the algo only give you a bag of points? If it gives you faces, odds are it's already ordered in a sane way.
scipy's spatial.convex_hull uses Qhull which I'm pretty sure can also cook you dinner qhull.org/html/qconvex.htm
> i: list vertices for each facet. The first line is the number of facets. The remaining lines list the vertices for each facet. The facets are oriented. In 4-d and higher, triangulate non-simplicial facets by adding an extra point.
(emphasis mine)
you can also query hyperplanes which sound very useful for bool masks
 
I was looking at this one: doc.cgal.org/latest/Convex_hull_3/index.html -- I can't make much sense of these data structures, but I presume it provides faces and not just vertices. And the faces likely are oriented as well. I mean, it makes sense to provide that information, they get it out of the quickhull algorithm anyway.
4D faces? What does that look like? ;)
 
polyhedra
but surely you know that :P
given my own familiar tools I'd go for scipy with hyperplane querying, assuming Qhull can return the results in some semi-sane format
 
Could you build a 4D face, to show me what it looks like? But don't make a 3D projection of it, that's lame...
 
If the face is 4d, then no. But "in 4-d and higher" includes 4d polytopes with 3d faces :P
 
9:06 PM
Of course. <facepalm>
 
9:18 PM
@CrisLuengo So, is the polyhedron convex? If so, there's this File Exchange function (I haven't tried it)
Ah, it seems that function works in the non-convex case
 
9:32 PM
import numpy as np
from scipy.spatial import ConvexHull

nx, ny, nz = 40, 50, 60
grid = np.mgrid[:nx, :ny, :nz]  # shape (3, nx, ny, nz)

points = np.array([
    [     0,      0,      0],
    [nx - 1, ny - 1,      0],
    [     0, ny - 1, nz - 1],
    [nx - 1,      0, nz - 1],
])
hyperplanes = ConvexHull(points).equations

img = np.ones((nx, ny, nz), dtype=bool)
for *normal, offset in hyperplanes:
    inside = np.einsum('i, ixyz -> xyz', normal, grid) <= -offset
    img &= inside
img = img.astype(np.uint8)
^ the img array thresholded at 0.5 value
 
9:49 PM
@AndrasDeak--СлаваУкраїні Neat! That's quite compact, thanks!
 
no problem, I hope it works out at least for prototyping
if you'd be using it in production you'd want to replace that einsum call with a reshape -> matmul -> reshape trip I think
(I'd have to time it)
 
@LuisMendo Now that's a complicated function. That's more in line with what I expected in terms of complexity. But it makes sense that things are so much simpler for the convex case.
 
I don't even know how I'd do this naively for concave polyhedra. Probably try to break it up into convex ones using some heuristics.
or go all-in with computing winding numbers, but that sounds exhausting
Yeah, with lots of memory or CPU time you could compute the solid angles from each query point to every face and sum them up. If you get 4 pi you're inside. I think...
but no, that's containment for convex polyhedra
 
still works if you use signed solid angles
 
yeah but that starts being messy
 
9:58 PM
not much messier than unsigned ones:)
 
but you'll have to end up with some kind of topological number anyway
@flawr you need well-defined orientations which might not readily be available for a general closed surface, right?
 
@AndrasDeak--СлаваУкраїні as long as the surface is orientable (which it is in the case of polyhedra) it is not an issue
 
I'm thinking it would be easier to draw a line from some point outside the polyhedron to your test point, and see how many faces your line intersects. Maybe more expensive, but simpler conceptually.
 
@flawr it would be for my naive midnight implementation :P
 
@CrisLuengo I'm not sure, but intuitively if you have some kind of nice spatial tree structure over the faces this might be quite efficient I think
 
10:01 PM
@CrisLuengo hmm, yeah, that sounds good (naivity-wise)
 
@flawr something like an R*-tree, I guess. But it's not really efficient if you can't reuse the results for one pixel to compute the test for the one next to it.
 
I've also used data structures that store the neighbourhoods of the triangles which might help
 
Marching cubes/flying edges?
no, that would work the other way around
 
The function that Luis linked (mathworks.com/matlabcentral/fileexchange/…) uses the ray/faces intersection method. It draws a ray straight up from each query point, so for each (x,y) coordinate it needs to find all faces that cover that point. Then it determines, for all points with the shared (x,y) coordinate, if they're above or below each of those faces. So it does re-use some of the work.
I think it should be possible to reuse more of it.
 
That sounds a lot like drawing triangles on the screen: Let's say the (x,y) plane is the screen: Then you could introduce a two depth buffers, one for the closest and the farthest triangle intersection. (This only works for convex polyhedra, or polyhedra that have at most 2 line intersections in z direction.)
After rasterizing all triangles to the (x,y) plane that way, you have the start and end z-coordinates in these two buffers.
(I'm just borrowing the terms from computer graphics here.)
(In traditional computer graphics you might have only one depth-buffer that records the closest triangle, to be able to compute whether the next triangle is over or under an already recorded triangle, that is, to determine whether we have to update the actual frame buffer at that position.)
Does that make sense?
Another maybe stupid idea: You could also voxelize the triangles using the 3d-bresenham generalization, and then floodfill the interior.
 
10:17 PM
yeah, that's the marching cubes angle
that probably only works for the convex case
At least you need to have a "known inside" point for floodfill, right? Which is only trivial for convex polyhedra.
 
I think that should work for all finite polyhedra.
 
Isn't floodfill basically BFS until you hit the wall?
 
@AndrasDeak--СлаваУкраїні That you' could do by the ray/counting line intersection method Cris mentioned.
 
any kind of nearest-neighbour graph traversal for that matter
 
Right, the order doesn't matter!
 

« first day (2641 days earlier)      last day (581 days later) »