COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### Finding the neighbours of a triangle

• Email
• Follow

I have a file containing first a list of vertices (vertex number, x-,
y-, z-coordinates) and after that a list of triangles (triangle-number,
and three vertices) and all together this represents some 3D-models.
I'm to read this in to perform some simulations on those models and for
each triangle I will need to know it's three neighbours (the triangles
which share an edge). What I need is some way to find those neighbours
fast.

Another way to formulate the problem would be to say that I have a
number of triplets of numers (the triplet being the triangle and the
number the vertex) and I need to find all triplets that have two
numbers identical to those of a specific triplet. And than do it for
all triplets.

My current plan is to make a mapping from vertex number to triangle
while reading them in. For each vertex this will give me a list of all
triangles using that vertex. And from that list search for those that
have a second vertex in common.

Does anyone have any better idea of how to solve this problem?

PS: No mail replys please, I won't be able to check my mail for a
while.

--
Erik Wikstr=F6m

 0
Reply eriwik (511) 11/8/2006 1:08:15 PM

See related articles to this posting

On Wed, 8 Nov 2006 eriwik@student.chalmers.se wrote:
>
> I have a file containing first a list of vertices (vertex number, x-,
> y-, z-coordinates) and after that a list of triangles (triangle-number,
> and three vertices) and all together this represents some 3D-models.
> I'm to read this in to perform some simulations on those models and for
> each triangle I will need to know it's three neighbours (the triangles
> which share an edge). What I need is some way to find those neighbours
> fast.
>
> Another way to formulate the problem would be to say that I have a
> number of triplets of numers (the triplet being the triangle and the
> number the vertex) and I need to find all triplets that have two
> numbers identical to those of a specific triplet. And than do it for
> all triplets.
>
> My current plan is to make a mapping from vertex number to triangle
> while reading them in. For each vertex this will give me a list of all
> triangles using that vertex. And from that list search for those that
> have a second vertex in common.
>
> Does anyone have any better idea of how to solve this problem?

No, your method sounds as good as any, to me. But you can speed it up
over a large number of queries by keeping a copy of each computed result
attached to the triangles in question:
[UNTESTED CODE]

struct triangle {
vertex v[3];
triangle *opp[3];
};

void fetch_neighbors(const triangle *in, triangle *neighbors[3]) {
int i, j;
for (i=0; i < 3; ++i) {
if (in->opp[i] == NULL) {
/* After enough queries, this won't need to execute. */
vertex shared_a = in->v[(i+1)%3];
vertex shared_b = in->v[(i+2)%3];
triangle *neigh =
do_tedious_search(shared_a, shared_b, in);
for (j=0; j < 3; ++j)
if (neigh->v[j] != shared_a && neigh->v[j] != shared_b)
neigh->opp[j] = in;
}
neighbors[i] = in->opp[i];
}
return;
}

This was probably obvious to you already, but since you didn't mention
caching the results, I thought it was worth pointing out.

-Arthur
 0
Reply ajonospam (382) 11/8/2006 5:26:48 PM

eriwik@student.chalmers.se wrote:
> Does anyone have any better idea of how to solve this problem?

If there are lots of triangles in a set then using balanced binary trees or
hash tables will be faster than linear search. However, this is not the
case if your models are essentially meshes.

--
Dr Jon D Harrop, Flying Frog Consultancy
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists
 0
Reply jon (3344) 11/9/2006 1:47:26 AM

Arthur J. O'Dwyer wrote:

> On Wed, 8 Nov 2006 eriwik@student.chalmers.se wrote:
> >
> > I have a file containing first a list of vertices (vertex number, x-,
> > y-, z-coordinates) and after that a list of triangles (triangle-number,
> > and three vertices) and all together this represents some 3D-models.
> > I'm to read this in to perform some simulations on those models and for
> > each triangle I will need to know it's three neighbours (the triangles
> > which share an edge). What I need is some way to find those neighbours
> > fast.
> >
> > Another way to formulate the problem would be to say that I have a
> > number of triplets of numers (the triplet being the triangle and the
> > number the vertex) and I need to find all triplets that have two
> > numbers identical to those of a specific triplet. And than do it for
> > all triplets.
> >
> > My current plan is to make a mapping from vertex number to triangle
> > while reading them in. For each vertex this will give me a list of all
> > triangles using that vertex. And from that list search for those that
> > have a second vertex in common.
> >
> > Does anyone have any better idea of how to solve this problem?
>
>    No, your method sounds as good as any, to me. But you can speed it up
> over a large number of queries by keeping a copy of each computed result
> attached to the triangles in question:

Yes, I hunt down the neighbours right after parsing the input files and
store them along with the triangle as you said.

Jon Harrop wrote:

>If there are lots of triangles in a set then using balanced binary trees or
>hash tables will be faster than linear search. However, this is not the
>case if your models are essentially meshes.

Yes, they are normal meshes and I've never seen any more than 7
triangles sharing a vertex so I don't see that as a performance
bottleneck. In fact, it takes longer to read in and parse the input
files than it takes to find all neighbours.

