Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2007-08-08 10:03:44

luca-deltodesco
Member
Registered: 2006-05-05
Posts: 1,470

rendering polynomial implicit shapes 2D

Ive been thinking, how would one go about rendering an implict 2d polynomial graph?

i.e. lets say i have the function:

f(x,y) = 2x^4 - 3x^2y^2 + 2xy - 4x^2 + 5x^3y + 10x + 2 = 0

is there any simple way of being able to render this?

obviously, since its not in the form y = f(x) or x = f(y) i can't just run through values of x,y joining points together, but i know there must be a way, because ive even seen programs that can take implicit functions in 3 dimensions, and render it as a polygonal mesh of arbitrary complexity

---

maybe this would have been better in coders corner, move if appropriate tongue

Last edited by luca-deltodesco (2007-08-08 10:06:21)


The Beginning Of All Things To End.
The End Of All Things To Come.

Offline

#2 2007-08-08 11:26:48

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,711

Re: rendering polynomial implicit shapes 2D

Ideas off the top of my head:

If you could find one point, say (3,4), you could then try small differences to find the next point, and continue that way following the curve in both directions.

To find the first point you could do a "hill climb" (move in the direction that reduces the error the most), or just a brute-force search dividing the space into (say) 1,000 x 1,000, and then narrowing down further as needed.

Continuous functions would be easiest.


"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Offline

#3 2007-08-08 12:01:44

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: rendering polynomial implicit shapes 2D

You could go about graphing it in 3D, storing only those points which satisfy the requirement = 0.  The important thing when doing this is to build in a "step size" parameter allowing you to get approximations first.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#4 2007-08-08 19:59:32

luca-deltodesco
Member
Registered: 2006-05-05
Posts: 1,470

Re: rendering polynomial implicit shapes 2D

ive figured out a good method that renders the objects perfectly, at arbitrary depth, and works for any implicit function

Basicly: i split the viewing area into equally sized squares.

for each square:

i evaluate the function for each corner, and also whether that point is inside (if the value is less than 0)
if all are inside, or all are outside, i finish here:

then i go through the following 6 cases:

top left is inside ONLY or outside ONLY
top right is inside ONLY or outside ONLY
bottom left is inside ONLY or outside ONLY
bottom right is inside ONLY or outside ONLY
(top is inside AND bottom is outside) OR (top is outside AND bottom is inside)
(left is inside AND right is outside) OR (left is outside AND right is inside)

then for each case, i use the function values to interpolate linearly for where it is assumed f(x,y) would be 0 from the two function values (not perfect, but a good approximation) then same for the other side for whatever case it is, and draw a line.

---------

the red graph is for the square size of 50pixels (pretty terrible)
the green graph is for the square size of 25pixels (not too bad)
the blue graph is for the square size of 10pixels (almost perfect)
the black graph is for teh square size of 5pixels (perfect for all itensive purposes)

----
0.02x³ - 2x² + y² + 2xy - 100 = 0
http://denvish.net/ulf/090807/32088_laser.php
----
20cos(0.08y) - 50sin(0.04x) - 0.004xy= 0
http://denvish.net/ulf/090807/32340_laser.php
----


http://denvish.net/ulf/090807/33048_laser.php

i absolutely adore the second graph, and third graph is just immense

--------

thinking about it, this could be directly extended into 3D aswell, only you would have a few more cases to check for, but otherwise it is directly extendable smile

Last edited by luca-deltodesco (2007-08-08 20:12:48)


The Beginning Of All Things To End.
The End Of All Things To Come.

Offline

#5 2007-08-08 23:57:50

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,711

Re: rendering polynomial implicit shapes 2D

A good technique, a bit like my "brute force" method would you say? But some kind of brute force may be the only way, as the function could pop up anywhere.

The graphs are excellent, I love the "narrowing in" boxes effect, looks very high tech.


"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Offline

#6 2007-08-09 00:10:32

luca-deltodesco
Member
Registered: 2006-05-05
Posts: 1,470

Re: rendering polynomial implicit shapes 2D

the narrowing in of boxes looks cool, but the only reason it 'narrows' in is because i am rendering the graphs at different accuracies, it draws a box whenever it detects that the graph passes through it. so having different accuracies, different sized boxes, they congrugate around where the graph parts are drawn

next i need to make it render the shapes as solids, shouldnt be too hard, only a bit of changing to do (have to seperate teh different cases a bit etc, but shouldnt be too hard)


The Beginning Of All Things To End.
The End Of All Things To Come.

Offline

#7 2007-08-09 00:34:02

luca-deltodesco
Member
Registered: 2006-05-05
Posts: 1,470

Re: rendering polynomial implicit shapes 2D

yep, there we are:

0.02x³ - 2x² + y² + 2xy - 100 = 0
http://denvish.net/ulf/090807/48838_laserrend.php
----
20cos(0.08y) - 50sin(0.04x) - 0.004xy= 0
http://denvish.net/ulf/090807/48722_laserrend.php
----


http://denvish.net/ulf/090807/48788_laserrend.php


The Beginning Of All Things To End.
The End Of All Things To Come.

Offline

#8 2007-08-09 00:43:32

luca-deltodesco
Member
Registered: 2006-05-05
Posts: 1,470

Re: rendering polynomial implicit shapes 2D

my god, this is just plain cool:

http://denvish.net/ulf/090807/49336_laserrend.php

i had to make it render at a higher quality to pick up details:


The Beginning Of All Things To End.
The End Of All Things To Come.

Offline

#9 2007-08-09 09:20:01

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,711

Re: rendering polynomial implicit shapes 2D

Should be hanging in The Museum of Modern Art!


"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Offline

#10 2007-08-22 16:39:42

John E. Franklin
Member
Registered: 2005-08-29
Posts: 3,588

Re: rendering polynomial implicit shapes 2D

You're a genuous!! Aside from the pun,  what if you set some equations equal to values close to zero, but not exactly, and compare the graphs you get to the zero set equations.
And if they look totally different, then set them even closer to zero until they look similar.


igloo myrtilles fourmis

Offline

#11 2007-08-27 04:27:34

Kargoneth
Member
Registered: 2007-08-11
Posts: 33

Re: rendering polynomial implicit shapes 2D

Intriguing... that they are anti-aliased is even more impressive (super-sampling?)

Reminds me of fractals... lol...

I wonder if this kind of stuff could be used to make a crude 'plasma' effect...

How long does it take to render one of those images?

Offline

Board footer

Powered by FluxBB