Sign in to follow this  
Spa8nky

Sphere Collision & 270 degree corners.

Recommended Posts

Spa8nky    230
I currently have a Sphere surrounding the camera which acts as a boundary for collision detection. After your help with the Ray Intersection methods, moving the idea forward to a method involving a Sphere wasn't too difficult. However, although I now no longer have stuttering when colliding with walls that are 90 degrees or less, I am getting horrible stuttering when colliding with two walls that are exposed at 270 degrees. E.G
              (Wall 1)
                |
                |
                |
                |___________(Wall 2)

                ^
                |
              (Camera Direction)
If the camera hits the intersection between Wall 1 and Wall 2 it will stutter between each wall until pushed out. It wont do this for any other scenario, why? Here is my code, I am using a Sphere/Triangle Collision method:

    struct CollisionResult
    {
        public bool hasHit;                     // The following parameters are only valid when hasHit is true

        //public float distanceSqr;               // distance to intersection point
        public float distance;                  // Distance to the intersection point
        public Vector3 location;                // Actual location of the hit (always a point on the triangle)
        public Vector3 normal;                  // Normal of the hit

        public static CollisionResult CreateNoHit()
        {
            CollisionResult result;
            result.hasHit = false;
            result.location = new Vector3(0, 0, 0);
            result.normal = new Vector3(0, 0, 0);
            //result.distanceSqr = 0;
            result.distance = 0;

            return result;
        }

        public void KeepClosest(CollisionResult result)
        {
            if (result.hasHit && (!hasHit || (result.distance < distance)))
            {
                this = result;           
            }
        }
    }

