Will-O 122 Report post Posted November 9, 2006 Hello, First post on GD forum so patience please... I would like to know if anyone has come across any solutions for this problem, in which case please show me where, or if anyone might be able to explain how I can solve the following problem. In the normal scheme of things a mean value from a set of data can be found by simply adding up the recorded values and dividing through by the number of records: mean[x] = (x[0] + x[1] + ... x[n]) / n mean[y] = (y[0] + y[1] + ... y[n]) / n mean[z] = (z[0] + z[1] + ... z[n]) / n The location of mean[xyz] may, and in fact probably, will not lie on the original surface. This is the problem - it must lie on the surface to be a part of the surface. Indeed "mean" may not be an entirely apropriate term for this average, maybe mid-point would convey the notion better. For an enclosed surface and particularly symetrical ones, eg a sphere, the problem seems virtually unsolveable because the likelyhood is equal and there is no mid-point on the surface itself. However, for un-enclosed surfaces a mid-point should exist and this is what I want to know how to find. To bring the conundrum to life a little - imagine a human nose, where is the mid-point of the upper-surface? (one could consider the surface rolled out flat). One thought I had was to reduce the number if dimensions in question from 3 to 2, and then 2 to 1 (a line) from where a mid point amy easily be found; then reverse the process to put this mid-point on the surface. Any more detail of how to do it than that I'm not sure of though. Please do ask me to elaborate on anything if something appears unclear. Thanks in advance for the help. Will-O [Edited by - Will-O on November 9, 2006 8:59:30 AM] 0 Share this post Link to post Share on other sites
DaBookshah 175 Report post Posted November 9, 2006 I don't understand, but the closest I can think of is finding center of mass/moments using multiple integrals. Just a stab in the dark at what you mean. Or maybe you mean something more advanced. 0 Share this post Link to post Share on other sites
smc 292 Report post Posted November 9, 2006 Im not sure if there is a general solution to this. It realy depends on the context of your problem. For instance your sphere example. Yes you are right there is no solution to finding a mean value / mid point (All points on the surface could be considerd such a point). However, if you restrict your domain/range in some way then there should be sufficient parameters to support finding a mean value / mid point. Using your nose example for instance. Using this open surface you could find its region in the xy plane. Then treat this region as a lamina of uniform densitiy. Then find the moments to find the center of mass. Once you find the centers plug back into f(x,y) to find the mid point on the surface.I am also just taking a stab in the dark with this... 0 Share this post Link to post Share on other sites
Mastaba 761 Report post Posted November 9, 2006 There is certainly no general solution to this problem, as the problem is not defined! You need to be precise in what your definition of 'mid point' is.For example, take a simple 2D planar disc, cut a hole in it. Where is the 'mid-point' of that disc with a hole? 0 Share this post Link to post Share on other sites
iMalc 2466 Report post Posted November 9, 2006 Are you interested in centre of mass, or bounding spheres, or something else? 0 Share this post Link to post Share on other sites
Will-O 122 Report post Posted November 9, 2006 DaBookShah:Erm yes thought may not have been totally clear.Hope this helps...I've tried to think of an example but it's hard when I can't add in an image. A quick sketch of the following should show what I'm trying to say:p0(1,0,5), p1(4,0,4), p2(5,0,0), p3(0,5,6), p4(5,3,5), p5(6,5,0), p6(0,8,3), p7(2,8,2), p8(3,8,0);Doesn't look too pretty in numerical form (ahh the beauty of visualization). Anyway the shape is a surface patch consisting of 8 triangles.If the positions of each vertex were added up and divided then this would give the arithmetic mean which would not lie on the surface. I am looking for some sort of average value that lies on the surface.smc:In the cases I am dealing with there is a clearly defined sub-region of the overall geometry, which is always going to be a small patch of about 3 - 15 vertices.From what you have said, do I suppose that you suggest projecting the isolated points onto a plane and then finding a 2D mid-point?Please clarify "lamina of uniform density". Been a while since the classroom!Both your comment and the previous one refered to finding the centre of mass - why would this be useful here? Mastaba:I think, judging by the disc comment you do understand despite my slightly sketchy explanation. I admit: I hadn't thought of instances where the mesh is incomplete. if it were a perfect circle and the hole where in the middle - then yes the desired mid-point would exist where I don't want it to: in thin air!iMalc:Something else I think. See above - you posted after I wrote most of this. 0 Share this post Link to post Share on other sites
erissian 727 Report post Posted November 9, 2006 As an idea, and this may or may not be what you want:1. Calculate the normal for the surface by averaging the normal of every point on the surface. In the event of a closed surface, this correctly should be 0.2. Project the object on the plane perpendicular to it's normal.3. Find the 2D midpoint on the projection4. Project the 2D midpoint on to the surfaceThere's likely a more intuitive and easier way to do it, or at least streamline the above, but I haven't given it too much thought. Maybe after lunch :) 0 Share this post Link to post Share on other sites
smc 292 Report post Posted November 9, 2006 Quote:Original post by Will-Osmc:In the cases I am dealing with there is a clearly defined sub-region of the overall geometry, which is always going to be a small patch of about 3 - 15 vertices.From what you have said, do I suppose that you suggest projecting the isolated points onto a plane and then finding a 2D mid-point?Please clarify "lamina of uniform density". Been a while since the classroom!Both your comment and the previous one refered to finding the centre of mass - why would this be useful here? I was thinking it may be possible to use the region of the surface to find the 'ballancing point' of the 2d projected surface, or region if you will. I should not have use the phrase 'A lamina of uniform density'. Simply stated this is just a very thin sheet of some material. The material is spread about the sheet uniformly. To see what I was thinking, take a look at this link. Scroll down to the section titled 'Locating the center of mass of an arbitrary 2D physical shape'.Thinking about it further, I am not sure this is even correct for continuous surfaces. I am sure someone on this board will have good solution.Edit:I was thinking you could use the centroid to find this. Once you found the centroid of the surfaces region, you could use these coordinates as the inputs to the surfaces function. Again my shot in the dark. 0 Share this post Link to post Share on other sites
Will-O 122 Report post Posted November 9, 2006 by erissianQuote:As an idea, and this may or may not be what you want:1. Calculate the normal for the surface by averaging the normal of every point on the surface. In the event of a closed surface, this correctly should be 0.2. Project the object on the plane perpendicular to it's normal.3. Find the 2D midpoint on the projection4. Project the 2D midpoint on to the surface:)by smcQuote: I was thinking you could use the centroid to find this. Once you found the centroid of the surfaces region, you could use these coordinates as the inputs to the surfaces function. In you case I guess you could cast a ray in the direction of the z axis. Again my shot in the darkI think I may try to mix both of these...1. Get the centroid for the whole patch.2. Calculate the mean normal for the whole patch.3. Cast a ray from the centroid along the mean normal in a (positive and negative) to see which triangle this passes through, thus where it lies on the original surface.Does that sound plausable?Can anyone think of instances where(a) this might not work?(b) or how to speed this up?(c) other problem might occur?-----------------------------------------------------------------------------And now for something completely different...Can someone direct me to where info for the forum is and how to do stuff like upload imgs, which html tags work and stuff like that. 0 Share this post Link to post Share on other sites
Zipster 2359 Report post Posted November 9, 2006 Projecting the 3D surface into 2D to find the mean, and then reverse projecting the mean back into 3D, is the first thought that came to my mind as well. But then I realized that there are a number of surfaces where invertible projection isn't possible. For instance, take a tessellated sphere surface, and cut out a piece of it that is less than a full hemisphere. This would be something like a bowl, only where the top part still "overhangs" the bottom. Here's a gorgeous ASCII side-profile: / \ / \ | | \ / \ / ------ There's no way you can project this onto any plane without overlaps. You might have to perform a similar process that's done often in texture skinning, where you literally unroll the surface onto a plane using texture coordinates. You'd probably have to assign the texture coordinates manually though, I'm not sure of the exact process. 0 Share this post Link to post Share on other sites
erissian 727 Report post Posted November 9, 2006 That's true, but since we're working with a simple shape, you can easily visual where the center of the surface is. Even though it's an overlapping shape when projected in 2 dimensions, the center of that projection will still coincide with the center of that surface. The crux being that you project onto a plane perpendicular to the normal of the surface. 0 Share this post Link to post Share on other sites
Will-O 122 Report post Posted November 9, 2006 Quote:Original post by ZipsterYou might have to perform a similar process that's done often in texture skinning, where you literally unroll the surface onto a plane using texture coordinates. You'd probably have to assign the texture coordinates manually though, I'm not sure of the exact process.I like that idea not sure how it might work for non-uniform shapes: there might be u-v distortion.The whole un-role then re-role sounds good. I'm a shocking programmer but I'll give it a go with pen and paper.Quote: Origninal by erissianbut since we're working with a simple shapeThe shape described (ahh so that's how you do mono-spaced characters) is more complicated than the ones I need to deal with at the moment but I think my theory might still work.(Sometimes we all need to think out-loud).(a) Calc mid-point in volume occupied by patch: the centroid(b) Calc mean normal for whole patch(c) Find the intesect of a ray/line/vector (whatever you want to call it!) from the centroid along the normal back to the patch.Any thoughts?Have to say all you people are great! Never thought I'd get any takers... don't let the praise go to your head keep it coming :) 0 Share this post Link to post Share on other sites
Mastaba 761 Report post Posted November 9, 2006 Quote:Original post by Will-OMastaba:I think, judging by the disc comment you do understand despite my slightly sketchy explanation. I admit: I hadn't thought of instances where the mesh is incomplete. if it were a perfect circle and the hole where in the middle - then yes the desired mid-point would exist where I don't want it to: in thin air!Think about where the 'mid-point' would be even if the hole did not remove the center of the disc and allow that hole to be of any shape. Only when the hole has certain properties would an intuitive mid-point be present. The trick is determining what the mid-point is even when it is not intuitive. The first step to the solution is define precisely what one means by mid-point. 0 Share this post Link to post Share on other sites
smc 292 Report post Posted November 9, 2006 Quote:Original post by Will-OThe shape described is more complicated than the ones I need to deal with at the moment but I think my theory might still work.(Sometimes we all need to think out-loud).(a) Calc mid-point in volume occupied by patch: the centroid(b) Calc mean normal for whole patch(c) Find the intesect of a ray/line/vector (whatever you want to call it!) from the centroid along the normal back to the patch.Any thoughts?Have to say all you people are great! Never thought I'd get any takers... don't let the praise go to your head keep it coming :)This is along the lines of what I was thinking. The only difference is I am thinking about continious (curved) surfaces. I am still not sure if this will work or not. I'll go ahead and break out the white board and run a test case. 0 Share this post Link to post Share on other sites
smc 292 Report post Posted November 9, 2006 For the trivial example I put together this works. My (trival) example:Imagine a sin wave running along the y axis centered on the plane z=2 z = sin(y) + 2Now bound the region under the graph (in the xy plane) by (0,0) (0,2PI) (4,0) (4,2PI).Now you have a rectangle in the xy plane representing the region R (shadow) bounded by the above constraints. It is trivial to find the center of this box (cx,cy). Now cast a ray along the z axis. It will intersect the sine wave at the point (cx,cy,2). Using these bounds we have essentialy found where the sin wave intersects the z = 2 plane. This is correct and it is the center of the surface bounded by the rectangle.This was trivial being that sin is smooth, semetrical and uniform, not to mention I chose convieniant bounding parameters. I am still not sure if this will work with arbitrary shapes. I am interested to know if it will. 0 Share this post Link to post Share on other sites
TheAdmiral 1122 Report post Posted November 9, 2006 There are indeed uncountably many ways to tackle this. Here's mine:Find some centre of the vertex soup. There are many candidates, but the area-weighted mean sounds decent. Calculate the principal axes about this centre, to get an idea of how the soup is posed about this point. 'Inflate' an ellipsoid, centred at this point, according to these axes until it collides with something. Any collision point can be your centre.In the case of a sphere, any point will be the result.For a cube, this solves to any face centre.A plane; the centroid.A cylinder; its equator.A nose, somewhere in the bridge, or one of the sides if it's a particularly flat nose.The biggest problem I see is with an ellipsoid: the result is the whole surface, rather than its smallest circumference, as one may hope. To solve this, you could take square-roots (or something) on the magnitudes of the principal axes.Practically, however, I think you need to rethink the problem. Given any proposed answer, one could contrive a surface on which it fails miserably. Could you perhaps tell us what you plan to use this algorithm on? Maybe we could suggest an alternative.RegardsAdmiral 0 Share this post Link to post Share on other sites
Will-O 122 Report post Posted November 10, 2006 Quote:Original by MastabaThe first step to the solution is define precisely what one means by mid-point.For a 2D surface, the mid-point can be found simply: it's the centroid. For a surface where some of the vertices are displaced, ie it's in 3D, the problem is that this centroid may and probably won't be on the surface. It is for these cases that I am trying to find a solution. (see bottom of this piece).Quote:Original from smcThis is correct and it is the center of the surface bounded by the rectangle.This was trivial being that sin is smooth, semetrical and uniform, not to mention I chose convieniant bounding parameters. I am still not sure if this will work with arbitrary shapes. I am interested to know if it will.Ahh - but you got something working. This is a simple case because you can project along the z-axis (which I think is the mean normal to the surface) and don't have to find another normal but it works. Nice. This surface is mathematically defined, rather than merely by a set of points so doing some of the calcs might have been easier?I'm going to spend some time later having a look at this with the 9 points I put up here yesterday.Quote:Original post by TheAdmiralFind some centre of the vertex soup. There are many candidates, but the area-weighted mean sounds decent. Calculate the principal axes about this centre, to get an idea of how the soup is posed about this point. 'Inflate' an ellipsoid, centred at this point, according to these axes until it collides with something. Any collision point can be your centre.To clarify...By principle axes - you mean the axes local to the aptly names vertex soup so that z = mean normal?So vectors/lines/rays are sent out from the centroid normal to the z-axis (ie along the xy plane?) until collision occurs?Quote:In the case of a sphere, any point will be the result.For a cube, this solves to any face centre.Yup - already discounted enclosed surfaces, especially symetrical ones, becuase the point I need must lie on the surface. I think if you take 1 vert away it might asymetrise (if there is such a word) the surface enough to put the mid-point somewhere opposite this new void.That is not really the point of what I'm up to though.Quote:A plane; the centroid.A cylinder; its equator.Again cylinders are whole shapes, not just surfaces so no need. Planes - well yup that's what happens when a 3D surface gets projected: a plane with limits, so that's useful.Quote:A nose, somewhere in the bridge, or one of the sides if it's a particularly flat nose.Now this I like! An irregular shaped surface with no holes in the middle.Quote:The biggest problem I see is with an ellipsoid: the result is the whole surface, rather than its smallest circumference, as one may hope. To solve this, you could take square-roots (or something) on the magnitudes of the principal axes.Think I'd just treat it as a plane. Solid (whole ones) though go in the catagory with spheres, cylinders etc: enclosed surfaces are not of concern at this point!Quote:Practically, however, I think you need to rethink the problem. Given any proposed answer, one could contrive a surface on which it fails miserably. Could you perhaps tell us what you plan to use this algorithm on? This will be used to determine a mid-pont on a small patch that has been extracted from existing geometry.Original geometry is 3D scan of a face which is very fine-detail. Once the scan has been loaded into a 3D veiwing environment, users are asked to plot where they think certain positions are on the face.Taking the example of the tip of the subject's nose and with 50 plots of the subject's scanned face, it is likely that a number different positions will emerge as the perceived tip of the nose. These positions make up a patch for which I need to find the mid-point.Typical patch may resemble the one described by the nine points I mentioned earlier, althought this is quite regular in its form and has no concave edges or other troublesome stuff.Quote:Maybe we could suggest an alternative.RegardsAdmiralHope that helps 0 Share this post Link to post Share on other sites
Mastaba 761 Report post Posted November 10, 2006 Quote:Original post by Will-OQuote:Original by MastabaThe first step to the solution is define precisely what one means by mid-point.For a 2D surface, the mid-point can be found simply: it's the centroid. Don't be so quick! Given the presence of a hole, the centroid may not be on the surface. The best you could do is make one or more cuts of such a surface and create a set of centroids. But then the problem becomes even more complicated, because the centroids are relative to the cuts you take.[Edited by - Mastaba on November 10, 2006 11:25:40 AM] 0 Share this post Link to post Share on other sites
TheAdmiral 1122 Report post Posted November 10, 2006 Hi Will-O.Your interpretation of my liberally coined 'principal axes' was right on the money.Quote:Original post by Will-OThis will be used to determine a mid-pont on a small patch that has been extracted from existing geometry.Original geometry is 3D scan of a face which is very fine-detail. Once the scan has been loaded into a 3D veiwing environment, users are asked to plot where they think certain positions are on the face.Taking the example of the tip of the subject's nose and with 50 plots of the subject's scanned face, it is likely that a number different positions will emerge as the perceived tip of the nose. These positions make up a patch for which I need to find the mid-point.Typical patch may resemble the one described by the nine points I mentioned earlier, althought this is quite regular in its form and has no concave edges or other troublesome stuff.I see. Then perhaps a projective method would be better. If you drew a closed path around a portion of my face (please don't) and asked me to put a dot in the 'centre', I'd probably (subconsciously) do something like this: Find the viewing angle that minimises the area of the patch (i.e. 'get a good view'), pick the interior point that maximises the mean (or perhaps RMS) distance to the bounding curve.Roughly translating this to the current setting, and fixing for some exceptional circumstances, we get exactly erissian's method [rolleyes]:1. Find the mean face normal and project the patch along this. 2. Calculate a centre of this patch, again, probably an area-weighted mean of the triangle centres.3. Unproject back along the mean normal to the 3D patch.4. Pray that the result exists and is unique.I can't think of an example where this doesn't give excellent results, when the projection is convex. Now to deal with the concave case:If you want a truly reliable method, you'd create a uniformly-parameterised closed spline that fits on (or snugly in) the perimeter of the projected patch, take uniform samples along this spline, and numerically compute the interior point that minimises the distance to these samples.This sounds like a headache to me.As a looser alternative, I imagine the un-normalised 2D analogue of my 'inflating ellipsoid' method would do reasonably well. That is, inflate a circle about the visiocentre (yes, I made the name up - it's the centre calculated above) until something collides.I don't think it's appropriate to employ the canonical axes in this case, as the weighted mean takes care of appendages.RegardsAdmiral 0 Share this post Link to post Share on other sites
oliii 2196 Report post Posted November 11, 2006 I dont really get what you mean by mean point, but say, calcualte the average mean, calculate the eigen vectors of your mesh, trace a ray along the smallest vector -> point?There may not be a solution, if you have holes or some freakish mesh. 0 Share this post Link to post Share on other sites
smc 292 Report post Posted November 12, 2006 Quote:Original post by Will-OQuote:Original from smcThis is correct and it is the center of the surface bounded by the rectangle.This was trivial being that sin is smooth, semetrical and uniform, not to mention I chose convieniant bounding parameters. I am still not sure if this will work with arbitrary shapes. I am interested to know if it will.Ahh - but you got something working. This is a simple case because you can project along the z-axis (which I think is the mean normal to the surface) and don't have to find another normal but it works. Nice. This surface is mathematically defined, rather than merely by a set of points so doing some of the calcs might have been easier?I'm going to spend some time later having a look at this with the 9 points I put up here yesterday.The calculation was easy because the projected shape was a rectangle. In your case it should still not be terrably difficult to find the centroid of the projected polygon. The calculations would be the same. The problem is you would need to define the projected polygon in terms of an equation due to the fact finding the centroid requires integration. However, there is probibly a nice numerical way to do it.I realy think the previous post by oliii is on the right track. Talking briefly with my math professor, he suggested the same. 0 Share this post Link to post Share on other sites