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: 162
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: 2935
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.
It is by will alone, I set my donuts in motion
ICN5D
Pentonian
 
Posts: 1135
Joined: Mon Jul 28, 2008 4:25 am
Location: the Land of Flowers

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: 2935
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!
It is by will alone, I set my donuts in motion
ICN5D
Pentonian
 
Posts: 1135
Joined: Mon Jul 28, 2008 4:25 am
Location: the Land of Flowers

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?
It is by will alone, I set my donuts in motion
ICN5D
Pentonian
 
Posts: 1135
Joined: Mon Jul 28, 2008 4:25 am
Location: the Land of Flowers

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: 2935
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 11:42 pm

Well, it is straightforward, relatively speaking :) It took me only two months to learn Marek's cut algorithm, thus allowing me to visualize 9D toratopes, no joke. Those things are no longer scary impossible complex any more. I'll be resorting to axial cuts initially, but a challenging goal would be the oblique cuts. If the rendering program has an ability to adjust the angle and depth of the slicing n-plane, then obliques and merge animations aren't so hard. This part may require some programming cleverness. I'd like to make cut rotation animations, going from one cross section to another by rotating the cut-plane. The toratope cut algorithm is golden in this respect. It's doing the same exact math, in a long division context on paper. High order polynomials don't frighten me one bit. If there's patterns to be found, I will find them, and master them. I'm exceedingly proficient at that part :)


EDIT: Okay, downloaded POVray. I have NO idea how to use this thing. It looks like it only accepts software code. Hmm, can it do plain old equations without all the other stuff? I certainly hope so!
It is by will alone, I set my donuts in motion
ICN5D
Pentonian
 
Posts: 1135
Joined: Mon Jul 28, 2008 4:25 am
Location: the Land of Flowers

Re: Alogorithm/maths behind rendering cross sections?

Postby quickfur » Wed Mar 19, 2014 5:27 am

I'm quite certain you're not afraid of high-order polynomials, but the question is, should you be? :P

They're (relatively) tame up to degree 4, where if the polynomial has any solution at all, it can be expressed in terms of +, -, *, /, and the n-th root operation (square root, cube root, fourth root, etc.). The trouble is, while it may seem at first glance that this simple pattern should hold for polynomials of any degree, it's a proven fact that from degree 5 onwards, only a subset of polynomials will have a solution of this form; there will be some polynomials for which the solution cannot be expressed in terms of +, -, *, /, and the n-th root operation. This is bad news, because it means that algebraic analysis will be hampered by the fact that there is no way to write down the value of the root, except implicitly as the solution to a degree ≥5 polynomial. Which sux if that's the polynomial you're trying to solve in the first place! In order to get around this, you will have to resort to heavy weaponry like the hyperradical functions, which are not so nice because they're now opaque functions that you can't manipulate as easily as simple algebraic expressions. Well, you still can, but things will no longer be so nice.

Furthermore, even if your initial polynomial is relatively tame (e.g., x^2 + y^2 = r^2, sweet and simple), as soon as you start doing oblique sections or ray-tracing, all sorts of complicated terms will start crawling out of the woodwork, and your equation quickly grows into something like 5*x^2 + 1/2*y^2 - 14*x + 7*y - 2*x*y + r^2 + ... = 0. For this particular example, it's not so bad: everything is quadratic, and when things get unruly, we just pull out the quadratic formula hammer and smash it open. The resulting root values may look ugly with ± and √ sprinkled everywhere, but it works. It's a totally different story when you start dealing with degree-5 polynomials. For example, even the relatively tame-looking x^5 - x + 1 = 0 has a solution that cannot be written in terms of +, -, *, /, and n-th root extraction. (You're welcome to try it if you don't believe me. :P) Not to mention what happens when you start inserting plane equations into it (to compute the intersection with an oblique plane); then all the x^5, x^4, x^3, x^2, and x terms will start crawling out, and basically the only thing you can do at this point is just to use Newton's method to brute-force a numerical solution out of it, or bring out the really big guns like the hyperradical functions (which, being big guns, are beasts to handle).