// In separate class:


        public void BoundingSphereTriangleCollisionDetection(Camera camera)
        {
            Vector3 projectedPosition = camera.Position;                    // Position we will move to
            BoundingSphere boundingSphere = camera.BoundingSphere;          // Object's BoundingSphere
                                            
            foreach (Triangle tri in Game1.levelTriangleList)
            {      
                SphereTriangleCollision(projectedPosition, boundingSphere.Radius, tri, out result);
         
                // Don't continue until all collisions have been resolved
                while (result.hasHit)
                {
                    // Distance to current Triangle from Object's BoundingSphere Centre (I.E. Object's Centre/Position)
                    //Console.WriteLine("Distance to Triangle: " + result.distance); 
                    projectedPosition -= result.normal * (result.distance - boundingSphere.Radius - EPSILON);

                    SphereTriangleCollision(projectedPosition, boundingSphere.Radius, tri, out result);
                }
            }

            camera.Position = projectedPosition;        
            // Bounding Sphere Position should be updated in Object Method (not here)
        }

        /// <summary>
        /// Perform a Sphere/Triangle check. (Will work with XNA BoundingSpheres also)
        /// 
        /// [Note]:
        /// - Spheres can only collide with the front side of triangles! (Much like Bounding Sphere/Plane behaviour)
        /// - Always the closest possible intersection position is returned, which is always inside the triangle.
        /// </summary>
        /// <param name="position"></param>
        /// <param name="sphereRadius"></param>
        /// <param name="result"></param>
        private void SphereTriangleCollision(Vector3 position, float sphereRadius, Triangle triangle, out CollisionResult result)
        {
            result = new CollisionResult();
            Vector3 faceNormal = triangle.FaceNormal;
            Vector3[] trianglePoints = triangle.Points;
            Vector3[] triangleEdgeNormals = triangle.EdgeNormals;

            Vector3 v = position - trianglePoints[0];

            // Check which side of the plane we are on			
            float dist;
            Vector3.Dot(ref v, ref faceNormal, out dist);

            if (dist < 0)
            {
                return;     // We need some more testing, since we're at the wrong side of the polygon!
            }
            if (dist > sphereRadius)
            {
                return;     // We're too far away from the triangle
            }

            // If the above two rules are false there is a collision point
            Vector3 collisionPoint = position - (dist * faceNormal);
            //Console.WriteLine("Triangle Collision At " + collisionPoint);

            // Is the collision point in the current Triangle?			
            if (PointInTriangle(ref collisionPoint, trianglePoints, triangleEdgeNormals))
            {
                CollisionResult t;
                t.hasHit = true;
                //t.distanceSqr = (collisionPoint - position).LengthSquared();
                t.distance = (collisionPoint - position).Length();
                t.normal = faceNormal;
                t.location = collisionPoint;

                result.KeepClosest(t);
                return;
            }

            // If the point is not inside the triangle it could still intersect the triangle! (It would intersect the Triangle edge)
            for (int i = 0; i < 3; i++)
            {
                Vector3 E = trianglePoints[(i + 1) % 3] - trianglePoints[i];

                // Relative position to edge start.
                Vector3 H = collisionPoint - trianglePoints[i];

                // Distance of P to edge plane
                float hn = Vector3.Dot(H, triangleEdgeNormals[i]);

                // Point is on the same side of the triangle, from the edge plane, try another
                if (hn < 0.0f)
                {
                    continue;
                }

                // Too far away from this edge's plane
                if (hn > sphereRadius)
                {
                    return; 
                }

                // test intersection with polygon's edge
                Vector3 intersectionPoint = new Vector3();

                if (SpherePartialEdgeCollide(ref position, ref trianglePoints[i], ref E, ref intersectionPoint))
                {
                    CollisionResult t;
                    t.hasHit = true;
                    //t.distanceSqr = (intersectionPoint - position).LengthSquared();
                    t.distance = (intersectionPoint - position).Length();
                    t.normal = faceNormal; //triangleEdgeNormals[i];
                    t.location = intersectionPoint;

                    result.KeepClosest(t);
                }
            }
        }

        private bool SpherePartialEdgeCollide(ref Vector3 start, ref Vector3 edgeV0, ref Vector3 edgeDir, ref Vector3 intersection)
        {
            // Find the point on line [edgeV0, edgeV0+edgeDir] that is closest to start
            // See: http://softsurfer.com/Archive/algorithm_0102/algorithm_0102.htm

            // Distance of a Point to a Ray or Segment
            Vector3 w = start - edgeV0;

            float c1 = Vector3.Dot(w, edgeDir);
            if (c1 <= 0)
            {
                if ((start - edgeV0).LengthSquared() <= 1)
                {
                    intersection = edgeV0;
                    return true;
                }
                else
                {
                    return false;
                }
            }

            float c2 = Vector3.Dot(edgeDir, edgeDir);
            if (c2 <= c1)
            {
                Vector3 p1 = edgeV0 + edgeDir;
                if ((start - p1).LengthSquared() <= 1)
                {
                    intersection = p1;
                    return true;
                }
                else
                {
                    return false;
                }
            }

            float b = c1 / c2;

            intersection = edgeV0 + b * edgeDir;

            float distance = 0;
            Vector3.DistanceSquared(ref start, ref intersection, out distance);

            return (distance <= 1.0f);
        }

        /// <summary>
        /// Determine for a given point (that lies on our triangle's plane) if
        /// it lies within the triangle's borders or not.
        /// 
        /// Implemented by using the triangle's edge's planes.
        /// </summary>
        /// <param name="pt">a point on the triangle's plane</param>
        /// <returns>true when point pt lies within the triangle</returns>
        private bool PointInTriangle(ref Vector3 point, Vector3[] trianglePoints, Vector3[] triangleEdgeNormals)
        {
            Vector3 a = point - trianglePoints[0];
            Vector3 b = point - trianglePoints[1];
            Vector3 c = point - trianglePoints[2];

            float v;

            Vector3.Dot(ref a, ref triangleEdgeNormals[0], out v);
            if (v >= 0)
            {
                return false;
            }

            Vector3.Dot(ref b, ref triangleEdgeNormals[1], out v);
            if (v >= 0)
            {
                return false;
            }

            Vector3.Dot(ref c, ref triangleEdgeNormals[2], out v);
            if (v >= 0)
            {
                return false;
            }

            return true;
        }



I'm not sure why it is happening, can anyone enlighten me please? Thank you. [Fixed formatting - Zahlman] [Edited by - Zahlman on May 6, 2009 3:05:46 PM]

Share this post


Link to post
Share on other sites
Atrix256    539
You should pick up this book, it is seriously the greatest book i have ever seen on collision detection:

