## layout algorithm

### layout algorithm

Another question relating to a 3D world

In my 3D application, I draw objects.
Thoses objects are inter connected (by example a network).

I'd like to have a kind of auto-layout feature that would find the best way
of setting the position of the objects in the 3D space to avoid manual
positionning that can be time consuming on large worlds

The goal, of course, is to limit the crossing of connectors and to put an
object over another one :-)

Thanks
Thierry

### layout algorithm

Hi

Quote:> Another question relating to a 3D world

> In my 3D application, I draw objects.
> Thoses objects are inter connected (by example a network).

> I'd like to have a kind of auto-layout feature that would find the best
way
> of setting the position of the objects in the 3D space to avoid manual
> positionning that can be time consuming on large worlds

> The goal, of course, is to limit the crossing of connectors and to put an
> object over another one :-)

This depends very strongly on what your connectors are and how the graph is
arranged.  Assuming the connectors are flexible string-like things, and your
objects don't overlap or surround one another, you can always find a way to
very much.  Also, what do you mean by the "best way" to position the
objects?  Using the minimum volume?  That is an NP-hard problem.

The only thing I can do with this amount of information is suggest a general
approach where for each new object added to the graph, you pick a position
such that it does not intersect any other object, and then route its
connector(s) around the obstacles.  This is relatively easy to do with a
spacial subdivision tree.

If, on the other hand, you had some sort of *tree* (hierarchy) of objects
linked to their parents by rigid cylinders, then I could give you a more

Regards
David Turner

I'm looking for a fast 3-D graf layout algorithm which produces the same
result for a given input at all times (deterministic).

I've found references to the following on the web, please give comments if
You have any experience from any of these.

1. R. F. Cohen, P. Eades, T. Lin, and F. Ruskey. Three-dimensional graph
drawing. In Tamassia and Tollis [123], pages 1-11.

2. Kim M. Fairchild, Steven E. Poltrock, and George W. Furnas. SemNet:
Three-Dimensional Graphic Representations of Large Knowledge Bases, chapter
5. Lawrence Erlbaum associates, 1988.

3. T. Kamada and S. Kawai. A simple method for computing general position
in displaying three-dimensional objects. Computer Vision, Graphics, and
Image Processing, 41:43-56, 1988.

4. Can Keskin. Kombination von schneller heuristiken mit
constraint-verfahren zur erzeugung von graphen-layouts in 3-d.
Studienarbeit, Universit?t Karlsruhe, 1995.

5. S.P. Reiss. 3-D Visualization of Program Information. In R. Tamassia and
I. Tollis, editors, Graph Drawing DIMACS International Workshop GD '94,
number 894 in LNCS, pages 12-24. Springer Verlag, 1994.

6. Fast Interactive 3-D Graph Visualization, Ingo Bruss, Arne Frick,
Universit?t Karlsruhe, Fakult?t fr Informatik

Of which I've only got the hold of the last one, which is good except that
it's not deterministic.

/johan

2. cre/sre