Hi,
is there an algorithm that creates indexing for a given set of vertices, so there will not be any intersection between the triangles? I found an algorithm that creates an external outline that connects a group of dots, but this is on 2d, there must be one for 3d, anyone heard of such a thing? I would search for it, but I need a name for the algorithm.
Algorithm that creates indexing for a given set of vertices
(21 posts) (4 voices)
Posted 2 weeks ago #

delaunay triangulation
Posted 2 weeks ago # 
Triangulation is an essentially 2D operation. Your vertices may be arranged in 3D but you are thinking of them as a 2D surface if you want to generate triangles from them.
So you can use Delaunay triangulation, as that is a 2D algorithm. There are a couple of ways to go about it.
Simplest is map the 3D data to 2D. There are a large number of projections you can use to do this; many were discovered by cartographers looking to create flat maps of the round Earth – search for 'map projections' for examples of them. Or use one or more linear projections. A matrix of the form
a b 0 c d 0 e f 0
will map 3D coords to 2D coords in the xy plane
The other way is use an algorithm like Delaunay triangulation but in 3D, using 3D distances instead of 2D. I am not sure how easy this would be, without looking closely at some algorithms. You might find someone has already done this. It would only work with some sorts of surfaces.
Posted 2 weeks ago # 
So what you are basically saying is that delaunay triangulation is a 2D algorithm, not a 3D one, and I need another algorithm to project the 3d structure to a 2D surface like it was spreading its skin. what is the name of such an algorithm?  that Strips the skin off an object and spread it?
Posted 2 weeks ago # 
So you mean like uv mapping/unwrapping?
If so just search for uv mapping or unwrapping algorithms.
I dont think any are perfect and are probably quite complex to get a decent result.
If you only want it for an effect maybe you could project each vertex onto a bounding sphere, then unwrap that into a flat rectangle and use that as the final mapping?
Maybe you could use a tool like blender to do the unwrapping and use the generated uvs?
Posted 2 weeks ago # 
Delaunay triangulation is not 2D(only) algorithm, due the implementation of 3d will probably have different optimizations.
Posted 2 weeks ago # 
So what you are basically saying is that delaunay triangulation is a 2D algorithm, not a 3D one, and I need another algorithm to project the 3d structure to a 2D surface like it was spreading its skin. what is the name of such an algorithm?  that Strips the skin off an object and spread it?
I mentioned map projections earlier. They are designed for mapping e.g. the Earth but many work in ways that mean they can map arbitrary objects onto a flat surface. Or raycast your object onto a sphere by normalising each coordinate before using a map projection.
https://en.wikipedia.org/wiki/Map_projection
Some have properties that are useful in this case. E.g. a conformal mapping preserves angles. This means small shapes look the same once mapped. Delaunay triangulation works by considering [small] circles around triangles, so a mapping that maps small circles to small circles would work well for it.
Posted 2 weeks ago # 
found this page, an as3 library that contains these algorithms, but the link to demo is broken, need a demo to see how to work with this library.
Posted 2 weeks ago # 
Which page?
Posted 2 weeks ago # 
this one:
http://nodename.github.io/as3delaunay/Posted 2 weeks ago # 
This archive.org capture seems to work
https://web.archive.org/web/20140807233250/http://nodename.com:80/blog/2009/05/11/avoronoitoy
Posted 2 weeks ago # 
this demo does work but it doesn't provide the source code, I need to see an example so I know how to use the library. found this library on github: https://github.com/nodename/as3delaunay
But no example code and no documentry.
Posted 1 week ago # 
It just shows one way it can be used. What you are trying to do is very different, the only thing in common is the underlying Delaunay/Voronoi algorithm, which is in the Github repository:
https://github.com/nodename/as3delaunay
I would download that, go through it and try and work out how you would use it. You can also look at some of the other links from the link you posted.
Posted 1 week ago # 
found an example
package { import com.nodename.Delaunay.Voronoi; import com.nodename.geom.LineSegment; import flash.display.Sprite; import flash.events.Event; import flash.geom.Point; import flash.geom.Rectangle; public class Example extends Sprite { private var _points:Vector.<Point>; private var _plotBounds:Rectangle; private var _voronoi:Voronoi; private var _segments:Vector.<LineSegment>; public function Example() { if (stage) init(); else addEventListener(Event.ADDED_TO_STAGE, init); } private function init(event:Event = null):void { _points = new Vector.<Point>(); for (var i:uint = 0; i < 50; i++) { var point:Point = new Point(Math.random() * stage.stageWidth, Math.random() * stage.stageHeight); _points.push(point); } _plotBounds = new Rectangle(0, 0, stage.stageWidth, stage.stageHeight); _voronoi = new Voronoi(_points, null, _plotBounds); _segments = _voronoi.delaunayTriangulation(); for each (var segment:LineSegment in _segments) { graphics.lineStyle(2, 0x000000, 1); graphics.moveTo(segment.p0.x, segment.p0.y); graphics.lineTo(segment.p1.x, segment.p1.y); } } } }
now I need the uv map algorithm, to create the set of point as a projection of the 3d object
Posted 1 week ago # 
I thought it would be easy to find an algorithm for uv unwrap, seems to be a complicated task, I found some information about an algorithm called "Triplanar" is that something that can help me?
Anybody knows anything about this algorithm  "Triplanar"?
Posted 1 week ago # 
I was going to ask how you were getting on with finding a uv mapping algorithm. It’s not something I know about, as it’s not something I can think of a use for. Normally in 3D modelling the texture coordinates are generated by the 3D modelling application, based on the edits of the artist creating the model.
There’s no algorithm for it as there’s no one way to do it. This is easiest to describe with an analogy – dressmaking:
When a tailor comes to make a suit, or dress, they need to cut up and arrange the cloth as the human body is not flat. And there are many ways to do this. There are conventions for certain sorts of clothing but they are just conventions, easily broken  I would think we have all bought at some time clothes with seams in odd places.
And in 3D modelling there is far more freedom. Unlike in clothing, where cloth tends to lie a particular way so it stretches with movement, in 3D modelling if a texture does not line up you can modify the texture. A texture atlas for a 3D model normally contains bits of texture all jumbled up, flipped and rotated with varying scales, sometimes stretched and deformed to fit.
There is no way to automatically generate uv coordinates for such texture data, and so for texture data in general. There may be ways to generate uv coordinates for particular sorts of model: for e.g. a particular geometric shape. What sort of shape or shapes are you dealing with, and what sort of effect are you trying to achieve?
Posted 1 week ago # 
Hi John,
If you remember, I told you I have a unique mouse picking method, I give every object a bounding box generated automatically, or the 3d artist can make his own bounding box, and group it with the object, and if this object is called "boundingbox" my x3d viewer will replace the default bounding box with the one the 3d artist created, this bounding box gives the artist more control over the area that is sensitive to mouse clicking, so my bounding box is made up of 8 points, that don't have to be a cube, they can be of different shapes, I also created an object which is half transparent to show the shape of the bounding box around the object, just for testing. this object is shaped by the 8 points that make up the bounding box of the object, my problem starts when the bounding box of the object is shaped in a very twisted form, how do I know which point is the upper left, and which is the downright and so on, I used to sort the 8 points by their Y position, and assume the 4 upper ones are the top ones and the 4 lower ones are the bottom, but this works only if the shape is more or less cubic, not if it is twisted. so I'm looking for a way to create an object from a cloud of vertices, and I know in 3d max you can map an object and then unwrap it in to a 2d map, so mathematically this is possible.I ended up using a different method for mouse picking, I render all objects each with a color that is generated from the object index number in the objects array, then I use getPixel to find out the color under the mouse click, but I still want the other method to be optional for the 3d artist, and it will probably will be useful if I'll add a simulation feature, so I still want to find a way to project the 8 point object on 2d and will then use Voronoi
to connect them with triangles.Posted 1 week ago # 
and I know in 3d max you can map an object and then unwrap it in to a 2d map, so mathematically this is possible.
This sounds familiar. But if I am remembering it correctly, what happens is an artist builds a model with textures, pulled e.g. from a folder of art the’ve made, and slaps them on anyhow. Then when the model is exported it exports the textures as an atlas, putting them all in one bitmap, eliminating duplicates, rotating and scaling them to fit. The coordinates the patches of textures end up at become the uv coordinates.
Essentially it‘s a form texture packing, though different from most texture packing apps which work with rectangles and pack images 1:1. With a 3D model bits need not be rectangular, and they need not be 1:1 with the source material but might be scaled or stretched to fit in the atlas.
That’s the only mathematical operation I can think is part of this. Not sure if it useful, I can’t follow what you are trying to do with textures from your description.
Posted 1 week ago # 
I'm not doing anything with textures, I just want an algorithm that projects the vertices of a 3d object on a 2d surface, what I need is used for textures, so I thought maybe I can take the algorithm from there, if anyone know how it's done on textures uv unwrappers.
Posted 1 week ago # 
You only need uv coordinates for textures – if you are not texturing a model/mesh they are ignored – so it is unclear what you are trying to do. I have already described how I think 3D modelling apps work; I think it is a form of texture packing.
As for projecting a 3D object onto a 2D surface, the map projections mentioned earlier are the way I would do it. There are a large number of them for all possible situations. Some can be used with any data, some require a sphere so need e.g. coordinates normalised first.
Posted 1 week ago # 
It occurred to me you might be looking for an algorithm to unfold a model, when it’s considered as a polyhedron:
http://mathworld.wolfram.com/Unfolding.html
But no such algorithm exists. Not only are such unfoldings ‘tricky’ but it is an unsolved problem whether it is possible without overlaps for all convex polyhedra (it is definitely impossible for all nonconvex polyhedra).
It’s not something that normally arises in computer modelling. Textures can be stretched and distorted over an uneven surface, eliminating cuts needed to flatten a polyhedral net. The mapping can be cut into many pieces, to better fit into a texture atlas – there’s no need for it to be in one piece. And textures can be mirrored, repeated or used in multiple places, all things not found in normal paper models.
Posted 1 week ago #
Reply
You must log in to post.