http://www.amazon.com/Real-Time-Collision-Detection-Interactive-Technology/dp/1558607323/ref=sr_1_1?ie=UTF8&s=books&qid=1241469247&sr=8-1

it is really full featured in the collision it talks about, and it talks about the theory and math behind the collision detection, as well as gives you source code in case you dont feel like digging into the theory and math (or can't understand it completely as is generally my case haha).

Really awesome book, every game programmer should own a copy (:

Share this post


Link to post
Share on other sites
Spa8nky    230
I do own a copy! :)

It is a truly awesome book but I have problems porting some of the code over to C#.

An simple example would the following:



if (Max(v0.Y, v1.Y, v2.Y) < -e1 || Min(v0.Y, v1.Y, v2.Y) > e1)



Now in C# Math.Max can only take 2 arguments.

Assuming of course that the Maximum value is to be found with Max() how would I create a Max function that can take EITHER 2 or 3 arguments in and return the maximum value?



// Naff example for 2:

public static float Max(float a, float b)
{
float max = float.MinValue;
if (a > max)
{
max = a;
}
if (b > a)
{
max = b;
}
}



Thanks

Share this post


Link to post
Share on other sites
Zahlman    1682
Quote:
Original post by Spa8nky
Now in C# Math.Max can only take 2 arguments.

Assuming of course that the Maximum value is to be found with Max() how would I create a Max function that can take EITHER 2 or 3 arguments in and return the maximum value?


You don't write a function that takes either 2 or 3 arguments; you write a function that takes 2 arguments, and one that takes 3 arguments, and give them the same name (i.e. overload the function).

The maximum of 3 elements can be found, for example, as the maximum of (the maximum of the first 2 elements) and the 3rd element.

Better yet, you can write a function that calculates the maximum of an array of elements; then you can pass in however many you need. Beware, I did a quick Google search to find examples of such a function and they were all buggy. :)

P.S. Checking if the maximum of however many values is less than a threshold is equivalent to checking if all the values are less than the threshold. Similarly for the minimum and greater-than check.

Share this post


Link to post
Share on other sites
Spa8nky    230
Quote:
Original post by Zahlman

You don't write a function that takes either 2 or 3 arguments; you write a function that takes 2 arguments, and one that takes 3 arguments, and give them the same name (i.e. overload the function).



Awesome. I didn't know about this until now but that's probably only giving away that I am very new to this whole programming thang.

Thanks Zahlman.

Share this post


Link to post
Share on other sites
Spa8nky    230
I have come up with the following for Max(). It doesn't have any bugs in it as far as I can tell.

Comments please :D



private float Max(float v1, float v2, float v3)
{
float[] array = new float[3];
float max = float.MinValue;

array[0] = v1;
array[1] = v2;
array[2] = v3;

foreach (float value in array)
{
if (value > max)
{
max = value;
}
}

return max;
}



Feel free to rip it apart...

Share this post


Link to post
Share on other sites
mightypigeon    576
Try something like


float m = Math.Max( v1, v2 );
m = Math.Max( m, v3 );


You want to avoid allocating memory and looping in a function that could be potentially called hundreds or even thousands of times per frame depending on your scene size.

Share this post


Link to post
Share on other sites
Zahlman    1682
Quote:
Original post by Spa8nky
I have come up with the following for Max(). It doesn't have any bugs in it as far as I can tell.

Comments please :D


There's no point in accepting 3 separate elements, putting them into an array and then iterating over the array. Iterating over an array allows you to avoid repeating per-item code, but then you have per-item code to *create* the array anyway.

Also, while initializing the maximum to float.MinValue will work, it's a little cleaner to initialize it to the first element and then check every *other* element.

Oh, and your variable names are bit strange, too. Why "v1" for a float?

I came up with this version for maximum-of-array, when I was looking for examples for you, found a horrible blog post and felt compelled to comment:


// Actually this is adapted slightly...

public float max(float[] thearray) {
// Throws NullReferenceException if thearray is null
// Throws IndexOutOfRangeException if thearray is zero length
float max = thearray[0];
for (int i = 1; i != thearray.Length; ++i) {
if (thearray[i] > max) { max = thearray[i]; }
}
return max;
}



