Tell me more ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.
up vote 2 down vote favorite

Currently I'm working on a basic 3D model viewer in MATLAB, which can import .OBJ files (modeled in e.g. Blender). The purpose of this viewer is to test different subdivision schemes (like Catmull-Clark, or Doo-Sabin). A subdivision scheme is basically a method to convert a mesh to a smoother (refined) mesh.

In order to do this properly, I would like to implement some functionality to select Vertices and Edges in my viewer.

Vertex selection isn't very hard -- the way this works is that when I click somewhere in the viewer, MATLAB provides me with two points, the begin- and end points of the line perpendicular to the screen (by clicking on a 2D screen that depicts a 3D scene, you actually click on a line, not a single point). Using this method it is relatively simple to find the closest Vertex.

However, I'm not quite sure how to do the same for an Edge. Imagine that the imported geometry is a simple cube, so 8 Vertices and 12 Edges. If I know click on an arbitrary point in the viewer (i.e. on some line perpendicular to the screen), how can I then determine which of the 12 Edges is the closest one?

[First Edit] Just to be clear, I'm not really looking for a piece of (MATLAB) code, but rather for some theoretical explanation (or just a reference to an article/book/website). Thanks!

[Second Edit] By the way, is this the correct place for such a question? Or might the Mathematics or StackOverflow boards be better suited?

share|improve this question

1 Answer

up vote 1 down vote

A similar question has actually been posed on stackoverflow before and is answered there (with matlab): http://stackoverflow.com/a/702174/545346

Edit: I was actually thinking about writing something about spatial indexing, but I then thought it was not necessary since you spoke about 12 edges.

A logical approach would be a filter using the distance of both vertices to your new line: if you have found an edge with both vertices further away from your line than a previous edge you are sure that the second edge will not be the closest one, so you don't need to do more advanced calculations.

A more advanced procedure would actually use spatial indexes to make sure not too many combinations are used. A good start could be http://en.wikipedia.org/wiki/R-tree

Anyway, this is not something you generally want to implement yourself: you could check out postgis, which has support for 3d objects.

share|improve this answer
Thanks, I noticed that topic earlier today. Basically it determines the minimal distance from the line to each edge, and subsequently it looks for the minimum value in the list of distances. The thing is, when there are many edges (i.e. a couple of hundreds or even thousands), this method will be quite slow. Probably should have mentioned that I'd like the method to be generally applicable :) – Ailurus Oct 7 '12 at 21:45
The 12 edges were just an example, I'd like to apply the selection procedure on a general model (with a lot more edges). I'll take a look at the filter and the R-tree, thanks for adding these suggestions! – Ailurus Nov 11 '12 at 13:29
By the way, why a spatial data partitioning tree (e.g. R-tree) and not a binary space partitioning tree (BSP tree) or something else? – Ailurus Nov 13 '12 at 12:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.