137:
to solve the interior ambiguities, which is based on the
Asymptotic Decider. Later, in 2003, Nielson proved that Chernyaev's lookup table is complete and can represent all the possible behaviors of the trilinear interpolant, and Lewiner et al. proposed an implementation to the algorithm. Also in 2003 Lopes and Brodlie extended the tests proposed by Natarajan. In 2013, Custodio et al. noted and corrected algorithmic inaccuracies that compromised the topological correctness of the mesh generated by the Marching Cubes 33 algorithm proposed by Chernyaev.
120:
Marching Cubes presented discontinuities and topological issues. Given a cube of the grid, a face ambiguity occurs when its face vertices have alternating signs. That is, the vertices of one diagonal on this face are positive and the vertices on the other are negative. Observe that in this case, the signs of the face vertices are insufficient to determine the correct way to triangulate the isosurface. Similarly, an interior ambiguity occurs when the signs of the cube vertices are insufficient to determine the correct
141:
20:
128:
incomplete, and that certain
Marching Cubes cases allow multiple triangulations. Durst's 'additional reference' was to an earlier, more efficient (see de Araujo) isosurface polygonization algorithm by Wyvill, Wyvill and McPheeters. Later, Nielson and Hamann in 1991 observed the existence of ambiguities in the interpolant behavior on the face of the cube. They proposed a test called
254:
191:, in order to circumvent the patent as well as solve a minor ambiguity problem of marching cubes with some cube configurations. The patent expired in 2005, and it is now legal for the graphics community to use it without royalties since more than the 20 years have passed from its issue date (December 1, 1987).
160:
This is done by creating an index to a precalculated array of 256 possible polygon configurations (2=256) within the cube, by treating each of the 8 scalar values as a bit in an 8-bit integer. If the scalar's value is higher than the iso-value (i.e., it is inside the surface) then the appropriate bit
136:
The
Marching Cubes 33, proposed by Chernyaev in 1995, is one of the first isosurface extraction algorithms intended to preserve the topology of the trilinear interpolant. In his work, Chernyaev extends to 33 the number of cases in the triangulation lookup table. He then proposes a different approach
132:
to correctly track the interpolant on the faces of the cube. In fact, as observed by
Natarajan in 1994, this ambiguity problem also occurs inside the cube. In his work, the author proposed a disambiguation test based on the interpolant critical points, and added four new cases to the Marching Cubes
127:
The popularity of the
Marching Cubes and its widespread adoption resulted in several improvements in the algorithm to deal with the ambiguities and to correctly track the behavior of the interpolant. Durst in 1988 was the first to note that the triangulation table proposed by Lorensen and Cline was
119:
The first published version of the algorithm exploited rotational and reflective symmetry and also sign changes to build the table with 15 unique cases. However, due to the existence of ambiguities in the trilinear interpolant behavior in the cube faces and interior, the meshes extracted by the
133:
triangulation table (subcases of the cases 3, 4, 6 and 7). At this point, even with all the improvements proposed to the algorithm and its triangulation table, the meshes generated by the
Marching Cubes still had topological incoherencies.
112:, can easily be identified because the sample values at the cube vertices must span the target isosurface value. For each cube containing a section of the isosurface, a triangular mesh that approximates the behavior of the
153:
The algorithm proceeds through the scalar field, taking eight neighbor locations at a time (thus forming an imaginary cube), then determining the polygon(s) needed to represent the part of the
252:, Cline, Harvey & Lorensen, William, "System and method for the display of surface structures contained within the interior region of a solid body", issued 1987-12-01
164:
Finally each vertex of the generated polygons is placed on the appropriate position along the cube's edge by linearly interpolating the two scalar values that are connected by that edge.
161:
is set to one, while if it is lower (outside), it is set to zero. The final value, after all eight scalars are checked, is the actual index to the polygon indices array.
541:
Lewiner, Thomas; Lopes, Hélio; Vieira, Antônio Wilson; Tavares, Geovan (January 2003). "Efficient
Implementation of Marching Cubes' Cases with Topological Guarantees".
90:
628:
Custodio, Lis; Etiene, Tiago; Pesco, Sinesio; Silva, Claudio (November 2013). "Practical considerations on
Marching Cubes 33 topological correctness".
171:
of the scalar field at each grid point is also the normal vector of a hypothetical isosurface passing from that point. Therefore, these normals may be
479:
Marching Cubes 33 : construction of topologically correct isosurfaces : presented at GRAPHICON '95, Saint-Petersburg, Russia, 03-07.07.1995
94:
500:
187:
An implementation of the marching cubes algorithm was patented as United States Patent 4,710,876. Another similar algorithm was developed, called
841:
585:
767:
Montani, Claudio; Scateni, Riccardo; Scopigno, Roberto (1994). "A modified look-up table for implicit disambiguation of
Marching cubes".
175:
along the edges of each cube to find the normals of the generated vertices which are essential for shading the resulting mesh with some
930:
317:
de Araujo, Bruno; Lopes, Daniel; Jepp, Pauline; Jorge, Joaquim; Wyvill, Brian (2015). "A Survey on
Implicit Surface Polygonization".
77:
or other metasurfaces. The marching cubes algorithm is meant to be used for 3-D; the 2-D version of this algorithm is called the
207:
Lorensen, William E.; Cline, Harvey E. (1 August 1987). "Marching cubes: A high resolution 3D surface construction algorithm".
1068:
813:
404:
749:
1042:
701:
Lorensen, W. E.; Cline, Harvey E. (1987). "Marching cubes: A high resolution 3d surface construction algorithm".
1073:
1027:
923:
431:
Natarajan, B. K. (January 1994). "On generating topologically consistent isosurfaces from uniform samples".
104:
The premise of the algorithm is to divide the input volume into a discrete set of cubes. By assuming linear
898:
1007:
732:
Nielson, G.M.; Hamann, B. (1991). "The asymptotic decider: Resolving the ambiguity in marching cubes".
387:
Nielson, G.M.; Hamann, B. (1991). "The asymptotic decider: Resolving the ambiguity in marching cubes".
70:
66:
880:
642:
1078:
986:
916:
849:
715:
221:
101:. At General Electric they worked on a way to efficiently visualize data from CT and MRI devices.
113:
157:
that passes through this cube. The individual polygons are then fused into the desired surface.
1037:
875:
710:
637:
216:
991:
121:
105:
62:
352:
Wyvill, Geoff; Wyvill, Brian; McPheeters, Craig (1986). "Data structures for soft objects".
172:
8:
1022:
1012:
981:
688:
683:
188:
857:
586:"Improving the robustness and accuracy of the marching cubes algorithm for isosurfacing"
819:
784:
755:
663:
566:
494:
456:
410:
369:
334:
299:
176:
129:
1047:
809:
745:
655:
558:
482:
448:
400:
291:
35:
788:
759:
414:
373:
338:
303:
885:
823:
801:
776:
737:
720:
667:
647:
608:
600:
570:
554:
550:
523:
440:
392:
361:
326:
281:
226:
124:, i.e., when multiple triangulations are possible for the same cube configuration.
98:
78:
73:
scan data images, and special effects or 3-D modelling with what is usually called
460:
939:
866:
Newman, Timothy S.; Yi, Hong (2006). "A survey of the marching cubes algorithm".
805:
741:
396:
46:
889:
651:
604:
527:
249:
1062:
960:
947:
832:
659:
562:
486:
452:
295:
1032:
955:
54:
286:
269:
965:
724:
230:
796:
Nielson, G.M.; Junwon Sung (1997). "Interval volume tetrahedrization".
780:
613:
444:
365:
154:
109:
50:
74:
38:
19:
330:
140:
168:
42:
908:
61:). The applications of this algorithm are mainly concerned with
248:
58:
540:
24:
23:
Head and cerebral structures (hidden) extracted from 150
627:
593:
IEEE Transactions on Visualization and Computer Graphics
516:
IEEE Transactions on Visualization and Computer Graphics
316:
766:
351:
27:
slices using marching cubes (about 150,000 triangles)
45:
proceedings by Lorensen and Cline, for extracting a
850:"Introductory description with additional graphics"
798:
Proceedings. Visualization '97 (Cat. No. 97CB36155)
795:
1060:
144:The originally published 15 cube configurations
108:, each cube, which contains a piece of a given
862:. Some of the early history of Marching Cubes.
270:"Re: Additional reference to "marching cubes""
924:
731:
700:
386:
206:
200:
583:
499:: CS1 maint: multiple names: authors list (
57:(the elements of which are sometimes called
514:Nielson, G.M. (2003). "On marching cubes".
244:
242:
240:
931:
917:
896:
879:
714:
641:
612:
481:. CERN. Computing and Networks Division.
430:
285:
220:
865:
839:
237:
139:
18:
899:"Specializing visualization algorithms"
830:
513:
1061:
912:
267:
472:
470:
426:
424:
938:
116:in the interior cube is generated.
13:
476:
97:as a result of their research for
53:from a three-dimensional discrete
14:
1090:
694:
467:
421:
182:
621:
584:Lopes, A.; Brodlie, K. (2003).
577:
534:
268:Dürst, Martin J. (1988-10-01).
89:The algorithm was developed by
555:10.1080/10867651.2003.10487582
507:
380:
345:
310:
274:ACM SIGGRAPH Computer Graphics
261:
209:ACM SIGGRAPH Computer Graphics
1:
1028:Principles of Grid Generation
1069:Computer graphics algorithms
734:Proceeding Visualization '91
389:Proceeding Visualization '91
148:
7:
677:
16:Computer graphics algorithm
10:
1095:
833:"Overview and source code"
806:10.1109/VISUAL.1997.663886
742:10.1109/VISUAL.1991.175782
477:V., Chernyaev, E. (1995).
397:10.1109/visual.1991.175782
194:
84:
1000:
974:
946:
890:10.1016/j.cag.2006.07.021
652:10.1016/j.cag.2013.04.004
605:10.1109/tvcg.2003.1175094
543:Journal of Graphics Tools
528:10.1109/TVCG.2003.1207437
250:US granted US4710876A
987:Parallel mesh generation
630:Computers & Graphics
106:reconstruction filtering
41:, published in the 1987
1008:Chew's second algorithm
868:Computers and Graphics
145:
63:medical visualizations
28:
992:Stretched grid method
703:ACM Computer Graphics
319:ACM Computing Surveys
287:10.1145/378267.378271
143:
122:surface triangulation
114:trilinear interpolant
22:
1074:3D computer graphics
800:. pp. 221–228.
1038:Ruppert's algorithm
1023:Marching tetrahedra
1013:Image-based meshing
982:Laplacian smoothing
769:The Visual Computer
725:10.1145/37402.37422
689:Marching tetrahedra
684:Image-based meshing
433:The Visual Computer
354:The Visual Computer
231:10.1145/37402.37422
189:marching tetrahedra
91:William E. Lorensen
842:"GameDev overview"
781:10.1007/BF01900830
736:. pp. 83–91.
445:10.1007/bf01900699
391:. pp. 83–91.
366:10.1007/BF01900346
177:illumination model
146:
130:Asymptotic Decider
29:
1056:
1055:
1048:Unstructured grid
815:978-0-8186-8262-9
325:(4): 60:1–60:39.
36:computer graphics
1086:
933:
926:
919:
910:
909:
905:
903:
893:
883:
861:
858:"Marching Cubes"
853:
845:
836:
827:
792:
763:
728:
718:
672:
671:
645:
625:
619:
618:
616:
590:
581:
575:
574:
538:
532:
531:
511:
505:
504:
498:
490:
474:
465:
464:
428:
419:
418:
384:
378:
377:
349:
343:
342:
314:
308:
307:
289:
265:
259:
258:
257:
253:
246:
235:
234:
224:
204:
99:General Electric
93:(1946-2019) and
79:marching squares
1094:
1093:
1089:
1088:
1087:
1085:
1084:
1083:
1079:Mesh generation
1059:
1058:
1057:
1052:
996:
970:
942:
940:Mesh generation
937:
901:
897:Stephan Diehl.
881:10.1.1.413.7458
856:
848:
816:
752:
697:
680:
675:
643:10.1.1.361.3074
626:
622:
588:
582:
578:
539:
535:
512:
508:
492:
491:
475:
468:
429:
422:
407:
385:
381:
350:
346:
331:10.1145/2732197
315:
311:
266:
262:
255:
247:
238:
205:
201:
197:
185:
151:
95:Harvey E. Cline
87:
17:
12:
11:
5:
1092:
1082:
1081:
1076:
1071:
1054:
1053:
1051:
1050:
1045:
1040:
1035:
1030:
1025:
1020:
1018:Marching cubes
1015:
1010:
1004:
1002:
998:
997:
995:
994:
989:
984:
978:
976:
972:
971:
969:
968:
963:
958:
952:
950:
944:
943:
936:
935:
928:
921:
913:
907:
906:
894:
874:(5): 854–879.
863:
854:
846:
840:Matthew Ward.
837:
828:
814:
793:
775:(6): 353–355.
764:
750:
729:
716:10.1.1.545.613
709:(4): 163–169.
696:
695:External links
693:
692:
691:
686:
679:
676:
674:
673:
636:(7): 840–850.
620:
576:
533:
522:(3): 283–297.
506:
466:
420:
406:978-0818622458
405:
379:
360:(4): 227–234.
344:
309:
260:
236:
222:10.1.1.545.613
215:(4): 163–169.
198:
196:
193:
184:
181:
150:
147:
86:
83:
47:polygonal mesh
32:Marching cubes
15:
9:
6:
4:
3:
2:
1091:
1080:
1077:
1075:
1072:
1070:
1067:
1066:
1064:
1049:
1046:
1044:
1041:
1039:
1036:
1034:
1031:
1029:
1026:
1024:
1021:
1019:
1016:
1014:
1011:
1009:
1006:
1005:
1003:
999:
993:
990:
988:
985:
983:
980:
979:
977:
973:
967:
964:
962:
961:Triangle mesh
959:
957:
954:
953:
951:
949:
948:Types of mesh
945:
941:
934:
929:
927:
922:
920:
915:
914:
911:
900:
895:
891:
887:
882:
877:
873:
869:
864:
859:
855:
851:
847:
843:
838:
834:
831:Paul Bourke.
829:
825:
821:
817:
811:
807:
803:
799:
794:
790:
786:
782:
778:
774:
770:
765:
761:
757:
753:
751:9780818622458
747:
743:
739:
735:
730:
726:
722:
717:
712:
708:
704:
699:
698:
690:
687:
685:
682:
681:
669:
665:
661:
657:
653:
649:
644:
639:
635:
631:
624:
615:
610:
606:
602:
598:
594:
587:
580:
572:
568:
564:
560:
556:
552:
548:
544:
537:
529:
525:
521:
517:
510:
502:
496:
488:
484:
480:
473:
471:
462:
458:
454:
450:
446:
442:
438:
434:
427:
425:
416:
412:
408:
402:
398:
394:
390:
383:
375:
371:
367:
363:
359:
355:
348:
340:
336:
332:
328:
324:
320:
313:
305:
301:
297:
293:
288:
283:
279:
275:
271:
264:
251:
245:
243:
241:
232:
228:
223:
218:
214:
210:
203:
199:
192:
190:
183:Patent issues
180:
178:
174:
170:
165:
162:
158:
156:
142:
138:
134:
131:
125:
123:
117:
115:
111:
107:
102:
100:
96:
92:
82:
81:algorithm.
80:
76:
72:
68:
64:
60:
56:
52:
48:
44:
40:
37:
33:
26:
21:
1043:Tessellation
1033:Regular grid
1017:
956:Polygon mesh
871:
867:
797:
772:
768:
733:
706:
702:
633:
629:
623:
596:
592:
579:
546:
542:
536:
519:
515:
509:
478:
439:(1): 52–62.
436:
432:
388:
382:
357:
353:
347:
322:
318:
312:
277:
273:
263:
212:
208:
202:
186:
173:interpolated
166:
163:
159:
152:
135:
126:
118:
103:
88:
55:scalar field
31:
30:
966:Volume mesh
614:10316/12925
549:(2): 1–15.
1063:Categories
280:(5): 243.
155:isosurface
110:isosurface
51:isosurface
876:CiteSeerX
711:CiteSeerX
660:0097-8493
638:CiteSeerX
599:: 16–29.
563:1086-7651
495:cite book
487:897851506
453:0178-2789
296:0097-8930
217:CiteSeerX
149:Algorithm
75:metaballs
39:algorithm
789:31316542
760:35739150
678:See also
415:35739150
374:18993002
339:14395359
304:36741734
169:gradient
65:such as
43:SIGGRAPH
1001:Related
975:Methods
824:5575097
668:1930192
571:6195034
195:Sources
85:History
878:
822:
812:
787:
758:
748:
713:
666:
658:
640:
569:
561:
485:
461:526698
459:
451:
413:
403:
372:
337:
302:
294:
256:
219:
59:voxels
49:of an
902:(PDF)
820:S2CID
785:S2CID
756:S2CID
664:S2CID
589:(PDF)
567:S2CID
457:S2CID
411:S2CID
370:S2CID
335:S2CID
300:S2CID
34:is a
810:ISBN
746:ISBN
656:ISSN
559:ISSN
501:link
483:OCLC
449:ISSN
401:ISBN
292:ISSN
167:The
69:and
886:doi
802:doi
777:doi
738:doi
721:doi
648:doi
609:hdl
601:doi
551:doi
524:doi
441:doi
393:doi
362:doi
327:doi
282:doi
227:doi
71:MRI
25:MRI
1065::
884:.
872:30
870:.
818:.
808:.
783:.
773:10
771:.
754:.
744:.
719:.
707:21
705:.
662:.
654:.
646:.
634:37
632:.
607:.
595:.
591:.
565:.
557:.
545:.
518:.
497:}}
493:{{
469:^
455:.
447:.
437:11
435:.
423:^
409:.
399:.
368:.
356:.
333:.
323:47
321:.
298:.
290:.
278:22
276:.
272:.
239:^
225:.
213:21
211:.
179:.
67:CT
932:e
925:t
918:v
904:.
892:.
888::
860:.
852:.
844:.
835:.
826:.
804::
791:.
779::
762:.
740::
727:.
723::
670:.
650::
617:.
611::
603::
597:9
573:.
553::
547:8
530:.
526::
520:9
503:)
489:.
463:.
443::
417:.
395::
376:.
364::
358:2
341:.
329::
306:.
284::
233:.
229::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