But for a function accepting 3 separate floats, it makes more sense to just do what mightypigeon suggests - although we can simplify it even further:


public float max(float a, float b, float c) {
return Math.Max(Math.Max(a, b), c);
}

Share this post


Link to post
Share on other sites
phresnel    953
Quote:
Original post by Zahlman
// Actually this is adapted slightly...
public float max(float[] thearray) {
// Throws NullReferenceException if thearray is null
// Throws IndexOutOfRangeException if thearray is zero length
float max = thearray[0];
for (int i = 1; i != thearray.Length; ++i) {
if (thearray[i] > max) { max = thearray[i]; }
}
return max;
}


silently I dreamt of the day where my infernal knowledge of this comes in handy ...

Step aside and get on distance, I know Generics [cool]

static T Max<T> (T arg0, params T [] ps) where T : IComparable<T> {
T max = arg0;
foreach (T curr in ps)
if (curr.CompareTo (max) > 0)
max = curr;
return max;
}


... and now, the Dread Ternary Operator:

static T Max<T> (T arg0, params T [] ps) where T : IComparable<T> {
T max = arg0;
foreach (T curr in ps)
max = curr.CompareTo (max) > 0 ? curr : max;
return max;
}


Both let you write code like
Console.WriteLine (Max(1.0,2.0,5.0,0.5,3.0).ToString());
Console.WriteLine (Max(2U).ToString());
Console.WriteLine (Max(1,2,3).ToString());
Console.WriteLine (Max ("FOO", "BAR", "BAZ"));
, and we see that apparently Foo is still the winner.

But certainly there should also be overloads of that function that specialize upon a limited parameter count.

Share this post


Link to post
Share on other sites
Spa8nky    230
Quote:


... and now, the Dread Ternary Operator:



I learn something new every day. I have seen this before but not in C# and I didn't know what it was called to look it up, but now I do!!!

Thanks dude.

Share this post


Link to post
Share on other sites
phresnel    953
Quote:
Original post by Spa8nky
Quote:


... and now, the Dread Ternary Operator:



I learn something new every day. I have seen this before but not in C# and I didn't know what it was called to look it up, but now I do!!!

Thanks dude.


It is called "ternary operator" with the meaning that there are 3 operands to that operator (compare to: a unary operator is one that accepts 1 operand, for example negation (as in "x=-y;") or increment ("i++;"), a binary operator is one that takes two operands, e.g. addition ("y=a+b;") or multiplication("x=a*;b")) and because operator "?:" is the only operator in C/C++ that takes three operands, it is commonly called "the ternary operator". Another name for that operator is "conditional operator", and probably there exist more.

Note that I called it "Dread Ternary Operator" because many people frown upon it, as there is some potential to make your code hard to read. My personal opinion is that, if you don't make up your statement too complex, why not use it?

E.g., I don't consider the following hard to read:

const int max = x>y ? x : y; // though in this case, better use a function "max()"
const int x = a<b && b>=c
? foo (a,b)
: bar (c,d);

And if you do it right, even a nested statement using ?: can be simple to read. Of course this reflects my personal opinion; if the team leader dictates to not use it, I will obey that rule :D


Btw, no problemo ;)

Share this post


Link to post
Share on other sites
bjarnia    219
No offense but I just had to come to the rescue after seeing that first Min function for 3 floats, and was not too impressed by the generics that followed :)

In many cases with intersections you need both min and max. It's a really simple problem.


static void MinMax(float x0, float x1, float x2, out float min, out float max)
{
min = max = x0;
if (x1 < min) min = x1;
if (x1 > max) max = x1;
if (x2 < min) min = x2;
if (x2 > max) max = x2;
}


No messy arrays or fancy stuff. Just simple.
If you only need the min or max it's obvious how to reduce it to that.

Share this post


Link to post
Share on other sites
phresnel    953
Quote:
Original post by bjarnia
No offense but I just had to come to the rescue after seeing that first Min function for 3 floats, and was not too impressed by the generics that followed :)

No offense, but it wasn't really intended to impress you. Otherwise I wouldn't have been that sarcastic and overly grandstanding :D