--
Erik Wikstr=F6m

 0
Reply eriwik (511) 11/9/2006 3:04:31 PM

3 Replies
25 Views

Similar Articles

12/12/2013 2:04:14 AM
[PageSpeed]

Similar Artilces:

find in which triangle algorithm
Hello, I have a matrix of points, and a simple patch of triangles. I have the indices of those triangles and the coordenates of the vertices. I need to find in which of the triangle, is each point. p is the matrix with the points tri are the indices of the triangles in the form [12 13 14, 21 2 3, etc] face_triangulos are the coordinates of the points which formed the triangles I am assinging for each point the form [x y z T], where T is the triangle in which the point is contained. z is always zero .. p = [p, zeros(size(p,1),1)]; for I=1:size(tri,1) for J=1:size(p,1) ...

m-file function to find the area of the triangle
1)Write an m-file to find the area of the triangle for a given three corners of a triangle by using cross product in R^3. Hint: write a subfunction which evaluates the determinant of a matrix 2)Write an m-file function which finds the rank and the nullity of a given mxn matrix. Do not use rank function of matlab. Write your own function. Hint: Reduce the matrix to a row echelon form and count the number of basis of column space or row space. Then use the theorem which states rank(A)+nullity(A)= number of columns of A Um, no thank you. Especially after I see the part that says "Write ...

How to exclude action of Find::Find::find in subdirectories with known names? 136296
I must pass through directory tree and to execute some action with files, names of which described by regex. I need not do it in directories SCCS and VVS, which can be in every subdirectory. The following code works correctly, does not action ("THE ACTION") in unwanted directories, but it pass through every subdirectory. I'd would like that it will worked faster, and procedure "wanted" will not step inside SCCS and VVS. I have tried for that purpose the "untaint_pattern" and "untaint_skip" options but did not success. Perhaps I used incorre...

Re: Found a Find.find() bug?
Sorry, there was a typo in my e-mail. One should be "/tmp" and the other should be "/tmp/" And yes, I am using this on Mac OS X where /tmp is a symlink to /private/tmp. Should Ruby care about symlinks? IMHO, it should work whether or not it is a symlink or not. On 15.02.2007 23:25, robertlaferla@comcast.net wrote: > Sorry, there was a typo in my e-mail. One should be "/tmp" and the other should be "/tmp/" > And yes, I am using this on Mac OS X where /tmp is a symlink to /private/tmp. > Should Ruby care about symlinks? IMHO, it should ...

Find and delete a line, problems finding
I got my first PERL project last Monday and have written 3 pages of working PERL, but 1 page is driving me nuts! I am very much a newbie, so please have patience with me. below is a snippet of my code that is having problems. open(LISTFILE, "<.ccglist"); open(TEMPFILE, ">.tempfile"); while (\$line=<LISTFILE>) { print TEMPFILE \$line unless \$line =~ (/\$accountnumber/ && /\$effectivedate/); } close TEMPFILE; close LISTFILE; unlink ".ccglist"; rename ".tempfile", ".ccglist"; I have finally got the deleting of a line ...

I got confused by the following information from the help for "FIND": find(s, *args) find(s, sub [,start [,end]]) -> in what does *args mean (especially the '*')? also, in the sub, why put a comma before start? what does 'in' mean? ...

Find.find --- returns directories/files backwards
New user question: It seems to me when I run: Find.find('/user/name/documents') {|path| puts path} it returns all the directories in the reverse order. I was expecting the directories to be returned in alphabetical order, but that doesn't seem to be the case. Also, in one case it reads half of a directory's files, then the sub dirs and then it finished reading the rest of the directory it started in and finished writing them in the Puts statement. Am I missing something? How do you do get it to write out the directories in alphabetical order? Any and all help welcome. Th...

Passing paramaters to the File::Find find() function
I've just used the File::Find module for the first time. I can't figure out how to pass variables into the find() function. Here is a trivial example (I know that what this does can be done many other better ways, but it was about the smallest bit of code that I could come up with which illustrates my problem) The point is that \$mytext and @myfiles both have to be global variables since there doesn't seem to be a way of passing them from the testclpm7() sub to the pushfiles() sub via the find() call. Is it possible to pass values through so I can avoid having to use global vari...

find/replace a word in multiple files with find/awk
Hello all, I've got a problem that I could do in Perl, but since I'm sorta learning awk (at least following this newsgroup), I would like to know how to do it in awk. The problem is that I've got a bunch of C source files (from Stevens' Unix Network Programming) that have a structure in them (in_pktinfo) that is now a real system structure in Linux, so I get redefinition errors while compiling. Well, I can just comment out that structure since I don't use the functions (yet) that require it, but the two structures are not compatible, at least not in definition, so at som...

