CGTalk > Technical > Graphics Programming
Login register
Thread Closed share thread « Previous Thread | Next Thread »  
 
Thread Tools Search this Thread Display Modes
Old 04-28-2005, 01:55 AM   #1
billrobertson42
Frequenter
portfolio
Bill Robertson
Ohio, USA
 
Join Date: Jan 2005
Posts: 257
How to figure out points that are close to each other in an arbitrary set of points

Ok, I'm sure I'm not the first with this idea...

I'm working on a plug-in to align points that are "close enough" to each other points from an arbitrary set of points. For example, you're working on a model that consists of multiple mesh objects and you want to make sure that the edges of the various meshes line up exactly. You select the points on the matching edges, and if they're within a given tolerence the postion of those two points will be averaged.

In order to avoid having to compare the location of every point to every other point in the set I want to group them so I only have to compare the locations of those that are close to each other. My cunning plan is to create a sparse matrix and the location of each point will be specified by the original coordinate divided by the tolerence. And then traverse through the sparse matrix looking for clusters of points that might be close enough and then average them.

Does this make sense?
 
Old 04-28-2005, 09:01 AM   #2
playmesumch00ns
Lord of the posts
 
playmesumch00ns's Avatar
render monkey
pretty picture maker
United Kingdom
 
Join Date: Jul 2002
Posts: 3,420
I'm not sure I entirely understand how you would construct this matrix. Without having a clear picture in my mind it's hard to judge how effective it would be...

The standard (and proven) way of doing this would be to use a Kd-tree (google for it). This is a heirachical spatial data structure that allows you to quickly find points in space near to a specified search point. A good Kd-tree implementation is a very useful thing to have around as you can do all sorts of things with it.
__________________

You can have your characters photoreal, fast or cheap. Pick two.
 
Old 04-28-2005, 10:58 PM   #3
billrobertson42
Frequenter
portfolio
Bill Robertson
Ohio, USA
 
Join Date: Jan 2005
Posts: 257
I guess what I was considering would have been sort of like re-mapping the coordinates of the points to a lower resolution coordinate system.

I figured that there had to be a more standard (i.e. proven) way of doing this though. I'll check out the kd tree.

thanks
 
Old 04-28-2005, 10:58 PM   #4
CGTalk Moderation
Lord of the posts
CGTalk Forum Leader
 
Join Date: Sep 2003
Posts: 1,066,481
Thread automatically closed

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.
__________________
CGTalk Policy/Legalities
Note that as CGTalk Members, you agree to the terms and conditions of using this website.
 
Thread Closed share thread


Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
CGSociety
Society of Digital Artists
www.cgsociety.org

Powered by vBulletin
Copyright 2000 - 2006,
Jelsoft Enterprises Ltd.
Minimize Ads
Forum Jump
Miscellaneous

All times are GMT. The time now is 05:21 AM.


Powered by vBulletin
Copyright ©2000 - 2016, Jelsoft Enterprises Ltd.