Btw, I have the slight feeling that you mixed together the intention of my two changes "variable argument list" and introducing "generics".


Quote:
In many cases with intersections you need both min and max. It's a really simple problem.

True.

Quote:
Quote:
static void MinMax(float x0, float x1, float x2, out float min, out float max)
{
min = max = x0;
if (x1 < min) min = x1;
if (x1 > max) max = x1;
if (x2 < min) min = x2;
if (x2 > max) max = x2;
}

No messy arrays or fancy stuff. Just simple.

You are already in C#, and you still consider arrays messy, fancy and non-trival? Also, from the client perspective, no array must be formed to call my generalized Max() function.

Also, as there exist different specializations for different parameter counts, why not make the calling convention more consistent and put the out parameters as the first parameters? The latter would make calls to MinMax() more transparent, as variable argument list versions and specialized versions have an identical syntax.

Quote:
If you only need the min or max it's obvious how to reduce it to that.

After you have already specialized onto three parameters, I don't see any performance optimization. Hence, why not have a min/max function, and upon those build a minmax function? Your code above leads to redundancy. Basically, instead of "build simple tools, and build mightier tools using those" you went "build mighty tools, from those, extract simple tools". If you are consistent with that, you really start with a enterprisey application with just a single main()-function, and then start to divide and conquer.


Finally, here is the summary according to my above points:

// At first, the general form, which works for every parameter count
// n >= 1 (which I consider important, because the minimum and maximum
// of a set that only contains 1 element is very well that element,
// and absolutely not undefined)
static T Max<T> (T arg0, params T [] ps) where T : IComparable<T> {
T max = arg0;
foreach (T curr in ps)
max = Max (max, curr);
return max;
}
static T Min<T> (T arg0, params T [] ps) where T : IComparable<T> {
T min = arg0;
foreach (T curr in ps)
min = curr.CompareTo (min) < 0 ? curr : min;
return min;
}
// For the sake of performance, and for the lack of mightier concepts
// like located in C++ templates, I introduce some redundancy
static void Min<T> (out T min, out T max, T arg0, params T [] ps) where T : IComparable<T> {
min = arg0;
max = arg0;
foreach (T curr in ps) {
max = Max (max, curr);
min = Min (min, curr);
}
}

At no place we directly index into fancy and messy arrays. Check. The signature for every MinMax() call is always the same, independent of parameter count. Check.

Now the specialised version. We begin with the very basic 1-parameter version:
// 1
static T Max<T> (T arg0) where T : IComparable<T> { return arg0; }
static T Min<T> (T arg0) where T : IComparable<T> { return arg0; }
static void MinMax<T> (out T min, out T max, T arg0) where T : IComparable<T> { min = max = arg0; }


// 2
static T Max<T> (T arg0, T arg1) where T : IComparable<T> {
return arg0.CompareTo (arg1) > 0 ? arg0 : arg1;
}
static T Min<T> (T arg0, T arg1) where T : IComparable<T> {
return arg0.CompareTo (arg1) < 0 ? arg0 : arg1;
}
static void MinMax<T> (out T min, out T max, T arg0, T arg1) where T : IComparable<T> {
// could be made branch free
if (arg0.CompareTo (arg1) < 0) {
min = arg0;
max = arg1;
} else {
min = arg1;
max = arg0;
}
}


Now comes an example of "build simple tools, and build mightier tools using those":
// 3
static T Max<T> (T arg0, T arg1, T arg2) where T : IComparable<T> {
return Max (Max (arg0, arg1), arg2);
}
static T Min<T> (T arg0, T arg1, T arg2) where T : IComparable<T> {
return Min (Min (arg0, arg1), arg2);
}
static void MinMax<T> (out T min, out T max, T arg0, T arg1, T arg2) where T : IComparable<T> {
min = Min (arg0, arg1, arg2);
max = Max (arg0, arg1, arg2);
}


