PDA

View Full Version : Find the corners of an object


prettyPixel
02-16-2005, 01:29 PM
Hello. Does anybody know a simple algorythme to find 4 corners of an object 3D? (naturally my object is similar of a rectangle but not completely)
I have write a routine but it is sloooow and complex.
First I find the openEdge of my object and after I use a test based on the combination of series of 4 points: more there is of points more that becomes slow :-(

Of course I use angles but it is not also simple. Example:
http://users.skynet.be/arketip/CGtalk/U2.jpg

Can anyone help?
any idea would be really appreciated :thumbsup:

ThE_JacO
02-16-2005, 01:57 PM
it would help a lot if you could shrink down the amount of cases you will have to consider or provide more details about what you expect your routine to do.

will it always be something sitting on a plane and finding it's 4 corners?? or could it be that you will have to find corners of a box, and not just a rectangle?

for what you SEEM to want to do all you'd need is finding out the optimal bounding rectangle (or box) and picking the closest points to each corner, but it could very well be that just your example or your wording are simple in nature, while the scope of the project and potential objects ia a lot larger and more complex.

prettyPixel
02-16-2005, 03:37 PM
Yes you are right.
I am going to give you concrete examples of my project.

First here is my project:
http://www.cgtalk.com/showthread.php?t=210233

It is a tools for apply mapping coordinates.
First of all I search the 4 corners in my object...
In many case, the object to map is approximately flat (not a full 3D object as a box)
The goal is to find the 4 corners of this type of objects.

http://users.skynet.be/arketip/CGtalk/morphMap-formS.jpg

http://users.skynet.be/arketip/CGtalk/morphMap-circle-flag.jpg

(the current routine is too slow)

How make you to find the optimal bounding box ?
I can't use "standard" bounding box (aligned on the grid) because my object can be turned by 45 for example.

Thank you for your answer :thumbsup:

mummey
02-16-2005, 03:54 PM
1. Identify max and min coordinate values.

2. Create a list of points that contain at least one of those values.

3. Grab four points (each one contains a max/min value). Test its bounding box area.

4. Return the four points with the smallest area.

prettyPixel
02-16-2005, 05:15 PM
Thank you very much for your help mummey :-)
I am going to write this routine...

Have a good day

ThE_JacO
02-16-2005, 09:51 PM
Thank you very much for your help mummey :-)
I am going to write this routine...

Have a good day

I'm replying in this thread because I don't follow the max forums, so I'd forget and/or loose sight of the topic if it turns out to be interesting.

first things first, about your question regarding other apps, XSI has a subprojection method that does exactly what you are trying to do, HDN has a pretty damn powerful pelting since one or two versions (and before that I think there were a few SOPs hanging around) and I think Maya has some pelting scripts around, but don't quote me on that.
One of the operational algorithms I've seen in both XSI and HDN is called walking on the mesh, even accademically I think.

I don't know how much user input you require, or want to require, and to what degree you want this to be effective and automated, but what you are trying to do is basically automatic the most simple pelting tasks.

pelting is part of an unwrapping process that helps dealing with polys very much in the same way UVs are handled on surfaces.

by asking the user to pick corners of their mesh walking (imagine the object like wrapped paper and identify the corners basically, it's very visual so even non coding savy users don't have much of an issue with this in my experience), you can figure out edgeloops and or poly patterns connecting the corners, from those you can approximate a wrapping surface (easily generated in memory by standards, no need for the app to support surfaces like Maya, HDN or XSI) and map that surface by its UVs in a second.

then you can either walk the surface and project on the polygons (can be tricky and could need approximation to stitch the discrete elements) or simply raycast from each poly's vertex, along its normal, and fish the surface's UVs (won't always be as smooth but will always end up with perfect seamless mapping).

this is, in a nutshell, at the base of pelting for texturing.
It could very well be what you are trying to do (from what I saw in the post you seem to already have had some pretty good results anyway).

prettyPixel
02-17-2005, 01:12 PM
Thank you very much for all your precisions :thumbsup:
It helps me to understand better what I make.

I ignored that XSI could make that. It is really an great tool for a 3D artist.
Why? In the creation of a video game or an interactive presentation, I often create complex objects. It is not possible to keep UV "clean" during the modelling phase. Then to be able to put them later is the ideal solution.
But with a planar mapping for example, it is necessary to edit the mapping coordinates manually. It is a long work, uninteresting and demotivating... Then why not write a program which made it in a single click ;)
I am not a programmer. I have already asked to the programmers to create a utility as this one but they do not want to make it, then I decided to make it myself.


by asking the user to pick corners of their mesh walking (imagine the object like wrapped paper and identify the corners basically, it's very visual so even non coding savy users don't have much of an issue with this in my experience), you can figure out edgeloops and or poly patterns connecting the corners, from those you can approximate a wrapping surface (easily generated in memory by standards, no need for the app to support surfaces like Maya, HDN or XSI) and map that surface by its UVs in a second.

This algorythm "walking on the mesh".. yes i believe that is exactly what I am going to make ! :) In the concept at least... I don't know How this algorythm really works. For example I don't use edgeloops or poly patterns...
Where can we find this algorithm? I am very interested to compare it with mine.

I'm tring to obtain a perfect seamless mapping.
Mine work in this way:
1- I look for 4 corners of the shape
2- I deduct the 4 borders
3- I created a virtual grid on my object (by connecting the opposite borders)
4- I estimate the position of every vertex on this grid
5- I create UV coordinates
And Yes that's working already...

But the automatic detection of corners is slow for example and not working in all cases.
I use a combination of 5 tests to find corners (Are you interrested by this subject ?). It is complex. I would like to find a faster and more reliable routine. As I program in maxscript, I have to find fast routines.

For the moment the algorithm works only on the flat forms and with some 3Dshapes but not all. I know how to avoid this problem but I miss time to make it (i'm not a programmer and that takes time to me)
Do you know a good website about the base of pelting for texturing ? I am interested to teach it much more this subject.

( I hope that you understand me because my english is not very good lol )

dantea
02-24-2005, 02:02 PM
I think the jaco was referring to OBB (Oriented Bounding Box) ... google that.

CGTalk Moderation
02-24-2006, 03:00 PM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.