On Thu, 22 Feb 2001 17:56:21 +0100, Christoph Hormann wrote:
>
>
>Ron Parker wrote:
>> 
>> Isosurfaces can be viewed as basic mathematical objects for the sake of
>> this exercise, since the approximation is purely visual.  The problem
>> of determining whether two "basic mathematical objects" overlap reduces
>> to a simple matter of solving a set of simultaneous equations and looking
>> for solutions within given ranges.  Unfortunately, the equations you're
>> solving aren't necessarily linear or even polynomial.  Presumably it's
>> possible to solve such a system for any given combination of objects
>> (though not necessarily) but it's either impossible or ridiculously
>> difficult to automate the process for any two arbitrary objects.
>> 
>
>Seems you are right if you want to make it work for any CSG.  Anyway if
>you only need the objects themselves (or unions) it could be reduced to a
>set of independent equations.  

Yes and no.  Some objects, like isosurfaces, blobs, and polys, are fairly
ugly even then.  Other objects, like cubes and cones and cylinders, can 
get fairly ugly after you apply transformations to them.

Even CSG intersections could be handled, if you could handle the solution of
the independent equations.  The problem is that that solution is not easy.

-- 
Ron Parker   http://www2.fwi.com/~parkerr/traces.html
My opinions.  Mine.  Not anyone else's.

Post a reply to this message

On Thu, 22 Feb 2001 17:57:43 +0100, Christoph Hormann wrote:
>One could also use the brute force method using eval_pattern on the object
>patterns of the two objects in a fine parallel raster...

Or on the object pattern of the intersection of the two objects.

-- 
Ron Parker   http://www2.fwi.com/~parkerr/traces.html
My opinions.  Mine.  Not anyone else's.

Post a reply to this message

Ron Parker wrote:
> 
> Yes and no.  Some objects, like isosurfaces, blobs, and polys, are fairly
> ugly even then.  Other objects, like cubes and cones and cylinders, can
> get fairly ugly after you apply transformations to them.
> 

I was only thinking about spheres, cylinders and objects made of planes
(like boxes) which would result in distances between points, lines and
planes.  I agree that everything else can get really ugly.  

Christoph

-- 
Christoph Hormann <chr### [at] gmxde>
IsoWood include, radiosity tutorial, TransSkin and other 
things on: http://www.schunter.etc.tu-bs.de/~chris/

Post a reply to this message

In article <3A953C06.F7A4B59D@gmx.de>, Christoph Hormann 
<chr### [at] gmxde> wrote:

> (maybe it would be a good idea to make the Inside_Object()
> function available in POV script just like trace()).

I haven't done it before, since this macro is pretty easy:
#macro InObj(Pt, Obj) eval_pattern(object {Obj}, Pt) #end

But all it should take is adding a "inside_object" token to parse.h and 
tokenize.c, and adding this case to Parse_Num_Factor() in express.c 
(make sure you put it with the float functions):
          case INSIDE_OBJECT_TOKEN:
          {
            OBJECT * Object; 
            VECTOR Point;

            GET(LEFT_PAREN_TOKEN);
            Parse_Vector(Point);
            Parse_Comma();
            EXPECT
                CASE(OBJECT_ID_TOKEN)
                    Object = Token.Data;
                    EXIT
                END_CASE
                OTHERWISE
                    Object = NULL;
                    UNGET
                    EXIT
                END_CASE
            END_EXPECT
            if(Object == NULL)
            {   Error ("Object Identifier Expected.");}
            GET(RIGHT_PAREN_TOKEN);
            
            Val = Inside_Object(Point, Object);
          }
          break;

I haven't tested this patch (I haven't even compiled it), but it should 
work.

-- 
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/

<><

Post a reply to this message

Chris Huff wrote:
> 
> I haven't done it before, since this macro is pretty easy:
> #macro InObj(Pt, Obj) eval_pattern(object {Obj}, Pt) #end
> 
> But all it should take is adding a "inside_object" token to parse.h and
> tokenize.c, and adding this case to Parse_Num_Factor() in express.c
> (make sure you put it with the float functions):
> [...]
> 
> I haven't tested this patch (I haven't even compiled it), but it should
> work.
> 

The hardcoded version would probably be much faster so i think it's quite
a good idea when it should be used for collision detection where it would
be called quite often.  

Christoph