// 4 
static T Max<T> (T arg0, T arg1, T arg2, T arg3) where T : IComparable<T> {
return Max (Max (arg0, arg1), Max (arg2, arg3));
}
static T Min<T> (T arg0, T arg1, T arg2, T arg3) where T : IComparable<T> {
return Min (Min (arg0, arg1), Min (arg2, arg3));
}
static void MinMax<T> (out T min, out T max, T arg0, T arg1, T arg2, T arg3) where T : IComparable<T> {
min = Min (arg0, arg1, arg2, arg3);
max = Max (arg0, arg1, arg2, arg3);
}

MinMax in two lines, without any internal state. Of course, there is place for optimization, if needed. But those two lines of MinMax() should be emitted into nearly the same code as bjarnias version.

Further, before writing a plethora of specializations, maybe just check if the JIT compiler emits unrolled versions of the general functions (if we only had non-type parameters and explicit or partial specializations for C# generics, we could do generalized unrolling manually).

Share this post


Link to post
Share on other sites
bjarnia    219
I will not argue that your code is indeed more elegant and flexible.

However... We need to remember that we're working with games here. And a function like this could potentially be called tens of thousands of times within just one frame, hundreds of thousands of times per second. So every nanosecond counts :)
It's my instinct that the simpler function would be faster than your version. But I can not back that up with any data. I don't even know how the compiler optimizes it. For example, your "3 minmax" functions appear to call 2 other functions. Will the compiler optimize that out? Would be very interesting to see a speed comparison (with real data in a real scenario).

I do recognize that we are using C# and should take advantage of that, but there is plenty of chances to do that everywhere else, in everything that you are not calling thousands of times per frame :)

So... As a side note. Since you think generics are fast enough, why do you think XNA does not use generics at all almost (except in the contentpreprocessor and content loading (one time operations))? (This is a genuine question, not trying to be a smartass)

In fact, XNA does go so far that most of it's built in math stuff (Vector, matrix, quaternion, etc) use structs (STRUCTS IN C#??? right? :) ) and the helper functions always provide an overload to pass in by reference instead of returning an instance, to avoid an unnecessary allocation and data passing on the stack.

All in all, XNA seems to be pretty devoid of most c# specific functionality.

Share this post


Link to post
Share on other sites
bjarnia    219
I just performed some informal testing...

Over 10000000 triangles created with Random, the generic function was twice as slow as the simple one. 1.5 seconds vs 0.75 seconds.

Edit: that was on debug... The difference is not as big in release but there is still a noticable difference, especially for a function that is going to be called so often.

Release compiled without debugger attached: (50000000 triangles
Time: 00:00:02.4691412 (Simple)
Time: 00:00:03.8562034 (Generics)

Share this post


Link to post
Share on other sites
phresnel    953
The compiler would be dumb to not inline my inner functions calls, as they are very thin. Note that writing a competent benchmark requires is not exactly easy. Is your code predictable? How much can the compiler rollout? How much constant propagation can the compiler perform? How much can the compiler fold away? How much redundancy can it detect, a form of that being common subexpression elimination? How exactly looks the implementation of generics like *? Did you measure branch and cache misses, if that is relevant to your real application? Et cetera.


A good starting point would be to consider that if all code is visible at once, and no code depends on external information, the program could be optimized to pure output.

Sorry to say, but your benchmark does not exist as long as you don't post the sourcecode. Btw, did you at least turn optimization on?

*: Generics are a runtime construct, but it would make me nervous if no type-native code would be emitted. Is that the case with version xxx of mono/.net?


Btw,
Quote:
(STRUCTS IN C#??? right? :) )

could you maybe stop teaching ppl like that?.

Share this post


Link to post
Share on other sites
phresnel    953
Let me elaborate on some of your assumptions:

Quote:
Since you think generics are fast enough

No. Because I haven't measured, I haven't pretended anything. Stop lying.

Quote:
It's my instinct that the simpler function would be faster than your version.

Wrong. Consider those C functions, which compute the remainder of a division of a number x by 3, under the assumption that x is in the interval [0..2]:

int mod3(int x) {
return x % 3;
}


int mod3(int x) {
static const int ret[5] = {0, 1, 2, 0, 2};
return ret [1+x];
}


On modern x86 or x86-64, which one do you expect to be faster?

Hint: The second version is a common optimization in modern ray tracing with kd-trees.

Quote:
data passing on the stack

Where, do you think, are references passed, in case the function is not inlined?

Quote:
I don't even know how the compiler optimizes it.

Okay.

Quote:
For example, your "3 minmax" functions appear to call 2 other functions. Will the compiler optimize that out?

As said, he would be a bad compiler if he cannot speculate about performance of inlined and a non-inlined version. I could also ask the question whether the compiler is able to make your or mine code branch free at the if's, the else's and the ?:'s.

Share this post


Link to post
Share on other sites
bjarnia    219
Quote:


Quote:
It's my instinct that the simpler function would be faster than your version.

Wrong. Consider those C functions, which compute the remainder of a division of a number x by 3, under the assumption that x is in the interval [0..2]:



Wrong? What was wrong? My instincts? (clearly not, after I benchmarked it was confirmed)

Not going to bother with responding to the rest of the stuff since you are coming off extremely defensive as if I challenged your manhood.

And here is the benchmark code. Actually posted it yesterday but didn't know what tag to use so it would become scrollable so I didn't feel like it was worth ruining the thread as it's just a repitition of the above code. And yes optimization is turned on.

Edit: Found out about the source tag




using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
Random r = new Random();
float min, max;

{
DateTime start = DateTime.Now;
for (int i = 0; i &lt; 50000000; i++)
MinMax2((float)r.NextDouble(), (float)r.NextDouble(), (float)r.NextDouble(), out min, out max);
Console.WriteLine("Time: {0}", start - DateTime.Now);
}
{
DateTime start = DateTime.Now;
for (int i = 0; i &lt; 50000000; i++)
MinMax(out min, out max, (float)r.NextDouble(), (float)r.NextDouble(), (float)r.NextDouble());
Console.WriteLine("Time: {0}", start - DateTime.Now);
}


Console.ReadLine();

}



static void MinMax2(float x0, float x1, float x2, out float min, out float max)
{
min = max = x0;
if (x1 &lt; min) min = x1;
if (x1 &gt; max) max = x1;
if (x2 &lt; min) min = x2;
if (x2 &gt; max) max = x2;
}

// At first, the general form, which works for every parameter count
// n &gt;= 1 (which I consider important, because the minimum and maximum
// of a set that only contains 1 element is very well that element,
// and absolutely not undefined)
static T Max&lt;T&gt;(T arg0, params T[] ps) where T : IComparable&lt;T&gt;
{
T max = arg0;
foreach (T curr in ps)
max = Max(max, curr);
return max;
}
static T Min&lt;T&gt;(T arg0, params T[] ps) where T : IComparable&lt;T&gt;
{
T min = arg0;
foreach (T curr in ps)
min = curr.CompareTo(min) &lt; 0 ? curr : min;
return min;
}


// 1
static T Max&lt;T&gt;(T arg0) where T : IComparable&lt;T&gt; { return arg0; }
static T Min&lt;T&gt;(T arg0) where T : IComparable&lt;T&gt; { return arg0; }
static void MinMax&lt;T&gt;(out T min, out T max, T arg0) where T : IComparable&lt;T&gt; { min = max = arg0; }



// 2
static T Max&lt;T&gt;(T arg0, T arg1) where T : IComparable&lt;T&gt;
{
return arg0.CompareTo(arg1) &gt; 0 ? arg0 : arg1;
}
static T Min&lt;T&gt;(T arg0, T arg1) where T : IComparable&lt;T&gt;
{
return arg0.CompareTo(arg1) &lt; 0 ? arg0 : arg1;
}
static void MinMax&lt;T&gt;(out T min, out T max, T arg0, T arg1) where T : IComparable&lt;T&gt;
{
// could be made branch free
if (arg0.CompareTo(arg1) &lt; 0)
{
min = arg0;
max = arg1;
}
else
{
min = arg1;
max = arg0;
}
}


// 3
static T Max&lt;T&gt;(T arg0, T arg1, T arg2) where T : IComparable&lt;T&gt;
{
return Max(Max(arg0, arg1), arg2);
}
static T Min&lt;T&gt;(T arg0, T arg1, T arg2) where T : IComparable&lt;T&gt;
{
return Min(Min(arg0, arg1), arg2);
}
static void MinMax&lt;T&gt;(out T min, out T max, T arg0, T arg1, T arg2) where T : IComparable&lt;T&gt;
{
min = Min(arg0, arg1, arg2);
max = Max(arg0, arg1, arg2);
}

// 4
static T Max&lt;T&gt;(T arg0, T arg1, T arg2, T arg3) where T : IComparable&lt;T&gt;
{
return Max(Max(arg0, arg1), Max(arg2, arg3));
}
static T Min&lt;T&gt;(T arg0, T arg1, T arg2, T arg3) where T : IComparable&lt;T&gt;
{
return Min(Min(arg0, arg1), Min(arg2, arg3));
}
static void MinMax&lt;T&gt;(out T min, out T max, T arg0, T arg1, T arg2, T arg3) where T : IComparable&lt;T&gt;
{
min = Min(arg0, arg1, arg2, arg3);
max = Max(arg0, arg1, arg2, arg3);
}


}
}





