66:
102:
25:
230:
498:. The responsibility of a rendering engine is to allow for large world spaces, and as the world’s size approaches infinity, the engine should not slow down but remain at a constant speed. Optimizing this process relies on being able to ensure the deployment of as few resources as possible towards the rendering of surfaces that will not end up being displayed to the user.
590:). Polygons are displayed from the nearest to the furthest. New polygons are clipped against already displayed polygons' edges, creating new polygons to display then storing the additional edges. It's much harder to implement than S/C/Z-buffers, but it scales much better with increases in resolution.
575:
era. Instead of storing the Z value per pixel, they store a list of already displayed segments per line of the screen. New polygons are then cut against already displayed segments that would hide them. An S-buffer can display unsorted polygons, while a C-buffer requires polygons to be displayed from
616:
Divides a scene along planes corresponding to polygon boundaries. The subdivision is constructed in such a way as to provide an unambiguous depth ordering from any point in the scene when the BSP tree is traversed. The disadvantage here is that the BSP tree is created with an expensive pre-process.
551:
graphics hardware. This is the current standard. The cost of using Z-buffering is that it uses up to 4 bytes per pixel and that the rasterization algorithm needs to check each rasterized sample against the Z-buffer. The Z-buffer can also suffer from artifacts due to precision errors (also known as
550:
is used) is checked against an existing depth value. If the current pixel is behind the pixel in the Z-buffer, the pixel is rejected, otherwise, it is shaded and its depth value replaces the one in the Z-buffer. Z-buffering supports dynamic scenes easily and is currently implemented efficiently in
694:
Incidentally, this also makes the objects completely transparent when the viewpoint camera is located inside them, because then all the surfaces of the object are facing away from the camera and are culled by the renderer. To prevent this the object must be set as double-sided (i.e. no back-face
690:
With 3D objects, some of the object's surface is facing the camera, and the rest is facing away from the camera, i.e. is on the backside of the object, hindered by the front side. If the object is completely opaque, those surfaces never need to be drawn. They are determined by the vertex winding
770:
is a ray-tracing approach that divides the visible volumes into beams. Various screen-space subdivision approaches reducing the number of primitives considered per region, e.g. tiling, or screen-space BSP clipping. Tiling may be used as a preprocess to other techniques. Z-buffer hardware may
625:
Attempts to model the path of light rays to a viewpoint by tracing rays from the viewpoint into the scene. Although not a hidden-surface removal algorithm as such, it implicitly solves the hidden-surface removal problem by finding the nearest surface along each view-ray. Effectively this is
493:
Hidden-surface determination is a process by which surfaces that should not be visible to the user (for example, because they lie behind opaque objects such as walls) are prevented from being rendered. Despite advances in hardware capability, there is still a need for advanced
635:
Divides the screen into smaller areas and sorts triangles within these. If there is ambiguity (i.e., polygons overlap in-depth extent within these areas), then further subdivision occurs. At the limit, the subdivision may occur down to the pixel
606:
turned on. The cost here is the sorting step and the fact that visual artifacts can occur. This algorithm is broken by design for general scenes, as it cannot handle polygons in various common configurations, such as surfaces that intersect each
617:
This means that it is less suitable for scenes consisting of dynamic geometry. The advantage is that the data is pre-sorted and error-free, ready for the previously mentioned algorithms. Note that the BSP is not a solution to HSR, only an aid.
672:. Naturally, objects outside this volume will not be visible in the final image, so they are discarded. Often, objects lie on the boundary of the viewing frustum. These objects are cut into pieces along this boundary in a process called
740:) rendering divides a scene into regions and pre-computes visibility for them. These visibility sets are then indexed at run-time to obtain high-quality visibility sets (accounting for complex occluder interactions) quickly.
485:. Hidden-surface determination is necessary to render a scene correctly, so that one may not view features hidden behind the model itself, allowing only the naturally viewable portion of the graphic to be visible.
797:, then each of its children needs to be evaluated. This traversal is effectively a tree walk, where invisibility/occlusion or reaching a leaf node determines whether to stop or whether to recurse respectively.
691:
order: if the triangle drawn has its vertices in clockwise order on the projection plane when facing the camera, they switch into counter-clockwise order when the surface turns away from the camera.
656:
The advantage of culling early on in the pipeline is that entire objects that are invisible do not have to be fetched, transformed, rasterized, or shaded. Types of culling algorithms include:
725:
Objects that are entirely behind other opaque objects may be culled. This is a very popular mechanism to speed up the rendering of large scenes that have a moderate to high
576:
the nearest to the furthest. Because the C-buffer technique does not require a pixel to be drawn more than once, the process is slightly faster. This was commonly used with
505:
and usually vary in the order in which the sort is performed and how the problem is subdivided. Sorting large quantities of graphics primitives is usually done by
793:, then all of its child nodes are also invisible, and no further processing is necessary (they can all be rejected by the renderer). If a node is considered
774:
726:
750:
Hansong Zhang's dissertation "Effective
Occlusion Culling for the Interactive Display of Arbitrary Models" describes an occlusion culling approach.
473:, which was one of the first major problems in the field of 3D computer graphics. The process of hidden-surface determination is sometimes called
847:
412:
771:
typically include a coarse "hi-Z", against which primitives can be rejected early without rasterization, this is a form of occlusion culling.
119:
38:
703:
Often, objects are so far away that they do not contribute significantly to the final image. These objects are thrown away if their screen
166:
879:
649:, which usually happens before VSD in a rendering pipeline. Primitives or batches of primitives can be rejected in their entirety, which
602:
and draws them back to front. This produces few artifacts when applied to scenes with polygons of similar size forming smooth meshes and
138:
746:
divides a scene into cells/sectors (rooms) and portals (doors), and computes which sectors are visible by clipping them against portals.
145:
789:). This allows visibility determination to be performed hierarchically: effectively, if a node in the tree is considered to be
152:
1310:
1268:
1241:
1284:
888:
842:
462:
134:
1008:
405:
203:
185:
52:
44:
872:
1131:
932:
123:
1256:
1246:
1136:
955:
398:
1251:
1116:
806:
759:
673:
526:
506:
159:
1044:
865:
331:
610:
577:
501:
There are many techniques for hidden-surface determination. They are fundamentally an exercise in
465:
and parts of surfaces can be seen from a particular viewing angle. A hidden-surface determination
733:
300:
112:
1263:
1213:
1178:
1156:
1151:
676:, and the pieces that lie outside the frustum are discarded as there is no place to draw them.
620:
593:
315:
1305:
1106:
1085:
1029:
280:
989:
975:
919:
522:
426:
219:
8:
1121:
1049:
937:
586:
Used in Quake 1, this was storing a list of the edges of already displayed polygons (see
495:
482:
381:
305:
79:
Please help update this article to reflect recent events or newly available information.
1183:
1171:
1018:
1013:
965:
587:
518:
470:
349:
344:
1233:
1126:
1111:
927:
763:
685:
630:
603:
1218:
1208:
1090:
1078:
743:
720:
386:
376:
361:
1039:
904:
896:
851:
665:
366:
310:
1188:
708:
669:
371:
295:
285:
1299:
1193:
1067:
997:
704:
530:
1198:
1161:
1146:
1141:
1061:
1002:
767:
254:
1166:
1034:
970:
826:
537:
259:
249:
244:
777:(BVHs) are often used to subdivide the scene's space (examples are the
552:
356:
290:
546:
in the case of anti-aliasing, but without loss of generality the term
466:
339:
857:
101:
1024:
778:
599:
565:
275:
1073:
786:
572:
502:
229:
1203:
960:
782:
1223:
909:
640:
626:
equivalent to sorting all the geometry on a per-pixel basis.
947:
729:. There are several types of occlusion culling approaches:
668:
is a geometric representation of the volume visible to the
533:
steps are handled differently by the following algorithms:
580:(BSP) trees, which would provide sorting for the polygons.
542:
During rasterization, the depth/Z value of each pixel (or
645:
A related area to visible-surface determination (VSD) is
571:
Faster than Z-buffers and commonly used in games in the
827:"Occlusion Culling with Hierarchical Occlusion Maps"
848:
A Characterization of Ten Hidden-Surface
Algorithms
695:culling is done) or have separate inside surfaces.
126:. Unsourced material may be challenged and removed.
481:. When referring to line rendering it is known as
1297:
477:, and such an algorithm is sometimes called a
873:
406:
653:reduces the load on a well-designed system.
53:Learn how and when to remove these messages
880:
866:
659:
413:
399:
228:
758:A popular theme in the VSD literature is
641:Culling and visible-surface determination
204:Learn how and when to remove this message
186:Learn how and when to remove this message
698:
1298:
461:)) is the process of identifying what
887:
861:
753:
1285:List of computer graphics algorithms
714:
679:
124:adding citations to reliable sources
95:
59:
18:
946:
13:
16:Visibility in 3D computer graphics
14:
1322:
34:This article has multiple issues.
100:
64:
23:
766:pioneered dividing the screen.
111:needs additional citations for
42:or discuss these issues on the
819:
135:"Hidden-surface determination"
1:
1242:3D computer graphics software
512:
488:
455:visible-surface determination
1311:Computer graphics algorithms
1057:Hidden-surface determination
843:Hidden Surface Determination
721:Z-buffering § Z-culling
431:hidden-surface determination
7:
800:
775:Bounding volume hierarchies
435:shown-surface determination
332:Computer-generated imagery
10:
1327:
812:
718:
683:
1277:
1232:
1099:
988:
918:
895:
611:Binary space partitioning
578:binary space partitioning
73:This article needs to be
598:Sorts polygons by their
1269:Vector graphics editors
1264:Raster graphics editors
734:Potentially visible set
660:Viewing-frustum culling
583:Sorted active edge list
1152:Checkerboard rendering
564:) and surface buffer (
439:hidden-surface removal
316:Virtual cinematography
220:Three-dimensional (3D)
1107:Affine transformation
1086:Surface triangulation
1030:Anisotropic filtering
469:is a solution to the
281:Computer-aided design
699:Contribution culling
496:rendering algorithms
427:3D computer graphics
120:improve this article
1122:Collision detection
1050:Global illumination
594:Painter's algorithm
483:hidden-line removal
382:Global illumination
306:Virtual engineering
1172:Scanline rendering
966:Parallax scrolling
956:Isometric graphics
760:divide and conquer
754:Divide and conquer
707:is too small. See
588:scanline rendering
558:Coverage buffers (
519:rendering pipeline
507:divide and conquer
471:visibility problem
1293:
1292:
1234:Graphics software
1127:Planar projection
1112:Back-face culling
984:
983:
928:Alpha compositing
889:Computer graphics
764:Warnock algorithm
715:Occlusion culling
686:Back-face culling
680:Back-face culling
631:Warnock algorithm
604:back-face culling
447:occlusion culling
423:
422:
222:computer graphics
214:
213:
206:
196:
195:
188:
170:
94:
93:
57:
1318:
1219:Volume rendering
1091:Wire-frame model
944:
943:
882:
875:
868:
859:
858:
835:
834:
823:
744:Portal rendering
727:depth complexity
563:
562:
517:Considering the
415:
408:
401:
387:Volume rendering
377:Crowd simulation
362:Wire-frame model
335:
232:
216:
215:
209:
202:
191:
184:
180:
177:
171:
169:
128:
104:
96:
89:
86:
80:
68:
67:
60:
49:
27:
26:
19:
1326:
1325:
1321:
1320:
1319:
1317:
1316:
1315:
1296:
1295:
1294:
1289:
1273:
1228:
1095:
1040:Fluid animation
980:
942:
914:
905:Diffusion curve
897:Vector graphics
891:
886:
852:Wayback Machine
839:
838:
825:
824:
820:
815:
803:
756:
723:
717:
701:
688:
682:
666:viewing frustum
662:
643:
560:
559:
515:
491:
433:(also known as
419:
367:Texture mapping
333:
311:Virtual reality
221:
210:
199:
198:
197:
192:
181:
175:
172:
129:
127:
117:
105:
90:
84:
81:
78:
69:
65:
28:
24:
17:
12:
11:
5:
1324:
1314:
1313:
1308:
1291:
1290:
1288:
1287:
1281:
1279:
1275:
1274:
1272:
1271:
1266:
1261:
1260:
1259:
1254:
1249:
1238:
1236:
1230:
1229:
1227:
1226:
1221:
1216:
1211:
1206:
1201:
1196:
1191:
1189:Shadow mapping
1186:
1181:
1176:
1175:
1174:
1169:
1164:
1159:
1154:
1149:
1144:
1134:
1129:
1124:
1119:
1114:
1109:
1103:
1101:
1097:
1096:
1094:
1093:
1088:
1083:
1082:
1081:
1071:
1064:
1059:
1054:
1053:
1052:
1042:
1037:
1032:
1027:
1022:
1016:
1011:
1005:
1000:
994:
992:
986:
985:
982:
981:
979:
978:
973:
968:
963:
958:
952:
950:
941:
940:
935:
930:
924:
922:
916:
915:
913:
912:
907:
901:
899:
893:
892:
885:
884:
877:
870:
862:
856:
855:
845:
837:
836:
831:www.cs.unc.edu
817:
816:
814:
811:
810:
809:
802:
799:
755:
752:
748:
747:
741:
716:
713:
709:Clipping plane
700:
697:
684:Main article:
681:
678:
670:virtual camera
661:
658:
642:
639:
638:
637:
633:
627:
623:
618:
614:
608:
596:
591:
584:
581:
569:
556:
540:
514:
511:
490:
487:
421:
420:
418:
417:
410:
403:
395:
392:
391:
390:
389:
384:
379:
374:
372:Motion capture
369:
364:
359:
354:
353:
352:
347:
337:
326:
325:
324:Related topics
321:
320:
319:
318:
313:
308:
303:
298:
296:Visual effects
293:
288:
286:Graphic design
283:
278:
270:
269:
265:
264:
263:
262:
257:
252:
247:
239:
238:
234:
233:
225:
224:
212:
211:
194:
193:
108:
106:
99:
92:
91:
72:
70:
63:
58:
32:
31:
29:
22:
15:
9:
6:
4:
3:
2:
1323:
1312:
1309:
1307:
1304:
1303:
1301:
1286:
1283:
1282:
1280:
1276:
1270:
1267:
1265:
1262:
1258:
1255:
1253:
1250:
1248:
1245:
1244:
1243:
1240:
1239:
1237:
1235:
1231:
1225:
1222:
1220:
1217:
1215:
1212:
1210:
1207:
1205:
1202:
1200:
1197:
1195:
1194:Shadow volume
1192:
1190:
1187:
1185:
1182:
1180:
1177:
1173:
1170:
1168:
1165:
1163:
1160:
1158:
1155:
1153:
1150:
1148:
1145:
1143:
1140:
1139:
1138:
1135:
1133:
1130:
1128:
1125:
1123:
1120:
1118:
1115:
1113:
1110:
1108:
1105:
1104:
1102:
1098:
1092:
1089:
1087:
1084:
1080:
1077:
1076:
1075:
1072:
1069:
1068:Triangle mesh
1065:
1063:
1060:
1058:
1055:
1051:
1048:
1047:
1046:
1043:
1041:
1038:
1036:
1033:
1031:
1028:
1026:
1023:
1020:
1017:
1015:
1012:
1010:
1006:
1004:
1001:
999:
998:3D projection
996:
995:
993:
991:
987:
977:
974:
972:
969:
967:
964:
962:
959:
957:
954:
953:
951:
949:
945:
939:
938:Text-to-image
936:
934:
931:
929:
926:
925:
923:
921:
917:
911:
908:
906:
903:
902:
900:
898:
894:
890:
883:
878:
876:
871:
869:
864:
863:
860:
853:
849:
846:
844:
841:
840:
832:
828:
822:
818:
808:
805:
804:
798:
796:
792:
788:
784:
780:
776:
772:
769:
765:
761:
751:
745:
742:
739:
735:
732:
731:
730:
728:
722:
712:
710:
706:
696:
692:
687:
677:
675:
671:
667:
657:
654:
652:
648:
634:
632:
628:
624:
622:
619:
615:
612:
609:
605:
601:
597:
595:
592:
589:
585:
582:
579:
574:
570:
567:
557:
554:
549:
545:
541:
539:
536:
535:
534:
532:
531:rasterization
528:
524:
520:
510:
508:
504:
499:
497:
486:
484:
480:
476:
472:
468:
464:
460:
456:
452:
448:
444:
440:
436:
432:
428:
416:
411:
409:
404:
402:
397:
396:
394:
393:
388:
385:
383:
380:
378:
375:
373:
370:
368:
365:
363:
360:
358:
355:
351:
348:
346:
343:
342:
341:
338:
336:
330:
329:
328:
327:
323:
322:
317:
314:
312:
309:
307:
304:
302:
301:Visualization
299:
297:
294:
292:
289:
287:
284:
282:
279:
277:
274:
273:
272:
271:
267:
266:
261:
258:
256:
253:
251:
248:
246:
243:
242:
241:
240:
236:
235:
231:
227:
226:
223:
218:
217:
208:
205:
190:
187:
179:
168:
165:
161:
158:
154:
151:
147:
144:
140:
137: –
136:
132:
131:Find sources:
125:
121:
115:
114:
109:This article
107:
103:
98:
97:
88:
85:February 2016
76:
71:
62:
61:
56:
54:
47:
46:
41:
40:
35:
30:
21:
20:
1306:3D rendering
1199:Shear matrix
1162:Path tracing
1147:Cone tracing
1142:Beam tracing
1062:Polygon mesh
1056:
1003:3D rendering
830:
821:
794:
790:
773:
768:Beam tracing
757:
749:
737:
724:
702:
693:
689:
663:
655:
650:
646:
644:
547:
543:
516:
500:
492:
478:
474:
458:
454:
450:
446:
442:
438:
434:
430:
424:
268:Primary uses
237:Fundamentals
200:
182:
173:
163:
156:
149:
142:
130:
118:Please help
113:verification
110:
82:
74:
50:
43:
37:
36:Please help
33:
1214:Translation
1167:Ray casting
1157:Ray tracing
1035:Cel shading
1009:Image-based
990:3D graphics
971:Ray casting
920:2D graphics
621:Ray tracing
538:Z-buffering
291:Video games
1300:Categories
1278:Algorithms
1132:Reflection
719:See also:
705:projection
600:barycenter
553:Z-fighting
529:, and the
523:projection
513:Algorithms
489:Background
357:3D display
146:newspapers
39:improve it
1257:rendering
1247:animation
1137:Rendering
791:invisible
467:algorithm
340:Animation
276:3D models
255:Rendering
176:July 2017
45:talk page
1252:modeling
1179:Rotation
1117:Clipping
1100:Concepts
1079:Deferred
1045:Lighting
1025:Aliasing
1019:Unbiased
1014:Spectral
807:Clipping
801:See also
785:and the
779:BSP tree
674:clipping
566:S-buffer
561:C-buffer
527:clipping
463:surfaces
350:skeletal
345:computer
260:Printing
250:Scanning
245:Modeling
1184:Scaling
1074:Shading
813:Sources
795:visible
787:kd-tree
651:usually
647:culling
573:Quake I
503:sorting
160:scholar
75:updated
1204:Shader
976:Skybox
961:Mode 7
933:Layers
783:octree
781:, the
762:. The
636:level.
607:other.
544:sample
525:, the
521:, the
475:hiding
162:
155:
148:
141:
133:
1224:Voxel
1209:Texel
910:Pixel
854:copy)
613:(BSP)
548:pixel
479:hider
453:) or
334:(CGI)
167:JSTOR
153:books
948:2.5D
664:The
629:The
139:news
738:PVS
459:VSD
445:),
443:HSR
425:In
122:by
1302::
829:.
711:.
555:).
509:.
451:OC
437:,
429:,
48:.
1070:)
1066:(
1021:)
1007:(
881:e
874:t
867:v
850:(
833:.
736:(
568:)
457:(
449:(
441:(
414:e
407:t
400:v
207:)
201:(
189:)
183:(
178:)
174:(
164:·
157:·
150:·
143:·
116:.
87:)
83:(
77:.
55:)
51:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
