Alogorithm/maths behind rendering cross sections?

Discuss interdimensional programming, Java applets and so forth.

Alogorithm/maths behind rendering cross sections?

Postby Secret » Sat Mar 19, 2011 8:10 am

What is the maths behind a program which render 2D cross sections from a 3D model? (or 3D cross sections from a 4D model)
OR how does computers calculate the (n-1)D cross section obtained from a nD model?

when trying to look for the ans in wikipedia and google, there are a lot of stuff (some maths articles and some irrelevant stuff) that I don't know where to look first
Secret
Trionian
 
Posts: 143
Joined: Tue Jul 06, 2010 12:03 pm

Re: Alogorithm/maths behind rendering cross sections?

Postby quickfur » Sat Aug 20, 2011 4:21 am

It depends on what form the input has, i.e., do you have a bunch of vertices, or a bunch of faces, or equations defining the input polyhedron/polytope, etc.. But the main underlying idea is the same: intersect the object with a horizontal plane at some user-given height. How this is calculated depends on the input representation, of course. If you have a bunch of halfspace equations, it's as simple as adding one more equation to it (the plane's equation). For a bunch of vertices, you need to apply some convex hull algorithm to find the faces and edges, and then calculate their intersection with the plane. If the input already has edges (say it's in the form of a graph) then you can just use simple line equations to solve for the points of intersection. (But you'll still have to solve for how those points are connected in the intersection -- probably some kind of convex hull algorithm. If the cross-section is 2D, then a simple "gift-wrapping" algorithm should do it. If it's 3D, then a more involved convex hull algo is required. If you're brave and making 4D cross-sections of objects in 5D or beyond, then you need a full-blown, general convex hull algo to compute the boundaries of the thing.)
quickfur
Pentonian
 
Posts: 2157
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Alogorithm/maths behind rendering cross sections?

Postby ICN5D » Tue Mar 18, 2014 12:59 am

I'm also interested in this, too. I would like to find/develop a program that can do midsection cuts of toratopes. The shape can be programmed in by its parametric equation or surface hypervolume equation. I would like the ability to move and rotate the cross section plane around, and fly through the cut array. I also have zero programming skill in this respect. But, I do have a good feel for how the arrays should look by now. It looked like the one made by Mrrl could work, but I have no idea where to start.
" Usul, we have wormsign the likes of which even God has never seen. " - Stilgar
ICN5D
Tetronian
 
Posts: 656
Joined: Mon Jul 28, 2008 4:25 am
Location: Orlando, FL

Re: Alogorithm/maths behind rendering cross sections?

Postby quickfur » Tue Mar 18, 2014 1:43 am

ICN5D wrote:I'm also interested in this, too. I would like to find/develop a program that can do midsection cuts of toratopes. The shape can be programmed in by its parametric equation or surface hypervolume equation. I would like the ability to move and rotate the cross section plane around, and fly through the cut array. I also have zero programming skill in this respect. But, I do have a good feel for how the arrays should look by now. It looked like the one made by Mrrl could work, but I have no idea where to start.

If you can somehow derive the equation(s) for the toratope you're interested in, then the equation(s) for the cross-sections are trivially derived by setting one or more coordinates to a constant value. For example, a sphere has equation x^2 + y^2 + z^2 = r^2. So to find its cross-section with the z=1 plane, you just substitute z=1 and obtain: x^2 + y^2 + 1^2 = r^2, which simplifies to: x^2 + y^2 = r^2 - 1, the form of which indicates that the cross-section is a circle. Of course, this is a trivial example; interesting toratopes will have more complex equations and produce different cross-section shapes.

P.S. Generally I'd expect toratope analysis to be primarily driven by equations, because most of the interesting toratopes have no vertices, so convex hull based approaches like I described in the previous post don't work very well. You could use vertex-based approaches if you use polytopic approximations of the toratopes, but then you'll have to make sure the approximations used are sufficiently fined-grain to yield correct results, and to yield results to the desired accuracy.
quickfur
Pentonian
 
Posts: 2157
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Alogorithm/maths behind rendering cross sections?

Postby ICN5D » Tue Mar 18, 2014 3:32 am

Well, the beautiful thing about the toratope notation is that is reflects the equations! So, every one of the equations can be derived through a formulaic conversion. Also, the cut algorithm works by removing a marker, or " I " , to make a cross section. This also happily reflects the actual method of doing so, as you describe. So, in theory, I ought to be able to do this up pretty simple. I am interested in equation-only input, no approximation. It would be wayyyy easier. I have seen a few 9D shapes recently, and I thought it would be cool to see them in action!
" Usul, we have wormsign the likes of which even God has never seen. " - Stilgar
ICN5D
Tetronian
 
Posts: 656
Joined: Mon Jul 28, 2008 4:25 am
Location: Orlando, FL

Re: Alogorithm/maths behind rendering cross sections?

Postby ICN5D » Tue Mar 18, 2014 8:11 pm

So, this sounds pretty straightforward. Where do I find a program that can do this?
" Usul, we have wormsign the likes of which even God has never seen. " - Stilgar
ICN5D
Tetronian
 
Posts: 656
Joined: Mon Jul 28, 2008 4:25 am
Location: Orlando, FL

Re: Alogorithm/maths behind rendering cross sections?

Postby quickfur » Tue Mar 18, 2014 9:41 pm

ICN5D wrote:So, this sounds pretty straightforward. Where do I find a program that can do this?

Straightforward?? :o :lol: :lol:

It's only straightforward with the simplest of equations, and the simplest of slices! Once you get into more complex (i.e., interesting) toratopes, you start getting things with high-degree polynomials, and once you start doing oblique slices, the equations will turn hairy. Very hairy. For example, the equation for a plain ole innocent 3D torus requires a degree-4 polynomial. While innocent enough when you're dealing with axis-aligned slices, it quickly turns very hairy with oblique slices... or, for that matter, when trying to solve for the intersection of a ray with a torus (e.g., done in ray-tracing or when you want to calculate projections), since you have to solve a quartic polynomial. And consider yourself lucky that it's "only" degree-4, since if you go any higher than that, then there is in general no solution to the equations in the form of +, -, *, /, and n-th root extraction. You'll need to start using heavy-duty weapons like hyperradical functions to deal with those things.

Unless, of course, you're content with axis-aligned slicing and non-analytic (i.e. numerical) solutions, then it's just a matter of choosing some value for some of the coordinates, and substituting it into the equations and seeing what comes out. You could use povray's isosurface feature to help with doing renderings of the resulting equations -- IIRC, it uses Newton's method to solve high-order polynomials so that at least something will come out when you throw something like a 5th degree polynomial at it. Good luck if you're trying to do algebraic analysis on 5th degree (or higher) polynomials, though... I don't recommend attempting that at home; your brain may catch fire. :P
quickfur
Pentonian
 
Posts: 2157
Jo