[Edited by - bjarnia on May 11, 2009 11:59:21 AM]

Share this post


Link to post
Share on other sites
bjarnia    219
Well your post made me want to do a better benchmark where the random calls and the typecast overheads were avoided. All I can say is OUCH because the generics code got dismembered.

Time: 00:00:00.6260369 (Simple)
Time: 00:00:04.4302525 (Generics)

Same functions as above, diff main

Edit: I noticed I got some massive negative rep from someone... lol, so much for trying to help.



static void Main(string[] args)
{
Random r = new Random();
float min, max;
TimeSpan t1 = new TimeSpan();
TimeSpan t2 = new TimeSpan();

for (int j = 0; j &lt; 50000; j++)
{

float f1 = (float)r.NextDouble();
float f2 = (float)r.NextDouble();
float f3 = (float)r.NextDouble();

DateTime start1 = DateTime.Now;
for (int i = 0; i &lt; 500; i++)
{
MinMax2(f1, f2, f3, out min, out max);
MinMax2(f1, f3, f2, out min, out max);
MinMax2(f2, f1, f3, out min, out max);
MinMax2(f2, f3, f1, out min, out max);
MinMax2(f3, f2, f1, out min, out max);
MinMax2(f3, f1, f2, out min, out max);
}
t1 += DateTime.Now - start1;

DateTime start2 = DateTime.Now;
for (int i = 0; i &lt; 500; i++)
{
MinMax(out min, out max, f1, f2, f3);
MinMax(out min, out max, f1, f3, f2);
MinMax(out min, out max, f2, f1, f3);
MinMax(out min, out max, f2, f3, f1);
MinMax(out min, out max, f3, f2, f1);
MinMax(out min, out max, f3, f1, f2);
}
t2 += DateTime.Now - start2;
}
Console.WriteLine("Time: {0}", t1);
Console.WriteLine("Time: {0}", t2);

Console.ReadLine();

}


