Calculating min and max values of an arbitrary mesh.

This is a discussion on Calculating min and max values of an arbitrary mesh. within the Game Programming forums, part of the General Programming Boards category; How are the min and max values calculated for an arbitrary mesh? (for setting bounding volumes) I know it has ...

  1. #1
    The Right Honourable psychopath's Avatar
    Join Date
    Mar 2004
    Location
    Where circles begin.
    Posts
    1,070

    Calculating min and max values of an arbitrary mesh.

    How are the min and max values calculated for an arbitrary mesh? (for setting bounding volumes)

    I know it has something to do with adding up the total verticies, and then dividing or subtracting something else..or not. I don't really know.

    Thanks.
    Memorial University of Newfoundland
    Computer Science

    Mac and OpenGL evangelist.

  2. #2
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    Just iterate through all the vertices keeping track of min/max x, y, and z?

  3. #3
    The Right Honourable psychopath's Avatar
    Join Date
    Mar 2004
    Location
    Where circles begin.
    Posts
    1,070
    That works too.

    I was almost positive that there was some formula (or more complicated way) of doing it though. Maybe I confused it with something else?
    Memorial University of Newfoundland
    Computer Science

    Mac and OpenGL evangelist.

  4. #4
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,586
    None that I know of except using averaging and/or tracking min/max.

  5. #5
    Absent Minded Programmer
    Join Date
    May 2005
    Posts
    964
    Just add it to your loading process..

    When you're loading the model you're iterating through all the vertices anyways, just check each one to find out if it is higher or lower then the one before...

    Then store the minimum and maximum...

    To me this sounds very costly though.
    Sometimes I forget what I am doing when I enter a room, actually, quite often.

  6. #6
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    >To me this sounds very costly though.

    why is that? you iterate through every vertex while you read it in anyway. And a couple of lt/gt's isn't going to hurt anything. The only alternative would be to store the bounds.

  7. #7
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,586
    The way to setup bounding volumes is to use meshes. In the 3D modeler you will create your mesh and then also create a bounding mesh for it as well. The bounding mesh can double as your physics collision hull. In order to do accurate collision detection you must simplify your mesh which is done by creating a totally new one based on the actual mesh.

    The bounding volume can either be included as a very simple cube mesh or you can iterate the vertices of the collision mesh/hull to find out the min/maxes.

  8. #8
    Absent Minded Programmer
    Join Date
    May 2005
    Posts
    964
    Shrug, maybe you're right...

    But those greater and less than signs might cause a problem with a couple if's in a loop of 5000++ vertices.

    Course I could be underestimating the processing abilities of modern processors.
    Sometimes I forget what I am doing when I enter a room, actually, quite often.

  9. #9

    Join Date
    May 2005
    Posts
    1,041
    Once you have the min/max as perspective said, you can define the middle as:

    Vector3 middle = (maxs + mins) * .5f;

    If you want the mesh exactly centered around this 'middle,' while in object space, you simply do:

    for(each_vertex)
    vertices[current_vertex] -= middle;


    And if you want a radius:

    Vector3 radius_vector;

    if(-mins.x > maxs.x)
    radius_vector.x = -mins.x;
    else
    radius_vector.x = maxs.x;

    ..etc...

    float radius_magnitude = radius_vector.length();
    Last edited by BobMcGee123; 04-20-2006 at 03:34 PM.
    I'm not immature, I'm refined in the opposite direction.

  10. #10
    Registered User
    Join Date
    Jan 2005
    Posts
    847
    Quote Originally Posted by Shamino
    Shrug, maybe you're right...

    But those greater and less than signs might cause a problem with a couple if's in a loop of 5000++ vertices.

    Course I could be underestimating the processing abilities of modern processors.
    I think you would get a greater bottle neck from disk I/O.

  11. #11

    Join Date
    May 2005
    Posts
    1,041
    It's not like you need to do this every frame.

    Anything you would need to do in computer graphics is never considered expensive just as long as you only need to do it once.
    Last edited by BobMcGee123; 04-20-2006 at 05:02 PM.
    I'm not immature, I'm refined in the opposite direction.

  12. #12
    Registered User
    Join Date
    Jan 2006
    Location
    Sweden
    Posts
    92
    For my skeletal animation I'm looping through all vertices, normals and tangents once per frame for every model and recalculating them for the new skeleton. This process takes about 0.5 milliseconds for a model I've imported from Doom3 and with all optimisations on. And that is on a 4 years old computer, 1.6 GHz. Since I'm used to Flash I always underestimate the power nowadays myself I simulated a simulation (ehm, yes ^^) of half a million particles and that would run at about 25 fps, and that simulation involved a square root calculation for each particle along with ~40 lines of other calculations.

    So I think that you can take the ~0.5 milliseconds at startup to calculate the bounding box for the mesh Thats at least what I'm going to do after I've figured out how to write a good scene manager.

    EDIT: Small spelling mistake.
    Last edited by The Wazaa; 04-21-2006 at 02:30 AM.

  13. #13
    The Right Honourable psychopath's Avatar
    Join Date
    Mar 2004
    Location
    Where circles begin.
    Posts
    1,070
    Got it working. The loading time didn't seem to increase at all, and if it did, it was by a very, very small amount.
    Memorial University of Newfoundland
    Computer Science

    Mac and OpenGL evangelist.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. need help finding the max and min of a 2d array
    By finalreign in forum C Programming
    Replies: 6
    Last Post: 04-29-2009, 11:39 AM
  2. Max Min Problem
    By smithc2005 in forum C Programming
    Replies: 7
    Last Post: 10-22-2008, 10:38 AM
  3. Ranged numbers
    By Desolation in forum Game Programming
    Replies: 8
    Last Post: 07-25-2006, 10:02 PM
  4. HELP! Min Max values using array.
    By steverushby in forum C++ Programming
    Replies: 6
    Last Post: 11-28-2005, 09:13 AM
  5. help finding max and min values from list
    By ericp023 in forum C Programming
    Replies: 7
    Last Post: 02-22-2003, 05:51 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21