241:
the scene graph (tree) to the child nodes, until a leaf node is reached. At this point, many scene graph engines then traverse back up the tree, applying a similar operation. For example, consider a render operation that takes transformations into account: while recursively traversing down the scene graph hierarchy, a pre-render operation is called. If the node is a transformation node, it adds its own transformation to the current transformation matrix. Once the operation finishes traversing all the children of a node, it calls the node's post-render operation so that the transformation node can undo the transformation. This approach drastically reduces the necessary amount of matrix multiplication.
487:
20:
103:. A layer acts like a transparent sheet upon which any number of shapes and shape groups can be placed. The document then becomes a set of layers, any of which can be conveniently made invisible, dimmed, or locked (made read-only). Some applications place all layers in a linear list, while others support layers within layers to any desired depth.
342:(BSP) trees are heavily favored to minimize visibility tests. BSP trees, however, take a very long time to compute from design scene graphs, and must be recomputed if the design scene graph changes, so the levels tend to remain static, and dynamic characters aren't generally considered in the spatial partitioning scheme.
357:, which are specialized variants of a 3D bounding box hierarchy. Since a heightfield occupies a box volume itself, recursively subdividing this box into eight subboxes (hence the 'oct' in octree) until individual heightfield elements are reached is efficient and natural. A quadtree is simply a 2D octree.
326:
model and build an internal representation that breaks up its individual parts into bounding boxes (also called bounding slabs). These boxes are grouped hierarchically so that ray intersection tests (as part of visibility determination) can be efficiently computed. A group box that does not intersect
307:
Spatial data is usually static and generally contains non-moving scene data in some partitioned form. Some systems may have the systems and their rendering separately. This is fine and there are no real advantages to either method. In particular, it is bad to have the scene graph contained within the
248:
For example, in 2D cases, scene graphs typically render themselves by starting at the tree's root node and then recursively draw the child nodes. The tree's leaves represent the most foreground objects. Since drawing proceeds from back to front with closer objects simply overwriting farther ones, the
240:
are the key to the power of applying operations to scene graphs. A traversal generally consists of starting at some arbitrary node (often the root of the scene graph), applying the operation(s) (often the updating and rendering operations are applied one after the other), and recursively moving down
136:
to reduce memory costs and increase speed. In our example above, each knight is a separate scene node, but the graphical representation of the knight (made up of a 3D mesh, textures, materials and shaders) is instanced. This means that only a single copy of the data is kept, which is then referenced
291:
There are some similarities between BVHs and scene graphs. A scene graph can easily be adapted to include/become a BVH – if each node has a volume associated or there is a purpose-built "bound node" added in at convenient location in the hierarchy. This may not be the typical view of a scene graph,
228:
Variations on these techniques exist, and new methods can offer added benefits. One alternative is scene graph rebuilding, where the scene graph is rebuilt for each of the operations performed. This, however, can be very slow, but produces a highly optimised scene graph. It demonstrates that a good
330:
A similar efficiency holds in 2D applications as well. If the user has magnified a document so that only part of it is visible on his computer screen, and then scrolls in it, it is useful to use a bounding box (or in this case, a bounding rectangle scheme) to quickly determine which scene graph
283:
or oriented bounding boxes). At the bottom of the hierarchy, the size of the volume is just large enough to encompass a single object tightly (or possibly even some smaller fraction of an object in high resolution BVHs). As one ascends the hierarchy, each node has its own volume that tightly
72:) at each group level and concatenating such matrices together is an efficient and natural way to process such operations. A common feature, for instance, is the ability to group related shapes and objects into a compound object that can then be manipulated as easily as a single object.
59:
structure. A tree node may have many children but only a single parent, with the effect of a parent applied to all its child nodes; an operation performed on a group automatically propagates its effect to all of its members. In many programs, associating a geometrical
168:
Applying an operation on a scene graph requires some way of dispatching an operation based on a node's type. For example, in a render operation, a transformation group node would accumulate its transformation by matrix multiplication, vector displacement,
385:
appears to have been the first commercial scene graph library provided by a single software vendor. It was designed to run on disparate lower-level 2D and 3D interfaces, with the first major production version (v3.0) completed in 1991.
287:
BVHs are useful for speeding up collision detection between objects. If an object's bounding volume does not intersect a volume higher in the tree, it cannot intersect any object below that node (so they are all rejected very quickly).
244:
Some scene graph operations are actually more efficient when nodes are traversed in a different order – this is where some systems implement scene graph rebuilding to reorder the scene graph into an easier-to-parse format or tree.
125:
For instance, a game might define a logical relationship between a knight and a horse so that the knight is considered an extension to the horse. The scene graph would have a 'horse' node with a 'knight' node attached to it.
204:, where each represents an operation that can be performed on a node. Virtual functions are simple to write, but it is usually impossible to add new operations to nodes without access to the source code. Alternatively, the
268:(BVHs) are useful for numerous tasks – including efficient culling and speeding up collision detection between objects. A BVH is a spatial structure, but doesn't have to partition the geometry (see
334:
Depending on the particulars of the application's drawing performance, a large part of the scene graph's design can be impacted by rendering efficiency considerations. In 3D video games such as
106:
Internally, there may be no real structural difference between layers and groups at all, since they are both just nodes of a scene graph. If differences are needed, a common type declaration in
257:, it is more efficient to draw the closest objects first, since farther objects often need only be depth-tested instead of actually rendered, because they are occluded by nearer objects.
193:
usually lacks portability, one might separate the scene graph and rendering systems instead. In order to accomplish this type of dispatching, several different approaches can be taken.
137:
by any 'knight' nodes in the scene graph. This allows a reduced memory budget and increased speed, since when a new knight node is created, the appearance data needs not be duplicated.
110:
would be to make a generic node class, and then derive layers and groups as subclasses. A visibility member, for example, would be a feature of a layer, but not necessarily of a group.
177:. After which a leaf node sends the object off for rendering to the renderer. Some implementations might render the object directly, which invokes the underlying rendering
217:). The operation can be realised as a class that is passed to the current node; it then queries the node's type using RTTI and looks up the correct operation in an array of
129:
The scene graph may also describe the spatial, as well as the logical, relationship of the various entities: the knight moves through 3D space as the horse moves.
132:
In these large applications, memory requirements are major considerations when designing a scene graph. For this reason, many large scene graph systems use
442:-ratified standard that provides a system for the storage, retrieval and playback of real-time graphics content embedded in applications, all within an
304:
and scene graphs is by creating a scene leaf node that contains the spatial partitioning data. This can increase computational efficiency of rendering.
409:
in 1994, another iteration of the high level scene graph built on top of newer releases of
Performer. More 3D scene graph libraries can be found in
600:
225:. This requires that the map of types to callbacks or functors be initialized at runtime, but offers more flexibility, speed and extensibility.
47:
applications and modern computer games, which arranges the logical and often spatial representation of a graphical scene. It is a collection of
516:
122:
and increasingly large worlds or levels. In such applications, nodes in a scene graph (generally) represent entities or objects in the scene.
284:
encompasses all the volumes beneath it. At the root of the tree is a volume that encompasses all the volumes in the tree (the whole scene).
156:, and displaying its shapes is simply a matter of linearly iterating the nodes one by one. Other common operations, such as checking to see
702:
322:
programs), require defining of group nodes in a more automated fashion. A raytracer, for example, will take a scene description of a
593:
439:
96:, it is practical to think of the scene graph as composed of shapes rather than going to a lower level of representation.
401:
or more commonly called
Performer in 1991 which was the primary scenegraph system for most SGI products into the future.
308:
spatial partitioning system, as the scene graph is better thought of as the grander system to the spatial partitioning.
312:
405:
1.0 (1992) was released by SGI, which was a high level scene graph built on top of
Performer. It was followed up with
573:
538:
509:
218:
587:
707:
65:
650:
410:
660:
210:
can be used. This has a similar disadvantage in that it is similarly difficult to add new node types.
499:
339:
265:
214:
503:
495:
382:
100:
48:
520:
455:
316:
250:
157:
92:. Although shapes themselves (particularly paths) can be decomposed further into nodes such as
52:
470:
61:
56:
146:
93:
8:
335:
133:
84:
in a scene graph represents some atomic unit of the document, usually a shape such as an
465:
319:
301:
627:"IRIS Performer: A High Performance Multiprocessing Toolkit for Real-Time 3D Graphics"
569:
443:
201:
672:
612:
434:
and run-time architecture to represent and communicate 3D scenes and objects using
398:
394:
229:
scene graph implementation depends heavily on the application in which it is used.
160:
are also done via linear searches. For small scene graphs, this tends to suffice.
276:
222:
206:
44:
19:
638:
633:– "Unofficially, the PHIGS Extension to X. Officially, PEX was not an acronym."
626:
566:
The
Inventor Mentor: Programming Object-Oriented 3D Graphics with Open Inventor
428:
237:
153:
40:
682:
696:
406:
402:
374:
190:
69:
632:
460:
425:
280:
254:
174:
89:
617:
431:
346:
170:
150:
119:
667:
687:
327:
an eye ray, for example, can entirely skip testing any of its members.
260:
31:
supporting feature-rich and widely adopted scene graph implementation.
323:
81:
350:
373:
was the first commercial scene graph specification, and became an
311:
Very large drawings, or scene graphs that are generated solely at
182:
85:
677:
354:
186:
601:"Hierarchical Geometric Models for Visible Surface Algorithms"
370:
197:
107:
655:
292:
but there are benefits to including a BVH in a scene graph.
113:
378:
269:
435:
421:
331:
elements are visible and thus actually need to be drawn.
178:
75:
28:
295:
446:
to support a wide array of domains and user scenarios.
163:
377:
in 1988. Disparate implementations were provided by
261:
Scene graphs and bounding volume hierarchies (BVHs)
99:Another useful and user-driven node concept is the
189:. But since the underlying implementation of the
694:
508:but its sources remain unclear because it lacks
345:Scene graphs for dense regular objects such as
118:Scene graphs are useful for modern games using
598:
140:
213:Other techniques involve the use of RTTI (
616:
539:Learn how and when to remove this message
145:The simplest form of scene graph uses an
114:Scene graphs in games and 3D applications
594:"The Annotated VRML 97 Reference Manual"
588:"Scenegraphs: Past, Present, and Future"
158:which shape intersects the mouse pointer
18:
80:In vector-based graphics editing, each
695:
639:"IRIS Inventor, a 3D Graphics Toolkit"
76:Scene graphs in graphics editing tools
296:Scene graphs and spatial partitioning
196:In object-oriented languages such as
592:Carey, Rikk and Bell, Gavin (1997).
480:
253:. In 3D systems, which often employ
164:Scene graph operations and dispatch
13:
349:and polygon meshes tend to employ
249:process is known as employing the
14:
719:
703:Computer graphics data structures
644:
625:Helman, Jim; Rohlf, John (1994).
200:, this can easily be achieved by
557:Leler, Wm and Merry, Jim (1996)
485:
300:An effective way of combining
1:
476:
279:(often spheres, axis-aligned
232:
45:vector-based graphics editing
27:, an open-source 3D graphics
360:
7:
580:
449:
411:Category:3D scenegraph APIs
266:Bounding Volume Hierarchies
10:
724:
141:Scene graph implementation
605:Communications of the ACM
340:binary space partitioning
215:Run-Time Type Information
551:
494:This article includes a
383:HOOPS 3D Graphics System
365:
599:James H. Clark (1976).
564:Wernecke, Josie (1994)
523:more precise citations.
637:Strauss, Paul (1993).
456:Graph (data structure)
416:
389:
381:hardware vendors. The
32:
16:Form of data structure
708:Graph data structures
688:Visualization Library
618:10.1145/360349.360354
471:Tree (data structure)
62:transformation matrix
22:
302:spatial partitioning
270:spatial partitioning
275:A BVH is a tree of
251:Painter's algorithm
134:geometry instancing
568:, Addison-Wesley,
496:list of references
466:Space partitioning
33:
549:
548:
541:
444:open architecture
202:virtual functions
43:commonly used by
715:
683:VulkanSceneGraph
622:
620:
561:, Addison-Wesley
544:
537:
533:
530:
524:
519:this article by
510:inline citations
489:
488:
481:
399:OpenGL Performer
395:Silicon Graphics
277:bounding volumes
23:Architecture of
723:
722:
718:
717:
716:
714:
713:
712:
693:
692:
647:
611:(10): 547–554.
586:Bar-Zeev, Avi.
583:
554:
545:
534:
528:
525:
514:
500:related reading
490:
486:
479:
452:
419:
397:(SGI) released
392:
368:
363:
315:(as happens in
298:
263:
235:
207:visitor pattern
166:
143:
116:
78:
17:
12:
11:
5:
721:
711:
710:
705:
691:
690:
685:
680:
678:OpenSceneGraph
675:
670:
665:
664:
663:
658:
646:
645:External links
643:
642:
641:
635:
629:
623:
596:
590:
582:
579:
578:
577:
562:
553:
550:
547:
546:
504:external links
493:
491:
484:
478:
475:
474:
473:
468:
463:
458:
451:
448:
429:open standards
418:
415:
391:
388:
367:
364:
362:
359:
297:
294:
281:bounding boxes
262:
259:
234:
231:
165:
162:
154:data structure
142:
139:
115:
112:
77:
74:
66:transformation
41:data structure
25:OpenSceneGraph
15:
9:
6:
4:
3:
2:
720:
709:
706:
704:
701:
700:
698:
689:
686:
684:
681:
679:
676:
674:
673:IRISPerformer
671:
669:
666:
662:
659:
657:
654:
653:
652:
649:
648:
640:
636:
634:
630:
628:
624:
619:
614:
610:
606:
602:
597:
595:
591:
589:
585:
584:
575:
574:0-201-62495-8
571:
567:
563:
560:
559:3D with HOOPS
556:
555:
543:
540:
532:
529:December 2014
522:
518:
512:
511:
505:
501:
497:
492:
483:
482:
472:
469:
467:
464:
462:
459:
457:
454:
453:
447:
445:
441:
437:
433:
430:
427:
423:
414:
412:
408:
407:Open Inventor
404:
403:IRIS Inventor
400:
396:
387:
384:
380:
376:
375:ANSI standard
372:
358:
356:
352:
348:
343:
341:
337:
332:
328:
325:
321:
318:
314:
309:
305:
303:
293:
289:
285:
282:
278:
273:
271:
267:
258:
256:
255:depth buffers
252:
246:
242:
239:
230:
226:
224:
220:
216:
211:
209:
208:
203:
199:
194:
192:
191:rendering API
188:
184:
180:
176:
172:
161:
159:
155:
152:
148:
138:
135:
130:
127:
123:
121:
111:
109:
104:
102:
97:
95:
91:
87:
83:
73:
71:
67:
63:
58:
54:
50:
46:
42:
39:is a general
38:
30:
26:
21:
608:
604:
565:
558:
535:
526:
515:Please help
507:
461:Graph theory
426:royalty-free
420:
393:
369:
347:heightfields
344:
333:
329:
310:
306:
299:
290:
286:
274:
264:
247:
243:
236:
227:
212:
205:
195:
175:Euler angles
167:
144:
131:
128:
124:
117:
105:
98:
94:spline nodes
79:
36:
34:
24:
576:(Release 2)
521:introducing
438:. It is an
432:file format
317:ray tracing
171:quaternions
151:linked list
120:3D graphics
90:Bezier path
37:scene graph
697:Categories
656:Aviatrix3D
477:References
238:Traversals
233:Traversals
181:, such as
64:(see also
631:PEXTimes
361:Standards
351:quadtrees
320:rendering
219:callbacks
82:leaf node
581:Articles
450:See also
272:below).
223:functors
517:improve
355:octrees
313:runtime
183:DirectX
86:ellipse
668:OpenSG
651:Java3D
572:
187:OpenGL
70:matrix
552:Books
502:, or
424:is a
371:PHIGS
366:PHIGS
336:Quake
147:array
101:layer
53:graph
51:in a
49:nodes
661:LG3D
570:ISBN
379:Unix
353:and
68:and
57:tree
613:doi
440:ISO
436:XML
422:X3D
417:X3D
390:SGI
221:or
198:C++
185:or
179:API
173:or
149:or
108:C++
88:or
55:or
29:API
699::
609:19
607:.
603:.
506:,
498:,
413:.
338:,
324:3D
35:A
621:.
615::
542:)
536:(
531:)
527:(
513:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