Share this post


Link to post
Share on other sites
Zahlman    1682
Try to keep it civil, guys. It's beneficial for your ratings. (No, I didn't rate either of you down. No, I don't know who did, and I'm not going to even try to check. I'm just saying.)

Share this post


Link to post
Share on other sites
phresnel    953
Quote:
Quote:
Quote:
It's my instinct that the simpler function would be faster than your version.

Wrong. Consider those C functions, which compute the remainder of a division of a number x by 3, under the assumption that x is in the interval [0..2]:

Wrong? What was wrong? My instincts? (clearly not, after I benchmarked it was confirmed)

Not wrong in that case, sorry. But in the general case, your instinct is wrong because "simpler == faster" is not always right, or better, is generally not right if you do more than just some adds and muls and min/max.


Quote:
Not going to bother with responding to the rest of the stuff since you are coming off extremely defensive as if I challenged your manhood.

Actually, there was a lie (I didn't say that generic code is faster, but you said I pretended so; and lies makes me indeed a bit angry). Then you were saying that C# has structs, as if people reading this thread, or maybe specifically me, didn't know that C# classes and structs are distinct or that C# has structs at all.

For me, let's not elaborate that further and get back to discussion ;)

Quote:
And here is the benchmark code.

Merci Beaucoup. Gonna reply about it later after I found some time to check. Or is that going too OT?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this