That's only the beginning of it, though. You may think that as long as you stay with low-degree polynomials, you're safe, but that's not true if you have more than one simultaneous equation. What starts out as a pair of innocent quadratic equations, say x^2 + y = 0, and x = z^2 - y^2, once you try solving them, you discover that suddenly you have a degree-4 polynomial on your hands. Add a few more variables and (quadratic) equations to the mix, and you may find yourself grappling with a degree-5 (or higher) polynomial pretty quickly. Worse, it's been shown that any system of polynomials (of arbitrary degree) can be reduced to a system of quadratics by adding more variables (of the form x = y^2), or, to put it another way, that a system of quadratic equations is potentially equivalent to a system of degree-n polynomials where n can be arbitrarily large, like 100. And then you're back to choosing between Newton's method (numerical approximation) or hyperradical functions (all-round nastiness when you're trying to manipulate them algebraically).

So you could say, let's resort to numerical methods instead of dealing with these crazy hyperradicals, which is perfectly fine, except that numerical methods suffer from locality, that is, without knowing beforehand the analytical properties of the polynomial, you may not know where to fix the starting point of the algorithm, and so it may get stuck in a local minimum/maximum and not be able to find the root you're looking for. Newton's method suffers from this if you don't give it a "good" starting point.

All this is important because while povray does have the powerful isosurface primitive, which lets you use almost any arbitrary equation to define your shapes (which lends itself rather conveniently to what you want, since the toratopic equations are easily derived from their symbolic representation), the way povray implements this in the back-end is via numerical methods like Newton's method. So if you give it a particularly pathological equation, it may suffer from getting "stuck" in local minima, thus not finding the root(s) it's supposed to, which in turn causes the output to have visual artifacts (like missing patches of surface where they're supposed to be there). You also run the risk of numerical overflow/underflow/catastrophic roundoff error, which can introduce strange-looking geometric artifacts in your isosurface like holes or "spikes" that vanish/appear when you move the camera, because they aren't really there analytically, they're just artifacts of the limitations of numerical methods.

But having said all that, generally numerical methods do work rather well, so unless you're dealing with particularly pathological shapes, you shouldn't run into any big problems. But you should be aware that problems sometimes do crop up, so when it happens, just remember that you've been warned. :P
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Alogorithm/maths behind rendering cross sections?

Postby ICN5D » Wed Mar 19, 2014 3:18 pm

Okay, no oblique cuts for now. I'm happy with midsection cuts. So, I guess what I'm looking for, to jump into playing around with it, is a premade fully functional template of code that sets up the camera, lightsource, and math operator equation in it. Then, I can play around and modify it to see how it works. I'm afraid I still don't know how to use it at all, though. I can press the run button, and I see it runs the code in the text field. One thing I've been thinking about is how to render the merge sequences. It seems like I can translate the midpoint of the shape with respect to the cross-cut plane, but I'm not sure it can work that way.
It is by will alone, I set my donuts in motion
ICN5D
Pentonian
 
Posts: 1135
Joined: Mon Jul 28, 2008 4:25 am
Location: the Land of Flowers

Re: Alogorithm/maths behind rendering cross sections?

Postby quickfur » Wed Mar 19, 2014 6:28 pm

ICN5D wrote:Okay, no oblique cuts for now. I'm happy with midsection cuts. So, I guess what I'm looking for, to jump into playing around with it, is a premade fully functional template of code that sets up the camera, lightsource, and math operator equation in it. Then, I can play around and modify it to see how it works. I'm afraid I still don't know how to use it at all, though. I can press the run button, and I see it runs the code in the text field. One thing I've been thinking about is how to render the merge sequences. It seems like I can translate the midpoint of the shape with respect to the cross-cut plane, but I'm not sure it can work that way.

Keep in mind that povray is a 3D rendering program, and although it has some hacks to deal with 4D and 5D vectors, those are not fully supported and only have very limited operations available. So if you're going to be using it, you'll have to first reduce your equations to 3 variables first, otherwise you'll have a hard time coaxing it to do what you want. :) IOW, you're gonna hafta do some manual work in massaging your equations to fit into povray's 3D model. Fortunately, the scripting language is powerful enough that you might very well get away with automating most of this work.

But I think we're getting way ahead of ourselves. First, you should learn how to use the thing and get some feel for how it works. :) For this, I highly recommend following through the povray tutorial, especially the "Getting Started" section. Also, don't just read through it; actually try out the examples and fiddle with the scripts yourself so that you understand what's going on. Yes, I know most of this stuff is probably boring to you, since it's mostly talking about setting up boring ole 3D objects, lighting effects, and stuff, but bear with it, you'll be glad later when you need to make use of some 3D tricks to make things show up nicely in toratope renders.

Once you're finished with the "Getting Started" section and feel reasonably confident in your command of the scripting language, read the "isosurface object" and "poly object" subsections under "Advanced Features". These are some of the most powerful of povray's features, and probably what you'll want to use to render toratopic sections. :) And once you've mastered that one, read the "Making Animations" section, also under "Advanced Features". That's your key to making toratopic slices without needing to manually run povray 50 times. You just program your script to produce a different equation based on the clock variable (hint: set the coordinate you're sectioning along to some function of the clock), then you can just run it with the +k option to specify a slice of any depth you want. You can also make a full-blown animation out of it, by using a periodic function like sin or cos to loop your slices around. (Wouldn't you just love that? :P)
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Alogorithm/maths behind rendering cross sections?

Postby quickfur » Wed Mar 19, 2014 6:34 pm

P.S. Keep in mind that povray basically is using numerical methods to solve polynomial equations, so you can actually coax it to do oblique sectioning if you feel up to it. You just have to figure out a way to express this as a polynomial equation, and then let povray do the rest of the job. The difficulties I talked about earlier mainly come up when you're trying to manually tackle these things or you want to get algebraic solutions out of them; for the purposes of making images, you don't need that (numerical methods are good enough), so as long as you can write out the polynomial equation, povray will take care of the rest.
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Alogorithm/maths behind rendering cross sections?

Postby ICN5D » Thu Mar 20, 2014 12:39 am

All right, finally found the part about the poly equations and functions. You weren't kidding about the complexity. There MUST be another way. I guess the CSG can be used to manually build the cuts, but it would be cheating the system a little bit. Man, this will take some time and learning. I have no idea how to derive those polynomials for the shapes. I didn't see it anywhere, but can POVray use parametric equations? Of course, they would be even more cryptic. Hmm, going to take some time.
It is by will alone, I set my donuts in motion
ICN5D
Pentonian
 
Posts: 1135
Joined: Mon Jul 28, 2008 4:25 am
Location: the Land of Flowers

Re: Alogorithm/maths behind rendering cross sections?

Postby quickfur » Thu Mar 20, 2014 12:59 am

ICN5D wrote:All right, finally found the part about the poly equations and functions. You weren't kidding about the complexity. There MUST be another way. I guess the CSG can be used to manually build the cuts, but it would be cheating the system a little bit. Man, this will take some time and learning. I have no idea how to derive those polynomials for the shapes. I didn't see it anywhere, but can POVray use parametric equations? Of course, they would be even more cryptic. Hmm, going to take some time.

You can only use CSG if you're doing 3D toratopes. For anything higher, you'll have to, essentially, do CSG manually on your toratopic equations. :lol: :nod:

I thought you said you knew how to derive polynomials for the shapes? 'cos if not, you're up polynomial creek without a paddle... :P Povray can't do parametric equations, unfortunately. Not as far as I know, anyway. They may have improved it since I last checked. But probably, you'll have to convert your parametric equations into polynomials. This page may help. Good luck. :P

Another approach might be to manually implement parametric equations in using povray's scene language, by implementing an intersection algorithm that solves said parametric equations for ray-shape intersections. But I'm guessing this is going to be even harder than finding the polynomial form of the equations, because parametric equations don't lend themselves very well to linear intersections. :lol: :(

Or if all else fails, you might want to consider Matlab instead. :o
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Alogorithm/maths behind rendering cross sections?

Postby ICN5D » Thu Mar 20, 2014 3:22 am

I thought you said you knew how to derive polynomials for the shapes?


Nope, I said they didn't scare me. But, I probably should be :)

But, other than that, there was some reference to a program that could make the vector arrays. When I checked out the layout of the vector arrays, it wasn't that bad. Just a long way to do it. POVray seems like a cool program, but it also seems kind of primitive when trying to do some real complex math. It's mainly the part with having to convert into a 3D equation. The cut algorithm is doing this too, so I feel that there is some kind of way to directly translate it into an equation. But, maybe a more advanced program designed to handle heavier calculations is what I should find. I have the perfect one in my head, but sadly a lack of programming knowledge. Boy would it be awesome, too. I know exactly how to represent the rest of the shape from the cut, I just need to find a way to illustrate it. Heck, I could draw it way faster than on the computer!


So, before you mentioned something like deriving the equation for a cut, as simple as setting a variable to 0 or 1, like here:

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



This mimics the cut algorithm when we take a sphere (III) = (x^2 + y^2 + z^2) = r^2, and cut it into a circle (IIi) = (x^2 + y^2 + 1^2) = r^2 . Moving along the cut axis " i ", we see the circle shrink, which would be made by increments of the value of 1 in the equation: (x^2 + y^2) = r^2 - 1 . The extra parentheses aren't really necessary, I'm throwing them in there for illustrative purposes.


And, for a torus ((II)I) = ((√(x^2+y^2) − R)^2 + z^2) = r^2 . There are two midsection axial cuts ((I)I) making two circles along a line, and ((II)) making two concentric circles.

((I)I) = ((√(x^2 + 1) − R)^2 + z^2) = r^2 , increase 1 to merge displaced circles into one

((II)) = ((√(x^2 + y^2) − R)^2 + 1) = r^2 , increase 1 to merge concentric circles into one


So, I feel that these equations for the cut arrays can be made through a direct translation into 3D, and what the merge sequence would be. But, wouldn't you wan't to set the cut axis value to zero? As in, (x^2 + y^2 + 0) = r^2 ? Then, of course keeping in mind that the value can be changed when moving out from center. I have yet to try my hand at converting the toratope notation into equations, much less into the 9D ones I've been working with.

So far, I can put these together:


(II) = (x^2 + y^2) = r^2

(III) = (x^2 + y^2 + z^2) = r^2

((II)I) = ((√(x^2+y^2) − R)^2 + z^2) = r^2

(IIII) = (x^2 + y^2 + z^2 + w^2) = r^2

((III)I) = ((√(x^2 + y^2 + z^2) − R)^2 + w^2) = r^2

((II)II) = ((√(x^2 + y^2) − R)^2 + z^2 + w^2) = r2

(((II)I)I) = ((√((√(x^2 + y^2) − ρ)^2 + z^2) − r)^2 + w^2) = R^2

((II)(II)) = ((√(x^2 + y^2) − a)^2 + (√(z^2 + w^2) − b)^2) = r^2


which definitely follows some very strict congruencies between both. By setting any one of the x, y, z, w axes to 0 or 1, the equation for the resulting array of shapes should come out. If a rendering program can take these equations and make cool pictures, and then adjust the values, the complex merge sequence can be made. I'm not so sure about the oblique slices, though. They are pretty cool, but the maths required sound heavy. It's a good challenge, and probably the next step.
It is by will alone, I set my donuts in motion
ICN5D
Pentonian
 
Posts: 1135
Joined: Mon Jul 28, 2008 4:25 am
Location: the Land of Flowers

Re: Alogorithm/maths behind rendering cross sections?

Postby quickfur » Thu Mar 20, 2014 5:32 am

ICN5D wrote:
I thought you said you knew how to derive polynomials for the shapes?


Nope, I said they didn't scare me. But, I probably should be :)

Perhaps they should. :P

But, other than that, there was some reference to a program that could make the vector arrays. When I checked out the layout of the vector arrays, it wasn't that bad. Just a long way to do it. POVray seems like a cool program, but it also seems kind of primitive when trying to do some real complex math. It's mainly the part with having to convert into a 3D equation.

And the part about it being a 3D ray-tracing program, not Matlab... :roll:

The cut algorithm is doing this too, so I feel that there is some kind of way to directly translate it into an equation. But, maybe a more advanced program designed to handle heavier calculations is what I should find. I have the perfect one in my head, but sadly a lack of programming knowledge. Boy would it be awesome, too. I know exactly how to represent the rest of the shape from the cut, I just need to find a way to illustrate it. Heck, I could draw it way faster than on the computer!

Last I heard, Matlab had a built-in graphing function... but with the caveat, of course, that it has to be 3D or less, since most people don't do things like visualize 4D or higher in their free time, so such a feature would be rather rare! :roll: :P

So, before you mentioned something like deriving the equation for a cut, as simple as setting a variable to 0 or 1, like here:

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


This mimics the cut algorithm when we take a sphere (III) = (x^2 + y^2 + z^2) = r^2, and cut it into a circle (IIi) = (x^2 + y^2 + 1^2) = r^2 . Moving along the cut axis " i ", we see the circle shrink, which would be made by increments of the value of 1 in the equation: (x^2 + y^2) = r^2 - 1 . The extra parentheses aren't really necessary, I'm throwing them in there for illustrative purposes.

I didn't say 0 or 1, it can be any constant value. By varying the value, you get different cuts. Let's take something other than a sphere for example, since spheres are so boring. What about a cylinder? We can describe its surface as x^2 + y^2 = r^2, with the additional constraint -1 < z < 1 for the end caps. So let's say we cut it at z = 0. What do we get? Well, we substitute z=0 into x^2 + y^2 = r^2, but since z doesn't occur there, the result is still x^2 + y^2 = r^2, i.e., a circle of radius r. This holds for every z between -1 and 1. When z is outside this range, then the section is empty, because our constraint -1 < z < 1 stipulates that the equation x^2 + y^2 = r^2 only holds for that particular range of z values. What about a vertical cut? Say x = 0. So we get: 0 + y^2 = r^2, or y^2 = r^2, which means y = ±r. This gives us a pair of lines. And of course, we always have to take care of the constraint that z must be between -1 and 1, so taken together, this gives us a rectangular section. Suppose we move the cut to x = 1. Then we get 1^2 + y^2 = r^2, which rearranges to y^2 = r^2 - 1, meaning that y = ±√(r^2 - 1). Again taking the constraints on z into account, this gives us a rectangle: but a narrower one now, since √(r^2 - 1) < r. Notice also, that if we move the cut to x = r+1, then we get (r^2 + 2r + 1) + y^2 = r^2, which rearranges to y^2 = r^2 - r^2 - 2r -1 = -2r - 1. Notice that y^2 is negative, which means y has no real solutions. This means the intersection is empty: the cutting plane falls past the cylinder and doesn't intersect it at all.

All of this is boring, of course. Let's do an oblique cut. We may specify an oblique cutting plane by choosing a normal vector N, say N = (1,2,3), and for simplicity let's say the plane passes through the origin. This gives us the plane equation x + 2y + 3z = 0. To find the intersection, then, involves solving the following system of equations:
Code: Select all
x^2 + y^2 = r^2
x + 2y + 3z = 0
-1 < z < 1

One way to solve this, is to rearrange the plane equation into x = -2y - 3z, and then substitute that into the first equation in order to eliminate x from it. So we get (-2y-3z)^2 + y^2 = r^2, which expands to 4y^2 + 6yz + 9z^2 + y^2 = r^2, and rearranges to 5y^2 + 6yz + 9z^2 = r^2. This is the equation of an ellipse (since x doesn't occur in it anymore). There are some further algebraic tricks you can use to rewrite this into canonical form Ap^2 + Bq^2 = R^2, for some A, B, and R, but we won't do that here (you could do that as a practice exercise :P :D). Now we apply the constraint -1 < z < 1, which (probably) will truncate the ellipse somewhat, so the resulting cross-section is some manner of truncated ellipse.

So this should give you some taste of what's involved in doing oblique cuts. :P As you can see, introducing the cutting plane's equation into the system causes the innocent-looking x^2 + y^2 = r^2 to explode into some complicated-looking quadratic equation. In general, this is what happens when you do oblique cuts. So imagine what happens when you take a torus, which has a degree-4 polynomial equation, and stick a cutting plane's equation into it: it explodes into some general-form 4th degree polynomial equation, the solutions of which will be very non-obvious as to what kind of shape they represent. :) And when you attempt this on a 5th degree or higher polynomial, you run the risk of getting an unsolvable 5th degree polynomial (as in, the solutions require heavy-duty weaponry like hyperradical functions).

Solving this sort of thing requires some pretty heavy-duty algebraic algorithms (probably some application of the calculus of variations), which require an internal algebraic representation of the equations -- most software don't bother with this level of complexity! The only ones that do are the ones designed to do heavy-duty math -- Matlab, for example. But then Matlab only has limited visualization capabilities (last I checked, but I could be wrong), so you still need to convert the final solution forms into some kind of 2D or 3D representation in order for it to be render-able to the screen.

And, for a torus ((II)I) = ((√(x^2+y^2) − R)^2 + z^2) = r^2 . There are two midsection axial cuts ((I)I) making two circles along a line, and ((II)) making two concentric circles.

((I)I) = ((√(x^2 + 1) − R)^2 + z^2) = r^2 , increase 1 to merge displaced circles into one

((II)) = ((√(x^2 + y^2) − R)^2 + 1) = r^2 , increase 1 to merge concentric circles into one


So, I feel that these equations for the cut arrays can be made through a direct translation into 3D, and what the merge sequence would be. But, wouldn't you wan't to set the cut axis value to zero? As in, (x^2 + y^2 + 0) = r^2 ? Then, of course keeping in mind that the value can be changed when moving out from center. I have yet to try my hand at converting the toratope notation into equations, much less into the 9D ones I've been working with.

The variable along the cut axis can take on any value you want. The form of the resulting equations will tell you what shape the cut has, as I illustrated above. It's just that 0 is a convenient value for getting results that have a simple-enough form for you to be able to tell what it represents. :P I mean, if you see something like 3x^4 - 13x^3 + 2x^2 - 20x + 20xy - 15y^2 + (1/2)y^3, how would you even know what shape it has? And mind you, that's only with two variables. In 9D you have nine variables, and a complex toratope may have an equation form with a degree 8 polynomial, say, so after sticking in your cutting plane's equations, you get this insane-looking 8th degree polynomial with 9 variables appearing in all sorts of combinations, x^9, x^4y^2z, w^2x^4y^3, etc., just to name a few, in who knows how many terms, where would one even begin to understand what sort of shape it's describing?

It's only that the axial cuts have (relatively) tame-looking forms that we have any hope of even understanding what it describes. :P

So far, I can put these together:


(II) = (x^2 + y^2) = r^2

(III) = (x^2 + y^2 + z^2) = r^2

((II)I) = ((√(x^2+y^2) − R)^2 + z^2) = r^2

(IIII) = (x^2 + y^2 + z^2 + w^2) = r^2

((III)I) = ((√(x^2 + y^2 + z^2) − R)^2 + w^2) = r^2

((II)II) = ((√(x^2 + y^2) − R)^2 + z^2 + w^2) = r2

(((II)I)I) = ((√((√(x^2 + y^2) − ρ)^2 + z^2) − r)^2 + w^2) = R^2

((II)(II)) = ((√(x^2 + y^2) − a)^2 + (√(z^2 + w^2) − b)^2) = r^2


which definitely follows some very strict congruencies between both. By setting any one of the x, y, z, w axes to 0 or 1, the equation for the resulting array of shapes should come out. If a rendering program can take these equations and make cool pictures, and then adjust the values, the complex merge sequence can be made. I'm not so sure about the oblique slices, though. They are pretty cool, but the maths required sound heavy. It's a good challenge, and probably the next step.

Did you go through the povray tutorial? 'cos you really should. I mean it. Like, actually do each of the suggested exercises. It may sound boring, but it's worth the time to learn. Some of your equations above are very easy to turn into povray animations, if you only knew how to make povray sing to your tune. Cool pictures take effort to produce; we don't just plug numbers into a magic box and get nice pictures out of them. :lol: The images on my website, for example, are individually built and colored -- not from scratch, of course, but an automated image generator would have produced images of far inferior quality. The program helps with automating the nitty-gritty details, but you still have to individually compose each image sequence. There's no free lunch here; what you get depends on what you put into it. :P
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Alogorithm/maths behind rendering cross sections?

Postby ICN5D » Thu Mar 20, 2014 6:35 am

Actually, I'm going to blow your mind on that note. I did some internet snooping around, and found a cool 3D calculus rendering program. It has an implicit equation input field. It also has 4 adjustable and animated variables. So, I experimented with plugging in the torus equation, and modifying it in its cut form. The shapes I got were cassini oval deforming circles, in the form of two hollow tubes. The circle-cuts of the tubes were the actual cross sections of a torus, and when animated, produced the real result. Then, I played with a 4D toratope, the torisphere. I modified it into it's 3D cut form by changing

((III)I) = (sqrt(x^2 + y^2 + z^2) − R)^2 + w^2 = r^2

into its 3D cut equation

(sqrt(x^2 + y^2 + A^2) - R)^2 + z^2 = r^2


where the variable " A " is the cut axis, and Z is in place of W.

The end result was a torus when a=0, but when animating " A " , I saw the cut sequence of a torisphere in motion for the first time ever! It was mind blowing at how easy it was. I can derive the 3D equation for any cut, and apply adjustable parameters to the removed cut axes. The animation feature lets you fly through the shape, exploring other cuts and merge sequences. It can have up to 4 parameters, which allows for a full 7D shape to be animated. Higher than that will require manual adjustments, no big deal. There's a lot of potential in this little program, I can feel it. Not to mention your little schooling on oblique cuts just got my attention. I was wondering how it was done with equations. That's very cool at how it works. I'm going to study up on that, because I know I can make them and put it into this new program.


The 3D calc rendering program:

http://web.monroecc.edu/manila/webfiles ... Plot3D.htm


Go to :
- Graph
- Add Implicit Surface

Copy-paste into the equation field:
(sqrt(x^2 + y^2 + a^2) - 2.5)^2 + z^2 = -0.5^2

Go to:
- Parameters
- Adjust parameters
- Range tab
-- change " A " to -3 > A > 3

-In the parameters box, you have to check the box at the right of the slider for " A "

-Click Animate Parameter, and watch the cut evolution of moving up and down through a torisphere :)


I did take a look at the POVray tutorial, but I went searching for an easier way, as you can tell. I think this program is an awesome find, and I'm going to pursue it. I can catalog all of the equations and parameter fields. Learning how to derive oblique equations will be the next decent challenge and expansion to my mind. Then, I can make oblique animations as well! For now, I will be experimenting with deriving the 3D equations and parameters. It's going to be fun :)
It is by will alone, I set my donuts in motion
ICN5D
Pentonian
 
Posts: 1135
Joined: Mon Jul 28, 2008 4:25 am
Location: the Land of Flowers

Re: Alogorithm/maths behind rendering cross sections?

Postby ICN5D » Thu Mar 20, 2014 7:33 am

Here you go. Check them out. I tested all of them, and they work!!!!!! It's the merges and tiger dances in motion rendered in real time.


Toripshere ((III)I) = (sqrt(x^2 + y^2 + z^2) - R)^2 + w^2 = r^2
----------------------------------------------------------------------------

• ((IIi)I) - torus
--------------------
(sqrt(x^2 + y^2 + a^2) - 2.5)^2 + z^2 = -0.5^2
-3 > a > 3

• ((III)i) - concentric spheres
-------------------------------------
(sqrt(x^2 + y^2 + z^2) - 2.5)^2 + a^2 = -0.5^2
-0.7 > a > 0.7
NEED TO CUT OPEN FOR CONCENTRIC ARRANGEMENT






Spheritorus ((II)II) = (sqrt(x^2 + y^2) - R)^2 + z^2 + w^2 = r2
----------------------------------------------------------------------------

• ((Ii)II) - displaced spheres
-------------------------------------
(sqrt(x^2 + a^2) - 2.5)^2 + y^2 + z^2 = -0.5^2
-3 > a > 3

• ((II)Ii) - torus
--------------------
(sqrt(x^2 + y^2) - 2.5)^2 + z^2 + a^2 = -0.5^2
-0.7 > a > 0.7




Ditorus (((II)I)I) = (sqrt((sqrt(x^2 + y^2) - ρ)^2 + z^2) - r)^2 + w^2 = R^2
-------------------------------------------------------------------------------------------

• (((Ii)I)I) - displaced toruses
-------------------------------------
(sqrt((sqrt(x^2 + a^2) - 2.5)^2 + y^2) - 1)^2 + z^2 = -0.3^2
-4.2 > a > 4.2

• (((II)i)I) - concentric toruses
--------------------------------------
(sqrt((sqrt(x^2 + y^2) - 2.5)^2 + a^2) - 1)^2 + z^2 = -0.3^2
-1.4 > a > 1.4

• (((II)I)i) - cocircular toruses
-------------------------------------
(sqrt((sqrt(x^2 + y^2) - 2.5)^2 + z^2) - 1)^2 + a^2 = -0.3^2
NEED TO CUT OPEN FOR COCIRCULAR ARRANGEMENT





Tiger ((II)(II)) = (sqrt(x^2 + y^2) - Ra)^2 + (sqrt(z^2 + w^2) - Rb)^2 = r^2
--------------------------------------------------------------------------------------------

• ((II)(Ii)) - vertical stack of torii
------------------------------------------
(sqrt(x^2 + y^2) - 2.5)^2 + (sqrt(z^2 + a^2) - 2.5)^2 = -0.5^2
-2.5 > a > 2.5
It is by will alone, I set my donuts in motion
ICN5D
Pentonian
 
Posts: 1135
Joined: Mon Jul 28, 2008 4:25 am
Location: the Land of Flowers

Re: Alogorithm/maths behind rendering cross sections?

Postby ICN5D » Tue Mar 25, 2014 12:17 am

Thanks to Marek, I have a neat little shortcut way to derive oblique cuts. Using sine and cosine, any oblique angle can be described as fractions of pi. This helps with navigating the orientation of the cut plane, since setting a parameter to 3.14 gives a full 360 degree rotation. Then of course, there's the consequence of having multiple 360 rotation directions, made by reducing the shape to lower dimensions multiple times. Each cutting plane can be rotated separately, or simultaneously at different rates. That's what I did with a rotation animation of the (((II)I)(II)), I set both cut axes to rotate at a 3:5 ratio, where the 3-cycle was offset by 180 degrees. Interesting emergent oblique cuts can be found using this method. Lying on these particular angles of the 3-plane, are a host of beautiful structures, some a single object, some several, and some sharing the attributes of combined axial cuts. I'm literally having to explore these shapes with this program, and I discover amazing things and effects, like multiple component symmetries. For once now, I'm exploring real places that aren't in some computer game ( hehe ) :)


Using the equation for a torisphere:

(sqrt(x^2 + y^2 + z^2) - R)^2 + w^2 = r^2

cut down to:

(sqrt(x^2 + y^2 + a^2) - R)^2 + z^2 = r^2

a = slides through 4D when changed


we can then establish a special rotation equation:

(sqrt(x^2 + y^2 + (z*cos(a))^2) - R)^2 + (z*sin(a))^2 = r^2


that will allow you to flip between the torus cut or the two concentric spheres cut. Setting a=0 makes an axial 0 degree cut, a=0.392 makes a 45 degree oblique cut, and a=0.784 makes a 90 degree cut. It's important to place the sine and cosine in different parts of the toratope, or you'll make nothing interetsing. What's really cool is seeing what it looks like to rotate into an empty 3D cut. This is a space where an infinitely sized cube could fit, and never touch the surface. Actually, there's two of these holes in duotorus tiger (((II)I)((II)I)), a shape I've been exploring a lot lately. Made a bunch of cool pics on the tiger explained thread. I see some future potential with this program and my new mathematical tools. It's mindblowing to see a cross section of a hypertorus in 3D.
It is by will alone, I set my donuts in motion
ICN5D
Pentonian
 
Posts: 1135
Joined: Mon Jul 28, 2008 4:25 am
Location: the Land of Flowers


Return to Programming

Who is online

Users browsing this forum: No registered users and 7 guests