-- 
Christoph Hormann <chr### [at] gmxde>
IsoWood include, radiosity tutorial, TransSkin and other 
things on: http://www.schunter.etc.tu-bs.de/~chris/

Post a reply to this message

In article <3A9550F9.80FAA811@gmx.de>, Christoph Hormann 
<chr### [at] gmxde> wrote:

> The hardcoded version would probably be much faster so i think it's quite
> a good idea when it should be used for collision detection where it would
> be called quite often.  

The patch I posted compiled and ran fine.
I tested the speed with a file that called the function or macro 64^3 
(262144) times.
The macro version used 238 seconds, and the function version used 208 
seconds, so the function version takes about 87% as long as the macro.

It seems macros don't have that much overhead...at least, the MegaPOV 
macros, which have been optimized. However, in a collision detection 
algorithm, which could easily use even more calls, this small 
improvement would still be helpful.

-- 
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/

<><

Post a reply to this message

In article <chrishuff-99F94F.13380822022001@news.povray.org>, Chris 
Huff <chr### [at] maccom> wrote:

> The macro version used 238 seconds, and the function version used 208 
> seconds, so the function version takes about 87% as long as the macro.

I decided to do a more accurate calculation by subtracting out the 
"overhead" of the rest of the scene (by replacing the call to the macro 
or function with a 0), and found out a surprisingly large portion of the 
time was spent in the loops themselves...and the function is a great 
deal faster than the macro.
The scene with no calls but the same number of repetitions used 204 
seconds, so the total time used by the function was 4 seconds and the 
total time used by the macro was 34 seconds. The function only takes 
about 11.7% as long as the macro...nearly 10 times faster.

Which figure is more relevant? The 11.7% is a better comparison of the 
speed of the macro with the speed of the function, but the 87% figure is 
closer to what you will see in real life...you will probably have the 
call nested in a bunch of loops and other macro calls. Only a small 
portion of the time was actually spent in the macro/function call.

-- 
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/

<><

Post a reply to this message

On Thu, 22 Feb 2001 13:55:25 -0500, Chris Huff wrote:
>> The macro version used 238 seconds, and the function version used 208 
>> seconds, so the function version takes about 87% as long as the macro.
>
>I decided to do a more accurate calculation by subtracting out the 
>"overhead" of the rest of the scene (by replacing the call to the macro 
>or function with a 0), and found out a surprisingly large portion of the 
>time was spent in the loops themselves...and the function is a great 
>deal faster than the macro.

If we're gonna add functions, might as well make one that does the whole
apprxomated-collision-detection operation, especially if loops are that
slow.

-- 
Ron Parker   http://www2.fwi.com/~parkerr/traces.html
My opinions.  Mine.  Not anyone else's.

Post a reply to this message

Ron Parker wrote:
> 
> If we're gonna add functions, might as well make one that does the whole
> apprxomated-collision-detection operation, especially if loops are that
> slow.
> 

You mean something like:

collide(object, object, method, accuracy)

returning 1 or 0 for collision or no collision?

It yould be useful, but what's really needed in most cases is a function
returning where an object collides with another one if it is moved in a
certain way.  This would mean something like 'trace' with an additional
object parameter. 

Christoph

-- 
Christoph Hormann <chr### [at] gmxde>
IsoWood include, radiosity tutorial, TransSkin and other 
things on: http://www.schunter.etc.tu-bs.de/~chris/

Post a reply to this message

In article <slr### [at] fwicom>, ron### [at] povrayorg 
wrote:

> If we're gonna add functions, might as well make one that does the whole
> apprxomated-collision-detection operation, especially if loops are that
> slow.

Agreed...a collision detection algorithm that works this way written 
entirely in POV-Script would likely be almost unbearably slow.


In article <3A9### [at] gmxde>, Christoph Hormann 
<chr### [at] gmxde> wrote:

> It yould be useful, but what's really needed in most cases is a function
> returning where an object collides with another one if it is moved in a
> certain way.  This would mean something like 'trace' with an additional
> object parameter. 

One little problem...how do you define "where an object collides with 
another one"? This will most likely not be a point.
Or do you mean a function that checks if objects *will* collide and 
returns the first point of contact? You might as well just implement a 
general kinetics system in POV. I've considered something like this, a 
system that would handle solid objects, cloths and strings, and fluid 
particles, all interacting with each other, but it would be a lot of 
work. It'd make some fun animations, though. :-)

-- 
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/

<><

Post a reply to this message