where to find gnu tools like find and grep on Solaris?
Hi, Do you know where I can download pre-compiled GNU version tools like grep, find and sed on Solaris? I have some BASH script all were written according to GNU tool command options. If the pre-compiled version is hard to find, do you know where I can download the source? Thanks. <linq936@hotmail.com> wrote in message news:1141010441.816306.235210@e56g2000cwe.googlegroups.com... > Hi, > Do you know where I can download pre-compiled GNU version tools like > grep, find and sed on Solaris? > > I have some BASH script all were written according to GNU tool >...

find-name-dired and find-dired fail on windows/cygwin
Hi I am trying to find (say a *.cpp) file using either one of the commands. For find-name-dired I get: find . \( -name '*.cpp' \) -exec ls -ld {} \; find: missing argument to `-exec' find exited abnormally with code 1 at Thu Jan 26 19:00:29 For find-dired I get: find . \( -name '*.cpp' \) -exec ls -ld {} \; find: missing argument to `-exec' find exited abnormally with code 1 at Thu Jan 26 19:02:42 It I make bash.exe a shell by setting: (add-hook 'comint-output-filter-functions 'shell-strip-ctrl-m nil t) (add-hook 'comint-output-filter-functions...

FMP Unlimited stays in Find mode after web user performs CDML find
This has been bugging me for months, but I am just getting around to asking others about it. I have a big FM system for in-house users, a portion of which is usable by people outside via a FMP Unlimited 6/CDML system running on a single Mac that is a normal LAN guest of my server. Typical stuff. I find that whenever a web user performs a Find for records, the corresponding file on the Unlimited machine is always left in Find mode aftwards. This normally is no big deal at all--of course the web machine is not used by anyone here--but it is annoying for me during troubleshooting or when I am ...

"Find" Doesn't find Mac OS Updates on all volumes

Do you find this weird too?
Hi there, hope this gets through to you guys, now with all the spam and whatnot. Anywho, maybe this has come up before, here is some code aa = randomu(12L, 200, 100) ff = findgen(100) maxs = max(aa, maxind, dimension=2) print, maxind[0:10] help, ff[maxind[0:10]] plot, ff[maxind[0:10]] Now I find this weird, because maxind is an array of longs clearly bigger than the size of ff but IDL does not complain and plots something (btw not what I want but this is solved with array_indices). Is this something to do with the fact that maxind is a 1D representation of 2D array indices? I hope it is bec...

Where to find grammars for...
Currently I'm looking at the build process as used for many GNU programs. A couple of languages are involved in the overall process, starting with the bash (or other shell) grammar, automake, configure, m4, make etc. Even if all these tools are more or less well described, I would like to have more precise grammars for all these languages. Any pointers? Thanks, DoDi [There's most of a BNF grammar for bash in its man page. Other than that, I doubt there's formal grammars for any of them. -John] > Currently I'm looking at the build process as used for many GNU > progr...

Finding IP
I have a FC4 box running as a web server with an internal IP 192.168.1.5 running behind an ADSL router connected to the 'net via a dynamic IP. I have a domain which is hosted by a company and any requests to that domain name get sent to a Perl script running on those machines, which looks up its most recent record of my server's IP in a text file and redirects to my machine. The router receives the request, and my FC4/Apache box is set up as a DMZ host so it receives the requests. Problem is I have a cron script running on my local server which updates my local server/router's IP...

Find command
I wanna find some files in solaris 10. I don't remember full name of them so I wanna look for all files which have "abc" (example) in their name. How can I do? I tried this command but it only show me the file name match exactly with my pattern #find / -name abc -print I also read the man pages but not clear :( Thx in advance SauDoi wrote: > I wanna find some files in solaris 10. I don't remember full name of > them so I wanna look for all files which have "abc" (example) in their > name. How can I do? > > I tried this command but it only show m...

Restore Find
I have a simple "enter find" and "perfrom find" script. Sometimes it runs fine, then sometmes it will come back with a "restore find" that I did not intend for it to do. Using FM7 v3 Thanks JC JC <jc@jclewis.biz> wrote: > I have a simple "enter find" and "perfrom find" script. Sometimes it > runs fine, then sometmes it will come back with a "restore find" that I > did not intend for it to do. Error capture on or off? -- http://clk.ch Error capture is "On" Thanks jc In article <1133295140.200369...

Finding executables
Don't you love auditors, they want me to prove that no executables have been modifed in the past year. I know how to find all files modified in the last year (find . -mtime 365 -print) but I am not sure how to locate executables within that search. thanks for any advise. So basically according to these auditors, you are not allowed to have any security updates for your software? Chad wrote: > Don't you love auditors, they want me to prove that no executables have > been modifed in the past year. I know how to find all files modified in > the last year (find . -mtime 365 -...

finding files?
I just scanned a bunch of images into PSP7 and saved to a folder with several images in it. They are all .tif and .jpg. I thought it a little weird that the new ones didn't show up in the browser, but even stranger that they don't show up in the file open dialogue. But they are there in my file manager, and they open in Irfanvu. Obviously this makes the program useless to me. Anybody have any hints on what's happening and how to fix it? Thanks for anything on this. Arthur Arthur wrote: > > I just scanned a bunch of images into PSP7 and saved to a folder with > severa...